Algebra af logik

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 7. november 2021; checks kræver 26 redigeringer .

Logikkens algebra ( propositionalgebra ) er et afsnit af matematisk logik , der studerer logiske operationer på propositioner [1] . Oftest antages det, at udsagn kun kan være sande eller falske, det vil sige, at den såkaldte binære eller binære logik bruges i modsætning til for eksempel ternær logik .

Dens grundlægger er J. Boole , en engelsk matematiker og logiker , som baserede sin logiske doktrin på analogien mellem algebra og logik. Logikkens algebra blev det første system af matematisk logik, hvor algebraisk symbolik begyndte at blive anvendt på logiske konklusioner i operationer med begreber betragtet fra siden af deres bind. Boole satte sig selv til opgave at løse logiske problemer ved hjælp af de metoder, der anvendes i algebra . Han forsøgte at udtrykke enhver dom i form af ligninger med symboler, hvor logiske love fungerer, svarende til algebralovene.

Efterfølgende blev forbedringen af logikkens algebra udført af W.S. ..Ch,PoretskyP.S.,SchroederE.,Jevons B. Russell bidrog og gav, sammen med A. Whitehead , matematisk logik et moderne udseende; I. I. Zhegalkin , hvis fortjeneste var den videre udvikling af klasseregningen og en betydelig forenkling af teorien om operationer af logisk addition; VI Glivenko tog emnet for logikkens algebra langt ud over studiet af volumetriske operationer med begreber.

Logikkens algebra i sin moderne fremstilling beskæftiger sig med studiet af operationer med udsagn, det vil sige med sætninger, der kun er karakteriseret ved én kvalitet - sandhedsværdien (sand, falsk). I logikkens klassiske algebra kan et udsagn samtidigt kun have én af to sandhedsværdier: "sand" eller "falsk". Logikkens algebra udforsker også udsagn - funktioner, der kan antage værdierne "sand" og "falsk", afhængigt af hvilken værdi der vil blive givet til variablen inkluderet i udsagnet - funktion.

Definition

De grundlæggende elementer, som logikkens algebra opererer på, er propositioner .

Udsagn er konstrueret over sættet { , , , , , }, hvor er et ikke-tomt sæt, på hvis elementer tre operationer er defineret : $B$ $\likke$ $\jord$ $\lor$ $0$ $en$ $B$

\likke

negation ( unær operation ),

\jord

konjunktion ( binær ),

\lor

disjunktion ( binær ),

og logisk nul 0 og logisk enhed 1 er konstanter .

Navne bruges også:

En disjunkt er en propositionsformel , der er en disjunktion af en eller flere bogstaver (for eksempel , ). $x_{1}\lor \neg x_{2}\lor x_{4}$
Et konjunkt er en propositionsformel , der er en konjunktion af en eller flere bogstaver (f.eks . ). $x_{1}\land \neg x_{2}\land x_{4}$

Den unære negationsoperator i formlerteksten er enten i form af et ikon før operanden ( ) eller som en bindestreg over operanden ( ), som er mere kompakt, men generelt mindre mærkbar. $\likke x$ ${\bar {x}}$

Aksiomer

${\bar {\bar {x))}=x$ , involutivitet af negation , lov om fjernelse af dobbelt negation
$x\lor {\bar {x}}=1$
$\x\lor 1=1$
$\x\lor x=x$
$\x\lor 0=x$
$\ x\land {\bar {x}}=0$
$\x\land x=x$
$\x\land 0=0$
$\x\land 1=x$

Logiske operationer

Det enkleste og mest udbredte eksempel på et sådant algebraisk system er konstrueret ved hjælp af sættet B, som kun består af to elementer:

B

= { Falsk, Sand }

Som regel identificeres Falsk i matematiske udtryk med et logisk nul, og Sandhed identificeres med en logisk enhed, og operationerne negation (NOT), konjunktion (AND) og disjunktion (OR) er defineret i den sædvanlige betydning. Det er let at vise, at der på et givet sæt B kan specificeres fire unære og seksten binære relationer, og alle kan opnås gennem overlejring af tre udvalgte operationer.

Baseret på dette matematiske værktøjssæt studerer propositionel logik propositioner og prædikater . Yderligere operationer introduceres også, såsom ækvivalens ("hvis og kun hvis"), implikation ("derfor"), modulo to-addition (" eksklusiv eller "), Schaeffers slag , Pierces pil og andre. $\venstrehøjrepil$ $\højre pil$ $\plus$ $\midt$ $\pil ned$

