Mesterséges intelligencia alapjai

Formális logika

Tudásszemléltetés formális logikával

• A logikáról��A logika a bölcselés tudománya, a helyes gondolkodás művészetének tana.�
• A logika osztályozása �

Logika

Arisztotelészi�(hagyományos)

Szimbolikus�(formális)

Nem klasszikus szimbolikus logika

Propozíciós logika

Predikátum logika

- modális�- temporális�- többértékű�- intuicionista�- valószínűségi.

Fuzzy

A szimbolikus logika kifejlődése

• Petrus Ramus (1515-1572)
• Bírálta az arisztotelészi logikát.
• "A logika: a helyes érvelés eszköze."�
• Francis Bacon (1561-1626)
• "A logika az új ismeretek megszerzésének �eszköze."
• Kísérletek, mérések fontossága.�
• René Descartes (1596-1650)
• "Értekezés a módszerről" c. műve
• A problémákat osszuk független, vagy kevéssé összefüggő részekre
• Az egyszerűtől haladjunk a bonyolultabb felé
• Csak olyan dolgokat fogadjunk el igaznak, melyek igazsága megkérdőjelezhetetlen
• Törekedjünk a teljes felsorolásokra.

​

​

• Gottfried Wilhelm Leibniz (1646-1716)
• A szimbolikus logika előfutára
• "Logika ≅ matematika.„
• a logika a matematikához hasonló rutinszerűen alkalmazható műveletekkel lenne kezelhető.
• Azonosság definíciója: �"Azok a terminusok tekintendők azonosnak, vagy egybeesőnek, amelyek egymással tetszés szerint felcserélhetők anélkül, hogy ezáltal bármelyik állítás igazsága megváltozna."
• George Boole (1815-1864)
• A szimbolikus logika megalapítója.
• "A logika matematikai analízise" című műve.
• Matematikai és más kijelentések formailag hasonlóan kezelhetők tartalmuktóól függetlenül
• A logikai szorzás és logikai összeadás műveletének bevezetése.�
• John Venn (1834-1923)
• "Symbolic Logic" című műve
• Diagramok: teljes esemény = téglalap; körök: mindenféle egymásbametszés

• William S. Jevons (1835-1882)
• "megengedő vagy"
• Első logikai gép (a logikai zongora)������
• Charles S. Peirce (1839-1914)
• Boole összes logikai művelete kiváltható egyetlen művelettel, a ‘sem...., sem…‘, NOR művelettel.��
• Augustus de Morgan (1806-1871)
• Reláció-azonosságok.�

​

• Gottlob Frege (1848-1925)
• Integrálta a korábbi eredményeket
• Bevezette a logikai függvény fogalmát
• "A szimbolikus logika atyja"
• "Fogalomírás, a tiszta gondolkodás aritmetika mintájára megalkotott formanyelve" c. műve

​

• Bertrand Russell (1872-1970)
• Frege-től függetlenül ugyanoda eljutott
• Hézagok az elődök munkáiban: logikai paradoxonok.
• "Az osztályok osztálya eleme-e önmagának ?"
• Típuselmélete: magyarázat a paradoxonokra.

​

Új irányzatok a logikában

• A modális logikákkal olyan terminusok is kifejezhetők, mint a "lehetséges", "szükségszerű" és ezek változatai. �A modális logika a klasszikus logika kiterjesztése.
• A deontikus logika olyan etikai és jogi kifejezések elemzésével� foglalkozik, mint a "Megtiltott, hogy...", "Megengedett, hogy...", stb.
• Jan Lukasiewicz (1878-1956)
• Háromértékű logika: 0, 1/2, 1, ahol az 1/2 érték a bizonytalanságot fejezi ki.
• Eljutott a végtelenértékű logikáig.
• E.L.Post (1897-1954)
• Többértékű logika, Lukasievicz-csel egyidőben.
• J.M.Keynes (1883-1946)
• Ch.S.Peirce-szel együtt a valószínűségi logika �megalkotójának tartják.
• Logikai valószínűség: a racionális hit (ésszerű meggyőződés) foka, 0...1 közötti érték.

.

Propozíciós logika

• Egyéb elnevezések: kijelentéskalkulus, ítéletkalkulus, nulladrendű predikátum-kalkulus.
• Propozíció: egy kijelentő mondat formában megadott állítás, mely az adott kontextusban egyértelmű igaz, vagy hamis logikai értékkel bír.
• A propozíciós logika olyan egyszerű nyelvtani kapcsolatokat alkalmaz a legegyszerűbb "atomi mondatok" között, mint az és, vagy, nem.�
• Atomi mondatok :� A= " A víz száz fokon forr."� B= " A macskák ugatnak."��Az ilyen atomi összetevők (objektumok) egyértelműen megítélhetők az igaz, vagy hamis értékek valamelyikével. ( Általános tapasztalat szerint A igaz, B hamis).

