1 Implicazione ed equivalenza tautologica

Il simbolo ≡\equiv indica l’equivalenza, mentre ⇒\Rightarrow indica l’implicazione. Per costruire dimostrazioni interessano in particolare le equivalenze e le implicazioni che sono tautologie.

Nelle tabelle di verità, 11 indica il vero e 00 il falso.

1.1 Connettivi e convenzioni di lettura

In queste note P≡QP\equiv Q è il connettivo bicondizionale, indicato anche con P⇔QP\Leftrightarrow Q. L’equivalenza tautologica richiede che questo bicondizionale sia vero in ogni interpretazione. Analogamente, la formula P⇒QP\Rightarrow Q può essere vera o falsa; è un’implicazione tautologica soltanto se è sempre vera.

I connettivi fondamentali si leggono come segue: ¬Pnon PP∧QP e QP∨QP oppure Q (anche entrambe)P⇒Qse P, allora QP≡QP se e solo se Q\begin{array}{c|l} \neg P&\text{non }P\\ P\land Q&P\text{ e }Q\\ P\lor Q&P\text{ oppure }Q\text{ (anche entrambe)}\\ P\Rightarrow Q&\text{se }P\text{, allora }Q\\ P\equiv Q&P\text{ se e solo se }Q \end{array} Si usano parentesi per delimitare premesse, conclusioni e sottoformule. In assenza di parentesi, si valuta prima la negazione, poi la congiunzione, poi la disgiunzione, infine l’implicazione e il bicondizionale.

Una tabella riassume i valori dei connettivi binari: PQP∧QP∨QP⇒QP≡Q000011010110100100111111\begin{array}{cc|cccc} P&Q&P\land Q&P\lor Q&P\Rightarrow Q&P\equiv Q\\\hline 0&0&0&0&1&1\\ 0&1&0&1&1&0\\ 1&0&0&1&0&0\\ 1&1&1&1&1&1 \end{array} Inoltre ¬0=1\neg0=1 e ¬1=0\neg1=0. In particolare, ¬(P⇒Q)≡(P∧¬Q).\neg(P\Rightarrow Q)\equiv(P\land\neg Q).

1.2 Implicazione tautologica

Definizione 1. Una formula PP implica tautologicamente una formula QQ se P⇒QP\Rightarrow Q è una tautologia.

Si parte da una premessa e si giunge a una conclusione. Nell’implicazione tautologica, la relazione di conseguenza vale indipendentemente dai valori assegnati alle variabili proposizionali: ogni assegnazione che rende vera la premessa rende vera anche la conclusione.

Esempio 1. La formula (A∨B)⇒C(A\lor B)\Rightarrow C non è una tautologia. Infatti, se almeno una tra AA e BB è vera e CC è falsa, l’implicazione è falsa.

Esempio 2. La formula (A∧B)⇒A(A\land B)\Rightarrow A è una tautologia, come mostra la tabella: ABA∧B(A∧B)⇒A0001010110011111\begin{array}{cc|c|c} A&B&A\land B&(A\land B)\Rightarrow A\\\hline 0&0&0&1\\ 0&1&0&1\\ 1&0&0&1\\ 1&1&1&1 \end{array}

Si calcola prima il valore della congiunzione e poi quello dell’implicazione. Il connettivo principale si valuta per ultimo, perché determina il valore dell’intera formula.

1.3 Equivalenza tautologica

Definizione 2. Due formule PP e QQ sono tautologicamente equivalenti se e solo se P≡QP\equiv Q è una tautologia.

Esempio 3. L’equivalenza A≡BA\equiv B non è una tautologia. Per verificarlo basta considerare le prime due righe della tabella: ABA≡B001010\begin{array}{cc|c} A&B&A\equiv B\\\hline 0&0&1\\ 0&1&0 \end{array}

La seconda riga fornisce già un’assegnazione che rende falsa la formula; non occorre proseguire per escludere che sia una tautologia.

2 Strumenti di dimostrazione

Per stabilire se una formula è una tautologia, è soddisfacibile oppure è una contraddizione, si possono utilizzare i seguenti strumenti:

  1. Studiare la negazione della formula. Se la negazione è falsa per ogni assegnazione, la formula iniziale è una tautologia. Questo procedimento può richiedere la trasformazione della formula.

  2. Costruire la tabella di verità.

  3. Svolgere una dimostrazione mediante leggi e regole di inferenza, senza ricorrere al solo procedimento meccanico della tabella.

Un’interpretazione assegna un valore di verità alle variabili proposizionali. Per esempio: I1={A↦1, B↦0, C↦0}.I_1=\{A\mapsto 1,\ B\mapsto 0,\ C\mapsto 0\}.