Propositionel logik har fungeret som det vigtigste matematiske værktøj i skabelsen af computere. Det konverteres let til bitlogik : sandheden af et udsagn er angivet med en bit (0 - FALSK, 1 - SAND); så får operationen betydningen at trække fra enhed; - ikke-modulær tilføjelse; & - multiplikationer; - lighed; - i bogstavelig forstand addition modulo 2 (eksklusiv Eller - XOR); - ikke summens overlegenhed over 1 (det vil sige = ). $\neg$ $\lor$ $\venstrehøjrepil$ $\plus$ $\midt$ $EN$ $\midt$ $B$ $(A+B)<=1$

Efterfølgende blev boolsk algebra generaliseret fra propositionel logik ved at indføre aksiomer, der er karakteristiske for propositionel logik. Dette gjorde det muligt at overveje for eksempel logikken i qubits , trepartslogik (når der er tre muligheder for sandheden af et udsagn: "sandt", "falsk" og "udefineret"), kompleks logik osv.

Egenskaber for logiske operationer

Kommutativitet :. _ $x\circ y=y\circ x,\circ \i \{\land ,\lor ,\oplus ,\sim ,\mid ,\downarrow \}$
Idempotens :. _ $x\cirkel x=x,\cirkel \i \{\land ,\lor \}$
Associativitet :. _ $(x\circ y)\circ z=x\circ (y\circ z),\circ \i \{\land ,\lor ,\oplus ,\sim \}$
Fordelingen af konjunktioner og disjunktioner med hensyn til henholdsvis disjunktion, konjunktion og sum modulo to:
- $x\land (y\lor z)=(x\land y)\lor (x\land z)$ ,
- $x\lor (y\land z)=(x\lor y)\land (x\lor z)$ ,
- $x\land (y\oplus z)=(x\land y)\oplus (x\land z)$ .
De Morgans love :
- ${\overline {x\land y}}={\bar {x}}\lor {\bar {y}}$ ,
- ${\overline {x\lor y}}={\bar {x}}\land {\bar {y}}$ .
Absorptionslove:
- $x\land (x\lor y)=x$ ,
- $x\lor (x\land y)=x$ .
Andre (1):
- $x\land {\bar {x}}=x\land 0=x\oplus x=0$ .
- $x\lor {\bar {x}}=x\lor 1=x\sim x=x\højrepil x=1$ .
- $x\lor x=x\land x=x\land 1=x\lor 0=x\oplus 0=x$ .
- $x\oplus 1=x\højrepil 0=x\sim 0=x\midt x=x\pil ned x={\bar {x))$ .
- ${\bar {\bar {x))}=x$ , involutivitet af negation , lov om fjernelse af dobbelt negation .
Andre (2):
- $x\oplus y=x\land {\bar {y}}\lor {\bar {x}}\land y=(x\lor y)\land ({\bar {x}}\lor {\bar { y)))$ .
- $x\sim y={\overline {x\oplus y}}=1\oplus x\oplus y=x\land y\lor {\bar {x}}\land {\bar {y}}=(x\ lor {\bar {y)))\land ({\bar {x))\lor y)$ .
- $x\højrepil y={\bar {x}}\lor y=x\land y\oplus x\oplus 1$ .
- $x\lor y=x\oplus y\oplus x\land y$ .
Andre (3) (Tilføjelse af de Morgans love ):
- $x\mid y={\overline {x\land y}}={\bar {x}}\lor {\bar {y}}$ .
- $x\downarrow y={\overline {x\lor y}}={\bar {x}}\land {\bar {y}}$ .

Der er metoder til at forenkle den logiske funktion: f.eks. Carnot map , Quine-McCluskey metode

Historie

Videnskaben om "logikkens algebra" skylder sin eksistens til den engelske matematiker George Boole , som studerede propositionel logik . Det første russiske kursus om logikkens algebra blev leveret af PS Poretsky ved Kazan State University .

Se også

Noter

↑ Algebra of logic // Great Soviet Encyclopedia : [i 30 bind] / kap. udg. A. M. Prokhorov . - 3. udg. - M . : Sovjetisk encyklopædi, 1969-1978.

Ordbøger og encyklopædier

I bibliografiske kataloger
BNE : XX4576349 BNF : 119793249 GND : 4146280-4 J9U : 987007293933005171 LCCN : sh85003429 NDL : 00560863

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