Algebra logiky

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 7. listopadu 2021; kontroly vyžadují 26 úprav .

Algebra logiky ( propositional algebra ) je úsek matematické logiky , který studuje logické operace s výroky [1] . Nejčastěji se předpokládá, že výroky mohou být pouze pravdivé nebo nepravdivé, to znamená, že se používá tzv. binární či binární logika, na rozdíl např. od ternární logiky .

Jeho zakladatelem je J. Boole , anglický matematik a logik , který založil svou logickou doktrínu na analogii mezi algebrou a logikou. Algebra logiky se stala prvním systémem matematické logiky, ve kterém se algebraická symbolika začala uplatňovat na logické závěry v operacích s pojmy uvažovanými ze strany jejich objemů. Boole si dal za úkol řešit logické problémy pomocí metod používaných v algebře . Jakýkoli úsudek se snažil vyjádřit formou rovnic se symboly, v nichž fungují logické zákony, podobné zákonům algebry.

Následně zdokonalení algebry logiky provedli W. .Ch,S. PoretskyP.,SchroederE.,JevonsS. B. Russell přispěl , dávat, spolu s A. Whitehead , matematická logika moderní vzhled; I. I. Zhegalkin , jehož zásluhou byl další rozvoj kalkulu tříd a výrazné zjednodušení teorie operací logického sčítání; VI Glivenko posunul předmět algebry logiky daleko za hranice studia objemových operací s pojmy.

Algebra logiky se ve svém moderním podání zabývá studiem operací s výroky, tedy s větami, které se vyznačují pouze jedinou kvalitou - pravdivostní hodnotou (pravda, nepravda). V klasické algebře logiky může mít výrok současně pouze jednu ze dvou pravdivostních hodnot: „pravda“ nebo „nepravda“. Algebra logiky také zkoumá příkazy - funkce, které mohou nabývat hodnot "true" a "false" v závislosti na tom, jakou hodnotu bude dána proměnné obsažené v příkazu - funkce.

Definice

Základní prvky, na kterých algebra logiky pracuje, jsou výroky .

Příkazy jsou konstruovány nad množinou { , , , , , }, kde je neprázdná množina, na jejíchž prvcích jsou definovány tři operace : $B$ $\lne$ $\přistát$ $\lor$ $0$ $jeden$ $B$

\lne

negace ( unární operace ),

\přistát

konjunkce ( binární ),

\lor

disjunkce ( binární ),

a logická nula 0 a logická jednotka 1 jsou konstanty .

Také používaná jména:

Disjunkce je výroková formule , která je disjunkcí jednoho nebo více literálů (například , ). $x_{1}\lor \neg x_{2}\nebo x_{4}$
Konjunkce je výroková formule , která je konjunkcí jednoho nebo více literálů (např . ). $x_{1}\země \neg x_{2}\země x_{4}$

Operátor unární negace v textu vzorců je buď ve formě ikony před operandem ( ) nebo jako pomlčka nad operandem ( ), což je kompaktnější, ale obecně méně nápadné. $\lne x$ ${\bar {x}}$

Axiomy

${\bar {\bar {x))}=x$ , involutivita negace , zákon odstranění dvojité negace
$x\lor {\bar {x}}=1$
$\x\nebo 1=1$
$\x\nebo x=x$
$\x\nebo 0=x$
$\ x\land {\bar {x}}=0$
$\x\land x=x$
$\x\land 0=0$
$\x\land 1=x$

Logické operace

Nejjednodušší a nejpoužívanější příklad takového algebraického systému je konstruován pomocí množiny B, která se skládá pouze ze dvou prvků:

B

= { False, True }

Zpravidla se v matematických výrazech False ztotožňuje s logickou nulou a Pravda se ztotožňuje s logickou jednotkou a operace negace (NOT), konjunkce (AND) a disjunkce (OR) jsou definovány v obvyklém smyslu. Je snadné ukázat, že na dané množině B lze zadat čtyři unární a šestnáct binárních relací a všechny je získat superpozicí tří vybraných operací.

Na základě této matematické sady nástrojů studuje výroková logika výroky a predikáty . Jsou také zavedeny další operace, jako je ekvivalence ("pokud a pouze tehdy"), implikace ("proto"), sčítání modulo dva (" exkluzivní nebo "), Schaefferův tah , Pierceova šipka a další. $\leftrightarrow$ $\šipka doprava$ $\oplus$ $\střední$ $\šipka dolů$

