Legile lui De Morgan

Legile lui Morgan sunt identități între propuneri Logică. Au fost formulate de matematicianul britanic Augustus De Morgan (1806-1871).

Se vorbește în franceză

În logica clasică , negarea disjuncției a două propoziții este echivalentă cu conjuncția negațiilor celor două propoziții, ceea ce înseamnă că „nu (A sau B)” este identic cu „(nu A) și (nu B)” .

Încă în logica clasică , negarea conjuncției a două propoziții este echivalentă cu disjuncția negațiilor celor două propoziții, ceea ce înseamnă că „nu (A și B)” este identic cu „(nu A) sau (nu B) ".

Enunț matematic

Știind că conjuncția este exprimată prin semnul :, disjuncția este exprimată prin semnul: și se scrie negarea unei formule . $\ teren$ $\ lor$ $F$ $\ overline {{F}}$

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

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

Dintre aceste patru implicații valabile în logica clasică, trei sunt valabile în logica intuiționistă , dar nu: $\ overline {(A \ land B)} \ rightarrow (\ overline A) \ lor (\ overline B)$

Justificare

Pentru a justifica aceste formule, de exemplu, utilizați metoda semantică a tabelelor de adevăr . Reamintim că două formule sunt echivalente dacă și numai dacă au același tabel de adevăr.

$\ overline {(A \ land B)} \ leftrightarrow (\ overline A) \ lor (\ overline B)$
$LA$	$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)$
$LA$	$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

Generalizare

Afirmațiile lui De Morgan sunt generalizate la propoziții prin inducție, utilizând asociativitatea legilor și, de asemenea, dubla lor distributivitate . Întrucât cele două dovezi sunt simetrice (este suficient să înlocuim o lege cu cealaltă), oferim aici doar pentru prima lege. $nu$ $\ teren$ $\ lor$

Adevărat la rang $n = 2$
Atât de fidel la rând $nu$

$\ 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}}})$

Generalizarea acestor reguli dincolo de finit dă regulile indefinibilității cuantificatorilor universali și existențiali ai calculului predicat clasic. Cuantificatorul universal poate fi văzut ca o generalizare a conjuncției și cuantificatorul existențial poate fi văzut ca o generalizare a disjuncției (neexclusivă).

$\ forall x (\ overline {Ax}) \ leftrightarrow \ overline {\ există x (Ax)}$

$\ există x (\ overline {Ax}) \ leftrightarrow \ overline {\ forall x (Ax)}$

Și dintre aceste patru implicații clasice, doar una nu este valabilă în logica intuiționistă . $\ overline {\ forall x (Ax)} \ rightarrow \ există x (\ overline {Ax})$

În logica intuiționistă

În logica intuiționistă, avem doar o formă slăbită a legilor lui De Morgan. Există doar implicații

${\ 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)}$

Să demonstrăm prima implicație. Pentru asta trebuie să demonstrăm că, recunoscând că avem . Prin urmare, trebuie să arătăm că tragem și că tragem . Să dovedim primul. Acest lucru înseamnă a demonstra că de și de , avem . Aur . Prin urmare, este suficient să se aplice modus ponens de două ori (eliminarea implicației). ${\ 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}$ $LA$ $\ bot$ ${\ displaystyle A \ to (A \ lor B)}$