Naar inhoud
BetaAI Begrippen

AI-begrippen in gewone taal. Zoek een begrip, blader op letter of filter op onderwerp.

True quantified Boolean formula

Engels: True quantified Boolean formula · Ook wel: TQBF, QSAT, true QBF, quantified SAT

In het kort

Een ware gekwantificeerde booleaanse formule is een logische formule die als geheel waar is. Elke variabele krijgt vooraan de eis ‘voor elke waarde’ of ‘er is een waarde’, zodat de formule niet meer per invulling kan wisselen. De uitspraak ‘voor elke waarde van x is er een y zodat x of y waar is’ komt waar uit en hoort daarom bij de verzameling TQBF, ook QSAT genoemd.

Waarom is dit belangrijk?

Met een ware gekwantificeerde booleaanse formule kunnen onderzoekers nagaan of een plan standhoudt bij elke mogelijke tegenreactie. In de robotica gebruiken zij dit voor veilige planning, zodat een machine ook bij onverwachte situaties een geldige reeks stappen houdt. Voor studenten en ontwikkelaars geeft dat een vaste toets voor lastige planningsvragen, maar de benodigde rekentijd groeit bij meer keuzes zeer snel.

Zo werkt het in de praktijk

Bij onvolledige schakelingen dekt een ware gekwantificeerde booleaanse formule open gedrag. Een universele kwantor staat voor keuzes die het ontwerp nog niet vastlegt. Een overzicht van de Johannes Kepler Universiteit Linz koppelt deze toepassingen aan het portaal QBFLIB.

Het Archive of Formal Proofs beschrijft twee oplosprogramma’s met een bewijs in Isabelle. Isabelle is een systeem dat zo’n bewijs machinaal controleert. Eén programma vouwt kwantoren uit, het andere zoekt stap voor stap.

De wedstrijd QBFEVAL laat oplosprogramma’s formules in het formaat QDIMACS lezen. Sterke programma’s zoeken met QDPLL, een uitbreiding van de methode DPLL. Zij lezen ook de formaten QCIR en QAIGER.

Bron: en.wikipedia.org

Gecontroleerd op 5 november 2026