Výroková logika sloužila jako hlavní matematický nástroj při vytváření počítačů. Lze jej snadno převést do bitové logiky: pravdivost výroku je označena jedním bitem (0 - FALSE, 1 - TRUE); pak operace nabývá významu odečítání od jednoty; - nemodulární sčítání; & - násobení; - rovnost; - v doslovném smyslu sčítání modulo 2 (exkluzivní Or - XOR); - ne nadřazenost součtu nad 1 (tj. = ). $\neg$ $\lor$ $\leftrightarrow$ $\oplus$ $\střední$ $A$ $\střední$ $B$ $(A+B)<=1$

Následně byla Booleova algebra zobecněna z výrokové logiky zavedením axiomů charakteristických pro výrokovou logiku. To umožnilo uvažovat například logiku qubitů , tripartitní logiku (když existují tři možnosti pro pravdivost výroku: „pravda“, „nepravda“ a „nedefinováno“), komplexní logika atd.

Vlastnosti logických operací

Komutativnost : . $x\circ y=y\circ x,\circ \in \{\land ,\lor ,\oplus ,\sim ,\mid ,\downarrow \}$
Impotence : . $x\circ x=x,\circ \in \{\land ,\lor \}$
Asociativita : . $(x\circ y)\circ z=x\circ (y\circ z),\circ \in \{\land ,\lor ,\oplus ,\sim \}$
Distributivita konjunkcí a disjunkcí vzhledem k disjunkci, konjunkci a součtu modulo dva, v tomto pořadí:
- $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 Morganovy zákony :
- ${\overline {x\land y}}={\bar {x}}\nebo {\bar {y}}$ ,
- ${\overline {x\lor y}}={\bar {x}}\land {\bar {y}}$ .
Absorpční zákony:
- $x\land (x\lor y)=x$ ,
- $x\lor (x\land y)=x$ .
Ostatní (1):
- $x\land {\bar {x}}=x\land 0=x\oplus x=0$ .
- $x\nebo {\bar {x}}=x\nebo 1=x\sim x=x\šipka doprava x=1$ .
- $x\nebo x=x\land x=x\land 1=x\nebo 0=x\plus 0=x$ .
- $x\oplus 1=x\šipka doprava 0=x\sim 0=x\střed x=x\šipka dolů x={\bar {x))$ .
- ${\bar {\bar {x))}=x$ , involutivita negace , zákon odstranění dvojité negace .
Ostatní (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)))\země ({\bar {x))\lor y)$ .
- $x\rightarrow y={\bar {x}}\lor y=x\land y\oplus x\oplus 1$ .
- $x\lor y=x\oplus y\oplus x\land y$ .
Ostatní (3) (Přidání de Morganových zákonů ):
- $x\mid y={\overline {x\land y}}={\bar {x}}\nebo {\bar {y}}$ .
- $x\downarrow y={\overline {x\lor y}}={\bar {x}}\land {\bar {y}}$ .

Existují metody pro zjednodušení logické funkce: např. Carnotova mapa , metoda Quine-McCluskey

Historie

Věda o "algebře logiky" vděčí za svou existenci anglickému matematikovi George Boole , který studoval výrokovou logiku . První ruský kurz algebry logiky přednesl PS Poretsky na Kazaňské státní univerzitě .

Viz také

Poznámky

↑ Algebra logiky // Velká sovětská encyklopedie : [ve 30 svazcích] / kap. vyd. A. M. Prochorov . - 3. vyd. - M .: Sovětská encyklopedie, 1969-1978.

Slovníky a encyklopedie

V bibliografických katalozích
BNE : XX4576349 BNF : 119793249 GND : 4146280-4 J9U : 987007293933005171 LCCN : sh85003429 NDL : 00560863

Logika

Filosofie • Sémantika • Syntaxe • Historie

Logické skupiny

klasická logika	Aristotelská logika výroková logika Logika prvního řádu Logika druhého řádu logika vyššího řádu
matematická logika	teorie množin Teorie modelu Teorie vyčíslitelnosti Důkazová teorie a konstruktivní matematika Lineární logika formální systém přirozený závěr Sekvenční počet Algebra logiky Relevantní logika Deontická logika intuicionistická logika Lambekův počet
Neklasická logika	intuicionismus fuzzy logika Substrukturální logika logika Popisná logika Vícehodnotová logika Logická syntéza Závazná logika Časová logika Modální logika ( Hybrid logic ) epistemická logika
Filosofická logika	Kritické myšlení neformální logika deduktivní uvažování

Komponenty

Seznam booleovských symbolů