Emlékezzünk arra a 7. fejezetből, hogy a logikai nyelvek modelljei azok a formális struktúrák, amelyek a vizsgálat tárgyát képező lehetséges világokat alkotják. Az ítéletkalkulus modelljei csupán az ítéletszimbólumok igazságértékeinek halmazai. Az elsőrendű logika modelljei ennél érdekesebbek. Először is, ezek tartalmaznak objektumokat! A modell tárgyterülete (domain) azoknak az objektumoknak a halmaza, amelyeket a tárgyterület tartalmaz; ezeket az objektumokat szoktuk a tárgyterület elemeinek (domain elements) nevezni. A 8.2. ábra bemutat egy modellt öt objektummal: Oroszlánszívű Richárd, Anglia királya 1189-től 1199-ig; öccse, gonosz János király, aki 1199-től 1215-ig uralkodott; Richárd és János bal lába; végül egy korona.

A modellben található objektumok többféle relációban lehetnek egymással. A 8.2. ábrán Richárd és János testvérek. Formálisan, egy reláció csak egymással kapcsolatban lévő objektumok n-eseinek (tuple) halmaza. (Egy n-es az objektumok egy rögzített sorrendben felsorolt gyűjteménye, amely objektumokat a 〈〉 zárójelpár vesz körbe.) Így tehát ebben a modellben a testvérreláció a következő halmaz:

{〈Oroszlánszívű Richárd, János király〉, 〈János király, Oroszlánszívű Richárd〉}(8.1)

(Itt magyarul neveztük meg az objektumokat, de képzeletben be lehetne helyettesíteni a neveket például képekkel is.) A korona János király fején van, tehát a „fején” relációhoz csak egy n-es tartozik 〈a korona, János király〉.

A „testvér” és a „fején” relációk bináris relációk – ez azt jelenti, hogy két objektum között állítanak fel kapcsolatot. A modell ezenkívül egyelemű, unáris relációkat vagy tulajdonságokat is tartalmaz: A „személy” tulajdonság egyaránt igaz Richárdra és Jánosra; a „király” tulajdonság csak Jánosra igaz (feltehetően azért, mert Richárd ekkor már halott volt); míg a „korona” tulajdonság csak a koronára igaz.

8.2. ábra - Egy öt objektumot – két bináris relációt, három egyelemű relációt (címkékkel jelezve az objektumokon) és egy egyargumentumú függvényt, bal láb – tartalmazó modell

A kapcsolatok egyes típusai leginkább függvényeknek tekinthetők, ahol egy adott objektumnak pontosan csak egy másik objektummal kell ilyen kapcsolatban lennie. Például minden egyes személynek egy bal lába van, tehát a modellben található egy „bal láb” függvény, ami a következő leképezéseket teszi lehetővé:

〈Oroszlánszívű Richárd〉 ⟶ Richárd bal lába

〈János király〉 ⟶ János bal lába (8.2)

Pontosabban megfogalmazva, az elsőrendű logika modelljei totális függvényeket (total functions) kívánnak meg, ami azt jelenti, hogy minden bemeneti n-eshez tartoznia kell egy értéknek. Így tehát a koronához tartoznia kell egy bal lábnak, és ennek így kell lennie minden bal láb esetében. Létezik erre a problémára egy technikai megoldás, amely egy hozzáadott „láthatatlan” objektumot vezet be: egy bal lábat rendel mindenhez, amelynek nincs bal lába, beleértve önmagát is. Szerencsére, amíg valaki nem tesz kijelentéseket a bal lábakról vagy olyan dolgokról, amelyeknek nincs bal lábuk, ezeknek a technikai problémáknak nincs jelentőségük.

Most pedig nézzük a nyelv szintaxisát. A türelmetlen olvasó teljes leírást talál az elsőrendű logika formális nyelvtanáról a 8.3. ábrán.

