Propositionell logik

Propositionell logik , propositionslogik ( lat. propositio - "påstående" [1] ) eller propositionskalkyl [2] , även nollordningslogik , är en gren av symbolisk logik som studerar komplexa påståenden som bildas av enkla och deras samband. Till skillnad från predikatlogik tar satslogik inte hänsyn till den interna strukturen av enkla påståenden, den tar bara hänsyn till med vilka konjunktioner och i vilken ordning enkla påståenden kombineras till komplexa [3] .

Trots sin betydelse och breda räckvidd är propositionell logik den enklaste logiken och har mycket begränsade medel för att studera bedömningar [2] .

Språket för propositionell logik

Språket för propositionell logik (propositionellt språk [4] ) är ett formaliserat språk utformat för att analysera den logiska strukturen hos komplexa propositioner [1] .

Syntax för propositionell logik

Inledande symboler, eller alfabetet för propositionslogikspråket [5] :

uppsättning satsvariabler (satsbokstäver):

Var=\{p,q,r...\}

propositionella bindningar (logiska konjunktioner):

Symbol	Menande
$\neg$	Negativt tecken
$\landa$ eller &	Konjunktionstecken ( "logiskt AND")
$\vee$	Disjunktionstecken ( "logiskt ELLER")
$\höger pil$	implikationstecken _

Hjälptecken: vänster parentes (, höger parentes ). [6]

Propositionsformler

En satsformel är ett ord på satslogikens språk [7] , det vill säga en ändlig sekvens av alfabetiska tecken konstruerade enligt reglerna nedan och som bildar ett fullständigt uttryck i satslogikens språk [1] .

Induktiv definition av uppsättningen av propositionella logiska formler : [4] [1] $fm$

Om , då (varje propositionsvariabel är en formel); $p\in Var$ $p\in Fm$
om är en formel, då är också en formel; $A$ $\neg A$
om och är godtyckliga formler, då är , , också formler. $A$ $B$ $(A\kil B)$ $(A\vee B)$ $(A till B)$

Det finns inga andra formler i propositionslogikens språk.

Backus-Naur-formen , som definierar syntaxen för propositionell logik, har notationen:

$A::=p\;|\;(\neg A)\;|\;(A\land A)\;|\;(A\eller A)\;|\;(A\till A )$

Stora latinska bokstäver och andra som används i definitionen av en formel tillhör inte propositionslogikens språk, utan dess metaspråk, det vill säga språket som används för att beskriva själva propositionslogikens språk. Uttryck som innehåller metallbokstäver och andra är inte propositionsformler, utan formlerscheman. Till exempel är ett uttryck ett schema som passar formler och andra [1] . $A$ $B$ $\neg A$ $(A till B)$ $(A\kil B)$ $(p\kil q)$ $(p\kil (r\vee s))$

Med avseende på vilken sekvens av alfabetiska tecken som helst i propositionslogikens språk kan man bestämma om det är en formel eller inte. Om denna sekvens kan konstrueras i enlighet med paragrafer. 1-3 formeldefinitioner så är det en formel, om inte så är det inte en formel [1] .

Konventioner för parentes

Eftersom det finns för många parenteser i formler byggda per definition, ibland inte nödvändigt för en entydig förståelse av formeln, finns det en konvention om parenteser , enligt vilken några av parenteserna kan utelämnas. Poster med utelämnade parenteser återställs enligt följande regler.

Om de yttre parenteserna utelämnas återställs de.
Om det finns två konjunktioner eller disjunktioner sida vid sida (t.ex. ) omges den längst till vänster inom hakparenteser först (det vill säga dessa konnektivitet lämnas associativa ). $A\kil B\kil C$
Om det finns olika buntar i närheten, är fästena ordnade enligt prioriteringar: och (från högsta till lägsta). $\neg ,\wedge ,\vee$ $\till$

När man talar om längden på en formel , menar de längden på den underförstådda (återställda) formeln, och inte den förkortade notationen.

Till exempel: posten betyder formel , och dess längd är 12. $A\vee B\wedge\neg C$ $(A\vee (B\kil (\neg C)))$

