44090454 Inteligenta Artificial A Inferenta in Logica Propozitionala Si Predicativa

Download 44090454 Inteligenta Artificial A Inferenta in Logica Propozitionala Si Predicativa

Post on 28-Aug-2014

64 views

Category:

Documents

5 download

Embed Size (px)

TRANSCRIPT

<p>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</p> <p>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</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>2</p> <p>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</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>3</p> <p>Logica i limbajul natural</p> <p>n limbajul natural, multe propoziii sunt ambigue i pentru ele exist mai multe moduri de reprezentare</p> <p>Reprezentrile simple sunt preferabile, ns pot face imposibile unele tipuri de raionament</p> <p>Logica aduce formalizarea codrii cunotinelor</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>4</p> <p>Logica propoziional</p> <p>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</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>5</p> <p>Formule bine formate</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>6</p> <p>Propoziie</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>7</p> <p>Deducie. Teorem</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>8</p> <p>Tautologie</p> <p>Demonstrare semantic9</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>Teorema de completitudine a calculului propoziional</p> <p>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 </p> <p>Orice tautologie poate fi dedus pe cale sintactic Orice propoziie adevrat n orice caz este o teorem i poate fi folosit ulterior pentru inferene10</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>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</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>11</p> <p>Metode de inferen: MP, MT</p> <p>Modus ponendo ponens (prescurtat Modus Ponens) </p> <p>Modus tollendo tollens (prescurtat Modus Tollens) </p> <p>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</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>12</p> <p>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</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>13</p> <p>Reguli de transformare a formulelor (I)</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>14</p> <p>Reguli de transformare a formulelor (II)</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>15</p> <p>Forma normal conjunctiv </p> <p>engl. Conjunctive Normal Form O conjuncie de disjuncii</p> <p>un I de SAU-uri</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>16</p> <p>Transformarea n FNC</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>17</p> <p>Transformarea eitin (I)</p> <p>G.S. Tseitin - On the complexity</p> <p>of derivation in propositional calculus, Studies in Constructive</p> <p>Mathematics and Mathematical Logic, part 2, pp. 115-125, 1968</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>18</p> <p>Transformarea eitin (II)</p> <p>Evit expandarea exponenial</p> <p>Rezultatul este proporional cu dimensiunea formulei originare</p> <p>Noua formul poate s nu fie echivalent cu formula originar</p> <p>De exemplu dac xi = fals</p> <p>Formula originar este (ne)satisfiabil dac i numai dac formula nou este (ne)satisfiabil</p> <p>Proprietate necesar pentru procesul de rezoluie</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>19</p> <p>Rezoluia propoziional (I)</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>20</p> <p>Rezoluia propoziional (II)</p> <p>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</p> <p>Se bazeaz pe reducere la absurdFlorin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>21</p> <p>Demonstrarea semanticTermenii nu sunt echivaleni, dar implicaia este adevrat</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>22</p> <p>Exemplul 1</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>23</p> <p>FNC</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>24</p> <p>Procesul de rezoluie</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>25</p> <p>Exemplul 2</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>26</p> <p>FNC</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>27</p> <p>Rezoluia</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>28</p> <p>Rezoluia</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>29</p> <p>Rezoluia</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>30</p> <p>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</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>31</p> <p>Logica predicatelor</p> <p>Formulele depind de variabile</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>32</p> <p>Exemple</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>33</p> <p>Reducerea la inferena propoziional</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>34</p> <p>Reducerea la inferena propoziional</p> <p>Orice formul predicativ de ordinul I poate fi propoziionalizat Mulimea de termeni ar putea fi infinit</p> <p>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</p> <p>Teorema lui Herbrand</p> <p>Ordinul termenilor crete iterativ n adncime </p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>35</p> <p>Forma normal conjunctiv</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>36</p> <p>Exemplu: transformarea n FNC</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>37</p> <p>Transformarea n FNC</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>38</p> <p>Transformarea n FNC</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>39</p> <p>Transformarea n FNC</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>40</p> <p>Transformarea n FNC</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>41</p> <p>Substituia</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>42</p> <p>Unificarea</p> <p>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</p> <p>43</p> <p>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</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>44</p> <p>Raionamentul nainte</p> <p>Clauz Horn definit </p> <p>Disjuncie n FNC cu un singur termen pozitiv Formula este echivalent cu o implicaie</p> <p>Procedur de cutare</p> <p>Descoperirea unei ci n spaiul problemei care conduce de la starea iniial la starea scop</p> <p>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</p> <p>45</p> <p>Raionamentul nainte</p> <p>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</p> <p>46</p> <p>Exemplul 1</p> <p>Problema cnilor cu ap </p> <p>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:</p> <p>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)</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>47</p> <p>Exemplul 1</p> <p>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</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>48</p> <p>Exemplul 1</p> <p>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</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>49</p> <p>Exemplul 2</p> <p>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</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>50</p> <p>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)</p> <p>1. American(x) Weapon(y) Sells(x,y,z) Hostile(z) Criminal(x)M1: funcie Skolem, tratat ca un simbol</p> <p>Missiles are weapons:</p> <p>An enemy of America counts as hostile: West, who is American 6. American(West)5. Enemy(x,America) Hostile(x)</p> <p>The country Nono, an enemy of America 7. Enemy(Nono,America)</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>51</p> <p>Exemplul 2</p> <p>6</p> <p>2</p> <p>2</p> <p>7</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>52</p> <p>Exemplul 2</p> <p>4</p> <p>3</p> <p>5</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>53</p> <p>Exemplul 21</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>54</p> <p>Probleme (I)</p> <p>Potriviri redundante de reguli</p> <p>Raionament nainte incremental</p> <p>Fiecare fapt nou dedus n iteraia t trebuie derivat din cel puin un fapt nou dedus n iteraia t-1</p> <p>Algoritmul Rete (Clips)</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>55</p> <p>Probleme (II)</p> <p>Fapte irelevante </p> <p>Mulime magic: folosirea informaiilor din scop Exemplu: scopul este Criminal(West) Regula care are drept concluzie acest predicat: American(x)</p> <p> 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</p> <p>Acum n BC pot exista milioane de americani, dar inferena se poate face numai cu West</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>56</p> <p>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</p> <p>Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm</p> <p>57</p> <p>Raionamentul napoi </p> <p>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</p> <p>58</p> <p>Exemplul 1</p> <p>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 pen...</p>