Az elsőrendű logika alapvető szintaktikai elemei az objektumokat, relációkat és függvényeket megjelenítő szimbólumok. A szimbólumoknak tehát három típusa létezik: konstansszimbólumok (constant symbols), amelyek az objektumokat jelölik; predikátumszimbólumok (predicate symbols), amelyek a relációkat jelenítik meg; és a függvényszimbólumok (function symbols), amelyekkel függvényekre hivatkozhatunk. Azt a konvenciót fogjuk követni, hogy a szimbólumok mind nagybetűvel kezdődnek. Például használhatjuk a Richárd és János konstansszimbólumokat; a Testvér, Fején, Személy, Király és Korona predikátumszimbólumokat, valamint a BalLáb függvényszimbólumot. Úgy, mint az ítéletszimbólumoknál, a nevek megválasztása itt is teljes mértékben a felhasználóra van bízva. Minden egyes predikátum- és függvényszimbólum együtt jár egy számossággal (arity), ami behatárolja a paraméterek számát.

8.3. ábra - Az elsőrendű logika (egyenlőséggel kiegészített) szintaxisa Backus–Naur-forma jelöléseivel. (Lásd az 1. szakasz - B1. Nyelvek definiálása Backus–Naur-Formában (BNF) részben, ha ez a jelölés ismeretlen.) A szintaxis szigorú a zárójelezés tekintetében; a zárójelekről és az operátori elsőbbségről a 7.4.1. szakasz - Szintaxis részben szereplő megjegyzések ugyanúgy vonatkoznak az elsőrendű logikára is.

A szemantika a mondatokat a modellekhez kapcsolja, és képesnek kell lennie az igazság meghatározására. Hogy ez megtörténjen, szükségünk van egy interpretációra, amely pontosan megjelöli, hogy mely objektumok, relációk és függvények felelnek meg a konstans-, predikátum- és függvényszimbólumoknak. Egy lehetséges interpretáció – amit szándékolt interpretációnak (intended interpretation) nevezünk – a mi esetünkben a következő:

Sok más lehetséges interpretáció is létezik, ami ezeknek a szimbólumoknak a modellhez való kapcsolatát írja le. Például egy lehetséges interpretációban Richárd jelenti a koronát és János a János király bal lábát. A modell öt objektumot tartalmaz, így 25 lehetséges interpretáció adható meg csak a Richárd és a János konstansszimbólumokhoz.

Figyeljük meg, hogy nem minden objektumnak van arra szüksége, hogy elnevezzék – például a szándékolt interpretáció nem nevezi meg a koronát vagy a lábakat. Az is lehetséges, hogy egy objektumnak több neve legyen; létezik olyan interpretáció, amelyben a Richárd és a János is a koronára vonatkozik. Ha ez a lehetőség zavaró, emlékezzünk arra, hogy az ítéletlogikában teljességgel elfogadható egy olyan modell, amelyben a Felhős és a Napos egyaránt igaz. A tudásbázis feladata az, hogy kizárja azokat a modelleket, amelyek ellentmondásban vannak ismereteinkkel.

Bármely mondat igazságát egy modell és a mondat szimbólumainak az interpretációja határozza meg. Így tehát a vonzat, az érvényesség és más jellemzők az összes lehetséges modell és az összes lehetséges interpretáció termjeinek felhasználásával vannak meghatározva. Fontos megjegyezni, hogy a tárgyterület elemek száma minden egyes modellben korlátlan lehet – a tárgyterület elemei például lehetnek egész vagy valós számok. Ebből következően, a lehetséges modellek száma korlátlan, mint ahogy az interpretációk száma is. A maga után vonzásnak az összes lehetséges modell felsorolásával történő vizsgálata, ami az ítéletlogikában működik, nem lehetséges az elsőrendű logikában. Még ha az objektumok száma korlátos is, a kombinációk száma nagyon nagy lehet. A példánkban szereplő objektumokkal hozzávetőlegesen 10²⁵ a kombinációk száma, egy öt objektummal rendelkező tárgyterületben (lásd 8.5. feladat).

