otsustusprotseduure

Otsustusprotseduur on arvutuslik meetod (algoritm), mis iga etteantud lausete kogumi jaoks lõplikult otsustab, kas antud lause on loogiliselt kehtiv või kas ta on teoorias tõeline. Tavaliselt on jutt teooriast või loogikast: kui teoorial T on olemas otsustusprotseduur, siis iga lauseline φ teoorias T saab lõpliku jah/ei vastuse. Selline võime nimetatakse decidability ehk otsustatavus.

Otsustusprotseduuride manustused ja näited

- Propositsionaalne loogika: igale lausele saab anda otsustava vastuse tõeste/valede väärtustega töövahenditega (nt tõevärtidabelid), mis teevad lause otsustatavaks.

- Presburgeri aritmeetika: loogika arvude kohta, mis sisaldab ainult lisamist ja naturaalsete arvude korpust, on otsustusprotseduuriga decidable.

- Reaalsete sulgunud alade teooria (real closed fields): Tarski tõestas, et teooria, mis käsitleb reaalnumbreid koos lisamise ja korrutamisega, on otsustatav. See on aluseks reaalsete algebraliste omaduste otsingule.

- Lineaarne reaalarvude aritmeetika (LRA): lineaarprogrammide ja erijuhtude puhul on olemas otsustusprotseduurid.

- SMT-lahendajad: erinevate teooriate jaoks ühendatakse otsustusprotseduurid (või nende kvaliteetseid heuristikuid) tarkvaralistes tõestus- ja kontrollisüsteemides.

Piirangud ja ajalugu

Mitte kõik teooriad on decidable. Näiteks esimese järgu teooria, mis hõlmab loomade liiki arveid ja loomuliku arvu suurendamist ja korrutamist (Peano aritmeetika) ei ole decidable. Otsustusprobleemide uurimine sai alguse Tarski küsimustikust 20. sajandi keskpaigas ning on oluline valdkond loogikas, automaatse tõestamise ja tarkvara verifikatsiooni kontekstis. SMT-lahendused ja otsustusprotseduurid annavad praktilisi vahendeid formaliseeritud süsteemide kontrolliks ning muidugi näitavad teooriate decidability ulatust.