​

​

.

​

• A propozíciós logika tárgya, célja összetett szerkezetek kiértékelésére formális szabályt adni. A kiértékelésben az atomi összetevők (objektumok) igazságértékeit kell csak figyelembe venni, jelentésüktől eltekintünk.�
• Atomi kijelentések helyett szimbólumok:�� Esik az eső. ⇒ A�
• Eltekintünk a természetes nyelvi jelentéstől �Nem természetes átalakítás, pl.:� A: Jóska megbetegedett.� B: Jóska elment az orvoshoz.��Hétköznapi értelemben A és B jelentése eltér B és A összetett kijelentésétől. ��Csak az igaz, vagy hamis értéke fontos számunkra A-nak és B-nek.

​

​

.

A propozíciós logika szintaxisa

• Jelkészlet
• Elválasztójelek: , ( ) [ ]�
• Logikai operátorok (műveleti jelek): {csökkenő precedenciasorrendben}

¬ ∧ ∨ → ≡

negáció konjunkció diszjunkció  implikáció ekvivalencia

'nem’ 'és’ 'vagy’ 'ha ... akkor ...’ 'akkor és csak akkor’

'következik' 'azonos'

• Logikai változók (ítéletváltozók): p, q, r, …�
• Logikai konstansok (ítélet-, predikátumkonstansok) : T, F (True, False), (igaz, hamis).

.

• A propozíciós logika (kijelentéskalkulus, ítéletkalkulus) formuláit a jelkészlet elemeiből a szintaxis szabályai szerint építjük fel:�
• Atomi formula (atom)
• Minden ítéletkonstans atom : T, F
• Minden ítéletváltozó atom : p, q, r, …�
• Formula (jól formált formula):
• Minden atomi formula egyben formula
• Ha A és B formulák, akkor a ��¬A, A∧B, A∨B, A→B, A≡B �� kifejezések is formulák.

​

.

A propozíciós logika szemantikája

• Egy logikai formulának az igazságértéke ad jelentést, mely igazságértéket a szemantika szabályai szerint kapja meg.
• A jelentésadás lépései:

1. Interpretálás

2. Kiértékelés

1. Interpretálás�A formula interpretálása: minden egyes ítéletváltozójához az igaz, vagy a hamis értéket rendeljük minden lehetséges módon. Egy hozzárendelés egy interpretációt ad.�Az interpretációk száma a propozíciós logikában véges: 2ⁿ ahol n a változók száma.

pl.: A:=(p∧q) → (r ≡ (¬ s))

      két lehetséges interpretációja:

      I₁: (p,q,r,s)←(T,T,F,F)

      I₂: (p,q,r,s)←(F,T,T,F)

​

.

2. Kiértékelés�Az interpretált formula kiértékelését a logikai műveleti jelek szemantikája alapján végezzük:�����������Pl.: Ha süt a nap, nem tanul Péter.

       süt a nap    : p

       tanul Péter : q

       A:= p→(¬ q)�A lehetséges 4 interpretáció egyike: p= T, q= F, �a kiértékelt formula: T→(¬ F); T → T; T, az A állítás igaz.

.

Kielégíthetetlen és érvényes kifejezések

• A kielégíthetetlen logikai kifejezések és az érvényes kifejezések fontos szerepet játszanak a tételbizonyításban. A tétel azt jelenti, hogy állításokból logikailag következik a konklúzió.�
• Tautologikus törvény: A ∨ B = A, ha A tautológia,

A ∧ B = B, ha A tautológia.�

A logikai kifejezés tautológia, azaz érvényes kifejezés akkor, ha minden lehetséges helyettesítése igaz.

​

• Kielégíthetetlenségi törvény: A∨ B = B, ha A kielégíthetetlen,

A∧ B = A, ha A kielégíthetetlen.

A logikai kifejezés kontradikció, azaz kielégíthetetlen kifejezés akkor, ha minden lehetséges helyettesítésre hamis értéket ad. �

Természetesen a formulák többsége egyes interpretációkban hamis, más interpretációkban igaz, azaz kielégíthető.

​

.

Tételbizonyítás a propozíciós logikában