Egy term (term) egy objektumra vonatkozó logikai kifejezés. A konstansszimbólumok tehát termek, de nem mindig kényelmes önálló szimbólumot alkalmazni minden egyes objektum megnevezésénél. Magyarul inkább a „János király bal lába” kifejezést használjuk, mintsem nevet adjunk a lábának. Ezért használunk függvényszimbólumokat: a konstansszimbólumok használata helyett inkább a BalLáb(János)-t alkalmazzuk. Általános esetben egy összetett term egy függvényszimbólumból áll, amelyet a függvényszimbólum argumentumainak zárójelezett listája követ. Fontos megjegyezni, hogy egy összetett term nem más, mint egy bonyolult formájú név, és nem egy „értéket visszaadó szubrutin hívás”. Nem egy BalLáb szubrutinról van szó, amely bemenetként megkap egy személyt, és visszaad egy lábat. Tudunk következtetni a bal lábakkal kapcsolatban (pl. kiindulva az általános szabályból, hogy mindenkinek van egy bal lába, és ebből levezethető, hogy Jánosnak is lennie kell) anélkül, hogy valaha is megadnánk a BalLáb definícióját. Ez is olyasmi, amit nem tehetünk meg a programozási nyelvek szubrutinjaival.^[77]

A termek formális szemantikája nyilvánvaló. Tekintsük az f(t₁, …, t_n) termet. Az f függvényszimbólum a modellben található valamely függvényre (nevezzük F-nek) vonatkozik; az argumentum termek a tárgyterületben fellelhető objektumokra vonatkoznak (nevezzük őket d₁, …, d_n-nek); és a term egészében arra az objektumra vonatkozik, ami a d₁, …, d_n-re alkalmazott F függvény értéke. Például tételezzük fel, hogy ha a BalLáb függvényszimbólum a (8.2) egyenletben mutatott függvényre vonatkozik, és a János vonatkozik János királyra, akkor a BalLáb(János) János király bal lábát jelöli. Ezen a módon az interpretáció rögzíti minden termnek a referenciáit.

Most, hogy vannak objektumokra vonatkozó termeink és relációkra vonatkozó predikátumszimbólumaink, összerakhatjuk őket, hogy tényeket kifejező atomi mondatokat (atomic sentences) állítsunk elő. Egy atomi mondatot egy predikátumszimbólum és az azt követő zárójelezett listában található termek listája alkot. Például a

Testvér(Richárd, János)

azt jelenti egy korábban megadott szándékolt interpretáció szerint, hogy Oroszlánszívű Richárd testvére János királynak.^[78] Az atomi mondatoknak is lehetnek összetett termek az argumentumai. Így tehát a

Házas(Apja(Richárd), Anyja(János))

azt jelenti, hogy Oroszlánszívű Richárd apja feleségül vette János király anyját (ismét csak egy alkalmas interpretációban).

Összetett mondatok létrehozásához használhatunk logikai összekötőjeleket (logical connectives) úgy, mint az ítéletkalkulusban. A logikai kötőszavakkal formált mondatok szemantikája azonos az ítéletkalkulusban látott szemantikával. Íme négy mondat, amelyek igazak a 8.2. ábra modelljében, a szándékolt interpretációnk szerint.

¬Testvér(BalLáb(Richárd), János)

Testvér(Richárd, János) ∧ Testvér(János, Richárd)

Király(Richárd) ∨ Király(János)

¬Király(Richárd) ⇒ Király(János)

Ha egyszer létrehoztunk egy objektumokat is tartalmazó logikát, természetes, hogy objektumok egész gyűjteményeire vonatkozó tulajdonságokat is ki akarunk fejezni anélkül, hogy az objektumokat nevük felhasználásával fel kellene sorolni. Ezt a kvantorok (quantifiers) alkalmazása teszi lehetővé. Az elsőrendű logika két standard kvantort tartalmaz, amelyeket univerzális és egzisztenciális kvantoroknak nevezünk.

Univerzális kvantor (∀)

Emlékezzünk vissza arra, hogy a 7. fejezetben milyen nehézségeink voltak általános szabályok ítéletlogikában történő megfogalmazásával. Az olyan szabályok, mint az „A wumpus mellett található négyzetek büdösek” vagy a „Minden király személy” adják meg a savát-borsát az elsőrendű logikának. Az első szabállyal a 8.3. alfejezetben fogunk foglalkozni. A második szabály, „Minden király személy”, az elsőrendű logikában így írható le:

∀x Király(x) ⇒ Személy(x)

