ÉLÉMENTS DE LOGIQUE — COURS COMPLET
Logique propositionnelle, calcul des prédicats et techniques de 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.

SOMMAIRE
1. Introduction : syntaxe et sémantique
2. Partie I — Le calcul des propositions
3. Partie II — Le calcul des prédicats
4. Partie III — Les techniques de raisonnement
5. Annexe — Sommes et produits
6. Corrigés des exercices
7. Mémo récapitulatif


═══════════════════════════════════════════════════════════
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 (les règles de grammaire).
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, la formule (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.

DÉFINITION — Alphabet. L'alphabet de la logique propositionnelle contient :
• les constantes Faux (⊥) et Vrai (⊤) ;
• une infinité dénombrable de variables : a, b, c, … ;
• un connecteur unaire : la négation ¬ ;
• quatre connecteurs binaires : conjonction ∧ (ET), disjonction ∨ (OU),
implication → , équivalence ↔ ;
• les séparateurs ( et ).

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 travailler en train ou en voiture ».

DÉFINITION — Formule propositionnelle (définition inductive) :
• toute constante (⊤, ⊥) et toute variable est une formule (les formules ATOMIQUES) ;
• si F est une formule, alors (¬F) est une formule ;
• si F1 et F2 sont des formules, alors (F1 ∧ F2), (F1 ∨ F2) et (F1 → F2) sont des formules.

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 le sous-arbre b ∧ c. L'arbre lève toute ambiguïté de lecture.


──────────────────────────────
B. SÉMANTIQUE
──────────────────────────────

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

Attention : ⊤ et ⊥ sont des SYMBOLES du langage (syntaxe) ; 1 et 0 sont des VALEURS
mathématiques (sémantique). Deux mondes distincts.

TABLES DE VÉRITÉ DES CONNECTEURS
(lecture : pour chaque ligne (a,b), valeur de chaque connecteur)

a b | ¬a | a∧b | a∨b | a→b | a↔b | a⊕b
0 0 | 1 | 0 | 0 | 1 | 1 | 0
0 1 | 1 | 0 | 1 | 1 | 0 | 1
1 0 | 0 | 0 | 1 | 0 | 0 | 1
1 1 | 0 | 1 | 1 | 1 | 1 | 0

• 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 ! Comme la prémisse
(2+2 = 5) est 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).

a b | XOR | NAND | NOR
0 0 | 0 | 1 | 1
0 1 | 1 | 1 | 0
1 0 | 1 | 1 | 0
1 1 | 0 | 0 | 0

NAND et NOR sont dits 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 → 𝔹). Elle se prolonge en
une interprétation ⟦·⟧ sur toutes les formules :
• ⟦¬φ⟧ = 1 − ⟦φ⟧
• ⟦φ ∧ ψ⟧ = min(⟦φ⟧, ⟦ψ⟧)
• ⟦φ ∨ ψ⟧ = max(⟦φ⟧, ⟦ψ⟧)
• ⟦φ → ψ⟧ = f→(⟦φ⟧, ⟦ψ⟧)
• ⟦φ ↔ ψ⟧ = 1 si et seulement si ⟦φ⟧ = ⟦ψ⟧

Exemple de calcul, 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 possibles. Sa valeur ne
dépend que des valeurs 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 φ est une interprétation qui la satisfait ; un CONTRE-MODÈLE, une
interprétation qui la falsifie.
• φ est COHÉRENTE (satisfaisable) si elle a au moins un modèle ; INCOHÉRENTE sinon.
• φ est VALIDE si elle n'a AUCUN contre-modèle ; INVALIDE sinon.

Formule valide : a → a (TAUTOLOGIE — vraie pour toute interprétation)
Cohérente mais non valide: a → ¬a (CONTINGENTE — vraie ici, fausse là)
Incohérente : a ∧ ¬a (ANTI-TAUTOLOGIE — fausse pour toute interprétation)

On a : « φ valide ⟹ φ cohérente » et « φ incohérente ⟹ φ invalide ».

THÉORÈME. φ est valide ⟺ ¬φ est incohérente.
Preuve : si ¬φ est cohérente, φ admet un contre-modèle, donc est invalide ; si ¬φ est
incohérente, φ n'a aucun contre-modèle, donc est valide. ∎

