Dans cette section, nous allons nous intéresser à la notion d'équivalence entre des propositions. Intuitivement, deux propositions sont équivalentes si elles affirment la même chose. Au fil de la section, nous allons mettre en lumière des équivalences entre des propositions.

On dit qu'une proposition est équivalente à une autre proposition si les deux propositions ont la même valeur de vérité pour toutes les interprétations possibles. On peut constater que les deux propositions sont équivalentes de manière visuelle à l'aide d'une table de vérité : les colonnes de deux propositions équivalentes contiennent les mêmes valeurs.

Lois de De Morgan

Auguste De Morgan est un mathématicien anglais du XIX^e siècle, qui a donné son nom à des lois de la logique – les lois de De Morgan – qui mettent en évidence des équivalences entre des propositions. Les lois de De Morgan énoncent comment les connecteurs et et ou se comportent avec le connecteur non.

Les lois sont les suivantes :

• La proposition non (p et q) est équivalente à (non p) ou (non q).
• La proposition non (p ou q) est équivalente à (non p) et (non q).

Les lois établissent le comportement de la négation sur les connecteurs logiques et et ou : Elles stipulent que la négation d'une conjonction est une disjonction de négations, tandis que la négation d'une disjonction est une conjonction de négations.

♣︎ Exemple

Soit la variable F qui signifie « La personne commande des fromages. » et la variable D qui signifie « La personne commande un dessert. ».

La proposition non (F et D) est équivalente à (non F) ou (non D). Dire que la personne ne commande pas à la fois des fromages et un dessert revient à dire qu'elle ne commande pas de fromages ou pas de dessert.

La proposition non (F ou D) est équivalente à (non F) et (non D). Dire qu'il n'est pas vrai que la personne commande des fromages ou un dessert revient à dire qu'elle ne commande pas de fromages et qu'elle ne commande pas de dessert.

Les lois de De Morgan peuvent être visualisées à l'aide de la table de vérité ci-dessous. Les colonnes contenant les mêmes valeurs correspondent à des propositions équivalentes.

Contraposée de l'implication

L'implication interagit elle aussi de façon intéressante avec la négation. On pourrait croire, à première vue, que si p implique q, alors forcément (non p) implique (non q). Cependant, ce n'est pas le cas, comme on peut le voir à l'aide de la table de vérité ci-dessous. En effet, les colonnes correspondant à ces propositions ne contiennent pas les mêmes valeurs.

Cependant, il y a bien une proposition formée d'une implication et de négations qui est équivalente à p implique q : il s'agit de (non q) implique (non p). Notez l'inversion de place des propositions pp et q à l'intérieur des deux propositions.

On appelle (non q) implique (non p) la contraposée de l'implication p implique q. Comme on peut le voir à l'aide de la table de vérité ci-dessous, les colonnes correspondant à ces deux propositions contiennent les mêmes valeurs, les propositions sont donc équivalentes.

♣︎ Exemple

Prenons par exemple la variable A qui représente la proposition « La personne boit de l'alcool. » et la variable M qui représente la proposition « La personne est majeure. ».

L'implication A implique M énonce que lorsque la personne boit de l'alcool, alors forcément elle est majeure. La contraposée de cette implication est (non M) implique (non A). Cette proposition énonce que lorsque la personne n'est pas majeure, alors forcément elle ne boit pas d'alcool. Les deux propositions sont équivalentes : satisfaire une proposition revient à satisfaire sa contraposée, et inversement.

Ces propositions contrastent avec la proposition (non A) implique (non M), qui elle énonce que lorsque une personne ne boit pas d'alcool c'est forcément qu'elle n'est pas majeure. Cette proposition est équivalente à la proposition M implique A, qui énonce que lorsque la personne est majeure, alors forcément elle boit de l'alcool.

Le connecteur ssi

De manière intéressante, énoncer que deux propositions sont équivalentes est aussi une proposition. En effet, il s'agit d'une affirmation qui peut être vraie ou fausse.

On utilise le connecteur logique si et seulement si pour énoncer cette proposition. On utilisera l'abréviation ssi pour dénoter ce connecteur. Parfois, la notation p ⇔ q est utilisée pour dénoter l'équivalence entre deux propositions p et q.

La table de vérité du connecteur ssi est affichée ci-dessous. L'équivalence est vraie uniquement quand les deux propositions ont la même valeur.

Les lois de De Morgan, que l'on a vues plus haut, peuvent être exprimées sous forme de propositions à l'aide de ce connecteur. Vues sous cette forme, les lois correspondent aux deux propositions suivantes:

• (non (p et q)) ssi ((non p) ou (non q))
• (non (p ou q)) ssi ((non p) et (non q))

En l'occurence, les deux propositions sont des tautologies. Peu importe la valeur de vérité des propositions p et q, les deux lois seront toujours vraies.