1. Propositions, valeur de vérité

1.1. Définition

Une proposition est une phrase (dont on peut comprendre le langage sans ambiguïté) dont on peut connaître la véracité (valeur de vérité). La valeur de vérité peut être « vrai » (ou $\mathcal V$, ou True, ou T, mais évitons 1), ou « faux » (ou $\mathcal F$, ou False, ou F, mais évitons 0). On utilisera cependant 0 et 1 pour les tables de vérité.

1.2. Exemples

1. « Il fait beau. »
2. « Il fera beau demain. »
3. « 1+1=2 »
4. « Attention ! »
5. « 2×3=5 »
6. « UF2 (maths approfondies) est obligatoire. »
7. « Cette mange rouge très je lévitation. »
8. « $n$ est pair. »

Pour chaque phrase ci-dessus, dire si c’est une proposition et dans ce cas, dire si elle est vraie ou fausse.

1.3. Notations

On aura parfois besoin d’une proposition constante et fausse, que l’on notera $\mathcal F$.
De même, $\mathcal V$ représentera une proposition vraie.

2. Connecteurs logiques

On peut assembler des propositions pour en construire d’autres, un peu comme on effectue des opérations sur les nombres pour obtenir d’autres nombres.

2.1. Connecteurs unaires

Ces connecteurs ne travaillent que sur une proposition. Le seul connecteur logique unaire qui soit intéressant est la négation.

Si $P$ est une proposition, on note $\neg P$ ou $\overline P $ (on prononcera « non pé » ou « pé barre ») la négation de $P$, c’est-à-dire la proposition qui est :

• vraie quand $P$ est fausse,
• fausse quand $P$ est vraie.

On a la table de vérité suivante :

C’est une involution. En effet, $\neg (\neg P)$ (« non non pé ») et $P$ ont la même valeur de vérité. Avec des barres, on écrit $\overline{\overline P}$ et on prononce « pé barre barre » ou « pé double barre ».

Remarques :

• Cette possibilité de réduire $\neg (\neg P)$ en $P$ est donnée par le principe du tiers exclu, présent en logique classique, mais que les intuitionistes refusent d'utiliser.
• Pour construire la négation d’une phrase en français, il suffit souvent d’insérer « ne … pas ». En programmation, on utilise suivant les langages not ou ! devant la condition que l’on veut nier.

2.2. Connecteurs binaires

2.2.1. Rappels

On dit que ? est un connecteur commutatif si pour toutes propositions A et B, A?B a exactement la même valeur que B?A (insensible au sens).

On dit que ? est un connecteur associatif si pour toutes propositions A, B et C, (A?B)?C a exactement la même valeur que A?(B?C) (insensible à l’ordre).

Exercice :

Parmi les opérations sur les nombres, dire si l’addition, la soustraction, la multiplication et la division sont commutatives et/ou associatives.

2.2.2. Équivalence

2.2.2.1. Définition

On définit l’équivalence $\Leftrightarrow$ par la table de vérité suivante :

$P \Leftrightarrow Q$ est vraie si et seulement si $P$ et $Q$ ont la même valeur de vérité. L’équivalence est le connecteur que l’on doit utiliser pour écrire des formules de logique, quand la valeur de vérité est conservée. Par exemple :

$$\neg (\neg P) \Leftrightarrow P$$

On omettra parfois les parenthèses qui nuisent à la lisibilité, lorsque l’on sent que l’équivalence n’est pas ambiguë. Pour l’exemple précédent, on espère que le lecteur ne comprendra pas $\neg \left((\neg P) \Leftrightarrow P\right)$ à la place de $\left(\neg (\neg P)\right) \Leftrightarrow P$ (qui par coïncidence ici sont toujours vraies toutes les deux).
Pour plus de lisibilité, jouer sur la taille des parenthèses.

2.2.2.2. Tautologies

Soient des propositions $P$, $Q$, $R$ (…). Une tautologie est une proposition résultant de l’assemblage par des connecteurs logiques de propositions prises parmi $P$, $Q$, $R$… qui est vraie quelle que soit la valeur de vérité des propositions en jeu. Un peu comme une « formule » de mathématiques.

2.2.2.3. Propriétés

C’est un connecteur commutatif et associatif :

