Document related concepts
Transcript
Ejercicio 1 Decidir si la siguiente afirmación es verdadera o falsa:
Si k es un número natural y a es una fórmula del cálculo proposicional con complejidad menor que k, entonces el número de
variables proposicionales de ex es menor que k + 1.
Ejercicio 2 Sea a una fórmula del cálculo proposicional tal que Var(a) ~ {Pl, pd· Sea ex(Pl) la fórmula que se obtiene de sustituir
en ex la variable P2 por Pl en ca.:;o que P2 E Var(a), mientras que a(pd = a si P'2 no figura en a Probar que si a(Pl) es tautología,
entonces (((Pl ~ P2) /\ (P2 ~ Pl)) -+ ex) es tautología.
Ejercicio 3 Decidir si existe una fórmula a de la lógica proposicional tal que
Ejercicio 4 Sea L un lenguaje con igualdad y un símbolo de función binario p. Sean 1 y J las siguientes
interpretaciones de L. El universo de 1 son los números reales, el universo de J es el intervalo real [-1, 1] Y j2 se interpreta
como el producto en ambos casos. Encontrar un enunciado que sea válido en 1 pero no en J.
Ejercicio 5 Sea L un lenguaje con un símbolo de predicados temario p3. Decidir si el siguiente enunciado es
universalmente válido:
(Vx~yVZ(P3(X, y, z) /\ P3(X, z, y)) ~ Vx~yVzP3(z, y, x))
