« Formule booléenne quantifiée vraie » : différence entre les versions
Aucun résumé des modifications |
Aucun résumé des modifications |
||
| Ligne 3 : | Ligne 3 : | ||
== Définition == | == 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. | 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. | |||
Version du 3 janvier 2021 à 23:57
en construction
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 féminin
formule booléenne quantifiée féminin
Anglais
True quantified Boolean formula
Contributeurs: Claude Coulombe, wiki, Sihem Kouache
