Introduction à la logique des propositions

Logique des propositions

• Une proposition est un énoncé déclaratif qui peut être vrai ou faux.
  • Exemple : « La terre est une planète » ou « Le soleil est une étoile ».
• Les propositions élémentaires ou atomiques ne peuvent pas être décomposées en propositions plus simples.
• Une proposition peut être affirmative ou négative.
  • Exemple : « La terre est ronde » (affirmative) ou « La terre n’est pas ronde » (négative).
• Une proposition peut être la composition de plusieurs propositions élémentaires et sa valeur de vérité est déterminée par la valeur de vérité de chacune d'entre elles.
  • Exemple : « Le soleil se lève à l'est et se couche à l'ouest" est vraie car les deux propositions le sont.
• La proposition "La terre n'est pas ronde" n'est pas atomique, c'est la négation de "La terre est ronde".
• Paradoxes : Énoncés déclaratifs dont on ne peut décider s'ils sont vrais ou faux.
  • Exemple : « Cette phrase est fausse ».

Langage propositionnel

• Un langage, formel ou naturel, est caractérisé par sa syntaxe et sa sémantique.

Syntaxe du langage propositionnel

• Les formules sont écrites avec des symboles d'un alphabet selon des règles d'écriture définies.

Alphabet

• L'alphabet du langage propositionnel comprend :
  • Un ensemble de variables propositionnelles désignées par des lettres majuscules (P, Q, P1, P2, ...).
  • Connecteurs logiques : ¬, ∧, ∨, →, ↔.
  • Parenthèses : "(", ")".

Règles d'écriture

• Conventions : les formules sont désignées par des lettres grecques minuscules.
  • r1. Toute variable propositionnelle est une formule (atomique).
  • r2. Si a est une formule, (a) est une formule.
  • r3. Si a est une formule, ¬a est une formule.
  • r4. Si a et ẞ sont des formules, les expressions a∧β, a∨β, a→β, a↔β sont des formules.
  • r5. Aucune autre expression n'est une formule du langage.

Définitions

• Formule atomique : variable propositionnelle.
• Littéral : formule atomique ou sa négation (exemples : P, ¬P).
• Littéraux complémentaires : lorsque l'un est la négation de l'autre.

Précédence des connecteurs

