Éléments de logique - cours complet (propositions, prédicats et raisonnement)

Ce cours reprend et complète le chapitre « Éléments de logique » du module UTC501 (Outils mathématiques pour l'informatique, CNAM Hauts-de-France, d'après B. Foltz). Il a été réorganisé, les coquilles des tables de vérité et de certaines définitions ont été corrigées, des intuitions ont été ajoutées, et surtout tous les exercices sont corrigés en fin d'article.

1. Introduction : syntaxe et sémantique

On distingue deux niveaux de logique :

• la logique des propositions, qui définit les lois formelles du raisonnement ;
• la logique des prédicats, qui formalise le langage des mathématiques en autorisant les quantificateurs ∀ (« pour tout ») et ∃ (« il existe »).

Pour décrire proprement ce langage, on sépare toujours deux aspects :

• La syntaxe : comment on écrit les formules. Ex. : (a ∨ b) → b est une formule propositionnelle ; ∃x | (x ∨ b) → b relève des prédicats.
• La sémantique : ce que veulent dire les formules, en attribuant aux variables une valeur (vrai/faux) puis en calculant la valeur de la formule. Ex. : pour a = vrai et b = faux, (a ∨ b) → b est fausse.

Idée-clé. La syntaxe ne dit jamais si une formule est vraie ; elle dit seulement si elle est bien écrite. C'est la sémantique (les tables de vérité) qui donne les valeurs.

2. Partie I — Le calcul des propositions

A. Syntaxe

Définition — Variable propositionnelle. Un énoncé indécomposable dont on peut affirmer sans ambiguïté qu'il est vrai ou faux. Exemples : « 4 est un nombre impair » (faux), « 3 × 2 = 6 » (vrai).

Le paradoxe du menteur : « cette phrase est fausse » n'est PAS une variable propositionnelle. Si elle est vraie, alors elle est fausse, et inversement : il y a ambiguïté, donc on l'exclut.

Alphabet de la logique propositionnelle : les constantes Faux (⊥) et Vrai (⊤) ; une infinité de variables a, b, c… ; la négation ¬ ; quatre connecteurs binaires — conjonction ∧ (ET), disjonction ∨ (OU), implication →, équivalence ↔ ; et les séparateurs ( ).

OU inclusif vs OU exclusif :

