Raisonnements

Par la Notation 1.1, montrer $F \equiv G$ revient à montrer que $F \iff G$ est une tautologie, c'est-à-dire vraie pour toutes valeurs de vérité des propositions qui la composent (Définition 1.8). On procède donc par tables de vérité pour chacune des trois identités.

Première identité : $(P \implies Q) \equiv ((\text{non } P) \text{ ou } Q)$.

On dresse la table de vérité des deux formules en parcourant les 4 cas possibles :

$$\begin{array}{|c|c|c|c|c|} P & Q & P \implies Q & \text{non } P & (\text{non } P) \text{ ou } Q \\ \text{V} & \text{V} & \text{V} & \text{F} & \text{V} \\ \text{V} & \text{F} & \text{F} & \text{F} & \text{F} \\ \text{F} & \text{V} & \text{V} & \text{V} & \text{V} \\ \text{F} & \text{F} & \text{V} & \text{V} & \text{V} \\ \end{array}$$

Les colonnes $P \implies Q$ et $(\text{non } P) \text{ ou } Q$ sont identiques (d'après la Définition 1.5 pour l'implication et la Définition 1.2 et 1.4 pour les colonnes de droite). Donc $(P \implies Q) \iff ((\text{non } P) \text{ ou } Q)$ est vraie dans tous les cas : c'est une tautologie.

Deuxième identité : $(P \iff Q) \equiv ((P \implies Q) \text{ et } (Q \implies P))$.

On dresse la table de vérité :

$$\begin{array}{|c|c|c|c|c|c|} P & Q & P \iff Q & P \implies Q & Q \implies P & (P \implies Q) \text{ et } (Q \implies P) \\ \text{V} & \text{V} & \text{V} & \text{V} & \text{V} & \text{V} \\ \text{V} & \text{F} & \text{F} & \text{F} & \text{V} & \text{F} \\ \text{F} & \text{V} & \text{F} & \text{V} & \text{F} & \text{F} \\ \text{F} & \text{F} & \text{V} & \text{V} & \text{V} & \text{V} \\ \end{array}$$

Les colonnes $P \iff Q$ et $(P \implies Q) \text{ et } (Q \implies P)$ sont identiques (d'après la Définition 1.6 pour l'équivalence, la Définition 1.5 pour les deux implications, et la Définition 1.3 pour la conjonction). Donc la formule est une tautologie.

Troisième identité : $(P \text{ ou } Q) \equiv ((\text{non } P) \implies Q)$.

On dresse la table de vérité :

$$\begin{array}{|c|c|c|c|c|} P & Q & P \text{ ou } Q & \text{non } P & (\text{non } P) \implies Q \\ \text{V} & \text{V} & \text{V} & \text{F} & \text{V} \\ \text{V} & \text{F} & \text{V} & \text{F} & \text{V} \\ \text{F} & \text{V} & \text{V} & \text{V} & \text{V} \\ \text{F} & \text{F} & \text{F} & \text{V} & \text{F} \\ \end{array}$$

Les colonnes $P \text{ ou } Q$ et $(\text{non } P) \implies Q$ sont identiques (d'après la Définition 1.4 pour la disjonction, la Définition 1.2 pour la négation, et la Définition 1.5 pour l'implication). Donc la formule est une tautologie.

Les trois identités étant vérifiées par tables de vérité exhaustives, la proposition est démontrée.

Par la Notation 1.1, il s'agit dans chaque cas de montrer que la formule $F \iff G$ est une tautologie (Définition 1.8). On traite les deux premières identités par tables de vérité, et la troisième en utilisant la Proposition 1.1.

Première identité (première loi de De Morgan) : $\text{non}(P \text{ et } Q) \equiv ((\text{non } P) \text{ ou } (\text{non } Q))$.

$$\begin{array}{|c|c|c|c|c|c|c|} P & Q & P \text{ et } Q & \text{non}(P \text{ et } Q) & \text{non } P & \text{non } Q & (\text{non } P) \text{ ou } (\text{non } Q) \\ \text{V} & \text{V} & \text{V} & \text{F} & \text{F} & \text{F} & \text{F} \\ \text{V} & \text{F} & \text{F} & \text{V} & \text{F} & \text{V} & \text{V} \\ \text{F} & \text{V} & \text{F} & \text{V} & \text{V} & \text{F} & \text{V} \\ \text{F} & \text{F} & \text{F} & \text{V} & \text{V} & \text{V} & \text{V} \\ \end{array}$$

Les colonnes 4 et 7 sont identiques dans les 4 cas (d'après la Définition 1.3 pour la conjonction, la Définition 1.2 pour la négation, et la Définition 1.4 pour la disjonction). La formule est une tautologie.

Deuxième identité (deuxième loi de De Morgan) : $\text{non}(P \text{ ou } Q) \equiv ((\text{non } P) \text{ et } (\text{non } Q))$.

$$\begin{array}{|c|c|c|c|c|c|c|} P & Q & P \text{ ou } Q & \text{non}(P \text{ ou } Q) & \text{non } P & \text{non } Q & (\text{non } P) \text{ et } (\text{non } Q) \\ \text{V} & \text{V} & \text{V} & \text{F} & \text{F} & \text{F} & \text{F} \\ \text{V} & \text{F} & \text{V} & \text{F} & \text{F} & \text{V} & \text{F} \\ \text{F} & \text{V} & \text{V} & \text{F} & \text{V} & \text{F} & \text{F} \\ \text{F} & \text{F} & \text{F} & \text{V} & \text{V} & \text{V} & \text{V} \\ \end{array}$$

Les colonnes 4 et 7 sont identiques dans les 4 cas. La formule est une tautologie.

Troisième identité : $\text{non}(P \implies Q) \equiv (P \text{ et } (\text{non } Q))$.

D'après la Proposition 1.1 (première reformulation), on a $P \implies Q \equiv (\text{non } P) \text{ ou } Q$. Autrement dit, $(P \implies Q) \iff ((\text{non } P) \text{ ou } Q)$ est une tautologie. En particulier, pour toutes valeurs de vérité de $P$ et $Q$, les formules $P \implies Q$ et $(\text{non } P) \text{ ou } Q$ ont la même valeur de vérité, donc leurs négations aussi. Ainsi :
$$\text{non}(P \implies Q) \equiv \text{non}((\text{non } P) \text{ ou } Q).$$

Or, d'après la deuxième identité démontrée ci-dessus (appliquée à $\text{non } P$ à la place de $P$ et $Q$ à la place de $Q$) :
$$\text{non}((\text{non } P) \text{ ou } Q) \equiv (\text{non}(\text{non } P)) \text{ et } (\text{non } Q).$$

Enfin, d'après la Définition 1.2 de la négation, $\text{non}(\text{non } P)$ a la même valeur de vérité que $P$ (la double négation redonne la proposition initiale), donc :
$$\text{non}((\text{non } P)) \text{ et } (\text{non } Q) \equiv P \text{ et } (\text{non } Q).$$

En enchaînant les trois équivalences, on obtient bien $\text{non}(P \implies Q) \equiv P \text{ et } (\text{non } Q)$.