Source: https://www.scribd.com/doc/127471595/r34051
Timestamp: 2017-03-24 23:02:43+00:00

Document:
BrowseInterestsStay InformedCareerPersonal GrowthFiction & BiographiesHealth & FitnessLifestyleCultureBrowse byBooksAudiobooksNews & MagazinesSheet MusicBrowse allUploadSign inJoinCuaderno DidacticoLógica de Predicados Jose Lmilio Labra Gayo Daniel lernandez Lan·in Lscuela Uni·ersitaria de Ingeniería 1écnica en Iníormatica de O·iedo ,L.U.I.1.I.O., |virer.iaaa ae Orieao 1abla de Contenidos Introducción ......................................................................................................................................... 1 Lenguaje lormal de la Lógica de Predicados .................................................................................. 2 Otros Ordenes...................................................................................................................................... 6 Interpretación....................................................................................................................................... ¯ Consecuencia y Lqui·alencia Lógicas............................................................................................. 14 lormas Normales............................................................................................................................... 18 Algoritmo de Resolución.................................................................................................................. 23 Introducción............................................................................................................ 23 Resolución Proposicional ...................................................................................... 23 Resolución General ................................................................................................ 2¯ Uniíicación.......................................................................................................................................... 30 Algoritmo de Resolución General ................................................................................................... 35 Lstrategias de resolución....................................................................................... 44 Prueba de 1eoremas por Resolución.............................................................................................. 49 Bibliograíía.......................................................................................................................................... 51 Índice Alíabético................................................................................................................................ 53 Iníormación de Contacto ................................................................................................................. 56 Lógica de Predicados L.U.I.1.I.O. -1- Introducción Ln las últimas décadas, ha aumentado considerablemente el interés de la iníormatica por la aplicación de la lógica a la programación. De hecho, ha aparecido un nue·o paradigma de programación ,la programación declarati·a, cuyos íundamentos teóricos se basan en los desarrollos de la lógica de predicados que pretendían alcanzar sistemas de demostración automatica de teoremas. Ln este cuaderno didactico se describiran los conceptos basicos de esta disciplina aplicables a la iníormatica, en concordancia con el programa de la asignatura de Lógica pesente en el primer ano de los planes de estudio de Ingeniero 1écnico en Iníormatica de Sistemas e Ingeniero 1écnico en Iníormatica de Gestión impartidos en la Lscuela de Ingeniería 1écnica en Iníormatica de O·iedo ,LUI1IO,. Para su lectura no se necesita ningún conocimiento pre·io ya que se ·an deíiniendo todos los términos que aparecen. No obstante sería recomendable cierta íamiliarización con la lógica de proposiciones y la nomenclatura matematica. Ll orden de exposición se di·ide en dos bloques: - Un primer bloque contiene los conceptos clasicos de la lógica de predicados con la deíinición sintactica del lenguaje ,íórmulas bien íormadas,, la aproximación semantica ,concepto de interpretación y de equi·alencia lógica, . - A continuación, se expone el algoritmo de resolución, para lo cual se describen los conceptos de substitución y uniíicación. Lógica de Predicados L.U.I.1.I.O. -2- Lenguaje Formal de la Lógica de Predicados Ll instrumento íundamental de comunicación humana es el Lenguaje, íormado por írases de tipo interrogati·o, imperati·o y declarativo. Lstas últimas constituyen el elemento basico de descripción del conocimiento. La lógica es la disciplina que estudia los métodos de íormalización del conocimiento humano. Ln lógica se estudian, por tanto, métodos de íormalización de írases declarati·as. Para ello existen dos ni·eles de abstracción según el grado de detalle que se quiera íormalizar: Lógica proposicional y lógica de predicados. La lógica proposicional o lógica de enunciados toma como elemento basico las írases declarati·as simples o proposiciones que son aquellos elementos de una írase que constituyen por sí sólos una unidad de comunicación de conocimientos y pueden ser considerados Verdaderos o Ialsos. La lógica de predicados estudia las írases declarati·as con mayor grado de detalle, considerando la estructura interna de las proposiciones. Se tomaran como elemento basico los objetos y las relaciones entre dichos objetos. Ls decir, se distingue: - Que se afirma ,predicado o relación, - De quien se afirma ,objeto, A continuación se deíinira el lenguaje íormal que se utilizara en la lógica de predicados. Se deíine el conjunto de símbolos que apareceran en las distintas íormalizaciones ,alíabeto,. Seguidamente se deíinen las reglas sintacticas de construcción de íórmulas correctas. Definición 1: Ll alfabeto de la lógica de predicados estara íormado por los siguientes conjuntos de símbolos: • Conjunto de símbolos de Variables (JAR): Lsta íormado por las últimas letras del alíabeto minúsculas.1ambién se utilizan subíndices, por ejemplo: x v : x v : x v : JAR
L ∈ . • Conjunto de símbolos de Constantes (CONS ): Primeras letras del alíabeto minúsculas ,con subíndices,, por ejemplo: a b c a b c a b c CONS
L ∈ • Conjunto de letras de función ( FUNC): Lsta íormado por las letras f g h , , ,L . 1ambién se pueden incluir subíndices para diíerenciar distintas íunciones: f g h f g h FUNC
n n n 1 1 1
, , , , , , L ∈ Ln algunos casos se indica la aridad
mediante un superíndice. Así por ejemplo f FUNC
∈ sera una íunción con dos argumentos. 1
La aridad de una íunción o de un predicado se deíine como el número de argumentos que tiene. Lógica de Predicados L.U.I.1.I.O. -3- • Conjunto de letras de Predicado ( PRED): Se representan mediante letras mayúsculas, P Q R PRED , , ,K ∈ Como en el caso de las íunciones, se puede representar la aridad mediante un superíndice, por ejemplo: P PRED
∈ sera un predicado con tres argumentos. Símbolos de conectivas: Seran: ¬ ÷ Negacion ∧ ÷ conectiva ' y' ∨ ÷ conectiva ' o' → ÷ implicacion ↔ ÷ doble implicacion o equivalencia Cuantificadores: Seran los símbolos: ∀ ÷ CuantiIicador universal ∃ ÷ CuantiIicador existencial Signos de puntuación: Paréntesis ( ) y coma. Definición 2: Un termino es una cadena de símbolos utilizada para representar objetos siguiendo las siguientes reglas: - 1oda ·ariable o constante indi·idual es un término. - Si t t t
, , , L son términos y f
es una íunción de aridad n entonces f t t t
L es un término. - 1odos los términos posibles se generan aplicando únicamente las dos reglas anteriores. Definición 3: Un átomo
es una cadena de símbolos de la íorma: ) , , , (
t t t P Donde P
es un predicado de aridad v y n
son términos. 2
Obsér·ese que un término representara un objeto, mientras que un atomo tomara un ·alor Verdadero o lalso según la interpretación. Lógica de Predicados L.U.I.1.I.O. -4- Definición 4: Dado un alfabeto de lógica de predicados, se puede definir el conjunto de fórmulas bien formadas (fbf) cuyos elementos siguen las reglas: - 1odo atomo es una íórmula bien íormada ,se denominara fórmula atómica, - Si A y B son íórmulas bien íormadas entonces: ;.) ;ß) ¬. ¬ß .∧ß .∨ß .→ß .↔ß - Si A es una íórmula bien íormada y · una ·ariable
entonces ∀x A ( ) y ∃x A ( ) seran íórmulas bien íormadas. Ljemplo 1: La frase "1odos los estudiantes de informática son listos" podria formalizarse empleando los predicados I x x ( ) " = estudia inIormatica" y L x x ( ) " = es listo" como: Definición 5: Ln una expresión del tipo ∀xA, ∃xA, la ·ariable x es conocida como variable de cuantificación, a la íórmula A como ámbito o recorrido de la cuantiíicación. Definición 6: Ln una íórmula bien íormada A, una ·ariable esta ligada si esta en el ambito de un cuantiíicador que la tiene como ·ariable de cuantiíicación.. Una ·ariable esta libre si no esta ligada. 3
Mas adelante se modiíicara esta regla imponiendo la condición de que · sea una variable libre en . ∀·; í; · ) → í ; · ) ) 1érmino Átomo ,íbí íbí Son íórmulas bien íormadas Lógica de Predicados L.U.I.1.I.O. -5- Definición ¯: Se dice que una íórmula bien íormada es una fórmula cerrada si todas sus ·ariables estan ligadas. Con las deíiniciones anteriores podrían aparecer problemas si una ·ariable aparece cuantiíicada dos ·eces. Por ejemplo, en la íórmula ∃ → ∀ x P x xQ x ( ( ) ( )) , la · esta sometida a dos cuantiíicaciones. Para e·itar coníusiones. Ln la deíinición de íórmula bien íormada, se establece una restricción en el tercer punto que quedaría: ´i A e. vva fórvvta biev forvaaa , x una variable libre en evtovce. ∀xA , ∃xA .erav fórvvta. biev forvaaa..` Ljemplo 2: Ln la expresión: ¸ ¸¸ ¸ ¸_ ¸
)) , ( , ( v x f x P x ∀ - La ·ariable · aparece en el ambito del cuantiíicador uni·ersal que ademas la tiene como ·ariable de cuantiíicación, por tanto, la ·ariable · esta ligada. - La variable y también esta en el ambito del cuantiíicador uni·ersal, pero éste no la tiene como ·ariable de cuantiíicación, por lo tanto, es una ·ariable libre. Lógica de Predicados L.U.I.1.I.O. -6- Otros Ordenes Como ya se ha indicado, existen di·ersos órdenes dentro del calculo de predicados. Se denomina lógica de predicados de Orden Cero a la lógica de predicados en la que se trabaja con predicados de aridad cero ,seran proposiciones Verdaderas o lalsas, de ahí que también se le conozca como lógica de proposiciones o enunciados,. Puesto que no se utilizan constantes, ·ariables, íunciones ni cuantiíicadores su estudio es sencillo. Sin embargo, existen estructuras deducti·as que la lógica de proposiciones no puede íormalizar de íorma adecuada, por ejemplo, la deducción: ¨1oao. to. ivforvatico. .ov ti.to., ]vav e. ivforvatico, tvego ]vav e. ti.to¨ Ln lógica de predicados de orden cero se íormalizaría mediante tres proposiciones ¡,q y r independientes y la íórmula resultante " p q r ∧ → " no sería ·alida. Ln lógica de predicados de Primer Orden se permite la cuantiíicación de ·ariables. De esa íorma, el razonamiento anterior se íormalizaría : ( ( ( ) ( )) ( )) ( ) ∀ → ∧ → x Informatico x Listo x Informatico Juan Listo Juan Ln este caso, sí se puede comprobar la ·alidez de esa íórmula ,se estudiaran métodos en los siguientes apartados,. Sin embargo, se impone la limitación de no poder cuantiíicar mas que ·ariables, con lo cual, existe un amplio conjunto de írases que se quedan íuera del ambito de la lógica de primer orden. Ljemplo 3: Una írase de la íorma: ¨í·i.te vva fvvcióv f tat qve ¡ara cvatqvier · e·i.te vv , ae forva qve f x v ( ) = ¨ se debería íormalizar incluyendo un cuantiíicador existencial sobre las íunciones : ∃ ∀ ∃ f x v Igual f x v ( ( ), ) Ljemplo 4: La írase ¨.tgvva. retaciove. evtre ¡are. ae atvvvo. ae ta cta.e .ov .ivetrica.
¨ se íormalizaría: )) , ( ) , ( ( x v R v x R v x R → ∀ ∀ ∃ Ln los ejemplos anteriores aparecen íórmulas con cuantiíicadores aplicados a ·ariables de predicado y íunción, suponiendo la existencia de dominios predicados y de íunciones. La lógica que premite ese tipo de cuantiíicación se conoce como lógica de predicados de Segundo Orden. Ll problema de identiíicar íórmulas ·alidas esta resuelto
en lógica proposicional ,Orden Cero,, es parcialmente resoluble en lógica de predicados de Primer Orden e irrsoluble en lógica de Orden Superior. 4
Se recuerda que una relación R es simétrica si ·R, implica ,R· para todo · e ,. Lógica de Predicados L.U.I.1.I.O. -¯- Interpretación Una interpretación es un mecanismo que permitira asignar un ·alor Verdadero , V, o lalso ,F, a una íórmula. Para ello es necesario dar un signiíicado a cada uno de los símbolos que aparecen en la íórmula. Las conecti·as y los cuantiíicadores tienen un signiíicado íijo, mientras que el signiíicado de las constantes, símbolos de íunción y símbolos de predicado puede ·ariar. Ln una interpretación, se deíine un dominio de discurso sobre el cual ·arían las ·ariables, se asignan ·alores a las constantes y se deíinen los símbolos de íunción y de predicados de íorma particular. Se necesita, por tanto, asignar un ·alor concreto a cada símbolo de la íórmula en un dominio determinado. Definición 8: Una interpretación de una íórmula l consiste en: -Un conjunto no ·acío D, llamado Dominio de la interpretación -Asociar a cada letra de constante c F ∈ un elemento del dominio c D
∈ . -Asignar a cada letra de íunción f de aridad n una aplicación f
de la íorma D D D D
→ × × × . . -Asignar a cada letra de predicado P de aridad n una aplicación P
de la íorma { } F V, → × × × D D D
Un problema esta resuelto si siempre se puede encontrar solución. Ls parcialmente resoluble si se encuentra solución para algunos casos y no se encuentra para otros, y es irresoluble si no se encuentra solución en ningún caso. Lógica de Predicados L.U.I.1.I.O. -8- Ljemplo 5: Sea ( ) ( ) ( ) ( ) ( ) ) (a Q x f R x Q x P x F ∧ → ∧ ∀ = y las interpretaciones siguientes: Interpretación I
Dominio: Números naturales Personas Constantes a
2 = a fuan
= Iunciones f x x
( ) = f x x
( ) = madre de P x x
( ) = es un numero impar P x x
( ) = juega al poker Q x x
0 ( ) = > Q x x
( ) = estudia inIormatica Predicados: R x x
( ) = es multiplo de 9 R x x
( ) = es terco Bajo la interpretación I
la íórmula equi·aldría a: "Ll cuadrado de todo número impar mayor que cero es múltiplo de 9 y el 2 es mayor que cero" Mientras que bajo la interpretación I
sería: "1odas las madres de los estudiantes de iníormatica que juegan al póker son tercas y juan estudia iníormatica". Definición 9: Dada una interpretación í se deíine el ·alor de una íórmula F bajo I , denotado por J F
de la siguiente íorma
: - Si F es un predicado de n argumentos de la íorma P a a a a
K entonces J F P a a a
( ) ( , , , ) =
K donde cada elemento a
es el resultado de aplicar la interpretación í al argumento a
. -Si F es de la íorma ¬G entonces ¹
G J si
Ln esta deíinición se supone que la íórmula l no tiene ·ariables libres. Si l tu·iese, por ejemplo, x x x
, , , K ·ariables libres, la ·aloración de la íórmula se dejaría en íunción de los posibles ·alores que puedan tomar x x x
, , , K en el dominio. La expresión correcta sería J F x x x
K . No se ha utilizado esa notación para no complicar las expresiones resultantes. ¯
Obsér·ese que J F
( ) es el ·alor de ·erdad de F, que puede ser Verdadero o lalso. Lógica de Predicados L.U.I.1.I.O. -9- -Si F es de la íorma G H ∧ entonces ¹
contrario caso en
V V H J G J si
-Si F es de la íorma G H ∨ entonces ¹
F F H J G J si
-Si F es de la íorma G H → entonces ¹
) ( y ) (
F V F H J G J si
-Si F es de la íorma G H ↔ entonces ¹
V H J G J si
-Si F es de la íorma ∀xG x ( ) entonces ¹
¦ ∈ =
todo para )) ( (
V V D d d G J si
-Si F es de la íorma ∃xG x ( ) entonces: ¹
algun para )) ( (
,Ln las dos posibilidades anteriores, G d ( ) se íorma sustituyendo todas las apariciones de · por a en la íórmula C;·) , Ls importante remarcar la naturaleza no constructi·a de la deíinición. Si el dominio es iníinito, para calcular el ·alor de la íórmula se deberían chequear iníinitos elementos, lo cual es inviable. Nótese la diíerencia con respecto a la lógica ed proposiciones o lógica de orden 0, en donde SI era posible acotar todas las posibles interpretaciones desde la premisa que cada letra proposicional podía adoptar sólo dos ·alores ,1 , í,. La deíinición no aporta ningún algoritmo para calcular J F
( ), de hecho, en la mayoría de los casos, no existe tal algoritmo. Ljemplo 6: Dada la íórmula ( ) ( ) ( ) ( ) ( ) ( ) ) ( , , , v f b a g Q x f Q v x P v x F ¬ → ∧ ∃ ∀ = , una interpretación I para la íórmula sería: Dominio: { } 3 , 2 , 1 = D Constantes: a b
= = 1 3 , lunciones: f x x
( ) = − 4 g x v : x v :
( , , ) ( ) = + + + MOD 3 1 Lógica de Predicados L.U.I.1.I.O. -10- Predicados: P x v x v
( , ) " " = ≤ Q x x OR x
( ) " " = = = 2 3 Para calcular el ·alor de la íórmula para esa interpretación se chequeara si para todo · existe un , que cumpla ( ) ( ) ( ) ( ) ( ) ( ) ) ( , , , v f b a g Q x f Q v x P ¬ → ∧ . Se comienza por x=J: a, Se busca un ,, escogiendo, por ejemplo, ,~1. Como se puede ·er en el siguiente esquema, el ·alor que se obtiene sera F: ( ) ( ) ( ) ( ) ( ) ( ) ) ( , , , v f b a g Q x f Q v x P ¬ → ∧
b, Puesto que para ,~1 no se cumple, se busca un nue·o ·alor de ,. Para ,~2 se tiene: ( ) ( ) ( ) ( ) ( ) ( ) ) ( , , , v f b a g Q x f Q v x P ¬ → ∧ Al obtener ·alor V no es necesario chequear mas ·alores de , ,ya se ha encontrado uno, y se sigue buscando un nue·o ·alor de ·. V 3 2 V 1 V V V V 3 3 V 2 V I I 1 1 1 1 3 1 1 2 1 1 3 2 Lógica de Predicados L.U.I.1.I.O. -11- c, Para x=2: a. y=J: ( ) ( ) ( ) ( ) ( ) ( ) ) ( , , , v f b a g Q x f Q v x P ¬ → ∧ ,ya se ha encontrado un ·alor de ,, se chequea el último ·alor de ·, d, Para x=3: a. y=J: ( ) ( ) ( ) ( ) ( ) ( ) ) ( , , , v f b a g Q x f Q v x P ¬ → ∧ Como se ha encontrado un ·alor de , para todos los · que hacía V la íórmula, el ·alor de la íórmula bajo esa interpretación J F
( ) = V I 1 3 I 2 I I V I 2 3 V 2 I I V 2 1 2 1 3 1 3 1 3 1 3 1 Lógica de Predicados L.U.I.1.I.O. -12- Ljemplo 7: Dada la íórmula F x vP x f v Q a = ∀ ∃ ∧ ( , ( )) ( ) y la interpretación I : Dominio: { } 3 , 2 , 1 = D Constantes: a
= 3 lunciones: ` f x
( ) 1 2 2 ² ² 1 Predicados: { } ) 3 , 2 ( ), 3 , 1 ( =
P , { } 3 , 2 =
Q Se puede comprobar que, en este caso, para x = 3 no existe ningún ·alor de , que haga V la íórmula. Por tanto, J F
( ) = F. Definición J0: Una interpretación I de una íórmula F es un modelo para F si J F
( ) = V. Definición JJ: Una íórmula F es válida si y sólo si toda interpretación I es un modelo de F . Obsér·ese que al existir iníinitas interpretaciones, no sera posible chequear si una íórmula es o no ·alida mediante tablas de ·erdad. Definición J2: Una íórmula F es satisfacible si existe alguna interpretación I que sea un modelo de F Definición J3: Una íórmula F es insatisfacible o contradicción si no existe ninguna interpretación I que sea un modelo de F. Lógica de Predicados L.U.I.1.I.O. -13- Una íórmula puede ser: satisíacible o insatisíacible. Un tipo especial de íórmula satisíacible, es aquella que toma siempre ·alor V ,es ·alida,. Por tanto, las íórmulas ·alidas son un subconjunto de las satisíacibles. 1eorema J: Una íórmula l es válida si y sólo si su negación ¬F es insatisfacible. Dem: Si l es ·alida quiere decir que J F
( ) = V
para toda Interpretación I. Por tanto, J F
( ) ¬ = F
para toda interpretación, y no existe ninguna interpretación tal que J F
. Lógica de Predicados L.U.I.1.I.O. -14- Consecuencia y Equivalencia Lógicas Definición 14: Sea C un conjunto de Iormulas { }
P P P , ,
y sea Q una Iormula. Se dice que Q es consecuencia lógica del conjunto C de premisas (se denotara C Q ¬ ) si toda interpretacion que es un modelo de C es tambien un modelo de Q. Es decir, si para toda interpretacion I se cumple que si V = = = = ) ( ) ( ) (
2 1 n I I I
P J P J P J entonces J Q
( ) = V (Intuitivamente, se podria considerar cada interpretacion como un "posible mundo". De esa Iorma, decir que Q es consecuencia logica de unas premisas es equivalente a pensar que Q toma valor V en cualquier mundo en el que las premisas tomen valor V). Una estructura de la Iorma { } Q P P P
¬ , ,
se denomina razonamiento. Donde { }
es el conjunto de premisas y Q, la conclusion. Se dice que un razonamiento es correcto si la conclusion es consecuencia logica de las premisas. 1eorema 2: Q P P P
¬ , , ,
es correcto si y sólo si Q P P P
→ ∧ ∧ ∧ 2 1
es ·alida Dem: La demostración se di·idira en dos partes: J.- Si Q P P P
entonces Q P P P
es ·alida. Q P P P
no es ·alida cuando existe una interpretación I que cumple que V = ∧ ∧ ∧ ) (
P P P J mientras que J Q
( ) = F. Ls decir en caso de que V = = = = ) ( ) ( ) (
P J P J P J y J Q
( ) = F. Ls decir cuando no se cumple que Q P P P
. 2.-Si Q P P P
es ·alida entonces Q P P P
Si Q P P P
es válida entonces toda interpretación para la cual V = = = = ) ( ) ( ) (
P J P J P J obliga a que J Q
( ) = V, por tanto Q P P P
Lógica de Predicados L.U.I.1.I.O. -15- A continuacion se indican una serie de Iormulas validas o leyes del calculo de predicados. Se supone que A, B y C son Iormulas bien Iormadas y x una variable. Supresión de Implicación: A B A B → ≡ ¬ ∨ Supresión de Doble Implicación: ( ) ( ) A B B A B A → ∧ → ≡ ↔ Definición JS: Se dice que dos íórmulas A y B son equivalentes lógicamente ,se denota por A B ≡ ó A B ⇔ , si para toda interpretación í, se cumple que J A J B
( ) ( ) = Absorcion ( ) A A B A ≡ ∨ ∧ ( ) A A B A ≡ ∧ ∨ A∧ ≡ F F A∨ ≡ V V Elemento neutro A A ∧ ≡ V A A ∨ ≡ F El. Complementario A A ∧ ¬ ≡ F A A ∨ ¬ ≡ V Idempotencia A A A ∧ ≡ A A A ∨ ≡ Prop. Commutativa A B B A ∨ ≡ ∨ A B B A ∧ ≡ ∧ Prop. Asociativa ( ) ( ) C B A C B A ∧ ∧ ≡ ∧ ∧ ( ) ( ) C B A C B A ∨ ∨ ≡ ∨ ∨ Prop. Distributiva ( ) ( ) ( ) C A B A C B A ∨ ∧ ∨ ≡ ∧ ∨ ( ) ( ) ( C A B A C B A ∧ ∨ ∧ ≡ ∨ ∧
Leyes de De Morgan ( ) B A B A ¬ ∧ ¬ ≡ ∨ ¬ ( ) B A B A ¬ ∨ ¬ ≡ ∧ ¬ Doble Negacion (Involucion) ¬¬ ≡ A A Lógica de Predicados L.U.I.1.I.O. -16- Leyes de De Morgan con cuantificadores: ( ) ( ) x A x x xA ¬ ∀ ≡ ¬∃ ( ) ( ) x A x x xA ¬ ∃ ≡ ¬∀ Ljemplo 8: La írase ¨^o e·i.tev are. qve vo .e¡av rotar¨ se íormalizaría: ¬∃ ∧ ¬ x Ave x Juela x ( ( ) ( )) Aplicando las leyes anteriores sería equi·alente a: ( ) ( ) ( ) ) ( ) ( ) ( ) ( ) ( ) ( x Juela x Ave x x Juela x Ave x x Juela x Ave x → ∀ ≡ ∨ ¬ ∀ ≡ ¬ ∧ ¬ ∀ que podría leerse como: "1odas las a·es saben ·olar". Intercambio de cuantificadores: ) , ( ) , ( v x A x v v x A v x ∀ ∀ ≡ ∀ ∀ ) , ( ) , ( v x A x v v x A v x ∃ ∃ ≡ ∃ ∃ ) , ( ) , ( v x A x v v x A v x ∃ ∀ ¬ ∀ ∃ Nota: La ley anterior se cumple únicamente en el sentido dado , ya que ) , ( ) , ( v x A v x v x A x v ∀ ∃ ¬
∃ ∀ . Si se Considera la interpretación: Dovivio~Per.ova., .;·,,)~¨· e.ta ca.aao cov ,¨. La ley anterior implicaría la írase: ¨´i toaa. ta. ¡er.ova. ;,) e.tav ca.aaa. cov atgviev ;·) evtovce. e·i.te atgviev ;·) qve e.ta ca.aao cov toaa. ta. ¡er.ova. ;,)¨ Gran distributividad ( ) ( ) ( ) ( ) ( ) ( ) x xB x xA x B x A x ∃ ∨ ∃ ≡ ∨ ∃ ( ) ( ) ( ) ( ) ( ) ( ) x xB x xA x B x A x ∀ ∧ ∀ ≡ ∧ ∀ Nota: No se cumplen cambiando la conecti·a ¨o¨ por la conecti·a ¨,¨, es decir: ( ) ( ) ( ) ( ) ( ) ( ) x xB x xA x B x A x ∃ ∧ ∃ ≡/ ∧ ∃ , por ejemplo, para la interpretación .;·)~ · e. atvvvo y ß;·)~· e. vv borracbo. No es lo mismo: ¨í·i.tev atvvvo. borracbo.¨ que ¨í·i.tev atvvvo. , e·i.tev borracbo.¨. De la misma íorma: ( ) ( ) ( ) ( ) ( ) ( ) x xB x xA x B x A x ∀ ∨ ∀ ≡/ ∨ ∀ , ejemplo: Dovivio: e.tvaiavte.. .;·)~· e.ta ategre. ß;·)~· e.ta tri.te. La írase ¨1oao. to. e.tvaiavte. e.tav ategre. o tri.te.¨ no es equi·alente a ¨1oao. to. e.tvaiavte. e.tav ategre. o toao. e.tav tri.te.¨. Lógica de Predicados L.U.I.1.I.O. -1¯- Gran distributividad restringida: ( ) ( ) ( ) x A B x x xA B ∨ ∃ ≡ ∃ ∨ ( ) ( ) ( ) x A B x x xA B ∨ ∀ ≡ ∀ ∨ ( ) ( ) ( ) x A B x x xA B ∧ ∃ ≡ ∃ ∧ ( ) ( ) ( ) x A B x x xA B ∧ ∀ ≡ ∀ ∧ ,donde · no aparece en ß, Lógica de Predicados L.U.I.1.I.O. -18- Formas Normales Definición J6: Se dice que una íórmula F esta en Iorma Normal Prenexa(INP) si es de la íorma M x Q x Q x Q
Q Q Q 2 1
son cuantiíicadores ,∀ ∃ , , y M es una íórmula sin cuantiíicadores. La secuencia Q x Q x Q
L se denomina prefijo de F, mientras que M sera la matriz de la íórmula. A continuación se indica mediante un teorema que cualquier íórmula cerrada puede ser tranasíormada en una íórmula equi·alente en lorma Normal Prenexa. Si la íórmula no íuese cerrada ,tu·iese ·ariables libres, se aplicaría el cierre existencial consistente en anadir al principio de la íórmula un cuantiíicador existencial por cada ·ariable libre. 1eorema 3: Para cualquier íórmula cerrada de calculo de predicados se puede encontrar una íórmula equi·alente en lorma Normal Prenexa. Dem: La demostración consiste en indicar cómo se transíormaría la íórmula original utilizando las reglas de equi·alencia de la sección anterior, obteniendo la íórmula en lorma Normal Prenexa. Los pasos a seguir serían: - Renombrar ·ariables con el mismo nombre y distinto cuantiíicador. -Lliminar la doble implicación ,↔,, utilizando F G F G G F ↔ ≡ → ∧ → ( ) ( ) -Lliminar implicación: F G F G → ≡ ¬ ∨ -Aplicar leyes de De Morgan con y sin cuantiíicadores de íorma que las negaciones sólo aíecten a íórmulas atómicas. - Pasar los cuantiíicares al principio de la íórmula aplicando las leyes de cuantiíicadores. A continuación se deíiniran la lorma Normal Conjunti·a y la lorma Normal Disyunti·a. Para ello, se utilizara la siguiente notación: Lógica de Predicados L.U.I.1.I.O. -19- ∧
es igual a la íórmula X X X
∧ ∧ ∧ L ∨
∨ ∨ ∨ L Definición J7: Un literal es una íórmula atómica p t t t
K ,también llamado literal positivo, o una íórmula atómica negada ¬p t t t
K ,llamado literal negativo, Definición J8: Una íórmula F esta en Iorma Normal Conjuntiva(INC) si es una conjunción íinita de la íorma |
, donde cada L
es un literal. Definición J9: Una íórmula F esta en Iorma Normal Disyuntiva(IND) si es una disyunción íinita de la íorma |
es un literal. 1eorema 4: Para cualquier íórmula cerrada se puede encontrar una íórmula equi·alente en lorma Normal Conjunti·a ,disyunti·a,. Dem: Cualquier íórmula se puede transíormar en una íórmula en lorma Normal Conjunti·a ,disyunti·a, equi·alente mediante las leyes de De Morgan y las propiedades distributi·as. Definición 20: Una íórmula esta en Iorma Normal Conjuntiva (disyuntiva) Prenexa, se escribe lNCP ,lNDP,, si esta en lorma Normal Conjunti·a ,disyunti·a, y en lorma Normal Prenexa. 1eorema S: Cualquier íórmula cerrada se puede transíormar en una íórmula lógicamente equi·alente a ella en lNCP. Dem: Se transíorma la íórmula en lNP mediante el teorema 3 obteniendo la íórmula en lNP y, mediante el teorema 4 se transíorma la matriz a lNC Definición 2J: Una íórmula cerrada esta en Iorma Normal de Skolem (INS) si esta en lNCP y todos los cuantiíicadores son uni·ersales. Para con·ertir una íórmula a lorma Normal de Skolem es necesario suprimir los cuantiíicadores existenciales. La íórmula obtenida no sera lógicamente equi·alente a la anterior, sino que sera equisatisíacible. A continuación se muestra el algoritmo de skolemización para suprimir los cuantiíicadores existenciales de una íórmula cerrada. Lógica de Predicados L.U.I.1.I.O. -20- Algoritmo (skolemización) 1.- Se busca el primer cuantiíicador existencial comenzando por la izquierda. 2.- Si no se encontró, íinalizar. 3.- Si el cuantiíicador existencial esta al principio ,de la íorma ∃xF x ( ),, se suprime la ·ariable cuantiíicada por una nue·a constante ,quedaría F a ( ) ,. Vol·er al paso 1. 4.- Si existen n cuantiíicadores uni·ersales antes del cuantiíicador existencial de la íorma: ) , , , , (
v x x x F v x x x
∃ ∀ ∀ ∀ suprimir la ·ariable cuantiíicada existencialmente ,,, por una nue·a íunción de las ·ariables uni·ersales anteriores ,
,. Quedando de la íorma: )) , , , ( , , , , (
2 1 2 1 2 1 n n n
x x x f x x x F x x x ∀ ∀ ∀ . Vol·er al paso 1. 1eorema 6: Dada cualquier íórmula en lógica de predicados se puede encontrar una íórmula eqvi.ati.facibte a ella en lorma Normal de Skolem. Dem: Mediante los teoremas anteriores, se puede obtener una íórmula equi·alente en lorma Normal Conjunti·a Prenexa ,lNCP,. Para obtener la íórmula en lNS es necesario suprimir los cuantiíicadores existenciales según los pasos 3 y 4 del algoritmo anterior. Si se realiza el paso 3, una íórmula de la íorma ∃xF x ( ) es satisíacible cuando existe un ·alor constante del dominio que satisíace F. Puesto que la nue·a constante a no tiene ·alor asignado, si se le asocia el ·alor que satisíace F, entonces F a ( ) sera satisíacible. Si se realiza el paso 4, tenemos un ·alor que satisíace F dependiendo de los ·alores n
,. Si escogemos una íunción f , que asigne ese ·alor a ) , , , (
x x x f . . Lntonces, la íórmula )) , , , ( , , , , (
x x x f x x x F x x x ∀ ∀ ∀ también sera satisíacible. La demostración en el otro sentido es e·idente. Obsér·ese la diíerencia entre ∀ ∃ x vC x v ( , ) y ∃ ∀ v xC x v ( , ). Si se toma la siguiente interpretación: "C;·,,)~ · esta casado con ," se tiene: ∀ ∃ x vC x v ( , ) ~ "1oao. e.tav ca.aao. cov atgviev¨ que sería satisíacible con C;·,f;·)) donde se habría escogido la íunción f;·) como la persona que esta casada con ·. ∃ ∀ v xC x v ( , ) ~"í·i.te atgviev qve e.ta ca.aao cov toao.¨ . Ln este caso sería equisatisíacible con C;·,a). Lscogiendo la constante a como la persona que esta casada con todos. Lógica de Predicados L.U.I.1.I.O. -21- Definición 22: Una íórmula esta en Iorma Clausal si esta en lNS y se suprimen los cuantiíicadores uni·ersales y las conjunciones por comas
. Ljemplo 9: lormalizar y pasar a lorma Clausal la írase: ¨1oao et qve e.tvaie bi.toria o fito.ofía, a¡revaera atgo ivtere.avte , covocera cvatqvier ¡er.ova;e griego¨ Para íormalizar la írase, se toma: - í;·) ~ x estudia historia - í;·) ~ x estudia íilosoíía - í;·) ~ x es interesante - A,x,y,~ x aprende y - C;·,,) ~ x conoce y - C;·)~ x es un personaje griego Quedaría la íórmula: ( ) ( ) ( ) ( ) ( ) ( ) ) , ( ) , ( ) ( ) ( ) ( v x C v G v v x A v I v x F x H x → ∀ ∧ ∧ ∃ → ∨ ∀ Para transíormar la íórmula a lorma Clausal se seguira, los pasos generales: 1.- Renombrar ·ariables comunes: ( ) ( ) ( ) ( ) ( ) ( ) ) , ( ) , ( ) ( ) ( ) ( : x C : G : v x A v I v x F x H x → ∀ ∧ ∧ ∃ → ∨ ∀ 1.- Lliminar → ( ) ( ) ( ) ( ) ( ) ( ) ) , ( ) , ( ) ( ) ( ) ( : x C : G : v x A v I v x F x H x ∨ ¬ ∀ ∧ ∧ ∃ ∨ ∨ ¬ ∀ 2.- Introducir negaciones. ( ) ( ) ( ) ( ) ( ) ( ) ) , ( ) , ( ) ( ) ( ) ( : x C : G : v x A v I v x F x H x ∨ ¬ ∀ ∧ ∧ ∃ ∨ ¬ ∧ ¬ ∀ 3.- Pasar cuantiíicadores al principio de la íórmula. Se obtiene lNP. ( ) ( ) ( ) ( ) ( ) ( ) ) , ( ) , ( ) ( ) ( ) ( : x C : G v x A v I x F x H : v x ∨ ¬ ∧ ∧ ∨ ¬ ∧ ¬ ∀ ∃ ∀ 4.- Poner la matriz en lNC, aplicando propiedades distributi·as. Se obtiene lNCP. 8
La lorma Clausal es equi·alente a la lNS, simplemente se reescribe como un conjunto de clausulas. ; ¬í;·) ∨ í;,) ) ∧ ; ¬í;·) ∨ .;·,,) ) ∧ ;¬í;·) ∨¬C;¸) ∨ C;·,¸) ) ∧ ;¬í;·)∨ í;,) ) ∧ ;¬í;·)∨ .;·,,) ) ∧ ;¬í;·)∨¬C;¸) ∨ C;·,¸) ) ∀·∃,∀¸ Lógica de Predicados L.U.I.1.I.O. -22- 5.- Quitar cuantiíicadores existenciales. Se obtiene lNS 6.- Suprimir cuantiíicadores uni·ersales y reescribir como un conjunto de clausulas, obteniendo, así lorma Clausal. ( )
∨ ¬ ∨ ¬ ∨ ¬ ∨ ¬
) , ( ) ( )), ( , ( ) ( )), ( ( ) (
), , ( ) ( )), ( , ( ) ( )), ( ( ) (
: x C : G x F x f x A x F x f I x F
: x C : G x H x f x A x H x f I x H
Definición 23: Una clausula lorn es una clausula que tiene como mucho un literal positi·o, se denota de la íorma: , ,
P P C . ←
donde el literal positi·o C se conoce como la cabeza de la clausula y los literales negati·os como el cuerpo de la clausula. Si n = 0, se denomina Hecho, sera "C" Una clausula lorn sin literal positi·o se conoce como Objetivo, sera de la íorma " , ,
P P . ← " Definición 24: Se denomina clausula ·acía y se denota por J a la clausula que no tiene literales. Por deíinición, la clausula ·acía es insatisíacible o contradicción ; ¬í;·) ∨ í;f;·)) ) ∧ ; ¬í;·) ∨ .;·,f;·)) ) ∧ ;¬í;·) ∨¬C;¸) ∨ C;·,¸) ) ∧ ;¬í;·)∨ í;f;·)) ) ∧ ;¬í;·)∨ .;·,f;·)) ) ∧ ;¬í;·)∨¬C;¸) ∨ C;·,¸) ) ∀·∀¸ Lógica de Predicados L.U.I.1.I.O. -23- Algoritmo de Resolución Introducción La presentacion se di·idira en dos partes, en la primera parte se presenta el algoritmo de resolución para lógica de proposiciones demostrando su consistencia y completud. Ln la segunda parte se presentara el algoritmo de resolución general para lógica de predicados, el cual incluye un paso pre·io de uniíicación de clausulas mediante substituciones. Ll algoritmo se basa en una única regla de iníerencia sencilla y, a la ·ez de gran potencia: la regla de resolución. Puesto que se utiliza una sola regla, es Iacil de analizar e implementar. Resolución Proposicional Intuiti·amente, la idea de la resolucion proposicional es simple: Si se sabe que se cumple: "P ó Q" y que se cumple "no P ó R" entonces se puede deducir que se cumplirá "Q ó R". Ljemplo 2J: Si se tiene: "Gana o Pierde o Lmpata" y "Si Gana entonces da una liesta o Va de Viaje". Se puede deducir que: "O Pierde o Lmpata o da una liesta o ·a de Viaje". lormalizando, la primera írase sería: G P E ∨ ∨ y la segunda: G F J G F J → ∨ ≡ ¬ ∨ ∨ La regla de resolución iníerira: P E F J ∨ ∨ ∨ Definición 34: Dadas dos clausulas C
tales que exista un literal t de íorma que l C ∈
, se denomina resolvente de C
respecto a l a: { } ( ) { } ( ) l C l C C C R
¬ − ∪ − =
) ( . Se dice que C
son cláusulas resolubles. 1eorema 6 (Consistencia de la regla de resolución): Ll resol·ente de dos clausulas es consecuencia lógica de ellas. Ls decir { } ( )
, , C C R C C ¬ Dem: Sean m
∨ ∨ ∨ ∨ = y n
∨ ∨ ∨ ∨ ¬ = dos clausulas resolubles. Ll resol·ente de C
respecto a t sera n m l
l l l l l l C C R
2 22 21 1 12 11 2 1
) , ( ∨ ∨ ∨ ∨ ∨ ∨ = Ll método de resolución es un algoritmo íacilmente mecanizable propuesto por J.A. Robinson en 1965. Si un conjunto de clausulas es insatisíacible, el algoritmo lo detecta y para ,teorema de Completud,. Si el conjunto es satisíacible podría detectarlo o no parar, por lo cual se dice que es un algoritmo parcialmente completo. Lógica de Predicados L.U.I.1.I.O. -24- Por el teorema 2, probar que { } ( )
, , C C R C C ¬ es equi·alente a probar que ( )
, C C R C C → ∧ es ·alida. Supóngase que existe una interpretación que la hace lalsa, la asignación de ·alores sera: Puesto que se llega a una contradicción, la íórmula no puede ser Ialsa y sera siempre ·erdadera, es decir, la íórmula es Válida. 1eorema 7: Si el resol·ente de 2 clausulas C
es la clausula ·acía, entonces esas dos clausulas son insatisíacibles. Dem: Según el teorema anterior, el resol·ente de 2 clausulas es consecuencia lógica de ellas, por tanto, la íórmula: C C
∧ →Ì es ·alida. Puesto que Ì tiene ·alor lalso, para que la implicación sea ·alida, C C
∧ tienen que tener ·alor lalso. Ls decir, son insatisíacibles. Ll algoritmo de resolución chequeara si un conjunto de clausulas es insatisíacible, para ello seleccionara pares de clausulas resolubles y calculara su resol·ente. Si se obtiene la clausula ·acía, el conjunto es insatisíacible. Ln caso contrario, el resol·ente se anade al conjunto de clausulas y se seguiran buscando nue·os pares de clausulas. Algoritmo de resolución proposicional Lntrada: Un conjunto de clausulas C Salida: Detecta si C es insatisíacible 1.- Buscar dos clausulas C C C
, ∈ tales que exista un literal t que cumple que l C ∈
2.- Si se encuentran: 3.- Calcular R C C
y anadirlo al conjunto C 4.- Si R C C
= Ì entonces SALIR indicando que C es insatisfacible. 5.- Si no, Anadir R C C
a C y Vol·er a 1 3.- Si no se encuentran: SALIR indicando que C no es insatisfacible. Ljemplo 22: Sea C el siguiente conjunto de clausulas { } r q p r q p p ∨ ¬ ∨ ¬ ¬ ∨ ¬ , , , , se puede demostrar que C es insatisíacible por resolución. Para ello: I ∨ I
11 ∨ . ∨ I
∧ ∧∧ ∧ ¬I ∨ I
∨ . ∨ I
V I I V I ¡Contradicción! Lógica de Predicados L.U.I.1.I.O. -25- - Se resuel·e la tercera clausula ,¬ r , con la cuarta ,¬ ∨ ¬ ∨ p q r ,, obteniendo ¬ ∨ ¬ p q. - Se resuel·e ahora la clausula anterior con la segunda clausula ,¬ ∨ p q , obteniendo: ¬p - Se resuel·e ahora la clausula anterior con la primera y se llaga a la clausula ·acía J Puesto que se llega a la clausula ·acía, C es insatisíacible. A continuación se presentaran las ideas generales necesarias para la demostración del teorema de completud del algoritmo de resolución proposicional basandose en el concepto de arbol semantico deíinido en la sección anterior. Se puede proíundizar mas en |Ben-Ari 93|. Ademas, existe otra íorma de demostrar el teorema por inducción en el número de literales, ·éase |Sperschneider 91| Ljemplo 23: Sea el conjunto de clausulas { } r q p r q p p C ∨ ¬ ∨ ¬ ¬ ∨ ¬ = , , , , para construir el arbol semantico para C se recuerda que un conjunto de clausulas equi·ale a una íórmula en lorma Normal Conjunti·a, en este caso, ( ) ( ) ( ) r q p r q p p ∨ ¬ ∨ ¬ ∧ ¬ ∧ ∨ ¬ ∧ . Ln la siguiente íigura se muestra el arbol semantico correspondiente marcando la clausula íalsiíicada en los nodos de íallo. Ll arbol semantico sera: ( ) p
Lema J: Si un conjunto de clausulas es insatisíacible, entonces el arbol semantico es íinito y esta limitado por nodos de íallo, se denomina, en ese caso, árbol de fallo. Lema 2: Cada nodo de íallo v íalsiíica al menos a una de las clausulas del conjunto que sera la cláusula asociada a n. Lema 3: La clausula C asociada a un nodo de íallo v contiene un subconjunto de los complementos de los literales que aparecen en la rama que ·a desde la raíz del arbol semantico hasta v. Dem: Puesto que la clausula C es íalsiíicada en el nodo v, todos sus literales deben tener asignado un ·alor en la interpretación parcial correspondiente a v. Ademas, el ·alor de esos literales debe ser F,puesto que C es una disyunción, con lo cual, el ·alor asignado debe ser el complementario. Definición 3S: Se denomina nodo de inferencia a un nodo del arbol semantico cuyos dos hijos son nodos de íallo. Lema 4: Ln un arbol de íallo, sal·o que sólo tenga un nodo, debe existir al menos un nodo de iníerencia. Dem: Puesto que el arbol de íallo es íinito y las ramas se desarrollan de dos en dos, necesariamente tendremos un último nodo desarrollado con dos hijos. Lógica de Predicados L.U.I.1.I.O. -26- Lema S: Un nodo de iníerencia i indica un paso de resolución de las clausulas asociadas a sus dos hijos. Ll resol·ente de dichas clausulas es íalsiíicado por el nodo i y, ocasionalmente, por alguno de sus antecesores. Dem: Ln un nodo de iníerencia i cualquiera, se tendra un esquema como el que sigue: F (C
- Puesto que el nodo i no íalsiíicó C
y lo único que cambia en el nodo ; respecto a i es el ·alor de ¡, la clausula C
debe contener el literal ¬p ,complementado para que sea lalso,. - Por la misma razón anterior, la clausula C
debe contener el literal ¡ ,sin complementar para que sea lalso, Por tanto C
son resolubles respecto a ¡. Ll esquema sera: k f k f p
C resto C resto C C R
C resto p C
¸ ¸ ) , (
∨ ¬ =
Ln el nodo ;, C
toma ·alor lalso, por tanto resto C
¸ tomara también ·alor lalso, como resto C
¸ no contiene el literal ¡ también tomaran ·alor lalso en el nodo i. De la misma íorma, resto C
¸ tomara ·alor lalso en et voao i. Por tanto, R C C resto C resto C
p f k f k
( , ) ¸ ¸ = ∨ tomara ·alor lalso en el nodo i, es decir, el nodo i, es un nodo de íallo para el resol·ente de C
Ln ocasiones, puede ocurrir que el resol·ente sea íalsiíicado también por alguno de los padres del nodo de iníerencia, como ejemplo, considérese el conjunto de clausulas { } r p r q p p ∨ ¬ ¬ ∨ ¬ , , , , el arbol semantico, junto con los resol·entes sería: ( ) p
Ll resol·ente de los nodos 6 y ¯ es ,¬p, que íalsiíica al nodo 4 pero también íalsiíica a su antecesor, el nodo 2. Lógica de Predicados L.U.I.1.I.O. -2¯- 1eorema 8 (Completud del Algoritmo de Resolución Proposicional): Si un conjunto de clausulas es insatisíacible entonces, aplicando el algoritmo de resolución, se alcanza la clausula ·acía. Dem: Dado un conjunto de clausulas insatisíacibles, el arbol semanttico sera un arbol de íallo ,Lema 1,, ademas existira al menos un nodo de iníerencia ,Lema 4, con el cual se puede íormar un resol·ente de sus dos hijos ,Lema 5, y anadirlo al conjunto. Si se construye el arbol semantico para el nue·o conjunto, el nue·o arbol semantico sera mas pequeno que el anterior ,puesto que se encuentra un nodo de íallo antes, y, como el conjunto es insatisíacible, existira de nue·o otro nodo de iníerencia, ..., repitiendo el proceso se llegara a un arbol semantico con un solo nodo que correspondera a la clausula ·acía. Resolución General Como ya se ha indicado, el algoritmo de resolución general para lógica de predicados de primer orden es una generalización del algoritmo de resolución proposicional que incluye un paso pre·io de uniíicación de clausulas mediante substituciones. Ls necesario, por tanto, deíinir qué es una substitución para deíinir a continuación qué es un uniíicador de clausulas. Una ·ez deíinidos ambos conceptos se presenta el método de resolución general demostrando su consistencia y completud. Definición 36: Una substitución σ es un conjunto íinito de la íorma { }
t v t v t v / , , / , /
donde cada v
es una ·ariable, cada t
es un término distinto de v
y las ·ariables v v v
, , , L son distintas entre sí. Definición 37: Una expresión es un término, un literal o una conjunción o disyunción de literales. Una expresión simple es un término o un atomo. Definición 38: Sea { }
= σ y E una expresión, entonces se deíine la instancia de í por σ , denotado por ( ) E σ , como la expresión que resulta de substituir simultaneamente cada aparición de la ·ariable v
en í por el término t
,i n = 1, , K ,. Ljemplo 24: Sea E P x v f a = ( , , ( )) y { } ) ( / , / x f v b x = σ entonces ( ) )) ( ), ( , ( a f x f b P E = σ . Substitución Una substitución sera un mecanismo que nos permitira transíormar íórmulas. Ll interés principal de las substituciones radica, en esta exposición, en su aplicación a la unificación de un conjunto de expresiones, haciendo que las expresiones resulten sintacticamente idénticas. Una substitución es básica si los términos t
no contienen ·ariables. Si ( ) E σ no contiene ·ariables entonces ( ) E σ es una instancia básica de í. Lógica de Predicados L.U.I.1.I.O. -28- Definición 39: Sean { }
t x t x t x / , , / , /
. = σ y { }
s v s v s v / , , / , /
. = σ dos substituciones, entonces la composición de substituciones σ σ
o es la substitución: Ejemplo 25: Sea { } : v v f x / ), ( /
= σ y { } v : b v a x / , / , /
= σ entonces Definición 40: La substitución deíinida por el conjunto ·acío se denomina substitución vacia ó substitución identidad y se denota por ε . Ljemplo 26: Sea { } : v v f x / ), ( /
= σ y { } b : a x / , /
= σ . { } b : b v v f x / , / ), ( /
= σ σ · . Definición 4J: Dadas dos expresiones, E y F, se dice que son variantes si existen dos substituciones σ
tales que ( ) F E
σ = y ( ) E F
σ = . 1ambién se dice que í es una ·ariante de í o que í es una ·ariante de í. Ljemplo 27: P f x v g : a ( ( , ), ( ), ) es una ·ariante de P f v x g u a ( ( , ), ( ), ). Sin embargo, 9
Obsér·ese que no se incluye el par v v / . ( ) ( ) ( ) { } { }
s v t x t x t x / / , , / , /
¸ σ σ σ Donde f n = 1K , { }
x x x v , , ,
. ∉ y se eliminan los elementos ( )
/ σ que cumplen ( )
σ = . { } v : b f x / ), ( /
= σ σ ·
Propiedades de la Composición de Substituciones - Asociativa: σ σ σ σ σ σ
o o o o ( ) ( ) = para todas las substituciones σ σ σ
, , Lsta propiedad permite omitir los paréntesis en la composición de v substituciones - Llemento Neutro: La substitución ·acía cumple σ ε ε σ σ o o = = para toda substitución σ. - No cumple la propiedad commutativa. - ( ) ( ) ( ) E E
σ σ σ σ · = para todas las substituciones σ σ
, y las expresiones E. Sea E P x v g : = ( , , ( )) , entonces: σ
( ) ( ( ), , ( )) E P f v : g : = y ( ) )) ( , ), ( ( ) (
b g b v f P E = σ σ De la misma íorma: σ σ
o ( ) ( ( ), , ( )) E P f v b g b = Lógica de Predicados L.U.I.1.I.O. -29- P x x ( , ) no es una ·ariante de P x v ( , ). Definición 42: Sea E una expresión y 1 el conjunto de ·ariables que aparecen en í. Una substitución de renombramiento para í es una substitución de la íorma { }
v x v x / , , /
tal que { } J x x
⊆ , ,
son ·ariables distintas entre sí que no pertenecen a 1 Lógica de Predicados L.U.I.1.I.O. -30- Definición 43: Dado un conjunto íinito de expresiones simples { }
E E E C , , ,
= y una substitución ω. Se dice que ω es un unificador para C si después de aplicar la substitución, el conjunto es unitario. Ls decir, si: ( ) ( ) ( )
E E E ω ω ω = = = 2 1
Ljemplo 28: Sea { } ) , ( ), ), ( ( a v P : x f P C = , entonces { } a : a f v a x / ), ( / , / = ω es un uniíicador de C, ya que ( ) ( ) ) ), ( (
a a f P E E = = ω ω Definición 44: Se dice que un uniíicador ω para un conjunto íinito de expresiones simples es un unificador más general,umg, si para cualquier otro uniíicador ′ ω existe una substitución σ que cumple ′ = ω ω σ o . De íorma intuiti·a, el uniíicador mas general puede considerarse como el uniíicador mas simple de todos los posibles uniíicadores. Ljemplo 29: Sea { } )) , ( , ( )), , ( ), ( ( a v g v P : u g x f P C = , se puede comprobar que { } a : v u x f v / , / ), ( / = ω es un uniíicador mas general que cualquier otro uniíicador. Por ejemplo el uniíicador { } a : v u a x a f v / , / , / ), ( / = ′ ω puede ser obtenido a partir de ω aplicando la substitución { } a x / = σ . Ls decir, se cumple que ′ = ω ω σ o . Ln el ejemplo anterior, se puede obtener otro umg: { } a : u v x f v / , / ), ( /
= ω . Lsto indica que un uniíicador no esta únicamente determinado. Sin embargo se puede obser·ar que ω y ω
estan relacionados por dos substituciones de renombramiento { } u v / y { } v u / , ya que: { } v u /
· ω ω = y { } u v /
· ω ω = , y por tanto, las clausulas que resulten de aplicar dos umg distintos seran ·ariantes. 1eorema 9: Si ω
son dos umg de un conjunto de expresiones C, entonces las expresiones ω
( ) C y ω
( ) C son ·ariantes. Unificación Ll concepto de uniíicación se debe a lerbrand que presentó, en su tesis de 1930, un algoritmo no determinista para calcular el uniíicador de dos términos. Sin embargo, sería Robinson, en 1965, quien lo ·ol·iera a redisenar para aplicarlo al algoritmo de prueba de teoremas por resolución. Ll algoritmo de Robinson requería tiempo y espacio exponenciales y, desde entonces, se ha realizado un gran esíuerzo para mejorar su eíicacia. Para un tratamiento detallado del algoritmo de uniíicación y sus aplicaciones a otros campos, ·éase |Knight 89|. Sin embargo, el conjunto { } )) ( , ( ), ), ( ( w f v P a x f P no es uniíicable porque los segundos argumentos a y f;r) no uniíican. Lógica de Predicados L.U.I.1.I.O. -31- Definición 4S: Dado un conjunto de expresiones simples { }
E E E E , , ,
= , se deíine el Conjunto de Discrepancias o desacuerdos de E y se denota por ( ) E D , como el conjunto obtenido de la siguiente íorma: Ljemplo 30: Sea { } ) ), ( ), ( ( ), , ), ( ( ), ), ( ), ( ( b v h x f P a : x f P a v h x f P E = , puesto que las tres expresiones de E son similares, se buscan el primer conjunto E
cuyas discrepancias sean distintas del conjunto ·acío. Se tiene: 10
Se consideran expresiones similares, las que estan íormadas por una misma letra ,de predicado o íunción, seguida de un mismo número v de argumentos, donde n ≥ 0 A continuación se presentara el algoritmo de unificación , que toma como entrada un conjunto íinito de expresiones y de·uel·e el umg si las expresiones son uniíicables. Ln caso contrario iníorma que las expresiones no son uniíicables. Intuiti·amente se comporta de la siguiente íorma. Supóngase que se quieren uniíicar dos expresiones, se toman dos punteros comenzando por la izquierda de cada una de las expresiones. Los punteros se mue·en juntos hacia la derecha hasta que se encuentran dos símbolos diíerentes. Ln ese momento, se intentan uniíicar las dos subexpresiones encontradas. Si se pudieron uniíicar, el proceso continúa con las dos expresiones tras aplicarles la nue·a substitución, si no, las expresiones no son uniíicables y se acaba. Cuando los punteros alcancen el íinal de las dos expresiones, la composición de todas las substituciones sera el umg. Para la descripción del algoritmo es necesario deíinir qué es el conjunto de discrepancias. - Si E es unitario, entonces D E ( ) = ∅ - Si no: - Si las expresiones de E son todas "similares"
, es decir, E es de la íorma: { } ) , , , ( , ), , , , ( ), , , , (
2 1 2 22 21 1 12 11 mn m m n n
t t t f t t t f t t t f E = Se deíine { }
mf f f f
t t t E , , ,
= y D E D E
( ) ( ) = para el menor ; tal que D E
( ) ≠ ∅ Si no D E E ( ) = . Lógica de Predicados L.U.I.1.I.O. -32- { } ) (
x f E = , que al ser unitario, sus discrepancias son igual al conjunto ·acío. { } : v h E ), (
= , se buscan las discrepancias de E
, que, como no es unitario, ni las expresiones similares, quedara { } : v h E E D ), ( ) (
= = Ll menor ; que cumple que D E
( ) ≠ ∅ es 2 y, por tanto, { } : v h E D E D ), ( ) ( ) (
= = Algoritmo de Unificación 1.- Inicialización: k:= 0, σ ε
: = 2.- Si σ
E ( ) consta de una sola íórmula atómica , la sido uniíicado por σ
, entonces: Salir y De·ol·er σ
que sera el umg de E sino: ( ) ( ) E D D
σ = : 3.- Si en D
existe una ·ariable r y un término t en el que no aparece la variable v entonces: { } t v
· σ σ =
k k = +1 Vol·er al paso 2. sino: Salir y De·ol·er que el conjunto E no es uniíicable. Ll algoritmo de uniíicación presentado contiene una indeterminación en el paso 3, ya que pueden existir ·arias posibilidades a la hora de seleccionar r y t. Sin embargo, la aplicación de cualquier umg producido por el algoritmo obtiene expresiones que sólo diíieren en el nombre de las ·ariables. Lsta claro que el algoritmo termina, ya que se tiene un número íinito de ·ariables y cada aplicación del paso 3 elimina una ·ariable. Lógica de Predicados L.U.I.1.I.O. -33- Ljemplo 3J: Sea { } ) , ( )), ( ), ( ( v v P x g a f P E =
. Ljemplo 32: Sea { } )) ( ), ( , ( ))), ( ( , , ( v h v h : P : g h x a P E = Ln el paso 3 del algoritmo de uniíicación, se establece el chequeo de que el término no contenga la ·ariable. Lse chequeo se conoce como "chequeo de ocurrencias",occur check,. A continuación se da un ejemplo de su uso. Paso J: k = 0, σ ε
. Paso 2: { } v a f D ), (
Paso 3: Selecciona v v =
y t f a = ( )
. { } ) ( /
a f v = σ
, k = 1 Paso 2: { } )) ( ), ( ( )), ( ), ( ( ) (
a f a f P x g a f P E = σ
, { } ) ( ), (
a f x g D =
Paso 3: No encuentra variable en D
1 sale e indica que NO son uniíicables. Paso J: k = 0, σ ε
. Paso 2: { } : a D ,
Paso 3: Selecciona v=z, t=a. { } a : /
, k = 1 Paso 2: { } )) ( ), ( , ( ))), ( ( , , ( ) (
v h v h a P a g h x a P E = σ , { } ) ( ,
v h x D =
Paso 3: Selecciona: v=x, t=h(y). { } ) ( / , /
v h x a : = σ
. k=2 Paso 2: { } ) ( ), ( , ( ))), ( ( ), ( , ( ) (
v h v h a P a g h v h a P E = σ
. { } ) ( ,
a g v D = Paso 3: Selecciona v=y, t=g(a). { } ) ( / )), ( ( / , /
a g v a g h x a : = σ
, k=3. Paso 2: { } ))) ( ( )), ( ( , ( ) (
a g h a g h a P E = σ
es unitario. Salir y devolver σ
3 que será el umg de E. Lógica de Predicados L.U.I.1.I.O. -34- Ljemplo 33: Sea { } )) ( , ( ), , ( v f v P x x P E = . Ljemplo 34: Sea { } ) , ( , ), , ( ), , ( ( ), , , (
1 1 1 1 0 0 1 − −
x x f x x f x x f P x x P E . Paso 1: k = 0, σ ε
= . Paso 2: { } v x D ,
= Paso 3: Selecciona r~·, t~,. { } v : /
= σ , k = 1 Paso 2: { } )) ( , ( ), , ( ) (
v f v P v v P E = σ , { } ) ( ,
v f v D = Paso 3: Puesto que , aparece en f;,), el conjunto NO es uniíicable. Robinson demostró en lo que se conoce como teorema de unificación que el algoritmo de uniíicación para y de·uel·e un umg si el conjunto de expresiones es uniíicable o para e indica que el conjunto no es uniíicable si ése es el caso. Ll algoritmo de uniíicación puede llegar a ser muy ineíiciente. Ln el peor de los casos, su tiempo de ejecución puede llegar a ser una íunción exponencial de la longitud de la entrada. Lógica de Predicados L.U.I.1.I.O. -35- Algoritmo de Resolución General Definición 46: Dadas dos clausulas C
sin ·ariables comunes, tales que l C
∈ y ¬ ∈ l C
son dos literales que pueden ser uniíicados por un umg ω. Se dice entonces que C
son cláusulas resolubles y se deíine el resolvente de C
como la clausula: Ljemplo 36: Sean las clausulas: C P x
= ( ) y C P a
= ¬ ( ) . Uniíiacndo los dos únicos literales, se obtiene el umg { } a x / = ω y el resol·ente R C C ( , )
=J sera la clausula ·acía. Ljemplo 37: Sea el conjunto { } ) ( )), ( ( x P x f P ¬ . Ln lógica de Primer Orden el algoritmo de resolución requiere un paso pre·io de uniíicación de los literales por los que se resuel·e. A continuación se exponen las deíiniciones del algoritmo de resolución general con uniíicación y se demostrara que es consistente y parcialmente completo. { } { } ) ( ) ( ) ( ) ( ) , (
2 2 1 1 2 1 ,
l C l C C C R
¬ − − = ω ω ω ω ¸ Ljemplo 3S: Considérense las clausulas C P f x g v Q x v R x
= ∨ ∨¬ ( ( ), ( )) ( , ) ( ) y C P f f a g : Q f a :
= ¬ ∨ ( ( ( )), ( )) ( ( ), ) 1omando los literales l P f x g v
= ( ( ), ( )) y l P f f a g :
= ( ( ( )), ( )) se encuentra un umg { } v : a f x / ), ( / = ω Lntonces, el resol·ente de C
sera: R C C Q f a v R f a Q f f a v
( , ) ( ( ), ) ( ( )) ( ( ( )), ) = ∨¬ ∨ Se demostrara que, si el resol·ente de dos clausulas de un conjunto es la clausula ·acía, entonces ese conjunto es insatisíacible. Ln el ejemplo, esta claro que el conjunto { } ) ( ), ( a P x P ¬ es insatisíacible ya que representa la íórmula ∀ ∧ ¬ xP x P a ( ) ( ) . Para que el método sea completo ,·er pag. 42,, las clausulas no deben tener ·ariables en común. Lsto se logra manteniendo las clausulas en su íorma original y, a la hora de utilizarlas, substituyendo todas sus ·ariables por nombres de ·ariable nue·os, es decir, se aplica una substitución de renombramiento para obtener una clausula ·ariante. Se recuerda que las ·ariables en una clausula estan cuantiíicadas implícitamente de íorma uni·ersal luego el renombramiento de ·ariables no cambia la satisíacibilidad del conjunto. Lógica de Predicados L.U.I.1.I.O. -36- Algoritmo de resolución general Lntrada: Un conjunto de clausulas C Salida: Detecta si C es insatisíacible 1.- Buscar dos clausulas C C C
, ∈ resolubles 2.- Si se encuentran: 3.- Calcular R C C ( , )
y anadirlo al conjunto C 4.- Si R C C ( , )
= Ì entonces SALIR indicando que C es insatisfacible. 5.- Si no, Anadir R C C ( , )
a C , Vol·er a 1 3.- Si no se encuentran: SALIR indicando que C no es insatisfacible. 11
Ll proceso de renombramiento, no debe coníundirse con el chequeo de ocurrencias. Ll cual pre·iene la uniíicación dentro de una clausula: P f x P x ( ( )) ( ) ∨ ¬ . Lsa clausula representa la íórmula ∀ ∨¬ x P f x P x ( ( ( )) ( )) que no es ·alida. Las clausulasC P f x
= ( ( )) y C P x
= ¬ ( ) no pueden ser resueltas ya que no uniíican los literales debido al chequeo de ocurrencias. Sin embargo, si se renombran sus ·ariables, se tiene: C P f x
= ¬ ( ) Utilizando el umg { } ) ( /
x f x = ω , queda: R C C
=J Puesto que se obtiene la clausula ·acía, el conjunto { } ) ( )), ( (
x P x f P es insatisíacible, y el conjunto original: { } ) ( )), ( ( x P x f P también sera insatisíacible. Lste resultado es correcto, ya que, el conjunto anterior, teniendo en cuenta la cuantiíicación uni·ersal de las ·ariables, sería: ) ( )) ( ( x P x x f xP ¬ ∀ ∧ ∀ Lse conjunto, es, e·identemente, insatisíacible
. Utilizando la resolucion se puede comprobar que si un conjunto de clausulas es insatisIacible (teorema de completud, pag 42) se podran ir generando resolventes de una clausula con otra hasta que se llegue a la clausula vacia. A continuacion se describe el algoritmo general de resolucion: Lógica de Predicados L.U.I.1.I.O. -3¯- Ljemplo 38: A continuación se describe el comportamiento del algoritmo con el conjunto: 1 ¬ ∨ ∨ P x Q x R x f x ( ) ( ) ( , ( )) 2 ¬ ∨ ∨ P x Q x S f x ( ) ( ) ( ( )) 3 T a ( ) 4 P a ( ) 5 ¬ ∨ R a v T v ( , ) ( ) 6 ¬ ∨ ¬ T x Q x ( ) ( ) ¯ ¬ ∨¬ T x S x ( ) ( ) 8 ¬Q a ( ) { } a x / 6 3− 9 Q a S f a ( ) ( ( )) ∨ { } a x / 2 4 − 10 S f a ( ( )) ε 8 9 − 11 Q a R a f a ( ) ( , ( )) ∨ { } a x / 1 4 − 12 R a f a ( , ( )) ε 8 11 − 13 T f a ( ( )) { } ) ( / a f v 5 12 − 14 ¬S f a ( ( )) { } ) ( / a f x 7 13 − 15 J ε 10 14 − Puesto que se obtiene la clausula ·acía el algoritmo termina en el paso 3 indicando que el conjunto de clausulas es insatisíacible 12
Normalmente se dice que es reíutacionalmente completo. Ls decir, completo para reíutaciones o deri·aciones de la clausula ·acía. )
¬ ∨ ¬ ¬ ∨ ¬ ∨ ¬
∨ ∨ ¬ ∨ ∨ ¬
) ( ) ( ), ( ) ( ), ( ) , ( ), ( ), (
)), ( ( ) ( ) ( )), ( , ( ) ( ) (
x S x T x Q x T v T v a R a P a T
x f S x Q x P x f x R x Q x P
Ln las líneas 1-¯ se escriben de nue·o las clausulas del conjunto. A continuación ,líneas 8 a 15, aparecen las distintas Clausulas C ,resol·ente, junto con el umg utilizado y los números de clausulas resolubles. Ll siguiene paso consistira en demostrar que el sistema de razonamiento que utiliza el principio de resolución es consistente y parcialmente completo
. Lógica de Predicados L.U.I.1.I.O. -38- 1eorema J0 (Consistencia del principio de resolución): Si C es el resol·ente de C
entonces C es consecuencia lógica de C
. Supóngase que el resol·ente no es consecuencia lógica de C
, entonces, se tendrían los siguientes ·alores de ·erdad: Dem: Puesto que una substitución signiíica particularizar las ·ariables de una expresión. La instancia de cualquier expresión í sera consecuencia lógica de í, es decir, para cualquier substitución σ se cumple que ( ) E E σ ¬ Ln particular el umg de l
es una substitución ω y también se cumplira que ( )
C C ω ¬ ( )
C C ω ¬ . |1| Ahora resta probar que ( ) ( ) C C C ¬ ∧
ω ω Se tiene: C l RC
= ∨ y que C l RC
= ¬ ∨ ,Recuérdese que l C
∈ y que ¬ ∈ l C
, donde RC
representan el resto de literales de C
. Si ω es un umg de l
entonces ω ω ( ) ( ) l l
RC l C ω ω ω ∨ = ω ω ω ( ) ( ) ( ) C l RC
= ¬ ∨ ~¬ ∨ ω ω ( ) ( ) l RC
Por otra parte, { } { } ) ( ) ( ) ( ) ( ) , (
l C l C C C R C
¬ − − = = ω ω ω ω ¸ ~ω( ) ( ) RC RC
∨ ¦o;í
) ∨ o;RC
)¦ ∧ ¦¬o;í
) ∨ o; RC
)¦ → o;RC
) I I I V I I I ? ? Lógica de Predicados L.U.I.1.I.O. -39- ( )
- Puesto que son clausulas basicas, se pueden considerar como proposiciones con ·alor V F / . Se ha demostrado que al aplicar el algoritmo de resolución sobre un conjunto de proposiciones insatisíacibles se obtiene la clausula ·acía ,teorema de completud proposicional,. 1eorema JJ (Lema de elevación): Si C
son clausulas sin ·ariables comunes y σ
dos substituciones tales que ′ = C C
σ ( ) y ′ = C C
σ ( ) no tienen ·ariables en común y son resolubles mediante un umg ′ ω en una clausula ′ C entonces existe ,puede eterar.e, una clausula C y dos substituciones ω y σ tales que C es el resol·ente de C
mediante un umg ω y ( ) C C σ = ′ , ′ C es una instancia de C,. Véase el esquema de la íigura: C
′ = C C
σ ( ) ′ = C C
umg ÷ ′ ω
elevar a:
umg ÷ ω
ω( ) l
no puede tomar ·alor F, ya que la expresión del primer corchete sería íalsa ,tiene que ser V,. De la misma íorma, tampoco puede tomar ·alor V pues haría íalsa la expresión del segundo corchete. Por tanto, la íórmula anterior no puede tomar ·alor F y sera ·alida. Se cumple que: ( ) ( ) C C C ¬ ∧
ω ω y, uniendo con |¡Lrror! Marcador no definido.| se tiene: lalta demostrar que el algoritmo de resolución es parcialmente completo en el sentido de que, cuando el conjunto de clausulas es insatisíacible, encuentra la clausula ·acía. Los pasos a seguir en la demostración son: - Utilizando el teorema de lerbrand, si un conjunto de clausulas es insatisíacible entonces existe un subconjunto íinito de clausulas basicas insatisíacible. Lógica de Predicados L.U.I.1.I.O. -40- - Una ·ez obtenida la clausula ·acía sobre el conjunto de clausulas basicas se extrapola el resultado al conjunto original de clausulas, para lo cual se emplea el lema de ele·ación. Dem: Supóngase que: { }
RC l l l C
¸ ∨ ∨ ∨ = { }
¬ ∨ ∨ ¬ ∨ ¬ = Donde l
seran los literales que uniíicaran, RC
representan el resto de literales de cada clausula y, puesto que tiene que existir al menos un literal en cada clausula m> 0 y n > 0. Se cumplira que: { } ) ( ) ( ) ( ) (
RC l l C C
σ σ σ σ ¸ ∨ ∨ = = ′ { } ) ( ) ( ) ( ) (
σ σ σ σ ¸ + +
¬ ∨ ∨ ¬ = = ′ ′ ω es un umg de los literales: { } ) ( , ), ( ), ( , ), (
2 1 2 1 1 1 n m m m
σ σ σ σ y el resol·ente sera: ′ = ′ ′ C RC RC ω σ ω σ ( ( )) ( ( ))
U |2| Puesto que σ
no tienen ·ariables en común y σ
( ) C y σ
( ) C tampoco, la substitución ( )
σ σ ω ∪ ′ · sera un uniíicador de { }
. . ya que: ( ){ }= ∪
+ + n m m m
l l l l , , , , ,
. . σ σ
{ } = ∪ ∪ ∪ ∪
) ( , ), ( ), ( , ), (
2 1 1 2 1 2 1 1 2 1 n m m m
l l l l σ σ σ σ σ σ σ σ . .
{ } ) ( , ), ( ), ( , ), (
σ σ σ σ . . \ ese conjunto era uniíicable por ′ ω . Si existe un uniíicador, existira un umg, sea ω el umg de { }
. . , entonces, por la deíinición de umg cumplira que, para cualquier otro uniíicador ,en este caso ( )
σ σ ω ∪ ′ · , existe una substitución σ tal que ( ) ω σ σ σ ω · · = ∪ ′
|3| Sea C RC RC = ∪ ω ω ( ) ( )
el resol·ente de C
respecto a ω, entonces: ( ) = C σ σ ω ω ( ( ) ( )) RC RC
∪ = σ ω o ( ) RC RC
∪ = ,aplicando |2|, Lógica de Predicados L.U.I.1.I.O. -41- ( )( )
RC RC ∪ ∪ ′ σ σ ω · ~ ( )( ) ( )( ) = ∪ ′ ∪ ∪ ′
RC RC σ σ ω σ σ ω · · ,Puesto que C
no tienen ·ariables en común, la substitución σ
sólo aíecta a C
y no tiene eíecto sobre RC
,de igual íorma, σ
no aíecta a RC
,, por tanto: σ σ σ
∪ = ( ) ( ) RC RC y σ σ σ
∪ = ( ) ( ) RC RC , ~ ( ) ( ) ( ) ( ) = ′ ∪ ′
RC RC σ ω σ ω ,aplicando |¡Lrror! Marcador no definido.|, ~ ′ C Por tanto ( ) C C ′ = σ , es decir, ′ C es una instancia de C Ljemplo 39: Sea C P x v P f a Z R :
= ∨ ∨ ( , ) ( ( ), ) ( ) y C P f x g v Q x v
= ¬ ′ ′ ∨ ¬ ′ ′ ( ( ), ( )) ( , ) y las substituciones: { } ) ( / ), ( /
v f : a f x = σ y { } b v a x / , /
′ ′ = σ . Se obtiene el esquema: Lógica de Predicados L.U.I.1.I.O. -42- 1eorema J2 (Completud del principio de resolución general,: Si un conjunto de clausulas es insatisíacible, entonces, aplicando el algoritmo de resolución general se obtendra la clausula ·acía. C P x v P f a : R :
= ∨ ∨ ( , ) ( ( ), ) ( )
C P f x g v Q x v
= ¬ ′ ′ ∨ ¬ ′ ′ ( ( ), ( ) ( , )
= x f a v g b : g b / ( ), / ( ), / ( ) l q
= ′ ′ x a v b / , / m r
′ = ∨ C P f a g b R g b
( ( ), ( )) ( ( ))
′ = ¬ ∨¬ C P f a g b Q a b
′ = ∨¬ C R g b Q a b ( ( )) ( , )
umg ÷ ε
Siguiendo el lema de ele·ación, existira una clausula C resol·ente de C
con umg { } a x v g : v g v a f x / ), ( / ), ( / ), ( / ′ ′ ′ = ω que seguira el esquema: C P x v P f a : R :
C R g v Q a v = ′ ∨ ¬ ′ ( ( )) ( , )
σ = ′ v b / m r
Con el lema de ele·ación queda demostrado el teorema de completud: Lógica de Predicados L.U.I.1.I.O. -43- Dem: Sea C el conjunto de clausulas insatisíacibles, entonces se tiene la siguiente cadena de equi·alencias: C es insatisíacible ¸ ,por el teorema de lerbrand, Lxiste un subconjunto íinito de clausulas basicas de C insatisíacible ¹ ,Completud de resolución proposicional, Lxiste una deri·ación de un conjunto de clausulas basicas de C a la clausula ·acía. ¹ ,lema de ele·ación, Lxiste una deri·ación del conjunto C de clausulas a la clausula ·acía. NO1A: en la última implicación, para poder aplicar el lema de ele·ación, se supone que las clausulas de C no tienen ·ariables en común. Si no se utilizan ·ariantes, el algoritmo no es completo, así, por ejemplo, el conjunto: { } )) ( ( ), ( x f P x P ¬ es insatisíacible, sin embargo, P x ( ) y P f x ( ( )) no son uniíicables a no ser que se utilicen ·ariantes Lógica de Predicados L.U.I.1.I.O. -44- Estrategias de resolución Definición 47: Un literal es puro si y sólo si no existe un literal complementario con el que uniíique en el conjunto de clausulas. Una clausula que contenga un literal ¡vro es inútil en la búsqueda de la clausula ·acía, puesto que el literal ¡vro no podra ser eliminado nunca mediante resolución. Por tanto, una estrategia de borrado consiste en la eliminación de clausulas con literales puros. Ljemplo 40: Ll conjunto { } ) ( ), ( ) ( )), ( ( ) ( ), ( a Q a Q a P x f P x P a P C ¬ ∨ ¬ ∨ ¬ = es insatisíacible, sin embargo, para demostrarlo, se puede ignorar la segunda clausula, puesto que ambas contienen el literal puro P;f;·)). Definición 48: Una tautologia es una clausula que contiene el mismo literal en su íorma directa e in·ersa. Ljemplo 4J: La clausula p q r p ∨ ¬ ∨ ∨ ¬ es una tavtotogía. La presencia o ausencia de tautologías en un conjunto de clausulas no aíecta la condición de satisíacibilidad del conjunto. Un conjunto de clausulas permanecera satisíacible independientemente de que se le anadan tautologías. De la misma íorma, un conjunto de clausulas insatisíacible seguira siendo insatisíacible aunque se eliminen todas sus El metodo de resolucion es un algoritmo no determinista ya que pueden encontrarse multiples Iormas de alcanzar la clausula vacia en un conjunto insatisIacible. Muchas veces, siguiendo un determinado camino se alcanzara la clausula vacia con muchos menos pasos de resolucion que por otro camino. Durante el desarrollo del algoritmo es necesario responder las siguientes preguntas: ¿Que dos clausulas se seleccionan y sobre que literales se realiza la resolucion?. Las distintas estrategias de resolucion tratan de responder a ambas preguntas de Iorma que se mantenga la completud (si el conjunto es insatisIacible, alcanzar la clausula vacia) y que se obtenga un comportamiento eIiciente. Una de las desventajas de la utilizacion de la reglas de resolucion sin ninguna restriccion consiste en que se pueden seleccionar clausulas cuyo resolvente no sea util en el camino de busqueda de la clausula vacia. Se observa que muchas veces los resolventes son redundantes o no aportan ninguna utilidad para la busqueda. A continuacion se mencionan una serie de estrategias que serviran para eliminar el trabajo inutil. Estrategias de Borrado Una estrategia de borrado sera una tecnica en la cual se eliminan una serie de clausulas antes de que sean utilizadas. Si dichas clausulas no van a aportar nada para la busqueda de la clausula vacia, su eliminacion permitira un ahorro computacional. Eliminacion de clausulas con literales puros Lliminación de tautologías Lógica de Predicados L.U.I.1.I.O. -45- tautologías. Ls posible, por tanto, eliminar las tautologías de un conjunto de clausulas para que no inter·engan en el proceso de búsqueda sin alterar la satisíacibilidad del conjunto. Obsér·ese que los literales de una clausula deben ser exactamente complementarios para poder aplicar la eliminación de tautologías. No se pueden eliminar literales no idénticos simplemente porque sean uniíicables. Ljemplo 42: Ll conjunto { } ) ( ), ( ), ( ) ( b P a P x P a P ¬ ∨ ¬ es insatisíacible. Sin embargo, si se elimina la primera clausula el conjunto resultante sería satisíacible. Definición 49: Una clausula C subsume a una clausula D si existe una substitución σ tal que D C ⊆ ) ( σ . Ljemplo 43: Ln el conjunto { } ) ( ), ( ), ( ) ( ) ( ), ( ) ( a Q b P w R v Q a P v Q x P ¬ ∨ ¬ ∨ ¬ ∨ . La clausula ) ( ) ( v Q x P ¬ ∨ subsume a ) ( ) ( ) ( w R v Q a P ∨ ¬ ∨ puesto que la clausula resultante de aplicar la substitución { } v v a x / , / a la primera clausula, esta incluida en la segunda clausula. De esa íorma, se puede eliminar la segunda clausula, sin alterar la insatisíacibilidad del conjunto. Se puede demostrar que si una clausula D de un conjunto de clausulas es subsumida por otra, entonces el conjunto de clausulas tras eliminar D es satisíacible si y sólo si el conjunto original de clausulas lo era. Las clausulas subsumidas pueden ser, por tanto, eliminadas sin modiíicar la condición de satisíacibilidad del conjunto. Ls necesario obser·ar que, durante el desarrollo del proceso de resolución, se pueden generar resol·entes de clausulas que sean tavtotogía. o ctav.vta. .vb.vviaa.. Las estrategias de borrado deberan chequear el conjunto de clausulas original así como los distintos resol·entes generados en cada resolución. Resolución Unitaria Definición S0: Un resol·ente unitario es un resol·ente en el cual al menos uno de sus padres es una clausula unitaria ,con un sólo literal,. Una estrategia de resolución unitaria es una aplicación del algoritmo de resolución en la cual todos los resol·entes son unitarios. Ljemplo 44: Sea { } r r q r p q p C ¬ ∨ ¬ ∨ ¬ ∨ = , , , . A continuación se aplicara la estrategia de resolución unitaria, para ello, se seleccionan siempre dos clausulas resolubles tales que una de ellas tenga un literal. 1.- p q ∨ 2.- ¬ ∨ p r 3.- ¬ ∨ q r 4.- ¬r 5.- ¬p R
( , ) 2 4 6.- ¬q R
( , ) 3 4 ¯.- q R
( , ) 1 5 8.- ¡ R
( , ) 1 6 9.- r R
( , ) 3 7 10.- R
( , ) 6 7 Obsér·ese que los resol·entes generados son un subconjunto de los que se podrían generar mediante la resolución sin restricciones. Por ejemplo, las clausulas 1 y 2 podrían haberse seleccionado para obtener q r ∨ . Sin embargo ni esa clausula ni sus descendientes podran ser generados porque ninguna de las clausulas que la generan es unitaria. Eliminacion de Subsunciones Lógica de Predicados L.U.I.1.I.O. -46- Los procedimientos de resolución basados en resolución unitaria son sencillos de implementar y, normalmente, bastante eíicientes. Obsér·ese que si una clausula es resuelta con una clausula unitaria, su resol·ente tiene menos literales que la clausula original. De esa íorma los procedimientos siguen una búsqueda directa hacia la clausula ·acía ganando en eíiciencia. Desaíortunadamente, los procedimientos de iníerencia basados en resolución unitaria no son, en general, completos. Por ejemplo, el conjunto { } q p q p q p q p C ¬ ∨ ¬ ¬ ∨ ∨ ¬ ∨ = , , , es insatisíacible, sin embargo, la resolución unitaria no encontrara la clausula ·acía porque ninguna de las clausulas es unitaria. Por otro lado, restringiendo el íormato de clausulas a clausulas lorn ,clausulas con un literal positi·o como maximo, se puede demostrar que si un conjunto de clausulas lorn es insatisíacible, entonces se llegara a la clausula ·acía aplicando la estrategia de resolución unitaria. Definición SJ: Un resolvente de entrada es un resol·ente en el cual al menos uno de sus padres es una clausula del conjunto original de entrada. Una estrategia de resolución de entrada es una aplicación del algoritmo de resolución en la cual todos los resol·entes son de entrada. Ljemplo 4S: Sea { } r r q r p q p C ¬ ∨ ¬ ∨ ¬ ∨ = , , , . A continuación se aplicara la estrategia de resolución de entrada, para ello, se seleccionan siempre dos clausulas resolubles tales que una de ellas pertenezca al conjunto inicial de clausulas: 1.- p q ∨ 2.- ¬ ∨ p r 3.- ¬ ∨ q r 4.- ¬r 5.- q r ∨ R
( , ) 1 2 6.- p r ∨ R
( , ) 1 3 ¯.- ¬p R
( , ) 2 4 8.- r R
( , ) 2 6 9.- R
( , ) 4 8 Se puede demostrar que la resolución unitaria y la resolución de entrada tienen el mismo poder de iníerencia en el sentido de que si con una estrategia se puede alcanzar la clausula ·acía, con la otra también. Una consecuencia de lo anterior es que la resolución de entrada es completa para clausulas lorn, pero incompleta en general. Como contraejemplo, se puede tomar el del apartado anterior. Resolución de Entrada Resolución Lineal La resolucion lineal (tambien conocida como resolucion con Iiltrado de antepasados) es una generalizacion de la resolucion de entrada en la cual al menos una de cada par de clausulas a resolver pertenece al conjunto inicial de entrada o es un antepasado del otro padre. Lógica de Predicados L.U.I.1.I.O. -4¯- Definición S2: Sea ´ un conjunto de clausulas y C un elemento de ese conjunto. Lntonces una derivación por resolución lineal de C
desde S con cláusula inicial C es una secuencia de clausulas de la íorma n
C C C C , , ,
= tales que para cada i~0,1,...,v·1: ,1, C
es un resol·ente de C
;llamada ctav.vta cevtrat) y de otra clausula B
,llamada clausula lateral,, y ,2, Cada B
o pertenece a ´ ,sería una clausula de entrada, o es un antepasado de C
. La resolución lineal toma su nombre del aspecto lineal que presentan las iníerencias realizadas. Una resolución lineal comienza con una clausula del conjunto inicial ,llamada cláusula cabeza, y produce una cadena lineal de resoluciones como la que se muestra en la íigura para el conjunto de clausulas { } q p q p q p q p C ¬ ∨ ¬ ¬ ∨ ∨ ¬ ∨ = , , , . Obsér·ese que cada resol·ente, después del primero, se obtiene del resol·ente anterior y de alguna otra clausula del conjunto inicial o de sus antepasados. p q ∨
La resolucióon lineal e·ita muchas resoluciones inútiles centrandose en cada paso en los antepasados de una clausula y en los elementos del conjunto inicial. Se puede demostrar que la resolución lineal es completa. Ademas, no es necesario probar con todas las clausulas del conjunto inicial como clausulas cabeza ya que si un conjunto de clausulas ´ es satisíacible y S c ∪l qes insatisíacible, entonces se encuentra la clausula ·acía mediante resolución lineal tomando c como clausula cabeza. Por tanto, si se sabe que un conjunto de clausulas ´ es satisíacible, no es necesario probar con los elementos de ´ como clausulas cabeza. Resolución Ordenada La resolucion ordenada o selectiva es una estrategia de resolucion muy restrictiva en la cual cada clausula se toma como un conjunto de literales ordenados. La resolucion solo se realiza con el primer literal de cada clausula. Los literales del resolvente mantienen el orden de las clausulas padre con los literales del padre positivo (la clausula que contenia el literal por el que se resuelve aIirmado) seguidos de los literales del padre negativo (la clausula que contenia el literal por el que se resuelve negado). Lógica de Predicados L.U.I.1.I.O. -48- Ljemplo 46: Sea { } r r q r p q p C ¬ ∨ ¬ ∨ ¬ ∨ = , , , . A continuación se aplicara la estrategia de resolución ordenada ,se han ordenado los literales de cada clausula por orden alíabético,: 1.- p q ∨ 2.- ¬ ∨ p r 3.- ¬ ∨ q r 4.- ¬r 5.- q r ∨ R
( , ) 1 2 6.- r R
( , ) 3 5 ¯.- R
( , ) 4 6 La clausula 5 es el único resol·ente ordenado entre las clausulas 1 y 4. Las clausulas 1 y 3 no resuel·en puesto que sus literales complementarios no son los primeros. Por la misma razón tampoco resuel·en las clausulas 2 y 4 ni las clausulas 3 y 4. Una ·ez generada la clausula 5, resuel·e con la clausula 3 para producir la clausula 6, la cual resuel·e con la clausula 4 para producir la clausula ·acía. La resolución ordenada es la mas eíiciente ,en el ejemplo, se obtu·o la clausula ·acía en el tercer paso de resolución,. Desaíortunadamente, la resolución ordenada no es completa. Sin embargo, se ha demostrado que la resolución ordenada sí es completa para clausulas lorn. 1ras este bre·e repaso de las principales estrategias de resolución, cabe resenar que los principales sistemas de demostración automatica utilizan una combinación de las dos últimas estrategias restringidas a conjuntos de clausulas lorn. Ln particular, los sistemas de Programación Lógica utilizan la resolución lineal ordenada conocida como resolución SLD ,Setectire Livear re.otvtiov for Defivite Ctav.e., que se deíinira en la siguiente sección. Lógica de Predicados L.U.I.1.I.O. -49- Prueba de Teoremas por Resolución Una de las primeras aplicaciones de los ordenadores para la computación simbólica
íue la demostración automatica de teoremas. Una teoria esta íormada por un conjunto de consecuencias lógicas ,teoremas, que se siguen a partir de un conjunto inicial de íórmulas ,axiomas, mediante reglas de iníerencia. La axiomatización de las teorías matematicas íue estudiada de íorma intensi·a en las décadas que precedieron la aparición de los ordenadores. Se consideró que los ordenadores serían capaces de tomar como entrada un conjunto de axiomas y una íórmula y chequear si la íórmula era consecuencia lógica de los axiomas. Ll calculo de predicados es el lenguaje íormal utilizado uni·ersalmente para expresar las distintas teorías. Ln 1900, lilbert consideraba que se podría llegar a axiomatizar toda la teoría matematica, de íorma que probar nue·os teoremas sería una cuestión mecanizable. Sin embargo, en 1931, Godel demostró que cualquier sistema suíicientemente general como para contener la teoría elemental de los números naturales no es completo. Ls decir contiene íórmulas cuya ·alidez o insatisíacibilidad no puede ser demostrada. No existe, por tanto, un procedimiento general para decidir si una íórmula es consecuencia lógica de un conjunto de axiomas utilizando el calculo de predicados, de ahí que no todos los teoremas puedan ser descubiertos. Sin embargo, existen algoritmos de decisión para subconjuntos limitados como el calculo proposicional o teorías geométricas sencillas, donde se ha aplicado el ordenador como herramienta capaz de probar nue·os teoremas. Ljemplo 47: A continuación se muestran las clausulas resultantes de una posible axiomatización de la teoría de números naturales con las operaciones suma y producto. Para ello se utiliza la constante 0, la íunción s x x ( ) " " = +1 y los predicados: " a igual es " ) , , ( v x : : v x suma + = y " a igual es " ) , , ( v x : : v x producto ⋅ = 1.- ) , 0 , ( x x suma 2.- ( ) ) ( ), ( , ) , , ( : s v s x suma : v x suma ∨ ¬ 1 ) ( ) 1 ( + + = + + v x v x 3.- producto x ( , , ) 0 0 4.- ( ) ( ) : v s x producto : v x suma v v x producto , , ) , , ( ) , , ( ∨ ¬ ∨ ¬ x v x v x ∗ + = ∗ + ( ) 1 13
La computación simbólica utiliza el ordenador para manipular símbolos, se opone a la computación numérica que utiliza el ordenador como maquina de cómputo de cantidades numéricas. Un ejemplo característico consistiría en la diíerencia entre el calculo de la íunción deri·ada ,la solución es una íórmula, respecto al calculo de la deri·ada en un punto determinado ,la solución es una cantidad, Lógica de Predicados L.U.I.1.I.O. -50- A partir de los axiomas anteriores, se podrían intentar demostrar algunos teoremas sencillos de la teoría de números. Por ejemplo, para saber si existe un número X cuyo producto por sí mismo sea igual a uno. Se plantearía la conclusión: su producto se intentaría concluir: ( ) ( ) ( ) 0 , , s x x producto x ∃ Para comprobarlo, se anadiría la negación de esa conclusión al conjunto de clausulas y, si al aplicar resolución se obtiene la clausula ·acía, se deduce que existe tal número. Lógica de Predicados L.U.I.1.I.O. -51- Bibliografía |Ben-Ari, 93| M. Ben-Ari Mathematical Logic for Computer Science
Prentice Hall Intl. (1993) |Cuena 85| José Cuena íógica ívforvatica Alianza Iníormatica ,1985, |Genesereth, 87| M. R. Genesereth, N.J. Nilsson Logical foundations of Artificial Intelligence Morgan KauImann Publishers, Inc. (1987) |ISO 93| Comité ISO Internacional PROíOC. Part 1, Ceverat Covvittee Draft ;ßorraaor ^orvatira í´O). Reíerencia: ISO,ILC J1C1 SC22 \G1¯. N110. Marzo 1993 |Knight 89| Ke·in Knight |vificatiov: . Mvttiai.ci¡tivar, ´vrre, ACM Computing Sur·eys, Vol. 21 No. 1, Marzo 1989. pp. 92-124 |Kowalski ¯9| R. Kowalski íogic for Probtev ´otrivg North lolland. 1raducción espanola: Lógica, Programación e Inteligencia Artiíicial. ,19¯9, |Kumar 92| Subrata Kumar Das Deavctire Databa.e. ava íogic Progravvivg Addison-\esley ,1992, |Lloyd 8¯| John \ylie Lloyd íovvaatiov. of íogic Progravvivg. Springer Verlag . 2nd. Ld. ,198¯, |Maier, 88| David Maier, David S. Warren Computing with Logic The Benjamin/Cummings Publishing Company, Inc. (1988) |Nilsson 90| Ulí Nilsson, Jan Matuszynski íogic, Progravvivg ava Protog John \iley & Sons ,1990, Lógica de Predicados L.U.I.1.I.O. -52- |Sperschneider, 91| V. Sperschneider, G. Antoniou Logic: A Ioundation Ior Computer Science Addison-Wesley Publishing Company (1991) |Sterling 86| Leon Sterling, Lhud Shapiro 1be .rt of Protog 1he MI1 Press. 2nd. Ld. 94 ,1986, Lógica de Predicados L.U.I.1.I.O. -53- Índice Alfabético "chequeo de ocurrencias" 33 alfabeto 2 Algoritmo de resolución general
36 Algoritmo de resolución proposicional 24 algoritmo de unificación 31 Algoritmo de Uniíicación 32 ámbito 4 aridad 2 átomo 3 cabeza de una cláusula 22 chequeo de ocurrencias 36 cierre existencial 18 cláusula cabeza 4¯ cláusula Horn 22 clausula vacia 36 cláusula vacia 22 clausula ·ariante 35 cláusulas resolubles 23 completo 35 Completo 39 Completud del Algoritmo de Resolución Proposicional 2¯ completud del principio de resolución 42 composición de substituciones 28 computación simbólica 49 conectivas 3 Conjunto de Desacuerdos 31 Conjunto de Discrepancias 31 Conjunto de letras de función 2 Conjunto de letras de Predicado
3 Conjunto de simbolos de Constantes 2 Conjunto de simbolos de Variables 2 consecuencia lógica 14 contradicción 12 correcto 14 Cuantificadores 3 cuerpo de la cláusula 22 demostración automatica 49 dominio ¯ equi·alencia lógica 15 Lstrategias de resolución 44 expresión 2¯ expresión simple 2¯ Lxpresiones similares 31 lNC 19 INCP 19 Lógica de Predicados L.U.I.1.I.O. -54- lND 19 INDP 19 lNP 18 lNS 19 Iorma Clausal 21 lorma Normal Conjunti·a 19 lorma Normal Conjunti·a Prenexa
19 lorma Normal de Skolem 19 lorma Normal Disyunti·a 19 lorma Normal Disyunti·a Prenexa
19 lorma Normal Prenexa 18 fórmula atómica 4 fórmula cerrada 5 íórmula insatisíacible 12 íórmula satisíacible 12 íórmula ·alida 12 íórmulas bien íormadas 4 Godel 49 Hecho 22 lerbrand 30 lilbert 49 instancia 2¯ instancia básica 2¯ Interpretación ¯, 8, 14 lema de ele·ación 40 literal 19 literal negati·o 19 literal positi·o 19 literal puro 44 lógica 2 lógica de enunciados 2 lógica de predicados 2 lógica de predicados de orden cero 6 lógica de predicados de Primer Orden 6 lógica de predicados de Segundo Orden 6 lógica proposicional 2 matriz 18 modelo 12 nodo de inferencia 25 Objetivo 22 occur check 33 prefijo 18 programación lógica 1 razonamiento 14 recorrido 4 regla de resolución 23 Resolución proposicional 23 resolvente 23, 35 resolvente de entrada 46 Robinson 30 Signos de puntuación 3 Lógica de Predicados L.U.I.1.I.O. -55- substitución 2¯ substitución basica 2¯ substitución de renombramiento29, 30, 35 substitución ·acía 28 subsunción 45 tautologia 44 1eorema de completud proposicional 39 teorema de lerbrand 39 teorema de unificación 34 teoria 49 termino 3 umg 30 uniíicación 30 uniíicador 30 uniíicador mas general 30 ·alor de una íórmula 8 variable de cuantificación 4 ·ariable libre 4 ·ariable ligada 4 ·ariante 30 ·ariantes 28 Lógica de Predicados L.U.I.1.I.O. -56- Información de Contacto Lscuela Universitária de Ingenieria 1ecnica en Informática (L.U.I.1.O.) www.euitio.unio·i.es Jose Lmilio Labra Gayo labra¸lsi.unio·i.es Daniel Iernández Lanvin dílan·in¸unio·i.es More From This UserSkip carousel57483474 3 3 Semantica de Las Reglas de Producciona review of AI52467955-UNIDAD-2-IALispAdministracion de Proyectos1contabildadSimulacion_ISC
Sign up to vote on this titleUsefulNot usefulr34051 by Christian Reyes0.0 (0)EmbedDownloadRead on Scribd mobile: iPhone, iPad and Android.Copyright: Attribution Non-Commercial (BY-NC)List price: $0.00Download as PDF, TXT or read online from ScribdFlag for inappropriate contentMore informationShow less

References: Resolución 
 Resolución 
 Resolución 
 Resolución 
 resolución 
 resolución 
 Resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 Resolución 
 Resolución 
 resolución 
 resolución 
 resolución 
 Resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 Resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 Resolución 
 Resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 Resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 Resolución 
 resolución 
 resolución 
 resolución 
 Resolución 
 resolución 
 resolución 
 resolución 
 Resolución