Formalisation et Tables de Vérité en Logique Propositionnelle

Bonjour, et bienvenue dans cette première leçon de votre préparation à l'Agrégation.

Nous commençons notre parcours par les fondations mêmes du raisonnement en informatique et en mathématiques : la logique. L'objectif de cette première leçon est de vous rendre capable de formaliser une proposition en logique propositionnelle et de construire sa table de vérité. Cette compétence est le socle sur lequel nous construirons des notions plus avancées, comme les méthodes de preuve et la vérification de la correction des algorithmes.

Nous allons d'abord définir ce qu'est une proposition, introduire les connecteurs qui nous permettent de les combiner, puis nous apprendrons à évaluer la vérité de ces combinaisons de manière systématique grâce aux tables de vérité.

1. Propositions et Connecteurs Logiques

En logique, nous manipulons des propositions (aussi appelées assertions). Une proposition est une affirmation qui peut être soit vraie, soit fausse, sans ambiguïté.

Par exemple :

"2 est un nombre pair" est une proposition vraie.
"La lune est faite de fromage" est une proposition fausse.
"Quelle heure est-il ?" n'est pas une proposition, car on ne peut lui assigner de valeur de vérité.

Pour étudier la structure des raisonnements indépendamment de leur contenu, nous représentons ces propositions par des variables propositionnelles, souvent notées $p, q, r, \dots$ .

Ces propositions atomiques peuvent être combinées à l'aide de connecteurs logiques pour former des propositions plus complexes.

Pour vous familiariser avec ces concepts, je vous propose de visionner une vidéo qui présente de manière claire les définitions de base et les cinq connecteurs fondamentaux.

Prépa -MPSI -PCSI -COURS- Notion de logique-Le vocabulaire-table de vérité

Cette vidéo de la chaîne Maths en prépa avec Hans Amble introduit la notion de proposition, de négation, puis les connecteurs de conjonction (ET), disjonction (OU), implication et équivalence. Elle est très bien structurée et chaque connecteur est accompagné de sa table de vérité.

Regardez les sections suivantes : De 00:30 à 04:04 pour la définition d'une proposition logique et de la négation (¬). De 04:04 à 07:08 pour la conjonction (∧) et la disjonction (∨). De 07:08 à 10:19 pour l'implication (⇒). De 10:19 à 11:05 pour l'équivalence (⇔). \nPortez une attention particulière à la table de vérité de l'implication, notamment aux cas où l'hypothèse (la proposition à gauche de la flèche) est fausse.

Voici un résumé des connecteurs que vous venez de voir, avec la notation standard que nous utiliserons :

Opération	Langage Naturel	Notation
Négation	non $p$	$\neg p$
Conjonction	$p$ et $q$	$p \land q$
Disjonction	$p$ ou $q$ (inclusif)	$p \lor q$
Implication	si $p$ alors $q$	$p \Rightarrow q$
Équivalence	$p$ si et seulement si $q$	$p \Leftrightarrow q$

Ces tables de vérité sont le fondement sémantique de la logique propositionnelle.

2. Formalisation : La Syntaxe des Propositions

Traduire une phrase du langage naturel vers une formule logique est l'acte de formalisation. Pour qu'une formule soit valide, elle doit respecter des règles de construction précises. C'est ce qu'on appelle la syntaxe de la logique propositionnelle. Une formule qui respecte ces règles est une formule bien formée (fbf).

Pour approfondir la structure formelle de ces formules, je vous invite à lire un court extrait d'un polycopié de cours.

[PDF] Logique propositionnelle et Logique des Prédicats

Ce document, "Logique Propositionnelle et Logique des Prédicats", fournit une définition rigoureuse de la syntaxe des formules propositionnelles. C'est le genre de formalisme auquel vous devez vous habituer pour l'Agrégation.

Lisez la section 2.1.1 "Définition" (page 13 du PDF). Concentrez-vous sur la Définition 5 qui explique comment les formules sont construites récursivement à partir des variables propositionnelles et des connecteurs. Notez l'importance des parenthèses pour lever toute ambiguïté.

Essentiellement, les règles sont :

Toute variable propositionnelle ( $p, q, \dots$ ) est une formule bien formée.
Si $F$ est une formule bien formée, alors $(\neg F)$ l'est aussi.
Si $F$ et $G$ sont des formules bien formées, alors $(F \land G)$ , $(F \lor G)$ , $(F \Rightarrow G)$ , et $(F \Leftrightarrow G)$ le sont aussi.

Exercice de formalisation :

Traduisez la phrase suivante en une formule logique : "Si la batterie de mon téléphone est chargée et que le réseau est disponible, alors je peux appeler."

Identifiez d'abord les propositions atomiques.
Assignez-leur une variable.
Combinez-les avec les connecteurs appropriés.

Cliquez ici pour voir la solution.

Propositions atomiques :
- "La batterie de mon téléphone est chargée"
- "Le réseau est disponible"
- "Je peux appeler"
Variables :
- $p$ : La batterie est chargée.
- $q$ : Le réseau est disponible.
- $r$ : Je peux appeler.
Formule :
La partie "si... alors..." correspond à une implication. L'hypothèse ("si") est une conjonction ("et").
La formule est donc : $(p \land q) \Rightarrow r$

3. Les Tables de Vérité

La table de vérité d'une formule est un tableau qui donne sa valeur de vérité (Vrai ou Faux, souvent noté 1 ou 0) pour toutes les combinaisons possibles de valeurs de vérité de ses variables. Si une formule contient $n$ variables, sa table de vérité aura $2^{n}$ lignes.