Remarque : décider la validité (ou la cohérence) est un problème NP-complet : la méthode
naïve (tester les 2ⁿ lignes) explose avec le nombre de variables.


──────────────────────────────
D. CONSÉQUENCE LOGIQUE ET ÉQUIVALENCE
──────────────────────────────

CONSÉQUENCE LOGIQUE : φ ⊨ ψ (« φ a pour conséquence ψ ») si tout modèle de φ est aussi
un modèle de ψ. Exemple : a ∧ b ⊨ a → b.

THÉORÈME : φ ⊨ ψ ⟺ φ → ψ est une formule valide.

ÉQUIVALENCE SÉMANTIQUE : φ ≡ ψ si φ ⊨ ψ et ψ ⊨ φ, c.-à-d. si φ et ψ ont la même valeur
pour TOUTE interprétation.

Attention : ⊨ et ≡ ne font pas partie du langage ; ce sont des symboles métalogiques qui
parlent AU SUJET des formules. Ne pas les confondre avec → et ↔, connecteurs internes.

LES LOIS FONDAMENTALES (servent à simplifier les formules) :

• Involution : ¬¬φ ≡ φ
• Éléments neutres : φ ∧ ⊤ ≡ φ ; φ ∨ ⊥ ≡ φ
• Éléments absorbants: φ ∧ ⊥ ≡ ⊥ ; φ ∨ ⊤ ≡ ⊤
• Idempotence : φ ∧ φ ≡ φ ; φ ∨ φ ≡ φ
• Complémentarité : φ ∧ ¬φ ≡ ⊥ (non-contradiction) ; φ ∨ ¬φ ≡ ⊤ (tiers exclu)
• Commutativité : φ ∧ ψ ≡ ψ ∧ φ ; φ ∨ ψ ≡ ψ ∨ φ
• Associativité : φ ∧ (ψ ∧ θ) ≡ (φ ∧ ψ) ∧ θ (idem pour ∨)
• Distributivité : φ ∧ (ψ ∨ θ) ≡ (φ ∧ ψ) ∨ (φ ∧ θ)
φ ∨ (ψ ∧ θ) ≡ (φ ∨ ψ) ∧ (φ ∨ θ)
• Lois de De Morgan : ¬(φ ∧ ψ) ≡ ¬φ ∨ ¬ψ ; ¬(φ ∨ ψ) ≡ ¬φ ∧ ¬ψ
• Réécriture de → : φ → ψ ≡ ¬φ ∨ ψ
• Transposition : φ → ψ ≡ ¬ψ → ¬φ (contraposée)
• 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 φ → ψ :
• Contraposée : ¬ψ → ¬φ — TOUJOURS équivalente à l'implication d'origine.
• Réciproque : ψ → φ — PAS équivalente en général.
Ex. : « si c'est un rectangle, il a 4 angles droits » a pour contraposée « s'il n'a pas
4 angles droits, ce n'est pas un rectangle » (équivalente), et pour réciproque « s'il a
4 angles droits, c'est un rectangle » (non équivalente).


──────────────────────────────
E. ÉLÉMENTS DE MODÉLISATION
──────────────────────────────

Modéliser, c'est traduire un énoncé du langage courant en une formule.
Ex. : « S'il pleut, alors il y a des nuages ». Posons 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 peut parler d'objets d'un
domaine 𝔻 grâce aux quantificateurs ∀ et ∃.

Pourquoi cette extension ? Le syllogisme « 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 (elle perd la structure interne). En prédicats on écrit
fidèlement : ∀x (H(x) → M(x)) ; H(Socrate) ⊨ M(Socrate), et là le raisonnement EST valide.

──────────────────────────────
A. SYNTAXE
──────────────────────────────

PRÉDICAT : propriété ou relation portant sur des éléments d'un domaine 𝔻 ; c'est une
fonction 𝔻ⁿ → 𝔹. L'entier n est son ARITÉ.

SIGNATURE Σ : réunit des symboles de fonctions et des symboles de prédicats, chacun
d'arité fixée.

ALPHABET des prédicats : constantes, variables (du domaine 𝔻), une signature, les
connecteurs ¬ ∧ ∨ → ↔, les quantificateurs ∀ (universel) et ∃ (existentiel), et les
séparateurs. On utilise aussi ∃! pour « il existe un UNIQUE ».

