Egy
ábécé feletti elsőrendű logikai nyelv
interpretációját ( modelljét vagy algebrai struktúráját ) olyan
négyes határozza meg, melyben
az
individuumok (objektumok) nem üres halmaza (univerzuma),
a
függvény minden
konstansszimbólumhoz egy
individuumot rendel,
az
függvény minden
aritású függvényszimbólumhoz olyan
függvényt rendel, melynek értelmezési tartománya
, és értékeit
-ból veszi fel, azaz
a
függvény pedig olyan, hogy ha a
predikátumszimbólum aritása
és
, akkor
predikátum (
vagy
értéket felvevő, ún. logikai értékű függvény). Ha
propozicionális szimbólum, akkor
vagy
, vagy
.
Legyen az elsőrendű nyelv univerzuma
. Bővítsük ki a nyelvet az univerzum objektumait jelölő új konstansszimbólumokkal:
ahol
-t a
halmazból úgy kapjuk, hogy minden
objektumhoz rendelünk egy új – általunk
-val jelölt – konstansszimbólumot.
Egy olyan
függvényt, amely az elsőrendű nyelv véges sok változójához
-beli új szimbólumot rendel,
-értékelő helyettesítésnek nevezünk.
a
logikai kifejezés értékelése , ha
. Ha
a
logikai kifejezés értékelése, akkor a
kifejezést úgy nyerjük, hogy
-ban a paraméterek minden szabad előfordulását a
által hozzájuk rendelt új konstansszimbólumokkal helyettesítjük. A kibővített nyelv paramétermentes ( zárt ) logikai kifejezéseit értékelt kifejezéseknek nevezzük.
Legyen
a nyelv egy interpretációja. Egy értékelt term értéke
-ben az alábbi – rekurzív definícióval megadott –
-beli objektum. (Egy
term
-beli értékét
-mel fogjuk jelölni.)
Ha
és
, akkor
.
Ha
az
-hoz rendelt új
szimbólum, akkor
.
Ha
egy értékelt term, ahol a
termek értékei
-ben rendre
, és
, akkor
Egy
értékelt formula értéke
-ben (jelölése:
) a következő, rekurzív definícióval megadott érték:
Ha
egy értékelt atomi formula, ahol a
termek értékei
-ben rendre
, és
, akkor
Ha
és
értékei rendre
és
, akkor
pontosan akkor, ha
és
;
pontosan akkor, ha
vagy
;
pontosan akkor, ha
vagy
. Egyébként
.
Ha
értéke
, akkor
pontosan akkor, ha
, egyébként
.
A
értékelt formula igaz az
interpretációban, ha
, egyébként a
formula hamis
-ben.
Egy elsőrendű nyelv egy
formulája kielégíthető , ha van a nyelvnek olyan interpretációja és
-nak olyan
értékelése, amely mellett
igaz, egyébként
kielégíthetetlen (vagy logikai ellentmondás ). Egy elsőrendű nyelv egy
formulája logikai törvény , ha a nyelv bármely interpretációjában és
bármely
értékelése mellett
igaz. Jelölése:
.
Az
és
elsőrendű formulák logikailag ekvivalensek , ha a nyelv minden
interpretációjában és a formulák minden közös
értékelése mellett
és
azonos igazságértékű. Jelölése:
.
Legyen
elsőrendű formulák (premisszák) egy halmaza és
egy elsőrendű formula (konklúzió). Azt mondjuk, hogy
következménye a
-beli formuláknak, ha a nyelv minden olyan interpretációjában és a
-beli és a
formulák tetszőleges olyan közös
értékelése esetén, mely mellett a
-beli formulák mind igazak, ott
is igaz. Jelölése:
Elsőrendű formulák egy
halmaza kielégíthető , ha van olyan interpretáció és a
-beli formuláknak olyan közös értékelése, mely mellett minden
-beli formula épp igaz, egyébként a
formulahalmaz kielégíthetetlen .