Théorie > Fondements > Logique

La logique s'intéresse à ce que l'on appelle des propositions logiques et à leur véracité. Une proposition logique est simplement une affirmation qui peut-être vraie ou fausse, comme par exemple l'affirmation "$x+y$ est multiple de $4$". Cette affirmation est vraie pour les $x$ et $y$ tels que $x+y$ est multiple de $4$, mais fausse sinon. La logique permet notamment de comprendre ce qu'il se passe lorsque l'on combine plusieurs propositions logiques.

Une proposition peut en effet être construite à partir de sous-propositions et de connecteurs logiques tels que "ou", "et" et "non", que l'on note respectivement $\lor$, $\land$, $\lnot$. En logique, on définit ces connecteurs en expliquant les conditions sous lesquelles les propositions $P \lor Q$, $P \land Q$ et $\lnot P$ sont vraies. Par exemple, on va dire que $P \land Q$ est vrai exactement lorsque $P$ et $Q$ sont tous les deux vrais. On définit donc les symboles en donnant la valeur (vrai ou faux) de la proposition combinée pour chaque valeur possible des sous-propositions. On regroupe cela dans une table de vérité dans laquelle $1$ signifie "vrai" et $0$ signifie "faux".

• Le connecteur $\lor$ représente la disjonction logique (le "ou" logique). $P \lor Q$ est vrai si et seulement si au moins un de $P$ et $Q$ est vrai. En language naturel, le "ou" exclut parfois que les deux soient vrais. Par exemple, quand on dit "Il faut choisir, tu fais $P$ ou tu fais $Q$", on veut dire qu'on ne peut pas faire les deux. En logique, ce n'est pas le cas, si $P$ et $Q$ sont vrais, alors $P \lor Q$ est vrai. Pour faire une disjonction logique en language naturel, on écrit d'ailleurs souvent "et/ou".
  Le tableau de vérité correspondant vaut
  $$\begin{array}{|c|c|c|}
  \hline
  P & Q & P \lor Q \\
  \hline
  0 & 0 & 0 \\
  \hline
  0 & 1 & 1 \\
  \hline
  1 & 0 & 1 \\
  \hline
  1 & 1 & 1 \\
  \hline
  \end{array}$$


• Le connecteur $\land$ représente la conjonction logique (le "et" logique) : $P \land Q$ est vrai si et seulement si $P$ et $Q$ sont tous les deux vrais. Le tableau de vérité correspondant vaut
  $$\begin{array}{|c|c|c|}
  \hline
  P & Q & P \land Q \\
  \hline
  0 & 0 & 0 \\
  \hline
  0 & 1 & 0 \\
  \hline
  1 & 0 & 0 \\
  \hline
  1 & 1 & 1 \\
  \hline
  \end{array}$$


• Le connecteur $\lnot$ représente enfin la négation logique : $\lnot P$ est vrai si et seulement si $P$ est faux. Le tableau de vérité correspondant vaut
  $$\begin{array}{|c|c|}
  \hline
  P & \lnot P \\
  \hline
  0 & 1 \\
  \hline
  1 & 0 \\
  \hline
  \end{array}$$

Un des points souvent mal compris en mathématique est la différence cruciale entre une condition nécessaire et une condition suffisante. Il est intéressant de savoir que deux propositions sont liées mais dire quelle proposition implique laquelle est tout aussi important.

Définition

Si le fait que $P$ soit vrai implique que $Q$ est vrai, on dit que $P$ est une condition suffisante à la véracité de $Q$. En effet, il suffit que $P$ soit vrai pour que $Q$ soit vrai. S'il nous faut prouver que $Q$ est vrai, il nous suffit de prouver que $P$ est vrai. On écrit $P \Rightarrow Q$ ou $Q \Leftarrow P$.

On remarque aussi qu'il est nécessaire que $Q$ soit vrai pour que $P$ soit vrai. En effet, si $P$ est vrai, on sait que $Q$ est vrai aussi, et $P$ ne peut donc pas être vrai si $Q$ est faux. On dit alors que $Q$ est une condition nécessaire à la véracité de $P$.

Quand on utilise les formulations "si $P$, alors $Q$", "$P$ donc $Q$" ou encore "$P$. Par conséquent $Q$", on utilise le fait que $P \Rightarrow Q$ qui doit alors soit être évident, soit avoir été prouvé précédemment. Il ne faut donc surtout pas utiliser ces formulations à la légère dans une preuve : en mathématique, leur sens est très précis.

Exemple

Quand on dit "À minuit, je dors", on formule l'implication entre "$P$ : Il est minuit" et "$Q$ : Je dors". Le fait qu'il soit minuit est une condition suffisante pour me voir assoupi et le fait que je dorme est une condition nécessaire pour qu'il soit minuit. Par contre, on n'exclut pas que je puisse dormir à d'autres moments de la journée qu'à minuit.
Si par contre on dit "Quand je dors, il est minuit", cela devient $Q \Rightarrow P$. Cela signifie cette fois que je ne dors pas à d'autres moments qu'à minuit : à 23h59, je ne suis pas encore couché et à 00h01, je suis déjà debout. Par contre, il se peut que je ne dorme pas non plus à minuit.

Condition nécessaire et suffisante

Quand on a non seulement $P \Rightarrow Q$ mais aussi $Q \Rightarrow P$, on dit que $P$ est une condition nécessaire et suffisante à la véracité de $Q$ (et vice versa) ou plus couramment, $P$ est vrai si et seulement si $Q$ est vrai. On note cela $P \Leftrightarrow Q$ et on utilise des formulations avec les mots de la famille d'équivalence comme dans "$P$, ce qui est équivalent à $Q$".

En pratique, pour prouver que $P \Leftrightarrow Q$, on prouve séparément que $P \Rightarrow Q$ et que $Q \Rightarrow P$.

