| Sistemi vestacke inteligencije - treca godina |
 |
 |
|
1. NASTANAK I RAZVOJ VEŠTAČKE INTELIGENCIJE Za prepoznavalje inteligentnog ponašanja Tjuring je predložio sl. test: Ako je ponašanje mašine koja odgovara na pitanja ne moguće razlikovati od ponašanja čoveka koji odgovara na analogna pitanja, tada ta mašina poseduje inteligenciju. Razvoj V.I. orijentisan je u dva osn. pravca: 1. istraživanje prirodne inteligencije 2. postiyanje posebnih efekata ne nuzno po principima kako to radi čovek. Suština je stvaranje mašine koja će imati aktivnosti ya koje je potrebna intel. Čoveka. U osnovne pravce ove oblasti ubrajaju se: 1. automatske metode rešavanja zadataka 2. prepoznavanje vizuelnih oblika i govora 3. dokazivanje teorema 4. razumevanje i prevodjenje jezika 5. mašinsko učenje 6. intelektualne igre.
2. RAZLIČITI PRILAZI KREIRANJU S.V.I. Postoje 3 prilaza za kreiranje v.i. 1) veštačke ‚‚neuronske mreže‚‚ 2) modeliranje evolucije 3) heurističko programiranje. Stvaranje veštačkih neuronskih mreža inspirisano je hipotezom da se prirodna intelig. Formira isključivo na osnovu prorodnih neuronskih mreža. Mreža se sastoji od velikog broja veštačkih neurona i veza medju njima. Evolucioni prolaz zasniva se na hipotezi da je prirodna intel. Evoluirala u procesu koji uključuje prirodnu selekciju i mutaciju. Treći prilaz zasnovan na heurističkom programiranju sastoji se u kreiranju računskih programa koji se inteligentno ponašaju. Pod heuristikom se podrazumeva način, metod, pravilo, ili strategija za povecanje efikasnosti sistema koji rešava složene zadatke.
3. PROSTOR STANJA (PROBLEMSKI PROSTOR) Predstavljanje zadataka u prostoru stanja yasniva se na skupu stanja i skupu operatora koji transformišu jedno stanje u drugo. Rešavanje zadataka svoji se na nalaženju niza operatora kojima se neka od početnih stanja transformišu u neko od konačnih stanja.Prostor stanja se def. kao uredjena četvorka. (So,S,F,T) gde je : So – skup početnih stanja, S- skup stanja, F- skup operatora, T- skup završnih stanja.
4. METODE PRODUKCIJE I METODA REDUKCIJE SISTEMA Stanja se opisuju skupom obeležja i zovu se N-stanja. Skup N-stanja delimično uredjen relacijom susedstva koja je odredjena skupom pravila P, zove se prostor stanja. Sistemi produkcije zgodno je prikazivati usmerenim grafovima G=(X,F). X- skup čvorova koji odgovaraju N stanjima. F- skup čvorova naslednika u skupu X koji su pravila produkcije odredjeni kao susedni čvorovi.
Slika1 Rešenje zadataka heurističkog pretraživanja je nalaženje i izdvajanje puta koji povezuje početni čvor sa završnim čvorom. Taj put zove se rešavajući put. Cilj je da u generisanom podgrafu bude sadržan bar jedan rešavajući put. Sistem redukcija u suštini se oslanja na svodjenje datog zadatka na podzadatke. Terminalni korak u sistemu redukcije sastoji se u prepoznavanju stanja St=(St=»St). Rešenje zadatka u sistemu redukcije je niz R-stanja dostupnih primenom neterminalnih koraka. Počevši od početnog stanja i završno sa stanjem na koje je primenljiv terminalno korak.
5. FORMALNA POSTAVKA YADATAKA HEURISTIČKOG PRETRAŽIVANJA – I/ILI GRAFOVI
I/ILI grafovi su propozicioni grafovi za predstavljanje prostora R-stanja. Svaki čvor I/ILI grafa redstavlja jedan pod zadatak, tj. Odredjena R-stanja, a grana grafa predstavljaju operatore svodjenja na podzadatke. Razlikuju se dva tipa čvorova: konjuktivni I čvorovi ili disjunktivni ILI čvorovi. Za rešenje datog zadatka treba rešiti sve zadatke u I čvorovima ili bar jedan od zadataka u ILI čvorovima. Terminalnim čvborovima odgovara Bulova konstanta 1, a Bulova konstanta 0 odgovara nerešivom zadatku.
6. OBLICI PREDSTAVLJANJA ZNANJA ( deklarativni, semantički,procedurni)
Metode predstavljanja mogu se razlikovati po: opisu, nivou definisanja osnovnih objekata i relacija, formalnim modelima rešavanja zadataka. Izdvajaju se triosnovne kalse metoda predstavljanja: deklarativna, procedurna i semantička predstavljanja. Deklarativna predstavljanja – zadaju se potpunim opisom stanja i skupom operatora. Osnovne karakteristike deklarativnog predstavljanja su: - razlikovanje mehanizma pretraživanja i mehanizma upravljanja, - neophodnost rada sa potpunim opisom stanjana svakom koraku procesa rešavanja zadataka. Procedurno predstavljanje- zasniva se na opisu manupulacije objektima i relacijama u vidu procedura. Rešenje zadatka se sastoji u odredjivanju niza procedura, od kojih svaka obradjuje neku lokalnu oblast baze. Nosioci ove klase predstavljanja su problemski orijentisani jezici. Oni sadrže mehanizme za automatsko traženje rešenja na osnovu baze znanja i postavljenog cilja. Karakteristike: - semantička znanja odražena su u samim procedurama i njohovoj interakciji i povezivanju u procesu rešavanja zadataka. - u problemski orijentisane jezike ugradjen je velik broj specijalizovanih strategija i pravila - hijerarhijska podčinjenost procedura omogućuje rad na višem nivou opisa i skraćivanje rešavajućeg niza procedura. Problemski orijentisani jezici efikasniji su samo u oblasti za koje su namenjeni. Semantička predstavljanja: - izgradjuju se na ideji da se semantičko znanje direktno i neposredno odrazi u formalizme predstavljanja i na taj način izbegne podvojenost strukrurnog i senantičkog znanja. To se ostvaruje konstrukcijom semantičke mreže koja sadrži pojmove i semantičke veze medju njima. Karakteristike: - opis objekata daje se na nivou prorodnog jezika - sva znanja, nove činjenice, specijalne i tipične metode rešavanja skupljaju se u relativno jednorodnoj strukturi. - Metode izvodjenja zajedno sa ciljevima odredjuju onaj deo semantičkog znanja koje će se koristiti pri rešavanju. Neuralne mreže i frejmovi su posebni vidovi ovog tipa predstavljanja.
7. STRATEGIJE PRETRAŽIVANJA U PROSTORU STANJA
Strategijom pretraživanja odredjuju se stanja koja će biti posećena u procesu traženja rešavajućeg puta i prostoru stanja. Glavni ciljevi uvodjenja u kontrolne strategije pretraživanja su: -sužavanje prostora pretraživanja - usmeravanje pretraga u pravcu perspektivnog rešenja. Izbor kontrolne strategije bitno je uslovljen znanjima o domenu problema koji se rešava. Tu su karakteriskične sl. extremne mogućnosti: - odsustvo ikakvih znanja o problemskoj oblasti - potpuno znanje o problemskoj oblasti Sve kontrolne strategije mogu se podeliti u 2 tipa: nepovratne strategije i probne strategije. Nepovratne strategije- karakteristične su po tome što je izbor stanja i operatora koji će se promeniti na to stanje neopoziv, definitivan i ne podleže naknadnoj korekciji. Probne strategije dopuštaju naknadne korekcije. Razne tipove sintaksnih kao i heurističkih metoda pretdage moguće je predstaviti grafovima. Metode pretrage razlikuju se po redosledu otvaranja čvorova.
8. SINTAKSNE STRATEGIJE PRETRAŽIVANJA
Ne uključuju semantička znanja nego obezbedjuju da se pretraži kompletan prostor. U zavisnosti od redosleda otvaranja čvorova razlikuju se dva osnovna tipa sintaksničkih pretraga: pregled u širinu, pregled u dubinu. Pregled u širinu – najpre se otvara početni čvor i generišu se svi njegovi sledbenici. Tako generisani čvorovi pripadaju prvom nivou. Počev od prvog nivoa na svakom daljem nivou čvorovi se otvaraju u redosledu kako su generisani. Otvaranje čvorova se prekida kada je generisan neki završni čvor. Pregled u dubinu – polazeći od početnog čvora, za svaki generisani čvor generiše se njegov jedan sledbenik. Na taj način generišu se čvorovi koji se nalaze na sve većoj i većoj dubini. Mogući su sl. ishodi takve pretrage: - na nekoj dubini generisan je završni čvor, - generisan je čvor koji nema sledbenika, - generisani čvorovi pripadaju beskonačnoj gradi drveta.
9. HEURISTIČKO PRETRAŽIVANJE
Za usmeravanje pretrazivanja koristi se heuristička informacija. Heurističku informaciju sačinjavaju posebna pravila i druga znanja, tzv. Heuristike od koristi za skraćivanje i ubrzavanje pretraživanja. Heuristike za pretragu prostora stanja usmerene su na: - Izbor perspektivnog operatora, - izbor perspektivnog čvora. Zavisno od izbora heurističke f-je, razlikuju se dva tipa heurističke pretrage: 1. bez gubitka puta minimalne cene 2. sa gubitnom puta min. cene. Heuristike mogu da uključe neka opšta znanja, ali su najefikasnija ona koja koriste znanja o domenu problema koji se rešava.
Smisao uvojdenja f-je ocene je da se pomoću nje izvrši rangiranje u skupu čvorova i odredi redosled njihovog otvaranja. Domen f-je ocene je skup čvorova, a antidomen je skup realnih brojeva. Algoritni pretraživanja koji koriste f-je ocene zovu se algoritni uredjenog pretraživanja. Algoritam A* uz odredjene predpostavke obezbedjuje otvaranje najmanjeg broja čvorova uz nalaženje rešavajućeg puta minimalne cene. Zato ga ponekad nazivaju optimalnim algoritmom. Algoritam se zasniva na f-ji cene oblika f(n)=g(n)+h(n). F-ja g(n) predstavlja vrednost cene puta od početnog čvora do čvora n. F-ja h(n) predstavlja domenski orijentisanu heurističku procenu minimalne cene puta od čvora n do nekog završnog čvora. h(n) – se zove heuristička f-ja.Pretraga se vrši tako što se kreće od početnog čvora i na svakom koraku sa lista raspoloživih čvorova bira se onaj čvor u kojem f-ja f ima najmanju vrednost.
16. PROCEDURA POBIJANJA I POLUODLUČIVOSTI
Teorema o rezoluciji: Konačan skup sastavaka S je nezadovoljiv akko skup Rn (s) za neko konačno n>0 sadrži prazan sastavak. Na osnovu teoreme o rezoluciji može se izgraditi sl. procedura pobijanja: - za konačan skup sastavaka S primenom pravila rezolucije odredjuju se skupovi R1(S) , R2(S)...pri čemu može nastati jedan od sl. ishoda: 1. za neko konačno n>=0 skup Rn (s) sadrži prazan sastavak, pa je S nezadovoljiv. 2. za neko konačno n>=0 , Rn (s)=Rn+1(S) pa je S zadovoljiv. 3. procedura beskonačno generiše rezolvente što je u vezi sa neodlučivošću predikatskog računa prvog reda. Procedura pobijanja koja se gradi neposredno na osnovu teorema o rezoluciji ima više teorijski nego praktičan značaj jer brojnost skupova R1(S) sa povećanjem i naglo raste.
20. UPITNI DIJALOŠKI SISTEMI
Poznato je da složena pitanja dovode do složenog dokaza, a to ne daje precizne odgovore. Ovo se rešava pomoću ADT. Prvi postupak je:1. sastavci koji potiču od negacija teoreme pretvaraju se u tautologije; 2. ako sastavci iz negacija teoreme sadrže skolemove f-je one se zamenjuju novim promenljivim; 3. ponavlja se rezolucijsko pobijanje; 4. kao rezultat na mesto praznog sastavka stoji formula koja predstavlja traženi odgovor. Drugi postupak: 1. Uvodi se nov predikat odgovor (x) u sastavak dobijen iz negacije teoreme; 2. ponavlja se rezolucijsko pobijanje vršenjem istih rezolucija 3. kao rezultat na mesto praznog sastavka dobje se predikat. Odgovor sa odredjenom vrednošću promenljive x. Na izloženim idejama temelji se jezik logičkog programiraga PROLOG.
22. LOGIČKO PROGRAMIRANJE- karak. prologa
Prolog – je neprocedurni opisni jezik logičkog programiranja. Ovde korisnik saopštava računaru šta treba da radi; a ne kako to da radi. Prolog sistem se sastoji od procedura koje odredjuju kako se neka izvodjenja realizuju. Prolog jezik saopštava sistemu šta treba da radi, a ne kako se to radi. Saopštava se opis ciljeva i uslova a ne način zadovoljenja cilja. Prolog jezik je zasnovan na predikatskom računu I reda. Karakteristike prologa: 1. Prolog sistem je zasnovan na rezolucijskoj metodi pobijanja koja je ograničena na hornove sastavke koji se zapisuju u obliku klauzula 2. Prolog jezik sadrži tri vrste rečenmica ciljevi, pravila i činjenice. 3. Rezolucija se svodi na unifikaciju elemenata cilja sa glavom neke klauzule 4. Polazni cilj je zadovoljen ako se generiše prazan cilj. 5. Moguće nalaženje više različitih načina zadovoljenja cilja 6. Procedura pretraživanja podržava primenu rekurzije 7. Prolog sistem podržava vraćanje i rezoluciju 8. Prolog programi mogu se tumačiti deklarativno i proceduralno 9. Prolog sistem podrzava rad sa listama i binarnim stablima. 10. Primene prologa su raznovrsne.
24. FUNKCIONISANJE PROLOG SISTEMA- višestruko zadovolj. cilja
Cilj zapisan u prolog jeziku je zadovoljen ako prolog sistem izvede prazan podcilj. Izvodjenje praznog cilja prolog sistem pokušava da ostvari na osnovu činjenica i pravila, tj. Znanja sadržanih u prolog programu. Prolog sistem omogućuje nalaženje više različitih načina za zadfovoljenje postavljenog cilja. To znači da porlog sistem nalazi različite dokaze iste teoreme.
25. NALAŽENJE REKURZIJE U PROLOGU
Prolog podržava rad sa rekurzijama. Rekurzija se pojavljuje kad god neku relaciju odredjujemo pomoću nje same. Rekurzija može biti leva i desna. Rekurzija je levo rekurzivna kada se prvi literal u telu klauzule može unificirati sa glavom te klauzule. a( x,y):-b(x,y) a( x,y):-b(x,z), c(z,y) -prvo pravilo je nerekurzivno;-drugo pravilo je rekurzivno.Ovo drugo pravilo je desno rekurzivno.Za rayliku od njega pravilo a(x,y):-a(z,y),b(a,z) je levo rekurzivno.
26.VRACANJE I REZ U PROLOGU
Procedura pretrazivanja radi zadovoljenja cilja moze se vrsiti strategijom u dubinu i to plitko ili duboko.Ako je generisan čvor neuspeha atomatski se vraća na predhodni čvor, aa ukoliko je generisan čvor uspeha prelazak sa tog čvora se vrši tek kada se ispune zahtevi za zadovoljenje cilja. Procedura pretraživanja sadrži osobinu selekcije tj. Odsecanja grana. Grane se odsecaju jer se u procesu vraćanja neće generisati. Ovaj proces odsecanja grana naziva se raz. Prisustvo reza u prolog programu odredjuje koje će grane biti odsečene. Odsecanje delova stabla pretraživanja je korisno jer se time smanjuje prostor pretrage i ubrzava nalaženje zadovoljenja cilja.
27. PROBLEMI NEGACIJE I KONAČNOG NEUSPEHA U PROLOGU
Prolog ne dozvoljava da su u glavi klauzule nadju elementi koji su negirani. Negacija se tretira na specifičan način. Ta specifičnost se ogleda u sl. načinu generisanja podciljeva za slučaj kada je podcilj ili elemenat podcilja negiran. Neka je cilj ?- c1,c2,.....cn gde je c1 oblika not c1'. Ako cilj c1' ima konačno stablo pretraživanja sa granom uspeha, onda čvor u kojem je ?- c1,...ck. nema potomka (čvor neuspeha). Ako cilj c1' ima konačno stablo pretraživanja bez i jedne grane uspeha ondaje potomak čvora ?-not c1', C2....ck. Čvor sa podciljem ?-c2,.....ck. nemogućnost konačnog cilja c1' (konačan neuspeh) znači da je u skupu uslova sadržanih u prolog programu cilj c1' netačan, Pa je cilj not c1' zadovoljen kao tačan.
34. MERLJIVA OBELEŽJA I REŠAVAJUĆE F-JE
Za predstavljanje najpogodniji su oblici kod kojih su sva obeležja merljiva. Svako obeležje se predstavlja realnim brojem pa se obliku prodružuje vektor x=(x1,x2,...xn). Posebna vrsta merljivih obeležija su binarna obeležja. Ako obeležja nisu merljiva onda se oblici zapisuju na neki durgi način. Jedan od njih je opis hijerarhijeskih veza. Prilikom izbora obelezja razlikuju se bitna i nebitna obeležja. Potpun sistem obeležja ispunjava sl. 2 uslova: 1, svaka dva predstavnika iste kalse imaju slična obeležja 2, kod predstavnika različitih klasa obeležja su različita. U praksi postoje vremensko-prostorna ograničenja, pa se treba zadovoljiti približnim rešenjem. Algoritamsko klasifikovanje oblika vrši se pomoću rešavajućih f-ja. To su f-je na osnovu čijih vrednosti se vrši klasifikacija. Opšti oblik linearno rešavajuće f-je dopisati
38. MOGUĆNOST DAVANJA OBJAŠNJENJA U E.S.
Kada E.S. saopšti korisniku rezultat svog rada korisnik je u mogućnosti da vidi putanju kako se do rezultata došlo. Postoje IV tipa obješnjenja koja su rasprostranjena u raznim E.S.
Sistem daje korisniku šifre pravila i činjenice koje je koristio i to po redosledu korišćenja. 1. Na ovaj način korisnik je u
39. RAD SA PODACIMA RAZLIČITE POUZDANOSTI
Do sada se smatralo prilikom rada sa podacima i činjenicama da su podaci i činjenice tačni. Medjutim ispostavilo se da to nije tako. Iz tih razloga potrebno je govoriti o stepenu pouzdanosti izražavanje mere pouzdanosti najpogodnije je vršiti numerički, pomoću odgovarajućih verovatnoća. Verovatnoća se može izražavati brojevima od 0-1 ili procentualno. Prilikom rada sa nepouzdanim pravilima i činjenicama mogu se javiti sl. vrste problema: 1. cinjenica 100% pouzdana, zaključak pravila nepouzdan 2. činjenice različite pouzdanosti, pravilo 100% pouzdano. 3. Nepouzdane činjenice i nepouzdano pravilo.
40. FUZZY EKSPERTNI SISTEM
Kod formalne logike rezonovanje se vrši sa dve vrednosti (tačno, netačno), a fuzzy logika koristi vrednosti (0,1). Medjutim, kako je u prirodi vrlo teško objasniti neke pojave sa stanjima koja se medjusobno isključuju fuzzy logika omogućava opisivanje tzakvih »nepreciznih stanja» . Kako se neuronske mreže fuzzy logikom medjusobno dopunjuju fuzzy neuronske mreže su predstavljene sa tri sloja: 1. u ovom slučaju ulazni podaci koji ovde stižu množe se koeficijentom linarnosti da bi izlaz iz prvog sloja bio u opsegu (0,1) i to u domenu fuzzy signala. Ovde se vrši fuzzyfikacija. 2. drugi skriveni sloj je nelinearan. Ulazni podaci se množe sa težinskim keoficijentom, a zatim sabiraju sa pragom eksitacije. Zatim se ovi rezultati preslikavaju u nelinearnu f-ju. Ovo predstavlja izlaze srednjeg sloja. Ovo vrši fuzzy rezonovanje. 3. Treći sloj omogućuje da vrednosti sredn jeg sloja iz opsega (0,1) prevede u opseg za izlaz. Ovaj sloj se naziva proces defuzzyfikacije.
Automatsko rezonovanje-teorijski konce. i primene
Dva ključna problema vezana su za razvoj veštačke inteligencije i automatsko rezonovanje: - mogućnost formalizacije neformalno postavljenih zadataka, - nalaženje dovoljno efikasnih strategija i procedura pretraživanja u mnoštvu varijanata.
Od uspeha u njihovom rešavanju zavisi praktično ostvarivanje potencijalnih mogućnosti.
Bitna komponenta svakog rezonovanja je sposobnost zaključivanja. Na zaključivanju se temelje sposobnosti učenja, otkrivanja primera i kontraprimera, uočavanje analogija, prepoznavanje objekata i druge. Posebno značajno mesto u tome pripada logičkom zaključivanju, tj. izvođenju posledica iz datog skupa premisa. Logičko izvođenje se može svesti na problem dokazivanja teorema. Zato je jedan od ključnih aspekata formalizacije rezonovanja, razrada deduktivnih sistema koji omogućuju realizaciju automatskog dokazuvanja teorema. Cilj automatskog dokazivanja teorema jeste projektovanje i im- plementacija računarskih programa koji dokazuju. ili pomažu pri dokazivanju teorema. U početku je primena programa za dokazivanje teorema bila isključivo u oblasti matematike a posle I u oblastima kao što su: korektnost programa, generisanje programa, upitni jezici nad relacionim bazama podataka, projektovanje elektronskih kola, izgradnja ekspertnih sistema itd...
12.Metoda rezolucije
Tvrđenje koje je izraženo formulom A je posledica premisa izraženih formulama A1,A2,...,Ak , ako se iz formule A dobija tačno tvrđenje u svim onim interpretacijama u kojima se iz premisa A1,A2,...,Ak dobijaju tačna tvrđenja. U sintaksnom smislu, takva formula A je izvodljiva primenom formalnih pravila izvođenja iz skupa formula {A1,A2,...,Ak}. U semantičkom smislu ADT je proces utvrđivanja da je tvrđenje koje je izraženo formulom A posledica premisa izraženih formulama A1,A2,...,Ak. U formalnom smislu ADT je procedura kojom se utvrđuje da je formula A izvodljiva primenom pravila izvođenja iz skupa formula {A1,A2,...,Ak}. Formula A zove se teorema, a formule A1,A2,...,Ak su hipoteze koje se tretiraju kao aksiome. Kako smo već ranije videli, izvođenje formule A iz hipoteza A1,A2,...,Ak ekvivalentno je utvrđivanju fakta da je formula A1 ^ A2 ^ ... ^ Ak Þ A valjana. Postoje različiti prilazi za realizaciju takve automatske procedure. U ovom odeljku razmatramo prilaz koji se zasniva na rezolucijskoj metodi pobijanja.
Metode pobijanja temelje se na sledećem stavu: A1,A2,...,Ak ½¾ A ako i samo ako A1,A2,...,Ak,ØA ½¾ protivrečnost. Uopšte, izgrađivanje izvođenja F ½¾ A može se zameniti pobijanjem skupa FÈ{ØA}. 13.Skolemizacija i skup sastavaka Neka je Ax(t) oznaka za formulu određenu iz formule A(x) zamenom svakog slobodnog ulaženja promenljive x termom t, pri čemu je t slobodan za x u A(x).
Navodimo prvo opis procesa skolemizacije. Formula u preneksnoj formuli je univerzalna, ako su svi kvantifikatori u njenom prefiksu univerzalni. Neka je A zatvorena formula u preneksnoj normalnoj formi. Formula A* koja ne sadrži kvantifikatore određuje se na sledeći način: 1. Ako je A univerzalna, tj. oblika "x1 ..."xn B, gde n³0 i B ne sadrži kvantifikatore, onda je A* formula B. 2. Ako je A oblika "x ..."x $yB, n³0, uvodi se nov n-arni funkcijski simbol f; u slučaju n=0 f je nova konstanta. Neka je A° oznaka za formulu "x1 ..."xn B (f(x1 ,...,xn )). Formula A° sadrži jedan egzistencijalni kvantifikator manje od formule A. Ako A° nije univerzalna, postupak se ponavlja, tj. grade se formule A°° ,A°°° itd., sve dok se ne dobije univerzalna formula. Iz nje se A* određuje prema 1. Kažemo da je A* dobijena iz A skolemizacijom. Svaka zatvorena formula predikatskog računa prvog reda može se transformisati u skup sastavaka primenom sledećeg postupka:
1. Vrši se preoznačavanje promenljivih tako da različita ulaženja kvantifikatora vezuju različite promenljive 2. Eliminišu se simboli Û i Þ uzastopnom primenom zamena 3. Negacija se dovodi neposredno ispred predikatskih simbola primenom zamena: 4. Formula se dovodi u preneksnu formu primenom zamena: 5. Izvrši se skolemizacija preneksne forme. 6. Formula (bez kvantifikatora) dovodi se u konjunktivnu normalnu formu. 7. Eliminišu se simboli Ù zamenom A Ù B sa dve formule A,B.
Primenom (1) - (7) određuje se konačan skup formula od kojih je svaka disjunkcija konačnog broja atomičnih formula ili njihovih negacija.
Atomičnu formulu ili njenu negaciju zovemo literal.
Sastavak je disjunkcija literala.
Prema tome, primenom (1)-(7) na datu formulu određuje se skup sastavaka 14.Zamene, unifikacija i algoritam unifikacije Zapis oblika t/x, gde je x promenljiva i t term različit od x, zove se zamenska komponenta; x je promenljiva i t je term zamenske komponente t/x. Konačan skup zamenskih komponenti q={t1/x1,...,tn/xn} , gde xi ¹ xj za i¹j , zove se zamena. Prazan skup zamenskih komponenti zove se prazna zamena. Zamena q je unifikator skupa C, gde je C skup terma ili skup literala, ako je Cq jednočlan skup. Ako za skup C posotji unifikator q, kaže se da q unificira skup C, odnosno da je C unifikativan skup.
Očevidno, ako je q unifikator za skup A, onda q unificira i skup neslaganja B za skup A. Unifikativan skup A može imati više unifikatora.
Definicija 9. Neka su q i s unifikatori skupa literala A. Unifikator s je najopštiji unifikator (NOU) skupa A, ako za ma koji unifikator q skupa A posotji zamena l takva da je q=sl. Algoritam unifikacije za kona;an neprazan skup literala
1. korak Staviti k=0 i s0=e (e-prazna zamena). Preći na 2. 2. korak Ako Ask nije jednočlan skup, preći na 3. U suprotnom, staviti s=sk i završiti rad. korak Neka je Vk prvi, a Uk sledeći element u leksikografskom poretku uređenog skupa neslaganja Bk za Ask. Ako je Vk promenljiva, koja ne ulazi u Uk , onda odrediti sk+1=sk{Uk/Vk}(kompozicija sk i {Uk/Vk}), uvećati k za 1 i preći na 2. U suprotnom, prekinuti rad i saopštiti da unifikator za skup A ne postoji. Drugačije rečeno, NOU maksimalno održava (čuva) promenljive. Dokazano je da algoritam unifikacije završava rad za svaki neprazan konačan skup literala i da je u slučaju kad algoritam završava rad na 2. koraku, zamena s ustvari traženi NOU.
15.Pravilo rezolucije – teorema potpunostiDefinicija rezolventeNeka za sastavke D1 i D2, koji ne sadrže zajedničke promenljive (to se uvek može postići preoznačavanjem promenljivih), i za literale L1ÍD1, L2ÍD2 važe uslovi: (1) Skupovi L1 i L2 nisu prazni, (2) Za skup A svih atomičnih formula sadržanih u L1ÈL2 postoji NOU sA, (3) Elementi jednočlanih skupova L1sA i L2sA obrazuju komplementaran par. Rezolventa sastavaka D1 i D2 je sastavak (D1\L1)sAÈ(D2\L2)sA. Definicija rezolucije
Neka su D1 i D2 sastavci za koje su ispunjeni uslovi (1) - (3) i R njihova rezolventa. Pravilo izvođenja:
Neka je Â(C)defCÈF , gde F skup svih rezolventi elemenata skupa C. Za skup sastavaka S, skup Ân(S) definiše se na sledeći način: 1. Â0(S) = S ; 2. Ân+1(S) = Â(Ân(S)), n³0. Teorema o rezoluciji Konačan skup sastavaka S je nezadovoljiv akko skup Ân(S) za neko konačno n³0 sadrži prazan sastavak. Pobijanje (opovrgavanje) datog skupa sastavaka S je konačan niz sastavaka B1,...Bk, takav da za svaki član Bi, 1£i£k, važi: 1. BiÎS ili Bi je rezolventa neka dva prethodna člana niza, 2. Bk je prazan sastavak.
Sledi, pobijanje datog skupa sastavaka S je izvođenje praznog sastavka iz skupa S, pri čemu skup pravila izvođenja sadrži samo pravilo rezolucije.
Iz teoreme o rezoluciji sledi: Konačan skup sastavaka S je nezadovoljiv akko postoji pobijanje za S.
Zato je teorema o rezoluciji ujedno i teorema o potpunosti ovog logičkog sistema.
17. Specifične forme rezolucije (OL rezolucija) OL-rezolucija: uređena linearna rezolucija sa markiranim literalima
Povećanje efikasnosti linearne rezolucije, bez narušavanja potpunosti, postiže se uvođenjem uređenih sastavaka i informacije o rezolviranim literalima.
Informacija o rezolviranim literalima čuva se tako što se prilikom rezolucije ne odbacuju komplementarni literali, već se u rezolventi zadržava literal koji pripada prvom sastavku. Taj literal se na neki način markira. Sada se celokupan postupak određivanja OL-rezolvente može opisati na sledeći način. Neka je D1 centralni sastavak i D2 bočni sastavak. 1. Preoznačavanje promenljivih (tako da u sastavcima ne bude zajedničkih promenljivih). 2. Određivanje NOU za poslednji literal u D1 i k-ti (k=1,2,...) iz D2 (ako postoji za neko k, ako ne postoji onda se OL-rezolventa datih sastavaka ne može odrediti). 3. Formiranje rezolvente markiranjem poslednjeg literala u D1q i dopisivanjem ostatka sastavka D2q bez k-tog literala. 4. Isključivanje nemarkiranih literala identičnih mlađem literalu u rezolventi i ispitivanje tautologičnosti. 5. Operacija skraćivanja (brisanje svih markiranih literala iza kojih nema nemarkiranih). 6. Operacija sažimanja (brisanje poslednjeg nemarkiranog literala kada je on komplementaran nekom markiranom za neki unifikator l). 7. Ponovna primena koraka 5 i 6 sve dok je to moguće (dok se na poslednji nemarkirani literal ne bude mogla primeniti operacija sažimanja, ili dok se ne dobije prazan sastavak p).
Podesi kao favorit
Bookmark
Čitanja: 12317 Komentari (0)
 Napišite komentar
|
RSS link na komentare
