Algebra av logik

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 7 november 2021; kontroller kräver 26 redigeringar .

Logikens algebra ( propositionalgebra ) är en del av matematisk logik som studerar logiska operationer på propositioner [1] . Oftast antas att satser bara kan vara sanna eller falska, det vill säga att den så kallade binära eller binära logiken används, till skillnad från till exempel ternär logik .

Dess grundare är J. Boole , en engelsk matematiker och logiker , som baserade sin logiska doktrin på analogin mellan algebra och logik. Logikens algebra blev det första systemet för matematisk logik där algebraisk symbolik började tillämpas på logiska slutsatser i operationer med begrepp betraktade från sidan av deras volymer. Boole satte sig själv i uppgift att lösa logiska problem med de metoder som används i algebra . Han försökte uttrycka alla bedömningar i form av ekvationer med symboler, där logiska lagar fungerar, liknande algebras lagar.

Därefter genomfördes förbättringen av logikens algebra av W.S. ..Ch,PoretskyP.S.,SchroederE.,Jevons B. Russell bidrog och gav, tillsammans med A. Whitehead , matematisk logik ett modernt utseende; I. I. Zhegalkin , vars förtjänst var vidareutvecklingen av klasskalkylen och en betydande förenkling av teorin om operationer för logisk addition; VI Glivenko tog ämnet för logikens algebra långt bortom studiet av volymetriska operationer med begrepp.

Logikens algebra i sin moderna presentation handlar om studiet av operationer med påståenden, det vill säga meningar som kännetecknas av endast en egenskap - sanningsvärdet (sant, falskt). I logikens klassiska algebra kan ett påstående samtidigt bara ha ett av två sanningsvärden: "sant" eller "falskt". Logikens algebra utforskar också uttalanden - funktioner som kan anta värdena "true" och "false" beroende på vilket värde som kommer att ges till variabeln som ingår i satsen - funktion.

Definition

De grundläggande elementen som logikens algebra verkar på är propositioner .

Påståenden konstrueras över mängden { , , , , , }, där är en icke-tom mängd, på vars element tre operationer definieras : $B$ $\linte$ $\landa$ $\lor$ $0$ $ett$ $B$

\linte

negation ( enär operation ),

\landa

konjunktion ( binär ),

\lor

disjunktion ( binär ),

och logisk noll 0 och logisk enhet 1 är konstanter .

Namn som också används:

En disjunkt är en propositionsformel som är en disjunktion av en eller flera bokstaver (till exempel , ). $x_{1}\lor \neg x_{2}\lor x_{4}$
En konjunkt är en propositionsformel som är en konjunktion av en eller flera bokstaver (t.ex. ). $x_{1}\land \neg x_{2}\land x_{4}$

Den unära negationsoperatorn i formlertexten är antingen i form av en ikon före operanden ( ) eller som ett streck ovanför operanden ( ), som är mer kompakt, men i allmänhet mindre märkbar. $\linte x$ ${\bar {x}}$

Axiom

${\bar {\bar {x))}=x$ , involutivitet av negation , lagen om avlägsnande av dubbel 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$

Logiska operationer

Det enklaste och mest använda exemplet på ett sådant algebraiskt system är konstruerat med hjälp av mängden B, som bara består av två element:

B

= { Falskt, Sant }

Som regel, i matematiska uttryck, identifieras False med en logisk nolla, och Sanning identifieras med en logisk enhet, och operationerna negation (NOT), konjunktion (AND) och disjunktion (OR) definieras i vanlig mening. Det är lätt att visa att på en given mängd B kan fyra unära och sexton binära relationer specificeras, och alla kan erhållas genom överlagring av tre valda operationer.

Baserat på denna matematiska verktygslåda studerar propositionell logik propositioner och predikat . Ytterligare operationer introduceras också, såsom ekvivalens ("om och bara om"), implikation ("därför"), modulo två-addition (" exklusiv eller "), Schaeffers slag , Pierces pil och andra. $\vänster högerpil$ $\höger pil$ $\ plus$ $\mitten$ $\nedåtpil$

Propositionell logik har fungerat som det huvudsakliga matematiska verktyget vid skapandet av datorer. Den omvandlas lätt till bitlogik : sanningen i ett påstående indikeras med en bit (0 - FALSK, 1 - TRUE); då får operationen betydelsen av att subtrahera från enhet; - icke-modulär tillägg; & - multiplikationer; - jämlikhet; - i bokstavlig mening addition modulo 2 (exklusiv Eller - XOR); - inte summans överlägsenhet över 1 (det vill säga = ). $\neg$ $\lor$ $\vänster högerpil$ $\ plus$ $\mitten$ $A$ $\mitten$ $B$ $(A+B)<=1$

Därefter generaliserades boolesk algebra från propositionell logik genom att introducera axiom som är karakteristiska för propositionell logik. Detta gjorde det möjligt att överväga till exempel logiken för qubits , trepartslogik (när det finns tre alternativ för sanningen i ett påstående: "sant", "falskt" och "odefinierat"), komplex logik, etc.

Egenskaper för logiska operationer

Kommutativitet : . $x\circ y=y\circ x,\circ \in \{\land ,\lor ,\oplus ,\sim ,\mid ,\downarrow \}$
Idempotens : . $x\circ x=x,\circ \i \{\land ,\lor \}$
Associativitet :. _ $(x\circ y)\circ z=x\circ (y\circ z),\circ \in \{\land ,\lor ,\oplus ,\sim \}$
Fördelningen av konjunktioner och disjunktioner med avseende på disjunktion, konjunktion och summa modulo två:
- $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 lagar :
- ${\overline {x\land y}}={\bar {x}}\lor {\bar {y}}$ ,
- ${\overline {x\lor y}}={\bar {x}}\land {\bar {y}}$ .
Absorptionslagar:
- $x\land (x\lor y)=x$ ,
- $x\lor (x\land y)=x$ .
Övriga (1):
- $x\land {\bar {x}}=x\land 0=x\oplus x=0$ .
- $x\lor {\bar {x}}=x\lor 1=x\sim x=x\högerpil x=1$ .
- $x\lor x=x\land x=x\land 1=x\lor 0=x\oplus 0=x$ .
- $x\oplus 1=x\högerpil 0=x\sim 0=x\midt x=x\nedåtpil x={\stapel {x))$ .
- ${\bar {\bar {x))}=x$ , negationens involutivitet , lagen om borttagande av dubbel negation .
Övriga (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ögerpil y={\bar {x}}\lor y=x\land y\oplus x\oplus 1$ .
- $x\lor y=x\oplus y\oplus x\land y$ .
Andra (3) (Tillägg av de Morgans lagar ):
- $x\mid y={\overline {x\land y}}={\bar {x}}\lor {\bar {y}}$ .
- $x\downarrow y={\overline {x\lor y}}={\bar {x}}\land {\bar {y}}$ .

Det finns metoder för att förenkla logikfunktionen: t.ex. Carnot map , Quine-McCluskey-metoden

Historik

Vetenskapen om "logikens algebra" har sin existens att tacka för den engelske matematikern George Boole , som studerade propositionell logik . Den första ryska kursen om logikens algebra levererades av PS Poretsky vid Kazan State University .

Se även

Anteckningar

↑ Logikens algebra // Stora sovjetiska encyklopedin : [i 30 volymer] / kap. ed. A. M. Prokhorov . - 3:e uppl. - M . : Soviet Encyclopedia, 1969-1978.

Ordböcker och uppslagsverk

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

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