La tabella di verità permette di riconoscere una tautologia controllando che la formula sia vera in ogni riga. Per dimostrare la soddisfacibilità è invece sufficiente trovare un’interpretazione che la renda vera.

In una dimostrazione si possono usare:

  • un insieme di leggi, ossia tautologie già dimostrate, come le leggi commutative e distributive, da richiamare nei passaggi;

  • un insieme di regole di inferenza, che consentono di ricavare conclusioni dalle premesse, come il principio di sostituzione.

3 Principio di sostituzione dell’uguaglianza

Il principio di sostituzione consente di sostituire un’espressione con un’altra a essa uguale all’interno di un’espressione più ampia.

Esempio 4. Si vuole dimostrare l’identità (a+b)(a−b)=a2−b2.(a+b)(a-b)=a^2-b^2.

Si procede applicando le proprietà delle operazioni.

  1. Si utilizza la proprietà distributiva: (x+y)z=xz+yz.(x+y)z=xz+yz. Con la sostituzione {x↦a, y↦b, z↦a−b}\{x\mapsto a,\ y\mapsto b,\ z\mapsto a-b\} si ottiene (a+b)(a−b)=a(a−b)+b(a−b).(a+b)(a-b)=a(a-b)+b(a-b).

  2. Si applica nuovamente la proprietà distributiva, separatamente ai due addendi. Utilizzando z(x+y)=zx+zyz(x+y)=zx+zy, le sostituzioni sono rispettivamente {z↦a, x↦a, y↦−b},{z↦b, x↦a, y↦−b}.\begin{aligned} &\{z\mapsto a,\ x\mapsto a,\ y\mapsto -b\},\\ &\{z\mapsto b,\ x\mapsto a,\ y\mapsto -b\}. \end{aligned} Pertanto a(a−b)=a⋅a−a⋅b,b(a−b)=b⋅a−b⋅b,\begin{aligned} a(a-b)&=a\cdot a-a\cdot b,\\ b(a-b)&=b\cdot a-b\cdot b, \end{aligned} e quindi a(a−b)+b(a−b)=a⋅a−a⋅b+b⋅a−b⋅b.a(a-b)+b(a-b)=a\cdot a-a\cdot b+b\cdot a-b\cdot b.

  3. Si applicano la definizione di quadrato, x⋅x=x2x\cdot x=x^2, e la commutatività del prodotto: a⋅a−a⋅b+b⋅a−b⋅b=a2−ab+ab−b2.a\cdot a-a\cdot b+b\cdot a-b\cdot b=a^2-ab+ab-b^2.

  4. Si utilizza la cancellazione dei termini opposti: a2−ab+ab−b2=a2−0−b2.a^2-ab+ab-b^2=a^2-0-b^2.

  5. Poiché 00 è l’elemento neutro della somma, a2−0−b2=a2−b2.a^2-0-b^2=a^2-b^2.

Si conclude che (a+b)(a−b)=a2−b2(a+b)(a-b)=a^2-b^2.

4 Principio di sostituzione dell’equivalenza

Proposizione 1. Se PP e QQ sono tautologicamente equivalenti, sostituendo una qualsiasi occorrenza di PP in una formula RR con QQ si ottiene una formula tautologicamente equivalente a RR.

Indicando con R[P/Q]R[P/Q] la formula ottenuta sostituendo in RR le occorrenze di PP con QQ, la regola si esprime come ⊨(P≡Q)⊨(R≡R[P/Q]).\frac{\models(P\equiv Q)}{\models\bigl(R\equiv R[P/Q]\bigr)}. Il simbolo ⊨\models davanti a una formula indica che essa è vera in ogni interpretazione. La regola richiede dunque un’equivalenza tautologica come premessa.

La sostituzione può essere applicata anche a tutte le occorrenze di PP.

Conoscere le leggi di equivalenza permette di condurre dimostrazioni evitando di costruire ogni volta tabelle di verità, che possono diventare lunghe.

5 Leggi per l’equivalenza

5.1 Riflessività

P≡P.P\equiv P.

PP≡P1101\begin{array}{c|c} P&P\equiv P\\\hline 1&1\\ 0&1 \end{array}

5.2 Simmetria

(P≡Q)≡(Q≡P).(P\equiv Q)\equiv(Q\equiv P).

PQP≡QQ≡P(P≡Q)≡(Q≡P)00111010011000111111\begin{array}{cc|cc|c} P&Q&P\equiv Q&Q\equiv P&(P\equiv Q)\equiv(Q\equiv P)\\\hline 0&0&1&1&1\\ 0&1&0&0&1\\ 1&0&0&0&1\\ 1&1&1&1&1 \end{array}

5.3 Associatività