Formalisering och tolkning

Liksom vilket annat formaliserat språk som helst kan propositionslogikens språk betraktas som en uppsättning av alla ord som är konstruerade med hjälp av alfabetet för detta språk [8] . Propositionslogikens språk kan ses som en uppsättning av alla typer av propositionella formler [4] . Naturliga meningar kan översättas till propositionslogikens symbolspråk, där de kommer att vara formler för propositionell logik. Processen att översätta ett påstående till en formel på propositionslogikens språk kallas formalisering. Den omvända processen att ersätta specifika propositioner med propositionella variabler kallas tolkning [9] .

Axiom och slutledningsregler för ett formellt system av propositionell logik

En möjlig variant av ( hilbertsk ) axiomatisering av propositionell logik är följande system av axiom:

$A_{1}:A\högerpil (B\högerpil A)$ ;

$A_{2}:(A\högerpil (B\högerpil C))\högerpil ((A\högerpil B)\högerpil (A\högerpil C))$ ;

$A_{3}:A\kil B\högerpil A$ ;

$A_{4}:A\kil B\högerpil B$ ;

$A_{5}:A\högerpil (B\högerpil (A\kil B))$ ;

$A_{6}:A\högerpil (A\vee B)$ ;

$A_{7}:B\högerpil (A\vee B)$ ;

$A_{8}:(A\högerpil C)\högerpil ((B\högerpil C)\högerpil ((A\vee B)\högerpil C))$ ;

$A_{9}:\neg A\högerpil (A\högerpil B)$ ;

$A_{{10}}:(A\högerpil B)\högerpil ((A\högerpil \neg B)\högerpil \neg A)$ ;

$A_{{11}}:A\vee \neg A$ .

tillsammans med den enda regeln:

${\frac {A\quad (A\högerpil B)}{B}}$ ( modus ponens )

Propositionskalkylens korrekthetssats säger att alla axiom som anges ovan är tautologier , och med hjälp av modus ponens-regeln kan endast sanna påståenden erhållas från sanna påståenden. Beviset för detta teorem är trivialt och reduceras till en direkt verifiering. Mycket mer intressant är det faktum att alla andra tautologier kan erhållas från axiomen med hjälp av inferensregeln - detta är den så kallade fullständighetssatsen för propositionell logik.

Sanningstabeller för grundläggande operationer

Propositionslogikens huvuduppgift är att fastställa sanningsvärdet för en formel om sanningsvärdena för de variabler som ingår i den är givna. Sanningsvärdet för formeln i det här fallet bestäms induktivt (med de steg som användes för att konstruera formeln) med hjälp av sanningstabeller för bindningar [ 10] .

Låt vara uppsättningen av alla sanningsvärden och låt vara uppsättningen av propositionella variabler. Då kan tolkningen (eller modellen) av propositionslogikspråket representeras som en kartläggning $\mathbb {B}$ $\{0,1\}$ $Var$

M\colon Var\to \mathbb {B}

som associerar varje propositionsvariabel med ett sanningsvärde [10] . $sid$ $M(p)$

Negationspoängen ges av tabellen: $\neg sid$

$sid$	$\neg sid$
$0$	$ett$
$ett$	$0$

Värdena för dubbla logiska kopplingar (implikation), (disjunktion) och (konjunktion) definieras enligt följande: $\höger pil$ $\vee$ $\kil$

$sid$	$q$	$p\högerpil q$	$p\kil q$	$p\vee q$
$0$	$0$	$ett$	$0$	$0$
$0$	$ett$	$ett$	$0$	$ett$
$ett$	$0$	$0$	$0$	$ett$
$ett$	$ett$	$ett$	$ett$	$ett$

Identiskt sanna formler (tautologier)

En formel är identiskt sann om den är sann för alla värden av dess ingående variabler (det vill säga för vilken tolkning som helst) [11] . Följande är några välkända exempel på identiskt sanna propositionella logiska formler:

de Morgans lagar :

\neg (p\vee q)\vänsterhögerpil (\neg p\kil \neg q)

;