A ∀-t általában „Minden …re”-nek olvassuk ki. A mondat tehát azt jelenti: „Minden x-re, ha x egy király, akkor x egy személy.” Az x szimbólum neve változó (variable). A konvenció alapján a változókat kisbetűvel írjuk. Egy változó önmagában egy term, és mint olyan, szerepelhet egy függvény argumentumaként – például: BalLáb(x). Egy változó nélküli termet alaptermnek (ground term) nevezünk.

Egyszerűen a ∀x P mondat, ahol a P egy tetszőleges logikai kifejezés, azt mondja ki, hogy a P igaz minden x objektumra. Pontosabban, ∀x P igaz egy adott modellre az interpretáción belül, ha P igaz minden lehetséges kiterjesztett interpretációban (extended interpretations), amelyet az adott interpretáció felhasználásával hozunk létre, ahol minden egyes kiterjesztett interpretáció meghatároz egy tárgyterületelemet, amire az x vonatkozik.

Ez bonyolultnak hangzik, de valójában csak egy óvatos módja annak, hogy megállapítsuk az univerzális kvantorok intuitív jelentését. Tekintsük a 8.2. ábrát és a hozzá tartozó szándékolt interpretációt. Ötféle módon tudjuk kiterjeszteni az interpretációt:

x ⟶ Oroszlánszívű Richárd

x ⟶ János király

x ⟶ Richárd bal lába

x ⟶ János bal lába

x ⟶ a korona

A ∀x Király(x) ⇒ Személy(x) univerzális kvantort alkalmazó mondat igaz az eredeti interpretációban, ha a Király(x) ⇒ Személy(x) mondat igaz mind az öt kiterjesztett interpretációra. Eszerint az univerzális kvantorral ellátott mondat egyenértékű a következő öt mondattal:

Oroszlánszívű Richárd egy király ⇒ Oroszlánszívű Richárd egy személy

János király egy király ⇒ János király egy személy

Richárd bal lába egy király ⇒ Richárd bal lába egy személy

János bal lába egy király ⇒ János bal lába egy személy

A korona egy király ⇒ a korona egy személy

Nézzük meg alaposan ezt az állításhalmazt. Mivel a mi modellünkben János király az egyetlen király, a második mondat kijelenti, hogy ő egy személy, ahogy azt reméltük is. De mi a helyzet a többi négy mondattal, amelyek azért szerepelnek, hogy állításokat fogalmazzanak meg lábakról és koronákról? Része ez annak a jelentésnek, hogy „Minden király személy”? Valójában, a többi négy állítás is igaz a modellben, de egyáltalán nem állítanak semmit a lábak, koronák vagy akár Richárd személyes tulajdonságairól. Ez azért van, mert ezen objektumok egyike sem király. Ha megnézzük a (⇒) összekötőjel igazságtábláját (7.8. ábra), láthatjuk, hogy az implikáció igaz, amikor a premisszája hamis – tekintet nélkül a konklúzió igazságtartalmára. Így tehát az univerzális kvantorral ellátott mondat kijelentése egyenértékű azzal, hogy egyedi implikációk teljes listáját definiáljuk. Végül is egy szabály konklúzióját adjuk meg azokra az objektumokra, amelyek premisszája igaz, de nem mondunk egyáltalán semmit azokról az egyedekről, akikre nézve a premissza hamis. Így az implikáció igazságtáblájának sorai tökéletesnek bizonyulnak univerzális kvantorokat tartalmazó általános szabályok megírásához.

Gyakori hiba, amelyet még figyelmes olvasók is elkövetnek, akik pedig már többször is elolvasták ezt a bekezdést, hogy konjunkciót használnak implikáció helyett. A

∀x Király(x) ∧ Személy(x)

mondat egyenértékű lenne azzal az állítással, hogy

Oroszlánszívű Richárd egy király ∧ Oroszlánszívű Richárd egy személy

János király egy király ∧ János király egy személy

Richárd bal lába egy király ∧ Richárd bal lába egy személy

és így tovább. Nyilvánvaló, hogy ez nem azt jelenti, mint amit szeretnénk elérni.

Az univerzális kvantor állításokat fogalmaz meg minden objektumról. Hasonlóan, az egzisztenciális kvantor felhasználásához állításokat tehetünk az univerzum néhány objektumáról anélkül, hogy megneveznénk azokat. Azt az állítást tehát, hogy János királynak koronája van, így is leírhatjuk:

