Práctica 6 (LyC Verano)

Ejercicio 01

El b) es Termino y los demas son Formulas

Ejercicio 02

Entre corchetes las ligadas:
a)$\forall x\exists yP([x],[x])$
b)$\exists xP(y,y)\rightarrow \exists yP([y],z)$
c)$\exists x(\exists yP([x],[x])\wedge P([x],y))$
d)$\forall z(\forall xP([z],[x]))\vee P(x,z)$

Ejercicio 03

a) No, ya que $f_{I}(n)={\sqrt {n}}$ no es siempre natural
b) Si
c) No, por que $g_{I}(n,n)$ no es total, es decir, no esta definida para todo par n,m como lo es g en el lenguaje, sino que esta definida solamente para n = m.

Ejercicio 04

a)

Esta propiedad equivale a: Para todo x,y en R tq x<y, existe un z en Q tq x<z<y
Esto significa que los racionales son densos en los reales, es decir, siempre hay un racional entre dos reales cualesquiera.

b)

Esta propiedad significa: Todos los dias nace un esclavo

c)

Esta propiedad significa: La suma de pares es impar (No habran querido poner al reves?)

d)

• 1: Hay una persona x que quiere a todas las personas
• 2: Toda persona y es querida al menos por una persona x
• 3: Hay una persona x, que si y quiere a todas las personas entonces x quiere a y
• 4: Hay una persona x que no quiere a ninguna persona

No está en la práctica 6 del 2° cuat 2009

a)$\neg (\exists x)Politico(x)\wedge Honesto(x)$
b)$\neg (\forall x)Ave(x)\rightarrow Vuela(x)$
c)$(\forall x)((Trasc(x)\rightarrow Irrac(x))\wedge (Irrac(x)\rightarrow Trasc(x)))$
d)$(\exists x)(Ivanoff(x)\wedge (\forall y)\neg Odia(y,y)\rightarrow Odia(x,y))$
e)$((\forall x)(\exists y)Ama(x,y)\wedge \neg (\exists x)(\forall y)Ama(x,y))\vee (\exists x)(\forall y)Ama(x,y)$

Ejercicio 05

a)$(\exists x)(\exists y)(x\neq y)$
b)$(\exists x)((\exists y)(x\neq y)\wedge (\forall z)(x=z\vee y=z))$
c)$\neg (\exists x)(x=x)\vee (\exists x)(\forall y)(x=y)\vee$ Punto b)
d)Punto c) $\wedge (\exists x)P(x)$
e)$(\exists x)(P(x)\rightarrow (\forall y)(x=y))$
f)$(\exists x)(P(x)\wedge (\forall y)(x=y))$

Ejercicio 06

Podemos tomar φ = $((\forall x)(\forall y)f_{A}(x)=f_{A}(y)\rightarrow x=y)\wedge ((\exists x)(\forall y)x\neq f_{A}(y))$
Tal formula es satisfacible, por ej. fA(x)=2^x lo cumple. Para los modelos finitos no cumple, ya que en este caso una funcion inyectiva debe ser tambien sobreyectiva

Ejercicio 07

Un lenguaje podria ser A=<N,<,0>, dado que puede construirse un predicado para cada elemento tal que satisfaga unicamente a ese mismo elemento

Ejercicio 08

Recordemos que un elemento de una interpretacion es distinguible si existe un predicado unario que se verifica solo para ese elemento.

En el caso de (N, ·), el uno es el unico elemento neutro: $\forall y(y.x=y)$

En el caso de (N, +), el uno es el unico elemento que verifica que si dos numeros sumados dan 1, uno es cero y el otro no: $\forall y\forall z(y+z=x\rightarrow (\forall w(w+y=w)\wedge \exists w(w+z\neq w))\vee (\forall w(w+z=w)\wedge \exists w(w+y\neq w)))$

Ejercicio 9

(El unico predicado binario sera notado con $\leq$)

a)

Los siguientes seis predicados se verifican en un solo elemento del diagrama, y cada elemento verifica uno solo de ellos.

• El minimo:

$\forall y(x\leq y).$

• El que esta a la derecha del minimo:

$\exists y\forall z(z\leq x\rightarrow y=z)\wedge \exists z\exists y(z\neq y\wedge z\neq x\wedge y\neq z\wedge \forall w(x\leq w\rightarrow (w=y\vee w=z\vee w=x)))$
Tiene por lo menos uno abajo, y exactamente dos arriba.

• El que esta a la izquierda del minimo:

$\exists y\forall z(z\leq x\rightarrow z=y)\wedge \exists y\exists z\exists w(x\leq w\wedge x\leq z\wedge x\leq y\wedge z\neq y\wedge z\neq w\wedge z\neq x\wedge y\neq w\wedge y\neq x\wedge w\neq x\wedge \forall v(x\leq v\rightarrow (v=w\vee v=y\vee v=z))).$
Hay uno abajo, y exactamente tres arriba.

• El que esta a la izquierda del maximo:

$\exists y\forall z(x\leq z\rightarrow y=z)\wedge \exists z\exists y(z\neq y\wedge z\neq x\wedge y\neq z\wedge \forall w(w\leq x\rightarrow (w=y\vee w=z\vee w=x))).$

• El que esta a la derecha del maximo:

$\exists y\forall z(x\leq z\rightarrow z=y)\wedge \exists y\exists z\exists w(w\leq x\wedge z\leq x\wedge y\leq x\wedge y\neq z\wedge w\neq z\wedge z\neq x\wedge y\neq w\wedge y\neq x\wedge w\neq x\wedge \forall v(v\leq x\rightarrow (v=w\vee v=y\vee v=z))).$

• El maximo:

$\forall y(y\leq x).$

b)

Los siguientes cinco predicados se verifican en un solo elemento del diagrama, y cada elemento verifica uno solo de ellos.

• El minimo:

$\forall y(x\leq y).$

• El que esta arriba del minimo:

$\exists y(y\neq x\wedge y\leq x\wedge \forall z(z\leq x\rightarrow z=y))\wedge \exists y\exists z(z\neq y\wedge z\neq x\wedge y\neq x\wedge x\leq z\wedge x\leq y)$
Tiene exactamente uno abajo y dos arriba.

• El que sobresale:

$\exists y\exists z(y\neq x\wedge z\neq y\wedge z\neq x\wedge y\leq x\wedge z\leq x\wedge \forall w(w\leq x\rightarrow (w=y\vee w=z\vee w=x))\wedge \neg \exists y(y\neq x\wedge x\leq y))$
Tiene exactamente dos abajo y ninguno arriba.

• El de abajo del “maximo”:

$\exists y(y\neq x\wedge x\leq y\wedge \forall z(x\leq z\rightarrow (z=y\vee x=z))).$
Tiene exactamente uno arriba.

• El maximo: Tomo la conjuncion de las negaciones de todos los predicados anteriores. Hay un solo elemento que la cumple, y es este.

Ejercicio 10

Probar que si el universo de una interpretacion es finito con n+1 elementos, y tiene la propiedad que n elementos del universo son distinguibles, entonces todos los elementos son distinguibles.

Sea $\phi _{i}$ la funcion que es valida solo al ser evaluada en el elemento i, es decir, la funcion que distingue al elemento i del conjunto. Por hipotesis, existen las funciones $\phi _{1},\phi _{2},...\phi _{n}$.

Entonces la funcion que distingue al ultimo elemento, que es la que falta para que todos sean distinguibles, es:

$\phi _{n+1}=\neg \phi _{1}\wedge \neg \phi _{2}\wedge ...\wedge \neg \phi _{n}$