Equivalenza logica

Definizione: Due formule $\varphi$ e $\psi$ sono logicamente equivalenti, scritto $\varphi \equiv \psi$, se, per ogni modello $\cal A$ e per ogni assegnamento $e$ (su $\cal A$), si ha

$$ (\mathcal A, e)\models \varphi \iff (\mathcal A, e)\models \psi $$

Tutte le equivalenze logiche viste per la logica proposizionale — che riguardano solo il comportamento dei connettivi — valgono anche per la logica del primo ordine. Inoltre, nella logica del primo ordine esistono altre equivalenze logiche notevoli, che riguardano invece il comportamento dei quantificatori. Nel seguito, verranno presentate alcune di queste equivalenze.

Riscrittura dei quantificatori

  1. $\neg \forall x\varphi\equiv \exist x\neg \varphi$

    ($\forall x \varphi$ non vale se e solo se esiste almeno un elemento del dominio per cui vale $\neg \varphi$)

  2. $\neg \exist x\varphi\equiv \forall x \neg \varphi$

    ($\exist x\varphi$ non vale se e solo se per tutti gli elementi del dominio vale $\neg \varphi$)

  3. $\forall x \varphi \equiv \neg \exist x \neg \varphi$

    (ottenuta dalla 1, negando entrambi i lati dell’equivalenza ed eliminando la doppia negazione)

  4. $\exist x \varphi \equiv \neg \forall x \neg \varphi$

    (ottenuta analogamente dalla 2)

Esempio

Legame tra quantificatori e connettivi

Le equivalenze

$$ \neg \forall x\varphi \equiv \exist x\neg\varphi \ \ \ \ \ \ \ \ \ \ \ \neg\exist x\varphi \equiv \forall x \neg \varphi $$

sono generalizzazioni delle leggi di De Morgan:

$$ \neg(A\land B)\equiv \neg A\lor \neg B \ \ \ \ \ \ \ \ \ \ \ \ \neg (A\lor B)\equiv \neg A\land \neg B $$

Infatti, si possono considerare