Predikaattilogiikka

Predikaattilogiikka, eli ensimmäisen kertaluvun predikaattilogiikka, on logiikan osa, jossa lausekkeet rakentuvat predikaateista, muuttujista ja funktioista sekä kvantorimerkeistä (∀ ja ∃). Se laajentaa propositiologiikkaa mahdollistamalla suhteiden ja määritysten ilmaisun yleisesti.

Syntaksi kuvaa, millaisia lausekkeita kieli sisältää. Kielellä muodostetaan termiä, jotka voivat sisältää funktioita ja vakioita. Atominen lauseke on muoto P(t1,…,tn), missä P on predikaatti ja t1,…,tn termiä. Lauseet muodostuvat yhdistämällä atomisia lausekkeita logiikan yhdistys- ja implikaatiosymbolien kanssa sekä kvantorilausekkeilla ∀x φ ja ∃x φ, missä x on sidottu muuttuja. Vapaiden ja sidottujen muuttujien erottaminen sekä α-konversion muuttujien nimeämisen vuoksi ovat tärkeitä käsitteitä.

Semantiikka määrittelee, mitä lauseet tarkoittavat malleissa. Malli M koostuu domaanista D ja tulkinnoista funktioille sekä predikaateille. Lauseen totuus M:ssä merkitään M ⊨ φ, jolloin φ on totta tietyn tulkinnan ja mahdollisten muuttujien arvojen alaisuudessa. Lauseita voidaan tutkia mallien, totuuden ja malleihin liittyvän validiteetin kautta: lause on validi, jos se on tosi kaikkialla.

Deduktio ja todistaminen käsittelevät, miten lausekkeista voidaan johtaa johtopäätöksiä. Käytössä ovat järjestelmät kuten luonnollinen päättely, sekventiaalinen päättely ja Hilbert-tyyliset järjestelmät. Gödelin täydellisyyslause osoittaa, että jokainen validi lause on todistettavissa yleisillä päättelysäännöillä, ja toisin päin. Tärkeiksi ominaisuuksiksi nousevat kompaktisuus sekä normalisointimenetelmät kuten prenex-normaliforma ja Skolemisaatio. Ensimmäisen kertaluvun predikaattilogiikka on yleistyy, mutta se on myös ratkaisematon (undecidable) yleisellä tasolla.