Práctica 5: Cálculo de Predicados (Lógica y Computabilidad)

Ejercicio 01

• 1. Es un termino. c, x, f(c, x).
• 2. No es un termino, pues f es binaria.
• 3. No es un termino, pues aparece un cuantificador.
• 4. Es un termino. c, x, y, f(y, c), f(x, y), f(f(x, y), f(y, c)).

Ejercicio 02

a, b y e son formulas. Las otras dos no.

Ejercicio 03

Se indican en negrita

• 1. ∀x∃yP(x, y)
• 2. (∀xP(f(x, x), y) -> ∀y∀xP(x, y))
• 3. (∃x∃y∃z((P(x, y) ^ P(y, z)) -> P(x, z)) ^ ∀wP(w, z)).

Ejercicio 04

• 1. Los racionales son densos en los reales. Esto es, entre dos reales distintos, siempre hay un racional distinto a ambos. Distinto se deduce de menor.
• 2.
  • a) La coprimalidad es transitiva
  • b) Dos numeros pares no son nunca coprimos.
  • c) Si un numero no es par, existe otro entero que es coprimo con el.
  • d) Dados dos numeros, uno de ellos par, existe un tercero que no es coprimo con el par, y sı lo es con el otro.

Ejercicio 05

• 1. ∃x∀y(x = y).
• 2. ∃x∃y(x != y).
• 3. ∃x∃y(x != y ^ ∀z(x = z ν y = z)).
• 4. ¬(∃x(x = x)) ν ∃x∀y(x = y) ν ∃x∃y(x != y ^ ∀z(x = z ν y = z)).

Ejercicio 06

φ va a ser el enunciado “El unico numero que al cuadrado da 1 es el 1”. ψ va a ser “Si dos numeros multiplicados dan 1, son iguales”. φ = ∀x(x · x = 1 -> x = 1) y ψ = ∀x∀y(x · y = 1 -> x = y).

Ejercicio 07

Si hacemos I1 = (C, ·^2) y I2 = (N, ·^2), tenemos lo pedido.

Ejercicio 08

• 1. ∀x∀y(R(x, y) ^ ¬R(y, x) -> ∃z(R(x, z) ^R(z, y) ^ ¬R(z, x) ^ ¬R(y, z))). Agregamos los ¬R para sustituir la falta de igualdad.
• 2. ∃x(∀yR(x, y) ^ ∃y∃z(R(x, y) ^ ¬R(y, x) ^ (∀w(R(w, y) -> R(w, x))) ^ (R(x, z) ^ ¬R(z, x) ^ (∀w(R(w, z) -> R(w, x))))^(R(z, y) -> ¬R(y, z))^(R(y, z) -> ¬R(z, y)))^∀v(R(x, v)^¬R(v, x)^(∀w(R(w, v) -> R(w, x))) -> ((R(z, v) ^ R(v, z)) ν (R(y, v) ^ R(v, y))))). Es decir, hay un primer elemento, hay dos atomos, son distintos y son los unicos

Ejercicio 09

• 1. ' = 8x9y9z(z 6= y ^ x + z + y = x). Hay dos elementos distintos que sumados dan el neutro de la suma.
• 2. = 8x9y(x = y · y). Todo numero es un cuadrado.

Ejercicio 10

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 que verifica 8y(y·x = y). Esto es, es el neutro de la funcion. 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: 8y8z(y+z = x -> (8w(w+y = w)^9w(w+z 6= w))ν(8w(w+z = w)^9w(w+y 6= w))).

Ejercicio 11

El unico predicado binario sera notado con �.

• 1. Los siguientes seis predicados se verifican en un solo elemento del diagrama, y cada elemento verifica uno solo de ellos.
  • El mınimo: 8y(x � y).
  • El que esta a la derecha del mınimo: 9y8z(z � x -> y = z) ^ 9z9y(z 6= y ^ z 6= x ^ y 6= z ^ 8w(x � w -> (w = y ν w = z ν w = x))) (i.e. tiene por lo menos uno abajo, y exactamente dos arriba)
  • El que esta a la izquierda del mınimo: 9y8z(z � x -> z = y) ^ 9y9z9w(x � w ^ x � z ^ x � y ^ z 6= y ^ z 6= w ^ z 6= x ^ y 6= w ^ y 6= x ^ w 6= x ^ 8v(x � v -> (v = w ν v = y ν v = z))). Hay uno abajo, y exactamente tres arriba.
  • El que esta a la izquierda del maximo: 9y8z(x � z -> y = z) ^ 9z9y(z 6= y ^ z 6= x ^ y 6= z ^ 8w(w � x -> (w = y ν w = z ν w = x))).
  • El que esta a la derecha del maximo: 9y8z(x � z -> z = y) ^ 9y9z9w(w � x ^ z � x ^ y � x ^ y 6= z ^ w 6= z ^ z 6= x ^ y 6= w ^ y 6= x ^ w 6= x ^ 8v(v � x -> (v = w ν v = y ν v = z))).
  • El maximo: 8y(y � x).
• 2. Los siguientes cinco predicados se verifican en un solo elemento del diagrama, y cada elemento verifica uno solo de ellos.
  • El mınimo: 8y(x � y).
  • El que esta arriba del mınimo. 9y(y 6= x ^ y � x ^ 8z(z � x -> z = y)) ^ 9y9z(z 6= y ^ z 6= x ^ y 6= x ^ x � z ^ x � y) tiene exactamente uno abajo y dos arriba.
  • El que sobresale. 9y9z(y 6= x ^ z 6= y ^ z 6= x ^ y � x ^ z � x ^ 8w(w � x -> (w = y ν w = z ν w = x)) ^ ¬9y(y 6= x ^ x � y)). Tiene exactamente dos abajo y ninguno arriba.
  • El de abajo del “maximo”. 9y(y 6= x ^ x � y ^ 8z(x � z -> (z = y ν 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 12

Nota: No todos los elementos de todas las interpretaciones son distinguibles. Por ejemplo, si L es un lenguaje de primer orden que no tiene constantes, sımbolos de funcion ni predicados, la interpretacion Z no tiene elementos distinguibles. Lo mismo ocurre si le agregamos un sımbolo de funcion unario, y lo interpretamos como la funcion sucesor. Y tambien si agregamos a esto ultimo un predicado binario que mandamos en la relacion �.