TERMES : les variables et constantes sont des termes ; si f est d'arité n et t1,…,tn des
termes, alors f(t1,…,tn) est un terme.
FORMULE ATOMIQUE : un prédicat appliqué à des termes, p(t1,…,tn). Les formules se
construisent ensuite comme en propositionnel, plus : si F est une formule et x une
variable, alors (∀x F) et (∃x F) sont des formules.

VARIABLES LIBRES ET LIÉES
Portée : dans (∀x F), la formule F est le CHAMP du quantificateur, et x est QUANTIFIÉE.
Une occurrence de variable est LIÉE si elle est dans le champ d'un quantificateur qui la
quantifie, LIBRE sinon.

Ex. : dans ∀y ( (p(x) ∨ ∃x p(x)) ∧ q(y) ) : la 1ʳᵉ occurrence de x est LIBRE, la 2ᵉ est
LIÉE (par ∃x), et y est liée (par ∀y).

Bonne pratique : renommer les variables liées par des lettres distinctes. Une variable
liée est « muette » : son nom n'a aucune importance.

──────────────────────────────
B. SÉMANTIQUE
──────────────────────────────

Quantificateur UNIVERSEL ∀ (« pour tout », « quel que soit ») : tous les éléments du
domaine vérifient la propriété. Ex. : ∀x ∈ ℝ, x² ≥ 0.
Quantificateur EXISTENTIEL ∃ (« il existe au moins un ») : au moins un élément la vérifie.
Ex. : ∃x ∈ ℝ, x² ≤ 0 (vraie, prendre x = 0).
(La virgule après le quantificateur se lit « tel que ».)

L'ORDRE DES QUANTIFICATEURS EST CRUCIAL :
• ∃x ∈ ℝ, ∀y ∈ ℝ, x < y est FAUSSE (pas de réel plus petit que tous les autres).
• ∀y ∈ ℝ, ∃x ∈ ℝ, x < y est VRAIE (pour tout y, prendre x = y − 1).
Les mêmes quantificateurs ont été intervertis, mais le sens — et la valeur de vérité — a
changé !

THÉORÈME : deux quantificateurs de MÊME nature peuvent être permutés sans changer le sens
(∀x ∀y, F ≡ ∀y ∀x, F et ∃x ∃y, F ≡ ∃y ∃x, F). En revanche ∀x ∃y et ∃y ∀x diffèrent.

NÉGATION D'UNE FORMULE QUANTIFIÉE (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 ».

Interprétation d'une signature : un triplet (𝔻, I_F, I_P) où 𝔻 est le domaine, I_F
interprète chaque fonction par 𝔻ⁿ → 𝔻, et I_P chaque prédicat par 𝔻ⁿ → 𝔹. Une assignation
v : χ → 𝔻 donne une valeur aux variables libres ; v[x := d] est identique à v sauf qu'elle
envoie x sur d.

SÉMANTIQUE DES QUANTIFICATEURS (formulation corrigée) :
• ⟦∀x, P(x)⟧ = 1 si POUR TOUT d ∈ 𝔻, ⟦P(x)⟧ avec x := d vaut 1 ;
• ⟦∃x, P(x)⟧ = 1 s'IL EXISTE d ∈ 𝔻 tel que ⟦P(x)⟧ avec x := d vaut 1.
(Le polycopié d'origine écrit par erreur « pour tout d » dans les deux cas ; pour le ∃ il
faut bien lire « il existe d ».)

Quelques équivalences sémantiques en prédicats :
• ¬∀x, F ≡ ∃x, ¬F et ¬∃x, F ≡ ∀x, ¬F
• ∀x, (F1 ∧ F2) ≡ (∀x, F1) ∧ (∀x, F2)
• ∃x, (F1 ∨ F2) ≡ (∃x, F1) ∨ (∃x, F2)
• si x n'est pas libre dans F1 : ∀x, (F1 ∧ F2) ≡ F1 ∧ ∀x, F2, etc.
Attention : ∀x ne se distribue PAS sur ∨, et ∃x ne se distribue PAS sur ∧.

──────────────────────────────
C. MODÉLISATION EN PRÉDICATS
──────────────────────────────

