Le leggi di De Morgan

Le leggi di Morgan sono identità tra logiche di proposta . Sono stati formulati dal matematico britannico Augustus De Morgan (1806-1871).

Parlato in francese

Nella logica classica , la negazione della disgiunzione di due proposizioni equivale alla congiunzione delle negazioni delle due proposizioni, il che significa che “non (A o B)” è identico a “(non A) e (non B)” .

Sempre nella logica classica , la negazione della congiunzione di due proposizioni equivale alla disgiunzione delle negazioni delle due proposizioni, il che significa che “non (A e B)” è identico a “(non A) o (non B) ”.

Dichiarazione matematica

Sapendo che la congiunzione è espressa dal segno :, la disgiunzione è espressa dal segno: e la negazione di una formula si scrive . $\ terra$ $\ lor$ $F$ $\ sopra {{F}}$

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

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

Di queste quattro implicazioni valide nella logica classica, tre sono valide nella logica intuizionista , ma non: $\ overline {(A \ land B)} \ rightarrow (\ overline A) \ lor (\ overline B)$

Giustificazione

Per giustificare queste formule, è ad esempio, utilizzare il metodo semantica delle tabelle di verità . Ricordiamo che due formule sono equivalenti se e solo se hanno la stessa tabella di verità.

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

Generalizzazione

Le affermazioni di De Morgan sono generalizzate alle proposizioni per induzione, usando l' associatività delle leggi e la loro doppia distributività . Poiché le due dimostrazioni sono simmetriche (basta sostituire una legge con l'altra), diamo qui solo quello per la prima legge. $non$ $\ terra$ $\ lor$

Fedele al rango $n = 2$
Così fedele alla riga $non$

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

La generalizzazione di queste regole oltre il finito dà le regole di indefinibilità dei quantificatori universali ed esistenziali del calcolo classico dei predicati . Il quantificatore universale può essere visto come una generalizzazione della congiunzione e il quantificatore esistenziale può essere visto come una generalizzazione della disgiunzione (non esclusiva).

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

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

E di queste quattro implicazioni classiche, solo una non è valida nella logica intuizionista . $\ overline {\ forall x (Ax)} \ rightarrow \ esiste x (\ overline {Ax})$

Nella logica intuizionista

Nella logica intuizionista, abbiamo solo una forma indebolita delle leggi di De Morgan. Ci sono solo le implicazioni

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

Dimostriamo la prima implicazione. Per questo dobbiamo dimostrare che ammettendo di avere . Dobbiamo quindi dimostrare che si spara e che si spara . Dimostriamo il primo. Ciò equivale a mostrare che de e de , abbiamo . Oro . È quindi sufficiente applicare due volte il modus ponens (eliminazione dell'implicazione). ${\ displaystyle \ lnot (A \ lor B)}$ ${\ displaystyle \ non A \ land \ non B}$ ${\ displaystyle \ lnot (A \ lor B)}$ ${\ displaystyle A \ a \ bot}$ ${\ displaystyle \ lnot (A \ lor B)}$ ${\ displaystyle B \ a \ bot}$ ${\ displaystyle (A \ lor B) \ a \ bot}$ $A$ $\ bot$ ${\ displaystyle A \ a (A \ lor B)}$