((P≡Q)≡R)≡(P≡(Q≡R)).\bigl((P\equiv Q)\equiv R\bigr) \equiv\bigl(P\equiv(Q\equiv R)\bigr).

Con tre variabili vi sono 23=82^3=8 assegnazioni possibili. Le righe possono essere disposte in qualsiasi ordine, purché siano presenti tutte le assegnazioni.

Per rendere leggibile la tabella, poniamo U=((P≡Q)≡R),V=(P≡(Q≡R)).U=((P\equiv Q)\equiv R),\qquad V=(P\equiv(Q\equiv R)).U=((P≡Q)≡R),V=(P≡(Q≡R)).\begin{gathered}U=((P\equiv Q)\equiv R),\\[0.5em]V=(P\equiv(Q\equiv R)).\end{gathered}

PQRP≡QQ≡RUVU≡V0001100100110111010001110110100110001111101000011101000111111111\begin{array}{ccc|cc|cc|c} P&Q&R&P\equiv Q&Q\equiv R&U&V&U\equiv V\\\hline 0&0&0&1&1&0&0&1\\ 0&0&1&1&0&1&1&1\\ 0&1&0&0&0&1&1&1\\ 0&1&1&0&1&0&0&1\\ 1&0&0&0&1&1&1&1\\ 1&0&1&0&0&0&0&1\\ 1&1&0&1&0&0&0&1\\ 1&1&1&1&1&1&1&1 \end{array}

5.4 Unità

Si indica con TT la costante logica vera. Vale la legge (P≡T)≡P.(P\equiv T)\equiv P.

PP≡T(P≡T)≡P111001\begin{array}{c|c|c} P&P\equiv T&(P\equiv T)\equiv P\\\hline 1&1&1\\ 0&0&1 \end{array}

La colonna relativa a TT può essere omessa, perché contiene sempre il valore 11.

5.5 Transitività

((P≡Q)∧(Q≡R))⇒(P≡R).\bigl((P\equiv Q)\land(Q\equiv R)\bigr)\Rightarrow(P\equiv R).

Se PP è equivalente a QQ e QQ è equivalente a RR, allora PP è equivalente a RR.

Qui il connettivo principale è un’implicazione: non si sta affermando l’equivalenza tra la premessa complessiva e la conclusione. Per verificare la tautologia occorre escludere il caso in cui la premessa sia vera e la conclusione falsa, perché tale caso renderebbe falsa l’implicazione.

6 Leggi per la congiunzione e la disgiunzione

6.1 Commutatività

P∨Q≡Q∨P,P∧Q≡Q∧P.\begin{aligned} P\lor Q&\equiv Q\lor P,\\ P\land Q&\equiv Q\land P. \end{aligned}

La tabella per la disgiunzione è PQP∨QQ∨P(P∨Q)≡(Q∨P)00001011111011111111\begin{array}{cc|cc|c} P&Q&P\lor Q&Q\lor P&(P\lor Q)\equiv(Q\lor P)\\\hline 0&0&0&0&1\\ 0&1&1&1&1\\ 1&0&1&1&1\\ 1&1&1&1&1 \end{array}

La legge per la congiunzione si verifica analogamente mediante la relativa tabella di verità.

6.2 Associatività

(P∧Q)∧R≡P∧(Q∧R),(P∨Q)∨R≡P∨(Q∨R).\begin{aligned} (P\land Q)\land R&\equiv P\land(Q\land R),\\ (P\lor Q)\lor R&\equiv P\lor(Q\lor R). \end{aligned}

Entrambe le leggi si possono verificare mediante le tabelle di verità.

6.3 Idempotenza

P∨P≡P,P∧P≡P.\begin{aligned} P\lor P&\equiv P,\\ P\land P&\equiv P. \end{aligned}

Per la disgiunzione: PP∨P(P∨P)≡P001111\begin{array}{c|c|c} P&P\lor P&(P\lor P)\equiv P\\\hline 0&0&1\\ 1&1&1 \end{array}

La verifica per la congiunzione si svolge nello stesso modo.

6.4 Unità

Si indica con FF la costante logica falsa. Valgono le leggi P∨F≡P,P∧T≡P.\begin{aligned} P\lor F&\equiv P,\\ P\land T&\equiv P. \end{aligned}

Dunque FF è l’elemento neutro della disgiunzione e TT è l’elemento neutro della congiunzione: in entrambi i casi, l’operazione lascia invariato il valore di PP.

PP∨F(P∨F)≡PP∧T(P∧T)≡P0010111111\begin{array}{c|cc|cc} P&P\lor F&(P\lor F)\equiv P&P\land T&(P\land T)\equiv P\\\hline 0&0&1&0&1\\ 1&1&1&1&1 \end{array}

