8.5. Összefoglalás

Ebben a fejezetben megmutattuk, hogy hogyan használható az elsőrendű logika (first-order logic) egy tudásalapú ágens reprezentációs nyelveként. A legfontosabb megállapítások a következők:

  • A tudásreprezentációs nyelveknek deklaratívnak, kompozíciósnak, kifejezőnek, a szövegkörnyezettől függetlennek és egyértelműnek kell lenniük.

  • A logikák különböznek ontológiai és episztemológiai megállapításaikban. Amíg az ítéletlogika megállapításai csak tények létezésére vonatkoznak, addig az elsőrendű logika az objektumok és a relációk létezését is felhasználhatja, így nagyobb kifejezőerővel rendelkezik.

  • Egy lehetséges világot vagy modellt az elsőrendű logikában objektumok egy halmaza definiál, a köztük lévő relációk és a rájuk alkalmazható függvények által.

  • A konstansszimbólumok (constant symbols) objektumokat neveznek meg, a predikátumszimbólumok (predicate symbols) relációkat, míg a függvényszimbólumok (function symbols) függvényeket. Egy interpretáció megadja a leképezést a szimbólumok és a modell között. Az összetett termek (complex terms) függvényszimbólumokat rendelnek hozzá a termekhez, hogy nevet adjanak egy objektumnak. Ha megadunk egy interpretációt és egy modellt, a mondat igazságtartalmát meghatároztuk.

  • Egy atomi mondat (atomic sentence) egy vagy több termre alkalmazott predikátumból áll. A mondat csak akkor igaz, ha a predikátum által megnevezett reláció fennáll a termek által megnevezett objektumok között. Az összetett mondatok (complex sentences) – az ítéletlogikához hasonló módon – összekötőjeleket használnak, a kvantorok (quantifiers) használata pedig lehetővé teszi általános szabályok megfogalmazását is.

  • Egy tudásbázis építése az elsőrendű logikában a tárgyterület alapos elemzését igényli, valamint egy szótár megválasztását és a kívánt következtetések eléréséhez szükséges axiómák kódolását.

8.5.1. Irodalmi és történeti megjegyzések

Habár már Arisztotelész logikája képes volt objektumok feletti általánosítások kezelésére, az igazi elsőrendű logika keletkezését Gottlob Frege Begriffschrift (Fogalmak írása vagy Fogalmi jelölés; Frege, 1879) c. művének megjelenésétől, a kvantorok bevezetésétől számíthatjuk. A Frege-féle képesség a kvantorok egymásba ágyazása jelentős előrelépést jelentett, de az általa alkalmazott jelölésrendszer igen körülményes volt. Az elsőrendű logika jelenlegi jelölésrendszere alapvetően Giuseppe Peanótól származik (Peano, 1889), a szemantika azonban megegyezik a Frege által bemutatottal. Eléggé különös, hogy Peano axiómái nagyrészt Grassmann-nak (Grassmann, 1861) és Dedekindnek (Dedekind, 1888) voltak köszönhetők.

Az elsőrendű logika fejlődésének fontos akadálya volt az egyváltozós predikátumok előtérbe helyezése, illetve a többváltozós predikátumok kizárása. Az egyváltozós predikátumokhoz való ragaszkodás általánosan jellemző volt a logikai rendszerekre Arisztotelésztől Boole-ig. A logikai relációk első rendszerezett leírását Augustus De Morgan adta (De Morgan, 1864). De Morgan a következő példával mutatta be az arisztotelészi logikával nem kezelhető következtetéseket: „Minden ló állat; ezért a ló feje egy állat feje”. Ez a következtetés nem valósítható meg az arisztotelészi rendszerrel, mert bármely, a következtetésben alkalmazható szabálynak először az „x a feje y-nak” két predikátumot tartalmazó mondatot kell elemeznie. A relációk logikáját alaposan tanulmányozta Charles Sanders Peirce (Peirce, 1870), aki Frege-től függetlenül, néhány évvel később szintén kifejlesztette az elsőrendű logikát (Peirce, 1883).