∃x Korona(x) ∧ Fején(x, János)

Az ∃x kiolvasása „Létezik egy olyan x…” vagy „Néhány x-re…” .

Érthetően fogalmazva, az ∃x P mondat azt jelenti, hogy a P legalább egy x objektumra igaz. Pontosabban az ∃x P igaz egy adott modellben, egy adott interpretáción belül, ha a P igaz legalább egy kiterjesztett interpretációban, amely az x-et a tartomány egy eleméhez rendeli. A mi példánkban ez azt jelenti, hogy a következő állítások közül legalább egy igaz:

Oroszlánszívű Richárd egy korona ∧ Oroszlánszívű Richárd János fején van

János király egy korona ∧ János király János fején van

Richárd bal lába egy korona ∧ Richárd bal lába János fején van

János bal lába egy korona ∧ János bal lába János fején van

A korona egy korona ∧ a korona János fején van

Az ötödik állítás igaz a modellben, így az eredeti egzisztenciális kvantorral ellátott mondat igaz a modellben. Vegyük észre, hogy definíciónk szerint a mondat igaz lenne egy olyan modellben is, ahol János király két koronát visel. Ez teljes mértékben konzisztens az eredeti mondattal, miszerint „János királynak korona van a fején.”^[79]

Mint ahogy természetesnek tűnik az ⇒ használata összekötőjelnek a ∀ használatakor, az ∧ az a természetes összekötőjel, amit az ∃-vel használunk. Az ∧ használata fő összekötőjelként az ∀-val túlságosan is erős állításokhoz vezetett az előző alfejezetben tárgyalt példában; a ⇒ használata az ∃-vel igazából nagyon gyenge állításhoz vezet:

∃x Korona(x) ⇒ Fején(x, János)

A felszínen ez a mondatunk elfogadható átírásának tűnik. A szemantikát alkalmazva látjuk, hogy a mondat azt jelenti ki, hogy a következő állítások legalább egyike igaz:

Oroszlánszívű Richárd egy korona ⇒ Oroszlánszívű Richárd János fején van

János király egy korona ⇒ János király János fején van

Richárd bal lába egy korona ⇒ Richárd bal lába János fején van

és így tovább. Mármost, egy implikáció akkor igaz, ha a premissza és a konklúzió egyaránt igaz, vagy ha a premisszája hamis. Tehát ha Oroszlánszívű Richárd nem egy korona, akkor az első állítás igaz, és az egzisztenciális kvantort kielégítettük. Így tehát egy egzisztenciális kvantort tartalmazó implikációs mondat igaz bármely olyan modellben, amely tartalmaz egy olyan objektumot, amelyre az implikáció premisszája hamis; következésképpen az ilyen mondatok valójában nem túl sokat mondanak.

Gyakran szükségünk van még összetettebb mondatok kifejezésére, amelyek több kvantort is használnak. A legegyszerűbb eset az, amikor a kvantorok azonos típusúak. Például „A fivérek testvérek” mondat leírható úgy, hogy:

∀x ∀y Fivér(x, y) ⇒ Testvér(x, y)

Az egymást követő azonos típusú kvantorokat írhatjuk úgy is, hogy egy kvantort alkalmazunk az összes változóra. Például hogy azt állítsuk, a testvérség egy szimmetrikus kapcsolat, ezt írhatjuk:

∀x, y Testvér(x, y) ⇔ Testvér(y, x)

Más esetekben kevert jelöléssel van dolgunk. A „mindenki szeret valakit” azt jelenti, hogy minden személyhez tartozik valaki, akit a személy szeret:

∀x ∃y Szeret(x, y)

Másrészt, hogy azt állítsuk: „Van valaki, akit mindenki szeret”, ezt írjuk:

∃y ∀x Szeret(x, y)

A kvantorok sorrendje tehát nagyon fontos. Még világosabbá válik, ha zárójeleket is alkalmazunk. A ∀x (∃y Szeret(x, y)) azt jelenti, hogy mindenkinek van egy bizonyos tulajdonsága, nevezetesen, az a tulajdonság, hogy mindenki szeret valakit. Másrészt, a ∃x (∀y Szeret(x, y)) azt jelenti, hogy a világban valakinek van egy bizonyos tulajdonsága, méghozzá az, hogy mindenki szereti őt.