\neg (p\kil q)\vänsterhögerpil (\neg p\vee \neg q)

;

kontrapositionslag :

(p\högerpil q)\vänsterhögerpil (\neg q\högerpil \neg p)

;

absorptionslagar :

p\vee (p\kil q)\vänsterhögerpil sid

;

p\kil (p\vee q)\vänsterhögerpil sid

;

distributionslagar :

p\wedge (q\vee r)\vänsterhögerpil (p\wedge q)\vee (p\wedge r)

;

p\vee (q\wedge r)\vänsterhögerpil (p\vee q)\wedge (p\vee r)

Se även

Anteckningar

↑ 1 2 3 4 5 6 Chupakhin, Brodsky, 1977 , sid. 203-205.
↑ 1 2 Kondakov, 1971 , artikel "Propositionskalkyl".
↑ NFE, 2010 .
↑ 1 2 3 Gerasimov, 2011 , sid. 13.
↑ Voishvillo, Degtyarev, 2001 , sid. 91-94.
↑ Ershov Yu. L. , Palyutin E. A. Matematisk logik. - M. , Nauka , 1979. - sid. 24
↑ Edelman, 1975 , sid. 130.
↑ Edelman, 1975 , sid. 128.
↑ Igoshin, 2008 , sid. 32.
↑ 1 2 Gerasimov, 2011 , sid. 17-19.
↑ Gerasimov, 2011 , sid. 19.

Litteratur

Kondakov N. I. Logisk ordbok / Gorsky D. P. - M . : Nauka, 1971. - 656 sid.
Edelman S. L. Matematisk logik. - M . : Högre skola, 1975. - 176 sid.
Chupakhin I. Ya., Brodsky IN Formell logik. - Leningrad: Leningrad University Publishing House , 1977. - 357 s.
Voishvillo E.K. , Degtyarev M.G. Logic. - M. : VLADOS-PRESS, 2001. - 528 sid. — ISBN 5-305-00001-7 .
Igoshin VI Matematisk logik och teori för algoritmer. - 2:a uppl., stereotyp .. - M . : Publishing Center "Academy", 2008. - 448 sid. - ISBN 978-5-7695-4593-1 .
A. S. Karpenko. Propositionell logik // New Philosophical Encyclopedia : i 4 volymer / föregående. vetenskaplig-ed. råd av V. S. Stepin . — 2:a uppl., rättad. och ytterligare - M . : Tanke , 2010. - 2816 sid.
Gerasimov AS Kurs i matematisk logik och teori om beräkningsbarhet . - St Petersburg. : Förlaget "LEMA", 2011. - 284 sid. - ISBN 978-5-98709-292-7 .

Ordböcker och uppslagsverk	Stor ryss Britannica (online) Britannica (online) Universalis
I bibliografiska kataloger	GND : 4136098-9 NKC : ph127455

Logik

Filosofi • Semantik • Syntax • Historia

Logiska grupper

klassisk logik	Aristotelisk logik propositionell logik Första beställningslogik Andra ordningens logik högre ordningslogik
matematisk logik	mängdteori Modellteori Beräkningsbarhetsteori Bevisteori och konstruktiv matematik Linjär logik formellt system naturlig slutsats Sekvenskalkyl Algebra av logik Relevant logik Deontisk logik intuitionistisk logik Lambek kalkyl
Icke-klassisk logik	intuitionism rolig logik Substrukturell logik logik Beskrivningslogik Flervärdig logik Logisk syntes Bindande logik Temporal logik Modal logik ( Hybrid logik ) epistemisk logik
Filosofisk logik	Kritiskt tänkande informell logik deduktiva resonemang

Komponenter

Bortförande (logik)
Sannolikhet
påstående
Avdrag / Induktion / Traduktion
Verklighet
induktivt resonemang
slutledning
boolesk konstant
Sann
logiskt följa
Logisk form
Nödvändiga och tillräckliga förutsättningar
Beskrivning
Definition
Utbyte
Paket
Kontrovers ( Antinomy )
Syntetisk bedömning / Analytisk bedömning
Länk

Lista över booleska symboler