Leopold Löwenheim adta meg a modellelmélet rendszerezett leírását az elsőrendű logika számára (Löwenheim, 1915). Cikke az egyenlőségszimbólumot már a logika szerves részének tekinti. Löwenheim eredményeit Thoralf Skolem fejlesztette tovább (Skolem, 1920). Alfred Tarski a halmazelméletet felhasználva megadta az igazság és a modellelméleti kielégíthetőség explicit definícióját (Tarski, 1935, 1956).

Elsősorban McCarthy érdeme az elsőrendű logika alkalmazása az MI-rendszerek eszközeként (McCarthy, 1958). A logikán alapuló MI-rendszerek fejlődésében jelentős előrelépést jelentett Robinson rezolúciós algoritmusa (Robinson, 1965), ami egy komplett elsőrendű logikai következtetési folyamat. A rezolúciót a 9. fejezetben fogjuk tárgyalni. A logikai megközelítés alapjaival a Stanfordon sok eredményt értek el. Cordell Green kifejlesztett egy elsőrendű logikai következtetési rendszert, a QA3-at (Green, 1969a, 1969b), amely ahhoz vezetett, hogy először kíséreltek meg létrehozni egy logikai robotot a Stanford Research Institute-ban (Fikes és Nilsson, 1971). Az elsőrendű logikát Zohar Manna és Richard Waldinger alkalmazta a programokban való következtetésre (Manna és Waldinger, 1971), majd később Michael Genesereth az áramkörökhöz (Genesereth, 1984). Európában a logikai programozást – az elsőrendű következtetés korlátozott változatát – fejlesztették ki a nyelvészeti elemzésekhez (Colmerauer és társai, 1973) és általános deklaratív rendszerekhez (Kowalski, 1974). A számítógépes logikával Edinburgh-ban sikeresen foglalkoztak, az LCF (Számítási Funkciók Logikája) projekten keresztül (Gordon és társai, 1979). Ezeket a fejlesztéseket a 9. és 10. fejezetben követjük nyomon.

Számos színvonalas, az elsőrendű logika korszerű bevezetését adó írás ismert. Ezek közül Quine műve az egyik legjobban áttekinthető (Quine, 1982). Enderton írása inkább matematikai megközelítést követ (Enderton, 1972). Bell és Machover erősen formális leírást készített az elsőrendű logikáról, és ezzel együtt számos bonyolult, a logika tárgyterületébe tartozó témáról (Bell és Machover, 1977). Manna és Waldinger a számítástechnika oldaláról közelítő, jól olvasható bevezetést készített (Manna és Waldinger, 1985). Gallier az elsőrendű logika rendkívül precíz matematikai bemutatását adta meg, együtt a logika automatikus következtetésre történő alkalmazásának részletes tárgyalásával (Gallier, 1986). A Logical Foundations of Artificial Intelligence (A mesterséges intelligencia logikai alapjai) (Genesereth és Nilsson, 1987) c. könyv a logika alapos bemutatásán kívül az érzeteket és cselekvéseket kezelő logikai ágensek első rendszerezett bevezetését nyújtja.

8.5.2. Feladatok

8.1.

Egy logikai tudásbázis a világot mondatokkal reprezentálja határozott struktúra nélkül. Egy analóg (analog) reprezentáció viszont strukturált, ahol a leírás struktúrája közvetlenül megfelel a reprezentált dolog struktúrájának. Tekintsük egy ország autótérképét mint az országról ismert tények egy részének analóg reprezentációját. A térkép kétdimenziós felépítése megfelel a terület kétdimenziós felszínének.

  1. Adjon öt példát a térképnyelv szimbólumaira.

  2. Explicit mondatnak nevezzük az olyan mondatot, amelyet a reprezentáció létrehozója közvetlenül leír. Az implicit mondatok az explicit mondatokból keletkeznek az analóg reprezentáció tulajdonságai szerint. Adjon három példát a térképnyelv implicit és explicit mondataira.

  3. Adjon az ország fizikai struktúráját leíró tényekre három olyan példát, amely nem reprezentálható a térképnyelvvel.

  4. Adjon két példát olyan tényekre, amelyek egyszerűbben kifejezhetők a térképnyelvvel, mint az elsőrendű logikával.

  5. Adjon még két példát analóg reprezentációkra. Melyek az előnyei és a hátrányai ezeknek a nyelveknek?

