L'equivalenza logica

Due o più espressioni logiche A e B sono espressioni equivalenti quando hanno gli stessi valori in uscita nella tavola di verità. $$ A = B $$ Per rappresentare l'equivalenza logica si usa il simbolo uguale = oppure $ \equiv $

In altre parole, due espressioni logiche, \( A \) e \( B \), sono logicamente equivalenti se condividono lo stesso valore di verità in ogni possibile modello.

$$ A \equiv B \quad \text{se e solo se} \quad (A \models B) \land (B \models A) $$

Questa definizione si traduce in due affermazioni chiave:

• \( \mathbf{A \models B} \): L'espressione \( B \) è una conseguenza logica di \( A \), cioè ogni volta che \( A \) è vera, anche \( B \) è vera.
• \( \mathbf{B \models A} \): L'espressione \( A \) è una conseguenza logica di \( B \), cioè ogni volta che \( B \) è vera, anche \( A \) è vera.

Quindi, l'equivalenza logica \( A \equiv B \) può essere interpretata come una doppia conseguenza logica. 

A cosa serve?

Il criterio di equivalenza logica è molto importante perché mi permette di semplificare i costrutti logici e ha diverse applicazioni pratiche.

Ad esempio, in elettronica mi è utile per semplificare i circuiti combinatori. Utilizzando leggi come quelle di De Morgan, formule complesse possono essere trasformate in forme più semplici senza modificarne il significato. Quindi, l’equivalenza logica aiuta a progettare circuiti più efficienti.

Un esempio pratico

Esempio 1

Considero le proposizioni semplici

$$ A = \text{vado al mare} $$

$$ B = \text{vado in montagna} $$

e le proposizioni composte

$$ A∨B = \text{vado al mare o in montagna} $$

$$ B∨A = \text{vado in montagna o al mare} $$

Le proposizioni composte A∨B e B∨A sono espressioni equivalenti perché generano gli stessi valori di verità.

$$ \begin{array}{cr|c} p & q & A∨B & B∨A \\ \hline F & F & F & F \\ F & V & V & V \\ V & F & V & V \\ V & V & V & V \end{array} $$

I valori di verità in uscita della tavola sono identici (terza e quarta colonna).

Nota. Per essere equivalenti le espressioni devono avere i valori di verità in uscita uguali (terza e quarta colonna). $$ \begin{array}{cr|c} p & q & A∨B & B∨A \\ \hline F & F & \color{red}F & \color{red}F \\ F & V & \color{red}V & \color{red}V \\ V & F & \color{red}V & \color{red}V \\ V & V & \color{red}V & \color{red}V \end{array} $$ Le combinazioni dei valori di verità in entrata, in questo caso la prima e la seconda colonna della tavola, possono anche essere diversi.

 

Nota 2. In questo esempio per semplicità ho usato la disgiunzione inclusiva (or) anziché la disgiunzione esclusiva (xor) che sarebbe stata più propriamente adatta. Per questa ragione nella tavola di verità risulta vera anche l'affermazione "vado al mare e in montagna" (ultima riga). In ogni caso, anche usando la disgiunzione esclusiva le due proposizioni sarebbero state equivalenti.$$ \begin{array}{cr|c} p & q & A \ \dot{∨} \ B & B \ \dot{∨} \ A \\ \hline F & F & F & F \\ F & V & V & V \\ V & F & V & V \\ V & V & F & F \end{array} $$

Esempio 2

Considero due proposizioni composte A∧B e (A∧B)∨A

Le due espressioni A∧B e (A∧B)∨A non sono equivalenti perché hanno valori di verità diversi.

$$ \begin{array}{cr|c} p & q & A∧B & (A∧B)∨A \\ \hline F & F & F & F \\ F & V & F & F \\ V & F & F & V \\ V & V & V & V \end{array} $$

Tuttavia, le proposizioni A (prima colonna) e (A∧B)∨A (quarta colonna) sono equivalenti perché manifestano gli stessi valori di verità.

Pertanto, posso sostituire l'espressione (A∧B)∨A con la proposizione semplice A e ottenere lo stesso risultato finale.

Le proprietà dell'equivalenza logica

L’equivalenza logica soddisfa tre proprietà fondamentali:

• Riflessività: \( A \equiv A \)
  La proprietà di riflessività afferma che ogni formula logica è sempre equivalente a se stessa. Questo è intuitivo: una proposizione, indipendentemente dal contesto, esprime sempre il proprio significato.
• Simmetria: Se \( A \equiv B \), allora \( B \equiv A \)
  La simmetria garantisce che, se una formula \( A \) è equivalente a una formula \( B \), allora \( B \) è equivalente a \( A \). Questo significa che l’equivalenza logica funziona in entrambe le direzioni.
• Transitività: Se \( A \equiv B \) e \( B \equiv C \), allora \( A \equiv C \)
  La transitività stabilisce che, se una formula \( A \) è equivalente a una formula \( B \), e \( B \) è equivalente a una formula \( C \), allora \( A \) è equivalente a \( C \). Questo mi permette di concatenare equivalenze logiche senza perdere coerenza.

Queste tre proprietà fanno dell’equivalenza logica una relazione di equivalenza.

E così via.