Avec H(x) = « x est un homme », M(x) = « x est méchant », C(y) = « y est un chien »,
a(x,y) = « x aime y » :
• 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 utilisés, 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 (ou supposer distincts
deux objets de noms différents).

B. RAISONNEMENT PAR DISJONCTION DE CAS
Pour démontrer P, on choisit une proposition Q et on prouve à la fois P ∧ Q et P ∧ ¬Q.
Justification : (P ∧ Q) ∨ (P ∧ ¬Q) ≡ P ∧ (Q ∨ ¬Q) ≡ P ∧ ⊤ ≡ P (tiers exclu).
Exemple : montrons que n(n+1) est divisible par 2 pour tout n ∈ ℕ.
• Si n est pair, n est divisible par 2, donc n(n+1) aussi.
• Si n est impair, n+1 est pair, donc n(n+1) aussi.
Dans les deux cas le produit est pair. ∎

C. RAISONNEMENT PAR CONTRAPOSÉE
Pour démontrer P → Q, il est équivalent de démontrer ¬Q → ¬P (souvent plus simple).
Exemple : pour des réels x, y : xy ≠ 0 → (x ≠ 0 ∧ y ≠ 0). La contraposée est
(x = 0 ∨ y = 0) → xy = 0, évidente (un facteur nul annule le produit). ∎
Ne pas confondre contraposée (¬Q → ¬P, équivalente) et réciproque (Q → P, non équivalente).
Ex. : (x ∈ [0;2]) → (x² ∈ [0;4]) est vraie, mais sa réciproque est fausse (prendre x = −1).

D. RAISONNEMENT PAR CONTRE-EXEMPLE
Pour réfuter ∀x ∈ E, P(x), il suffit d'exhiber un x ∈ E tel que ¬P(x)
(car ¬(∀x, P(x)) ≡ ∃x, ¬P(x)).
Exemple : l'énoncé ∀x ∈ ℝ, x² > 0 est faux : x = 0 donne 0² = 0, non strictement positif. ∎

E. RAISONNEMENT PAR L'ABSURDE
Pour démontrer P, on suppose ¬P et on aboutit à une contradiction. Donc ¬P est fausse,
donc P est vraie (tiers exclu).
Exemple : montrons ∀x ∈ ℝ, x ≠ 0 → 1/x ≠ 0. Supposons la négation : il existe x ≠ 0 avec
1/x = 0. En multipliant par x : 1 = 0, absurde. ∎

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

Principe de récurrence — pour démontrer Pₙ pour tout n ≥ n0 :
1. Initialisation : P(n0) est vraie ;
2. Hérédité : pour k ≥ n0, Pₖ ⟹ Pₖ₊₁.
Alors Pₙ est vraie pour tout n ≥ n0.

Exemple 1 : 2ⁿ > n pour tout n ∈ ℕ.
• P0 : 2⁰ = 1 > 0. ✓
• Hérédité : si 2ᵏ > k, alors 2ᵏ⁺¹ = 2·2ᵏ > 2k ≥ k + 1 (pour k ≥ 1 ; k = 0 se vérifie à part). ✓

Exemple 2 : somme des impairs Sₙ = Σ(i=0..n) (2i+1) = (n+1)².
• Découverte : S0 = 1, S1 = 4, S2 = 9 → on conjecture (n+1)².
• P0 : S0 = 1 = (0+1)². ✓
• Hérédité : Sₖ₊₁ = Sₖ + (2k+3) = (k+1)² + (2k+3) = k² + 4k + 4 = (k+2)². ✓


═══════════════════════════════════════════════════════════
5. ANNEXE — SOMMES ET PRODUITS
═══════════════════════════════════════════════════════════

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

Sommes de référence (utiles partout) :
• Σ(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)² (somme des n+1 premiers impairs)
• Σ(i=0..n) rⁱ = (r^(n+1) − 1)/(r − 1) si r ≠ 1 (somme géométrique)


═══════════════════════════════════════════════════════════
6. CORRIGÉS DES EXERCICES
═══════════════════════════════════════════════════════════
(Ces corrigés ne figurent pas dans le polycopié d'origine ; ajoutés pour rendre le cours
auto-suffisant.)

