UNGS - Lógica y Teorı́a de Números - Turno noche
Ejercicios de Parcial para Practicar
UNIDAD 1
1. (a) Determinar, usando solo equivalencias, si la fórmula (P ⇒ Q) ∧ (¬P ⇒ R) ⇒ Q ∨ R
es una tautologı́a, contradicción o contingencia.
(b) Sabiendo que P ⇒ Q es falso, determinar, si es posible, el valor de verdad de la
fórmula P ⇒ Q ∧ ¬P ⇒ R ⇒ Q ∨ R.
2. Demostrar utilizando solo equivalencias que las fórmulas P ∨ Q ∧ ¬R ∨ ¬Q ⇒ ¬R y
¬(P ∨ ¬Q) ∨ ¬R son equivalentes.
3. (a) Determinar, una fórmula equivalente a ¬P ∨ ¬(¬Q ∧ ¬R) ∧ (¬Q ⇒ P ) que esté en
forma normal conjuntiva completa.
(b) Sabiendo que P ∧ Q es falso, determinar, si es posible, el valor de verdad de la
fórmula P ⇒ P ∨ ¬Q ⇔ (¬R ⇒ ¬P ) ∨ (Q ⇒ ¬P ).
4. Sean A = ¬P ∨ Q ∧ P ⇒ Q y B = ¬Q ⇒ P .
(a) Demostrar utilizando solo equivalencias que las fórmulas A y B son equivalentes.
(b) Obtener una fórmula equivalente a A que esté en forma normal disyuntiva completa.
5. Sean ϕ = (¬Q ⇔ P ) ∨ (¬P ⇒ Q) y ψ = ¬P ⇒ Q.
(a) Demostrar que ϕ y ψ son equivalentes utilizando equivalencias.
(b) Obtener una fórmula equivalente a ψ que esté en FNC completa y otra que esté en
FND completa.
6. (a) Sabiendo que P ∧ R ⇔ ¬R es verdadero, determinar, si es posible, el valor de verdad
de ϕ = ¬P ∨ Q ∧ R ⇒ ¬Q ⇒ P ∧ R.
(b) Dar una fórmula equivalente a ϕ que esté en forma normal disyuntiva completa.
7. Determinar, utilizando solo equivalencias, si la siguiente fórmula es una tautologı́a, con-
tradicción o contingencia:
(P ∨ Q) ∧ R ⇔ ¬(P ∧ R) ∧ ¬(Q ∧ R).
8. (a) Sabiendo que Q ∧ P ∨ ¬P ≡ F y ¬(P ⇒ ¬R) ≡ F, determinar, si es posible, el valor
de verdad de la fórmula ¬S ⇒ P ⇒ R ⇔ ¬R ∧ Q ⇒ S.
(b) Obtener una fórmula equivalente a ¬(P ⇒ ¬R) que esté en forma normal conjuntiva
completa.
UNIDAD 2
1. Sea ϕ : ∃xq(x) ∧ ¬∀yp(x, y) ⇒ q(y).
(a) Demostrar que ϕ es inválida.
(b) Escribir a ϕ en forma normal prenexa conjuntiva.
2. Sea ϕ = ∃x p(x) ∧ q(x) ⇒ ∀y p(y)
(a) Demostrar que es inválida. ¿Es insatisfacible? Justificar
(b) Determinar una fórmula equivalente a ϕ que esté en forma normal prenexa conjun-
tiva.
3. Sea W : ∃x p(x, a) ⇒ ∀y q(y) ∨ p(b, y).
(a) Determinar todos los posibles valores de a y de b tales que W sea verdadera bajo la
siguiente interpretación:
D = {1, 2}
p(x, y) : “ xy = 1”
q(x) : “x es par”
I:
y=1
a = ...
b = ...
(b) Dar una fórmula equivalente a W que esté en forma normal prenexa.
4. Sea A = ∀x (p(x) ∨ q(x)) ⇒ ∀x p(x) ∨ ∀x q(x).
(a) Demostrar que A no es una fórmula válida.
(b) Obtener una fórmula equivalente a A que esté en forma normal prenexa.
5. Sea ϕ : ∃y(¬∃x p(x, y) ∧ q(x)) ⇒ q(y).
(a) Definir una interpretación I que incluya al conjunto D = {0, 1} y a los predicados
p(x, y) : “x < y” y q(x) : “x > 0”, y que sea un antimodelo para ϕ.
(b) Dar una fórmula equivalente a ϕ que esté en forma normal prenexa.
6. (a) Sea W = ∃x ¬∀yq(x, y) ∧ p(f (x), y) . Definir una interpretación que sea un modelo
para W y que incluya las siguientes asignaciones:
• q(x, y) : “x = y”
• p(x, y) : “x > y”.
(b) Escribir a la fórmula p(x) ∧ ∃xq(x) ⇒ ¬∀xr(x) en forma normal prenexa conjuntiva.
7. Sea W : ∃x p(y) ∧ q(x, y) ⇒ ∀x p(x).
(a) Utilizar el dominio D = {2, 3} para definir una interpretación que resulte ser un
antimodelo para W .
¿Se puede asegurar que W es insatisfacible? Justificar
(b) Escribir W en forma normal prenexa conjuntiva.
8. Sea W : ¬∀x p(x) ⇒ ∀x ¬p(x) ∨ q(x, y)
(a) Encontrar un antimodelo para W .
(b) Hallar una fórmula equivalente a W que esté en forma normal prenexa.
UNIDAD 3 - Conjuntos
1. (a) Dado el conjunto universal U = {1, {8}, −6, 7, 10, {1, 2, 8}, 8} y dado los subconjun-
tos A = {1, −6, 7, 8}, B = {1, {8}, 10} y C = {−6, {1, 2, 8}, 8} Hallar P (A) ∩ (B △
C)c
(b) Sean A y B subconjuntos del conjunto referencial U. Utilizando propiedades probar
que:
(B △ A) − Ac = A − B
2. (a) Dado el conjunto universal U = {1, 2, 3, {4, 7}, 5, 8, 9} y dado los subconjuntos A =
{1, 3, 6, 9}, B = {5, 6, 8, 9} y C = {1, {4, 7}, 9}. Hallar (B − C)c △ A
(b) Sean A y B subconjuntos del conjunto referencial U. Utilizando propiedades probar
que:
A ⊆ B ⇒ (A ∪ B) ∩ C − (A △ B) = A ∩ C
3. (a) Dados el conjunto referencial U = {n ∈ N : n es primo} y los subconjuntos
A = {a ∈ U : a ≥ 20} y B = {b ∈ U : b es impar y menor a 15}. Hallar B∆Ac .
(b) Sean A , B y C subconjuntos del conjunto referencial U. Utilizando propiedades
probar que:
A ⊆ B ⇒ A − (C − B) = A
4. (a) Dado el conjunto universal U = {1, 2, −4, {8, 9}, 7, 5, 6, −1, 3{5, 6}} y dado los sub-
conjuntos A = {1, 2, −4}, B = {{8, 9}, 7, 1} y C = {5, 6, −1, 3, {5, 6}} Hallar P (A)
y determinar si B c − C esta incluido o pertenece a P (A).
(b) Sean A , B y C subconjuntos del conjunto referencial U. Utilizando propiedades
probar que:
(A − B) △ (B c ∪ Ac ∪ C) = Ac ∪ (B ∩ C)
5. Sean A, B y C subconjuntos del conjunto universal U. Demostrar usando propiedades
que: A − (B ∩ C) = (A − B) ∪ (A − C).
6. Sean A, B subconjuntos del conjunto universal U. Demostrar la siguiente igualdad uti-
lizando propiedades de conjuntos:
B ∩ (A − Ac )∆(B − (B ∩ A)) = B
7. Sean A, B y C subconjuntos del conjunto referencial U. Utilizando propiedades probar
que:
A ⊆ B ⇒ A − (C − B) = A.
8. Sean A y B subconjuntos del conjunto universal U. Demostrar, utilizando propiedades
de conjuntos la siguiente igualdad de conjuntos:
(A∆B)c − A = Ac − B
UNIDAD 3 - Relaciones
1. Sea R la relación definida por R = {(x, y) ∈ A × A : (x + y)2 = 4x2 }. Sea A el conjunto
definido por:
(a) A = {−1, 1, 3}. Determinar si la relación es antisimétrica y transitiva. Justificar.
(b) A = Z. Demostrar que la relación es antisimétrica.
2. (a) Sea A = {0, 1, 2, 3, 4}, y R = {(x, y) ∈ A × A : 3x − y > 0·}. Determinar si la
relación es reflexiva, simétrica y antisimétrica.
x−y
(b) Sea R = {(x, y) ∈ Z2 : 3
∈ Z}. Probar que la relación es simétrica y transitiva.
3. (a) Dado el conjunto A = {a, b, c, d}, definir una relación sobre A que sea no reflexiva,
no simétrica, no antisimétrica y no transitiva simultáneamente. Justificar.
(b) Sea R = {(x, y) ∈ Z2 : x · (y − 1) = 0}. Demostrar que la relación es antisimétrica.
4. (a) Sea A = {x ∈ N : x < 10} y R = {(x, y) ∈ A × A : x + y = 10}. Determinar si R
es reflexiva, simétrica, antisimétrica y/o transitiva.
(b) Sea R una relación en Z definida por: xRy ⇔ ∃k ∈ Z : x = y + 10 · k. Probar que
R es transitiva.
5. Sean A = {1; 2; 3; 4; ...; 30} y R = {(x, y) ∈ A × A : x − 3y es par}
(a) Probar que R es una relación de equivalencia en A.
(b) Hallar la clase de equivalencia del 1.
6. Sea R = {(x, y) ∈ N × N : x2 + y 2 es par}. Determinar si R reflexiva, simétrica, anti-
simétrica, transitiva, de orden y/o de equivalencia.
7. Sea A = {−20, −19, ..., 19, 20} y sea R una relación de equivalencia en A definida por
R = {(x, y) ∈ A × A : 9x − 5y es múltiplo de 4}.
(a) Demostrar que R es transitiva.
(b) Determinar la clase de 7.
8. Sea A = {x ∈ Z : 1 ≤ x ≤ 20} y sea la relación R en A definida por:
xRy ⇔ x + 3y es divisible por 4
(a) Demostrar que R es transitiva.
(b) Sabiendo que R es una relación de equivalencia determinar la clase del 1.