Propositionel logik

Propositionel logik , propositionel logik ( lat. propositio - "udsagn" [1] ) eller propositionel regning [2] , også nul-ordens logik, er et afsnit af symbolsk logik , der studerer komplekse udsagn dannet ud fra simple og deres relationer. I modsætning til prædikatlogik tager propositionel logik ikke hensyn til den interne struktur af simple udsagn, den tager kun højde for med hvilke konjunktioner og i hvilken rækkefølge simple udsagn kombineres til komplekse [3] .

På trods af dens betydning og brede rækkevidde er propositionel logik den enkleste logik og har meget begrænsede midler til undersøgelse af domme [2] .

Propositionslogikkens sprog

Propositionslogikkens sprog (propositionssprog [4] ) er et formaliseret sprog designet til at analysere den logiske struktur af komplekse propositioner [1] .

Syntaks for propositionel logik

Indledende symboler eller alfabetet for propositionslogiksproget [5] :

sæt af propositionelle variabler (propositionelle bogstaver):

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

propositionelle bindeord (logiske konjunktioner):

Symbol	Betyder
$\neg$	Negativt tegn
$\jord$ eller &	Konjunktionstegn ( "logisk OG")
$\vee$	Disjunktionstegn ( "logisk ELLER")
$\højre pil$	implikationstegn _

Hjælpetegn: venstre parentes (, højre parentes). [6]

Propositionsformler

En propositionsformel er et ord i propositionslogikkens sprog [7] , det vil sige en endelig række af alfabetiske tegn konstrueret efter reglerne angivet nedenfor og danner et komplet udtryk i propositionslogikkens sprog [1] .

Induktiv definition af sættet af propositionelle logiske formler : [4] [1] $fm$

Hvis , så (hver propositionel variabel er en formel); $p\in Var$ $p\in Fm$
hvis er en formel, så er det også en formel; $EN$ $\neg A$
hvis og er vilkårlige formler, så er , , også formler. $EN$ $B$ $(A\kile B)$ $(A\vee B)$ $(A\til B)$

Der er ingen andre formler i propositionslogikkens sprog.

Backus-Naur-formen , som definerer syntaksen for propositionel logik, har notationen:

$A::=p\;|\;(\neg A)\;|\;(A\land A)\;|\;(A\lor A)\;|\;(A\til A )$

Store latinske bogstaver og andre, der bruges i definitionen af en formel, tilhører ikke propositionslogikkens sprog, men dets metasprog, det vil sige det sprog, der bruges til at beskrive selve propositionslogikkens sprog. Udtryk, der indeholder metalletter og andre, er ikke propositionelle formler, men formler. For eksempel er et udtryk et skema, der passer til formler og andre [1] . $EN$ $B$ $\neg A$ $(A\til B)$ $(A\kile B)$ $(p\ kile q)$ $(p\ kile (r\vee s))$

Med hensyn til enhver sekvens af alfabetiske tegn i propositionslogikkens sprog, kan man afgøre, om det er en formel eller ej. Hvis denne sekvens kan konstrueres i overensstemmelse med stk. 1-3 formeldefinitioner, så er det en formel, hvis ikke, så er det ikke en formel [1] .

Konventioner i parentes

Da der er for mange parenteser i formler bygget per definition, nogle gange ikke nødvendigt for en entydig forståelse af formlen, er der en konvention om parenteser , ifølge hvilken nogle af parenteserne kan udelades. Registreringer med udeladte parenteser gendannes i henhold til følgende regler.

Hvis de ydre parenteser udelades, gendannes de.
Hvis der er to konjunktioner eller disjunktioner side om side (f.eks. ), så er den del til venstre omgivet af parenteser først (det vil sige, at disse bindeled efterlades associative ). $A\kile B\kile C$
Hvis der er forskellige bundter i nærheden, er beslagene arrangeret efter prioriteter: og (fra højeste til laveste). $\neg ,\kile ,\vee$ $\til$

Når man taler om længden af en formel , mener de længden af den underforståede (genoprettede) formel og ikke den forkortede notation.

For eksempel: indtastningen betyder formel , og dens længde er 12. $A\vee B\wedge\neg C$ $(A\vee (B\kile (\neg C)))$

Formalisering og fortolkning

Som ethvert andet formaliseret sprog kan propositionslogikkens sprog betragtes som et sæt af alle ord, der er konstrueret ved hjælp af dette sprogs alfabet [8] . Propositionslogikkens sprog kan ses som et sæt af alle slags propositionelle formler [4] . Natursproglige sætninger kan oversættes til propositionslogikkens symbolsprog, hvor de vil være formler for propositionel logik. Processen med at oversætte et udsagn til en formel på propositionslogikkens sprog kaldes formalisering. Den omvendte proces med at substituere specifikke propositioner med propositionelle variable kaldes fortolkning [9] .

Aksiomer og slutningsregler for et formelt system af propositionel logik

En mulig variant af den ( hilbertske ) aksiomatisering af propositionel logik er følgende system af aksiomer:

$A_{1}:A\højrepil (B\højrepil A)$ ;

$A_{2}:(A\højrepil (B\højrepil C))\højrepil ((A\højrepil B)\højrepil (A\højrepil C))$ ;

$A_{3}:A\kile B\højrepil A$ ;

$A_{4}:A\kile B\højrepil B$ ;

$A_{5}:A\højrepil (B\højrepil (A\kile B))$ ;

$A_{6}:A\højrepil (A\vee B)$ ;

$A_{7}:B\højrepil (A\vee B)$ ;

$A_{8}:(A\højrepil C)\højrepil ((B\højrepil C)\højrepil ((A\vee B)\højrepil C))$ ;

$A_{9}:\neg A\højrepil (A\højrepil B)$ ;

