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). Affermano quanto segue:
- not (P and Q) = (not P) or (not Q)
- not (P or Q) = (not P) and (not Q)
Nella logica proposizionale possono essere formulate in vario modo:
oppure 
oppure 
e nella teoria degli insiemi così:
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 |
[modifica] Codice
In C, Java, e altri linguaggi di programmazione simili, le leggi di De Morgan possono essere scritte come:
!(p && q) == !p || !q !(p || q) == !p && !q
