44090454 Inteligenta Artificial A Inferenta in Logica Propozitionala Si Predicativa

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



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


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


5

Formule bine formate


6

Propoziie


7

Deducie. Teorem


8

Tautologie

Demonstrare semantic9


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


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


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


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


13

Reguli de transformare a formulelor (I)


14

Reguli de transformare a formulelor (II)


15

Forma normal conjunctiv

engl. Conjunctive Normal Form O conjuncie de disjuncii

un I de SAU-uri


16

Transformarea n FNC


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


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


19

Rezoluia propoziional (I)


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


22

Exemplul 1


23

FNC


24

Procesul de rezoluie


25

Exemplul 2


26

FNC


27

Rezoluia


28

Rezoluia


29

Rezoluia


30



31

Logica predicatelor

Formulele depind de variabile


32

Exemple


33

Reducerea la inferena propoziional


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


35

Forma normal conjunctiv


36

Exemplu: transformarea n FNC


37

Transformarea n FNC


38

Transformarea n FNC


39

Transformarea n FNC


40

Transformarea n FNC


41

Substituia


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



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)


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


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


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


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)


51

Exemplul 2

6

2

2

7


52

Exemplul 2

4

3

5


53

Exemplul 21


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)


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


56



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


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


60

Exemplul 2


61

Exemplul 2


62

Exemplul 2


63

Exemplul 2


64

Exemplul 2


65

Exemplul 2


66

Exemplul 2


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




69

Rezoluia predicativ


70

Exemplul 1


71

Exemplul 1


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


73

Exemplul 2


74

Exemplul 3


75

Exemplul 3: FNC


76

Exemplul 3: Rezoluia


77

Exemplul 4


78

Exemplul 4: FNC (I)


79

Exemplul 4: FNC (II)


80

Exemplul 4: FNC (III)


81

Exemplul 4: Rezoluia


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


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


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


85

44090454 Inteligenta Artificial A Inferenta in Logica Propozitionala Si Predicativa

Documents

forma normal

metode de

reguli de

avem de

modus ponens

modus tollens

face cu

raionamentul

Transcript of 44090454 Inteligenta Artificial A Inferenta in Logica Propozitionala Si Predicativa

02 Inferenta Test Ipot Power 2014

Curs3.PDF Logica Propozitionala

PRELUCRAREA DATELOR DE SONDAJ SI INFERENTA …PRELUCRAREA DATELOR DE SONDAJ SI INFERENTA STATISTICA Testarea ipotezelor statistice- II Stud. Master - AMP ISAIC- MANIU ALEXANDRU web

Inteligenta artificiala: Inferenta in logica propozitionala si predicativa

propozitia predicativa

Modul 4 Inferenta Statistica

Intervalul de Incredere. Inferenta Statistica

Paradigme de programareandrei.clubcisco.ro/cursuri/f/f-sym/2pp/cb/curs12.pdfLogicaogica cu predicate de ordinul 1 (FOL)cu predicate de ordinul 1 (FOL) • Extinde logica propozitionala

Curs 5 - planificarea experimentelor cross - over fileCurs 5 2 Inferenta statistic ă pentru efecte într-un experiment standard 2*2 cross – over Modelul statistic Consider ăm dou

Predicatul Si Subordonata Predicativa