Formule booléenne quantifiée vraie

Définition

En théorie de la complexité et en logique mathématique, une formule booléenne quantifiée vraie (en anglais true quantified binary formula) est une formule de logique propositionnelle évaluée à vrai où les variables propositionnelles sont quantifiées par des opérateurs de quantification comme «pour tout» ∀ et «il existe», ∃. Cela entraîne le problème de satisfaisabilité booléenne (problème SAT) qui consiste à trouver l'assignation des variables qui rend une formule de logique propositionnelle vraie. Ce problème est très important en théorie de la complexité et pour la solution du problème P = NP.

Français

Formule booléenne quantifiée vraie

formule booléenne quantifiée

Anglais

True quantified Boolean formula

Source: https://fr.wikipedia.org/wiki/Formule_bool%C3%A9enne_quantifi%C3%A9e

source : Claude Coulombe, Datafranca.org