Aller au contenu

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.

Logique mathématique

Document source

Logique mathématique

Programming, Math, etc. · ENIT · PDF · 52 pages

Afficher l'aperçu du document

Consulter le document original →

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 :

  1. Supprimer les connecteurs d'équivalence et d'implication.
  2. Ramener les signes de négation immédiatement avant les atomes.
  3. Renommer les variables si nécessaire.
  4. 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.

Partager

Commentaires

Aucun commentaire pour le moment. Posez la première question.

Les commentaires sont relus avant publication. Votre e-mail n'est jamais affiché.

← Toutes les révisions