Logique mathématique
Logique mathématique cours Ce cours sur la logique mathématique se concentre sur le calcul des prédicats, une extension de la logique propositionnelle. Vous y découvrirez les aspects syntaxiques, sémantiques et déductifs, ainsi que des méthodes pour formaliser des raisonnements.
D'après le document Logique mathématique
Cet article a été rédigé automatiquement à partir du document source, puis vérifié avant publication.

Document source
Programming, Math, etc. · ENIT · PDF · 52 pages
Afficher l'aperçu du document
Logique mathématique cours
Ce cours sur la logique mathématique se concentre sur le calcul des prédicats, une extension de la logique propositionnelle. Vous y découvrirez les aspects syntaxiques, sémantiques et déductifs, ainsi que des méthodes pour formaliser des raisonnements. Des exemples pratiques illustrent chaque concept, facilitant la compréhension des formules bien formées, des valeurs de vérité et des conséquences logiques.
Introduction au calcul des prédicats
Le calcul des prédicats (CP1) est une généralisation de la logique propositionnelle. Contrairement à cette dernière, qui ne peut traiter que des propositions simples, le CP1 permet d'exprimer des relations entre plusieurs variables et d'utiliser des prédicats. Un prédicat est défini comme une propriété ou relation qui s'applique à un ou plusieurs éléments d'un domaine D. C'est une fonction de D dans {V, F}.
Aspects syntaxiques
Le langage du CP1 est constitué de :
- Un ensemble dénombrable de variables X
- Un ensemble de symboles de fonction F
- Un ensemble de symboles de relation R
- Des connecteurs logiques : ¬ (négation), ∧ (conjonction), ∨ (disjonction), ⇒ (implication), ⇔ (équivalence)
- Des quantificateurs ∀ (pour tout), ∃ (il existe)
Formules bien formées
Les formules bien formées (fbf) sont définies par :
- Toute formule atomique est une formule.
- Si ϕ et ψ sont des formules, alors (ϕ ⇔ ψ), (ϕ ⇒ ψ), (ϕ ∧ ψ), (ϕ ∨ ψ) et (¬ϕ) sont des formules.
- Si ϕ est une formule et x est une variable, alors (∀x)(ϕ) est une formule.
- Si ϕ est une formule et x est une variable, alors (∃x)(ϕ) est une formule.
Valeur de vérité et interprétation
La valeur de vérité d'une formule dans un domaine D est déterminée par l'interprétation des symboles. Pour toute interprétation d'une formule ϕ dans un domaine D, ϕ est évaluée à V (vrai) ou F (faux) selon les règles suivantes :
- Si on connaît la valeur de vérité de ξ et ψ, alors la valeur de vérité des formules ¬ψ, ξ ∧ ψ, ξ ∨ ψ, ξ ⇒ ψ et ξ ⇔ ψ est obtenue conformément aux règles établies.
- (∀x)(Ψ) est évalué à V si Ψ est évaluée à V pour tout élément du domaine D, sinon elle est évaluée à F.
- (∃x)(Ψ) est évalué à V si Ψ est évaluée à V pour au moins un élément du domaine D, sinon elle est évaluée à F.
Exemple d'interprétation
Considérons l'interprétation suivante : F = {s}, C = {a}, R = {plus grand}. Une interprétation possible est de prendre les réels R comme domaine, où la valeur associée à a est la constante 0 de R, la fonction associée à s est x → x + 1, et l'interprétation de "plus grand" est >.
Conséquence logique et formules équivalentes
Une formule ϕ est une conséquence logique des formules ϕ1, ϕ2, ..., ϕn si, pour chaque interprétation I, si ϕ1, ϕ2, ..., ϕn est vraie dans I, alors ϕ est aussi vraie dans I. Dans le calcul des prédicats, il existe généralement une infinité de domaines et un nombre infini d'interprétations, ce qui rend la vérification de la validité ou de l'insatisfaisabilité d'une formule complexe.
Formules équivalentes
Deux formules sont équivalentes lorsqu'elles ont la même valeur dans toutes les interprétations. On note A ≡ B si A ⇔ B est valide. Par exemple :
- ∀xA(x) ∧ ∀xB(x) ≡ ∀x(A(x) ∧ B(x))
- ∃xA(x) ∨ ∃xB(x) ≡ ∃x(A(x) ∨ B(x))
- ¬(∀xA(x)) ≡ ∃x¬A(x)
- ¬(∃xA(x)) ≡ ∀x¬A(x)
Normalisation et résolution
La normalisation des formules est essentielle pour appliquer des règles d'inférence, comme le principe de résolution. Une formule est dite en forme normale prénexe (fnp) si elle est de la forme :
(Q1x1)(Q2x2)...(Qnxn)(M), où Qi est un quantificateur et M est une formule sans quantificateurs.
Algorithme de construction
Pour mettre une formule sous forme normale prénexe, on suit plusieurs étapes :
- Supprimer les connecteurs d'équivalence et d'implication.
- Ramener les signes de négation immédiatement avant les atomes.
- Renommer les variables si nécessaire.
- Ramener les quantificateurs au début de la formule.
Exemple de mise sous forme standard de Skolem
Considérons une formule en fnp. Si Qr est un quantificateur existentiel, on choisit une constante différente de toutes les constantes de M et on remplace toutes les occurrences de xr par cette constante dans M.
Questions fréquentes
Qu'est-ce que le calcul des prédicats ?
Le calcul des prédicats est une extension de la logique propositionnelle qui permet d'utiliser des variables et des prédicats pour formaliser des énoncés plus complexes.
Comment déterminer la valeur de vérité d'une formule ?
La valeur de vérité d'une formule est déterminée par l'interprétation des symboles et les règles d'évaluation des formules en fonction des éléments du domaine.
Qu'est-ce qu'une formule bien formée ?
Une formule bien formée est une formule qui respecte les règles syntaxiques du langage du calcul des prédicats, incluant les formules atomiques et les combinaisons de formules.
Qu'est-ce qu'une conséquence logique ?
Une conséquence logique est une formule qui est vraie dans toutes les interprétations où un ensemble de formules est vrai.
Comment fonctionne la normalisation ?
La normalisation consiste à transformer une formule en une forme standard qui facilite l'application de règles d'inférence, comme le principe de résolution.
Commentaires
Aucun commentaire pour le moment. Posez la première question.