Teoremi di De Morgan
Da Wikipedia, l'enciclopedia libera.
I teoremi di De Morgan, o leggi di De Morgan, prendono il nome dal matematico e logico britannico Augustus De Morgan e sono relativi alla logica booleana. Sono utilizzati per l'analisi di circuiti logici (elettrici, elettronici, pneumatici, comunque digitali, cioè ON-OFF).
I due teoremi sono duali:
Il primo si enuncia dicendo che se un elemento non appartiene ad 
, allora o non appartiene ad A, o non appartiene a B o non appartiene ad entrambi.
Il secondo teorema si enuncia dicendo che se un elemento non appartiene ad A + B, allora non appartiene ad A e non appartiene a B.
L'immediata generalizzazione a un numero n di variabili:
Nella logica proposizionale possono essere formulate in vario modo:
oppure 
oppure 
e nella teoria degli insiemi così:
oppure 
oppure 
In pratica esse descrivono il comportamento dei connettivi logici (AND e OR) quando una negazione viene tolta da o inserita in una formula in parentesi. Se si raccoglie la negazione fuori parentesi o la si distribuisce tra i termini in parentesi, il connettivo si trasforma nel suo opposto.
Espresse in forma tabellare :
| ¬(W+Y) = (¬W) * (¬Y) |
| ¬(W*Y) = (¬W) + (¬Y) |
| 1 + W = 1 |
| 0 * W = 0 |
| 0 + W = W |
| 1 * W = W |
Indice |
[modifica] Dimostrazione tramite tabelle della verità
[modifica] Primo teorema
| a | b | ¬a | ¬b | a ∨ b | ¬(a ∨ b) | ¬a ∧ ¬b |
| V | V | F | F | V | F | F |
| V | F | F | V | V | F | F |
| F | V | V | F | V | F | F |
| F | F | V | V | F | V | V |
[modifica] Secondo teorema
| a | b | ¬a | ¬b | a ∧ b | ¬(a ∧ b) | ¬a ∨ ¬b |
| V | V | F | F | V | F | F |
| V | F | F | V | F | V | V |
| F | V | V | F | F | V | V |
| F | F | V | V | F | V | V |