$A_{{10}}:(A\højrepil B)\højrepil ((A\højrepil \neg B)\højrepil \neg A)$ ;

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

sammen med den eneste regel:

${\frac {A\quad (A\rightarrow B)}{B}}$ ( modus ponens )

Propositionalregningens korrekthedssætning siger, at alle ovenstående aksiomer er tautologier , og ved at bruge modus ponens-reglen kan kun sande påstande opnås fra sande påstande. Beviset for denne teorem er trivielt og reduceres til en direkte verifikation. Meget mere interessant er det faktum, at alle andre tautologier kan opnås fra aksiomer ved hjælp af inferensreglen - dette er den såkaldte fuldstændighedssætning for propositionel logik.

Sandhedstabeller over grundlæggende operationer

Hovedopgaven for propositionel logik er at etablere sandhedsværdien af en formel, hvis sandhedsværdierne for de variable, der er inkluderet i den, er givet. Sandhedsværdien af formlen i dette tilfælde bestemmes induktivt (med de trin, der blev brugt til at konstruere formlen) ved hjælp af sandhedstabeller over forbindelser [10] .

Lad være sættet af alle sandhedsværdier og lad være sættet af propositionelle variabler. Så kan fortolkningen (eller modellen) af det propositionelle logiske sprog repræsenteres som en kortlægning $\mathbb {B}$ $\{0,1\}$ $Var$

M\colon Var\to \mathbb {B}

som forbinder hver propositionel variabel med en sandhedsværdi [10] . $s$ $M(p)$

Negationsscoren er givet af tabellen: $\negp$

$s$	$\negp$
$0$	$en$
$en$	$0$

Værdierne af dobbelte logiske forbindelser (implikation), (disjunktion) og (konjunktion) er defineret som følger: $\højre pil$ $\vee$ $\kile$

$s$	$q$	$p\højrepil q$	$p\ kile q$	$p\vee q$
$0$	$0$	$en$	$0$	$0$
$0$	$en$	$en$	$0$	$en$
$en$	$0$	$0$	$0$	$en$
$en$	$en$	$en$	$en$	$en$

Identisk sande formler (tautologier)

En formel er identisk sand, hvis den er sand for alle værdier af dens bestanddele (det vil sige for enhver fortolkning) [11] . Følgende er et par velkendte eksempler på identisk sande propositionelle logiske formler:

de Morgans love :

\neg (p\vee q)\venstrehøjrepil (\neg p\kile \neg q)

;

\neg (p\kile q)\venstrehøjrepil (\neg p\vee \neg q)

;

modsætningslov :

(p\højrepil q)\venstrepil (\neg q\højrepil \neg p)

;

absorptionslove :

p\vee (p\kile q)\venstrehøjrepil s

;

p\kile (p\vee q)\venstrehøjrepil s

;

distribution love :

p\wedge (q\vee r)\venstrehøjrepil (p\wedge q)\vee (p\wedge r)

;

p\vee (q\wedge r)\venstrehøjrepil (p\vee q)\wedge (p\vee r)

Se også

Noter

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

Litteratur

Kondakov N. I. Logisk ordbog / Gorsky D. P. - M . : Nauka, 1971. - 656 s.
Edelman S. L. Matematisk logik. - M . : Højere skole, 1975. - 176 s.
Chupakhin I. Ya., Brodsky IN Formel logik. - Leningrad: Leningrad University Publishing House , 1977. - 357 s.
Voishvillo E. K. , Degtyarev M. G. Logic. - M. : VLADOS-PRESS, 2001. - 528 s. — ISBN 5-305-00001-7 .
Igoshin VI Matematisk logik og teori om algoritmer. - 2. udg., stereotype .. - M . : Publishing Center "Academy", 2008. - 448 s. - ISBN 978-5-7695-4593-1 .
A. S. Karpenko. Propositionel logik // New Philosophical Encyclopedia : i 4 bind / prev. videnskabeligt udg. råd fra V. S. Stepin . — 2. udg., rettet. og yderligere - M . : Tanke , 2010. - 2816 s.
Gerasimov AS Kursus i matematisk logik og teori om beregningsevne . - Sankt Petersborg. : Forlaget "LEMA", 2011. - 284 s. - ISBN 978-5-98709-292-7 .

Ordbøger og encyklopædier	Stor russer Britannica (online) Britannica (online) Universalis
I bibliografiske kataloger	GND : 4136098-9 NKC : ph127455

Logikker

Filosofi • Semantik • Syntaks • Historie

Logiske grupper

klassisk logik	Aristotelisk logik propositionel logik Første ordens logik Anden ordens logik højere ordens logik
matematisk logik	mængdeteori Modelteori Beregnelighedsteori Bevisteori og konstruktiv matematik Lineær logik formelt system naturlig konklusion Sekvensberegning Algebra af logik Relevant logik Deontisk logik intuitionistisk logik Lambek regning
Ikke-klassisk logik	intuitionisme sløret logik Substrukturel logik logik Beskrivelseslogik Flerværdilogik Logisk syntese Bindende logik Tidsmæssig logik Modal logik ( Hybrid logik ) epistemisk logik
Filosofisk logik	Kritisk tænkning uformel logik deduktiv ræsonnement

Komponenter

Bortførelse (logik)
Sandsynlighed
udmelding
Fradrag / Induktion / Traduktion
Virkelighed
Induktiv begrundelse
slutning
boolsk konstant
Rigtigt
logisk følge
Logisk form
Nødvendige og tilstrækkelige betingelser
Beskrivelse
Definition
Substitution
Pakke
Kontrovers ( Antinomy )
Syntetisk dømmekraft / Analytisk dømmekraft
Link

Liste over booleske symboler