Septiembre 2012. Examen LI

7/23/2019 Septiembre 2012. Examen LI

http://slidepdf.com/reader/full/septiembre-2012-examen-li 1/5

L ogica Inform´ atica (2o de Ingenierıa Inform´ atica - Ingenierıa del Software ) (13–Septiembre-2012)

Nombre y Apellidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

UTILIZA S OLO ESTE FOLIO PARA LA RESPUESTA

Ejercicio 1.– Haciendo uso de tableros sem´anticos, decide si la f ormula p → q es consecuencialogica del conjunto de f ormulas {r → p, p → (r p), r → q }:






Ejercicio 2.– Sea S el siguiente conjunto de f ormulas proposicionales:

{ p q → m, m (s r ) → u, u w → j, u r → v, p s r → v}

Decide, usando el algoritmo DPLL, si S es consistente. Y en caso de que lo sea, explicita elmodelo que se encuentra al aplicar el algoritmo.






Ejercicio 3.– Se pide:

1. Calculese la forma Prenex, de Skolem y clausal de la siguiente f´ ormula:

( x )( y)[[P (x, y ) → Q (y, x )] [Q (x, y ) S (x, y )]] → ( x )( y)[P (x, y ) → S (x, y )]

2. Obtener, si es posible, un unicador de m´ axima generalidad para cada uno de los siguientesconjuntos:

(a) {Q (f (x ), a , y ), Q (u, f (v), b)}(b) {P (f (f (x )) , z ), P (f (u ), f (v))}






Ejercicio 4.– Sea Σ el conjunto de cl ausulas

{¬P (x, c ) ¬ P (x, b )) , ¬P (x, a ) P (x, b ), ¬P (x, z ) P (x, c )}

(donde a , b y c son sımbolos de constante). Se pide:

(a) Probar mediante resoluci´ on que Σ |= ¬ x z (P (x, z ) P (x, a ))

(b) Probar aplicando el teorema de Herbrand que Σ |= x z (P (x, z ) P (x, a ))






Ejercicio 5.– Las relaciones de parentesco verican el siguiente conjunto propiedades:

• Si x es hermano de y, entonces y es hermano de x.

• Todo el mundo es hijo de alguien.

• Nadie es hijo del hermano de su padre.

• Cualquier padre de una persona es tambien padre de todos los hermanos de esa persona.

• Nadie es hijo ni hermano de sı mismo.

Se pide:

1. Formalizar Σ en un lenguaje de primer orden usando s´ olo los siguientes predicados: Her (x, y )para expresar que x es hermano de y e Hijo (x, y ) para expresar que x es hijo de y.

2. Decidir si la siguiente estructura es un modelo de Σ:

|M | = {a,b,c ,d,e }, Her M = {(a, b ), (b, a ), (e, c ), (e, d ), (c, d ), (c, e ), (d, e ), (d, c )} y

Hijo M = {(a, e ), (b, e), (e, a ), (c, a ), (d, a ), (d, b)}

Septiembre 2012. Examen LI

Documents

Transcript of Septiembre 2012. Examen LI