Tarea-Examen 1, Álgebra.

Evelyn Ramı́rez de la Cruz

Cristian Eduardo Pichardo Rico
Luis Angel Duque Maldonado
Uriel Jovanni Aguirre C.

29 de octubre de 2020

1. Lógica
Ejercicio 1. Consideramos un lenguaje formado por el conjunto de sı́mbolos {M, I, U }.
Una sucesión de sı́mbolos es una palabra si empieza con la letra M . Consideramos a
el conjunto ∆ = {M I} y las siguientes reglas de inferencia:
MXUUY MX MXIIIY MXI
R1 : R2 : R3 : R4 :
MXY MXX MXUY MXIU
donde X y Y son sucesiones de sı́mbolos del lenguaje. Demuestra que (o argumenta por qué no)
las siguientes palabras son consecuencias de ∆.
a) M IU b) M U IU I c) M U

a) M IU Sı́ es una consecuencia de ∆.

Dem. Como M I ∈ ∆, aplicandole R4 y obtenemos M IU , que era la palabra que querı́amos de-
mostrar. Esto se permute debido a que las sucesiones de simbolos X y Y pueden ser vacı́as.
∴ M IU es una consecuencia de ∆. 

b) M U IU I Sı́ es una consecuencia de ∆

Dem. Como M I ∈ ∆, aplicandole R2 obtenemos M II....(1).

A (1) le aplicamos, nuevamente, R2 y obtenemos M IIII....(2).
A (2) l aplicamos R3 (como X y Y pueden ser sucesiones de simbolos vacı́as), tomamos a nuestra
conveniencia las primeras tres is, y obtenemos M U I...(3).
A (3) le aplicamos R2 y obtenemos M U IU I que era la palabra que querı́amos demostrar.
∴ M U IU I es una consecuencia de ∆. 

c) M U no es una consecuencia de ∆.
M U no es una consecuencia de ∆ porque no hay ninguna manera posible de que avanzando desde
M I, mediante las reglas de inferencia, nos de una palabra de la forma M III, que es la que
necesitamos para tener una U inmediatamente despues de la M sin ninguna sucesión despues de
esta.
Y esto pasa debido a que desde M I solo se puede avanzar por R4 , que poco ayuda en este caso,
ya que después de usarla solo podemos avanzar a más palabras mediante R2 y serán de la forma

1
M IU IU IU IU... . Y por R2 que duplica las sucesiones que vienen despues de la primera M . Esta
serı́a una gran opción porque podrı́amos duplicar la I de la palabra M I tantas veces hasta que
podamos usar R3 para transformar las I 0 s en U 0 s y luego de ello eliminar el sobrante de U 0 s
formando parejitas de U 0 s y aplicando R1 de tal forma que al final solo quede la palabra M U , pero
esto es imposible de hacer porque al usar R2 en M I las I 0 s se van duplicando exponencialmente,
y siempre, el número de I 0 s no es divisible entre 3 (por cuestiones de que el número de I 0 s que se
tienen al aplicar R2 n veces a M I viene dado por 2n ) por lo que siempre va a quedar una o dos
I 0 s sueltas y no se podrá hacer lo descrito de convertir todas las I 0 s en un número de U 0 s impares,
para aplicar R1 tantas veces fuese necesario y obtener M U .
Por lo que M U no es consecuencia de ∆

Ejercicio 2. Demuestra que las siguientes propiedades son ciertas en cualquier sistema
formal.
a) Si Γ ` A y A ` B entonces Γ ` B.
b) ∆ ` A si y sólo si existe Γ ⊆ ∆ finito tal que Γ ` A.

a) Si Γ ` A y A ` B entonces Γ `

Dem. Sea SF un sistema formal arbitrario que tenga un lenguaje y un conjunto de reglas de
inferencia.
Como Γ ` A entonces podemos decir que existen fórmulas de A1 , ..., An tales que An = A y que
cada Ai ∈ Γ ó se deduce de anteriores por alguna regla de inferencia. Entonces podemos decir que
A es un teorema de Γ.
Como de A podemos deducir B entonces podemos decir que existen fórmulas de A1 , ..., An , B1 , ..., Bk
tales que Bk = B y que cada A, B ∈ Γ ó se deduce de una anterior mediante reglas de inferencia.
Por lo que B también es un teorema de Γ.
Por lo tanto, si Γ ` A y A ` B entonces Γ ` B. 

b) ∆ ` A si y sólo si existe Γ ⊆ ∆ finito tal que Γ ` A.