• Simplification de l'écriture des formules par l'introduction de règles de précédence entre connecteurs :
  • ¬, ∧, ∨, →, ↔ (de gauche à droite lorsqu'ils se suivent dans une formule).
  • Exemple : P → Q → R se lit (P → Q) → R.

Sous-formules

• La notion de sous-formule peut être déduite des règles d'écriture (1.2.1.2).
• L'ensemble S(a) des sous-formules d'une formule a peut être défini comme suit :
  • r1. Si a est une formule, alors a ∈ S(a).
  • r2. Si a = ¬ẞ est une formule, alors ẞ ∈ S(a).
  • r3. Si a = ẞ1 0 ẞ2 avec 0 ∈ {∧, ∨, →, ↔}, alors ẞ1, ẞ2 ∈ S(a).
• Exemple : a: «P∨¬Q→ P
  • S(a) : {«P∨«Q → P, «P∨ ¬Q, P, «P, «Q, Q}

Sémantique du langage propositionnel

• Elle attribue une valeur de vérité aux formules de L, en associant une fonction de vérité ou de valuation v : {V,F}n → {V,F} à chaque formule a de L.
  • où n désigne le nombre de variables propositionnelles dans la formule.
  • v(P) = V ou F pour toute variable propositionnelle P.
• ν(«β) = V si ν(β) = F, sinon F
• ν(α∧β) = V si ν(a) = V et ν(β) = V, sinon F

Tables de vérité

• Pour une formule a avec n variables propositionnelles distinctes, il existe 2n fonctions de valuation.
  • Elles sont représentées dans un tableau de vérité à 2n lignes, où chaque ligne i indique la valeur de vérité de a pour la valuation vi.

Satisfaisabilité d'une formule, d'un ensemble de formules

• Une valuation v satisfait une formule a (v |= a) si la valeur de vérité de a est V (v(a) = V).
• v|≠a signifie que « v ne satisfait pas a » ou « v falsifie a ».
• Les valuations qui satisfont une formule correspondent aux lignes du tableau de vérité où la valeur de vérité de a est V.
• Une formule a est satisfiable s'il existe au moins une valuation v telle que v |= a.
  • Sinon, a est dite non satisfiable.

Proposition

• Si β1 et β2 sont des formules et v une valuation alors :
  • Pour toute variable propositionnelle P, si v(P) = V alors v |= P
  • v |= ¬ẞ ssi v|≠β
  • v |= β1∧β2 ssi v |= β1 et v |= β2
  • v |= β1∨β2 ssi v |= β1 ou v |= β2
  • v |= β1→β2 ssi (v|≠β1 ou v |= β2)
  • v |= β1↔β2 ssi (v |= β1→β2 et v |= β2→β1)

Satisfiabilité d'un ensemble de formules

• Un ensemble de formules Γ = {α1, ...,αn} est satisfiable ssi il existe au moins une valuation v qui satisfait toutes les formules de Γ (v |= α1 et v |= α2 et ... et v |= αn).
  • v correspond alors à une ligne du TV où les valeurs de vérité de α1, ..., αn sont toutes V.
• Exemple : L'ensemble { P ∧ Q, P ∨ Q, P → Q, P ↔ Q } est satisfiable.
  • Considérer la valuation v₁ correspondant à la première ligne du tableau 1.4.
• À l'opposé, l'ensemble { P ∧ Q, P ∨ Q, P → Q, P ↔ Q, ¬P } est non satisfiable (tableau 1.4).

Tautologie

• Une formule a est une tautologie ( |= a ) si et seulement si v |= a quelle que soit v. Exemple :|= P∧Q → Q

Formules logiquement équivalentes

• Deux formules a et ẞ sont logiquement équivalentes si, et seulement si v(a) = v(β) quelle que soit v, auquel cas a ↔ẞ.

Propriétés des connecteurs logiques

• Commutativité du ∨ et du ∧ :
  • α ∨ β = β ∨ α
  • α ∧ β = β ∧ α
• Associativité du ∨ et du ∧ :
  • (α ∨ β) ∨ γ = α ∨ (β ∨ γ)
  • (α ∧ β) ∧ γ = α ∧ (β ∧ γ)
• Distributivité du ∨, du ∧, et de :
  • α ∨ (β ∧ γ) = (α ∨ β) ∧ (α ∨ γ)
  • α ∧ (β ∨ γ) = (α ∧ β) ∨ (α ∧ γ)
• Idempotence :
  • α ∨ α = α
  • α ∧ α = α
• Lois de De Morgan :
  • ¬(α ∨ β) = ¬α ∧ ¬β
  • ¬(α ∧ β) = ¬α ∨ ¬β
• α = α.

Conséquence logique

• Une formule β est conséquence logique d'une formule α (notée α |= β) si, et seulement si, pour toute valuation v, si v |= α alors v |= β.
  • Sur le TV de α et β, la valeur de vérité de β est V sur toutes les lignes où les valeurs de vérité de α sont V.
  • De manière générale, une formule β est conséquence logique d'un ensemble de formules Γ : {α1, α2, ..., αn} (notée α1, ..., αn |= β ou Γ |= β) si et seulement si : Quelle que soit v, si v |= α1 et v |= α2 et ... et v |= αn alors v |= β.
• Exemple :
  • P → Q, «Q |= «P (Tableau 1.7a).
  • À l'opposé, ¬Q n'est pas conséquence logique de {P → Q, «P}.
    • La valuation qui correspond à la ligne 3 du tableau 1.7 satisfait P → Q, ¬P mais ne satisfait pas ¬Q.
• Theorème 1.4 :
  • Γ |= ẞ ssi Γ ∪ {¬ẞ} non satisfiable

Théorème 1.1

• α1, ..., αn |= β si, et seulement si α1, ..., αn-1 |= αn → β.

Théorème 1.2

• Si Γ |= α et Γ |= α → β alors Γ |= β.

Théorème 1.3

• Si Γ |= β et Γ |= ¬β alors Γ est non satisfiable.

Théorème 1.5 (Théorème de substitution)

• Soit β une formule où la variable propositionnelle P apparaît dans une ou plusieurs occurrences, et soit β' la formule obtenue en substituant une formule a à P dans toutes ses occurrences. Alors, Si |= β alors |= β'.
  • Exemple : β : P → ((Q → R) → P ).
    • (On vérifie que β est une tautologie.)
    • β': (A ∧ B) → ((Q → (B ∨ C)) → (A ∧ B) ) obtenue en substituant (A ∧ B) à P et (B ∨ C) à R. On vérifie aussi que β' est une tautologie.

Théorème 1.6 (Théorème de remplacement)

• Soit a une formule où la formule ẞ apparaît dans une ou plusieurs occurrences (i-e a est de la forme : ......β......β......ẞ......). Si a' est obtenue en remplaçant ẞ par une formule ẞ' dans une ou plusieurs de ces occurrences, alors : Si |= β' ↔ β alors |= α' ↔ α.
  • Exemple : α : P1 ∨ (P2 → P3) ↔ P4 ∨ (P2 → P3)
    • En remplaçant la première occurrence de (P2 → P3) par (¬P2 ∨ P3) on obtient la formule α': P1 ∨ (¬P2 ∨ P3) ↔ P4 ∨ (P2 → P3) logiquement équivalente à a.

Système complet de connecteurs

• Un ensemble S de connecteurs est complet, si, pour toute formule a du langage L, il existe une formule a' où seuls les connecteurs de S apparaissent et telle que a' ↔ a.
  • Exemple : l'ensemble {¬, ∧} forme un système complet.

Connecteurs de Sheffer

• Il existe deux ensembles complets de connecteurs formés chacun d'un seul connecteur.

Forme normale disjonctive et forme normale conjonctive

• Une formule a est sous forme normale disjonctive (FND) si elle est de la forme M1 ∨ M2 ∨ ... ∨ Mm où chaque Mi est de la forme L1 ∧ L2 ∧ ... ∧ Ln, où Li représente soit le littéral P, soit le littéral ¬P.
  • Exemple : P ∨ (Q ∧ R) ∨ («Q ∧ «P).
• Une formule a est sous forme normale conjonctive (FNC) si elle est de la forme C1 ∧ C2 ∧ ... ∧ Cn où chaque Ci est de la forme L1 ∨ L2 ∨ ... ∨ Ln.
  • Exemple : (P ∨ Q ∨ R) ∧ (¬Q ∨¬P) ∧ (Q ∨ ¬P)
• Théorème : À toute formule a correspond une formule a' sous FND (ou FNC) telle que : |= a'↔a.