Tautologie e contraddizioni: cosa sono le leggi di De Morgan
In questa lezione impari a riconoscere e usare la tautologia (una frase composta che è sempre vera), la contraddizione (una frase composta che è sempre falsa) e le leggi di De Morgan, che servono per negare la congiunzione di due proposizioni e per negare la disgiunzione di due proposizioni.
- Tautologia: è una frase composta che è sempre vera. Esempio: “Il mio iPad funziona o non funziona”, “L’orologio ha le lancette oppure no” sono tautologie.
- Contraddizione: è una frase composta che è sempre falsa. Esempio: “Il mio iPad funziona e non funziona”, “L’orologio ha le lancette e non le ha” sono contraddizioni.
- Le leggi di De Morgan uniscono negazione, congiunzione e disgiunzione e sono due: una per negare la congiunzione di due proposizioni, una per negare la disgiunzione di due proposizioni.
Vediamo insieme in dettaglio queste nozioni, evidenziando la loro importanza e fornendo esempi pratici del loro utilizzo.
Tautologie
Le tautologie sono proposizioni sempre vere. Ad esempio:
- £$A$£: “La macchina o parte o non parte.”;
- £$B$£: “L’orologio ha le lancette oppure no.”;
- £$C$£: “La lampadina o è accesa oppure no.”.
Come le rappresento formalmente con espressioni logiche? Consideriamo la proposizione
£$A$£: “La macchina o parte o non parte”
essa è costituita da due predicati, ovvero da due proposizioni logiche:
- £$P$£: “La macchina parte.”;
- £$Q$£: “La macchina non parte.”.
Legate dalla particella ‘o’: £$ P \vee Q$£. Inoltre, £$ Q= \overline{P}$£. Quindi posso riscrivere £$ A= P \vee \overline{P}$£.
Allora, costruendo la tavola di verità:
se £$P$£ è vera, £$ \overline{P}$£ è falsa e quindi £$ P \vee \overline{P}$£ è vera;
se £$P$£ è falsa, £$\overline{P}$£ è vera e quindi la proposizione composta è di nuovo vera.
Quindi, la £$P \vee \overline{P}$£ è sempre vera! Allora è una tautologia!
£$\begin{array}{|c|c|c|}\hline P & \overline P & P \vee \overline P\\ \hline V & F & V \\ \hline F & V & V\\ \hline\end{array}$£.
Contraddizioni
Le contraddizioni sono proposizioni composte sempre false. Ad esempio:
- £$A$£: “Il telefonino è acceso e non è acceso”
- £$B$£: “Il mio iPad funziona e non funziona”
- £$ C$£: ‘‘Il mio gatto è nero e non è nero’’
Sono proposizioni sempre false. Come le rappresento con espressioni logiche?
£$C$£:”Il mio gatto è nero e non è nero.”
£$C$£ è costituita da due predicati, ovvero due proposizioni logiche:
- £$P$£: “Il mio gatto è nero’’
- £$Q$£: “Il mio gatto non è nero”
Legate dalla particella ‘e’: £$ P \wedge Q$£
Inoltre, £$ Q=\overline{P}$£. Quindi posso riscrivere £$C= P \wedge \overline{P}$£
Allora, costruendo la tavola di verità:
se £$P$£ è vera, £$\overline{P}$£ è falsa e quindi £$P \wedge \overline{P}$£ è falsa;
se £$P$£ è falsa, £$\overline{P}$£ è vera e quindi la proposizione composta è ancora falsa.
Quindi, la £$P \wedge \overline{P}$£ è effettivamente sempre falsa! Allora è una contraddizione!
£$\begin{array}{|c|c|c|}\hline P & \overline P & P \wedge \overline P \\ \hline V & F & F \\ \hline F & V & F \\ \hline\end{array}$£
Leggi di De Morgan
Esistono delle leggi in Logica che uniscono negazione, congiunzione e disgiunzione: sono le Leggi di De Morgan. Le leggi di De Morgan sono due:
- una per negare la congiunzione di due proposizioni
- una per negare la disgiunzione di due proposizioni.
E si scrivono così:
£$\overline{(p \wedge q)}= \overline{p} \vee \overline{q}$£ £$\overline{(p \vee q)}= \overline{p} \wedge \overline{q} $£
Quindi:
La prima legge di De Morgan ci dice che negare la congiunzione di due proposizioni equivale a fare la disgiunzione delle due proposizioni negate.
La seconda legge di De Morgan ci dice che negare la disgiunzione di due proposizioni equivale a fare la congiunzione delle due proposizioni negate.
Prima legge di De Morgan
Esempio della prima legge di De Morgan:
£$P$£: “Il leone ha la criniera’’ £$ \rightarrow \overline{P}$£ : “ Il leone non ha la criniera.’’
£$Q$£: “Il leone ha £$4$£ zampe’’ £$\rightarrow \overline{Q}$£ : “ Il leone non ha £$4$£ zampe.’’
Allora £$P \wedge Q$£: “Il leone ha £$4$£ zampe e la criniera.’’
Se facciamo la negazione, otteniamo:
£$ \overline{(P \wedge Q)}$£: “Non è che il leone ha £$4$£ zampe e ha la criniera.’’
Il secondo membro della prima legge di De Morgan invece è £$ \overline{P} \vee \overline{Q}$£: “Il leone non ha quattro zampe o non ha la criniera.’’
Ovvero le due espressioni sono equivalenti.
Seconda legge di De Morgan
Esempio della seconda legge di De Morgan:
£$P$£: “Nel mio gelato ci sono le fragole.’’ £$ \rightarrow \overline{P}$£: “Nel mio gelato non ci sono le fragole’’
£$Q$£: “Nel mio gelato c’è il cioccolato.’’ £$ \rightarrow \overline{Q}$£: “Nel mio gelato non c’è il cioccolato.’’
£$P \vee Q$£: “Nel mio gelato ci sono le fragole o il cioccolato.’’
Se facciamo la negazione, otteniamo:
£$\overline{(P \vee Q)}$£: “Non è che nel mio gelato ci sono le fragole o il cioccolato.’’
Mentre il secondo membro della legge è
£$\overline{P} \wedge \overline{Q}$£ : “Nel mio gelato non ci sono le fragole e nel mio gelato non c’è cioccolato!’’