• Egy propozíciós logikai formula érvényességének igazolására alkalmas módszerek:
• Igazságtáblás
• Formális levezetés
• Quine algoritmusa
• Wang algoritmusa
• Rezolúció.
• A rezolúció szabálya: α ∨ β, ¬β ∨ γ� α ∨ γ��Mivel β nem lehet egyszerre igaz és hamis, ezért valamelyik premisszában, előfeltételben a másik tagnak (α, vagy γ ) igaznak kell lennie, tehát az α ∨ γ igaz.
• A rezolúció módszere kiemelkedik a többi közül, mivel ez a bizonyítási módszer alkalmazható a predikátum logikában is.

​

.

.

• A konjunktív normálforma�
• Klózok konjunkciója, ÉS kapcsolata
• Az eredeti formulával ekvivalens
• Egyszerű felépítése miatt gépiesen kezelhető.

​

• A klóz literálok diszjunkciója (VAGY kapcsolata), vagy egyetlen literál.
• A literál egy ítéletváltozó (logikai változó), vagy annak negáltja.��Példa:���� (p ∨ ¬q) ∧ (¬ p ∨ r ) ∧ (¬ r ∨ ¬ s ) ∧ q ∧ s

.

klóz

klóz

klóz

klóz

klóz

konjunktív normál forma

• Formulák konjunktív normálformára hozásának lépései:

1. Azonosságok kiküszöbölése: A ≡ B = (A → B) ∧ (B → A)

2. Implikációk kiküszöbölése: A → B = ¬ A ∨ B

3. A negálás hatáskörének redukálása:

¬ (A ∨ B) = ¬ A ∧ ¬ B� ¬ (A ∧ B) = ¬ A ∨ ¬ B

4. Klózok konjunkciójának létrehozása:

A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C).

• A diszjunktív normál formából elhagyva a konjunkció operátorokat, a formula klózokra esik szét, melyek halmazára alkalmazzuk a rezolúció szabályát ciklusban. Ily módon a rezolúció egy olyan könnyen automatizálható eljárás, melynek segítségével egy klózhalmaz, illetve a neki megfelelő konjunktív normál forma kielégíthetetlenségét belátjuk.
• A klózhalmaz egyszerűsítése rezolválható klózpárokon keresztül történik.
• Rezolválható klózpár: egyetlen ellentett literálpárt tartalmaznak, pl:� p ∨ A , ¬ p ∨ B�ahol A és B közvetlenül tovább már nem rezolválható klózok.

.

​

• A rezolúciós folyamat során a rezolválható párok rezolválása eredményeként adódó rezolvens klózt a halmazhoz adjuk.�
• A klózhalmaz kielégíthetetlenségét az jelzi, hogy végül üres klózt kapunk.�
• A rezolúció algoritmusa:�� Procedure Rezolúció� 1. KLÓZHALMAZ feltöltése� 2. do� 3. Rezolválható klózpár Ci, Cj kiválasztása a KLÓZHALMAZ-ból� 4. Rezolválás: Cij ⇐ R(Ci,Cj)� 5. KLÓZHALMAZ bővítése Cij rezolvenssel� 6. while Cij ≠ NIL � end

.

​

Példa:��KNF: (p ∨ ¬q) ∧ (¬ p ∨ r ) ∧ (¬ r ∨ ¬ s ) ∧ q ∧ s �

p ∨ ¬q ¬ p ∨ r ���� ¬q ∨ r ¬ r ∨ ¬ s ��A rezolúció�teljességének�tétele garantálja, ¬q ∨ ¬ s q�hogy egy kielégítetlen�formula klózhalmazából�kiindulva, minden lehetséges �módon képezve a klózpárok ¬ s s�rezolvensét, véges sok lépésben�eljutunk az üres klózhalmazhoz.� NIL

​

.

Predikátum logika�További elnevezések: elsőrendű predikátumkalkulus, vagy egyszerűen predikátumkalkulus.

• Predikátum: objektumok sajátságainak és az objektumok közötti kapcsolatok, viszonyok, relációk szimbolikus formában való megadására alkalmas állítás, mely egy adott interpretációban egyértelmű igaz, vagy hamis minősítéssel bír.
• A predikátum logika jellemzői:
• MI feladatok reprezentálására alkalmas (ld.: PROLOG).
• Kijelentéseink tartalmát is leírja, mivel az állítások az individuumkonstansok, individuumváltozók és individuumfüggvények révén egy tartomány (, alaphalmaz, domain) elemeire vonatkozhatnak.
• Az ítélet-, vagy logikai függvények, azaz a predikátumok használatával indivíduum paraméterektől függő igazságú állítások fogalmazhatók meg.
• Új logikai operátorok, a kvantorok segítségével kifejezhetjük a "minden" és a "létezik" fordulatokat is.
• Az interpretáció módja eltér a propozíciós logikáétól, és ebből eredően a predikátum logikában egy formulának végtelen sok interpretációja lehetséges az alaphalmaz, és az azon értelmezett függvények és predikátumok tetszőleges választhatósága miatt.