Construire une table de vérité est la méthode la plus fondamentale pour analyser une formule, déterminer si elle est toujours vraie (une tautologie), parfois vraie (satisfaisable) ou toujours fausse (une antilogie ou contradiction).

La méthode est simple : on décompose la formule en ses sous-formules et on calcule leur valeur de vérité colonne par colonne.

[PDF] Logique propositionnelle et Logique des Prédicats

Retournons au polycopié pour étudier la méthode de construction d'une table de vérité.

Lisez la section 2.2.2 "Table de vérité d'une formule" (page 19 du PDF). Le "Point Méthode 2" est particulièrement important : il formalise la démarche de construction pas à pas.

Appliquons cette méthode à la formule que nous avons trouvée précédemment : $(p \land q) \Rightarrow r$ .
Elle contient 3 variables ( $p, q, r$ ), donc sa table de vérité aura $2^{3} = 8$ lignes.

Système combinatoire - Table de vérité et équations logiques — Illustration d'un système à 3 entrées (a, b, c) avec sa table de vérité. La structure est identique pour notre formule $(p \wedge q) \Rightarrow r$. Les entrées correspondent à nos variables $p, q, r$ et la sortie 's' à la valeur finale de notre formule.

Voici la construction de la table de vérité pour $(p \land q) \Rightarrow r$ :

$p$	$q$	$r$	$p \land q$	$(p \land q) \Rightarrow r$
1	1	1	1	1
1	1	0	1	0
1	0	1	0	1
1	0	0	0	1
0	1	1	0	1
0	1	0	0	1
0	0	1	0	1
0	0	0	0	1

Note : 1 représente "Vrai" et 0 représente "Faux".

On observe que la formule est fausse dans un seul cas : quand $p$ et $q$ sont vraies, mais que $r$ est fausse. Cela correspond bien à l'intuition : si la batterie est chargée et le réseau disponible, mais que je ne peux pas appeler, alors l'affirmation de départ est démentie. Dans tous les autres cas, elle reste valide.

Exercice de synthèse

Soit le raisonnement suivant :
"S'il pleut, je prends mon parapluie. Il ne pleut pas. Donc, je ne prends pas mon parapluie."

Formalisez ce raisonnement. Il s'agit d'une implication dont l'hypothèse est une conjonction de deux propositions et la conclusion est une troisième proposition.
- Utilisez $p$ pour "Il pleut".
- Utilisez $q$ pour "Je prends mon parapluie".
Construisez la table de vérité de la formule obtenue.
Le raisonnement est-il correct ? (Autrement dit, la formule est-elle une tautologie ?)

Cliquez ici pour la solution détaillée.

Formalisation :
- "S'il pleut, je prends mon parapluie" se formalise par $p \Rightarrow q$ .
- "Il ne pleut pas" se formalise par $\neg p$ .
- "Je ne prends pas mon parapluie" se formalise par $\neg q$ .
Le raisonnement complet "([prémisse 1] ET [prémisse 2]) IMPLIQUE [conclusion]" se formalise donc par :
$((p \Rightarrow q) \land (\neg p)) \Rightarrow (\neg q)$
Table de vérité :
Nous avons 2 variables ( $p, q$ ), donc $2^{2} = 4$ lignes.

$p$ $q$ $p \Rightarrow q$ $\neg p$ $\neg q$ $(p \Rightarrow q) \land (\neg p)$ $((p \Rightarrow q) \land (\neg p)) \Rightarrow (\neg q)$

1 1 1 0 0 0 1

1 0 0 0 1 0 1

0 1 1 1 0 1 0

0 0 1 1 1 1 1
Conclusion sur le raisonnement :
La formule n'est pas une tautologie, car elle est fausse sur la troisième ligne. Le raisonnement n'est donc pas valide.
Le cas où le raisonnement est faux est le suivant : il ne pleut pas ( $p = 0$ ), mais je prends quand même mon parapluie ( $q = 1$ ). Dans ce scénario, les deux prémisses ("S'il pleut, je prends mon parapluie" est vraie car l'hypothèse $p$ est fausse ; et "Il ne pleut pas" est vraie) sont respectées, mais la conclusion ("Je ne prends pas mon parapluie") est fausse. Cela montre bien la faille logique de ce raisonnement.

$p$	$q$	$p \Rightarrow q$	$\neg p$	$\neg q$	$(p \Rightarrow q) \land (\neg p)$	$((p \Rightarrow q) \land (\neg p)) \Rightarrow (\neg q)$
1	1	1	0	0	0	1
1	0	0	0	1	0	1
0	1	1	1	0	1	0
0	0	1	1	1	1	1

Conclusion de la leçon

Félicitations, vous avez terminé cette première étape cruciale.

Points clés à retenir :

La logique propositionnelle permet de modéliser des énoncés et des raisonnements à l'aide de variables et de connecteurs ( $\neg, \land, \lor, \Rightarrow, \Leftrightarrow$ ).
La formalisation est le processus de traduction d'une phrase en une formule logique bien formée, en respectant une syntaxe précise.
La table de vérité est un outil systématique et infaillible pour déterminer la valeur de vérité d'une formule pour toutes les combinaisons de vérité de ses composantes.

Dans la prochaine leçon, nous verrons que les tables de vérité, bien que fondamentales, deviennent très lourdes dès que le nombre de variables augmente. Nous explorerons alors une autre façon de prouver la validité d'un raisonnement : les règles d'inférence, comme le modus ponens. Cette approche "syntaxique" est plus proche de la manière dont les mathématiciens construisent leurs démonstrations.

Recommended resources

1. Propositions et Connecteurs Logiques

2. Formalisation : La Syntaxe des Propositions

3. Les Tables de Vérité

Exercice de synthèse

Conclusion de la leçon