$$(P \Leftrightarrow Q) \Leftrightarrow (Q \Leftrightarrow P)$$

Il est important de comprendre que les tautologies peuvent se lire dans les deux sens. C’est par exemple le cas ci-dessous (associativité).

$$ \left((P \Leftrightarrow Q) \Leftrightarrow R\right) \Leftrightarrow \left(P \Leftrightarrow (Q \Leftrightarrow R)\right) $$

Une proposition est toujours équivalente à elle-même. Autrement dit, $P \Leftrightarrow P$ est une tautologie 

$$(P \Leftrightarrow P) \Leftrightarrow \mathcal V$$

2.2.2.4. Remarque sur le sous-entendu de vérité

Lorsque l’on énonce une proposition, on sous-entend qu’elle est vraie. Autrement dit, si $P$ est une proposition, alors « $P$ est vraie » est équivalente à $P$, c’est à dire :

$$(P \Leftrightarrow \mathcal V) \Leftrightarrow P$$

De même, en programmation, les == True sont inutiles dans les conditions.

De même, « « $P$ est vraie » est vraie » est équivalente à $P$ et ainsi de suite.

2.2.3. Conjonction

2.2.3.1. Définition

La conjonction de $P$ avec $Q$ est notée $P \wedge Q$. Elle correspond au ET logique et à l’opération ET en calcul binaire, mais aussi au minimum ou au produit. En programmation, il est noté && ou and (de l’anglais, c’est le mot utilisé en Python).
Voici sa table de vérité :

2.2.3.2. Schéma

Soit E un ensemble, et A et B deux sous ensembles de E. Sont représentés en rouge les éléments $x$ de E qui sont tels que $x \in A$ ET $x \in B$.

crédits

2.2.3.3. Propriétés

2.2.3.3.1. Commutativité et associativité

C’est un connecteur commutatif et associatif. Démontrez-le à l’aide d’une table de vérité !

2.2.3.3.2. Élément neutre et élement absorbant

On rappelle que pour tout nombre $x$, $0+x = x$ ; $0×x = 0$ ; $1×x = 1$.

De façon similaire, on a :

$$\left( P∧\mathcal F \right) ⇔ \mathcal F$$ $$\left( P∧\mathcal V \right) ⇔ P$$

2.2.3.3.3. Auto-connexion et connexion avec le contraire

$$\left(P \wedge P\right) \Leftrightarrow P$$ $$\left(P \wedge (\neg P)\right) \Leftrightarrow \mathcal F$$

Ces équivalences sont faciles à démontrer à l’aide de tables de vérité à deux lignes. La deuxième peut s’expliquer par « une proposition et son contraire ne peuvent pas être vraies en même temps ».

2.2.4. Disjonction

2.2.4.1. Définition

La disjonction de $P$ avec $Q$ est notée $P \vee Q$. Elle correspond au OU logique (inclusif) et à l’opération OU en calcul binaire, mais aussi au maximum. En programmation, il est noté || ou or (de l’anglais, c’est le mot utilisé en Python).
Voici sa table de vérité :

Attention : ce ou est inclusif, à la différence du ou exclusif que l’on sous-entend dans « fromage ou dessert ».

Parmi ces phrases, quelles sont celles qui font apparaître un « ou » inclusif, un « ou » exclusif ?

1. « je cherche quelqu’un de beau ou de riche »
2. « tu manges ta soupe ou tu vas te coucher tout de suite »

2.2.4.2. Schéma

Soit E un ensemble, et A et B deux sous ensembles de E. Sont représentés en rouge les éléments $x$ de E qui sont tels que $x \in A$ OU $x \in B$.

crédits

2.2.4.3. Propriétés

2.2.4.3.1. Commutativité et associativité

C’est un connecteur commutatif et associatif. On peut à nouveau le démontrer à l’aide d’une table de vérité.

2.2.4.3.2. Élément neutre et élement absorbant

On rappelle que pour tout nombre $x$, $0+x = x$ ; $0×x = 0$ ; $1×x = 1$.

De façon similaire, on a :

$$\left( P∨\mathcal F \right) ⇔ P$$ $$\left( P∨\mathcal V \right) ⇔ \mathcal V$$

2.2.4.3.3. Auto-connexion et connexion avec le contraire

