|
|
| (17 versions intermédiaires par 2 utilisateurs non affichées) |
| Ligne 1 : |
Ligne 1 : |
| | == Définition == |
| | En théorie de la complexité, en informatique théorique, en logique mathématique, une formule booléenne quantifiée (ou formule QBF pour ''quantified binary formula'' en anglais) est une formule de la logique propositionnelle où les variables propositionnelles sont quantifiées. |
|
| |
|
| == Domaine == | | == Français == |
| [[Category:Vocabulary]]
| |
| [[Category:Logique propositionnelle]]Logique propositionnelle<br/>
| |
| [[Category:Coulombe]]Coulombe<br/>
| |
|
| |
|
| == Définition ==
| | '''Formule booléenne quantifiée vraie''' |
|
| |
|
| | '''Formule booléenne quantifiée''' |
|
| |
|
|
| | == Anglais == |
| | |
| | '''True quantified Boolean formula ''' |
|
| |
|
| == Français ==
| |
| <h4>
| |
| <poll>
| |
| Choisissez parmi ces termes proposés :
| |
| formule booléenne quantifiée
| |
| Formule booléenne quantifiée vraie
| |
| </poll></h4>
| |
| <h4>Discussion:</h4>
| |
| Pour le moment, le terme privilégié est «formule booléenne quantifiée vraie».
| |
| <br />
| |
|
| |
|
| 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.
| | ==Sources== |
|
| |
|
| Source: https://fr.wikipedia.org/wiki/Formule_bool%C3%A9enne_quantifi%C3%A9e
| | [https://fr.wikipedia.org/wiki/Formule_bool%C3%A9enne_quantifi%C3%A9e Source : Wikipedia ] |
|
| |
|
| == Anglais ==
| | [[Utilisateur:Claude COULOMBE | source : Claude Coulombe, Datafranca.org]] |
|
| |
|
| === True quantified Boolean formula ===
| |
|
| |
|
| In computational complexity theory, the language TQBF is a formal language consisting of the true quantified Boolean formulas. A (fully) quantified Boolean formula is a formula in quantified propositional logic where every variable is quantified (or bound), using either existential or universal quantifiers, at the beginning of the sentence. Such a formula is equivalent to either true or false (since there are no free variables). If such a formula evaluates to true, then that formula is in the language TQBF. It is also known as QSAT (Quantified SAT).
| | [[Catégorie:GRAND LEXIQUE FRANÇAIS]] |
| <br/>
| |
| <br/>
| |
| <br/>
| |
| <br/>
| |
| <br/>
| |
| <br/>
| |
| <br/>
| |
Dernière version du 27 janvier 2024 à 21:56
Définition
En théorie de la complexité, en informatique théorique, en logique mathématique, une formule booléenne quantifiée (ou formule QBF pour quantified binary formula en anglais) est une formule de la logique propositionnelle où les variables propositionnelles sont quantifiées.
Français
Formule booléenne quantifiée vraie
Formule booléenne quantifiée
Anglais
True quantified Boolean formula
Sources
Source : Wikipedia
source : Claude Coulombe, Datafranca.org