EXERCICE 1 — Est-ce une variable propositionnelle ?
1. « Il fait beau. » → OUI (énoncé déclaratif, vrai ou faux).
2. « Il fera beau demain. » → OUI (affirmation tranchable à terme).
3. « 1 + 1 = 2 » → OUI (vrai).
4. « Attention ! » → NON (interjection, ni vraie ni fausse).
5. « Bonjour » → NON (pas une assertion).
6. « n est pair. » → NON (dépend de n : c'est un PRÉDICAT, pas une proposition).
7. « Le ciel bleu » → NON (groupe nominal, pas une phrase affirmative).
8. « 8 » → NON (un nombre n'est ni vrai ni faux).

EXERCICE 2 — Simplifier
1. ((¬a ∧ b) ∨ c) → (a ∧ c).
Par la table de vérité, la formule est fausse seulement pour
(a,b,c) ∈ {(0,0,1), (0,1,0), (0,1,1)}, c.-à-d. quand ¬a ∧ (b ∨ c) est vraie. Donc :
((¬a ∧ b) ∨ c) → (a ∧ c) ≡ ¬(¬a ∧ (b ∨ c)) ≡ a ∨ (¬b ∧ ¬c).
2. (¬a → b) ∨ (a ↔ (b ∧ c)).
Comme ¬a → b ≡ a ∨ b, la formule vaut (a ∨ b) ∨ (a ↔ (b ∧ c)). Quand a ∨ b est
fausse (a = b = 0), le terme a ↔ (b ∧ c) vaut 0 ↔ 0 = 1. Donc la formule est vraie
dans tous les cas : c'est une TAUTOLOGIE ≡ ⊤.

EXERCICE 3 — Non-contradiction a ∧ ¬a
a=0 : 0 ∧ 1 = 0 ; a=1 : 1 ∧ 0 = 0. Toujours faux : a ∧ ¬a ≡ ⊥. ∎

EXERCICE 4 — Tiers exclu a ∨ ¬a
a=0 : 0 ∨ 1 = 1 ; a=1 : 1 ∨ 0 = 1. Toujours vrai : a ∨ ¬a ≡ ⊤. ∎

EXERCICE 5
1. Table de ¬a ∨ b :
a b | ¬a | ¬a∨b | a→b
0 0 | 1 | 1 | 1
0 1 | 1 | 1 | 1
1 0 | 0 | 0 | 0
1 1 | 0 | 1 | 1
Les colonnes coïncident : ¬a ∨ b ≡ a → b (réécriture de l'implication).
2. a ∧ b → ¬a ∨ b : quand la prémisse a ∧ b est vraie (a = b = 1), la conclusion
¬a ∨ b = 0 ∨ 1 = 1 ; sinon la prémisse est fausse, l'implication est vraie.
C'est donc une TAUTOLOGIE (vraie).

EXERCICE 6 — a ↔ ¬a
a=0 : 0 ↔ 1 = 0 ; a=1 : 1 ↔ 0 = 0. Toujours faux (anti-tautologie) : une proposition
ne peut avoir la même valeur que sa négation. ∎

EXERCICE 7 — Tables de vérité
1) (a ∧ ¬b) ∨ c 2) ¬(¬a ∨ b) ∧ c [noter : ¬(¬a ∨ b) ≡ a ∧ ¬b, donc = a ∧ ¬b ∧ c]

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

EXERCICE 8 — Distributivité
On vérifie φ ∧ (ψ ∨ θ) ≡ (φ ∧ ψ) ∨ (φ ∧ θ) par table de vérité sur les 8 lignes
(φ,ψ,θ) : les deux colonnes finales sont identiques (vraies exactement quand φ est vrai
et qu'au moins l'un de ψ, θ est vrai). Idem pour la version duale avec ∨ et ∧. ∎

EXERCICE 9 — Lois de De Morgan
a b | ¬(a∧b) | ¬a∨¬b | ¬(a∨b) | ¬a∧¬b
0 0 | 1 | 1 | 1 | 1
0 1 | 1 | 1 | 0 | 0
1 0 | 1 | 1 | 0 | 0
1 1 | 0 | 0 | 0 | 0
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. Tester via la table de vérité (2ⁿ lignes).
• 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 des exercices, corrections de coquilles, intuitions
ajoutées).