​

.

�Bonyolultabb tételek bizonyíthatók, mint a propozíciós logikában:

�

Pl.:

​

Premisszák, ismert tények:

(1) Van olyan hallgató, aki minden tárgyat szeret.

(2) A szócséplést egyik hallgató sem szereti.

------------------------------------------------------------------------

Igaz-e a fenti állítások ismeretében a következő állítás?

​

Bizonyítandó állítás:

(4) Egyik tárgy sem szócséplés.

​

​

.

A predikátum logika szintaxisa

• Jelkészlet:
• Elválasztójelek: , ( ) [ ]
• Logikai operátorok (műveleti jelek): ¬ ∧ ∨ → ≡
• Kvantorok: univerzális kvantor ("minden"): ∀

egzisztenciális kvantor ("létezik" vagy "van olyan"): ∃ .

(precedencia: ∀ ∃ ¬ ∧ ∨ → ≡ )

• Elemkonstansok (individuumkonstansok): a, b, c,...,vagy nevek (például: János, asztal).
• Elemváltozók (individuum változók): x, y, z...
• Függvényszimbólumok (individuumfüggvények): f, g, h,... , vagy például: testvére(Józsi)⇒ Laci
• Itéletkonstansok (logikai konstansok): True, False.
• Itéletváltozók (logikai változók): p, q, r...
• Predikátumszimbólumok (logikai függvények): P, Q, R,... , vagy például: testvérek(x,y), P(x,y).

​

​

.

​

• A jelkészlet elemeiből a kifejezések 3 osztálya alkotható meg: �Term-ek, Atomi formulák (Atomok) és Jólformált formulák (Formulák).

�

• Term (individuum konstans, individuum változó, individuum függvény):
• Minden elemkonstans (individuum konstans) term. Pl.: a,b,...,asztal, szék, stb.

​

• Minden elemváltozó (individuum változó) term. Pl.: x, y.�
• Ha f egy n-argumentumú függvényszimbólum és t₁,...,t_n term-ek, akkor f(t₁,...,t_n) is term.

Pl.:

f(a,x),

gyereke(Pál, x), (x=Bori esetén az eredmény Józsi, x=Julcsi esetén az eredmény Béla) színe(haj,időskorban)⇒ősz,

színe(haj,fiatalkorban) ⇒ szőke.

​

.

• Atomi formula (kiértékelve True, vagy False):�
• Minden ítéletkonstans atomi formula. ( True, False )�
• Minden ítéletváltozó atomi formula. ( p, q, r,… )�
• Ha P egy n-argumentumú predikátumszimbólum (logikai függvény) és t₁,...,t_n term-ek, akkor P(t₁, ...,t_n) atomi formula. � Pl.:

házaspár(Pál,Irén) ⇒ True

gyereke(Pál, x) (x=Józsi esetén az eredmény igaz, x=Bori esetén az eredmény hamis)

színe(szőke, haj, időskorban) ⇒ True

.

• Formula (jólformált formula):�
• Minden atomi formula egyben formula. (True, p, P(a,b) )�
• Ha A és B formulák, akkor a

(¬ A), (A ∧ B), (A∨ B), (A → B), (A ≡ B) kifejezések is formulák.�

• Ha az A egy formula és az x egy elem (individuumváltozó), akkor a

(∀ x) A, (∃ x) A

kifejezések is formulák. Pl.: (∀ x) testvére (x,Pál) �

Precedenciasorrend: ∀∃¬ ∧ ∨ → ≡, pl.: (((∃x)A) ∨ (B) helyett: (∃x)A ∨ B�

Példa: Vagy van egy részeg, vagy nem volt már ital.

A:= részeg(x)=R(x), � C= volt ital� (∃x)R(x) ∨ ¬C.

�

​

.

• Kötött változó:�Minden előfordulása a formulában kvantor hatása alatt áll.�� (∀ x) P(x,y) x kötött változó, y nem kötött változó.

(∀ x) [P(x,y) ∧ (∃ y) Q(x,y)]

mindkét x kötött [] miatt,

y első előfordulása nem kötött, y második előfordulása kötött.

​

• Mondat: olyan formula, melyben minden változó összes előfordulása kötött. Csak mondatokkal foglalkozunk.��Példa mondatra: (∀ x) [P(x) ∨ (∃ y) Q(x,y)]

​

.

Példa a formulázásra

Feladat:

Állítások: (1) Van olyan hallgató, aki minden tárgyat szeret.

(2) A szócséplést egyik hallgató sem szereti.

------------------------------------------------------------------

(3) Egyik tárgy sem szócséplés�

Formalizálás:

Alkalmazott predikátumok:

H(x): az x egy hallgató

T(y): az y egy tárgy

C(y): az y egy szócséplés

S(x,y): az x szereti y-t.

A formalizált állítások:

F1: (∃ x)[H(x) ∧ (∀ y)(T(y) → S(x,y))]

F2: (∀ x)[H(x) → (∀ y)(C(y) → ¬ S(x,y))]

F3: (∀ x)[T(x) → ¬ C(x)]

​

.

A predikátumkalkulus szemantikája

• Az elsőrendű predikátumkalkulus formuláinak is hasonlóan adunk jelentést, mint az ítélet-kalkulusban:
• először interpretáljuk, majd
• kiértékeljük a formulát. (Eredmény: True, vagy False).
• Interpretáció:
• Individuumtartomány (az értelmezés alaphalmazának) megválasztása: jele D, nem üres.
• Hozzárendelések:
• Minden individuumkonstans-szimbólumnak feleltessük meg D egy elemét. (a:= asztal )
• Minden n-argumentumú individuumfüggvényhez (pl.: f(a,b) ) rendeljünk hozzá egy

Dⁿ ⇒ D leképezést. (Pl.: gyermeke(a,b) ⇒ c, gyermeke(Pál,Irén) ⇒ Jutka).

• Minden n-argumentumú predikátumfüggvénynek feleltessünk meg egy D² ⇒ {T,F} leképezést, ahol T a logikai igaz, F pedig a logikai hamis értéket jelöli.

(Pl.: házaspár(Pál,Irén) ⇒ True ).

​

.

Predikátum-logikai formulák kielégíthetősége

• Kielégíthető az a formula, amelyik valamely interpretációban igaz.
• Érvényesnek nevezünk egy formulát, ha minden interpretációban igaz. � Például a (∀ x)P(x) ∨ (∃ y) ¬ P(y).
• Kielégíthetetlen az a formula, amely minden interpretációban hamis értékű.� Például a (∀x)P(x) ∧ (∃y) ¬ P(y).
• Az érvényes, illetve a kielégíthetetlen formulák a fontosak számunkra, ugyanis a tételbizonyítást egy formula érvényességének, illetve kielégíthetetlenségének a belátására lehet visszavezetni.
• Probléma: az elsőrendű predikátum kalkulus egy formuláját nem tudjuk az összes lehetséges interpretációban kiértékelni, mivel végtelen sok alaphalmazt lehet megadni.
• Megoldás: a rezolúciós eljárás, mellyel egy formula érvényessége, vagy kielégíthetetlensége belátható.

​

.

Rezolúció a predikátum logikában

�Bonyolultabb tételek bizonyíthatók, mint a propozíciós logikában, ugyanakkor a bizonyítás lépései is jóval összetettebbek. �A következőkben egy egyszerű példát mutatunk, amely rámutat a predikátum logikán belüli rezolúció egyik erősségére: A bizonyítás folyamán individuumváltozó - individuumkonstans hozzárendeléseket is végez, amely révén arra is választ kapunk, hogy milyen feltételek mellett igaz a tétel. ��Igazi erejét megtapasztalhatjuk a Prolog programozási nyelvben.� Pl.: Feladat: Értik-e a hallgatók a rezolúciót?

Premisszák, ismert tények:

(1) A hallgatók értelmesek.

(2) Az értelmesek mindent értenek, ami egyszerű.

(3) Az értelmeseknek a rezolúció egyszerű.

------------------------------------------------------------------------

Igaz-e a fenti állítások ismeretében a következő állítás?

Bizonyítandó állítás:

(4) A hallgatók értik a rezolúciót.

​

.

• �Formulázás:�
• Alkalmazott predikátumok:

hallgató(x) - az x az egy hallgató

értelmes(x) - az x értelmes

érti(x,y) - az x érti az y-t

egyszerű(y) - az y egyszerű

​

• A premisszák és a negált következmény formalizált alakban:

(1) ¬ hallgató(x) ∨ értelmes(x)

(2) ¬ értelmes(x) ∨ érti(x,y) ∨ ¬egyszerű(y)

(3) ¬ értelmes(x) ∨ egyszerű (Rezolúció)

(4) hallgató(x) ∧ ¬ érti(x,Rezolúció) ⇐ tagadása ⇐ �� ¬ hallgató(x) ∨ érti(x,Rezolúció)

.

• ��A klózhalmaz: �¬ hallgató(x) ∨ értelmes(x) ¬ értelmes(x) ∨ érti(x,y) ∨ ¬egyszerű(y) �¬ értelmes(x) ∨ egyszerű (Rezolúció) hallgató(x) ¬ érti(x,Rezolúció)��A rezolúciós folyamat lépései:�� ¬ hallgató(x) ∨ értelmes(x) hallgató(x) �� értelmes(x) ¬ értelmes(x) ∨ érti(x,y) ∨ ¬egyszerű(y)�� ¬ érti(x,Rezolúció) érti(x,y) ∨ ¬egyszerű(y)�� y ⇐ Rezolúció � ¬egyszerű(Rezolúció) ¬ értelmes(x) ∨ egyszerű (Rezolúció) �� ¬ hallgató(x) ∨ értelmes(x) ¬ értelmes(x) �� ¬ hallgató(x) hallgató(x) �� NIL

​

.

A PROLOG

• PROLOG (Programming in Logic, Logika alapú programozás) �Alain Colmerauer, Bob Kowalski, 1970.

​

• Predikátum konstanson alapuló általános célú �programnyelv, amely azonban legelőnyösebben �logikai problémák megoldására alkalmazható. �
• A PROLOG létrehozására kihatott az a tapasztalat, amelyet a korábbi MI programozási nyelvekkel szereztek: minél több a rendszerbe épített lehetőség, a rendszer annál inkább lelassul.

​

• Deklaratív programnyelv: elegendő megadnunk csak a problématerületre vonatkozó tényeket, szabályokat és a megválaszolandó kérdést, ill. minősítendő állítást, és a program generálja a megoldáshoz vezető lépéseket és szolgáltatja a választ.

​

Bevezetés a PROLOG programozási nyelvbe

• Jellemzői:
• Az eljárások és a tények a mintaillesztés során kerülnek elő
• Betartja a bemenőállítások sorrendjét.
• A keresést automatikus visszalépéssel (back track) hajtja végre, amelyet azonban a programozó a ! (cut, vágás) operátorral módosíthat. Ez a lehetőség ellentmond a logikai programozás ideális koncepciójának: a programozó feladata csak a logikai probléma megadása, a problémaleírás algoritmikus kiértékelését pedig a gépnek kell elvégeznie. �Kowalski képlete:�                                                          �            algoritmus = logika + vezérlés  �                 �Jelentése a következő: egy algoritmus mindig két komponenst tartalmaz implicit formában:
• a logikai összetevőt, amely megadja a kérdéses problémára vonatkozó tudást,
• a vezérlési összetevőt, mely megtestesíti a megoldási stratégiát az adott probléma esetére.

​

​

• Bevezetésre került a symbol típus (domain), hogy a predikátumlogika individuumkonstansai, -változói és -függvényei a valóság egy részletét leképezhessék.�
• Fontos adatszerkezet a lista. A listafeldolgozás a mintaillesztésen és a rekurzión alapul.

​

• A függvények a predikátumfüggvényeken alapulnak, és nincs különbség a bemenő és a kimenő változók között.

​

• A bemeneti állítások (szabályok, clauses) formátuma korlátozott:�

P if Q and R and S.

fej törzs

�A fej egyetlen predikátum, a törzs pedig atomi formulák (többnyire predikátumok, azaz logikai függvények) negációt nem tartalmazó konjunkciója (csak and lehet).

​

​

• Mivel a törzs atomi formulák konjunkciója, azaz Horn-halmaz, így azt mondhatjuk, hogy a PROLOG a Horn halmazokra a rezolúció elvét alkalmazza. �
• A felhasználóra hagyja a rezolúciós stratégia megvalósítását: néhány megszorítást tett a bemenőállításokra, és az illesztés a bemenőállítások (clauses, tények és szabályok) megadott sorrendjében hajtódik végre. A rendszer így tömörebb lett és gyorsabb végrehajtást tesz lehetővé.

​

• A predikátum logikára épül, de vannak eltérések:
• Csak az elemváltozók kezdődnek nagybetűvel.
• Ítéletkonstansok közül a False (fail) ritkán, a True és ítéletváltozók még ritkábban fordulnak elő.
• Rendszerpredikátumok léteznek, melyek valamit elvégeznek és eközben igaz értéket vesznek fel. Pl.: read(). write(), circle(), stb.
• Infix (közbeírt) alakú relációoperátorok (<,>, <=,>=,<>,=,><) és aritmetikai operátorok (+,-,*,/ ) a predikátumos alak helyett. Pl.: kisebb(X,Y) helyett X<Y írható.

​

• Egyenlőséges reláció egyetlen hiányzó értékű változójának képes kiszámítani az értékét. Pl.: 5*7= X ⇒ X=35
• Aritmetikai kifejezéseket, műveleti operátorokat végrehajtja.
• A szabályokban szereplő if (:-) logikai szimbólumot úgy kezeli, mint egy infix alakban használt speciális rendszer-predikátumot, amely a PROLOG-tól egy speciális kiértékelő algoritmust kíván.
• A szabályok és az atomok (főként predikátumok ) ugyanolyan módon kezelendő objektumoknak minősülnek.
• Megengedi ítéletváltozók alkalmazását a szabályokban és megengedi helyettesítésüket szabályokkal.
• Képes manipulálni saját "adatbázisát" (az assert és a retract rendszerpredikátumok útján.)
• Kényelmes [ Fej | Törzs ] listaalak. [ ] az üres lista jele.
• A megoldási folyamat programozó általi vezérlésére alkalmazza a ! jelet, mely formailag egy atomi formula. Pl.: a if b and c and ! and d. A ! (cut) megváltoztatja, lerövidíti a PROLOG Depth-First (mélységi bejárás) algoritmusát a felesleges ágak bejárásának letiltásával, az ágak levágásával.

Példa

A PROLOG programok felépítésének és eszköz-rendszerének részletezése előtt tekintsünk egy egyszerű feladatot és PROLOG programját!�� Ismertek az alábbi tények:

Cleopátra szebb Ginánál.

Gina szebb Ursulánál.

Kérdés: Ki sokkal szebb Ursulánál ?

​

• A feladat megválaszolására alkalmas PROLOG program:�

domains hölgy = symbol

predicates szebb(hölgy, hölgy)� sokkal_szebb(hölgy,hölgy)

goal sokkal_szebb(Valaki, ursula)

clauses szebb(cleopátra,gina).

szebb(gina, ursula).

sokkal_szebb(A,C ) if szebb(A,B ) and szebb(B,C ).

A PROLOG működése

A működés két alapvető összetevője az

• illesztés (matching) és a
• visszalépés (backtracking).
• Lényege: a goal-ban feltett kérdést megpróbálja tényállításokra visszavezetni. Amennyiben nem létezik illeszkedő - nevében és a megadott paramétereiben egyező - tény, akkor illeszkedő szabályt keres. Ha van illeszkedő szabály, akkor az előbbi lépések ismétlésével megpróbálja a szabály Törzsében lévő feltételek kiértékelésével meghatározni a szabály Fejének igazságértékét (Hátraláncolás).
• Az összes lehetőség végigpróbálásával megállapítja, hogy a kérdés teljesülhet-e, és ha igen, hányféle módon.
• Ha próbálkozás közben zsákutcába jut - nincs illeszkedő tény, vagy szabály -, visszalép a legutolsó elágazási pontig, ahol a több illesztési lehetőség közül a következőt választja.

Példa fagráf

domains hölgy = symbol

predicates szebb(hölgy, hölgy)

sokkal_szebb(hölgy, hölgy)

goal sokkal_szebb(Valaki, ursula)

clauses szebb(cleopátra,gina).

szebb(gina, ursula).

sokkal_szebb(A,C) if szebb(A,B) and szebb(B,C).

​

​

Példa fagráf módosítva

domains hölgy = symbol

predicates szebb(hölgy, hölgy)

sokkal_szebb(hölgy, hölgy)

goal sokkal_szebb(Valaki, ursula)

clauses szebb(gina, ursula).

szebb(cleopátra,gina). sokkal_szebb(A,C) if szebb(A,B) and szebb(B,C).

​

​

A Fuzzy logika alapjai

�A Fuzzy logika Lofti Zadeh nevéhez fűződik. (1965)

​

• A hagyományos kétértékű logika helyett végtelenértékű, folytonos változókat és a hamis és igaz közötti folytonos átmenetet használ a fogalmak, jellemzők igazságértékének megadására.
• Hiányos adatok elfogadása, zajtűrő képessége, kollektív döntést utánzó működése a mesterséges neurális hálózatokhoz hasonlóan robusztus, megbízható alkalmazások készítését teszi lehetővé bizonytalan adatok esetére is.
• Szimbolikus szinten működik, nyelvi változókat használ, ezáltal közel áll az emberi gondolkodáshoz.
• Alkalmazása különösen a szabályozástechnikában igen elterjedt.

​

Fuzzy halmazok

• Egy elemnek a fuzzy halmazba való tartozásának foka, 0-1 közötti mértéke van, nem merev igen/nem.
• Értelmezés: �Ha X az x jellemzők, értékek egy csoportja, akkor az X-en értelmezett A fuzzy halmaz a következő rendezett párok halmaza:� A = (x, μ_A(x)): x ∈ X��A μ_A(x) neve tagsági függvény, értéke az x tagsági aránya, beletartozásának mértéke az A fuzzy halmazba, ill. az A tagsági függvényhez társított nyelvi érték igazságának foka.
• A μ_A(x) tagsági függvény az X értékhalmazt leképezi az M tagsági térbe ( μ_A(x) ∈ [0;1] ). �

• ��Példa: X testmagasságértékek [cm]. �A halmaz: a „hórihorgas” nyelvi értéknek �megfelelő x, μ_A(x) számpárok halmaza, ábrája:� fizikai változó: x= 200 ; � fuzzy változó: testmagasság = hórihorgas� igazságértéke= 0.9

fuzzifikálás

Tagsági függvények

Mean�Standard deviation

Center�Width �Slope

Fuzzy logikán alapuló következtető rendszer

• Produkciós, szabályalapú működés (R1: Ha x=A akkor y=B)
• A az R1 szabály antecedense (előzmény, feltétel), B pedig az R1 szabály konzekvense (következmény)
• Tehét a szabályok feltételoldalán fuzzy ÉS, ill. fuzzy VAGY logikai műveletekkel összekötött � fuzzy változó = nyelvi érték �beletartozási relációk vannak, melyek értékét a fuzzy változóhoz tartozó fizikai változó (x) aktuális értéke és a nyelvi értékhez tartozó tagfüggvény együttesen határozzák meg.
• A feltételoldali logikai kifejezés eredő érvényességi, igazsági értékét a fuzzy ÉS, ill, VAGY logikai műveletek értelmezésének felhasználásával számítjuk és ez lesz a következmény oldal érvényessége is egyben.
• A következmény oldalon egyetlen� fuzzy változó = nyelvi érték �reláció áll, melynek érvényessége, igazságértéke megegyezik a feltételoldalra meghatározott értékkel.

​

Fuzzy műveletek

• Fuzzy ÉS művelet értelmezése (C= A ∧ B): � μ_C(x)= min μ_A(x), μ_B(x) , x ∈ X

​

​

​

​

• Fuzzy VAGY művelet értelmezése (C= A ∨ B): � μ_C(x)= max μ_A(x), μ_B(x) , x ∈ X

A ∨ B

A ∧ B

​

• Az összes szabály egyszerre működik a fizikai változók, mint bemenő tények felhasználásával és kollektív döntést hoz. A kollektív döntés eredményét a fuzzy nyelvi értékek tagfüggvényeinek felhasználásával, a fuzzy változó terében az érvényességi értékekről a fizikai változóra való áttéréssel, ún. defuzzifikálással nyerjük.

​

• A defuzzifikálás módszerei:
• Területközéppont meghatározással (legelterjedtebb eljárás)
• Tagsági függvény maximumok súlyozott átlagának meghatározásával
• A legnagyobb érvényességű következmény-tagfüggvény maximumával.

� � If Zárthelyieredmény = Jó ÉS Előadáslátogatás = Ritka then Vizsgajegy = Jeles � If Zárthelyieredmény = Közepes ÉS Előadáslátogatás = Gyakori then Vizsgajegy = Jó

Min

Min

​

• A Fuzzy logika alapjai ..���Fuzzy szabályozórendszer vázlata�

​

Szabálybázis

2. Fuzzy �következtetés

1. Fuzzy-�fikálás

3. Defuzzy-�fikálás

Szabályozott �folyamat

Mért fizikai �értékek

Beállítandó �fizikai �értékek

Fuzzy�nyelvi �értékek

Fuzzy�nyelvi �eredmény�értékek