Définition du point de vue de la logique

L'affirmation $P \Rightarrow Q$ est aussi une proposition composée d'un connecteur logique $\Rightarrow$ et de deux sous-propositions $P$ et $Q$. Cette nouvelle proposition peut être vraie ou fausse en fonction des valeurs de $P$ et $Q$. Il est cependant moins évident de donner le tableau de vérité de $\Rightarrow$ que pour $\lor$ ou $\land$. Pour bien le comprendre, il faut se demander "Si j'observe une situation où $P$ est vrai/faux et $Q$ est vrai/faux, que puis-je en déduire de la proposition $P \Rightarrow Q$ ?" Si ces valeurs de $P$ et $Q$ ne contredisent pas que $P$ puisse impliquer $Q$, alors on dira que $P \Rightarrow Q$ est vrai dans ce cas.

Ainsi, si $P$ et $Q$ sont tous les deux vrais, alors $P$ peut bel et bien impliquer $Q$, d'où $P \Rightarrow Q$ est défini comme étant vrai dans ce cas. Si par contre, $P$ est vrai mais $Q$ est faux, alors il s'agit justement d'une contradiction au fait que $P$ implique $Q$ : on définit $P \Rightarrow Q$ comme étant faux.

Les cas où $P$ est faux est un peu moins évident. En fait, si $P$ est faux, alors quelle que soit la valeur de $Q$ la proposition $P \Rightarrow Q$ sera vraie. En effet, puisque $P$ est faux, on a aucune contradiction avec le fait que $P$ implique $Q$ (qui nous dit basiquement "si $P$ est vrai, alors $Q$ est vrai").

Pour bien comprendre ce phénomène, on peut observer l'exemple "$P$ : Il pleut" et "$Q$ : Je prends mon parapluie". La proposition $P \Rightarrow Q$ est alors "S'il pleut, je prends mon parapluie". Si un jour, $P$ et $Q$ sont faux, c'est-à-dire s'il ne pleut pas et que je ne prends pas mon parapluie, alors je ne contredis pas mon principe comme quoi je prends mon parapluie chaque fois qu'il pleut : $P \Rightarrow Q$ est vrai. En fait, la seule manière pour que $P \Rightarrow Q$ soit faux est que je ne prenne pas mon parapluie alors qu'il pleut : il faut que $P$ soit vrai mais que $Q$ soit faux.

On a donc le tableau de vérité suivant :
$$\begin{array}{|c|c|c|}
\hline
P & Q & P \Rightarrow Q & Q \Rightarrow P & P \Leftrightarrow Q\\
\hline
0 & 0 & 1 & 1 & 1\\
0 & 1 & 1 & 0 & 0\\
1 & 0 & 0 & 1 & 0\\
1 & 1 & 1 & 1 & 1\\
\hline
\end{array}$$

Remarque

La proposition $P \Rightarrow Q$ peut en fait aussi s'écrire $\lnot P \lor Q$. En effet, les deux expressions sont fausses exactement quand $P$ est vrai et $Q$ est faux. La proposition $P \Leftrightarrow Q$ s'écrit quant à elle $(P \Rightarrow Q) \land (Q \Rightarrow P)$, ou encore $(\lnot P \lor Q) \land (\lnot Q \lor P)$.

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".

Les ensembles peuvent être définis à l'aide d'une proposition. Par exemple,
$$A = \{n \in \mathbb{Z} \mid (n \geq -1) \land (n < 4)\} = \{-1, 0, 1, 2, 3\}.$$ Cette similitude rend la logique et la théorie des ensembles assez proches.

Similitudes

La relation d'inclusion s'apparente par exemple à une implication. En effet, $A \subseteq B$ est équivalent à $x \in A \Rightarrow x \in B$.

Aussi, les opérations $\lor$ et $\cup$ n'ont pas que leurs symboles qui se ressemblent puisqu'on a
$$A \cup B = \{x \mid (x \in A) \lor (x \in B)\}$$ et similairement pour $\land$ et $\cap$,
$$A \cap B = \{x \mid (x \in A) \land (x \in B)\}.$$ Le complémentaire est quant à lui lié à la négation logique $\lnot$ :
$$A^c = \{x \in U \mid \lnot (x \in A)\}$$ où $U$ est l'univers.

L'ensemble vide $\emptyset$ s'apparente enfin à $0$ et l'univers $U$ à $1$.

Toutes les relations que nous avons vues dans le cadre de la logique peuvent alors être réécrites dans le cadre de la théorie des ensembles.

Commutativité et associativité, neutre et absorbant

Les opérations $\cup$ et $\cap$ sont associatives et commutatives.
Le neutre de $\cup$ est $\emptyset$ et celui de $\cap$ est $U$ :
$$\begin{align*}
\emptyset \cup A & = A, & U \cap A & = A.
\end{align*}$$ L'absorbant de $\cup$ est $U$ et celui de $\cap$ est $\emptyset$ :
$$\begin{align*}
U \cup A & = U, & \emptyset \cap A & = \emptyset.
\end{align*}$$

Lois de De Morgan

Les lois de De Morgan pour les ensembles sont
$$\begin{align*}
(A \cup B)^c & = A^c \cap B^c,\\
(A \cap B)^c & = A^c \cup B^c.
\end{align*}$$

Distributivité

Comme pour $\lor$ et $\land$, on a la distributivité
$$\begin{align*}
(A \cup B) \cap C & = (A \cap C) \cup (B \cap C),\\
(A \cap B) \cup C & = (A \cup C) \cap (B \cup C).
\end{align*}$$

Contraposition

La contraposition devient finalement
$$(A \subseteq B) \Leftrightarrow (B^c \subseteq A^c).$$