#Logique propositionnelleCopier le lien

La logique propositionnelle formalise le raisonnement: elle remplace « si... alors... » par des symboles exacts et permettent de vérifier mécaniquement qu'un argument est valide. C'est l'outil derrière les conditions de code (raisonner sur if), les invariants de boucle, les préconditions de fonctions, et la correction des circuits.

Prérequis: manipulations ensemblistes de base, lecture de tables, un peu de Python (boucles, booléens).

Objectifs d'apprentissage:

• Écrire la syntaxe d'une formule (négation, conjonction, disjonction, implication, équivalence) et son contenu sémantique via les tables de vérité.
• Classifier une formule: tautologie, contradiction ou contingence.
• Simplifier via les équivalences usuelles (De Morgan, implication, contraposée, distribution).
• Vérifier la validité d'un argument (prémisses → conclusion) par table de vérité.
• Manipuler les quantificateurs ∀ et ∃, leur ordre et leurs négations.

#Syntaxe et sémantiqueCopier le lien

Les propositions (p, q, r...) sont des énoncés vrais ou faux. Les connecteurs, par priorité décroissante:

• ¬p (négation)
• p ∧ q (conjonction, ET)
• p ∨ q (disjonction, OU inclusif)
• p → q (implication)
• p ↔ q (équivalence)

La sémantique d'une formule est sa table de vérité: une ligne par valuation (attribution vrai/faux aux variables), une colonne pour le résultat. La table d'un connecteur se lit horizontalement; celle d'une formule complète verticalement. Table des trois connecteurs les plus subtils:

1p q | p→q | p↔q | p⊕q20 0 |  1  |  1  |  030 1 |  1  |  0  |  141 0 |  0  |  0  |  151 1 |  1  |  1  |  0

Deux surprises classiques:

• Implication et vacuité: p → q est vraie quand p est fausse, quel que soit q. « S'il pleut, j'annule » ne dit rien quand il ne pleut pas: la promesse tient.
• Ou inclusif: p ∨ q est vraie même si les deux le sont. Le « ou » exclusif (exactement l'un des deux) est p ⊕ q, soit p ↔ ¬q.

Classification d'une formule F selon sa table:

• Tautologie: vraie pour toutes les valuations (ex. p ∨ ¬p). On note ⊨ F.
• Contradiction: fausse pour toutes les valuations (ex. p ∧ ¬p).
• Contingence: tantôt vraie, tantôt fausse (ex. p → q).

Pour n variables, la table compte 2^n lignes: 4 pour deux variables, 8 pour trois, 1024 pour dix. Le coût double à chaque variable, d'où l'intérêt des équivalences pour simplifier sans tout dérouler.

#Animation: générer une table de véritéCopier le lien

#Équivalences usuellesCopier le lien

Deux formules sont équivalentes (F ≡ G) quand elles ont la même table de vérité. Ces réécritures préservent la vérité:

• Implication: p → q ≡ ¬p ∨ q
• Contraposée: p → q ≡ ¬q → ¬p
• De Morgan: ¬(p ∧ q) ≡ ¬p ∨ ¬q et ¬(p ∨ q) ≡ ¬p ∧ ¬q
• Double négation: ¬¬p ≡ p
• Distribution: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r), et la version duale
• Idempotence: p ∧ p ≡ p, p ∨ p ≡ p
• Absorption: p ∧ (p ∨ q) ≡ p
• Associativité et commutativité de ∧ et ∨

Exemple de simplification rédigée, chaque pas justifié:

