Práctica 4 (pre 2010, Paradigmas)

Ejercicio 01

Convertir a Forma Normal Conjuntiva las siguientes formulas proposicionales:

• i. p -> p
• ii. (p & q) -> p
• iii. ¬(p & q) -> (¬p | ¬q)
• iv. (p | (¬p -> q)) -> (p | q)
• v. (p | q) -> p
• vi. (p & q) | (p & r)

• i. {□}
• ii. {□}
• iii. {□}
• iv. {□}
• v. { {¬q,p} }
• vi. { {p},{q,r} }

Ejercicio 02

• i. Determinar si las formulas del ejercicio anterior son tautologıas utilizando el metodo de resolucion para la logica proposicional.
• ii. ¿Se deduce (p & q) de (¬p -> q) & (p -> q) & (¬p -> ¬q)? Contestar utilizando el metodo de resolucion para la logica proposicional.

• i. i-iv Tautologias
• ii. $(\neg p\rightarrow q)\wedge (p\rightarrow q)\wedge (\neg p\rightarrow \neg q)=(p\vee q)\wedge (\neg p\vee q)\wedge (p\vee \neg q)=$ { {p,q}, {~p,q}, {p,~q} } = { {p,q}, {~p,q}, {p,~q}, {p} } = { {p,q}, {~p,q}, {p,~q}, {p}, {q} } $\rightarrow$ Con lo cual debe cumplirse $p\wedge q$.

Ejercicio 04

Convertir a Forma Normal Negada (NNF) las siguiente formulas de primer orden:

• i. $\forall x.\forall y.(\neg Q(x,y)\rightarrow \neg P(x,y))$
• ii. $\forall x.\forall y.((P(x,y)\wedge Q(x,y))\rightarrow R(x,y))$
• iii. $\forall x.\exists y.(P(x,y)\rightarrow Q(x,y))$

• i. $\forall x.\forall y.(Q(x,y)\vee \neg P(x,y))$
• ii. $\forall x.\forall y.(\neg P(x,y)\vee \neg Q(x,y)\vee R(x,y))$
• iii. $\forall x.\exists y.(\neg P(x,y)\vee Q(x,y))$

Ejercicio 05

Convertir a Forma Normal de Skolem y luego a Forma Clausal las siguientes formulas de primer orden:

i)
Skolem:
$\exists x.\exists y.x<y$
$=\exists y.a<y=a<b$
Clausal: {{a < b}}

ii)
Skolem:
$\forall x.\exists y.x<y$
$=\forall x.x<f(x)$
Clausal: {{x < f(x)}}

iii)
Skolem:
$\forall x.(\neg P(x)\vee \exists y.(P(y)\wedge Q(y)))$
$=\forall x.(\neg P(x)\vee (P(f(x))\wedge Q(f(x)))))$
$=\forall x.([\neg P(x)\vee P(f(x))]\wedge [\neg P(x)\vee Q(f(x))])$
$=\forall x.[\neg P(x)\vee P(f(x))]\wedge \forall x.[\neg P(x)\vee Q(f(x))]$
Clausal: {{~P(x) v P(f(x))}, {~P(x) v Q(f(x))}}

iv)
Skolem:
$\exists x.\forall y.(P(x,y)\wedge Q(x)\wedge \neg R(y))$
$=\forall y.(P(a,y)\wedge Q(a)\wedge \neg R(y))$
Clausal: {{P(a,y)},{Q(a)},{~R(y)}}

v)
$\forall x.(P(x)\wedge \exists y.(Q(y)\vee \forall z.\exists w.(P(z)\wedge \neg Q(w))))$
$=\forall x.(P(x)\wedge \exists y.\forall z.\exists w.(Q(y)\vee (P(z)\wedge \neg Q(w))))$
$=\forall x.(P(x)\wedge \forall z.(Q(f(x))\vee (P(z)\wedge \neg Q(g(z)))))$
$=\forall x.(P(x)\wedge \forall z.([Q(f(x))\vee P(z)]\wedge [Q(f(x))\vee \neg Q(g(z))]))$
$=\forall x.\forall z.(P(x)\wedge [Q(f(x))\vee P(z)]\wedge [Q(f(x))\vee \neg Q(g(z))])$
Clausal: {{P(x)},{Q(f(x)) v P(z)},{Q(f(x)) v ~Q(g(z))}}

Ejercicio 06

Escribir en logica de primer orden y luego convertir a Forma Clausal los siguientes enunciados expresados en lenguaje natural:

• i) Todo conjunto no vacıo de numeros naturales tiene un elemento mınimo.

Utilizar los siguientes predicados: N(x) para expresar que x es un numero natural, C(x) para x es conjunto, $x\in y$ para x pertenece a y y $x\leq y$ para x menor o igual a y.

$\forall c.((C(c)\wedge \exists x.(N(x)\wedge x\in c))->\exists y.(y\in c\wedge \forall z.(z\in c->y<=z)))$

• ii) Un dragon es feliz si todas sus crıas pueden volar. Los dragones verdes pueden volar. Un dragon es verde si al menos uno de sus progenitores es verde, y es rosa en cualquier otro caso.

Utilizar los siguientes predicados: D(x) para expresar que x es un dragon, P(x, y) para x es el progenitor de y, F(x) para x es feliz, V (x) para indicar que x puede volar, V E(x) para x es verde y R(x) para x es rosa.

$\forall d.((D(d)\wedge \forall c.(P(d,c)\wedge V(c))->F(d)))$
$\forall d.((D(d)\wedge VE(d))->V(d))$
$\forall d.(((D(d)\wedge \exists p.P(p,d)\wedge VE(p))->VE(d))\wedge ((D(d)\wedge \neg \exists p.P(p,d)\wedge VE(p))->R(d)))$

Ejercicio 07

Es un hecho que A = Pago(s) Pero en nuestro universo ocurre que B = Pago(s) => -Pago(s)

Queremos demostrar que si ocurren A y B, entonces C = Presidente(p) es valida.

Esto es ver que A ^ B => C B = -Pago(s) v -Pago(s) = -Pago(s)

A ^ B = Pago(s) ^ -Pago(s), que es una contradiccion por lo tango al ser el antecedente falso, C es verdadero, quedando demostrado que el presidente es espia.