Logique des Prédicats
Logique des Prédicats
Logic, Programming, Mathematics · course
Fiche de révisionFiche de cours
Rédigée à partir de ce document, puis vérifiée avant publication.
La logique des prédicats est une branche de la logique qui étudie les propositions et leurs relations à travers des termes, des prédicats et des quantificateurs. Cet article couvre les concepts fondamentaux de la logique des prédicats, y compris l'interprétation des formules, les types de termes, et les propositions simples et quantifiées. Des exemples pratiques illustreront chaque notion, permettant ainsi une meilleure compréhension des mécanismes de cette logique.
En logique des prédicats, un terme peut être de trois types :
Une proposition simple s'écrit sous la forme :
P(t1, t2, t3, ...)
où P est le prédicat et ti sont les termes. Par exemple, l'égalité 2 + 2 = 4 peut être exprimée comme :
Égale(4, plus(2, 2))
Dans cet exemple, le prédicat est Égale et les termes sont la fonction Plus(2, 2) qui donne 4, une constante.
Les propositions peuvent également inclure des quantificateurs. Par exemple, une proposition avec un quantificateur universel s'écrit :
∀x P(x, ti)
où P est le prédicat et ti sont les termes. De même, une proposition avec un quantificateur existentiel s'écrit :
∃y P(y, tj)
Ces quantificateurs permettent d'exprimer des affirmations sur tous les éléments d'un domaine ou sur l'existence d'au moins un élément satisfaisant une condition donnée.
Pour interpréter une proposition ou une formule, il est nécessaire de définir un vocabulaire, un domaine d'interprétation et une fonction d'interprétation. Le vocabulaire peut inclure des constantes, des variables et des fonctions. Par exemple :
W {a, b, c, d : constantes; x, y : variables; f : une fonction}
Le domaine d'interprétation D pourrait être défini comme suit :
D = {0, 1, 2, 3}
La fonction d'interprétation I pourrait alors être :
Pour interpréter une proposition, on utilise cette fonction d'interprétation pour déterminer la valeur de vérité de propositions simples ou quantifiées.
Considérons le vocabulaire suivant :
W {a, b : constantes; f : fonction; P : prédicat}
Et le domaine d'interprétation :
D {1, 2}
La fonction d'interprétation I pourrait être :
Pour interpréter P(b, f(b)), on obtient :
I(P(b, f(b))) = v si I(b) et I(f(b)) sont dans I(P).
En substituant, cela devient I(P(2, 1)), et on peut vérifier si (2, 1) appartient à I(P).
Une proposition simple P(t1, t2) est interprétée comme :
I(P(t1, t2)) = v/f ?
Pour les propositions quantifiées, on a :
I(∀x P(x, ti)) = v si pour tout d ∈ D, I(P(d, ti)) = v
I(∃x P(x, ti)) = v si il existe d ∈ D tel que I(P(d, ti)) = v.
Soit le vocabulaire :
W {a, b : constantes; f : fonction; P : prédicat}
Et le domaine D {1, 2}.
La fonction d'interprétation I pourrait être :
Pour interpréter P(a, b), on obtient :
I(P(a, b)) = v si (I(a), I(b)) ∈ I(P).
En substituant, cela devient I(P(1, 2)), et on peut vérifier si (1, 2) appartient à I(P).
La logique des prédicats est une branche de la logique qui traite des relations entre les propositions à l'aide de termes, de prédicats et de quantificateurs. Elle permet d'exprimer des affirmations complexes sur des objets et leurs propriétés.
Pour interpréter une formule, il faut définir un vocabulaire (constantes, variables, fonctions), un domaine d'interprétation et une fonction d'interprétation. Cela permet de déterminer la valeur de vérité des propositions.
Il existe deux types de quantificateurs : le quantificateur universel (∀) qui exprime que quelque chose est vrai pour tous les éléments d'un domaine, et le quantificateur existentiel (∃) qui exprime qu'il existe au moins un élément pour lequel la proposition est vraie.
Oui, des exemples incluent des propositions simples comme P(a, b) et des propositions quantifiées comme ∀x P(x, a) ou ∃y P(y, b), où P est un prédicat et a, b, x, y sont des termes.