Leggi di De Morgan
Esistono due leggi di De Morgan che trattano la negazione della congiunzione (∧) e della disgiunzione (∨).
- Negare una congiunzione (∧) equivale a fare una disgiunzione (∨) tra le negazioni $$
\neg (A \land B) \equiv \neg A \vee \neg B $$ - Negare una disgiunzione (∨) equivale a fare una congiunzione (∧) tra le negazioni. $$ \neg (A \vee B) \equiv \neg A \land \neg B $$
Le leggi di De Morgan sono simmetriche perché sono due facce della stessa medaglia: entrambe spiegano come la negazione interagisce con gli operatori logici.
In ciascuna legge la negazione dell’espressione ribalta sia il tipo di operatore (da ∨ a ∧ o viceversa) e nega ogni singola proposizione.
In altre parole, negare un “e” diventa un “o” tra le negazioni, e negare un “o” diventa un “e” tra le negazioni.
A cosa servono? Sono fondamentali non solo perché i valori di verità coincidono, ma perché permettono di semplificare espressioni logiche, di progettare circuiti elettronici o di costruire negazioni corrette in linguaggio naturale.
Prima Legge di De Morgan
La prima legge afferma che negare una congiunzione (∧) equivale a fare una disgiunzione (∨) tra le due parti negate. $$
\neg (A \land B) \equiv \neg A \vee \neg B $$
Ad esempio, considero due proposizioni $ A $ e $ B $.
La tabella di verità delle espressioni è
$$
\begin{array}{|c|c|c|c|c|c|c|}
\hline
A & B & A \land B & \neg (A \land B) & \neg A & \neg B & \neg A \vee \neg B \\
\hline
V & V & V & F & F & F & F \\
\hline
V & F & F & V & F & V & V \\
\hline
F & V & F & V & V & F & V \\
\hline
F & F & F & V & V & V & V \\
\hline
\end{array}
$$
Come si può notare, le espressioni $ \neg (A \land B) $ e $ \neg A \vee \neg B $ hanno gli stessi valori di verità.
Esempio. Negare “Piove e fa freddo” significa “Non piove o non fa freddo”.
Seconda Legge di De Morgan
La seconda legge afferma che negare una disgiunzione equivale a fare una congiunzione tra le due parti negate. $$ \neg (A \vee B) \equiv \neg A \land \neg B $$
Ad esempio, considero due proposizioni $ A $ e $ B $.
La tabella di verità delle espressioni è
$$
\begin{array}{|c|c|c|c|c|c|c|}
\hline
A & B & A \vee B & \neg (A \vee B) & \neg A & \neg B & \neg A \land \neg B \\
\hline
V & V & V & F & F & F & F \\
\hline
V & F & V & F & F & V & F \\
\hline
F & V & V & F & V & F & F \\
\hline
F & F & F & V & V & V & V \\
\hline
\end{array}
$$
Le espressioni $ \neg (A \vee B) $ e $ \neg A \land \neg B $ hanno gli stessi valori di verità.
Esempio. Negare “Piove o fa freddo” significa “Non piove e non fa freddo”. Quindi, posso lasciare a casa sia l'ombrello che il cappotto.
E così via.