6.5 Legge dello zero o di dominanza

P∨T≡T,P∧F≡F.\begin{aligned} P\lor T&\equiv T,\\ P\land F&\equiv F. \end{aligned}

La costante TT domina nella disgiunzione: se almeno uno degli operandi è vero, la disgiunzione è vera. La costante FF domina nella congiunzione: se almeno uno degli operandi è falso, la congiunzione è falsa. Le leggi si verificano mediante le tabelle di verità.

6.6 Distributività

P∨(Q∧R)≡(P∨Q)∧(P∨R),P∧(Q∨R)≡(P∧Q)∨(P∧R).\begin{aligned} P\lor(Q\land R)&\equiv(P\lor Q)\land(P\lor R),\\ P\land(Q\lor R)&\equiv(P\land Q)\lor(P\land R). \end{aligned}

Nell’applicazione delle proprietà distributive, i valori di PP, QQ e RR devono rimanere gli stessi in tutte le loro occorrenze.

Per la prima legge poniamo U=P∨(Q∧R),V=(P∨Q)∧(P∨R).U=P\lor(Q\land R),\qquad V=(P\lor Q)\land(P\lor R).U=P∨(Q∧R),V=(P∨Q)∧(P∨R).\begin{gathered}U=P\lor(Q\land R),\\[0.5em]V=(P\lor Q)\land(P\lor R).\end{gathered}

Si calcolano prima le sottoformule, poi i due membri e infine la loro equivalenza: PQRQ∧RP∨QP∨RUVU≡V000000001001001001010010001011111111100011111101011111110011111111111111\begin{array}{ccc|ccc|cc|c} P&Q&R&Q\land R&P\lor Q&P\lor R&U&V&U\equiv V\\\hline 0&0&0&0&0&0&0&0&1\\ 0&0&1&0&0&1&0&0&1\\ 0&1&0&0&1&0&0&0&1\\ 0&1&1&1&1&1&1&1&1\\ 1&0&0&0&1&1&1&1&1\\ 1&0&1&0&1&1&1&1&1\\ 1&1&0&0&1&1&1&1&1\\ 1&1&1&1&1&1&1&1&1 \end{array}

7 Leggi per la negazione

7.1 Doppia negazione

¬(¬P)≡P.\neg(\neg P)\equiv P.

P¬P¬(¬P)¬(¬P)≡P10110101\begin{array}{c|cc|c} P&\neg P&\neg(\neg P)&\neg(\neg P)\equiv P\\\hline 1&0&1&1\\ 0&1&0&1 \end{array}

7.2 Terzo escluso

P∨¬P≡T.P\lor\neg P\equiv T.

P¬PP∨¬P(P∨¬P)≡T10110111\begin{array}{c|cc|c} P&\neg P&P\lor\neg P&(P\lor\neg P)\equiv T\\\hline 1&0&1&1\\ 0&1&1&1 \end{array}

7.3 Non contraddizione

P∧¬P≡F.P\land\neg P\equiv F.

La legge si verifica mediante la tabella di verità.

7.4 Leggi di De Morgan

¬(P∧Q)≡¬P∨¬Q,¬(P∨Q)≡¬P∧¬Q.\begin{aligned} \neg(P\land Q)&\equiv\neg P\lor\neg Q,\\ \neg(P\lor Q)&\equiv\neg P\land\neg Q. \end{aligned}

La negazione di una congiunzione equivale alla disgiunzione delle negazioni. La negazione di una disgiunzione equivale alla congiunzione delle negazioni.

7.5 Negazione delle costanti

¬T≡F,¬F≡T.\begin{aligned} \neg T&\equiv F,\\ \neg F&\equiv T. \end{aligned}

8 Leggi dell’implicazione

8.1 Eliminazione dell’implicazione

(P⇒Q)≡(¬P∨Q).(P\Rightarrow Q)\equiv(\neg P\lor Q).

PQP⇒Q¬P¬P∨Q(P⇒Q)≡(¬P∨Q)001111011111100001111011\begin{array}{cc|ccc|c} P&Q&P\Rightarrow Q&\neg P&\neg P\lor Q&(P\Rightarrow Q)\equiv(\neg P\lor Q)\\\hline 0&0&1&1&1&1\\ 0&1&1&1&1&1\\ 1&0&0&0&0&1\\ 1&1&1&0&1&1 \end{array}

8.2 Eliminazione dell’equivalenza

(P≡Q)≡((P⇒Q)∧(Q⇒P)).(P\equiv Q)\equiv\bigl((P\Rightarrow Q)\land(Q\Rightarrow P)\bigr).

L’equivalenza si esprime quindi come congiunzione delle due implicazioni, una in ciascun verso. La legge si verifica mediante la tabella di verità.