Een woordenboek van de filosofie

Begrippen, stromingen, denkers (2017)

Gepubliceerd op 19-04-2017

Beslisbaar

betekenis & definitie

Theorieën, in de zin waarin de rekenkunde een theorie is, zijn beslisbaar als er formaliseringen van bestaan die volledig zijn. In systemen zonder contingente proporties, zoals formaliseringen van de rekenkunde, is een welgevormde formule (zie axiomastelsel) beslisbaar als en alleen als zijzelf of haar negatie een theorema is.

Als er contingente proposities in het geding zijn, zoals in formaliseringen van de propositiec alculus , dan is een welgevormde formule beslisbaar als en alleen als men kan bewijzen dat zij logisch waar, logisch onwaar of geen van beide is. Een beslissingsprocedure stelt ons in staat dit mechanisch te doen door in een eindig aantal stappen eenvoudig een regel te volgen. Er bestaan beslissingsprocedures voor de propositiecalculus en de monadische predikatencalculus, maar in het algemeen niet voor complexere systemen. Een bewijs dat een dergelijke procedure voor een bepaald gebied bestaat, of niet bestaat, wordt een positieve, respectievelijk negatieve, oplossing van het beslissings- of decisieprobleem genoemd. De negatieve oplossing voor de (niet-monadische) predikatencalcu- lus vormt het theorema van Church (1936).