« Formule booléenne quantifiée vraie » : différence entre les versions
Aucun résumé des modifications Balise : Éditeur de wikicode 2017 |
m (Pitpitt a déplacé la page True quantified Boolean formula vers Formule booléenne quantifiée vraie) |
(Aucune différence)
| |
Version du 11 juin 2019 à 09:26
Domaine
Coulombe
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
Contributeurs: Claude Coulombe, wiki, Sihem Kouache
