La logique des prédicats traite des prédicats, qui sont des propositions constituées de variables.

Logique des prédicats – Définition

Un prédicat est une expression d'une ou plusieurs variables déterminées sur un domaine spécifique. Un prédicat avec des variables peut devenir une proposition soit en autorisant une valeur à la variable, soit en quantifiant la variable.

• Considérons que E(x, y) désigne 'x = y'
• Considérons que X(a, b, c) désigne 'a + b + c = 0'
• Considérons que M(x, y) désigne « x est marié à y ».

Quantificateur:

La variable des prédicats est quantifiée par des quantificateurs. Il existe deux types de quantificateurs dans la logique des prédicats : le quantificateur existentiel et le quantificateur universel.

Quantificateur Existentiel :

Si p(x) est une proposition sur l'univers U. Alors elle est notée ∃x p(x) et se lit comme « Il existe au moins une valeur dans l'univers de la variable x telle que p(x) est vraie. Le quantificateur ∃ est appelé quantificateur existentiel.

Il existe plusieurs manières d'écrire une proposition, avec un quantificateur existentiel, c'est-à-dire :

(∃x∈A)p(x) ou ∃x∈A tel que p (x) ou (∃x)p(x) ou p(x) est vrai pour certains x ∈A.

Quantificateur universel :

Si p(x) est une proposition sur l'univers U. Alors elle est notée ∀x,p(x) et se lit comme « Pour tout x∈U, p(x) est vrai. » Le quantificateur ∀ est appelé Quantificateur Universel.

Il existe plusieurs manières d’écrire une proposition, avec un quantificateur universel.

∀x∈A,p(x) ou p(x), ∀x ∈A Ou ∀x,p(x) ou p(x) est vrai pour tout x ∈A.

Négation des propositions quantifiées :

Lorsque nous nions une proposition quantifiée, c’est-à-dire lorsqu’une proposition universellement quantifiée est niée, nous obtenons une proposition existentiellement quantifiée, et lorsqu’une proposition existentiellement quantifiée est niée, nous obtenons une proposition universellement quantifiée.

Les deux règles de négation d'une proposition quantifiée sont les suivantes. Celles-ci sont également appelées loi de DeMorgan.

Exemple : annulez chacune des propositions suivantes :

1.∀x p(x)∧ ∃ y q(y)

Soleil: ~.∀x p(x)∧ ∃ y q(y))
≅~∀ x p(x)∨∼∃yq (y) (∴∼(p∧q)=∼p∨∼q)
≅ ∃ x ~p(x)∨∀y∼q(y)

2. (∃x∈U) (x+6=25)

Soleil: ~( ∃ x∈U) (x+6=25)
≅∀ x∈U~ (x+6)=25
≅(∀ x∈U) (x+6)≠25

3. ~( ∃ x p(x)∨∀ y q(y)

Soleil: ~( ∃ x p(x)∨∀ y q(y))
≅~∃ x p(x)∧~∀ y q(y) (∴~(p∨q)= ∼p∧∼q)
≅ ∀ x ∼ p(x)∧∃y~q(y))

Propositions avec plusieurs quantificateurs :

La proposition ayant plus d’une variable peut être quantifiée avec plusieurs quantificateurs. Les multiples quantificateurs universels peuvent être disposés dans n’importe quel ordre sans altérer le sens de la proposition résultante. De plus, les multiples quantificateurs existentiels peuvent être disposés dans n’importe quel ordre sans altérer le sens de la proposition.

La proposition qui contient à la fois des quantificateurs universels et existentiels, l'ordre de ces quantificateurs ne peut pas être échangé sans altérer le sens de la proposition, par exemple, la proposition ∃x ∀ y p(x,y) signifie « Il existe un x tel que p (x, y) est vrai pour chaque y.'

Exemple: Écrivez la négation de chacun des éléments suivants. Déterminez si la déclaration résultante est vraie ou fausse. Supposons que U = R.

1.∀ x ∃ m(x ²

Soleil: Négation de ∀ x ∃ m(x ² 2≧m). La signification de ∃ x ∀ m (x ² ≧m) est qu'il existe pour certains x tel que x ² ≧m, pour chaque m. L'affirmation est vraie car il existe un plus grand x tel que x ² ≧m, pour chaque m.

2. ∃ m∀ x(x ²

Soleil: Négation de ∃ m ∀ x (x ² 2≧m). La signification de ∀ m∃x (x ² ≧m) est que pour tout m, il existe pour certains x tel que x ² ≧m. L'affirmation est vraie car pour tout m, il existe pour un plus grand x tel que x ² ≧m.