Quantificateurs

Question 1

(Définition) Prédicat

Answer 1

Énonce mathématique dont la valeur de vérité dépend des variables libres noté P ( x )

Question 2

(Définition) Variable libre

Answer 2

Variable pour laquelle on ne connaît pas de valeur

Question 3

(Définition) Quantification universelle

Answer 3

Le prédicat évalué à vrai quelque soit la valeur du paramètre x.
noté ∀x

Question 4

(Définition) Quantification existentielle

Answer 4

Le prédicat évalué à vrai pour (au moins) la valeur du paramètre x.
noté ∃x

Question 5

(Traduire) ∀n ∈ ℕ, ∃m n ∈ ℕ; n<m

Answer 5

Quel que soit n appartenant à ℕ, il existe m appartenant à ℕ tel que n<m.

Question 6

(Définition) Expression booléenne atomique

Answer 6

Expression de type verbe sujet complément qui ne peut pas être subdivisée en d’autres expressions booléennes.

Question 7

(Définition) Satisfiabilité

Answer 7

Une instance du problème satifiable consiste en une équation booléenne contenant des variables libres. Une telle instance est dite satisfiable lorsqu’il existe une assignation de variables telle que l’équation est évaluée à vrai.

Question 8

(Définition) Insatisfiabilité

Answer 8

Une instance est insatifiable lorsqu’aucune assignation assignation de variables ne permet à son expression booléenne d’être vraie.

Question 9

La version abrégée de (∃x I x ∈ T ∧ P(x))

Answer 9

(∃x ∈ T I P(x))

Question 10

Loi de De Morgan généralisées aux quantificateurs ∃

Answer 10

(∃x ∈ T I ¬P(x)) ⇔ ¬(∀x ∈ T I P(x))

Question 11

Loi de De Morgan généralisées aux quantificateurs ∀

Answer 11

(∀x ∈ T I ¬P(x)) ⇔ ¬(∃x ∈ T I P(x))