44090454 inteligenta artificial a inferenta in logica propozitionala si predicativa
Embed Size (px)
TRANSCRIPT
Inteligen artificial6. Metode de inferen n logica propoziional i predicativFlorin LeonUniversitatea Tehnic Gh. Asachi Iai Facultatea de Automatic i Calculatoare http://florinleon.byethost24.com/curs_ia.htmFlorin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
Metode de inferen n logica propoziional i predicativ1. Logica propoziional 1.1. Modus Ponens 1.2. Modus Tollens 1.3. Rezoluia propoziional 2. Logica predicatelor 2.1. Raionamentul nainte 2.2. Raionamentul napoi 2.3. Rezoluia predicativ
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
2
Metode de inferen n logica propoziional i predicativ1. Logica propoziional 1.1. Modus Ponens 1.2. Modus Tollens 1.3. Rezoluia propoziional 2. Logica predicatelor 2.1. Raionamentul nainte 2.2. Raionamentul napoi 2.3. Rezoluia predicativ
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
3
Logica i limbajul natural
n limbajul natural, multe propoziii sunt ambigue i pentru ele exist mai multe moduri de reprezentare
Reprezentrile simple sunt preferabile, ns pot face imposibile unele tipuri de raionament
Logica aduce formalizarea codrii cunotinelor
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
4
Logica propoziional
Formalismul logic permite derivarea de noi cunotine din cunotine deja existente, prin deducie logico-matematic sau inferen O propoziie e adevrat dac deriv din propoziii cunoscute ca adevrate Domeniu strns legat de demonstrarea automat a teoremelor i inteligena artificial
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
5
Formule bine formate
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
6
Propoziie
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
7
Deducie. Teorem
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
8
Tautologie
Demonstrare semantic9
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
Teorema de completitudine a calculului propoziional
n calculul propoziional mulimea teoremelor coincide cu mulimea tautologiilor Noiunea de teorem este de natur sintactic, n timp ce noiunea de tautologie are o natur semantic Teorema subliniaz faptul c aceste noiuni sunt echivalente
Orice tautologie poate fi dedus pe cale sintactic Orice propoziie adevrat n orice caz este o teorem i poate fi folosit ulterior pentru inferene10
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
Metode de inferen n logica propoziional i predicativ1. Logica propoziional 1.1. Modus Ponens 1.2. Modus Tollens 1.3. Rezoluia propoziional2. Logica predicatelor 2.1. Raionamentul nainte 2.2. Raionamentul napoi 2.3. Rezoluia predicativ
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
11
Metode de inferen: MP, MT
Modus ponendo ponens (prescurtat Modus Ponens)
Modus tollendo tollens (prescurtat Modus Tollens)
Premise: P Q i P Concluzie: Q Lat. ponere = a pune, a afirma Modalitatea care afirmnd [P] afirm [Q] Afirmarea antecedentuluiPremise: P Q i non Q Concluzie: non P Lat. tollere = a lua, a nega Modalitatea care negnd [Q] neag [P] Negarea consecventului
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
12
Metode de inferen n logica propoziional i predicativ1. Logica propoziional 1.1. Modus Ponens 1.2. Modus Tollens 1.3. Rezoluia propoziional2. Logica predicatelor 2.1. Raionamentul nainte 2.2. Raionamentul napoi 2.3. Rezoluia predicativ
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
13
Reguli de transformare a formulelor (I)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
14
Reguli de transformare a formulelor (II)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
15
Forma normal conjunctiv
engl. Conjunctive Normal Form O conjuncie de disjuncii
un I de SAU-uri
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
16
Transformarea n FNC
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
17
Transformarea eitin (I)
G.S. Tseitin - On the complexity
of derivation in propositional calculus, Studies in Constructive
Mathematics and Mathematical Logic, part 2, pp. 115-125, 1968
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
18
Transformarea eitin (II)
Evit expandarea exponenial
Rezultatul este proporional cu dimensiunea formulei originare
Noua formul poate s nu fie echivalent cu formula originar
De exemplu dac xi = fals
Formula originar este (ne)satisfiabil dac i numai dac formula nou este (ne)satisfiabil
Proprietate necesar pentru procesul de rezoluie
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
19
Rezoluia propoziional (I)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
20
Rezoluia propoziional (II)
Ideea de baz a acestei forme de raionament este deducerea din dou propoziii, n care unul din termeni apare cu valori de adevr contrare, a unei concluzii din care este eliminat termenul respectiv
Se bazeaz pe reducere la absurdFlorin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
21
Demonstrarea semanticTermenii nu sunt echivaleni, dar implicaia este adevrat
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
22
Exemplul 1
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
23
FNC
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
24
Procesul de rezoluie
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
25
Exemplul 2
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
26
FNC
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
27
Rezoluia
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
28
Rezoluia
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
29
Rezoluia
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
30
Metode de inferen n logica propoziional i predicativ1. Logica propoziional 1.1. Modus Ponens 1.2. Modus Tollens 1.3. Rezoluia propoziional 2. Logica predicatelor 2.1. Raionamentul nainte 2.2. Raionamentul napoi 2.3. Rezoluia predicativ
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
31
Logica predicatelor
Formulele depind de variabile
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
32
Exemple
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
33
Reducerea la inferena propoziional
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
34
Reducerea la inferena propoziional
Orice formul predicativ de ordinul I poate fi propoziionalizat Mulimea de termeni ar putea fi infinit
Father(Father(Father(John)))Dac o propoziie este implicat de o baz de cunotine de ordin I, demonstraia implic o submulime finit a bazei de cunotine propoziionalizate Mai nti simbolurile constante: Richard, John Apoi la adncimea 1: Father(Richard), Father(John) .a.m.d. pn cnd demonstraia reuete
Teorema lui Herbrand
Ordinul termenilor crete iterativ n adncime
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
35
Forma normal conjunctiv
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
36
Exemplu: transformarea n FNC
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
37
Transformarea n FNC
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
38
Transformarea n FNC
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
39
Transformarea n FNC
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
40
Transformarea n FNC
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
41
Substituia
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
42
Unificarea
Unificarea returneaz o mulime de substituii Pot exista mai multe unificri posibile Pentru orice pereche unificabil de expresii exist cel mai general unificator (unic)Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
43
Metode de inferen n logica propoziional i predicativ1. Logica propoziional 1.1. Modus Ponens 1.2. Modus Tollens 1.3. Rezoluia propoziional 2. Logica predicatelor 2.1. Raionamentul nainte 2.2. Raionamentul napoi 2.3. Rezoluia predicativ
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
44
Raionamentul nainte
Clauz Horn definit
Disjuncie n FNC cu un singur termen pozitiv Formula este echivalent cu o implicaie
Procedur de cutare
Descoperirea unei ci n spaiul problemei care conduce de la starea iniial la starea scop
Cnd cutarea pornete din starea iniial ctre starea scop, avem de-a face cu un raionament nainteFlorin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
45
Raionamentul nainte
Dac procesul de cutare este modelat printr-un sistem de producie, rezolvarea problemei apare drept construirea unui arbore al operaiilor posibile Rdcina arborelui este starea iniial Nivelul urmtor al arborelui se completeaz prin determinarea tuturor regulilor a cror parte stng se potrivete nodului rdcin Noile noduri se creeaz prin intermediul prii drepte a regulilor considerate Procedura se repet pentru fiecare nod, pn cnd se genereaz o configuraie identic strii scopFlorin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
46
Exemplul 1
Problema cnilor cu ap
Avem la dispoziie 2 cni de capaciti diferite A i B Scopul este ca n cana A s rmn o cantitate specificat de ap prin aplicarea a 6 operaii posibile:
umple cana A (A) umple cana B (B) toarn apa din cana A n cana B (AB) toarn apa din cana B n cana A (BA) vars cana A (A) vars cana B (B)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
47
Exemplul 1
n figur se prezint arborele rezultat prin aplicarea celor 6 operaii unei probleme concrete: cana A are capacitatea de 4l, cana B are capacitatea de 3l iar n final n cana A trebuie s se obin un rest de 2l
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
48
Exemplul 1
Datorit complexitii sale, numai primul nivel a fost completat, n rest urmrindu-se drumul ctre soluia optim (calea cea mai scurt ctre scop) Se remarc faptul c nu exist o soluie optim unic, ea putnd fi atins pe dou ci diferite
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
49
Exemplul 2
The law says that it is a crime for an American to sell weapons to hostile nations. The country Nono, an enemy of America, has some missiles, and all of its missiles were sold to it by Colonel West, who is American. Trebuie demonstrat (scop): Col. West is a criminal
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
50
Exemplul 2... it is a crime for an American to sell weapons to hostile nations: Nono has some missiles: x Owns(Nono,x) Missile(x): all of its missiles were sold to it by Colonel West2. Owns(Nono,M1) and Missile(M1) 3. Missile(x) Owns(Nono,x) Sells(West,x,Nono) 4. Missile(x) Weapon(x)
1. American(x) Weapon(y) Sells(x,y,z) Hostile(z) Criminal(x)M1: funcie Skolem, tratat ca un simbol
Missiles are weapons:
An enemy of America counts as hostile: West, who is American 6. American(West)5. Enemy(x,America) Hostile(x)
The country Nono, an enemy of America 7. Enemy(Nono,America)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
51
Exemplul 2
6
2
2
7
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
52
Exemplul 2
4
3
5
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
53
Exemplul 21
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
54
Probleme (I)
Potriviri redundante de reguli
Raionament nainte incremental
Fiecare fapt nou dedus n iteraia t trebuie derivat din cel puin un fapt nou dedus n iteraia t-1
Algoritmul Rete (Clips)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
55
Probleme (II)
Fapte irelevante
Mulime magic: folosirea informaiilor din scop Exemplu: scopul este Criminal(West) Regula care are drept concluzie acest predicat: American(x)
Weapon(y) Sells(x,y,z) Hostile(z) Criminal(x) este rescris: Magic(x) American(x) Weapon(y) Sells(x,y,z) Hostile(z) Criminal(x) iar faptul Magic(West) este adugat n baza de cunotine
Acum n BC pot exista milioane de americani, dar inferena se poate face numai cu West
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
56
Metode de inferen n logica propoziional i predicativ1. Logica propoziional 1.1. Modus Ponens 1.2. Modus Tollens 1.3. Rezoluia propoziional 2. Logica predicatelor 2.1. Raionamentul nainte 2.2. Raionamentul napoi 2.3. Rezoluia predicativ
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
57
Raionamentul napoi
Spaiul problemei poate fi explorat i n direcie invers fa de cea urmat n cazul anterior Cnd cutarea pornete din starea scop ctre starea iniial, avem de-a face cu un raionament napoi Aici rdcina arborelui este starea scop Nivelul urmtor al arborelui se completeaz prin determinarea tuturor regulilor a cror parte dreapt se potrivete nodului rdcin Noile noduri se creeaz prin intermediul prii stngi a regulilor considerate Procedura se repet pentru fiecare nod, pn cnd se genereaz o configuraie identic strii iniialeFlorin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
58
Exemplul 1
Pentru problema cnilor cu ap, trebuie s facem unele precizri suplimentare pentru a o rezolva prin raionament napoi Cnd problema este rezolvat prin raionament nainte, n starea scop n cana B se poate gsi orice cantitate de ap Cnd problema este rezolvat prin raionament napoi, starea scop trebuie fixat pentru c de aici va ncepe raionamentul
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
59
Exemplul 1
S presupunem c dorim restul de 2l n cana A i 0l n cana B Nu toate cele 6 operaii se vor putea aplica pentru orice nod Vor exista constrngeri, de exemplu, dac la un anumit moment n cana A sunt 0l, este imposibil aplicarea primei operaii (umple A) Ar nsemna ca dup umplerea cnii, n ea s nu existe ap, ceea ce este absurd
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
60
Exemplul 2
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
61
Exemplul 2
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
62
Exemplul 2
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
63
Exemplul 2
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
64
Exemplul 2
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
65
Exemplul 2
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
66
Exemplul 2
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
67
Comparaie
Raionamentul nainte
Este dirijat de date (engl. data driven)
Recunoaterea obiectelor, decizii de rutin CLIPS
Poate determina ncercarea multor aciuni irelevante pentru atingerea scopului Este dirijat de scop (engl. goal driven) Unde sunt cheile de la main, cum pot gsi un serviciu bun
Raionamentul napoi
Prolog
Determin rezolvri cu o complexitate mult mai mic dect raionamentul nainte, dar are mai multe constrngeri68
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
Metode de inferen n logica propoziional i predicativ1. Logica propoziional 1.1. Modus Ponens 1.2. Modus Tollens 1.3. Rezoluia propoziional 2. Logica predicatelor 2.1. Raionamentul nainte 2.2. Raionamentul napoi 2.3. Rezoluia predicativ
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
69
Rezoluia predicativ
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
70
Exemplul 1
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
71
Exemplul 1
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
72
Exemplul 1
Se poate constata c a treia ipotez nu este necesar pentru demonstrarea concluziei
Dac pe al treilea nivel al arborelui am fi utilizat-o, nu am fi ajuns la o contradicie logic, ci am fi demonstrat c Geta nu este tatl lui Tudor
n general, dac exist mai multe posibiliti de substituie i unele ncercri nu dau rezultate, este nevoie de o cutare de tip backtracking pentru gsirea soluiei
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
73
Exemplul 2
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
74
Exemplul 3
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
75
Exemplul 3: FNC
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
76
Exemplul 3: Rezoluia
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
77
Exemplul 4
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
78
Exemplul 4: FNC (I)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
79
Exemplul 4: FNC (II)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
80
Exemplul 4: FNC (III)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
81
Exemplul 4: Rezoluia
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
82
Demonstrarea teoremelor n logica de ordinul nti
Turing, Church: problema demonstrrii teoremelor n logica de ordinul nti este semidecidabil
Se poate afla dac o propoziie se poate demonstra Nu se poate afla dac o propoziie nu se poate demonstra
Algoritmul de rezoluie poate rula la infinit
Problem echivalent cu determinarea opririi unei maini Turing83
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
Utilizri practice
Demonstratoarele automate de teoreme sunt folosite cu succes pentru:
Automatizarea demonstraiilor
Algebra Robbins Prima demonstraie formal riguroas pentru teorema incompletitudinii a lui Gdel Algoritmul de criptare RSA Algoritmul de string-matching Boyer-Moore Verificare CPU Proiectarea circuitelor Remote Agent (NASA Deep Space 1)84
Verificarea i sinteza componentelor software i hardware
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
Concluzii
Procesul de rezoluie este o modalitate convenabil de a deduce noi adevruri din premise multiple Un alt avantaj al su este posibilitatea aplicrii legilor logice, care au fost studiate intens Metoda beneficiaz de o formalizare strict, care asigur consistena deduciilor, nelsnd prea mult loc interpretrilor subiective
Exist i unele limitri; dac exist o demonstraie, metoda rezoluiei garanteaz gsirea ei, ns dac nu exist o astfel de demonstraie, algoritmul poate intra ntr-o bucl infinit n general, este imposibil de stabilit dac i cnd se va ntmpla acest lucru
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
85