7.3. A logika
Ez az alfejezet áttekintést nyújt a logikai reprezentáció és következtetés alapvető fogalmairól. A logika bármely speciális formájára vonatkozó technikai részletek bemutatását a következő fejezetre halasztjuk. Ehelyett egyszerű példákat fogunk használni a wumpus világból vagy ismerős aritmetikai területekről. Azért választjuk ezt az igen rendhagyó megközelítést, mivel a logika fogalmai messze általánosabbak és szebbek, mint azt általában feltételezik.
A 7.1. fejezetben említettük, hogy a tudásbázis mondatokból áll. Ezeket a mondatokat a reprezentációs nyelv szintaxisa (syntax) szerint fejezzük ki, amely specifikálja az összes jól formált, nyelvtanilag helyes mondatot. A szintaxis fogalma elég tiszta a szokásos aritmetikai műveleteknél: „x + y = 4” egy jól formált mondat, míg az „x2y + =” nem az. A logikai nyelvek szintaxisait (és a matematikáét is egyébként) rendszerint cikkek és könyvek írása céljából tervezték. A szó szoros értelmében tucatjai léteznek a különböző szintaxisoknak, néhány tele görög betűkkel és egzotikus matematikai szimbólumokkal, néhány inkább vizuálisan követhető, nyilakat és buborékokat tartalmazó diagramokból áll. Minden esetben azonban, az ágens tudásbázisában a mondatok az ágensnek magának vagy az ágens egy részének valódi fizikai konfigurációi. A következtetés ezeknek a konfigurációknak a létrehozását vagy manipulálását fogja jelenteni.
A logikának a nyelv szemantikáját (semantics) is definiálnia kell. Egyszerűen fogalmazva a szemantika a mondatok „jelentéséről” szól. A logikában a definíció pontosabb. A nyelv szemantikája definiálja minden mondat igazságát (truth) minden egyes lehetséges világra (possible world) vonatkozóan. Például egy szokásos aritmetikához választott szemantika meghatározza, hogy az „x + y = 4” mondat igaz abban a világban, ahol x értéke 2 és y értéke 2, de hamis abban a világban, ahol x értéke 1 és y értéke is 1.[60] A standard logikákban minden mondat vagy igaz, vagy hamis minden lehetséges világban, és nem lehet „valahol az igaz és hamis között”[61].
Amikor szükséges, hogy pontosak legyünk, a modell (model) kifejezést fogjuk használni a „lehetséges világ” helyén. (Szintén használni fogjuk az „m modellje α-nak” kifejezést, ami azt jelenti, hogy az α mondat igaz az m modellben.) Miután a lehetséges világokat úgy képzelhetjük el, mint (potenciálisan) valós környezeteket, amelyekben az ágens ott lehet vagy nem lehet ott, a modellek olyan matematikai absztrakciók, amelyek csak rögzítik az igazság vagy hamisság értékét minden releváns mondatnak. Például, tegyük fel, hogy x és y a férfiak és nők száma, akik egy kártyaasztal körül ülnek és bridzset játszanak, és az x + y = 4 mondat igaz, amikor négyen vannak összesen. Formálisan, a lehetséges modellek nem mások, mint minden lehetséges hozzárendelés az x és y változókhoz. Minden ilyen hozzárendelés bármely olyan aritmetikai mondat igazságát rögzíti, amely az x és y változókat tartalmazza.
Most, hogy van egy képünk az igazság fogalmáról, tudunk beszélni a logikai következtetésről. Ennek része a mondatok közötti logikai vonzat (entailment) reláció, annak kifejezése, hogy egy mondat logikusan következik egy másik mondatból. Matematikai jelöléssel ezt így írjuk:
α ⊨ β
aminek jelentése, hogy az α mondat maga után vonzza a β mondatot. A vonzat formális definíciója a következő: α ⊨ β akkor és csakis akkor, ha minden modellben, amelyben α igaz, β szintén igaz. Közvetlenebbül azt mondhatjuk, hogy β igazságát „tartalmazza” α igazsága. A vonzat reláció ismerős az aritmetikából is, örömmel vehetjük észre, hogy az x + y = 4 mondat maga után vonzza a 4 = x + y mondatot. Nyilvánvaló, hogy bármely modellben, ahol x + y = 4, mint például az a modell, amelyben x és y is 2 értékű, a 4 = x + y is fenn áll. Hamarosan látni fogjuk, hogy a tudásbázist tekinthetjük egy kijelentésnek, és gyakran beszélhetünk arról, hogy egy tudásbázis maga után vonz egy mondatot.
Alkalmazhatunk hasonló elemzést az előző részben bemutatott wumpus világbeli következtetési példára is. Tekintsük a 7.3. (b) ábrán látható szituációt: az ágens nem észlelt semmit az [1, 1]-ben és szellőt észlelt a [2, 1]-ben. Ezek az érzetek, kombinálva az ágensnek a wumpus világ szabályaira vonatkozó tudásával (7.1. szakasz - A tudásbázisú ágens részben található TKCSÉ-leírás), alkotja a TB-t. Az ágenst (más dolgok mellett) az érdekli, hogy vajon a szomszédos [1, 2], [2, 2], [3, 1] négyzetek tartalmaznak-e csapdát. Bármelyik a három négyzet közül tartalmazhat vagy éppen nem tartalmaz csapdát, így a példa esetében 23 = 8 lehetséges modell létezik. Ezt mutatja a 7.5. ábra.[62]
A TB hamis azokban a modellekben, amelyek ellentmondanak annak, amit az ágens tud. Például a TB hamis minden modellben, ahol az [1, 2] tartalmaz csapdát, mivel nincs szellő az [1, 1]-ben. Valójában csak három olyan modell van, amelyben a TB igaz, ezeket a 7.5. ábra a modellek egy részhalmazaként mutatja. Most tekintsünk két lehetséges következményt:
α1 = „Nincs csapda az [1, 2]-ben”
α2 = „Nincs csapda a [2, 2]-ben”
A 7.5. ábrán megjelöltük az α 1 és α 2 modelleket. Szemrevételezve megállapíthatjuk a következőt:
minden olyan modellben, ahol a TB igaz, ott α1 is igaz.
Így TB ⊭ α1, és nincs csapda az [1, 2]-ben. Azt is láthatjuk, hogy:
néhány modell, amelyben a TB igaz, az α2 hamis.
Így TB ⊭ α2 és az ágens nem tudja kikövetkeztetni, hogy nincs csapda a [2, 2]-ben. (És azt sem tudja kikövetkeztetni, hogy van csapda a [2, 2]-ben.)[63]
Az előző példa nem csak illusztrálja a maga után vonzást, hanem megmutatja, hogy a vonzat definícióját fel lehet használni a következmények levezetésére, azaz, hogy logikai következtetést (logical inference) végezzünk. A 7.5. ábrán illusztrált következtetési algoritmust modellellenőrzésnek (model checking) hívjuk, mivel számba vesz minden lehetséges modellt annak megvizsgálására, hogy α igaz-e minden modellben, amelyben a TB igaz.
![Lehetséges modelljei a csapda jelenlétének az [1, 2], [2, 2] és [3, 1]-ben, ha adott a megfigyelés, hogy az [1, 1]-ben semmi és a [2, 1]-ben szellő érezhető. (a) A tudásbázis és α1(nincs csapda[1, 2]-ben) modelljei. (b) A tudásbázis és α2(nincs csapda[2, 2]-ben) modelljei.](/sites/default/files/fejezetek/6138/zip/kepek/07-05.png)
A vonzat és a bizonyítás megértésében segíthet, ha a TB összes következményeit egy szénakazalnak, az α-t pedig egy gombostűnek képzeljük el. A vonzat olyan, mintha a gombostű benne volna a kazalban; a bizonyítás pedig nem más, mint megpróbálni megtalálni ezt a tűt. Ez a különbségtétel formálisan a következő megfogalmazásban ölt testet: ha egy i következtetési algoritmus képes levezetni α-t a TB-ből, akkor írhatjuk, hogy
TB ⊦iα
amely kimondva: „α az i által levezethető TB-ből” vagy „i levezeti α-t a TB-ből”.
Egy következtetési eljárást, amely csak vonzat mondatokat vezet le, helyesnek (sound) vagy igazságtartónak (truth-preserving) nevezzük. A helyesség egy igencsak kívánatos tulajdonság. Egy nem helyes következtetési eljárás kitalál olyan dolgokat ahogy előrehalad, olyan tűk megtalálását jelenti be, amelyek nem is léteznek. Egyszerű belátni, hogy a modellellenőrzés, ha alkalmazható,[64] akkor helyes eljárás.
A teljesség (completeness) tulajdonság szintén kívánatos: egy következtetési eljárás teljes, ha képes levezetni minden vonzatmondatot. Valódi szénakazlak esetében, amelyek véges méretűek, nyilvánvalónak tűnik, hogy szisztematikus kutatással mindig eldönthető, hogy a tű a kazalban van-e. Sok tudásbázis esetében azonban a konzekvenciák szénakazlának mérete végtelen, és így a teljesség egy fontos kérdéssé válik.[65] Szerencsére léteznek teljes következtetési eljárások a logikához, amelyek megfelelően kifejezők ahhoz, hogy számos tudásbázist kezeljenek.
Fontos
Egy olyan következtetési folyamatot írtunk le, amelynek következményei bármely világban garantáltan igazak, ahol a premisszák is igazak. Nevezetesen, ha a TB igaz a valódi világban, akkor bármely, a TB-ből helyes következtetési eljárással levezetett α mondat szintén igaz a valódi világban. Így, míg a következtetési folyamat a „szintaxison” működik – belső fizikai konfigurációkon, mint például regiszterek bitjein vagy az agy elektromos jelzéseinek mintáin –, addig a folyamat megfelel valódi világ viszonyainak. Ennek megfelelően a valódi világ néhány aspektusa lesz az eset,[66] mivel a valódi világ bizonyos más aspektusai jelenleg képezik az esetet. Ezt a megfeleltetést a világ és a reprezentáció között mutatja a 7.6. ábra.
Fontos
Az utolsó kérdés, amivel foglalkoznunk kell a logikai ágensek tárgyalásánál, a megalapozottság (grounding) kérdése, ami nem más, mint a kapcsolat, ha egyáltalán létezik ilyen, a logikai következtetési folyamat és a valódi környezet között, amelyben az ágens létezik. Nevezetesen hogyan tudhatjuk meg, hogy a TB igaz-e a valódi világban? (Ezután a TB már csak „szintaxis” az ágens fejében.) Ez egy filozófiai kérdés, amelyről sok-sok könyvet írtak (lásd 26. fejezet). Egy egyszerű válasz az, hogy az ágens érzékelői létesítik a kapcsolatot. Például a mi wumpus világbeli ágensünknek van egy szagló érzékelője. Az ágensprogram létrehoz egy megfelelő mondatot mindig, ha van illat. Így bármikor, ha ez a mondat a tudásbázisban van, ez igaz a valódi világban is. Ezáltal az érzetmondatok jelentését és igazságát az őket létrehozó érzékelő és mondatkonstruáló folyamatok határozzák meg. És mi a teendő az ágens tudásának egyéb részeivel, mint az a meggyőződése, hogy a wumpus rossz illatot terjeszt a szomszédos négyzetekben? Ez nem egy közvetlen reprezentációja egy egyedi érzetnek, hanem egy általános szabály, például érzékelési tapasztalatokból levezetve, de nem azonos magával a tapasztalatnak a kijelentésével. Az ilyen általános szabályokat a tanulásnak (learning) nevezett mondatkonstruáló folyamat hozza létre, ami a VI. résznek a tárgya. A tanulás nem tévedhetetlen. Lehet, hogy az eset az, hogy a wumpusok mindig rossz illatot árasztanak, kivéve szökőévekben február 29-én, amikor egyébként megfürödnek. Így lehet, hogy a TB nem igaz a valódi világban, de jó tanuló eljárásokkal van ok az optimizmusra.
7.4. Az ítéletkalkulus: egy nagyon egyszerű logika
Most egy nagyon egyszerű logikát, az ítéletkalkulust (propositional logic) mutatjuk be.[67]Áttekintjük az ítéletkalkulus szintaxisát, majd a szemantikáját – annak a módját, ahogy a mondatok igazságát meghatározzuk. Azután megnézzük a maga után vonzást – a relációt egy adott mondat és azon mondat között, amelyik az előbbiből következik –, és megnézzük, hogy hogyan vezet ez egy egyszerű logikai következtetés algoritmushoz. Mindez természetesen a wumpus világban fog lejátszódni.
Az ítéletkalkulus szintaxisa meghatározza a lehetséges mondatokat. Az atomi mondatok (atomic sentences) – oszthatatlan szintaktikai elemek – egyetlen ítéletszimbólumból (proposition symbol) állnak. Minden ilyen szimbólum egy kijelentés, ami igaz vagy hamis lehet. Nagybetűs neveket fogunk használni a szimbólumok jelölésére: P, Q, R és így tovább. A nevek tetszőlegesek, de gyakran úgy választjuk őket, hogy a nevek bizonyos jelentéssel is rendelkezzenek. Például használhatjuk a W1,3-t annak az állításnak a kifejezésére, hogy a wumpus az [1, 3]-ban van. (Ne felejtsük el, hogy a W1,3 atomi, így a W, az 1 és a 3 nem jelentéssel bíró részei a szimbólumnak.) Létezik két ítéletszimbólum, amelyeknek rögzített az értelmezése: az Igaz egy mindig igaz állítás, és a Hamis egy mindig hamis állítás.
Összetett mondatok (complex sentences) létrehozhatók egyszerűbb mondatokból logikai összekötőjelek (logical connectives) felhasználásával. Öt elterjedten használt összekötőjel van:
¬ (nem). Egy mondatot, mint a ¬W1,3-t, negációnak (negation) nevezünk. Egy literál (literal) vagy egy atomi mondat (egy pozitív literál), vagy egy negált atomi mondat (egy negatív literál).
∧ (és). Egy mondatot, amelynek fő kötőszava a ∧, mint például a W1,3 ∧ C1,3konjunkció-nak (conjunction) nevezünk; ennek részei a konjunktok (conjuncts). (Az ∧ jel hasonlít egy A-ra, az angol And (és) szóból.)
∨ (vagy). Egy mondat, amely használja a ∨ összekötőjelet, mint a (W1,3 ∧ C1,3) ∨ W2,2 egy diszjunkció (disjunction), méghozzá a (W1,3 ∧ C1,3) és a W2,2 diszjunktoknak (disjuncts) a diszjunkciója. (Történelmileg a ∨ jel a latin vel kifejezésből származik, ami „vagy”-ot jelent. A legtöbb ember számára könnyebb megjegyezni úgy, mint egy fejjel lefelé álló és jelet, vagy a magyar olvasók számára, mint a vagy szó első betűjét.)
⇒(implikáció). Egy mondatot, mint amilyen a (W1,3 ∧ C1,3) ⇒ ¬W2,2implikációnak (implication) (vagy feltételes mondatnak) nevezünk. Ennek premisszája (premise) vagy előzménye (antecedent) a (W1,3 ∧ C1,3), konklúziója (conclusion) vagy következménye (consequent) pedig a ¬W2,2 implikáció szabályként (rule) vagy ha–akkor (if–then) állításként is ismert. Az implikációt más könyvekben időnként a ⊃ vagy a → szimbólumokkal jelölik.
⇔ (akkor és csakis akkor). A W1,3 ⇔¬W2,2 mondat egy ekvivalencia (biconditional).
A 7.7. ábra mutatja az ítéletkalkulus formális nyelvtanát; ha nem ismeri a BNF jelölésrendszert, akkor nézze meg az 1. szakasz - B1. Nyelvek definiálása Backus–Naur-Formában (BNF) részt.
Vegyük észre, hogy a nyelvtan nagyon szigorú a zárójelezésnél: minden mondatot, amelyet bináris összekötőjellel hozunk létre, zárójelek közé kell tenni. Ez biztosítja, hogy a szintaxis teljesen egyértelmű. Ez azt is jelenti például, hogy ((A ∧ B) ⇒ C)-t kell írjunk A ∧ B ⇒ C helyett. Az olvashatóság javítása céljából gyakran elhagyjuk a zárójeleket, megbízva ehelyett az összekötőjeleknek egy precedencia-sorrendjében. Ez hasonló az aritmetikában alkalmazott precedenciához – például az ab + c-t ((ab) + c)-nek olvassuk, és nem a(b + c)-nek, mert a szorzásnak magasabb a precedenciája, mint az összeadásnak. Az ítéletkalkulus precedencia-sorrendje (a legmagasabbtól a legalacsonyabb felé: ¬, ∧, ∨, ⇒ és ⇔. Így a mondat:
¬P ∨ Q ∧ R ⇒ S
ekvivalens a következő mondattal:
((¬P) ∨ (Q ∧ R)) ⇒ S
A precedencia nem oldja fel a többértelműséget az olyan mondatoknál, mint az A ∧ B ∧ C, amelyet olvashatunk ((A ∧ B) ∧ C)-ként vagy (A ∧ (B ∧ C))-nek. Mivel a mondatnak ez a két olvasása ugyanazt jelenti a következő részben definiálandó szemantika szerint, az olyan mondatok, mint az A ∧ B ∧ C megengedettek. Szintén megengedjük az A ∨ B ∨ C és az A ⇔ B ⇔C mondatokat. Olyan mondatok, mint az A ⇒ B ⇒ C nem megengedettek, mert a két olvasásnak különböző jelentései vannak, ebben az esetben ragaszkodunk a zárójelhez. Végül, néha használni fogunk szögletes zárójelet az egyszerű zárójel helyett, ami a mondatot áttekinthetőbbé teszi majd.
Most, hogy specifikáltuk az ítéletkalkulus szintaxisát, definiáljuk a szemantikáját is. A szemantika definiálja a szabályokat, amivel meghatározható a mondat igazsága egy bizonyos modellben. Az ítéletkalkulusban a modell egyszerűen az igazságértéket – igaz vagy hamis – rögzíti minden ítéletszimbólumra. Például ha a tudásbázis mondatai a C1,2, C2,2 és C3,1 ítéletszimbólumokat használják fel, akkor egy lehetséges modell:
m1 ={C1,2 = hamis, C2,2 = hamis, C3,1 = igaz}
Három ítéletszimbólum esetén 23 = 8 lehetséges modell van – pontosan azok, amelyek a 7.5. ábrán vannak feltüntetve. Vegyük észre azonban, hogy miután elköteleztük magunkat egy szintaxis mellett, a modellek tisztán matematikai objektumokká váltak, amelyeknek nem feltétlenül van kapcsolatuk a wumpus világgal. A C1,2 csak egy szimbólum, jelentheti azt, hogy „csapda van az [1, 2]-ben” vagy azt, hogy „Párizsban vagyok ma és holnap”.
Az ítéletkalkulus szemantikájának meg kell határoznia, hogyan számítsuk ki bármely mondat igazságértékét egy adott modellben. Ez rekurzívan történik. Minden mondat atomi mondatokból és az ötféle összekötőjelből lett létrehozva, így meg kell határoznunk, hogy hogyan számítsuk ki az atomi mondatok igazságát, és meg kell határoznunk azt is, hogy hogyan számítsuk ki az igazságát az egyes összekötőjelek felhasználásával formált összetett mondatnak. Az atomi mondatok esete egyszerű:
-
Igaz minden modellben igaz, és Hamis ha minden modellben hamis.
-
Minden más ítéletszimbólumnak az igazságértékét közvetlenül a modellben kell meghatározni. Például a korábban megadott m1 modellben a C1,2 hamis.
Összetett mondatokra olyan szabályaink vannak, mint
-
Bármely s mondatra és bármely m modellre, a ¬s mondat az m-ben akkor és csakis akkor igaz, ha s hamis m-ben.
Az ilyen szabályok visszavezetik az összetett mondatok igazságának eldöntését egyszerűbb mondatokra. Minden összekötőjelre vonatkozó szabály összefoglalható egy igazságtáblában (truth table), amely meghatározza egy összetett mondat igazságértékét a mondat komponenseinek minden lehetséges igazságérték hozzárendeléseihez. Az öt logikai összekötőjel igazságtábláját mutatja a 7.8. ábra. Ilyen táblák felhasználásával bármely s mondat igazságértéke egy m modellre vonatkozóan kiszámolható rekurzív kiértékelések egyszerű folyamatával. Például a ¬C1,2 ∧ (C2,2 ∨ C3,1) mondatot kiértékelve m1-ben igaz ∧ (hamis ∨ igaz) = igaz ∧ igaz = igaz értéket kapunk. A 7.3. feladat azt kéri, hogy írjon egy IK-IGAZ? (s,m) algoritmust, amely kiszámítja az s ítéletkalkulus mondatnak az igazságértékét egy m modellben.
Korábban azt mondtuk, hogy a tudásbázist mondatok halmaza alkotja. Most láthatjuk, hogy egy logikai tudásbázis ilyen mondatok konjunkciója. Tehát ha egy üres TB-vel kezdünk, és végrehajtjuk a KIJELENT(TB, S1), ..., KIJELENT (TB, Sn) műveleteket, akkor a TB = S1 ∧ …∧ Sn áll elő. Ez azt jelenti, hogy tudásbázisokat és mondatokat egymással felcserélhetően használhatunk.
Az „és”, „vagy” és „nem” igazságtáblái eltérnek attól, amit a természetes nyelvi jelentésük alapján gondolnánk. A lehetséges félreértés legszembetűnőbb pontja, hogy a P ∨ Q kifejezés igaz akkor is, ha mind P, mind Q is igaz. Létezik másik összekötőjel is, a „kizáró vagy”-nak nevezett jel (röviden xor), amely hamisat ad, ha mindkét diszjunkt igaz.[68] Nincs általános egyetértés az „exkluzív vagy” szimbólumát illetően; két jelölés is ismert: 
Az implikáció (⇒) igazságtáblája rejtélyesnek tűnhet első látásra, mivel nem teljesen illeszkedik ösztönös megértésünkhöz, hogy „P implikálja Q-t” vagy „ha P, akkor Q”. Az ítéletkalkulus nem kíván semmilyen ok-okozati relációt vagy relevanciát P és Q között. A mondat: „az a tény, hogy 5 páratlan implikálja, hogy Tokió Japán fővárosa” az ítéletkalkulusnak egy igaz mondata (a normális interpretáció szerint), még akkor is, ha ez határozottan furcsa mondatnak tűnik. Egy másik esete a félreértéseknek, hogy bármely implikáció igaz, ha az előzménye hamis. Például az „az az állítás, hogy 5 páros szám, implikálja, hogy Samu okos” mondat igaz, függetlenül attól, hogy Samu okos-e. Ez bizarrnak tűnik, de elfogadható, ha a „P ⇒ Q”-t úgy értelmezzük, hogy „ha P igaz, akkor azt állítom, hogy Q is igaz. Egyébként nem állítok semmit”. Az egyetlen eset, amikor ez a mondat hamis, ha P igaz, de Q hamis.
A P ⇔ Q ekvivalencia igazságtáblája azt mutatja, hogy akkor igaz, ha mind P ⇒ Q és Q ⇒ P igaz. Ezt gyakran úgy írjuk le, hogy „P akkor és csakis akkor, ha Q” vagy matematikában szokták jelölni „P aa Q”-nak. A wumpus világ szabályait legjobban az ⇔ használatával tudjuk felírni. Például, egy négyzet szellős, ha a szomszédos, ha a szomszédos négyzetben csapda van, és egy négyzet csakis akkor szellős négyzetben csapda van. Így ekvivalenciákra van szükségünk, mint a
S1,1 ⇔ (C1,2 ∨ C2,1)
ahol S1,1 jelenti, hogy szellő van az [1, 1]-ben. Vegyük észre, hogy az egyirányú implikáció
S1,1 ⇒ (C1,2 ∨ C2,1)
igaz a wumpus világban, de nem teljes. Nem szabályozza azokat a modelleket, amelyekben S1,1 hamis és C1,2 igaz, amivel megszegnénk a wumpus világ szabályait. Egy másik mód ennek érzékeltetésére, hogy az implikáció igényli a csapda jelenlétét, ha szellő van, miközben az ekvivalencia szintén megkívánja a csapda hiányát, ha nincs szellő.
Most, hogy definiáltuk az ítéletkalkulus szemantikáját, létre tudunk hozni egy tudásbázist a wumpus világ számára. Az egyszerűség kedvéért csak a csapdákkal fogunk törődni, a wumpust magát feladatként az olvasóra hagyjuk. A tudás, amelyet most leírunk, elégséges ahhoz, hogy elvégezzük a 7.3. alfejezetben nem formálisan már elvégzett következtetést.
Először meg kell választanunk a szótárunkat az ítéletszimbólumaink megnevezéséhez. Minden i, j-re:
-
Legyen Ci,j igaz, ha csapda van [i, j]-ben.
-
Legyen Si,j igaz, ha szellő van [i, j]-ben.
A tudásbázis tartalmazza a következő mondatokat (mindegyiket felcímkézzük a kényelem kedvéért):
-
Nincs csapda az [1, 1]-ben:
-
Egy négyzet akkor és csakis akkor szellős, ha csapda van a szomszédos négyzetben. Ezt minden négyzetre vonatkozóan ki kell jelenteni, mi most csak a releváns négyzeteket tekintjük:
Sz2: S1,1 ⇔ (C1,2 ∨ C2,1)
Sz3: S2,1 ⇔ (C1,1 ∨ C2,2 ∨ C3,1)
-
Az eddigi mondatok minden wumpus világban igazak. Most hozzáadjuk a szellő érzetet az első két meglátogatott négyzetre abban a specifikus világban, ahol az ágens jelenleg tartózkodik, ami elvezet a 7.3. (b) ábrán látott szituációhoz.
A tudásbázis most Sz1-től Sz5-ig tartalmaz mondatokat. Tekinthetjük ezt úgy is, mint egyetlen mondatot – az Sz1 ∧ Sz2 ∧ Sz3 ∧ Sz4 ∧ Sz5 konjunkciót –, mivel ez azt is kijelenti egyben, hogy minden egyes mondat is igaz.
Emlékezzünk, hogy a logikai következtetés célja, hogy eldöntsük, hogy TB ⊨ α bizonyos α mondatokra. Például, hogy a tudásbázis maga után vonzza-e a C2,2 állítást. Az első algoritmusunk a következtetésre a vonzat definíciójának közvetlen megvalósítása lesz: vegyük sorba a modelleket, és ellenőrizzük, hogy α igaz-e minden modellben, amelyben a TB igaz. Az ítéletlogikában a modellek az igaz és hamis értékek hozzárendelései minden egyes ítéletszimbólumhoz. Visszatérve a mi wumpus világbeli példánkhoz, a releváns ítéletszimbólumok az S1,1, S1,2, C1,1, C1,2, C2,1, C2,2, C3,1. A 7 szimbólum 27 = 128 lehetséges modellt jelent, háromban ezek közül a TB igaz (7.9. ábra). Ebben a három modellben 
igaz, így nincsen csapda az [1, 2]-ben. Viszont a C2,2 a három modellből kettőben igaz és egyben hamis, így még nem tudjuk megmondani, hogy van-e csapda [2, 2]-ben.
A 7.9. ábra precízebb formában megismétli a 7.5. ábrán illusztrált következtetést. A 7.10. ábra egy általános algoritmust mutat a maga után vonzás eldöntésére az ítéletkalkulusban. Mint a VISSZALÉPÉSES-KERESÉS algoritmus a 3.4.3. szakasz - Mélységi keresés részben, az IT-VONZAT? egy rekurzív felsorolást végez a változó hozzárendelések véges terén. Az algoritmus helyes, mivel közvetlenül a vonzat definícióját valósítja meg, és teljes, mivel bármely TB-on és α mondaton működik, és mindig sikeresen véget ér, hiszen véges számú modellt kell megvizsgálni.
![A tudásbázis alapján épített igazságtábla látható az ábrán. A TB igaz, ha Sz1-től és Sz5-ig igaz, amely a 128 sorból csak 3-ban fordul elő. Mind a 3 sorban C1,2 hamis, tehát nincsen csapda az [1, 2]-ben. Viszont lehet, hogy van csapda [2, 2]-ben (bár lehet, hogy nincs).](/sites/default/files/fejezetek/6138/zip/kepek/07-09.png)
IK-IGAZ? igazat ad vissza, ha a mondatot tartalmazza a modell. A modell változó reprezentál egy részleges modellt, egy hozzárendelést a változók egy részéhez. A KIEGÉSZÍT (P, igaz, modell) függvény egy új részleges modellt ad vissza, amelyben P értéke igaz.
Fontos
Természetesen a „véges számosság” nem mindig jelenti a „néhányat”. Ha a TB és az α mondat összesen n szimbólumot tartalmaz, akkor 2n modell létezik. Így az algoritmus időigénye O(2n). (A tárigénye csak O(n), mivel a felsorolás mélységi jellegű.) A fejezet későbbi részében fogunk látni olyan algoritmusokat, amelyek sokkal hatékonyabbak a gyakorlatban. Sajnos minden ismert, az ítéletlogikára vonatkozó következtetési algoritmusnak a legrosszabb esetre vonatkozó komplexitása exponenciálisan függ a bemenetek számától. Nem remélhetjük, hogy ennél hatékonyabbak is lehetnénk, mivel az ítéletlogikában a maga után vonzás co-NP-teljes (lásd A) függelék).
Mielőtt belemerülnénk a logikai következtetés részleteinek tárgyalásába, szükségünk van néhány további, a vonzattal kapcsolatos fogalomra. Mint a vonzat, ezek a fogalmak is a logika minden formájára alkalmazhatók, de legjobban egy konkrét logikán – mint amilyen az ítéletkalkulus – lehet illusztrálni őket.
Az első fogalom a logikai ekvivalencia (logical equivalence): két mondat, az α és a β mondatok logikailag ekvivalensek, ha ezek a mondatok a modellek ugyanazon halmazán igazak. Ezt úgy jelöljük, hogy α ⇔ β. Például (igazságtáblákat használva) könnyen megmutathatjuk, hogy P ∧ Q és Q ∧ P logikailag ekvivalensek; további ekvivalenciák láthatók a 7.11. ábrán. Az ekvivalenciák nagyon hasonló szerepet játszanak a logikában, mint az aritmetikai identitások a közönséges matematikában. Az ekvivalencia alternatív definíciója a következő: bármely két α, β mondatra,
α ≡ β akkor és csakis akkor, ha α ⊨ β és β ⊨ α
(Emlékeztetőül, a ⊨ a maga után vonzást jelöli.)
A második fogalom, amelyre szükségünk lesz az érvényesség (validity). Egy mondat érvényes, ha igaz minden modellben. Például a 
mondat érvényes. Az érvényes mondatokat tautológiáknak (tautologies) is szokták nevezni, ezek szükségszerűen igazak és így feleslegesek. Mivel az Igaz mondat igaz minden modellben, minden érvényes mondat logikailag ekvivalens az Igaz mondattal.
Fontos
Mire jók akkor az érvényes mondatok? A vonzatokra vonatkozó definíciónk alapján levezethetjük a dedukcióelméletet (deduction theorem), amelyet már az ókori görögök is ismertek:
Bármely α és β mondatra α ⊨ β akkor és csakis akkor, ha az (α ⇒ β) mondat érvényes.
(A 7.4. feladatban ennek a bizonyítását kérjük.) A 7.10. ábrán látható következtetési algoritmust úgy tekinthetjük, mint a (TB ⇒ α) érvényességének ellenőrzését. Másik oldalról nézve viszont minden érvényes implikáció leír egy legitim következtetést.
Az utolsó fogalom, amelyre szükségünk lesz a kielégíthetőség (satisfiability). Egy mondat kielégíthető, ha igaz néhány modellben. Például a korábban bemutatott tudásbázis, az (Sz1 ∧ Sz2 ∧ Sz3 ∧ Sz4 ∧ Sz5), kielégíthető, mert van három olyan modell, amelyben igaz, ahogy ezt a 7.9. ábrán megmutattuk. Ha egy α mondat igaz az m modellben, akkor azt mondjuk, hogy m kielégíti (satisfies) α-t, vagy m egy modellje α-nak. A kielégíthetőség ellenőrizhető úgy, hogy a lehetséges modelleket felsoroljuk mindaddig, amíg nem találunk egyet, amely kielégíti a mondatot. A mondatok kielégíthetőségének meghatározása az ítéletlogikában az első olyan probléma volt, amelyről bebizonyították, hogy NP-teljes.
Számos probléma a számítástechnikában valójában kielégíthetőségi probléma. Például a kényszerkielégítési problémák az 5. fejezetben alapvetően arra kérdeznek rá, hogy a kényszerek kielégíthetők-e néhány hozzárendeléssel. Megfelelő transzformációk után a keresési problémák szintén megoldhatók a kielégíthetőség ellenőrzésével. Az érvényesség és a kielégíthetőség természetesen kapcsolatban vannak: α érvényes akkor és csakis akkor, ha 
nem kielégíthető; és fordítva, α akkor és csakis akkor kielégíthető, ha 
nem érvényes. A következő hasznos eredményt is ismerjük:
α ⊨ β akkor és csakis akkor, ha az (α ∧ ¬ β) nem kielégíthető
Fontos
A β mondat bizonyítása α alapján, az (α ∧ ¬β) kielégíthetetlenségének ellenőrzésével, pontosan megfelel a szokásos matematikai bizonyítási technikának a redukcio ad absurdumnak (szó szerint „redukció egy abszurd dologra”). Szokták ezt megcáfolás (refutation) általi bizonyításnak is nevezni vagy bizonyítás ellentmondás (contradiction) által. Feltételezzük, hogy a β mondat hamis, és megmutatjuk, hogy ez a feltételezés ellentmondásra vezet az ismert α axiómákkal. Ez az ellentmondás pontosan azt jelenti, mint amikor azt mondjuk, hogy az (α ∧ ¬β) mondat kielégíthetetlen.
[60] Az olvasó minden bizonnyal észrevette a hasonlóságot a mondatok igazságának fogalma és az 5. fejezetben bemutatott kényszerek kielégítésének fogalma között. Ez nem véletlen, a kényszernyelvek valójában logikák, és a kényszerproblémák megoldása a logikai következtetés egy formája.
[61] A fuzzy logika (fuzzy logics), amelyet a 14. fejezetben mutatunk be, megengedi az igazság fokának kezelését.
[62] Habár az ábra a modelleket, mint egy részleges wumpus világot mutatja, ezek valójában nem mások, mint az igaz és hamis értékek hozzárendelései a „csapda van az [1, 2]-ben” mondathoz. A modellek, matematikai értelemben, nem igénylik, hogy szörnyűséges illatú wumpusok legyenek benne.
[63] Az ágens ki tudja számolni, hogy mekkora a valószínűsége annak, hogy van csapda a [2, 2]-ben. A 13. fejezet fogja megmutatni azt, hogy hogyan.
[64] A modellellenőrzés működik, ha a modellek tere véges, mint például egy rögzített méretű wumpus világ esetében. Az aritmetika esetében ezzel szemben a modellek tere végtelen, még akkor is, ha korlátozzuk magunkat az egész számokra, mivel végtelen számú x, y értékpár létezik az x + y = 4 egyenlethez.
[65] Hasonlítsuk össze a 3. fejezet végtelen keresési tereinek esetével, ahol látható, hogy a mélységi keresés nem teljes.
[66] Mint azt Wittgenstein (1922) írta híres művében, a Tractatusban: „A világ mindaz, aminek az esete fennáll.”
[67] Az ítéletkalkulust Boole-logikának (Boolean logic) is nevezzük, a logikával foglalkozó George Boole (1815–1864) után.
[68] A latinnak létezik külön szava az „exkluzív vagy” kifejezésére, ez az aut.
- A hozzászóláshoz bejelentkezés szükséges