« Formule booléenne quantifiée vraie » : différence entre les versions
m (Remplacement de texte — « <small>Entrez ici les domaines et catégories...</small> » par « ») |
m (Remplacement de texte — « Category:Coulombe » par « <!-- Coulombe --> ») |
||
| Ligne 3 : | Ligne 3 : | ||
<!-- Vocabulary2 --> | <!-- Vocabulary2 --> | ||
<!-- Coulombe -->Coulombe<br/> | |||
== Définition == | == Définition == | ||
Version du 4 juillet 2019 à 10:07
en construction
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
