44090454 inteligenta artificial a inferenta in logica propozitionala si predicativa

Click here to load reader

Post on 28-Aug-2014

398 views

Category:

Documents

30 download

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