tyydyttävyys

Tyydyttävyys (satisfiability) on logiikan ja tietojenkäsittelyn keskeinen käsite, jolla kuvataan, voiko lauseke tai lausejoukko toteutua totuudellisesti tietyssä tulkinnassa. Propositional logiikassa lauseke on tyydyttävä, jos on totuusarvojen asettelu muuttujille, jolla koko lauseke saa arvon tosi. Ensimmäisen kertaluvun logiikassa tyydyttävyys tarkoittaa, että on malli eli tulkinta ja rakenne, jossa kaikki annetut lauseet pitävät paikkansa.

Esimerkki: Lauseke p ∨ q on tyydyttävä, koska voidaan asettaa p todeksi ja q epätodeksi tai päinvastoin, jolloin koko lauseke on tosi. Lauseke p ∧ ¬p on epätyydyttävä, koska se ei voi olla tosi missään tulkinnassa. Lauseke p ∨ ¬p on sekä tyydyttävä että pätevä, eli se on tosi kaikissa tulkinnoissa.

Sovelluksissa tyydyttävyys on keskeinen ongelma, tunnettu SAT-ongelmana. Propositional SAT on NP-kova, ja käytännön ratkaisut hyödyntävät erilaisia hakualgoritmeja sekä heuristiikkoja ja optimoituja järjestelmiä. Ensimmäisen kertaluvun tyydyttävyydellä on laajempia, tutkimuksellisia ja teoreettisia ulottuvuuksia, ja sen ratkaiseminen yleisellä tasolla voi olla ratkaisematon ongelma. Tyydyttävyysmittaukset ovat olennaisia esimerkiksi todistamiseen, mallintamiseen, ohjelmistotestaukseen sekä automaattiseen oikeudelliseen ja suunnitteluun.