De Morganovy zákony

The Morgan zákony jsou identity mezi návrhy logiky. Byly formulovány britským matematikem Augustem De Morganem (1806-1871).

Mluveno francouzsky

V klasické logice je negace disjunkce dvou výroků ekvivalentní spojení negací dvou výroků, což znamená, že „ne (A nebo B)“ je totožné s „(ne A) a (ne B)“ .

Stále v klasické logice je negace spojení dvou výroků ekvivalentní disjunkci negací dvou výroků, což znamená, že „ne (A a B)“ je totožné s „(ne A) nebo (ne B) “.

Matematický výrok

S vědomím, že spojka je vyjádřena znaménkem :, je disjunkce vyjádřena znaménkem: a je napsána negace vzorce . $\ přistát$ $\ lor$ $F$ $\ overline {{F}}$

$\ overline {(A \ land B)} \ leftrightarrow (\ overline {A}) \ lor (\ overline {B})$

$\ overline {(A \ lor B)} \ leftrightarrow (\ overline {A}) \ land (\ overline {B})$

Z těchto čtyř implikací platných v klasické logice jsou tři platné v logice intuice , ale ne: $\ overline {(A \ land B)} \ rightarrow (\ overline A) \ lor (\ overline B)$

Odůvodnění

Ospravedlnit tyto vzorce, to je například pomocí metody sémantiku z pravdivostní tabulky . Připomínáme, že dva vzorce jsou ekvivalentní právě tehdy, pokud mají stejnou tabulku pravdivosti.

$\ overline {(A \ land B)} \ leftrightarrow (\ overline A) \ lor (\ overline B)$
$NA$	$B$	$A \ land B$	$\ overline {(A \ land B)}$	$\ overline {A}$	$\ overline B$	$(\ overline A) \ lor (\ overline B)$
0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

$\ overline {(A \ lor B)} \ leftrightarrow (\ overline A) \ land (\ overline B)$
$NA$	$B$	$A \ lor B$	$\ overline {(A \ lor B)}$	$\ overline A$	$\ overline B$	$(\ overline A) \ land (\ overline B)$
0	0	0	1	1	1	1
0	1	1	0	1	0	0
1	0	1	0	0	1	0
1	1	1	0	0	0	0

Zobecnění

De Morganova prohlášení jsou generalizována na propozice indukcí, s využitím asociativity zákonů a jejich dvojí distribuce . Jelikož jsou dva důkazy symetrické (stačí nahradit jeden zákon druhým), uvádíme zde pouze to pro první zákon. $ne$ $\ přistát$ $\ lor$

Pravda, hodnost $n = 2$
Takže věrný řadě $ne$

$\ overline {(A_ {1} \ land A_ {2} \ land ... \ land A_ {n} \ land A _ {{n + 1}})}$

$\ leftrightarrow \ overline {((A_ {1} \ land A_ {2} \ land ... \ land A_ {n}) \ land A _ {{n + 1}})}$

$\ leftrightarrow (\ overline {(A_ {1} \ land A_ {2} \ land ... \ land A_ {n})}) \ lor (\ overline {A _ {{n + 1}}})$

$\ leftrightarrow ((\ overline {A_ {1}}) \ lor (\ overline {A_ {2}}) \ lor ... \ lor (\ overline {A_ {n}})) \ lor (\ overline {A_ {{n + 1}}})$

Zobecnění těchto pravidel nad konečnou hodnotu dává pravidla neurčitosti univerzálních a existenciálních kvantifikátorů klasického predikátového počtu . Na univerzální kvantifikátor lze pohlížet jako na zobecnění konjunkce a na existenční kvantifikátor lze chápat jako zobecnění (neexkluzivní) disjunkce.

$\ forall x (\ overline {Ax}) \ leftrightarrow \ overline {\ existuje x (Ax)}$

$\ existuje x (\ overline {Ax}) \ leftrightarrow \ overline {\ pro všechny x (Ax)}$

A z těchto čtyř klasických implikací není v intuitivní logice platná pouze jedna . $\ overline {\ forall x (Ax)} \ rightarrow \ existuje x (\ overline {Ax})$

V intuitivní logice

V intuicionistické logice máme pouze oslabenou formu zákonů De Morgana. Existují pouze důsledky

${\ displaystyle \ lnot (A \ lor B) \ to (\ lnot A \ land \ lnot B)}$
${\ displaystyle (\ lnot A \ land \ lnot B) \ to \ lnot (A \ lor B)}$
${\ displaystyle (\ lnot A \ lor \ lnot B) \ to \ lnot (A \ land B)}$

Ukažme první implikaci. K tomu musíme prokázat, že připustíme, že máme . Musíme tedy ukázat, že střílíme a že střílíme . Ukažme si první. To se rovná prokázání toho, že de a de máme . Zlato . Stačí tedy použít modus ponens dvakrát (eliminace implikace). ${\ displaystyle \ lnot (A \ lor B)}$ ${\ displaystyle \ lnot A \ land \ lnot B}$ ${\ displaystyle \ lnot (A \ lor B)}$ ${\ displaystyle A \ to \ bot}$ ${\ displaystyle \ lnot (A \ lor B)}$ ${\ displaystyle B \ to \ bot}$ ${\ displaystyle (A \ lor B) \ to \ bot}$ $NA$ $\ bot$ ${\ displaystyle A \ to (A \ lor B)}$