COURS DE MATHÉMATIQUES — LOGIQUE PROPOSITIONNELLE Niveau Universitaire
MATHÉMATIQUES
Cours Universitaire Complet
LOGIQUE PROPOSITIONNELLE
Calcul des propositions, sémantique, déduction formelle et applications
PLAN DU COURS
I. Introduction et cadre général de la logique
II. Syntaxe — Le langage propositionnel
III. Sémantique — Interprétations et tables de vérité
IV. Connecteurs logiques en détail
V. Propriétés sémantiques des formules
VI. Équivalences logiques fondamentales
VII. Formes normales (FND, FNC)
VIII. Déduction naturelle et systèmes de preuve
IX. Complétude et correction — Théorèmes fondamentaux
X. Résolution — Méthode algorithmique
XI. Applications et extensions
XII. Limites et ouvertures vers d'autres logiques
Cours complet — Logique Propositionnelle Page
, COURS DE MATHÉMATIQUES — LOGIQUE PROPOSITIONNELLE Niveau Universitaire
I. Introduction et cadre général de la logique
1.1 Qu'est-ce que la logique ?
La logique est la science du raisonnement correct. Elle étudie les formes du raisonnement
indépendamment de leur contenu spécifique, c'est-à-dire qu'elle s'intéresse à la structure des
arguments plutôt qu'aux objets dont ils parlent. Un argument valide est un argument dont la
conclusion suit nécessairement des prémisses, quels que soient les domaines concernés.
La logique mathématique, branche formalisée de la logique, se distingue de la logique ordinaire par
l'utilisation d'un langage artificiel précis, dépourvu d'ambiguïté, avec une syntaxe rigoureusement
définie et une sémantique formelle. Elle constitue l'un des fondements des mathématiques
modernes.
1.2 Place de la logique propositionnelle
La logique mathématique se divise en plusieurs grandes théories, dont les principales sont :
• La logique propositionnelle (ou calcul des propositions) : la plus simple, elle traite de
propositions entières reliées par des connecteurs.
• La logique du premier ordre (ou calcul des prédicats) : elle raffine la logique
propositionnelle en introduisant des variables, des quantificateurs et des prédicats.
• Les logiques d'ordre supérieur, la logique modale, la logique temporelle, etc.
La logique propositionnelle est le point d'entrée naturel et constitue la brique de base sur laquelle
sont construites les logiques plus expressives. Elle est à la fois simple à formaliser et suffisamment
riche pour illustrer les concepts fondamentaux (syntaxe, sémantique, déduction, complétude).
1.3 La notion de proposition
Définition — Proposition
En logique propositionnelle, une proposition (ou énoncé) est un énoncé déclaratif qui a une
valeur de vérité déterminée : il est soit vrai (noté V, 1, ou ⊤), soit faux (noté F, 0, ou ⊥). Cette
bivalence est un axiome fondateur du cadre classique.
Cette définition exclut immédiatement les phrases interrogatives (« Quelle heure est-il ? »), les
injonctions (« Ferme la porte ! »), les propositions vagues ou paradoxales. Les propositions sont soit
atomiques (irréductibles), soit composées à partir de propositions plus simples au moyen de
connecteurs logiques.
Cours complet — Logique Propositionnelle Page
, COURS DE MATHÉMATIQUES — LOGIQUE PROPOSITIONNELLE Niveau Universitaire
Exemple — Propositions valides et invalides
Propositions valides (ont une valeur de vérité) :
• « 2 + 2 = 4 » → vraie
• « Paris est la capitale de l'Allemagne » → fausse
• « Il pleut à Paris en ce moment » → vraie ou fausse selon les faits
Non-propositions (pas de valeur de vérité définie) :
• « Ferme la fenêtre ! » → injonction
• « Est-ce que tu viens ? » → question
• « Cette phrase est fausse » → paradoxe autoreférentiel (paradoxe du menteur)
Le paradoxe du menteur (« Cette phrase est fausse ») montre que certains énoncés résistent à la
bivalence. La logique propositionnelle classique les évacue en ne les reconnaissant pas comme des
propositions légitimes de son langage.
Cours complet — Logique Propositionnelle Page
, COURS DE MATHÉMATIQUES — LOGIQUE PROPOSITIONNELLE Niveau Universitaire
II. Syntaxe — Le langage propositionnel
2.1 L'alphabet du langage
Formaliser la logique propositionnelle commence par définir précisément un langage artificiel. Un
langage formel est entièrement déterminé par son alphabet et ses règles de formation.
L'alphabet de la logique propositionnelle se compose de trois catégories de symboles :
Catégorie Symboles Rôle
Variables p, q, r, s, ... (ou P, Q, Représentent les
propositionnelles R, ...) propositions
atomiques
Connecteurs ¬, ∧, ∨, →, ↔ Opérateurs pour
logiques composer les formules
Symboles de ( et ) Parenthèses pour
ponctuation lever les ambiguïtés
Constantes ⊤ (tautologie), ⊥ Valeurs fixes vrai et
logiques (contradiction) faux
(optionnel)
Les variables propositionnelles constituent un ensemble dénombrable, généralement infini. En
pratique, on utilise p, q, r, s, t, ... et éventuellement des indices : p₁, p₂, ...
2.2 Formules bien formées (FBF)
Définition — Formule Bien Formée (FBF)
Une formule bien formée (aussi appelée formule propositionnelle ou simplement formule) est
définie inductivement (par récurrence) comme suit : 1. Base : Toute variable propositionnelle p,
q, r, ... est une FBF. Les constantes ⊤ et ⊥ sont des FBF. 2. Induction : Si φ et ψ sont des FBF,
alors les expressions suivantes sont aussi des FBF : (¬φ) — négation de φ (φ ∧ ψ) —
conjonction (φ ∨ ψ) — disjonction (φ → ψ) — implication (φ ↔ ψ) — équivalence 3.
Clôture : Rien d'autre n'est une FBF.
Cette définition inductive est fondamentale : elle garantit que toute formule peut être construite étape
par étape à partir de formules plus simples, et qu'elle a une structure d'arbre unique (sauf
conventions sur les parenthèses). C'est cette propriété qui permettra de définir la sémantique et les
règles de déduction par récurrence structurelle.
Exemple — Construction inductive d'une formule
Cours complet — Logique Propositionnelle Page
MATHÉMATIQUES
Cours Universitaire Complet
LOGIQUE PROPOSITIONNELLE
Calcul des propositions, sémantique, déduction formelle et applications
PLAN DU COURS
I. Introduction et cadre général de la logique
II. Syntaxe — Le langage propositionnel
III. Sémantique — Interprétations et tables de vérité
IV. Connecteurs logiques en détail
V. Propriétés sémantiques des formules
VI. Équivalences logiques fondamentales
VII. Formes normales (FND, FNC)
VIII. Déduction naturelle et systèmes de preuve
IX. Complétude et correction — Théorèmes fondamentaux
X. Résolution — Méthode algorithmique
XI. Applications et extensions
XII. Limites et ouvertures vers d'autres logiques
Cours complet — Logique Propositionnelle Page
, COURS DE MATHÉMATIQUES — LOGIQUE PROPOSITIONNELLE Niveau Universitaire
I. Introduction et cadre général de la logique
1.1 Qu'est-ce que la logique ?
La logique est la science du raisonnement correct. Elle étudie les formes du raisonnement
indépendamment de leur contenu spécifique, c'est-à-dire qu'elle s'intéresse à la structure des
arguments plutôt qu'aux objets dont ils parlent. Un argument valide est un argument dont la
conclusion suit nécessairement des prémisses, quels que soient les domaines concernés.
La logique mathématique, branche formalisée de la logique, se distingue de la logique ordinaire par
l'utilisation d'un langage artificiel précis, dépourvu d'ambiguïté, avec une syntaxe rigoureusement
définie et une sémantique formelle. Elle constitue l'un des fondements des mathématiques
modernes.
1.2 Place de la logique propositionnelle
La logique mathématique se divise en plusieurs grandes théories, dont les principales sont :
• La logique propositionnelle (ou calcul des propositions) : la plus simple, elle traite de
propositions entières reliées par des connecteurs.
• La logique du premier ordre (ou calcul des prédicats) : elle raffine la logique
propositionnelle en introduisant des variables, des quantificateurs et des prédicats.
• Les logiques d'ordre supérieur, la logique modale, la logique temporelle, etc.
La logique propositionnelle est le point d'entrée naturel et constitue la brique de base sur laquelle
sont construites les logiques plus expressives. Elle est à la fois simple à formaliser et suffisamment
riche pour illustrer les concepts fondamentaux (syntaxe, sémantique, déduction, complétude).
1.3 La notion de proposition
Définition — Proposition
En logique propositionnelle, une proposition (ou énoncé) est un énoncé déclaratif qui a une
valeur de vérité déterminée : il est soit vrai (noté V, 1, ou ⊤), soit faux (noté F, 0, ou ⊥). Cette
bivalence est un axiome fondateur du cadre classique.
Cette définition exclut immédiatement les phrases interrogatives (« Quelle heure est-il ? »), les
injonctions (« Ferme la porte ! »), les propositions vagues ou paradoxales. Les propositions sont soit
atomiques (irréductibles), soit composées à partir de propositions plus simples au moyen de
connecteurs logiques.
Cours complet — Logique Propositionnelle Page
, COURS DE MATHÉMATIQUES — LOGIQUE PROPOSITIONNELLE Niveau Universitaire
Exemple — Propositions valides et invalides
Propositions valides (ont une valeur de vérité) :
• « 2 + 2 = 4 » → vraie
• « Paris est la capitale de l'Allemagne » → fausse
• « Il pleut à Paris en ce moment » → vraie ou fausse selon les faits
Non-propositions (pas de valeur de vérité définie) :
• « Ferme la fenêtre ! » → injonction
• « Est-ce que tu viens ? » → question
• « Cette phrase est fausse » → paradoxe autoreférentiel (paradoxe du menteur)
Le paradoxe du menteur (« Cette phrase est fausse ») montre que certains énoncés résistent à la
bivalence. La logique propositionnelle classique les évacue en ne les reconnaissant pas comme des
propositions légitimes de son langage.
Cours complet — Logique Propositionnelle Page
, COURS DE MATHÉMATIQUES — LOGIQUE PROPOSITIONNELLE Niveau Universitaire
II. Syntaxe — Le langage propositionnel
2.1 L'alphabet du langage
Formaliser la logique propositionnelle commence par définir précisément un langage artificiel. Un
langage formel est entièrement déterminé par son alphabet et ses règles de formation.
L'alphabet de la logique propositionnelle se compose de trois catégories de symboles :
Catégorie Symboles Rôle
Variables p, q, r, s, ... (ou P, Q, Représentent les
propositionnelles R, ...) propositions
atomiques
Connecteurs ¬, ∧, ∨, →, ↔ Opérateurs pour
logiques composer les formules
Symboles de ( et ) Parenthèses pour
ponctuation lever les ambiguïtés
Constantes ⊤ (tautologie), ⊥ Valeurs fixes vrai et
logiques (contradiction) faux
(optionnel)
Les variables propositionnelles constituent un ensemble dénombrable, généralement infini. En
pratique, on utilise p, q, r, s, t, ... et éventuellement des indices : p₁, p₂, ...
2.2 Formules bien formées (FBF)
Définition — Formule Bien Formée (FBF)
Une formule bien formée (aussi appelée formule propositionnelle ou simplement formule) est
définie inductivement (par récurrence) comme suit : 1. Base : Toute variable propositionnelle p,
q, r, ... est une FBF. Les constantes ⊤ et ⊥ sont des FBF. 2. Induction : Si φ et ψ sont des FBF,
alors les expressions suivantes sont aussi des FBF : (¬φ) — négation de φ (φ ∧ ψ) —
conjonction (φ ∨ ψ) — disjonction (φ → ψ) — implication (φ ↔ ψ) — équivalence 3.
Clôture : Rien d'autre n'est une FBF.
Cette définition inductive est fondamentale : elle garantit que toute formule peut être construite étape
par étape à partir de formules plus simples, et qu'elle a une structure d'arbre unique (sauf
conventions sur les parenthèses). C'est cette propriété qui permettra de définir la sémantique et les
règles de déduction par récurrence structurelle.
Exemple — Construction inductive d'une formule
Cours complet — Logique Propositionnelle Page
