Théorie > Fondements > Logique

Toutes les relations données dans cette section peuvent être aisément démontrées à l'aide de tableaux de vérités. Pour montrer que deux expressions sont équivalentes (c'est-à-dire qu'elles sont vraies exactement en même temps), il suffit en effet de construire le tableau de vérité de chacune d'entre elles et de vérifier qu'ils sont bien identiques. La notation $\equiv$ sera utilisée pour dire que deux expressions sont équivalentes : nous pourrions utiliser $\Leftrightarrow$ mais cela pourrait perturber le lecteur puisque ce symbole peut également intervenir à l'intérieur de telles expressions.

Associativité, commutativité et neutre

Les opérateurs $\lor$ et $\land$ sont associatifs et commutatifs :
$$\begin{align*} P \lor (Q \lor R) & \equiv (P \lor Q) \lor R, & P \lor Q & \equiv Q \lor P,\\ P \land (Q \land R) & \equiv (P \land Q) \land R, & P \land Q & \equiv Q \land P. \end{align*}$$ Le neutre de $\lor$ est $0$ (la proposition toujours fausse) et celui de $\land$ est $1$ (la proposition toujours vraie) :
$$\begin{align*} 0 \lor P & \equiv P, & 1 \land P & \equiv P. \end{align*}$$ $1$ est absorbant pour $\lor$ et $0$ est absorbant pour $\land$ :
$$\begin{align*} 1 \lor P & \equiv 1, & 0 \land P & \equiv 0. \end{align*}$$ Aussi, $P$ et $\lnot P$ ayant toujours des valeurs distinctes (l'un vaut $0$ quand l'autre vaut $1$), on a les relations
$$\begin{align*} P \lor \lnot P & \equiv 1, & P \land \lnot P & \equiv 0. \end{align*}$$

Lois de De Morgan

Les lois de De Morgan nous permettent de calculer la négation logique de propositions composées de $\lor$ et de $\land$ :
$$\begin{align*} \lnot (P \lor Q) & \equiv \lnot P \land \lnot Q,\\ \lnot (P \land Q) & \equiv \lnot P \lor \lnot Q. \end{align*}$$
Par exemple, pour "$P$ : $x$ est pair" et "$Q$ : $x$ est divisible par $3$", la proposition $P \land Q$ est "$x$ est un multiple de $6$". Sa négation doit être vraie pour tout nombre qui n'est pas multiple de $6$, même s'il est pair. La négation logique est donc "$x$ est impair ou n'est pas divisible par $3$", c'est-à-dire exactement $\lnot P \lor \lnot Q$.

Distributivité

On peut distribuer $\land$ dans une disjontion logique et $\lor$ dans une conjonction logique :
$$\begin{align*} (P \lor Q) \land R & \equiv (P \land R) \lor (Q \land R),\\ (P \land Q) \lor R & \equiv (P \lor R) \land (Q \lor R). \end{align*}$$ Comme $\land$ et $\lor$ sont commutatifs, la formule marche aussi si $R$ est à gauche.

Généralisations

Les lois de De Morgan et de la distributivité se généralisent facilement comme suit :
$$\begin{align*} \lnot(P_1 \lor P_2 \lor \ldots \lor P_n) & \equiv \lnot P_1 \land \lnot P_2 \land \ldots \land \lnot P_n,\\ \lnot(P_1 \land P_2 \land \ldots \land P_n) & \equiv \lnot P_1 \lor \lnot P_2 \lor \ldots \lor \lnot P_n,\\ Q \land (P_1 \lor P_2 \lor \ldots \lor P_n) & \equiv (Q \land P_1) \lor (Q \land P_2) \lor \ldots \lor (Q \land P_n),\\ Q \lor (P_1 \land P_2 \land \ldots \land P_n) & \equiv (Q \lor P_1) \land (Q \lor P_2) \land \ldots \land (Q \lor P_n). \end{align*}$$

Contrapositions

La contraposition est la loi qui affirme que
$$(P \Rightarrow Q) \equiv (\lnot Q \Rightarrow \lnot P).$$ Celle-ci est utile dans le cadre d'une démonstration. En effet, si $P \Rightarrow Q$ semble trop difficile à prouver directement, on peut plutôt essayer de supposer $\lnot Q$ et de démontrer qu'on a alors $\lnot P$.

Par exemple, dire "Si je dors, alors je ne bouge pas" revient exactement à dire "Si je bouge, c'est que je ne dors pas".