Introduction
Florent Capelli
07 Janvier 2025
Deux grandes parties :
Évaluation :
Pas de cours le 22/01 (rattrapé en deux fois, les 12/02 et 19/03).
Formaliser les raisonnements valides.
Domaine faisant historiquement partie de la philosophie mais devenu par la suite
Sophisme :
Comment formaliser ce raisonnement (et mettre le sophisme à jour) ? Cette symmétrie ?
Exemple par Pierre Marquis (note du cours de l’an dernier) :
Le revenu moyen des agriculteurs a progressé de 25% depuis l’an dernier. Donc la situation des agriculteurs s’est améliorée en un an.
Il existe de nombreux systèmes logiques différents permettant de modéliser différentes choses :
Logique propositionnelle étudie les liens logiques entre des propositions :
Le contenu des propositions atomique n’importe pas au niveau logique.
“Quand il pleut, je prends mon parapluie” peut se modéliser par la formule p ⇒ q.
“Quand il pleut, il y a du soleil” se modélise par la même formule p ⇒ q.
La logique propositionnelle fait abstraction du sens des propositions atomiques.
On peut choisir des propositions “complexes” comme étant atomiques dans la modélisation. Cela dépend du niveau de précision dont on a besoin.
“Il pleut et le magasin est fermé”.
C’est soit une seule proposition atomique, soit la conjonction de deux propositions atomiques (“il pleut”, “le magasin est fermé”).
Soit X un ensemble infini de propositions atomiques, on construit l’ensemble des formules propositionnelles inductivement :
Où x, y, z sont des propositions atomiques :
Les formules sont la syntaxe de la logique. On définit maintenant sa sémantique :
Pour l’interprétation ω = {x ↦ 1, y ↦ 1, z ↦ 0} :
La valeur ⟦F⟧(ω) ne dépend que de la valeur d’ω des propositions atomiques qui apparaissent dans F (qu’on notera var(F)).
On peut donc écrire la table de vérité d’une formule F: la liste de toutes les interprétations ω de var(F) et la valeur de ⟦F⟧(ω).
Si var(F) contient 5 propositions atomiques, combien d’interprétations différentes existe-t-il ? Et si |var(F)| = n ?
Table de vérité de (x∧y) ∨ (x∧¬z) :
| x | y | z | ⟦F⟧(ω) |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Point vocabulaire :
A-t-on x ∧ y ⊨ x ∨ y ? Et x ∨ y ⊨ x ∧ y ?
On peut utiliser d’autres connecteurs logiques dans les formules :
Sucre syntaxique :
Inclut dans la sémantique:
Intuitivement F ⇒ G : “si F est vrai, alors G est vrai aussi”.
Rien n’est exigé dans le cas où F est faux.
Une formule booléenne F sur les propositions atomiques X définit une unique fonction booléenne {0, 1}X → {0, 1}.
Complétude de la logique propositionnelle :
Toute fonction booléenne peut être décrite par une formule.
Trouver F qui a cette table de vérité :
| x | y | z | ⟦F⟧(ω) |
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| * | * | * | 0 |
(¬x∧¬y∧¬z) ∨ (¬x∧y∧¬z) ∨ (x∧¬y∧¬z)
On peut toujours faire ça : lister les modèles et écrire une formule de la forme ⋁ω⋀x(ω(x)⋅x)
C’est une Forme Normale Disjonctive.
Syntaxe de la logique propositionnelle avec les connecteurs {∧,∨,¬}.
Choix arbitraire, d’autres choix seraient possibles {⇒,¬} par exemple
Quid de {∧, ∨ } ?
Défini une logique mais cette logique ne peut pas capturer toutes les fonctions booléennes (pourquoi ?).
Un ensemble de connecteur (avec une sémantique) est fonctionnellement complet si la logique propositionnelle qu’il définit permet d’exprimer toutes les fonctions booléennes.
Choix d’un système de connecteurs ne change pas l’expressivité du langage mais possiblement sa concision et la structure du langage obtenu.