$$\left(P \vee P\right) \Leftrightarrow P$$ $$\left(P \vee (\neg P)\right) \Leftrightarrow \mathcal V$$

Ces équivalences sont faciles à démontrer à l’aide de tables de vérité à deux lignes. La deuxième peut s’expliquer par « entre une proposition et son contraire, au moins une des deux est vraie ».

2.2.5. Implication

2.2.5.1. Définition

« $P$ implique $Q$ » se note $P \Rightarrow Q$ et est définie par :

2.2.5.2. Remarques

2.2.5.2.1. Lien avec l’équivalence

Il faut comprendre la différence entre cette table et celle de l’équivalence. Elle se situe au niveau de $\mathcal F \Rightarrow \mathcal V$ est vrai.

Étudions rapidement un exemple : « Je vous punis si vous êtes bavards, et seulement si vous êtes bavards. » nous indique que :

• si vous êtes bavards je vous punis,
• si vous n’êtes pas bavards, je ne vous punis pas (puisque c’est « seulement si »).

En revanche, « Si vous êtes bavards, je vous punis. » n’empêche pas que je vous punisse même si vous n’êtes pas bavards. En effet, si $P$ est fausse, $P \Rightarrow Q$ est vraie, que $Q$ soit vraie ou fausse.

2.2.5.2.2. Principal rôle de l’implication

Le principal rôle de l’implication est l’idée de cause et de conséquence.

$P \Rightarrow Q$ peut se lire « Si P alors Q ».

En effet, si $P$ est vraie et si $P \Rightarrow Q$ est vraie, alors $Q$ est vraie. En d’autres termes, nous avons la tautologie : $$ \left(P \wedge (P \Rightarrow Q) \right) \Rightarrow Q $$

À vous de démontrer cette tautologie à l’aide d’une table de vérité ! (Nous le ferons plus loin sans table de vérité.)

2.2.5.3. Propriétés

2.2.5.3.1. Expression de l’implication à l’aide de la négation et de la disjonction

Une tautologie fondamentale à retenir :

$$ \left(P \Rightarrow Q \right) \Leftrightarrow \left((\neg P) \vee Q \right) $$

Ou en utilisant une barre :

$$ \left(P \Rightarrow Q \right) \Leftrightarrow \left(\overline P \vee Q \right) $$

Il suffit de donner la table de vérité de $(\neg P) \vee Q$ pour le démontrer. Nous serons bientôt capables de démontrer cette tautologie sans calculer la deuxième table de vérité, uniquement en travaillant par équivalence à partir du seul zéro de la table de l’implication.

2.2.5.3.2. Expression de l’équivalence à partir de l’implication et de la conjonction

$$\left[ \left( P \Rightarrow Q \right) \wedge \left( Q \Rightarrow P \right) \right] \Leftrightarrow \left[ P \Leftrightarrow Q \right]$$

À vous de le montrer à l’aide d’une table de vérité.

2.2.5.3.3. Commutativité et associativité

Attention : L’implication n’est ni commutative ni associative. À vous de trouver un contre-exemple pour chacune des propriétés.

Notons que $Q \Rightarrow P$ est appelée la réciproque de $P \Rightarrow Q$.

2.2.5.3.4. Élément neutre et élément absorbant

Remarque : Rarement utile, mais donné pour réflexion.

On ne peut pas parler d’élément neutre ou absorbant à proprement parler, mais on reste dans l’esprit. Donner une expression plus simple pour :

$$P \Rightarrow \mathcal F$$ $$P \Rightarrow \mathcal V$$ $$\mathcal F \Rightarrow P$$ $$\mathcal V \Rightarrow P$$

2.2.5.3.5. Auto-connexion et connexion avec le contraire

1. $\left( P \Rightarrow P \right) \Leftrightarrow \mathcal V$
2. $\left( P \Rightarrow (\neg P) \right) \Leftrightarrow (\neg P)$
3. $\left( (\neg P) \Rightarrow P \right) \Leftrightarrow P$

3. Autres propriétés

3.1. Distributivité

3.1.1. Rappel avec les nombres

On rapelle que pour tous nombres réels $a$, $b$ et $c$, on a $a×(b+c) = a×b + a×c$. C’est la distributivité de la multiplication par rapport à l’addition. En revanche, $a+(b×c) \ne (a+b) × (a+c)$ en général.