8.2.

Tekintsünk egy tudásbázist, amely csak két kijelentést tartalmaz: P(a) és P(b). Ebből a tudásbázisból következik-e az ∀x P(x)? Magyarázza meg válaszát modellek segítségével.

8.3.

Érvényes-e a következő mondat: ∃x, y x = y? Magyarázza meg.

8.4.

Írjon le egy olyan logikai mondatot, hogy minden olyan világban, ahol ez a mondat igaz, pontosan csak egy objektum legyen.

8.5.

Tekintsünk egy szimbólumszótárat, amely tartalmaz egy c konstansszimbólumot, pk predikátumszimbólumokat minden egyes k értékre és függvényszimbólumokat minden egyes k értékhez, ahol 1 ≤ k ≤ A. A tárgyterület méretét rögzítsük D-ben. Bármely adott interpretációmodell-kombinációban minden egyes predikátum vagy függvény hozzá van rendelve az ugyanazon értékhez tartozó relációhoz vagy függvényhez. Feltételezhetjük, hogy a modellben szereplő függvények lehetővé teszik, hogy néhány bemenetnek ne legyen értéke a függvény számára (vagyis, hogy az érték a láthatatlan objektum). Vezessen le egy formulát a lehetséges interpretációmodell-kombinációk számának megállapítására a D elemet tartalmazó tárgyterületben. Ne riassza meg, ha el kell távolítania a felesleges kombinációkat.

8.6.

Reprezentálja a következő mondatokat az elsőrendű logikában úgy, hogy egy következetes szótárt használ (amelyet előzőleg definiálnia kell):

  1. Néhány diák felvette a franciát 2001 tavaszi félévében.

  2. Minden diák, aki felveszi a franciát, átmegy a vizsgán.

  3. Csak egy diák vette fel a görögöt 2001 tavaszi félévében.

  4. A görögben elért legmagasabb pontszám mindig magasabb a franciában elért legmagasabbnál.

  5. Minden személy okos, aki biztosítást köt.

  6. Senki nem köt drága biztosítást.

  7. Van egy ügynök, aki csak azokkal köt biztosítást, akiknek még nincs kötvényük.

  8. Van egy borbély, aki minden férfit megborotvál a városban, aki nem borotválkozik.

  9. Az a személy, aki az Egyesült Királyságban születik, és akinek mindkét szülője brit állampolgár vagy ottani lakos, születésénél fogva brit állampolgár.

  10. Az a személy, aki az Egyesült Királyságon kívül születik, és egyik szülője született brit állampolgár, az származása alapján brit állampolgár.

  11. A politikusok bármikor bolonddá tehetnek néhány embert, és minden embert bolonddá tehetnek egy kis időre, de nem tehetnek bolonddá mindenkit örökre.

8.7.

Reprezentálja a „Minden német azonos nyelvet beszél” mondatot predikátumkalkulusban. Használja a Beszél(x, l) predikátumot, amely jelentse azt, hogy x az l nyelvet beszéli.

8.8.

Milyen axiómára van szükségünk, hogy ezt a tény kikövetkeztessük: Nő(Laura), ha adottak a tények: Férfi(Jim) és Házastársak(Jim, Laura)?

8.9.

Írjon egy általános tény- és axiómahalmazt, hogy reprezentálja a következő állítást: „Wellington hallott Napóleon haláláról”; és hogy helyesen megválaszolhassuk a kérdést: „Hallott Napóleon Wellington haláláról?”.

8.10.

Írja át a 7.5. alfejezetben bemutatott ítéletlogikai wumpus világ tényeit elsőrendű logikába. Mennyivel tömörebb ez a változat?

8.11.