Dem. Sea SF un sistema formal arbitrario que tenga un lenguaje y un conjunto de reglas de
inferencia.
⇒] Suponemos ∆ ` A entonces existen A1 , ..., An+1 ∈ Φ (Realmente podemos decir que existen
A, 1, ..., An+m ∈ Φ) tales que An = A. Sea Γ = A1 , ..., An tal que si ∆ = A1 , ..., An , An+1 entonces
Γ ⊆ ∆. Como dijimos que An = A entonces Γ ` A
⇐] Por hipotesis ∃A1 , ..., An ` Φ tales que An = A. A ∈ Γ o se deduce de anteriores por medio de
reglas de inferencia. Como Γ ⊆ ∆ y por la definición de subconjunto si A ∈ Γ entonces A ∈ ∆.
∴ Podemos afirmar que ∆ ` A ⇐⇒ Γ ⊆ ∆ finito tal que Γ ` A se cumple. 

Ejercicio 3. Has la tabla de verdad de las siguientes proposiciones:

a) α → (β ∧ ¬α) b) (α ∨ β) ∧ ¬α c) (α ∧ ¬α) → β

α β ¬α β ∧ ¬α α → (β ∧ ¬α)
1 1 0 0 0
1 0 0 0 0
0 1 1 1 1
0 0 1 0 1

Tabla 1: tabla de verdad (a)

2
 α β α∨β ¬α (α ∨ β) ∧ ¬α
1 1 1 0 0
1 0 1 0 0
0 1 1 1 1
0 0 0 1 0

Tabla 2: tabla de verdad (b)

α ¬α α ∧ ¬α β (α ∧ ¬α) → β
1 0 0 0 1
1 0 0 1 1
0 1 0 0 1
0 1 0 1 1

Tabla 3: tabla de verdad (c)

Ejercicio 4. En computación se usa comúnmente el conectivo if then else. Este se

define para cualesquiera tres proposiciones α, β y γ como sigue: si α es cierto entonces
β y si α es falso entonces γ.
a) Define if then else a partir de nuestros conectivos: {∧, ∨, ¬, →, ↔}

b) Define los conectivos ∧, ∨ y ¬ a partir de if then else.

a) Define if then else a partir de nuestros conectivos: {∧, ∨, ¬, →, ↔}
Sea α, β y γ proposiciones con valor de verdad v : P = (0, 1).
Definiremos if, then, else ≡ P
En programación if, then, else funciona bajo la siguiente estructura:
Si tenemos algo entonces sucede esto, si tenemos lo contrario, entonces sucede esto otro.
Esta estructura se puede traducir al lenguaje lógico como una conjunción de dos implicaciones, es
decir:
P ≡ (α → β) ∧ (¬α → γ) lo cual cumple con la estructura de nuestro if, then, else.
Es decir, si tenemos α con valor de verdad 1 entonces el valor de verdad de β serı́a 1, de lo
contrario, si tenemos ¬α con valor de verdad 1, entonces el valor de verdad de γ es 1. Como
ambas proposiciones son verdad, por la propiedad de la conjunción, tenemos que esta proposición
es verdadera e identica a la estructura de if, then, else.
También, podemos simplificar esta proposición con una equivalencia lógica, es decir P ≡ (α →
β) ∧ (¬α → γ) ≡ (α ∧ β) ∨ (¬α ∧ γ). Esto se puede comprobar comprobando que las tablas de
verdad de ambas son iguales.

α β α→β ¬α γ ¬α → γ (α → β) ∨ (¬α → γ)
1 1 1 0 1 1 1
1 1 1 0 0 1 1
1 0 0 0 1 1 0
1 0 0 0 0 1 0
0 1 1 1 1 1 1
0 1 1 1 0 0 0
0 0 1 1 1 1 1
0 0 1 1 0 0 0

Tabla 4: equivalencia lógica a

3
 α β α∧β ¬α γ ¬α ∧ γ (α ∧ β) ∨ (¬α ∧ γ
1 1 1 0 1 0 1
1 1 1 0 0 0 1
1 0 0 0 1 0 0
1 0 0 0 0 0 0
0 1 0 1 1 1 1
0 1 0 1 0 0 0
0 0 0 1 1 1 1
0 0 0 1 0 0 0

Tabla 5: equivalencia lógica b

b) Define los conectivos ∧, ∨ y ¬ a partir de if then else. Sea α y β proposiciones con valor de
verdad v : P = (0, 1).
Definimos α ∧ β como:
if α then β else ¬β

Es decir, si α tiene valor de verdad 1 entonces β tiene valor de verdad 1, de lo contrario, si ¬α tiene
valor de verdad 1 entonces ¬β tiene valor de verdad 1, por lo que la proposición es verdadera. Tal
y como lo indica las tablas de verdad de la conjunción. (Incluidas al final de este ejercicio).

Definimos α ∨ β, por casos:

Caso 1:
If ¬α then β else ¬β

Caso 2:
If ¬α then β else β

Es decir, si ¬α tiene valor de verdad 1 entonces β tiene el valor de verdad 1, de lo contrario, si α

tiene el valor de 1 entonces β puede tener el valor de 1 o 0, por lo que la proposición es cierta Tal
y como lo indica su tabla de verdad. (Incluidas al final de este ejercicio).

Definimos ¬α como:

If α then 1 else 0

Es decir, si α toma el valor de verdad 1 entonces la proposición tendrá el valor de verdad 1, de lo

contrario, si ¬α toma el valor de verdad 1, el valor de verdad de la proposición será 1, por lo que la
proposición se cumple. Tal y como lo indica su tabla de verdad. (Incluida al final de este ejercicio).

α β α∧β
1 1 1
1 0 0
0 1 0
0 0 0

Tabla 6: Conjunción

4
 ¬α ¬β ¬α ∧ ¬β
0 0 0
0 1 0
1 0 0
1 1 0

Tabla 7: Conjunción

α β α∨β
1 1 1
1 0 1
0 1 1
0 0 0

Tabla 8: Disyunción

¬α ¬β ¬α ∨ ¬β
0 0 0
0 1 1
1 0 1
1 1 1

Tabla 9: Disyunción

α ¬α
0 1
1 0

Tabla 10: Negación

2. Conjuntos
Ejercicio 5. Sea A = {1, 2, {2}}. Cuáles de las siguientes proposiciones son verdaderas
y cuáles falsas
a) 1 ∈ A b) {1} ∈ A c) {1} ⊆ A

d) {{1}} ⊆ A e) {2} ∈ A f) {2} ⊆ A

g) {{2}} ⊆ A

a) 1 ∈ A es verdadera, debido a que 1 está en A.

b) {1} ∈ A es falsa, pues {1} es un subconjunto conocido como unitario el cual no está en A.
c) {1} ⊆ A es verdadera, debido a que todos los elementos del conjunto {1} están en A.
d) {{1}} ⊆ A es falsa, debido a que existe un único elemento del conjunto {{1}}, el cual es el
unitario {1}, tal que no está en A.
e) {2} ∈ A es verdadero, debido a que el elemento {2} está en A.
f) {2} ⊆ A es verdadero, debido a que todos los elementos del conjunto {2} están en A.

5
g) {{2}} ⊆ A es verdadero, debido a que al único elemento del conjunto {{2}} es el unitario {2}
el cual sı́ está en A.
Ejercicio 6. Demuestre la verdad o falsedad (con un contraejemplo) de los siguientes
enunciados:
a) Si A ⊆ B y B * C entonces A * C.

b) Si A ∪ B = A ∪ C entonces B = C.

a) Si A ⊆ B y B 6⊆ C, entonces A 6⊆ C.
Afirmamos que es falsa, por lo que daremos un contraejemplo
Sean A = {1}, B = {1, 2} y C = {1, 4} conjuntos. Nótese que A ⊆ B, por la definición de
contención, ya que todos los elementos de A, en este caso 1, se encuentran en B. También nótese
que B 6⊆ C, debido a que al menos un elemento de B, en este caso 2, no está en C. Pero se cumple
que A ⊆ C porque todos los elementos de A, en este caso 1, están en el conjunto C.

b) Si A ∪ B = A ∪ C entonces B = C.
Afirmamos que esta proposición es falsa, por lo que daremos un contraejemplo.
Sean A = {1, 2, 3}, B = {1, 4} y C = {1, 2, 4} conjuntos.
Entonces A ∪ B = {1, 2, 3, 4} y A ∪ C = {1, 2, 3, 4}. Notemos que A ∪ B = A ∪ C tal que se cumple
que B ⊆ C pero C * B pues existe un elemento, en este caso 2, que está en C pero no en B, por
tanto B 6= C.

Ejercicio 7. Sean A, B y C conjuntos, demuestre que:

a) Si A ⊆ B entonces A ∩ C ⊆ B ∩ C para cualquier conjunto C

b) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

a) Si A ⊆ B entonces A ∩ C ⊆ B ∩ C para cualquier conjunto C.

Dem. Sea C un conjunto arbitrario, pero fijo, no vacı́o tal que ∀x(A ⊆ B) P.D. A ∩ C ⊆ B ∩ C
Sea x ∈ A ∩ C, entonces por definición de la intersección tenemos que x ∈ A ∧ x ∈ C... (1)
Como, por hipótesis, sabemos que A ⊆ B, es decir, x ∈ A → x ∈ B, entonces, por (1), tenemos
que x ∈ B ∧ x ∈ C, por la definición de la intersección, tenemos que x ∈ B ∩ C.
Por lo tanto, si A ⊆ B, entonces A ∩ C ⊆ B ∩ A. 

b) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).

Dem. Sean A, B, C conjuntos no vacı́os. P.D ∀x(A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C))

⊆] Sea x ∈ A ∪ (B ∩ C), ası́ x ∈ A ∨ x ∈ (B ∩ C), entonces tenemos los siguientes casos:
i) Si x ∈ A entonces, por la propiedad de la unión, x ∈ A ∪ B, e igualmente, x ∈ A ∪ C, ası́ por la
propiedad de la intersección tenemos que x ∈ (A ∪ B) ∩ (A ∪ C).
ii) Si x ∈ B ∩ C, entonces x ∈ B ∧ x ∈ C. Por la propiedad de la unión tenemos que x ∈ A ∪ B e
igualmente que x ∈ A ∪ C, y por la propiedad de la intersección tenemos que x ∈ (A ∪ B) ∩ (A ∪ C).
De los dos casos anteriores, se concluye que x ∈ (A ∪ B) ∩ (A ∪ C) y, por lo tanto, A ∪ (B ∩ C) ⊆
(A ∪ B) ∩ (A ∪ C).
⊇] Sea x ∈ (A ∪ B) ∩ (A ∪ C), entonces x ∈ A ∪ B ∧ x ∈ A ∪ C.

6
Como x ∈ A ∪ B entonces x ∈ A ∨ x ∈ B, e igualmente como x ∈ A ∪ C entonces x ∈ A ∨ x ∈ C,
y con esto tenemos los siguientes casos:
i) Si x ∈ A entonces, por la propiedad de la unión, x ∈ A ∪ (B ∩ C).
ii) Si x ∈
/ A entonces x ∈ B y x ∈ C, por la propiedad de la intersección, tenemos que x ∈ B ∩ C
y por la propiedad de la unión, tenemos que x ∈ A ∪ (B ∩ C).
De los casos anteriores concluimos que x ∈ A∪(B ∩C) y por lo tanto (A∪B)∩(A∪C) ⊆ A∪(B ∩C).
∴ A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). 

Ejercicio 8. Definición Sea A un conjunto y a, b ∈ A definimos el par ordenado de a y b como:

(a, b) := {{a}, {a, b}}.
Demuestra que para cualesquiera a, b, c, d ∈ A se cumple que: (a, b) = (c, d) si y sólo si
a=cyb=d

Dem. Sean a, b, c, d ∈ A
P.D. (a, b) = (c, d) ⇔ a = c y b = d
⇒] Supongamos que se cumple que (a, b) = (c, d). Resolveremos por casos.
(Caso 1) Supongamos que a = b
Por definición del par ordenado tenemos que (a, b) = (a, a) = {a, {a, a}} = {a}. Luego por hipótesis
tenemos que (a, b) = (c, d), esto implica que {a} = (a, b) = (c, d) = {c, {c, d}}.
Entonces {a} = {c, {c, d}}, notemos que hay una igualdad de conjuntos y por definción se debe
cumplir que ambos conjuntos tengan los mismos elemento, más aún el conjunto de la izquierda
satisface tener un único elemento, por lo que el conjunto de la derecha también lo debe cumplir.
Entonces {c, {c, d}} = {c, {c, c}} = {c} y esto implica que c = d.
Finalmente tenemos que {a} = {c}, esto implica que a = c ∴ a = b = c = d.
(Caso 2) Supongamos que a 6= b
Por hipótesis sabemos que (a, b) = (c, d) y por definición del par ordenado tenemos entonces que
{a, {a, b}} = {c, {c, d}}, lo cual es una igualdad de conjuntos.
Esto nos arroja los siguientes casos:

{a} = {c} ∨ {a} = {c, d}
{a, b} = {c} ∨ {a, b} = {c, d}
Notemos que el caso {a, b} = {c} no pueden suceder, pues supone que a = b, lo cual contradice
nuestra hipótesis. Ahora, el caso {a, b} = {c, d} como a 6= b implica que c 6= d.
Por tanto el caso {a} = {c, d} no puede suceder, pues aquı́ supone que c = d lo cual contradice lo
demostrado anteriormente.
Entonces {a} = {c} lo cual implica que a = c y como {a, b} = {c, d} pero ya demostramos que
a 6= b, c 6= d y a = c, entonces se cumple que b = d
∴a=cyb=d
⇐] Supongamos que se cumple a = c y b = d
Entonces se cumple que {a, {a, b}} = {c, {c, d}} pero esto es la definción del par ordenado.
∴ (a, b) = (c, d)
∴ (a, b) = (c, d) ⇔ a = c y b = d