3.1.2. Avec les propositions

Au niveau de la conjonction et de la disjonction, il y a distributivité dans les deux sens.

Autrement dit, nous avons les tautologies suivantes : $$ P \wedge (Q \vee R) \Leftrightarrow (P \wedge Q) \vee (P \wedge R) $$ $$ P \vee (Q \wedge R) \Leftrightarrow (P \vee Q) \wedge (P \vee R) $$

À vous de le démontrer avec deux tables de vérité.

3.1.3. Ordre des calculs important

Montrer que $$(P \vee Q) \wedge R \Leftrightarrow P \vee (Q \wedge R)$$ n’est pas une tautologie.

Le bon placement des parenthèses est donc crucial.

3.1.4. Plutôt utiliser l’associativité dans certains cas

Si un seul connecteur $\vee$ ou $\wedge$ apparaît, même si la tautologie de distributivité est vraie (puisque ce connecteur commutatif et associatif), on ne distribue pas. L’associativité permet souvent de débloquer un calcul (l’équivalence peut bien sûr se lire dans les deux sens) :

$$P \vee (Q \vee R) \Leftrightarrow (P \vee Q) \vee R$$ $$P \wedge (Q \wedge R)\Leftrightarrow(P \wedge Q) \wedge R$$

3.2. Lois de De Morgan

Article sur Wikipedia.

3.2.1. Découverte dans les tables

En méditant quelques minutes sur les tables de la conjonction et de la disjonction, on se rend compte qu’elles ont un air de famille (trois 0 et un 1 pour une, un 0 et trois 1 pour l’autre).

En effet, avec quelques négations bien placées, on peut passer de l’une à l’autre. Essayez !

3.2.2. Lois

En d’autres termes,

La négation de la conjonction est la disjonction des négations.

et

La négation de la disjonction est la conjonction des négations.

3.2.3. Remarques

• On remarque la symétrie de ces tautologies.
• La proposition « ni beau, ni intelligent » peut être reformulée par « (NON beau) ET (NON intelligent) ». Grâce à une de ces lois, ont peut aussi la reformuler en « NON (beau OU intelligent) ».
  On décrit bien ainsi les gens qui se feront refouler à la soirée « beau ou intelligent ».

3.2.4. Schémas

crédits

Conjonction :

Négation de la conjonction :

C’est bien la disjonction des négations :

De même, la disjonction :

Négation de la disjonction :

C’est bien la conjonction des négations :

3.2.5. Simulation de la conjonction ou de la disjonction

Ces lois permettent d’exprimer la disjonction en utilisant uniquement la conjonction et la négation, et de même pour la conjonction avec uniquement la disjonction et la négation.

4. Un exemple de calcul

En utilisant les différentes tautologies vues précédemment, nous pouvons réécrire des propositions sans changer leur valeur, ceci afin de les simplifier ou de démontrer que certaines propositions sont des tautologies.

Nous allons ici simplifier $\left( P \wedge (P \Rightarrow Q) \right) \Rightarrow Q$ jusqu’à montrer que c’est une tautologie.

\begin{aligned}
\left( P \wedge (P \Rightarrow Q) \right) \Rightarrow Q & \Leftrightarrow \left( P \wedge (\overline P \vee Q) \right) \Rightarrow Q & (1) \\
& \Leftrightarrow \left((P \wedge \overline P) \vee (P \wedge Q) \right) \Rightarrow Q & (2) \\
& \Leftrightarrow \left(\mathcal F \vee (P \wedge Q) \right) \Rightarrow Q & (3) \\
& \Leftrightarrow (P \wedge Q) \Rightarrow Q & (4) \\
& \Leftrightarrow \overline {(P \wedge Q)} \vee Q & (5) \\
& \Leftrightarrow (\overline P \vee \overline Q) \vee Q & (6) \\
& \Leftrightarrow \overline P \vee (\overline Q \vee Q) & (7) \\
& \Leftrightarrow \overline P \vee \mathcal V & (8) \\
& \Leftrightarrow \mathcal V & (9) \\
\end{aligned}

