Naar inhoud
BetaAI Begrippen

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

Vervulbaarheid (mathematische term)

Engels: Satisfiability · Ook wel: satisfiability

In het kort

Vervulbaarheid is een eigenschap van een logische formule in de wiskundige logica. Een formule is vervulbaar wanneer er minstens één interpretatie bestaat die alle symbolen zo invult dat de formule waar wordt, terwijl een geldige formule bij elke interpretatie waar is. Bestaat er geen enkele interpretatie die de formule waar maakt, dan heet de formule onvervulbaar, zoals de bewering dat iets tegelijk waar en onwaar is.

Waarom is dit belangrijk?

Zo kunnen computers bepalen of een reeks eisen samen een werkbare oplossing toelaat, bijvoorbeeld bij het indelen van taken. In wetenschap en techniek gebruiken ontwerpers dit bij het maken van hardware en de controle van software. Studenten en ontwikkelaars merken dat een programma zo een schema kan afwijzen of goedkeuren, al kan de zoektocht bij grote vraagstukken zeer lang duren of een oplossing missen.

Zo werkt het in de praktijk

Het systeem Satplan zoekt in de kunstmatige intelligentie een stappenplan via vervulbaarheid. Tang en Lin gebruikten een SAT-solver, een rekenprogramma voor dit probleem, om de stelling van Arrow te bewijzen. Die stelling beperkt welke stemregels tegelijk kunnen gelden.

Onderzoekers vergelijken solvers in de International SAT Solver Competition. Teams meten daar welke solver welke formules oplost. De wedstrijd heeft ook een onderdeel voor solvers op meerdere processoren.

Veel solvers bouwen op het DPLL-algoritme, een systematische zoektocht, of op CDCL. CDCL staat voor conflict-driven clause learning en leert uit een conflict een nieuwe voorwaarde. Solvers zetten de formule vaak eerst om naar de conjunctieve normaalvorm, een vaste schrijfwijze van losse eisen.

Bron: en.wikipedia.org

Gecontroleerd op 5 november 2026