Representacion del conocimiento

REPRESENTACIÓN DEL CONOCIMIENTO...
Abril 2010

Deducción en una base de conocimiento
•Teorema: BC p BC p

• Este teorema sugiere cómo implementar algoritmos para responder preguntas mediante una base de conocimiento • En escencia se trata de implementar procesos que buscan una secuencia de aplicaciones válidas de la regla de Modus Ponens que obtenga p como fórmula final

• Por tanto, sehace necesario algún algoritmo de búsqueda
• Esta búsqueda puede realizarse: • Hacia adelante: partiendo de BC

• Hacia atrás: partiendo de p

Representación de conocimiento

Encadenamiento hacia atrás proposicional
FUNCION ENCADENAMIENTO-HACIA-ATRAS-PROP (BC,p) Devolver ENCADENAMIENTO-HACIA-ATRAS-PROP-REC(BC,{p}) FUNCION ENCADENAMIENTO-HACIA-ATRAS-PROP-REC(BC,OBJETIVOS) 1. Si OBJETIVOSesta vacio, devolver EXITO y terminar 2. Hacer ACTUAL igual a SELECCIONA-UNO(OBJETIVOS)

3. Para cada elemento q ⇐ p1,...,pn (n ≥0) en BC tal que q=ACTUAL 3.1 Hacer NUEVOS-OBJETIVOS igual a {p1,...,pn}∪ (OBJETIVOS\{ACTUAL}) 3.2 Hacer RESULTADO igual a ENCADENAMIENTO-HACIA-ATRAS-PROP-REC(BC,NUEVOS-OBJETIVOS) 3.3 Si RESULTADO es EXITO, devolverlo y terminar 4. Devolver FALLO

Representación deconocimiento

representación de conocimiento
Encadenamiento hacia atrás proposicional • Si ENCADENAMIENTO-HACIA-ATRAS-PROP(BC,p) devuelve EXITO, entonces BC ⊢ p • completa (podría ser que BC ⊢ p y que el algoritmo no devolviera EXITO, debido a la posible existencia de ramas infinitas) •Estrategia de búsqueda:

• Búsqueda en profundidad
• Selección del objetivo a resolver: cualquier función deselección valdría • Orden de uso de las reglas de la base de conocimiento

Representación de conocimiento

representación de conocimiento
Lógica de primer orden
• Lenguaje de la lógica de primer orden • Símbolos de variable: x, y, ... • Símbolos de función (con su aridad): f, g, ... • Símbolos de predicado (con su aridad): p, q , ... • Conectivas: ¬, ∨, ∧, →, ↔ • Cuantificadores: ∀, ∃ •Términos de la lógica de primer orden • Las variables son términos • Si t1, . . ., tn son términos y f es un símbolo de función de aridad n, entonces f(t1,. . .,tn) es un término

Representación de conocimiento

representación de conocimiento
Lógica de primer orden
• Fórmulas de la lógica de primer orden • Si t1,. . .,tn son términos y p es un símbolo de función de aridad n, entonces p(t1,. ..,tn) es una fórmula (atómica) • Si F1 y F2 son fórmulas y x es una variable, también lo son F1 ∨ F2 F1 ∧ F2 F1 → F2 ¬F1 F1 ↔ F2 ∀x F1 ∃x F1

Representación de conocimiento

representación de conocimiento
Lógica de primer orden
• Consecuencia lógica: • Interpretación: un conjunto (universo) + asignación de funciones y relaciones concretas a los símbolos de función y predicado (en dichouniverso) • Una interpretación asigna un valor de verdad a cada fórmula • Consecuencia lógica: se dice que {F1,F2,. . .,Fn} I(Fi) = T para todo i =1,...,n, se tiene que I(G) = ⊤ Ejemplo: { ∀x(antecesor(y,x) → quiere(x,y)), antecesor(Pedro,Juan) } quiere(Juan,Pedro) G si para toda interpretación I tal que

Representación de conocimiento

representación de conocimiento
Ejemplo: base deconocimiento
Sean R = reglas y H = hechos resultado hechos regla

R1: hereda_de(x,y) ⇐ bueno(x), rico(y), quiere(x,y) R2: quiere(x,y) ⇐ amigo(x,y) R3: quiere(x,y) ⇐ antecesor(y,x) R4: antecesor(x,y) ⇐ progenitor(x,y) R5: antecesor(x,y) ⇐ progenitor(x,z), progenitor(z,y) H : progenitor(padre(x),x)

H : rico(Pedro) H : rico(padre(padre(Juan))) H : amigo(Juan,Pedro) H : bueno(Juan)

Representación deconocimiento

representación de conocimiento
Razonamiento hacia atrás con reglas de primer orden
•Se puede aplicar la misma idea que en el caso proposicional para diseñar un algoritmo de encadenamiento hacia atrás basado en la regla de Modus Ponens Generalizado •Dado un objetivo Q y una regla Q1 ∧ ... ∧ Qn → P, los nuevos objetivos podrían ser { (Q1), ... , (Qn) } si se encuentra una...