true quantified Boolean formula

Angol

Főnév

true quantified Boolean formula (tsz. true quantified Boolean formulas)

(informatika, mesterséges intelligencia) True Quantified Boolean Formula (TQBF) egy speciális logikai formula az elméleti számítástechnikában és logikában, amely teljesen kvantifikált Boole-formula, és amelynek eldöntése, hogy igaz-e vagy hamis, a PSPACE-teljes problémák egyik klasszikus példája.

1. Mi az a True Quantified Boolean Formula?

Egy logikai formula, amelyben minden változóra kvantor (egzisztenciális ∃ vagy univerzális ∀) van alkalmazva.
A formula Boole-műveleteket (ÉS, VAGY, NEM) is tartalmazhat.
A TQBF eldöntése azt jelenti, hogy meg kell határozni: a formula igaz-e minden lehetséges értékelés mellett a kvantorok logikája szerint.

2. Felépítése

Formátuma: ${\textstyle Q_{1}x_{1}Q_{2}x_{2}\dots Q_{n}x_{n}\,\varphi (x_{1},x_{2},\dots ,x_{n})}$ ${\textstyle Q_{1}x_{1}Q_{2}x_{2}\dots Q_{n}x_{n}\,\varphi (x_{1},x_{2},\dots ,x_{n})}$ , ahol
- ${\textstyle Q_{i}}$ kvantor (∃ vagy ∀),
- ${\textstyle x_{i}}$ Boole-változó,
- ${\textstyle \varphi }$ egy Boole-kifejezés kvantor nélküli változókkal.

3. Példa

$\exists x\forall y\exists z\,((x\lor y)\land (\neg y\lor z))$

Itt meg kell határozni, hogy létezik-e olyan ${\textstyle x}$ , hogy minden ${\textstyle y}$ -ra létezik ${\textstyle z}$ , amire a formula igaz.

4. Jelentősége

A TQBF probléma PSPACE-teljes, ami azt jelenti, hogy a legnehezebb problémák közé tartozik, amelyek megoldása polinom memóriával lehetséges.
Általánosítja a Boole-kifejezések igazságértékének eldöntését kvantorokkal.
Fontos szerepe van a komplexitáselméletben és a formális verifikációban.

5. Alkalmazások

Formális logika és matematikai logika.
Automataelmélet és modellezés.
Programverifikáció és automatizált következtetés.
Mesterséges intelligencia bizonyos területei.

6. Összefoglalás

A True Quantified Boolean Formula egy teljesen kvantifikált logikai formula igazságának eldöntésére irányuló kérdés, amely a PSPACE-teljes problémák kulcsfontosságú példája, és alapvető szerepet játszik az elméleti számítástechnikában és formális logikában.

További információk

true quantified Boolean formula - Szótár.net (en-hu)
true quantified Boolean formula - Sztaki (en-hu)
true quantified Boolean formula - Merriam–Webster
true quantified Boolean formula - Cambridge
true quantified Boolean formula - WordNet
true quantified Boolean formula - Яндекс (en-ru)
true quantified Boolean formula - Google (en-hu)
true quantified Boolean formula - Wikidata
true quantified Boolean formula - Wikipédia (angol)