La logique étudie les principes du raisonnement valide. Elle se divise en deux systèmes essentiels :
🔸 Logique Propositionnelle
Traite des propositions (vrai/faux) et leurs relations via des connecteurs logiques
🔸 Logique des Prédicats
Ajoute les quantificateurs (∀, ∃) pour exprimer des relations entre objets
📋 Règles de Raisonnement
Structure d'un raisonnement :
- Prémisses : Hypothèses de départ
- Règles d'inférence : Raisonnement déductif
- Conclusion : Résultat du raisonnement
Exemple classique :
SI il pleut ALORS la route est mouillée
OR il pleut
DONC la route est mouillée
→
Implication
"SI...ALORS"
↔
Équivalence
"SI ET SEULEMENT SI"
📊 Tables de Vérité
| A |
B |
A ∧ B |
A ∨ B |
A → B |
¬A |
| 0 |
0 |
0 |
0 |
1 |
1 |
| 0 |
1 |
0 |
1 |
1 |
1 |
| 1 |
0 |
0 |
1 |
0 |
0 |
| 1 |
1 |
1 |
1 |
1 |
0 |
🎯 Priorité des connecteurs (du plus fort au plus faible) :
¬ > ∧ > ∨ > → > ↔
✅ Formule Valide (Tautologie)
Vraie pour toute interprétation
⊨ A
Exemples :
• p ∨ ¬p
• (p ∧ q) → p
• (p → q) ↔ (¬q → ¬p)
⚠️ Formule Satisfiable
Vraie pour au moins une interprétation
Exemples :
• p
• p ∨ q
• p → q
❌ Formule Insatisfiable
Fausse pour toute interprétation
Exemples :
• p ∧ ¬p
• FALSE
• (p ∨ q) ∧ ¬p ∧ ¬q
⚡ Conséquence Logique
A₁, A₂, ..., Aₙ ⊨ B
B est conséquence logique de A₁, ..., Aₙ si tout modèle de A₁, ..., Aₙ est un modèle de B
Exemples de conséquences logiques :
- {p, p → q} ⊨ q (Modus Ponens)
- {p, q} ⊨ p ∧ q
- {¬q, p → q} ⊨ ¬p (Modus Tollens)
📜 Schémas d'Axiomes
1. A → (B → A)
2. (A → B) → ((A → (B → C)) → (A → C))
3. A → (B → A ∧ B)
4. (A ∧ B) → A
5. (A ∧ B) → B
6. A → A ∨ B
7. B → A ∨ B
8. (A → C) → ((B → C) → ((A ∨ B) → C))
9. (A → B) → ((A → ¬B) → ¬A)
10. ¬¬A → A
11. ¬FALSE
🔄 Règle d'Inférence : Modus Ponens
A A → B
───────────
B
💡 Preuve : Une preuve de A est une liste finie de formules où chaque formule est soit un axiome, soit obtenue par Modus Ponens.
| Élimination des connecteurs |
Propriétés |
| Implication |
(A → B) ≡ (¬A ∨ B) |
Idempotence |
A ∧ A ≡ A |
| Équivalence |
(A ↔ B) ≡ ((A → B) ∧ (B → A)) |
Associativité |
A ∧ (B ∧ C) ≡ (A ∧ B) ∧ C |
| Disjonction |
A ∨ B ≡ ¬(¬A ∧ ¬B) |
Commutativité |
A ∧ B ≡ B ∧ A |
| Double négation |
¬¬A ≡ A |
Distributivité |
A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C) |
🔧 Lois de De Morgan
¬(A ∨ B) ≡ ¬A ∧ ¬B
¬(A ∧ B) ≡ ¬A ∨ ¬B
Définitions :
- Littéral : Variable propositionnelle ou sa négation (p ou ¬p)
- Clause : Disjonction de littéraux (p ∨ ¬q ∨ r)
- FNC : Conjonction de clauses ((p ∨ q) ∧ (¬p ∨ r))
🔄 Algorithme de Mise en FNC
Étapes :
- Éliminer → et ↔ : (A → B) devient (¬A ∨ B)
- Descendre les négations : ¬(A ∨ B) devient (¬A ∧ ¬B)
- Éliminer double négation : ¬¬A devient A
- Distribuer ∨ sur ∧ : A ∨ (B ∧ C) devient (A ∨ B) ∧ (A ∨ C)
Exemple :
(p ∧ q) ∨ r
↓
(p ∨ r) ∧ (q ∨ r)
🎯 Quantificateurs
∀ Universel
"Pour tout x, P(x)"
∀x ∈ U, P(x)
Exemple :
Tout être humain est mortel
∀x (humain(x) → mortel(x))
∃ Existentiel
"Il existe x tel que P(x)"
∃x ∈ U, P(x)
Exemple :
Il existe un nombre premier pair
∃x (premier(x) ∧ pair(x))
🔄 Négation des Quantificateurs
¬(∀x, P(x)) ≡ ∃x, ¬P(x)
¬(∃x, P(x)) ≡ ∀x, ¬P(x)
⚠️ Attention : L'ordre des quantificateurs est important !
∀x ∃y, P(x,y) ≠ ∃y ∀x, P(x,y)
📌 Exemples de Prédicats
- Propriété : humain(Socrate)
- Relation : père(Jean, Pierre)
- Comparaison : plus-petit-que(3, 7)
- Énoncé complexe : ∀n ∈ ℕ, ∃m ∈ ℕ, m > n
🎯 Essentiel pour l'examen :
- Connecteurs : Maîtriser les tables de vérité de ∧, ∨, ¬, →, ↔
- Validité : Distinguer valide, satisfiable et insatisfiable
- Conséquence : A₁, ..., Aₙ ⊨ B signifie que B est vrai quand A₁, ..., Aₙ sont vrais
- Axiomes : Connaître les 11 schémas et le Modus Ponens
- Équivalences : Lois de De Morgan et élimination des connecteurs
- FNC : Algorithme de mise en forme normale conjonctive
- Quantificateurs : ∀ (universel) et ∃ (existentiel), négation
🧮 Formules Essentielles :
(A → B) ≡ (¬A ∨ B)
¬(A ∨ B) ≡ ¬A ∧ ¬B
¬(∀x, P(x)) ≡ ∃x, ¬P(x)
A₁, ..., Aₙ ⊨ B ⟺ ⊨ (A₁ ∧ ... ∧ Aₙ) → B
⚠️ Pièges Classiques :
- Ne pas confondre ⊨ (validité) et ⊢ (prouvabilité)
- L'implication A → B est vraie quand A est faux
- Bien respecter la priorité des connecteurs
- L'ordre des quantificateurs change le sens