Sostieni il corso con una donazione PayPal

(PayPal.Me/ManoloVenturin)

Ordine gerarchico e tautologie nelle proposizioni logiche

Obiettivo (corso Analisi Matematica 1)

  • Logica: Ordine gerarchico
  • Tautologia
  • Prima e seconda legge di De Morgan
  • Principio di contrapposizione
  • VIDEO
  • PDF

    • Riassunto operatori logici

    • Negazione: $\neg P$
    • Congiunzione: $P \land Q$
    • Disgiunzione: $P \lor Q$
    • Implicazione: $P \implies Q$
    • Doppia implicazione: $P \iff Q$

    Ordine gerarchico

    Definizione (dal più prioritario al meno prioritario)
    $$\neg\ ,\ \land\ , \ \lor\ , \ \implies\ ,\ \iff$$

    Aiuta la scrittura di espressioni logiche con poche parentesi (facili da leggere)


    Esempio

    • $P \lor (\neg P)$ diventa $P \lor \neg P$
    • $(P \implies Q) \iff ((\neg P) \lor Q)$ diventa $P \implies Q \iff \neg P \lor Q$


    Tautologia

    Definizione
    Tautologia: una proposizione i cui valori di verità sono tutti uguali a vero


    Esempio 1

    Dimostrare che $$P \lor \neg P$$ è una tautologia

    Dimostrazione

    $P$ $\neg P$ $\quad P \lor \neg P\quad$
    $V$ $F$ $V$
    $F$ $V$ $V$

    Esempio 2 (prima legge di De Morgan)

    Dimostrare che $$\neg(P\lor Q) \;\iff\; \neg P \land \neg Q$$

    Dimostrazione

    $P$ $Q$ $P\lor Q$ $\neg(P\lor Q)$ $\neg P$ $\neg Q$ $\neg P \land \neg Q$
    $V$ $V$ $V$ $F$ $F$ $F$ $F$
    $V$ $F$ $V$ $F$ $F$ $V$ $F$
    $F$ $V$ $V$ $F$ $V$ $F$ $F$
    $F$ $F$ $F$ $V$ $V$ $V$ $V$

    Esempio 3 (seconda legge di De Morgan)

    Dimostrare che $$\neg(P\land Q) \;\iff\; \neg P \lor \neg Q$$

    Dimostrazione

    $P$ $Q$ $P\land Q$ $\neg(P\land Q)$ $\neg P$ $\neg Q$ $\neg P \lor \neg Q$
    $V$ $V$ $V$ $F$ $F$ $F$ $F$
    $V$ $F$ $F$ $V$ $F$ $V$ $V$
    $F$ $V$ $F$ $V$ $V$ $F$ $V$
    $F$ $F$ $F$ $V$ $V$ $V$ $V$

    Esempio 4 (principio di contrapposizione)

    Dimostrare che $$P \implies Q \;\iff\; \neg Q \implies \neg P$$

    Dimostrazione

    $P$ $Q$ $P \implies Q$ $\neg P$ $\neg Q$ $\neg Q \implies \neg P$
    $V$ $V$ $V$ $F$ $F$ $V$
    $V$ $F$ $F$ $F$ $V$ $F$
    $F$ $V$ $V$ $V$ $F$ $V$
    $F$ $F$ $V$ $V$ $V$ $V$

    Esempio 5

    Dire se l'espressione logica $$P \land \neg(Q\land R) \implies P \lor (Q\land R)$$ è una tautologia

    Soluzione

    Cerchiamo di semplificare i casi prima di costruire al tabella di verità completa

    Nell'espressione logica se $P$ è falso allora si ha che l'ipotesi è falsa da cui segue che l'implicazione è vera (per ogni tesi)

    Nel caso in cui $P \;\operatorname{è\; VERO}$, l'espressione si riscrive come $$ \neg(Q\land R) \implies \operatorname{VERO} \quad \iff \quad (Q\land R) \lor \operatorname{VERO} \quad \iff \quad \operatorname{VERO} $$

    Quindi è sempre vera

    • Se $P \operatorname{è\;VERO}$ allora per qualuque valore di $R$ e $P$ l'implicazione è vera

    • Rimane fuore il calso $P \operatorname{è\; FALSO}$ (analogo)

    Tabella di verità

    Variabile valore...
    $P$ $F$ $F$ $F$ $F$ $V$ $V$ $V$ $V$
    $Q$ $F$ $F$ $V$ $V$ $F$ $F$ $V$ $V$
    $R$ $F$ $V$ $F$ $V$ $F$ $V$ $F$ $V$
    Espressione $V$ $V$ $V$ $V$ $V$ $V$ $V$ $V$

    Quindi possiamo concludere che è una tautologia


    Proprietà

    • $P \implies Q \iff \neg P \lor Q$ (equivalenza implicazione)
    • $\neg(P\lor Q) \iff \neg P \land \neg Q$ (prima legge di De Morgan)
    • $\neg(P\land Q) \iff \neg P \lor \neg Q$ (seconda legge di De Morgan)
    • $P \lor (Q \land R) \iff (P \lor Q) \land (P \lor R)$ (distributiva della disgiunzione sulla congiunzione)
    • $P \land (Q \lor R) \iff (P \land Q) \lor (P \land R)$ (distributiva della congiunzione sulla disgiunzione)

    Curiosità

    La funzione logica NAND ("not and") con la tavola di verità

    $P$ $Q$ $P\land Q\quad$ $\operatorname{NAND}$
    $V$ $V$ $V$ $F$
    $V$ $F$ $F$ $V$
    $F$ $V$ $F$ $V$
    $F$ $F$ $F$ $V$

    permette di scrivere ogni connettivo logico.

    Ad esempio, il $\operatorname{NOT}(x)$ è $\operatorname{NAND}(x,x)$

    Nell'ambito dell'elettronica ogni funzione logica è possibile costruirla attraverso delle porte $\operatorname{NAND}$ avendo così da gestire solo un tipo di tecnologia costruttiva


    Ricorda di sostenere questo progetto con una donazione (PayPal.Me/ManoloVenturin).