Naar inhoud
BetaAI Begrippen

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

Vervulbaarheidsprobleem

Engels: Boolean satisfiability problem · Ook wel: SAT, boolean satisfiability, satisfiability problem, propositional satisfiability, SAT-probleem

In het kort

Het vervulbaarheidsprobleem (SAT) is de vraag of een logische formule ooit helemaal waar kan worden. Anders dan een vaste berekening onderzoekt het of elke variabele waar of onwaar kan zijn, zodat de hele formule klopt. De formule "a en niet b" is vervulbaar met a waar en b onwaar, terwijl de formule "a en niet a" voor elke invulling onwaar blijft.

Waarom is dit belangrijk?

Het oplossen van zulke vragen maakt automatische planning van praktische taken en controle van technische ontwerpen mogelijk. In de wetenschap gebruiken onderzoekers het vervulbaarheidsprobleem bij het ontwerp en de controle van hardware en software. Voor studenten en werknemers ondersteunt dat de planning van werk en de controle van digitale systemen, maar bij grote vraagstukken kan de rekentijd soms sterk oplopen.

Zo werkt het in de praktijk

Bij het samenstellen van producten controleert het vervulbaarheidsprobleem of gekozen onderdelen samen geldig zijn. CAS Software AG doet dat in een commerciële configurator. Een vroeg praktijkgebruik lag bij opdrachten in de ruimtevaart.

Aan de Kyushu-universiteit onderzoeken wetenschappers het terugvinden van een deel van een AES-sleutel. AES is een bekende manier om gegevens te versleutelen. Zij schrijven die vraag als een formule voor het vervulbaarheidsprobleem.

Specialisten schrijven productregels als conjunctieve normaalvorm, een vaste vorm waarin elke groep voorwaarden moet gelden. Oplossers met DPLL en CDCL testen waarden stap voor stap, ook bij CAS Software AG. Bij een conflict gebruikt het systeem MaxSAT, een variant die zo veel mogelijk eisen laat gelden.

Bron: en.wikipedia.org

Gecontroleerd op 23 oktober 2026