On peut construire de nouvelles propositions logiques en utilisant des opérations (comme l’addition et la multiplication pour les nombres) en utilisant les connecteurs « non » noté « $\neg$ » pour la négation, « et » noté « $\wedge$ » pour la conjonction logique, le « ou » noté « $\vee$ » pour la disjonction logique, « implique » noté « $\Rightarrow$ » pour l’implication logique ; et « équivalent à » noté « $\Leftrightarrow$ » ou encore « $\equiv$ » pour l’équivalence logique.
Nous verrons que tous ces connecteurs peuvent être formulés à l’aide des deux premiers : le « non » et le « et ».
Convention.
L’écriture « non$P$ » ou « $\neg P$ » se passe de parenthèses. C’est ainsi que « non$P$ et $Q$ » signifie « (non$P$) et $Q$ » et non « non($P$ et $Q$) ».
1. Conjonction logique
Définition 1.
Soient $P$ et $Q$ deux propositions logiques.
La proposition ($P~\textbf{et}~Q$) se note aussi $(P\wedge Q)$, s’appelle une conjonction logique des deux propositions $P$ et $Q$. La proposition ($P~\textbf{et}~Q$) » est vraie si, et seulement si, $P$ et $Q$ sont simultanément vraies.
$(P~\textbf{et}~Q)$ est vraie $\Longleftrightarrow$ ($P$ est vraie et $Q$ est vraie).
On obtient la table de vérité de la conjonction logique comme suit : $$\begin{array}{c}
\begin{array}{|c|c|c|} \hline
P & Q & \color{brown}{(P~\text{et}~Q)}\\ \hline V&V&\color{brown}{V}\\ \hline V&F&\color{brown}{F}\\ \hline F&V&\color{brown}{F}\\ \hline F&F&\color{brown}{F}\\ \hline \end{array}\\
\color{brown}{\text{Fig.1.– Conjonction logique}}\\ \end{array}$$
2. Disjonction logique
Définition 2.
La proposition ($P~\textbf{ou}~Q$) se note aussi $(P\vee Q)$ s’appelle une disjonction logique des deux propositions $P$ et $Q$. La proposition ($P~\textbf{ou}~Q$) est vraie si, et seulement si, au moins l’une des deux propositions $P$ et $Q$ est vraie.
$(P~\textbf{ou}~Q)$ est vraie $\Longleftrightarrow$ [$P$ est vraie ou $Q$ est vraie ou ($P$ et $Q$) est vraie].
On obtient la table de vérité de la disjonction logique comme suit : $$\begin{array}{c}
\begin{array}{|c|c|c|} \hline
P & Q & \color{brown}{(P~\text{ou}~Q)}\\ \hline V&V&\color{brown}{V}\\ \hline V&F&\color{brown}{V}\\ \hline F&V&\color{brown}{V}\\ \hline F&F&\color{brown}{F}\\ \hline \end{array}\\
\color{brown}{\text{Fig.2.– Disjonction logique}}\\ \end{array}$$
3. Négation d’une conjonction logique
Nous allons voir que ces deux connecteurs sont très liés, en cherchant les négations de ces propositions logiques.
Propriété 1. Négation d’une conjonction logique.
Soient $P$ et $Q$ deux propositions logiques. Alors la négation de la proposition ($P~\textbf{et}~Q$) est la proposition :$$\text{non}(P~\textbf{et}~Q)\Longleftrightarrow (\text{non}P~\textbf{ou}~\text{non}Q)$$
Nous voyons cette équivalence en écrivant les tables de vérité de ces deux proposition. Tout d’abord la table de $\text{non}(P\textbf{ et }Q)$ : $$\begin{array}{c}
\begin{array}{|c|c|c|c|} \hline
P & Q & (P\text{ et }Q) & \color{brown}{\text{non}(P\textbf{ et }Q)}\\ \hline
V&V&V&\color{brown}{F}\\ \hline
V&F&F&\color{brown}{V}\\ \hline
F&V&F&\color{brown}{V}\\ \hline
F&F&F&\color{brown}{V}\\ \hline \end{array}\\
\color{brown}{\text{Fig.3.– Négation d’une conjonction logique}}\\ \end{array}$$
Puis la table de $(\text{non}P)\textbf{ ou }(\text{non}Q)$ : $$\begin{array}{c}
\begin{array}{|c|c|c|c|} \hline
P & Q & \text{non}P & \text{non}Q & \color{brown}{(\text{non}P)\textbf{ ou }(\text{non}Q)}\\ \hline
V&V&F &F&\color{brown}{F}\\ \hline
V&F&F&V&\color{brown}{V}\\ \hline
F&V&V&F&\color{brown}{V}\\ \hline
F&F&V&V&\color{brown}{V}\\ \hline \end{array}\\
\color{brown}{\text{Fig.4.– La négation d’une conjonction est une disjonction}}\\ \end{array}$$
4. Négation d’une disjonction logique
Propriété 2. Négation d’une disjonction logique.
Soient $P$ et $Q$ deux propositions logiques. Alors la négation de la proposition ($P~\textbf{ou}~Q$) est la proposition :$$\text{non}(P~\textbf{ou}~Q)\Longleftrightarrow (\text{non}P~\textbf{et}~\text{non}Q)$$
Nous voyons cette équivalence en écrivant les tables de vérité de ces deux proposition. Tout d’abord la table de $\text{non}(P\textbf{ ou }Q)$ : $$\begin{array}{c}
\begin{array}{|c|c|c|c|} \hline
P & Q & (P\textbf{ ou }Q) & \color{brown}{\text{non}(P\textbf{ et }Q)}\\ \hline
V&V&V&\color{brown}{F}\\ \hline
V&F&F&\color{brown}{V}\\ \hline
F&V&F&\color{brown}{V}\\ \hline
F&F&F&\color{brown}{V}\\ \hline \end{array}\\
\color{brown}{\text{Fig.3.– Négation de la disjonction logique}}\\ \end{array}$$
Puis la table de $\text{non}P\textbf{ ou }\text{non }Q)$ : $$\begin{array}{c}
\begin{array}{|c|c|c|c|} \hline
P & Q & \text{non}P & \text{non}Q & \color{brown}{\text{non}P\textbf{ ou }\text{non}Q}\\ \hline
V&V&F &F&\color{brown}{F}\\ \hline
V&F&F&V&\color{brown}{V}\\ \hline
F&V&V&F&\color{brown}{V}\\ \hline
F&F&V&V&\color{brown}{V}\\ \hline \end{array}\\
\color{brown}{\text{Fig.4.– La négation d’une disjonction est une conjonction}}\\ \end{array}$$
5. Disjonction logique exclusive (le « ou exclusif »)
Définition 3.
La proposition $(P~\Delta~Q)$ se note aussi $(P\veebar Q)$ s’appelle la disjonction logique exclusive des deux propositions $P$ et $Q$. La proposition ($P~\Delta~Q$) est vraie si, et seulement si, l’une des deux propositions $P$ ou $Q$ est vraie, mais pas les deux.
$(P~\Delta~Q)$ est vraie $\Longleftrightarrow$ [($P$ est vraie et $Q$ fausse) ou ($P$ est fausse et $Q$ est vraie)].
C’est l’équivalent de ce que l’on appelle la « différence symétrique » de deux ensembles, en théorie des ensembles. $$(A~\Delta~B)=(A\setminus B)\cup(B\setminus A)=(A\cup B)\setminus (A\cap B)$$
6. Propositions incompatibles. Tautologie et antilogies
Définition 4.
Une proposition ${\mathcal T}$ est dite une tautologie si, et seulement si, ${\mathcal T}$ est vraie indépendamment des valeurs logiques des assertions qui ont servi à la construire.
La négation d’une tautologie ${\mathcal A}\equiv\text{non }{\mathcal T}$ s’appelle une antilogie. ${\mathcal A}$ est fausse indépendamment des valeurs logiques des assertions qui ont servi à la construire.
Définition 5.
Deux propositions $P$ et $Q$ sont dites incompatibles si, et seulement si, leur conjonction est toujours fausse.
En particulier $P$ et (non$P$) sont incompatibles, mais ce n’est qu’un cas particulier.
Exemples
Dans tous les exemples ci-dessous, $P$ est une proposition logique donnée.
- Les deux propositions $(x<5)$ et $(x>10)$ sont incompatibles.
- La proposition ${\mathcal T}\equiv (P\textbf{ ou }\text{non}P)$ est une tautologie.
C’est ce qu’on appelle « Le principe du tiers exclu ». Une proposition logique $P$ peut être « vraie » ou « fausse », mais pas « vraie et fausse » en même temps. Cette troisième possibilité est exclue. - La proposition ${\mathcal A}\equiv (P\textbf{ et }\text{non}P)$ est une antilogie. (même principe).
- La proposition ${\mathcal T}\equiv \text{non}(P\textbf{ et }\text{non}P)\equiv (P\textbf{ ou }\text{non}P)$, est une tautologie.
C’est ce qu’on appelle aussi « Le principe de non-contradiction ». Principe de base du raisonnement par l’absurde. Une proposition et son contraire ne peuvent pas être vraies simultanément. - La transitivité de l’implication est une tautologie.
Soient $P$, $Q$ et $R$ trois propositions logiques. Alors :$$[(P\Rightarrow Q)\text{ et } (Q\Rightarrow R)]\Longrightarrow (P\Rightarrow R)$$
6 . Exercices résolus
Exercice résolu n°1.
Soient $P$, $Q$ et $R$ trois propositions logiques. Démontrer que :
1°) Commutativité :
$(P\textbf{ et }Q)\Longleftrightarrow (Q\textbf{ et }P)$. De même pour des disjonctions.
2°) Associativité :
$[P\textbf{ et }(Q\textbf{ et }R)]\Longleftrightarrow [(P\textbf{ et }Q)\textbf{ et }R)]$. Même chose pour des disjonctions.
3°) Lois de Morgan :
a) $[P\textbf{ et }(Q\textbf{ ou }R)]\Longleftrightarrow [(P\textbf{ et }Q)\textbf{ ou }(P\textbf{ et }R)]$.
b) $[P\textbf{ ou }(Q\textbf{ et }R)]\Longleftrightarrow [(P\textbf{ ou }Q)\textbf{ et }(P\textbf{ ou }R)]$.
Exercice résolu n°3.
Déterminer les négations des propositions logiques suivantes :
1°) « $n$ est paire et $n$ est premier ».
2°) « $n$ est un multiple de $2$ ou $n>10$ ».