Zavart okozhat, ha két kvantort használunk ugyanazzal a változó névvel. Tekintsük a következő mondatot:

∀x [Korona(x) ∨ (∃x Fivér(Richárd, x))]

Itt az x a Fivér(Richárd, x)-ben egzisztenciális kvantorral van ellátva. Az a szabály, hogy a változó ahhoz a legbelső kvantorhoz tartozik, ami a változót megemlíti, és utána a változó nem tárgya semmilyen kvantor alárendelésnek.^[80]

A másik módja a megoldásnak: ∃x Fivér(Richárd, x), ahol ez egy Richárdról szóló mondat (hogy neki van egy fivére), és nem pedig az x-ről. Így tehát annak nem lesz hatása, ha kívül elé teszünk egy ∀x-et. Éppen így írhattuk volna azt is, hogy ∃z Fivér(Richárd, z). Mivel ez tévesztés forrása lehet, ezért mindig különböző változókat fogunk használni.

A két kvantor valójában szoros kapcsolatban áll egymással a negáción keresztül. Ha valaki azt mondja, hogy mindenki utálja a paszternákot, akkor egyúttal azt is mondja, hogy nem létezik olyan valaki, aki szereti azt, és fordítva:

∀x ¬Szereti(x, Paszternák) egyenértékű azzal, hogy ¬∃x Szereti(x, Paszternák)

Egy lépéssel tovább is mehetünk. A „Mindenki szereti a fagylaltot” mondat azt jelenti, hogy nincs olyan, aki ne szeretné a fagylaltot:

∀x Szereti(x, Fagylalt) egyenértékű azzal, hogy ¬∃x Szereti(x, Fagylalt)

Mivel az ∀ igazából egy konjunkció minden univerzumbeli objektum felett, az ∃ pedig egy diszjunkció ugyanezen objektumok felett, ezért nem meglepő, hogy eleget tesznek a De Morgan-szabályoknak. A kvantorral és a kvantor nélkül álló mondatokra vonatkozó De Morgan-szabályok a következők:

Így valójában nincs szükségünk egyszerre mind az ∀-ra, mind az ∃-re, mint ahogy nincs szükség egyszerre mind az ∧-ra és az ∨-ra sem. Mégis, mivel az olvashatóság fontosabb, mint a takarékosság, használni fogjuk mindkét kvantort.

Az elsőrendű logika a predikátumok és termek korábban leírt használatán kívül még egy lehetőséget nyújt atomi mondatok készítésére. Alkalmazhatjuk az egyenlőségszimbólumot (equality symbol) állítások készítésére is annak kifejezésére, hogy két term ugyanarra az objektumra vonatkozik. Például az

Apja(János) = Henrik

azt mondja ki, hogy az Apja(János) által hivatkozott objektum és a Henrik által hivatkozott objektum azonos. Mivel az interpretáció rögzíti bármely term referenciáit, egy egyenlőségi állítás igazságának megállapításához elegendő azt látni, hogy a két term referenciái ugyanazok az objektumok.

Az egyenlőségszimbólumot használhatjuk arra, hogy tényeket állapítsunk meg egy adott függvényről, ahogy ezt megtettük az imént az Apja szimbólummal. Alkalmazhatjuk az egyenlőségszimbólumot negációval is, annak a kifejezésére, hogy két term nem ugyanaz az objektum. Ha azt akarjuk állítani, hogy Richárdnak legalább két fivére van, ezt írjuk:

∃x,y Fivér(x, Richárd) ∧ Fivér(y, Richárd) ∧ ¬(x = y)

Annak a mondatnak, hogy

∃x,y Fivér(x, Richárd) ∧ Fivér(y, Richárd)

nem ugyanaz a szándékolt jelentése. Ez a mondat például igaz a 8.2. ábrán látható modellre, ahol Richárdnak csak egy fivére van. Hogy ezt megértsük, figyeljük meg azt a kiterjesztett interpretációt, ahol mind az x, mind az y János királyhoz van rendelve. A ¬(x = y) viszont már nem eleme a modellnek. Az x ≠ y-t néha rövidítésként használjuk a ¬(x = y) kifejezésére.