Mathématiques discrètes - Logique des prédicats

Predicate Logic traite des prédicats, qui sont des propositions contenant des variables.

Logique des prédicats - Définition

Un prédicat est une expression d'une ou plusieurs variables définies sur un domaine spécifique. Un prédicat avec des variables peut être une proposition en attribuant une valeur à la variable ou en quantifiant la variable.

Voici quelques exemples de prédicats -

• Soit E (x, y) "x = y"
• Soit X (a, b, c) "a + b + c = 0"
• Soit M (x, y) "x est marié à y"

Formule bien formée

Well Formed Formula (wff) est un prédicat contenant l'un des éléments suivants -

• Toutes les constantes propositionnelles et variables propositionnelles sont des wffs

• Si x est une variable et Y est un wff, $ \ forall x Y $ et $ \ existe x Y $ sont également wff

• La valeur de vérité et les fausses valeurs sont des wffs

• Chaque formule atomique est un wff

• Tous les connecteurs connectant des wffs sont des wff

Quantificateurs

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

Quantificateur universel

Le quantificateur universel indique que les déclarations dans sa portée sont vraies pour chaque valeur de la variable spécifique. Il est désigné par le symbole $ \ forall $.

$ \ forall x P (x) $ est lu comme pour chaque valeur de x, P (x) est vrai.

Example - "L'homme est mortel" peut être transformé en la forme propositionnelle $ \ forall x P (x) $ où P (x) est le prédicat qui dénote x est mortel et l'univers du discours est tout homme.

Quantificateur existentiel

Le quantificateur existentiel indique que les déclarations dans sa portée sont vraies pour certaines valeurs de la variable spécifique. Il est indiqué par le symbole $ \ existe $.

$ \ existe x P (x) $ est lu car pour certaines valeurs de x, P (x) est vrai.

Example - "Certaines personnes sont malhonnêtes" peut être transformé en la forme propositionnelle $ \ existe x P (x) $ où P (x) est le prédicat qui dénote x est malhonnête et l'univers du discours est quelques personnes.

Quantificateurs imbriqués

Si nous utilisons un quantificateur qui apparaît dans le cadre d'un autre quantificateur, il est appelé quantificateur imbriqué.

Example

• $ \ forall \ a \: \ exists b \: P (x, y) $ où $ P (a, b) $ désigne $ a + b = 0 $

• $ \ forall \ a \: \ forall \: b \: \ forall \: c \: P (a, b, c) $ où $ P (a, b) $ désigne $ a + (b + c) = ( a + b) + c $

Note - $ \ forall \: a \: \ existe b \: P (x, y) \ ne \ existe un \: \ forall b \: P (x, y) $