Készítsen axiómákat, amelyek leírják a következő predikátumokat: Unokája, Dédnagyapja, Fivére, Húga, Lánya, Fia, Nagynénje, Nagybátyja, Sógornője, Sógora, Unokatestvére.

Írja le a 8.5. ábrán látható családfa tényeit. Használjon logikai következtető rendszert, és minden leírt mondat legyen a következtető rendszer számára KIJELENT-ve, és KÉRDEZ-ze meg, hogy ki Erzsébet unokája, ki Diana unokabátyja és kik Zara dédszülei.

8.12.

Írjon le egy mondatot, amely azt állítja, hogy a + egy kommutatív funkció. Következik ez a mondat Peano axiómáiból? Ha igen, magyarázza meg, hogy miért, ha nem, adjon meg egy modellt, amelyben az axiómák igazak, az Ön mondata pedig hamis.

8.13.

Magyarázza meg, mi a hibás az ∈ halmaz tagság predikátum következő javasolt definíciójával:

∀x, s x ∈ {x∣s}

∀x, s x ∈ s ⇒ ∀y x ∈ {y∣s}

8.14.

A halmazaxiómákat példaként használva, készítsen axiómákat a listák tárgyterületére, amelyek tartalmazzák a korábban a fejezetben említett összes konstanst, függvényt és predikátumot.

8.15.

Magyarázza meg, hogy mi a hiba a következő ajánlott definícióban a szomszédos négyzetekre a wumpus világban:

∀x, s Szomszédos([x, y], [x + 1, y]) ∧ Szomszédos([x, y], [x, y + 1])

8.5. ábra - Egy tipikus családfa. Az „=” szimbólum a házastársakat köti össze, a nyilak a gyerekekre mutatnak.
Egy tipikus családfa. Az „=” szimbólum a házastársakat köti össze, a nyilak a gyerekekre mutatnak.

8.16.

Írja meg a wumpus helyzetének meghatározásához szükséges axiómákat a Wumpus konstansszimbólum és a Be(Wumpus, Helyzet) bináris predikátum felhasználásával. Ne felejtse el, hogy csak egy wumpus van.

8.17.

Bővítse ki a 8.4. alfejezetben leírt szótárt úgy, hogy definiálja az összeadást az n-bites bináris számokra. Ezután kódolja a 8.6. ábrán látható négybites összeadó leírását, és tegye fel azokat a kérdéseket, amelyek szükségesek ahhoz, hogy igazoljuk összeadó-helyességét.

8.18.

A fejezetben az áramkör reprezentálása részletesebb a szükségesnél, ha csak az áramkör működése érdekel minket. Egy egyszerűbb formula bármely m bemenetű, n kimenetű kaput vagy áramkört leír, egy m + n argumentumos predikátum használatával, úgy, hogy a predikátum pontosan akkor igaz, amikor a bemenet és a kimenet konzisztens. Például, a NOT-kapukat így írjuk le: NOT(i, o), amelynél a NOT(0, 1)-et és a NOT(1, 0)-át ismerjük. A kapuk összeállítása a kapupredikátumok összekötésével van definiálva, amelyben a közös változók direkt összeköttetéseket jeleznek. Például egy NAND áramkört összeállíthatunk AND-ekből és NOT-okból:

∀i1, i2, oa, o NAND(i1, i2, o) ⇐ AND(i1, i2, o) ∧ NOT(oa, o)

Ezt a reprezentációt felhasználva definiálja a 8.4. ábrán látható egybites összeadót és a 8.6. ábra négybites összeadóját, és magyarázza meg, milyen lekérdezéseket használna, hogy igazolja a megoldásokat. Milyen fajta lekérdezéseket nem fogad el ez a reprezentáció, amelyeket pedig a 8.4. alfejezetben lévő reprezentáció elfogadott?

8.6. ábra - Egy négybites összeadó
Egy négybites összeadó

8.19.

Kérjen útlevéligénylő lapot az Ön saját országába, nevezze meg azokat a szabályokat, amelyek az igénylés jogosultságát meghatározzák, és fordítsa le az elsőrendű logika nyelvére a 8.4. alfejezetben felvázolt lépéseket követve.

fel