• OU inclusif (∨) : au moins l'une des propositions est vraie, éventuellement les deux (« une résidence accueille des personnes malades ou âgées »).
• OU exclusif (⊕) : l'une ou l'autre mais pas les deux (« j'irai en train ou en voiture »).

Définition — Formule propositionnelle (inductive) : toute constante et toute variable est une formule (les formules atomiques) ; si F est une formule, (¬F) en est une ; si F₁, F₂ sont des formules, alors (F₁ ∧ F₂), (F₁ ∨ F₂) et (F₁ → F₂) en sont.

Priorités (de la plus forte à la plus faible) : ¬ > ∧ > ∨ > → > ↔. Les opérateurs ∧ et ∨ sont associatifs à gauche : a ∧ b ∧ c se lit (a ∧ b) ∧ c. Les parenthèses permettent toujours de contredire ces règles.

Arbre d'expression : toute formule possède un arbre dont les feuilles sont les variables et les nœuds internes les connecteurs. Ex. : ¬a ∨ (b ∧ c) a pour racine ∨, à gauche ¬a, à droite b ∧ c.

B. Sémantique

Valeur de vérité. Propriété d'une formule d'être vraie (1) ou fausse (0). On note 𝔹 = {0, 1}.

Attention : ⊤ et ⊥ sont des symboles du langage ; 1 et 0 sont des valeurs mathématiques. Deux mondes distincts.

Tables de vérité des connecteurs :

• Conjonction a∧b : vraie uniquement si a ET b sont vraies.
• Disjonction a∨b : fausse uniquement si a et b sont fausses (OU inclusif).
• Implication a→b : fausse uniquement quand a est vraie et b fausse.
• Équivalence a↔b : vraie quand a et b ont la même valeur.

Le piège de l'implication. « 2+2 = 5 → √2 = 2 » est vraie ! La prémisse étant fausse, l'implication est automatiquement vraie. En logique, « du faux on peut déduire n'importe quoi ».

Trois connecteurs utiles en informatique — XOR (⊕), NAND (non-et), NOR (non-ou) :

NAND et NOR sont universels : à eux seuls ils reconstruisent tous les autres connecteurs — d'où leur importance pour les circuits logiques.

Valuation et interprétation. Une valuation v attribue une valeur à chaque variable (v : P → 𝔹), puis se prolonge en une interprétation ⟦·⟧ : ⟦¬φ⟧ = 1 − ⟦φ⟧ ; ⟦φ ∧ ψ⟧ = min(⟦φ⟧, ⟦ψ⟧) ; ⟦φ ∨ ψ⟧ = max(⟦φ⟧, ⟦ψ⟧) ; ⟦φ → ψ⟧ = f→(⟦φ⟧, ⟦ψ⟧) ; ⟦φ ↔ ψ⟧ = 1 ssi ⟦φ⟧ = ⟦ψ⟧.

Exemple. Pour v(a)=1, v(b)=0 : ⟦(a ∧ b) ∨ ¬b → ¬a⟧ = f→(max(min(1,0), ¬0), ¬1) = f→(max(0,1), 0) = f→(1, 0) = 0.

Remarque : une formule à n variables admet 2ⁿ interprétations ; sa valeur ne dépend que des variables qui y figurent.

C. Théorie des modèles

• Une interprétation satisfait φ si ⟦φ⟧ = 1 ; elle la falsifie si ⟦φ⟧ = 0.
• Un modèle de φ la satisfait ; un contre-modèle la falsifie.
• φ est cohérente si elle a au moins un modèle ; incohérente sinon.
• φ est valide si elle n'a aucun contre-modèle ; invalide sinon.

Théorème. φ est valide ⟺ ¬φ est incohérente.
Preuve : si ¬φ est cohérente, φ admet un contre-modèle, donc invalide ; si ¬φ est incohérente, φ n'a aucun contre-modèle, donc valide. ∎

Remarque : décider la validité/cohérence est NP-complet ; la méthode naïve (2ⁿ lignes) explose avec le nombre de variables.

D. Conséquence logique et équivalence

Conséquence logique. φ ⊨ ψ si tout modèle de φ est un modèle de ψ. Ex. : a ∧ b ⊨ a → b.

Théorème : φ ⊨ ψ ⟺ φ → ψ est une formule valide.

Équivalence sémantique. φ ≡ ψ si φ ⊨ ψ et ψ ⊨ φ, c.-à-d. si elles ont la même valeur pour toute interprétation.

Attention : ⊨ et ≡ sont des symboles métalogiques (ils parlent au sujet des formules) ; ne pas les confondre avec → et ↔, connecteurs internes.

Les lois fondamentales (pour simplifier les formules) :

• Involution : ¬¬φ ≡ φ
• Éléments neutres : φ ∧ ⊤ ≡ φ ; φ ∨ ⊥ ≡ φ
• Éléments absorbants : φ ∧ ⊥ ≡ ⊥ ; φ ∨ ⊤ ≡ ⊤
• Idempotence : φ ∧ φ ≡ φ ; φ ∨ φ ≡ φ
• Complémentarité : φ ∧ ¬φ ≡ ⊥ (non-contradiction) ; φ ∨ ¬φ ≡ ⊤ (tiers exclu)
• Commutativité : φ ∧ ψ ≡ ψ ∧ φ ; φ ∨ ψ ≡ ψ ∨ φ
• Associativité : φ ∧ (ψ ∧ θ) ≡ (φ ∧ ψ) ∧ θ (idem ∨)
• Distributivité : φ ∧ (ψ ∨ θ) ≡ (φ ∧ ψ) ∨ (φ ∧ θ) ; φ ∨ (ψ ∧ θ) ≡ (φ ∨ ψ) ∧ (φ ∨ θ)
• De Morgan : ¬(φ ∧ ψ) ≡ ¬φ ∨ ¬ψ ; ¬(φ ∨ ψ) ≡ ¬φ ∧ ¬ψ
• Réécriture de → : φ → ψ ≡ ¬φ ∨ ψ
• Transposition : φ → ψ ≡ ¬ψ → ¬φ
• Exportation : (φ ∧ ψ) → θ ≡ φ → (ψ → θ)

Attention : l'implication n'est ni commutative ni associative. a → b diffère de b → a (sa réciproque).

Contraposée et réciproque de φ → ψ : la contraposée ¬ψ → ¬φ est toujours équivalente ; la réciproque ψ → φ ne l'est pas. Ex. : « si rectangle, alors 4 angles droits » a pour contraposée « si pas 4 angles droits, alors pas rectangle » (équivalente).

E. Éléments de modélisation

Modéliser, c'est traduire un énoncé courant en formule. Ex. : « S'il pleut, alors il y a des nuages » → on pose p = « il pleut », n = « il y a des nuages » ; la formule est Σ : p → n. Elle doit être fausse exactement quand l'énoncé est contredit (il pleut sans nuage).

3. Partie II — Le calcul des prédicats

Le calcul des prédicats étend le calcul propositionnel : on parle d'objets d'un domaine 𝔻 grâce aux quantificateurs ∀ et ∃.

Pourquoi ? « Tout homme est mortel ; Socrate est un homme ; donc Socrate est mortel » se traduit en propositionnel par a ∧ b → c… mais cette traduction n'est PAS valide. En prédicats : ∀x (H(x) → M(x)) ; H(Socrate) ⊨ M(Socrate) — et là le raisonnement EST valide.

A. Syntaxe

Prédicat : propriété/relation sur des éléments d'un domaine 𝔻 ; fonction 𝔻ⁿ → 𝔹. L'entier n est son arité.

Signature Σ : symboles de fonctions + symboles de prédicats, chacun d'arité fixée.

Alphabet : constantes, variables (du domaine), signature, connecteurs ¬ ∧ ∨ → ↔, quantificateurs ∀ et ∃, séparateurs. On utilise aussi ∃! (« il existe un unique »).

Termes : variables et constantes ; si f est d'arité n et t₁…tₙ des termes, f(t₁,…,tₙ) est un terme. Formule atomique : p(t₁,…,tₙ). On combine ensuite comme en propositionnel, plus : si F est une formule et x une variable, (∀x F) et (∃x F) sont des formules.

Variables libres et liées. Dans (∀x F), F est le champ du quantificateur et x est quantifiée. Une occurrence est liée si elle est dans le champ d'un quantificateur qui la quantifie, libre sinon.

Exemple. Dans ∀y ((p(x) ∨ ∃x p(x)) ∧ q(y)) : la 1ʳᵉ occurrence de x est libre, la 2ᵉ liée (par ∃x), et y est liée (par ∀y).

B. Sémantique

∀ (« pour tout ») : tous les éléments du domaine vérifient la propriété (∀x ∈ ℝ, x² ≥ 0). ∃ (« il existe au moins un ») : au moins un la vérifie (∃x ∈ ℝ, x² ≤ 0, vraie pour x = 0). La virgule se lit « tel que ».

L'ordre des quantificateurs est crucial.
∃x ∈ ℝ, ∀y ∈ ℝ, x < y est FAUSSE (pas de réel plus petit que tous).
∀y ∈ ℝ, ∃x ∈ ℝ, x < y est VRAIE (pour tout y, prendre x = y − 1).
Mêmes quantificateurs intervertis, sens et valeur changés !

Théorème : deux quantificateurs de même nature peuvent être permutés (∀x ∀y ≡ ∀y ∀x ; ∃x ∃y ≡ ∃y ∃x). Mais ∀x ∃y ≠ ∃y ∀x.

Négation (De Morgan généralisé) : ¬(∀x, P(x)) ≡ ∃x, ¬P(x) ; ¬(∃x, P(x)) ≡ ∀x, ¬P(x). Pur bon sens : la négation de « tous les étudiants travaillent » est « il existe au moins un étudiant qui ne travaille pas ».

Sémantique des quantificateurs (corrigée) : ⟦∀x, P(x)⟧ = 1 si pour tout d ∈ 𝔻, P(x:=d) vaut 1 ; ⟦∃x, P(x)⟧ = 1 s'il existe d ∈ 𝔻 tel que P(x:=d) vaut 1. (Le polycopié écrit par erreur « pour tout d » dans les deux cas ; pour le ∃ il faut lire « il existe d ».)

Quelques équivalences : ¬∀x, F ≡ ∃x, ¬F ; ¬∃x, F ≡ ∀x, ¬F ; ∀x, (F₁ ∧ F₂) ≡ (∀x, F₁) ∧ (∀x, F₂) ; ∃x, (F₁ ∨ F₂) ≡ (∃x, F₁) ∨ (∃x, F₂). Attention : ∀ ne se distribue pas sur ∨, ∃ ne se distribue pas sur ∧.

C. Modélisation en prédicats

• Tous les hommes sont méchants : ∀x (H(x) → M(x))
• Seuls les hommes sont méchants : ∀x (M(x) → H(x))
• Il existe un homme méchant : ∃x (H(x) ∧ M(x))
• Il n'existe pas d'homme méchant : ¬∃x (H(x) ∧ M(x))
• Il existe un homme qui aime tous les chiens : ∃x (H(x) ∧ ∀y (C(y) → a(x,y)))

Règle d'or : avec ∀ on utilise presque toujours une implication (→) ; avec ∃ presque toujours une conjonction (∧).

4. Partie III — Les techniques de raisonnement

A. Rédiger une démonstration

Distinguer les hypothèses (admises) de la conclusion (à démontrer). Puis : introduire des notations, rapprocher d'un problème connu, tester des cas particuliers, structurer les étapes en citant les théorèmes, relire. Erreurs classiques : mal nier une proposition ; croire que « quelques exemples » prouvent un énoncé général ; donner le même nom à deux objets différents.

B. Disjonction de cas

Pour démontrer P, on choisit Q et on prouve à la fois P ∧ Q et P ∧ ¬Q. Justification : (P ∧ Q) ∨ (P ∧ ¬Q) ≡ P ∧ (Q ∨ ¬Q) ≡ P.

Exemple. n(n+1) est divisible par 2 : si n pair, n l'est donc le produit aussi ; si n impair, n+1 est pair donc le produit aussi. ∎

C. Contraposée

Pour démontrer P → Q, il est équivalent de démontrer ¬Q → ¬P (souvent plus simple).

Exemple. xy ≠ 0 → (x ≠ 0 ∧ y ≠ 0). Contraposée : (x = 0 ∨ y = 0) → xy = 0, évidente. ∎ Ne pas confondre avec la réciproque Q → P : (x ∈ [0;2]) → (x² ∈ [0;4]) est vraie mais sa réciproque est fausse (x = −1).

D. Contre-exemple

Pour réfuter ∀x ∈ E, P(x), il suffit d'exhiber un x tel que ¬P(x). Ex. : ∀x ∈ ℝ, x² > 0 est faux car x = 0 donne 0. ∎

E. Absurde

Pour démontrer P, on suppose ¬P et on aboutit à une contradiction. Ex. : x ≠ 0 → 1/x ≠ 0 ; si 1/x = 0, en multipliant par x on obtient 1 = 0, absurde. ∎

F. Récurrence

Axiomes de Peano (fondent ℕ) : 0 est entier ; tout n a un successeur S(n) ; 0 n'est successeur de personne ; S injective ; toute partie de ℕ contenant 0 et stable par S est ℕ tout entier (axiome de récurrence).

Principe. Pour Pₙ vraie pour tout n ≥ n₀ : (1) initialisation P(n₀) vraie ; (2) hérédité Pₖ ⟹ Pₖ₊₁. Alors Pₙ est vraie pour tout n ≥ n₀.

Exemple 1 : 2ⁿ > n. P₀ : 1 > 0 ✓ ; hérédité : 2ᵏ⁺¹ = 2·2ᵏ > 2k ≥ k + 1. ✓

Exemple 2 : Sₙ = Σ(i=0..n)(2i+1) = (n+1)². S₀ = 1 = 1² ✓ ; Sₖ₊₁ = Sₖ + (2k+3) = (k+1)² + (2k+3) = (k+2)². ✓

5. Annexe — Sommes et produits

Somme : Σ(i=p..q) f(i) = f(p) + … + f(q). Produit : Π(i=p..q) f(i) = f(p) × … × f(q).

• Σ(i=1..n) i = n(n+1)/2
• Σ(i=1..n) i² = n(n+1)(2n+1)/6
• Σ(i=0..n) (2i+1) = (n+1)²
• Σ(i=0..n) rⁱ = (r^(n+1) − 1)/(r − 1) si r ≠ 1 (somme géométrique)

6. Corrigés des exercices

Ajoutés ici (absents du polycopié) pour rendre le cours auto-suffisant.

Exercice 1 — Variable propositionnelle ?

• « Il fait beau. » → OUI (déclaratif).
• « Il fera beau demain. » → OUI (tranchable à terme).
• « 1 + 1 = 2 » → OUI (vrai).
• « Attention ! » → NON (interjection).
• « Bonjour » → NON (pas une assertion).
• « n est pair. » → NON (dépend de n : c'est un prédicat).
• « Le ciel bleu » → NON (groupe nominal).
• « 8 » → NON (un nombre n'est ni vrai ni faux).

Exercice 2 — Simplifier.

• ((¬a ∧ b) ∨ c) → (a ∧ c) ≡ ¬(¬a ∧ (b ∨ c)) ≡ a ∨ (¬b ∧ ¬c) (la formule n'est fausse que pour (0,0,1), (0,1,0), (0,1,1)).
• (¬a → b) ∨ (a ↔ (b ∧ c)) : comme ¬a → b ≡ a ∨ b, et que pour a = b = 0 le second terme vaut 0 ↔ 0 = 1, la formule est une tautologie ≡ ⊤.

Exercice 3 — a ∧ ¬a : 0 dans les deux cas → ≡ ⊥ (non-contradiction).

Exercice 4 — a ∨ ¬a : 1 dans les deux cas → ≡ ⊤ (tiers exclu).

Exercice 5 — 1) Table de ¬a ∨ b :

Les colonnes coïncident : ¬a ∨ b ≡ a → b. 2) a ∧ b → ¬a ∨ b est une tautologie (vraie).

Exercice 6 — a ↔ ¬a : 0 dans les deux cas → faux (anti-tautologie).

Exercice 7 — Tables :

La seconde formule (≡ a ∧ ¬b ∧ c) n'est vraie que pour (1,0,1).

Exercice 8 — Distributivité : on vérifie sur les 8 lignes que φ ∧ (ψ ∨ θ) et (φ ∧ ψ) ∨ (φ ∧ θ) ont la même colonne. ∎

Exercice 9 — De Morgan :

Colonnes 1=2 et 3=4 : ¬(a∧b) ≡ ¬a∨¬b et ¬(a∨b) ≡ ¬a∧¬b. ∎

7. Mémo récapitulatif

• Implication : a → b ≡ ¬a ∨ b ; fausse seulement quand a vrai et b faux.
• Contraposée ¬b → ¬a = équivalente ; réciproque b → a = non équivalente.
• De Morgan : ¬(a∧b) ≡ ¬a∨¬b ; ¬(a∨b) ≡ ¬a∧¬b ; ¬∀ ≡ ∃¬ ; ¬∃ ≡ ∀¬.
• Quantificateurs : ∀ va avec → ; ∃ va avec ∧ ; l'ordre ∀∃ ≠ ∃∀.
• Validité : φ valide ⟺ ¬φ incohérente.
• Méthodes de preuve : directe, disjonction de cas, contraposée, contre-exemple, absurde, récurrence.

Source : cours UTC501 « Éléments de logique », CNAM Hauts-de-France (B. Foltz), 2019-2020 — réorganisé et complété (corrigés, corrections de coquilles, intuitions ajoutées).