1¬(p ∧ q) → p2≡ ¬¬(p ∧ q) ∨ p        (forme de l'implication)3≡ (p ∧ q) ∨ p          (double négation)4≡ p                    (absorption, car p est absorbé par p∧q)

Méthode de vérification: une table de vérité à 4 lignes confirme que ¬(p∧q)→p vaut 1 partout où p vaut 1, et aussi partout où p vaut 0 (l'implication est alors vacuously vraie). C'est une tautologie.

#Vérifier par table de vérité (Python)Copier le lien

Le branchement exhaustif se programme en quelques lignes: une boucle par proposition sur (False, True), et chaque connecteur traduit littéralement (« non p » → not p, « p→q » → (not p) or q).

Lecture: les colonnes de p → q et ¬q → ¬p coïncident ligne à ligne, c'est la preuve expérimentale de la contraposée. Pour trancher « tautologie » il faut vérifier chaque ligne; votre code peut ajouter all(...) sur les valuations.

#Validité d'un argumentCopier le lien

Un argument « des prémisses P1...Pk, conclure C » est valide si, chaque fois que toutes les prémisses sont vraies, la conclusion l'est aussi. Attention: valide ne veut pas dire que la conclusion est vraie dans l'absolu, seulement qu'elle ne peut pas être fausse quand les prémisses tiennent.

Schémas valides fondamentaux:

• Modus ponens: de p → q et p, conclure q.
• Modus tollens: de p → q et ¬q, conclure ¬p. (Si la promesse tient et que le concert n'est pas annulé, c'est qu'il n'a pas plu.)
• Syllogisme: de p → q et q → r, conclure p → r.
• Disjonction: de p ∨ q et ¬p, conclure q.

Deux pièges d'invalidité à reconnaître:

• Affirmation du conséquent: de p → q et q, conclure p. Invalide: la pluie annule, mais le concert peut être annulé pour une autre raison.
• Négation de l'antécédent: de p → q et ¬p, conclure ¬q. Invalide pour la même raison.

#Exercice: vérifier la validité d'un argument par tableCopier le lien

Vérifiez par table de vérité l'argument suivant, puis un des deux pièges:

• Argument A: prémisses (p → q) et (q → r), conclusion (p → r).
• Argument B (piège): prémisses (p → q) et q, conclusion p.

#Correction guidéeCopier le lien

Argument A (syllogisme), table à 8 lignes:

1p q r | p→q  q→r  p→r | prémisses vraies ?  conclusion20 0 0 |  1    1    1  | oui                 1  ✓30 0 1 |  1    1    1  | oui                 1  ✓40 1 0 |  1    0    1  | non (P2 fausse)50 1 1 |  1    1    1  | oui                 1  ✓61 0 0 |  0    1    0  | non (P1 fausse)71 0 1 |  0    1    0  | non (P1 fausse)81 1 0 |  1    0    0  | non (P2 fausse)91 1 1 |  1    1    1  | oui                 1  ✓

Sur toutes les lignes où les deux prémisses valent 1, la conclusion vaut 1: l'argument A est valide.

Argument B (affirmation du conséquent):

1p q | p→q | prémisses ? | conclusion p20 0 |  1  | non30 1 |  1  | OUI         | 0  ✗ contre-exemple41 0 |  0  | non (P2 fausse)51 1 |  1  | OUI         | 1  ✓

La ligne (p=0, q=1) montre les prémisses vraies et la conclusion fausse: l'argument B est invalide. C'est exactement le rôle d'un contre-exemple: une seule ligne suffit pour invalider, il les faut toutes pour valider.

Programme de vérification correspondant:

1import itertools2 3def valide(premisses, conclusion, vars):4    for vals in itertools.product([False, True], repeat=len(vars)):5        env = dict(zip(vars, vals))6        if all(p(env) for p in premisses) and not conclusion(env):7            return False, vals   # contre-exemple trouvé8    return True, None9 10# Argument A: syllogisme, valide11okA, ceA = valide(12    [lambda e: (not e['p']) or e['q'], lambda e: (not e['q']) or e['r']],13    lambda e: (not e['p']) or e['r'],14    ['p', 'q', 'r'])

Méthode à retenir: pour prouver la validité, déroulez toutes les lignes à prémisses vraies et vérifiez la conclusion sur chacune; pour prouver l'invalidité, exhibez une seule ligne (un contre-exemple) où les prémisses sont vraies et la conclusion fausse.

#Quantificateurs du premier ordreCopier le lien

Les propositions deviennent des prédicats P(x) dépendant de variables, quantifiés:

• ∀x P(x): « pour tout x, P(x) », universel.
• ∃x P(x): « il existe (au moins) un x tel que P(x) », existentiel.

Deux règles de négation à connaître par cœur (les quantificateurs s'échangent):

• ¬(∀x P(x)) ≡ ∃x ¬P(x)
• ¬(∃x P(x)) ≡ ∀x ¬P(x)

Le même contre-exemple permet de réfuter un ∀ (un seul x suffit), et de vérifier un ∃ (un seul x suffit aussi). Prendre l'habitude de chercher le témoin ou le contre-exemple le plus simple possible.

L'ordre des quantificateurs change le sens, sauf entre deux ∀ ou deux ∃:

• ∀x ∃y P(x, y): pour chaque x, on peut trouver un y (qui peut dépendre de x).
• ∃y ∀x P(x, y): un seul y fonctionne pour tous les x simultanément.

La seconde affirmation est strictement plus forte. Exemple parlant sur ℕ: « ∀n ∃m, m > n » est vraie (prendre m = n+1, adapté à chaque n); « ∃m ∀n, m > n » est fausse (aucun entier ne majore tous les autres). Sur ℝ et sur une machine, un exemple type: « ∀ ε > 0 ∃ δ > 0 » (limite) ne permute jamais ses quantificateurs sans changer de contenu mathématique.

Traduction type en code, utile pour tester ses intuitions sur de petits domaines:

1domaine = range(6)2pour_tout = all(m > n for n in domaine for m in domaine)     # faux3il_existe = any(all(m > n for n in domaine) for m in domaine) # faux4# mais: ∀n ∃m, m > n  sur un domaine borné est vraie:5all(any(m > n for m in domaine) for n in domaine[:-1])        # vrai (borné)

La permutation ∀∃ / ∃∀ est la première source d'erreurs dans les énoncés d'examen; toujours relire en français avant de conclure.

#Conséquence logique et modèlesCopier le lien

Jusqu'ici on a évalué une formule isolée. Le vrai objet d'étude est la conséquence logique : une formule G suit d'un ensemble de formules T.

Modèle. Soit T un ensemble de formules. Une valuation (ou interprétation) est un modèle de T si elle rend vraies toutes les formules de T. On note $T \models G$ lorsque tout modèle de T est aussi un modèle de G.

Trois remarques qui évitent la plupart des contresens:

• $\models G$ (sans prémisses) signifie que G est une tautologie.
• $F \equiv G$ équivaut à $F \models G$ et $G \models F$: l'équivalence logique est une double conséquence.
• Une implication $F \to G$ est une formule; l'énoncé $F \models G$ est une affirmation sur des formules. Ils coïncident ici (théorème de déduction: $F \models G$ si et seulement si $\models F \to G$), mais pas au premier ordre, où les quantificateurs compliquent tout.

Méthode de décision en deux gestes.

• Pour prouver $T \models G$: on raisonne sur un modèle quelconque de T — supposer toutes les formules de T vraies, puis dériver G par les équivalences usuelles. On peut aussi démontrer la contraposée: si G est fausse, alors une des formules de T est fausse.
• Pour réfuter $T \models G$: exhiber une seule valuation qui rend vraies toutes les formules de T et fausse G. C'est un contre-exemple, exactement comme pour un ∀.

Exemple rédigé. Soit $T = \{a \to (b \lor c),\; b \to (a \lor c),\; a \lor c,\; (a \land b) \lor c\}$. A-t-on $T \models (a \lor b) \land (b \lor c)$?

Réfutation. Prenons $a = 0$, $b = 0$, $c = 1$. Alors $a \to (b \lor c) = 1$, $b \to (a \lor c) = 1$, $a \lor c = 1$, $(a \land b) \lor c = 1$: les quatre prémisses sont vraies. Mais $(a \lor b) \land (b \lor c) = 0 \land 1 = 0$. Donc $T \not\models (a \lor b) \land (b \lor c)$: la ligne $(0, 0, 1)$ est un contre-exemple, et un seul suffit.

Attention à la lecture inverse: une valuation qui rend G vraie ne prouve rien. Pour prouver, il faut vérifier toutes les lignes où les prémisses sont vraies — c'est la même asymétrie que pour la validité d'un argument, vue plus haut.

#Forme clausale et règle de résolutionCopier le lien

La méthode des tables de vérité a un coût exponentiel: $2^n$ lignes pour $n$ variables. Sur des formules à dix variables, cela fait 1024 lignes; sur trente, un milliard. La résolution remplace l'énumération par un calcul symbolique sur des clauses.

Vocabulaire.

• Un littéral est une variable $p$ ou sa négation $\neg p$.
• Une clause est une disjonction de littéraux, par exemple $a \lor \neg b \lor c$.
• Une formule est en forme clausale (ou forme normale conjonctive, CNF) si c'est une conjonction de clauses: $(a \lor b) \land (\neg a \lor c) \land c$.

Mise sous forme clausale. Trois étapes mécaniques:

1. Éliminer les connecteurs $\to$ et $\leftrightarrow$ par $p \to q \equiv \neg p \lor q$ et $p \leftrightarrow q \equiv (\neg p \lor q) \land (p \lor \neg q)$.
2. Descendre les négations jusqu'aux variables par De Morgan et la double négation.
3. Distribuer $\lor$ sur $\land$ jusqu'à obtenir une conjonction de disjonctions.

Exemple. $(a \lor c) \to (b \lor c) \equiv \neg(a \lor c) \lor b \lor c \equiv (\neg a \land \neg c) \lor b \lor c \equiv (\neg a \lor b \lor c) \land (\neg c \lor b \lor c)$. La seconde clause contient $c$ et $\neg c$: c'est une tautologie, donc la forme clausale se réduit à la clause unique $\neg a \lor b \lor c$.

Règle de résolution. De deux clauses contenant un littéral et son opposé, on déduit la clause formée des autres littéraux:

$\frac{C_1 \lor p \qquad C_2 \lor \neg p}{C_1 \lor C_2}$

La règle est correcte (sound): toute valuation qui rend vraies les deux clauses rend vraie la résolvante, car elle donne à $p$ une valeur, et c'est l'autre clause qui fournit alors un littéral vrai. Elle n'est pas complète au sens où elle n'engendre pas toutes les conséquences — mais elle l'est pour la réfutation:

Théorème (réfutation). $T \models G$ si et seulement si l'ensemble de clauses $T \cup \{\neg G\}$ permet de dériver la clause vide, notée $\square$, par applications répétées de la règle de résolution.

C'est ce procédé qu'on appelle zéro-résolution (ou preuve par réfutation): on ajoute la négation de la conclusion aux prémisses, on met le tout en forme clausale, et on cherche à produire $\square$ — la clause vide, satisfaite par aucune valuation, ce qui établit l'insatisfaisabilité et donc la conséquence.

Exemple rédigé. Soit $T = \{(a \lor b) \land c,\; \neg a \land (b \lor c),\; a \lor \neg b \lor c,\; (a \lor c) \to (b \lor c)\}$. Montrons $T \models a \to (b \lor c)$.

1. Clauses de T. $\{a, b\}$, $\{c\}$, $\{\neg a\}$, $\{b, c\}$, $\{a, \neg b, c\}$, $\{\neg a, b, c\}$ (la dernière vient du calcul ci-dessus).
2. Négation de la conclusion. $\neg(a \to (b \lor c)) \equiv a \land \neg b \land \neg c$, soit les trois clauses unitaires $\{a\}$, $\{\neg b\}$, $\{\neg c\}$.
3. Résolution. $\{a\}$ et $\{\neg a\}$ donnent $\square$: les prémisses contiennent $\neg a$ et la négation de la conclusion contient $a$. La réfutation est close.

Le calcul est court parce que la contradiction était visible; en pratique on enchaîne les résolutions en éliminant une variable à la fois, et l'ordre choisi ne change pas le résultat final (la méthode est complète: si la contradiction existe, une stratégie systématique la trouve). Le lien avec l'informatique est direct: c'est ce mécanisme qui sert de moteur d'inférence en programmation logique et dans les démonstrateurs automatiques.

#Calcul des prédicats: interprétationsCopier le lien

Au premier ordre, une formule n'est ni vraie ni fausse « en soi »: elle dépend du domaine sur lequel on l'interprète.

Une interprétation (ou structure) fixe:

• un ensemble non vide $D$, le domaine;
• un élément de $D$ pour chaque symbole de constante;
• une fonction $D^k \to D$ pour chaque symbole de fonction d'arité $k$;
• une relation sur $D^k$ pour chaque symbole de prédicat d'arité $k$; le symbole $=$ est toujours l'égalité.

Une formule est vraie dans une interprétation si elle est satisfaite pour toutes les valeurs des variables; valide si elle est vraie dans toutes les interprétations; satisfaisable s'il existe au moins une interprétation qui la rend vraie. Valide $\Rightarrow$ satisfaisable, jamais l'inverse.

Exemple rédigé. Considérons $\forall x\, \forall y\; \neg(x = y) \to \neg(x \times y = c)$, où $\times$ est un symbole d'opération binaire et $c$ une constante.

Interprétation qui rend la formule vraie. Domaine $D = \{2, 3, 5\}$, $\times$ interprété par la multiplication usuelle, $c$ interprété par $30$. Les produits de deux éléments distincts sont $2 \times 3 = 6$, $2 \times 5 = 10$, $3 \times 5 = 15$, et aucun n'est égal à $30$: l'implication est vraie pour tous les couples, donc la formule est vraie.

Interprétation qui la rend fausse. Domaine $D = \mathbb{R}$, $\times$ la multiplication, $c = 1$. Prenons $x = 2$ et $y = \tfrac{1}{2}$: on a $x \neq y$ mais $x \times y = 1 = c$. L'antécédent est vrai et le conséquent faux: la formule est fausse dans cette interprétation.

Moralité: pour réfuter une formule du premier ordre, une interprétation suffit (c'est le contre-exemple); pour l'établir, il faut un raisonnement valable dans toutes les interprétations, ce qui interdit d'utiliser une propriété particulière des nombres. C'est précisément pourquoi les preuves du premier ordre se font par règles d'inférence sur la syntaxe, et non par énumération.

#Mini-quizCopier le lien