1. On exprime l’implication dans les parenthèses les plus internes avec la négation et la disjonction.
2. On développe la conjonction sur la disjonction.
3. Au moins une des proposition entre $P$ et $\overline P$ est fausse.
4. $\mathcal F$ est un élément neutre de la disjonction.
5. On exprime la dernière implication avec la négation et la disjonction.
6. On applique une des lois de De Morgan.
7. La disjonction est associative.
8. Au moins une des proposition entre $Q$ et $\overline Q$ est vraie.
9. $\mathcal V$ est un élément absorbant de la conjonction.

$\left( P \wedge (P \Rightarrow Q) \right) \Rightarrow Q$ est une figure du raisonnement logique très utilisée et appelée le modus ponens.

5. Principe de dualité

On a pu remarquer tout au long du chapître que la plupart des tautologies possédaient une tautologie symétrique.

En « passant au travers de la négation » comme on passe au travers d’un miroir, on obtient à partir d’une tautologie une autre tautologie, sa tautologie duale.

$\mathcal F$ devient $\mathcal V$,
$\mathcal V$ devient $\mathcal F$,
$\wedge$ devient $\vee$,
$\vee$ devient $\wedge$.

Voir cet article sur Wikipedia pour plus de détails sur la dualité en mathématiques.

6. À retenir (ou à comprendre)

6.1. Moyen mnémotechnique

« Conjonction » et « disjonction » d’une part, et « ET » et « OU » d’autre part, sont par chance dans l’ordre alphabétique.

6.2. Éléments neutres et absorbants

$$\left( P∧\mathcal F \right) ⇔ \mathcal F$$ $$\left( P∧\mathcal V \right) ⇔ P$$ $$\left( P∨\mathcal F \right) ⇔ P$$ $$\left( P∨\mathcal V \right) ⇔ \mathcal V$$

6.3. Auto-opérations

$$\left(P∧P\right)⇔P$$ $$\left(P∧(\neg P)\right)⇔\mathcal F$$

$$\left(P∨P\right)⇔P$$ $$\left(P∨(\neg P)\right)⇔\mathcal V$$

6.4. Commutativité

$$\left( P⇔Q \right) ⇔ \left( Q⇔P \right)$$ $$\left( P∧Q \right) ⇔ \left( Q∧P \right)$$ $$\left( P∨Q \right) ⇔ \left( Q∨P \right)$$

6.5. Associativité

$$\left( P∧(Q∧R) \right) ⇔ \left( (P∧Q)∧R \right)$$ $$\left( P∨(Q∨R) \right) ⇔ \left( (P∨Q)∨R \right)$$

6.6. Distributivité

$$\left( P∧(Q∨R) \right) ⇔ \left( (P∧Q)∨(P∧R) \right)$$ $$\left( P∨(Q∧R) \right) ⇔ \left( (P∨Q)∧(P∨R) \right)$$

6.7. Lois de De Morgan

$$\left( \neg (P∧Q) \right) ⇔ \left( (\neg P)∨(\neg Q) \right)$$ $$\left( \neg (P∨Q) \right) ⇔ \left( (\neg P)∧(\neg Q) \right)$$

Avec les barres :

$$\left( \overline{(P∧Q)} \right) ⇔ \left( \overline P ∨\overline Q \right)$$ $$\left( \overline{(P∨Q)} \right) ⇔ \left( \overline P ∧\overline Q \right)$$

6.8. Implication

$$\left( P⇒Q \right) ⇔ \left( (\neg P)∨Q \right)$$

Avec la barre :

$$\left( P⇒Q \right) ⇔ \left( \overline P ∨Q \right)$$

7. Quelques tautologies

$$ \neg (P \Rightarrow Q) \Leftrightarrow P \wedge (\neg Q) $$

(En effet, la seule situation où je suis en faute, c’est si vous êtes bavards et que je ne vous punis pas.)

$$ \left( (P \Rightarrow Q) \wedge (Q \Rightarrow R) \right) \Rightarrow (P \Rightarrow R) $$

(On dit que l’implication est transitive.)

$$ \left((P \Rightarrow Q) \wedge (Q \Rightarrow P)\right) \Leftrightarrow (P \Leftrightarrow Q) $$

(Très utile en maths pour démontrer une équivalence en deux temps.)

$$(P \Rightarrow Q) \Leftrightarrow \left((\neg Q) \Rightarrow (\neg P)\right) $$

(On définit ici la contraposée d’une implication. Voir cet article sur Wikipedia.)