Définition

Deux formules F et G du calcul propositionnel sont dites 'logiquement équivalentes' si leur valeur de vérité est toujours la même, quelles que soient les valeurs de vérité de leurs composants.
Voici un exemple:
φ =(P∨Q)∧(¬(P ∧ Q))
ψ =(P∧(¬Q))∨(Q∧(¬P))
Il suffit pour le voir de dresser deux tables de vérité:
P Q P∨Q P∧Q ¬(P∧Q) φ
V V V V F F
V F V F V V
F V V F V V
F F F F V F
P Q ¬Q P∧(¬Q) ¬P Q∧(¬P) ψ
V V F F F F F
V F V V F F V
F V F F V V V
F F V F V F F

Notation

Quand  φ et ψ sont logiquement équivalentes on écrit:   φ ≡  ψ

Voici quelques équivalences usuelles :
¬(¬ P)≡P
¬(P∧Q)≡(¬P)∨(¬Q)
¬(P∨Q)≡(¬P)∧(¬Q)
P∨Q≡Q∨P
P∧Q≡Q∧P
P∧(Q∨R)≡(P∧Q)∨(P∧R)
P∨(Q∧R)≡(P∨Q)∧(P∨R)

Résultat important

Si dans une formule  G on substitue à une sous-formule une formule équivalente, la nouvelle formule obtenue est équivalente à la formule d'origine G.
Cela se voit en utilisant la définition récursive des formules.

Café Python

Voici un programme qui teste les équivalences classiques.