Equivalenze logiche e leggi di De Morgan

Due formule sono equivalenti ($\equiv$) se hanno la stessa tavola di verità: in ogni riga assumono lo stesso valore. Le equivalenze permettono di riscrivere una condizione complicata in una più semplice, senza cambiarne il significato.

Proprietà — Equivalenze logiche fondamentali

• Doppia negazione: $\lnot(\lnot p)\equiv p$.
• Leggi di De Morgan: $\lnot(p\land q)\equiv \lnot p\lor\lnot q$ e $\lnot(p\lor q)\equiv \lnot p\land\lnot q$.
• Implicazione come “or”: $p\Rightarrow q\equiv \lnot p\lor q$.
• Contrapposizione: $p\Rightarrow q\equiv \lnot q\Rightarrow\lnot p$ (alla base delle dimostrazioni per assurdo).
• Doppia implicazione: $p\Leftrightarrow q\equiv (p\Rightarrow q)\land(q\Rightarrow p)$.

Le leggi di De Morgan dicono che negare una congiunzione equivale a fare la disgiunzione delle negazioni, e viceversa: la negazione “scambia” $\land$ e $\lor$. Le ritroveremo, identiche, come leggi che scambiano intersezione e unione tra gli insiemi.

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Contrapposizione · Equivalenza logica · Leggi di de morgan
Competenze: Dimostrare
Persone: Augustus De Morgan