Matemática discreta TP1 resuelto (Corregido)

Vista previa del material en texto

61.07 Matemática Discreta
Trabajo Práctico 1
Joaquín Singer (josinger@fi.uba.ar)
Ejercicio 1.
A)
• Negación: El conjunto de veracidad es el complemento del conjunto de veracidad de la proposición
original. (P ′)
• Disyunción: El conjunto de veracidad es la unión de los conjuntos de veracidad de la proposiciones
originales. (P ∪Q)
• Conjunción: El conjunto de veracidad es la intersección de los conjuntos de veracidad de la proposi-
ciones originales. (P ∩Q)
• Condicionales: El conjunto de veracidad de p→ q es la unión del complemento de P con Q, y el de
q → p es la unión de P con el complemento de Q. (P ′ ∪Q y P ∪Q′)
• Equivalencia: El conjunto de veracidad es la intersección entre los conjuntos de veracidad de los dos
condicionales que conforman la equivalencia. ((P ′ ∪Q) ∩ (P ∪Q′))
Negación Disyunción Conjunción p→ q q → p Equivalencia
B) h⇒ t significa que el condicional h→ t es siempre válido, es decir, nunca
es falso. Esto sucede si no hay valores del conjunto de veracidad de h fuera
de t, entonces, H es subconjunto de T (H ⊂ T ), y se prueba demostrando
esto mismo. Por ejemplo, "Todo número primo mayor a 2 es impar", es
cierto para todos los números ya que el conjunto de primos mayores a 2 es
subconjunto de del conjunto de los números impares.
h⇒ t
Ejercicio 2.
Se probará la falsedad de los enunciados demostrando su negación.
A) ∃ conjuntos P,Q tales que P ∪Q = P y Q 6= ∅.
Sea Q ⊂ P . Entonces P ∪Q = P y Q 6= ∅
1
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
B) ∃ conjuntos P,Q tales que P ∩Q = P y Q 6= I.
Sea P ⊂ Q ⊂ I. Entonces P ∩Q = P y Q 6= I
C) ∃ conjuntos P,Q,R tales que P ∪Q = P ∪R y Q 6= R.
Sean dos conjuntos distintos Q y R, Q ⊂ P y R ⊂ P . Entonces P ∪Q = P ∪R y Q 6= R
D) ∃ conjuntos P,Q,R tales que P ∩Q = P ∩R y Q 6= R.
Sean dos conjuntos distintos Q y R, P ⊂ Q y P ⊂ R. Entonces P ∩Q = P ∩R y Q 6= R
P ∪Q = P , Q 6= ∅ P ∩Q = P , Q 6= I P∪Q = P∪R, Q 6= R P∩Q = P∩R, Q 6= R
Ejercicio 3.
A)
NAND - p ↑ q - (pq)′ NOR - p ↓ q - (p+ q)′
B) Para que (p ↑ q) ↑ r = p ↑ (q ↑ r), sus tablas de verdad deben ser iguales, y no lo son. Lo mismo pasa
con (p ↓ q) ↓ r = p ↓ (q ↓ r).
2
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
p q r (p ↑ q) ↑ r p ↑ (q ↑ r) (p ↓ q) ↓ r p ↓ (q ↓ r)
V V V V V F F
V V F V F V F
V F V F F F F
V F F V F V F
F V V F V F V
F V F V V V V
F F V F V F V
F F F V V F F
También se podrían dibujar sus conjuntos de veracidad, que tampoco coincidirán, pero con la tabla de verdad
alcanza para afirmas que no son asociativas.
Ejercicio 4.
Para determinar los conjuntos de veracidad, se puede realizar una tabla
de verdad. Cada fila de entradas en la tabla, se asociará con un único
subconjunto, y cada subconjunto se asociará con una única fila de en-
tradas. Entonces, se puede concluir que la cantidad de conjuntos posi-
bles (es decir, la cantidad de combinaciones de subconjuntos posibles)
es, por combinatoria básica, 2n, siendo n la cantidad de fila de en-
tradas en la tabla. Al ser una tabla donde cada variable tiene solo dos
valores posibles, la cantidad filas de entradas será igual a 2m, siendo m
la cantidad de variables independientes. Como dos proposiciones son
iguales si sus conjuntos de veracidad lo son, entonces la cantidad de
proposiciones posibles será igual a la cantidad de conjuntos posibles,
que tal como ya se calculó, es 2(2
m), en este caso m = 2, por lo que
pueden formarse 16 proposiciones.
n p q p↔ q p′q + p (q → p)′ (p→ q)(q → p) (pq)→ p′ p↔ p′ (p→ q)→ q
1 V V V V F V F F V
2 V F F V F F V F V
3 F V F V V F V F V
4 F F V F F V V F F
Entonces los conjuntos de veracidad son:
A) 1, 4
B) 1, 2, 3
C) 3
D) 1, 4
E) 2, 3, 4
F) ∅
G) 1, 2, 3
3
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
Ejercicio 5.
El razonamiento es igual al del ejercicio anterior, pero esta vez con 3 variables, por lo que la cantidad de
proposiciones es 2(2
3) = 256. Se debe realizar la tabla de verdad y a partir de allí averiguar los conjuntos de
veracidad de las proposiciones dadas por la consigna para este ejercicio.
Ejercicio 6.
Las proposiciones que representan son:
A) (qp) + (pr)
B) p+ (qr)
C) p(q + r)
D) (q + p)(p+ r)
E) p+ (pq)
F) p(p+ q)
G) p′q′
H) p′ + q′
I) (p+ q)′
J) (pq)′
K) p′ + q
L) (q′p)′
Con una tabla de verdad se pueden comparar para saber cuales son equivalentes:
p q r A B C D E F G H I J K L
V V V V V V V V V F F F F V V
V V F V V V V V V F F F F V V
V F V V V V V V V F V F V F F
V F F F V F V V V F V F V F F
F V V F V F V F F F V F V V V
F V F F F F F F F F V F V V V
F F V F F F F F F V V V V V V
F F F F F F F F F V V V V V V
Y a continuación se grafican los conjuntos de veracidad de las clases de equivalencia:
A = C B = D E = F G = I H = J K = L
Ejercicio 7.
Para resolver este ejercicio, se debe realizar la tabla de verdad agregando una columna para la probabilidad,
y luego sumar dicho valor en sus filas verdaderas para cada proposición.
p q p↔ q (q → p)′ (pq)→ p′ p↔ p′ (p→ q)→ q Probabilidad
V V V F F F V 0, 1
V F F F V F V 0, 6
F V F V V F V 0, 2
F F V F V F F 0, 1
0, 2 0, 2 0, 9 0 0, 9 1
4
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
Ejercicio 8.
Dada una función de verdad V (x) con dominio {0, 1}, que recibe una proposición y da como resultado su
valor de verdad, para probar que una proposición x es igual a una proposición y, basta con demostrar que
para un v perteneciente al dominio de la función, V (x) = v ⇔ V (y) = v. Ya que v solo puede tomar dos
valores, esta condición asegura que también se cumple la misma con el otro valor del dominio. Teniendo esto
en cuenta, en cada ítem (menos el D y el E) se reformulan las identidades en la forma V (x) = v ⇔ V (y) = v.
A) ∀p∀q proposiciones, V (p+ q) = 0⇔ V (q + p) = 0.
V (p+ q) = 0⇔ V (p) + V (q) = 0 (Por definición de disyunción)
V (p) + V (q) = 0⇔ V (p) = 0 ∧ V (q) = 0 (La suma binaria es nula sii ambos sumandos lo son)
V (p) = 0 ∧ V (q) = 0⇔ V (q) = 0 ∧ V (p) = 0 (Conmutatividad del operador lógico ∧)
V (q) = 0 ∧ V (p) = 0⇔ V (q) + V (p) = 0 (La suma binaria es nula sii ambos sumandos lo son)
V (q) + V (p) = 0⇔ V (q + p) = 0 (Por definición de disyunción) �
En álgebra de conjuntos:
P +Q = {x ∈ I|(x ∈ P ) ∨ (x ∈ Q)} = {x ∈ I|(x ∈ Q) ∨ (x ∈ P )} = Q+ P
Por principio de dualidad, se puede adaptar inmediatamente esta demostración para V (pq) = V (qp).
B) ∀p∀q∀r proposiciones, V (p(q + r)) = 1⇔ V (pq + pr) = 1.
V (p(q + r)) = 1⇔ V (p)V (q + r) = 1 (Por definición de conjunción)
V (p)V (q + r) = 1⇔ V (p)(V (q) + V (r)) = 1 (Por definición de disyunción)
V (p)(V (q) + V (r)) = 1⇔ V (p) = 1 ∧ (V (q) = 1 ∨ V (r) = 1)
(La multiplicación binaria es 1 sii ambos factores lo son, y la suma si alguno lo es)
V (p) = 1 ∧ (V (q) = 1 ∨ V (r) = 1)⇔ (V (p) = 1 ∧ V (q) = 1) ∨ (V (p) = 1 ∧ V (r) = 1)
(Distributividad del operador lógico ∧)
(V (p) = 1 ∧ V (q) = 1) ∨ (V (p) = 1 ∧ V (r) = 1)⇔ (V (p)V (q)) + (V (p)V (r)) = 1
(La multiplicación binaria es 1 sii ambos factores lo son, y la suma si alguno lo es)
((V (p)V (q)) + (V (p)V (r)) = 1⇔ V (pq) + V (pr) (Por definición de conjunción)
((V (p)V (q)) + (V (p)V (r)) = 1⇔ V (pq + pr) (Por definición de disyunción) �
En álgebra de conjuntos:
P (Q+R) = {x ∈ I|(x ∈ P ) ∧ ((x ∈ Q) ∨ (x ∈ R))} =
= {x ∈ I|((x ∈ P ) ∧ (x ∈ Q)) ∨ ((x ∈ P ) ∧ (x ∈ R))} = PQ+ PR
Por principio de dualidad, se puede adaptar inmediatamente esta demostración para V (p + qr) =
V ((p+ q)(p+ r)).
5
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
C) ∀p proposición, V (p+ F ) = 1⇔ V (p) = 1.
V (p+ F ) = 1⇔ V (p) + V (F ) = 1 (Por definición de disyunción)
V (p) + V (F ) = 1⇔ V (p) + 0 = 1 (V (F ) = 0)
V (p) + 0 = 1⇔ V (p) = 1 (La suma binaria es 1 si alguno de los sumandos lo es) �
En álgebra de conjuntos:
P + ∅ = {x ∈ I|(x ∈ P ) ∨ (x ∈ ∅)} = {x ∈ I|(x ∈ P )} = P
Por principio de dualidad, se puede adaptar inmediatamente esta demostración para V (pT ) = V (p).D) Asumiendo que V (p+ p′) = F = 0, se busca llegar a un absurdo.
V (p+ p′) = 0⇔ V (p) + V (p′) = 0 (Por definición de disyunción)
V (p) + V (p′) = 0⇔ V (p) = 0 ∧ V (p′) = 0 (La suma binaria es nula sii ambos sumandos lo son)
V (p) = 0 ∧ V (p′) = 0⇔ V (p) = V (p′) (Ambos valores son iguales)
Por definición de negación, V (p) = V (p′) es un absurdo, lo que demuestra que el supuesto inicial es
falso, y que, por solo haber otra opción posible:
V (p+ p′) = T = 1 �
En álgebra de conjuntos:
P + P ′ = {x ∈ I|(x ∈ P ) ∨ (x /∈ P )} = {x ∈ I|(x ∈ I)} = I
Por principio de dualidad, se puede adaptar inmediatamente esta demostración para V (pp′) = F = 0.
E) Asumiendo que V (p+ T ) = F = 0, se busca llegar a un absurdo.
V (p+ T ) = 0⇔ V (p) + V (T ) = 0 (Por definición de disyunción)
V (p+ T ) = 0⇔ V (p) + 1 = 0 (V (T ) = 1)
Ya que la suma binaria es nula sii ambos sumandos lo son, V (p)+1 = 0 es un absurdo, lo que demuestra
que el supuesto inicial es falso, y que, por solo haber otra opción posible:
V (p+ T ) = T = 1 �
En álgebra de conjuntos:
P + I = {x ∈ I|(x ∈ P ) ∨ (x ∈ I)} = {x ∈ I|(x ∈ I)} = I
Por principio de dualidad, se puede adaptar inmediatamente esta demostración para V (pF ) = F = 0.
F) ∀p∀q∀r proposiciones, V ((p+ q) + r) = 0⇔ V (p+ (q + r)) = 0.
V ((p+ q) + r) = 0⇔ V (p+ q) + V (r) = 0 (Por definición de disyunción)
V (p+ q) + V (r) = 0⇔ V (p) + V (q) + V (r) = 0 (Por definición de disyunción)
V (p) + V (q) + V (r) = 0⇔ V (p) + V (q + r) = 0 (Por definición de disyunción)
V (p) + V (q + r) = 0⇔ V (p+ (q + r)) = 0 (Por definición de disyunción) �
En álgebra de conjuntos:
(P +Q) +R = {x ∈ I|(x ∈ P ) ∨ (x ∈ Q) ∨ (x ∈ R)} = P + (Q+R)
Por principio de dualidad, se puede adaptar inmediatamente esta demostración para V ((pq)r) =
V (p(qr)).
6
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
G) ∀p proposición, V ((p′)′) = 1⇔ V (p) = 1.
V ((p′)′) = 1⇔ V (p′) = 0 (Por definición de negación)
V (p′) = 0⇔ V (p) = 1 (Por definición de negación) �
En álgebra de conjuntos:
(P ′)′ = {x ∈ I|(x /∈ P ′)} = {x ∈ I|(x ∈ P )} = P
H) ∀p∀q proposiciones, V ((p+ q)′) = 1⇔ V (p′q′) = 1.
V ((p+ q)′) = 1⇔ V (p+ q) = 0 (Por definición de negación)
V (p+ q) = 0⇔ V (p) + V (q) = 0 (Por definición de disyunción)
V (p) + V (q) = 0⇔ V (p) = 0 ∧ V (q) = 0
(La suma binaria es nula sii ambos sumandos lo son)
V (p) + V (q) = 0⇔ V (p′) = 1 ∧ V (q′) = 1 (Por definición de negación)
V (p′) = 1 ∧ V (q′) = 1⇔ V (p′)V (q′) = 1
(La multiplicación binaria es 1 sii ambos factores lo son)
V (p′)V (q′) = 1⇔ V (p′q′) = 1 (Por definición de conjunción) �
En álgebra de conjuntos:
(P +Q)′ = {x ∈ I|(x /∈ (P ∪Q))} = {x ∈ I|(x /∈ P ) ∧ (x /∈ Q))} = P ′Q′
Por principio de dualidad, se puede adaptar inmediatamente esta demostración para V ((pq)′) = V (p′+
q′).
I) ∀p proposición, V ((p+ p) = 0⇔ V (p) = 0.
V (p+ p) = 0⇔ V (p) + V (p) = 0 (Por definición de disyunción)
V (p) + V (p) = 0⇔ V (p) = 0 ∧ V (p) = 0
(La suma binaria es nula sii ambos sumandos lo son)
V (p) = 0 ∧ V (p) = 0⇔ V (p) = 0 (V (p) = V (p)) �
En álgebra de conjuntos:
P + P = {x ∈ I|(x ∈ P ) ∨ (x ∈ P )} = {x ∈ I|(x ∈ P )} = P
Por principio de dualidad, se puede adaptar inmediatamente esta demostración para V (pp) = V (p).
J) ∀p∀q proposiciones, V (p+ pq) = 0⇔ V (p) = 0.
V (p+ pq) = 0⇔ V (p) + V (pq) = 0 (Por definición de disyunción)
V (p) + V (pq) = 0⇔ V (p) + (V (p)V (q)) = 0 (Por definición de conjunción)
V (p) + (V (p)V (q)) = 0⇔ V (p) = 0 ∧ (V (p) = 0 ∨ V (q) = 0)
(La suma binaria es nula sii ambos sumandos lo son, y la multiplicación sii alguno lo es)
V (p) = 0 ∧ (V (p) = 0 ∨ V (q) = 0)⇔ V (p) = 0
(Si V (p) 6= 0, nunca se cumplirá la primera condición, y si V (p) = 0, se cumplen ambas) �
En álgebra de conjuntos:
P + PQ = {x ∈ I|(x ∈ P ) ∨ (x ∈ P ∩Q)} = {x ∈ I|(x ∈ P )} = P
Por principio de dualidad, se puede adaptar inmediatamente esta demostración para V (p(p+q)) = V (p).
7
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
Ejercicio 9.
La respuesta a la primera pregunta fue dada en el cuarto ejercicio. Las funciones reescritas son:
• f1(p, q) = pp′
• f2(p, q) = p
• f3(p, q) = q
• f4(p, q) = pq
• f5(p, q) = p+ q
• f6(p, q) = pq′ + p′q
• f7(p, q) = p′ + q
• f8(p, q) = p+ q′
• f9(p, q) = p+ p′
• f10(p, q) = p′
• f11(p, q) = q′
• f12(p, q) = (pq)′
• f13(p, q) = (p+ q)′
• f14(p, q) = pq+ p′q′
• f15(p, q) = pq′
• f16(p, q) = p′q
Ejercicio 10.
De la certeza sobre que (+, ·,′ ) es completo, se desprende que para demostrar que los siguientes juegos lo
son, alcanza con probar que se pueden construir funciones con los elementos de dichos juegos que reemplacen
las faltantes del juego completo conocido:
• En el caso de (+,′ ), es necesaria una función que suplante a "·". Para conseguirla hay que intentar
"transformar" el "·" en pq en una expresión con las otras operaciones que son parte del juego. Una
buena forma de hacerlo es con De Morgan e involución. Sabiendo que pq = ((pq)′)′ se puede aplicar
De Morgan a la primera negación y obtener pq = (p′+ q′)′. Con esto ya se consigue una expresión que
reemplace a "·". Definiendo f(p, q) = (p′ + q′)′ = pq se demuestra que el juego (+,′ ) es completo.
• Para (·,′ ), se necesita un nuevo "+", el cual siguiendo el mismo principio que en el juego anterior (esto
es útil por el principio de dualidad), puede escribirse como (p′q′)′. Definiendo f(p, q) = (p′q′)′ = p+ q
se demuestra que el juego (·,′ ) es completo.
• Con (→,′ ) hay que conseguir una función para "+" o para "·", ya que (·,′ ) y (+,′ ) son juegos completos
por si solos. El "+" puede ser reemplazado con p′ → q. Definiendo f(p, q) = p′ → q = p+q se demuestra
que el juego (→,′ ) es completo.
• Para (↑):
– f(p, q) = p↑p = p′
– f(p, q) = (p↑p)↑(q↑q) = p+ q
– f(p, q) = (p↑q)↑(p↑q) = pq
• Para (↓):
– f(p, q) = p↓p = p′
– f(p, q) = (p↓q)↓(p↓q) = p+ q
– f(p, q) = (p↓p)↓(q↓q) = pq
Los circuitos utilizando cada juego para p→ q son:
(+,′ ) (·,′ ) (↑) (↓)
8
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
Ejercicio 11.
• ∀p∀q proposiciones, (p↑q)′ = p′↓q′.
(p↑q)′ = ((pq)′)′ (Por definición de ↑)
((pq)′)′ = (p′ + q′)′ (Por De Morgan)
((p′ + q′)′ = p′↓q′ (Por definición de ↓) �
• ∀p∀q proposiciones, (p↓q)′ = p′↑q′.
(p↓q)′ = ((p+ q)′)′ (Por definición de ↓)
((p+ q)′)′ = (p′q′)′ (Por De Morgan)
((p′q′)′ = p′↑q′ (Por definición de ↑) �
Los circuitos lógicos que dan cuenta las equivalencias demostradas son:
(p↑q)′ p′↓q′
(p↓q)′ p′↑q′
9
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
Ejercicio 12.
A) p↔ qr =
(Por definición de equivalencia) = (p→ qr)(qr → p) =
(Por definición de condicional) = (p′ + (qr))((qr)′ + p) =
(Por De Morgan) = (p′ + (qr))((q′ + r′) + p) =
(Por conmutativa y asociativa) = (p′ + (qr))(p+ q′ + r′) =
(Por distributiva y conmutativa) = p′p+ p′q′ + p′r′ + pqr + qq′r + qrr′ =
(Por complemento) = F + p′q′ + p′r′ + pqr + F + F =
(Por neutros) = p′q′T + p′Tr′ + pqr =
(Por complemento) = p′q′(r + r′) + p′(q + q′)r′ + pqr =
(Por distributiva) = p′q′r + p′q′r′ + p′qr′ + p′q′r′ + pqr =
(Por idempotencia) = p′q′r + p′q′r′ + p′qr′ + pqr F.N.D.
B) (p+ q′)→ pr =
(Por definición de condicional) = (p+ q′)′ + pr =
(Por De Morgan) = p′(q′)′ + pr =
(Por involución) = p′q + pr =
(Por neutros) = p′qT + pTr =
(Por complemento) = p′q(r + r′) + p(q + q′)r =
(Por distributiva) = p′qr + p′qr′ + pqr + pq′r F.N.D.
10
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
C) ((p+ q)′(p+ q′))→ ((p+ q)(p+ r)) =
(Por definición de condicional) = ((p+ q)′(p+ q′))′ + ((p+ q)(p+ r)) =
(Por De Morgan) = ((p+ q)′)′ + (p+ q′)′ + ((p+ q)(p+ r)) =
(Por De Morgan e involución) = (p+ q) + (p′q) + ((p+ q)(p+ r)) =
(Por asociativa y distributiva) = p+ q + p′q + pp+ pr + pq + qr =
(Por absorción) = p+ q =
(Por neutros) = pTT + TqT =
(Por complemento) = p(q + q′)(r + r′) + (p+ p′)q(r + r′) =
(Por distributiva) = pqr + pqr′ + pq′r + pq′r′ + pqr + pqr′ + p′qr + p′qr′=
(Por idempotencia) = pqr + pqr′ + pq′r + pq′r′ + p′qr + p′qr′ F.N.D.
D) ((pq + pqr)→ rq)′ =
(Por absorción) = (pq → rq)′ =
(Por definición de condicional) = ((pq)′ + rq)′ =
(Por De Morgan) = ((pq)′)′(rq)′ =
(Por De Morgan e involución) = pq(r′ + q′) =
(Por distributiva) = pqr′ + pqq′ =
(Por complemento) = pqr′ + F =
(Por neutros) = pqr′ F.N.D.
11
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
E) pq′r′ =
(Ya se encuentra en su forma normal disyuntiva) = pq′r′ F.N.D.
Los pares inconsistentes son los de aquellas proposiciones que no pueden ser ciertas a la vez nunca, se pueden
encontrar fácilmente comparando los conjuntos de veracidad. Los pares son: A con D, A con E, B con D, B
con E, D con E.
Ejercicio 13.
A) (X + Y + Z)− Z(X + Y ) =
(Por distributiva) = (X + Y + Z)− (XZ + Y Z) =
(Por definición de diferencia) = (X + Y + Z)(XZ + Y Z)′ =
(Por De Morgan) = (X + Y + Z)(XZ)′(Y Z)′ =
(Por De Morgan) = (X + Y + Z)(X ′ + Z ′)(Y ′ + Z ′) =
(Por distributiva, complemento y neutros) = (X ′Y +X ′Z +XZ ′ + Y Z ′)(Y ′ + Z ′) =
(Por distributiva, complemento y neutros) = XY ′Z +XY ′Z ′ +X ′Y Z ′ +XZ ′Z ′ + Y Z ′Z ′ =
(Por idempotencia) = XY ′Z +XY ′Z ′ +X ′Y Z ′ +XZ ′ + Y Z ′ =
(Por absorción) = XY ′Z +XZ ′ + Y Z ′ =
(Por neutros) = XY ′Z +XIZ ′ + IY Z ′ =
(Por complemento) = XY ′Z +X(Y + Y ′)Z ′ + (X +X ′)Y Z ′ =
(Por distributiva) = XY ′Z +XY Z ′ +XY ′Z ′ +XY Z ′ +X ′Y Z ′ =
(Por idempotencia) = XY ′Z +XY Z ′ +XY ′Z ′ +X ′Y Z ′ F.N.D.
F.N.C: (X + Y + Z)(X ′ + Y + Z ′)(X + Y ′ + Z ′)(X ′ + Y ′ + Z ′)
12
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
B) (X ⊕ Y )(X ⊕ Z) =
(Por definición de ⊕) = (XY ′ +X ′Y )(Y Z ′ + Y ′Z) =
(Por distributiva) = XY Y ′Z +XY ′Y ′Z +X ′Y Y Z ′ +X ′Y Y ′Z =
(Por idempotencia y complemento) = X∅Z +XY ′Z +XY Z +X∅Z =
(Por neutros) = XY ′Z +X ′Y Z ′ F.N.D.
F.N.C: (X + Y + Z)(X + Y + Z ′)(X ′ + Y + Z)(X ′ + Y ′ + Z)(X + Y ′ + Z ′)(X ′ + Y ′ + Z ′)
C) X − Y Z ′ =
(Por definición de diferencia) = X(Y Z ′)′ =
(Por De Morgan) = X(Y ′ + (Z ′)′) =
(Por involución) = X(Y ′ + Z) =
(Por distributiva) = XY ′ +XZ =
(Por neutros) = XY ′I +XIZ =
(Por complemento) = XY ′(Z + Z ′) +X(Y + Y ′)Z =
(Por distributiva) = XY ′Z +XY ′Z ′ +XY Z +XY ′Z =
(Por idempotencia) = XY ′Z +XY ′Z ′ +XY Z F.N.D.
F.N.C: (X + Y + Z)(X + Y + Z ′)(X + Y ′ + Z)(X ′ + Y ′ + Z)(X + Y ′ + Z ′)
D) (X − Y )(X ⊕ Z) =
(Por definición de diferencia) = XY ′(X ⊕ Z) =
(Por definición de ⊕) = XY ′(XZ ′ +X ′Z) =
(Por distributiva) = XXY ′Z ′ +XX ′Y ′Z =
(Por idempotencia) = XY ′Z ′ +XX ′Y ′Z =
(Por complemento) = XY ′Z ′ + ∅Y ′Z =
(Por neutros) = XY ′Z ′ F.N.D.
13
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
F.N.C: (X+Y +Z)(X+Y +Z ′)(X+Y ′+Z)(X ′+Y ′+Z)(X+Y ′+Z ′)(X ′+Y +Z ′)(X ′+Y ′+Z ′)
E) X + (Y Z −X) =
(Por definición de diferencia) = X +X ′Y Z =
(Neutros) = XII +X ′Y Z =
(Complemento) = X(Y + Y ′)(Z + Z ′) +X ′Y Z =
(Distributiva) = XY Z +XY Z ′ +XY ′Z +XY ′Z ′ +X ′Y Z F.N.D.
F.N.C: (X + Y + Z)(X + Y + Z ′)(X + Y ′ + Z)
F) (X + Y )(X − Y ) =
(Por definición de diferencia) = (X + Y )XY ′ =
(Por distributiva) = XXY ′ +XY Y ′ =
(Por complemento e idempotencia) = XY ′ +X∅ =
(Por neutros) = XY ′I =
(Por complemento) = XY ′(Z + Z ′) =
(Por distributiva) = XY ′Z +XY ′Z ′ F.N.D.
F.N.C: (X + Y + Z)(X + Y + Z ′)(X + Y ′ + Z)(X + Y ′ + Z ′)(X ′ + Y ′ + Z)(X ′ + Y ′ + Z ′)
14
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
G) XZ +XY ′Z =
(Por absorción y neutros) = XIZ =
(Por complemento) = X(Y + Y ′)Z =
(Por distributiva) = XY Z +XY ′Z F.N.D.
F.N.C: (X + Y + Z)(X + Y + Z ′)(X + Y ′ + Z)(X ′ + Y + Z)(X + Y ′ + Z ′)(X ′ + Y ′ + Z)
H) (X − Z) +XY Z ′ =
(Por definición de diferencia) = XZ ′ +XY Z ′ =
(Por absorción y neutros) = XIZ ′ =
(Por complemento) = X(Y + Y ′)Z ′ =
(Por distributiva) = XY Z ′ +XY ′Z ′ F.N.D.
F.N.C: (X + Y + Z)(X + Y + Z ′)(X + Y ′ + Z)(X ′ + Y + Z ′)(X + Y ′ + Z ′)(X ′ + Y ′ + Z ′)
Ejercicio 14.
Hipótesis: ∀P ⊂ I, ∀Q ⊂ I, si P +Q = ∅, entonces P = ∅ ∧Q = ∅.
P = P + ∅ (Por neutros)
P = P + (P +Q) (Por hipótesis)
P = (P + P ) +Q (Por asociativa)
P = P +Q (Por idempotencia)
P = ∅ (Por hipótesis)
Q = Q+ ∅ (Por neutros)
Q = Q+ (P +Q) (Por hipótesis)
Q = P + (Q+Q) (Por asociativa)
Q = P +Q (Por idempotencia)
Q = ∅ (Por hipótesis) �
Por principio de dualidad, se puede adaptar inmediatamente esta demostración para ∀P ⊂ I, ∀Q ⊂ I, si
PQ = I, entonces P = I ∧Q = I. La demostración en álgebra de proposiciones es idéntica a la brindada.
15
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
Ejercicio 15.
Si XY = X, entonces X ⊂ Y , ya que si la intersección de X e Y es igual a X, cada elemento de X debe
pertenecer también a Y , de lo contrario existiría un elemento en X que no forme parte de la intersección y
esta ya no sería igual a X. (b ⇒ a)
Si X ⊂ Y , entonces X + Y = Y , ya que si X es subconjunto de Y , no hay elementos de X que estén fuera
de Y , y la unión de ambos conjuntos debe resultar Y , de lo contrario significaría que hay elementos de X
fuera de Y y esto se contradice directamente con la definición de subconjunto. (a ⇒ c)
SiX+Y = Y , entoncesXY ′ = ∅, ya que si la unión deX e Y es igual a Y , no hay elementos del complemento
de Y que que estén en X, de lo contrario la unión entre ambos no sería Y , sino Y y los elementos de X que
no pertenecieran a él. (c ⇒ d)
Si XY ′ = ∅, entonces X ′ + Y = I, ya que si XY ′ = ∅, entonces (XY ′)′ = I (por definición de negación y
por neutros), y por De Morgan (XY ′)′ = X ′ + Y . (d ⇒ e)
Si X ′ + Y = I, entonces Y ′ ⊂ X ′, ya que si la unión entre X ′ e Y es el conjunto universo, cada elemento de
I que no esté en Y debe estar en X ′, es decir cada elemento de Y ′ debe pertenecer a X ′. (e ⇒ f)
Si Y ′ ⊂ X ′, entonces XY = X, ya que si Y ′ es un subconjunto de X ′, no hay elementos de Y ′ fuera de X ′,
por lo que la unión entre ambos es X ′, es decir X ′+Y ′ = X ′, entonces (X ′+Y ′)′ = (X ′)′ y por De Morgan
e involución XY = X. (f ⇒ b)
Entonces, la equivalencia fue demostrada de forma circular, ya que: b ⇒ a ⇒ c ⇒ d ⇒ e ⇒ f ⇒ b.
En álgebra de proposiciones:
A) p⇒ q
B) pq = p
C) p+ q = q
D) pq′ = F
E) p′ + q = T
F) q′ ⇒ p′
Ejercicio 16.
Primero, si X = Y , necesariamente X ′ = Y ′, ya que X ′ = X ′ y al ser Y = X, se puede reemplazar X ′ por
Y ′ (porque (Y )′ = Y ′), y si X ′ = Y ′, también necesariamente X = Y , ya que X = X, y al ser Y ′ = X ′, se
puede reemplazar X por Y (porque por involución (Y ′)′ = Y ).
Luego, por complemento, X ′X = ∅, y si X = Y , X ′Y = ∅∧XY ′ = ∅. Como ∅+∅ = ∅, X ′Y +XY ′ = ∅.
Para que X ′Y +XY ′ = ∅, es necesario que sea cierto X = Y porque, por lo demostrado en el punto anterior,
si XY ′ = ∅, X ⊂ Y , y si X ′Y = ∅, Y ⊂ X, entonces X ⊂ Y ⊂ X, lo que es igual a X = Y .
La equivalencia entre X ′Y +XY ′ = ∅ y (X ′+Y )(X+Y ′) = I se obtiene aplicando el principio de dualidad,
o utilizando X = Y ⇔ X ′ = Y ′, complemento y De Morgan.
Ejercicio 17.
AX +BX ′ = ∅⇔ AX = ∅ ∧BX ′ = ∅ (Demostrado en el ejercicio 14)
AX = X(A′)′ = ∅⇔ X ⊂ A′ (Demostrado en el ejercicio 15)
BX ′ = ∅⇔ B ⊂ X (Demostrado en el ejercicio 15)
B ⊂ X ∧X ⊂ A′ ⇔ B ⊂ X ⊂ A′
B ⊂ X ⊂ A′ ⇔ B ⊂ A′
16
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
La solución es única cuando A′ = B, ya que la solución maximal sería igual a la minimal.
(A′ +A)X +X ′ = ∅⇔ IX +X ′ = ∅ (Por complemento)
IX +X ′ = ∅⇔ X +X ′ = ∅ (Por neutros)
X +X ′ = ∅⇔ I = ∅ (Por complemento)
Entonces, no hay soluciones para esta segunda ecuación.
Ejercicio 18.
AX = B ⇔
⇔ (AX)′B + (AX)B′ = ∅ (Demostrado en el ejercicio 16)⇔
⇔ (A′ +X ′)B + (AX)B′ = ∅ (Por De Morgan)⇔
⇔ BA′ +BX ′ +XAB′ = ∅ (Por distributiva, asociativa y conmutativa)⇔
⇔ BA′ = ∅ ∧BX ′ = ∅ ∧XAB′ = ∅ (Demostrado en el ejercicio 14)⇔
⇔ BA′ = ∅ ∧BX ′ = ∅ ∧X((AB′)′)′ = ∅ (Por involución)⇔
⇔ BA′ = ∅ ∧BX ′ = ∅ ∧X(A′ +B)′ = ∅ (Por De Morgan e involución)⇔
⇔ B ⊂ A ∧B ⊂ X ∧X ⊂A′ +B = ∅ (Demostrado en el ejercicio 15)⇔
⇔ B ⊂ A ∧B ⊂ X ⊂ (A′ +B) = ∅
A+X = B ⇔
⇔ (A+X)′B + (A+X)B′ = ∅ (Demostrado en el ejercicio 16)⇔
⇔ (A′X ′)B + (A+X)B′ = ∅ (Por De Morgan)⇔
⇔ A′BX ′ +AB′ +XB′ = ∅ (Por distributiva, asociativa y conmutativa)⇔
⇔ A′BX ′ = ∅ ∧AB′ = ∅ ∧XB′ = ∅ (Demostrado en el ejercicio 14)⇔
⇔ A′B ⊂ X ∧A ⊂ B ∧X ⊂ B (Demostrado en el ejercicio 15)⇔
⇔ A ⊂ B ∧A′B ⊂ X ⊂ B
En cada uno de los casos dados, para AX = B
A) • {a1, a2} • {a1, a2, a4} • {a1, a2, a5} • {a1, a2, a4, a5}
B) No se cumplen las condiciones suficientes y necesarias.
C) • {a1, a2, a3} • {a1, a2, a3, a4} • {a1, a2, a3, a5} • {a1, a2, a3, a4, a5}
En álgebra de proposiciones, la condición mínima y necesaria es q ⇒ p y la solución es q ⇒ x⇒ p′ + q.
17
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
Ejercicio 19.
A)
A+BX = ∅
A = ∅ ∧BX = ∅ (Demostrado en el ejercicio 14)
A = ∅ ∧ (B′)′X = ∅ (Por involución)
A = ∅ ∧X ⊂ B′ = ∅ (Demostrado en el ejercicio 15)
• A = ∅
• B = {1}
• I = {1, 2}
• Hay 2 soluciones.
B)
AX +BX = A′B′X
(AX +BX)′(A′B′X) + (AX +BX)(A′B′X)′ = ∅ (Demostrado en el ejercicio 16)
(AX)′(BX)′(A′B′X) + (AX +BX)((A′B′)′ +X ′) = ∅ (Por De Morgan)
(A′ +X ′)(B′ +X ′)(A′B′X) + (AX +BX)(A+B +X ′) = ∅ (Por De Morgan e involución)
A′B′X +ABX +AX +BX = ∅ (Por distributiva y varias)
X(A′B′ +AB +A+B) = ∅ (Por distributiva)
XI = ∅ (Por complemento)
X = ∅ (Por neutros)
• A = {1, 2, 3}
• B = {1, 2, 4}
• I = {1, 2, 3, 4}
• Hay una única solución.
18
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
C)
AX +BX ′ = CX +DX ′
(AX +BX ′)′(CX +DX ′) + (AX +BX ′)(CX +DX ′)′ = ∅ (Demostrado en el ejercicio 16)
(AX)′(BX ′)′(CX +DX ′) + (AX +BX ′)(CX)′(DX ′)′ = ∅ (Por De Morgan)
(A′ +X ′)(B′ +X)(CX +DX ′) + (AX +BX ′)(C ′ +X ′)(D′ +X) = ∅ (Por De Morgan e involución)
(A′ +X ′)(B′ +X)(CX +DX ′) + (AX +BX ′)(C ′ +X ′)(D′ +X) = ∅ (Por De Morgan e involución)
A′B′CX +A′B′DX ′ +A′XCX +A′XDX ′ +X ′B′CX +X ′B′DX ′ +X ′XCX +X ′XDX ′+
+AXC ′D′ +AXC ′X +AXX ′D′ +AXX ′X +BX ′C ′D′ +BX ′C ′X +BX ′X ′D′ +BX ′X ′X = ∅
(Por distributiva)
A′CX +B′DX ′ +AC ′X +BD′X ′ = ∅ (Por complemento, neutros y absorción)
X((A′C +AC ′)′)′ + (B′D +BD′)X ′ = ∅ (Por distributiva e involución)
X(AC +A′C ′)′ + (B′D +BD′)X ′ = ∅ (Por De Morgan)
X(AC +A′C ′)′ = ∅ ∧ (B′D +BD′)X ′ = ∅ (Demostrado en el ejercicio 14)
X ⊂ (AC +A′C ′) ∧ (B′D +BD′) ⊂ X (Demostrado en el ejercicio 15)
(B′D +BD′) ⊂ (AC +A′C ′) ∧ (B′D +BD′) ⊂ X ⊂ (AC +A′C ′)
• A = {1, 2}
• B = {4, 5}
• C = {2, 3}
• D = {5, 6}
• I = {1, 2, 3, 4, 5, 6}
• Hay 4 soluciones.
19
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
D)
AX ′ ⊂ B
AB′X ′ = ∅ (Demostrado en el ejercicio 15)
B′X + C = I
(B′X + C)′ = (I)′ (Demostrado en el ejercicio 16)
(B′X)′C ′ = ∅ (Por De Morgan y complemento)
(B +X ′)C ′ = ∅ (Por De Morgan e involución)
BC ′ + C ′X ′ = ∅ (Por distributiva)
BC ′ + C ′X ′ +AB′X ′ = ∅
BC ′ + (C ′ +AB′)X ′ = ∅
BC ′ = ∅ ∧ (C ′ +AB′)X ′ = ∅ (Demostrado en el ejercicio 14)
B ⊂ C ∧ (C ′ +AB′) ⊂ X (Demostrado en el ejercicio 15)
Ejercicio 20.
A)
AX = BX
(AX)′(BX) + (AX)(BX)′ = ∅ (Demostrado en el ejercicio 16)
(A′ +X ′)(BX) + (AX)(B′ +X ′) = ∅ (Por De Morgan)
A′BX +BXX ′ +AB′X +AXX ′ = ∅ (Por distributiva)
A′BX +AB′X = ∅ (Por complemento y neutros)
X((A′B +AB′)′)′ = ∅ (Por distributiva e involución)
X((A+B′)(A′ +B))′ = ∅ (Por De Morgan e involución)
X(AB +A′B′)′ = ∅ (Por distributiva, complemento y neutros)
X ⊂ (AB +A′B′) (Demostrado en el ejercicio 15)
• A = {1, 3} • B = {2, 3} • I = {1, 2, 3} • Hay 2 soluciones.
B)
A+X = B +X
(A+X)′(B +X) + (A+X)(B +X)′ = ∅ (Demostrado en el ejercicio 16)
(A′X ′)(B +X) + (A+X)(B′X ′) = ∅ (Por De Morgan)
A′BX ′ +A′XX ′ +AB′X ′ +B′XX ′ = ∅ (Por distributiva)
A′BX ′ +AB′X ′ = ∅ (Por complemento y neutros)
(A′B +AB′)X ′ = ∅ (Por distributiva)
(A′B +AB′) ⊂ X (Demostrado en el ejercicio 15)
• A = {1, 3} • B = {2, 3} • I = {1, 2, 3} • Hay 2 soluciones.
20
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
Ejercicio 21.
A) Verdadera.
B) Falsa.
C) Verdadera.
D) Verdadera.
E) Falsa.
F) Falsa.
G) Verdadera.
H) Verdadera.
I) Falsa.
J) Verdadera.
Ejercicio 22.
A) (F)
• C: Para todos los números reales x e y, si x2 6= y2 entonces x 6= y. (V)
• R: Para todos los números reales x e y, si x = y entonces x2 = y2. (V)
• CR: Para todos los números reales x e y, si x 6= y entonces x2 6= y2. (F)
• N: Existe un par de números reales x e y tales que, si x2 = y2 entonces x 6= y. (V)
B) (V)
• C: Para todos los números naturales x e y, si x2 6= y2 entonces x 6= y. (V)
• R: Para todos los números naturales x e y, si x = y entonces x2 = y2. (V)
• CR: Para todos los números naturales x e y, si x 6= y entonces x2 6= y2. (V)
• N: Existe un par de números naturales x e y tales que, si x2 = y2 entonces x 6= y. (F)
C) (V)
• C: Si el cuadrado de un número natural n cualquiera es impar, el número n es impar. (V)
• R: Si un número natural n cualquiera es par, el cuadrado de n es par. (V)
• CR: Si un número natural n cualquiera es impar, el cuadrado de n es impar. (V)
• N: Existe un número natural n cuyo cuadrado es impar y n es par. (F)
D) (V)
• C: Una condición suficiente para que
∫ 1
0
f(t) dt 6= 0 es que la función escalar f no sea nula. (F)
• R: Una condición suficiente para que una función escalar f sea nula, es que
∫ 1
0
f(t) dt = 0. (F)
• CR: Una condición suficiente para que una función escalar f no sea nula, es que
∫ 1
0
f(t) dt 6= 0.
(V)
• N: Existe una función f tal que,
∫ 1
0
f(t) dt = 0. (F)
E) (V)
• C: Siendo p, q dos proposiciones, una condición necesaria para que p↓q sea verdadera es que p′↑q′
sea falsa. (V)
• R: Siendo p, q dos proposiciones, una condición necesaria para que p′↑q′ sea verdadera es que p↓q
sea falsa. (V)
• CR: Siendo p, q dos proposiciones, una condición necesaria para que p′↑q′ sea falsa es que p↓q sea
verdadera. (V)
• N: Existe un par de proposiciones p, q tales que, una p↓q es falsa y que p′↑q′ sea falsa. (F)
21
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
F) (V)
• C: Una condición necesaria para la divergencia de la serie numérica
∑∞
n=1 an es que
limn→∞ an 6= 0. (F)
• R: Una condición suficiente para la convergencia de la serie numérica
∑∞
n=1 an es que
limn→∞ an = 0. (F)
• CR: Una condición suficiente para la divergencia de la serie numérica
∑∞
n=1 an es que
limn→∞ an 6= 0. (V)
• N: Existe una serie numérica convergente
∑∞
n=1 an, con que limn→∞ an 6= 0. (F)
G) (V)
• C: Una condición suficiente para que una matriz cuadrada A no sea regular es que 0 pertenezca
a su espectro. (V)
• R: Una condición necesaria para que una matriz cuadrada A sea regular es que 0 no pertenezca
a su espectro. (V)
• CR: Una condición necesaria para que una matriz cuadrada A no sea regular es que 0 pertenezca
a su espectro. (V)
• N: Existe una matriz cuadrada A, con 0 perteneciente a su espectro, que no es regular. (F)
H) (V)
• C: Si una función escalar no es derivable en un punto entonces no es continua en ese punto. (F)
• R: Si una función escalar es continua en un punto entonces es derivable en ese punto. (F)
• CR: Si una función escalar no es continua en un punto entonces no es derivable en ese punto.
(V)
• N: Existe una función escalar que es derivable en un punto y no es continua en ese punto. (F)
I) (F)
• C: Si el producto de dos matrices cuadradas A y B no es nulo, entonces ninguna de las matrices
es nula. (V)
• R: Si dadas dos matrices cuadradas A y B tales que, al menos una de las dos es nula, entonces el
producto de entre ellas es nulo. (V)
• CR: Si dadas dos matrices cuadradas A y B tales que, ninguna de las dos es nula, entonces el
producto de entre ellas no es nulo. (F)
• N: Existe un par de matrices cuadradas A y B tales que su producto es nulo y ninguna de ellas
es nula. (V)
J) (F)
• C: Si el cuadrado de una matriz cuadrada no es la matriz nula, entonces la matriz misma no es
nula. (V)• R: Si una matriz cuadrada es nula, entonces el cuadrado de la matriz es la matriz nula. (V)
• CR: Si una matriz cuadrada no es nula, entonces el cuadrado de la matriz no es la matriz nula.
(F)
• N: Existe una matriz no nula cuyo cuadrado es la matriz nula. (V)
22
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
Ejercicio 23.
• Acotación:
1 = x+ x′ 0 = xx′ (Por complemento)
1 = x+ 1x′ 0 = x(0 + x′) (Por neutros)
1 = (x+ 1)(x+ x′) 0 = x0 + xx′ (Por distributiva)
1 = (x+ 1)1 0 = x0 + 0 (Por complemento)
1 = x+ 1 0 = x0 (Por neutros) �
• Involución:
1 = x+ x′ 0 = xx′ (Por complemento)
1 = x′ + x 0 = x′x (Por conmutativa)
Entonces, (x′)′ = x (Inmediato del paso anterior) �
• Idempotencia:
x = x+ 0 x = 1x (Por neutros)
x = x+ xx′ x = (x+ x′)x (Por complemento)
x = (x+ x)(x+ x′) x = xx+ xx′ (Por distributiva)
x = (x+ x)1 x = xx+ 0 (Por complemento)
x = x+ x x = xx (Por neutros) �
• Absorción:
x+ xy = x1 + xy x(x+ y) = (x+ 0)(x+ y) (Por neutros)
x+ xy = x(1 + y) x(x+ y) = x+ (x+ y) (Por distributiva)
x+ xy = x1 x(x+ y) = x+ 0 (Por acotación)
x+ xy = x x(x+ y) = x (Por neutros) �
• De Morgan:
(x+ y)′ = x′y′ ⇔
⇔ (x+ y) + (x′y′) = 1 ∧ (x+ y)(x′y′) = 0 (Por complemento) ⇔
⇔ x+ y + x′y′ = 1 ∧ xx′y′ + x′yy′ = 0 (Por distributiva y asociativa) ⇔
⇔ 1 = 1 ∧ 0 = 0 (Por complemento y acotación) �
Luego, (xy)′ = (x′ + y′) se puede obtener de lo recién demostrado de la siguiente forma:
(x+ y)′ = x′y′ (Ya fue demostrado) ⇔
⇔ (x′ + y′)′ = (x′)′(y′)′ (x = x⇔ x′ = x′) ⇔
⇔ (x′ + y′)′ = xy (Por involución) ⇔
⇔ ((x′ + y′)′)′ = (xy)′ (x = x⇔ x′ = x′) ⇔
⇔ (x′ + y′) = (xy)′ (Por involución) �
23
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
• Asociativa:
Sean:
L = (xy)z
R = x(yz)
x+ L =
= x+ (xy)z (Por definición de L) =
= (x+ xy)(x+ z) (Por distributiva) =
= x(x+ z) (Por absorción) =
= x (Por absorción) =
= x(x+ yz) (Por absorción) =
= (x+ x)(x+ yz) (Por idempotencia) =
= x+ x(yz) (Por distributiva) =
= x+R (Por definición de R)
x′ + L =
= x′ + (xy)z (Por definición de L) =
= (x′ + xy)(x′ + z) (Por distributiva) =
= ((x′ + x)(x′ + y))(x′ + z) (Por distributiva) =
= (1(x′ + y))(x′ + z) (Por complemento) =
= (x′ + y)(x′ + z) (Por neutros) =
= x′ + yz (Por distributiva) =
= 1(x′ + yz) (Por neutros) =
= (x+ x′)(x′ + yz) (Por complemento) =
= x′ + x(yz) (Por distributiva) =
= x′ +R (Por definición de R) =
Entonces, se tiene que:
L = 0 + L = xx′ + L = (x+ L)(x′ + L) = (x+R)(x′ +R) = xx′ +R = 0 +R = R
L = R
(xy)z = x(yz)
Por principio de dualidad, se puede adaptar inmediatamente esta demostración para (x + y) + z =
x+ (y + z).
• Otras preguntas:
0 y 1 son únicos, ya que si 01 y 02 son ambos 0, debe cumplirse que 01 = 01 + 02 = 02, y entonces
serían el mismo elemento. Lo mismo ocurre con 1 ya que 11 = 1112 = 12.
Con la unicidad del complemento ocurre lo mismo, si hubiera otro serían iguales y esto se desprende
directamente de su definición.
Si un elemento fuese su propio complemento, se tendría que x+x 6= 0, lo que en este caso es x+x 6= xx,
y por idempotencia se llega a que x 6= x, por lo que esto no puedo ocurrir.
24
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
Ejercicio 24.
xy + xz x(y + z) x+ yz (x+ y)(x+ z)
Ejercicio 25.
(a1 + a2)(a2 + a3)(a3 + a1) =
(a1a2 + a1a3 + a2a2 + a2a3)(a3 + a1) (Por distributiva) =
(a1a3 + a2)(a3 + a1) (Por idempotencia y absorción) =
a1a3a3 + a1a3a1 + a2a3 + a2a1 (Por distributiva) =
a1a2 + a2a3 + a1a3 (Por asociativa e idempotencia)
Con cuatro elementos pueden repetirse estos mismos pasos y observar el mismo fenómeno.
Ejercicio 26.
Para observar con detenimiento el comportamiento de un álgebra de Boole, se pueden realizar las tablas de
sus operaciones.
+ 1 2 3 5 6 10 15 30
1 1 2 3 5 6 10 15 30
2 2 2 6 10 6 10 30 30
3 3 6 3 15 6 30 15 30
5 5 10 15 5 30 10 15 30
6 6 6 6 30 6 30 30 30
10 10 10 30 10 30 10 30 30
15 15 30 15 15 30 30 15 30
30 30 30 30 30 30 30 30 30
· 1 2 3 5 6 10 15 30
1 1 1 1 1 1 1 1 1
2 1 2 1 1 2 2 1 2
3 1 1 3 1 3 1 3 3
5 1 1 1 5 1 5 5 5
6 1 2 3 1 6 2 3 6
10 1 2 1 5 2 10 5 10
15 1 1 3 5 3 5 15 15
30 1 2 3 5 6 10 15 30
Con esta información, se puede concluir de forma inmediata que el elemento neutro de +, (0) es 1 y que el
elemento neutro de ·, (1) es 30.
Para que se trate de un álgebra de Boole, el complemento debe cumplir x+ x′ = 30 y xx′ = 1. Es decir, el
mínimo común múltiplo entre un elemento y su complemento debe ser 30 y el máximo común divisor debe
ser 1. Esto ocurre cuando x′ = 30x , ya que al tratarse de un conjunto de divisores de 30, número que está
compuesto por primos distintos entre sí, cuando se multiplican dos elementos y se obtiene 30, significa que
este es su mínimo común múltiplo y que 1 es su máximo común divisor, de lo contrario se podría afirmar
que estos elementos están compuestos por algún número primo en común, pero esto no puede ocurrir porque
como ya se dijo, 30 está compuesto por primos no repetidos.
25
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
Los átomos a para este álgebra, deben cumplir que mcd(x, a) = x ⇔ (x = a ∨ x = 1) y ser 6= 1. Desde la
tabla se puede observar que los elementos que cumplen esta condición son 2, 3 y 5. En este tipo de álgebras,
se da que los átomos son los elementos primos, ya que los demás elementos (salvo el 1, que por definición no
es átomo) tendrán como divisores a al menos dos de los primos del conjunto.
x+ yz + y′ + ux = 1
x = 1 ∧ yz = 1 ∧ y′ = 1 ∧ ux = 1
x = 1 ∧ y = 30
30z = 1 ∧ u1 = 1
z = 1 ∧ u ∈ D30
Las subálgebras son:
• {1, 2, 15, 30}
• {1, 3, 10, 30}
• {1, 5, 6, 30}
• {1, 30} (Trivial)
• {1, 2, 3, 5, 6, 10, 15, 30} (Trivial)
Resumiendo las conclusiones anteriores se responden las últimas preguntas: n debe estar compuesto por
primos distintos, es decir, ser un número "libre de cuadrados", ya que si no lo fuera, no se podría definir el
complemento. Como también ya fue explicado, los átomos serán los elementos primos.
Ejercicio 27.
Se tiene que β + γ = δ, y que γ · β = α. Al ser B un conjunto de cardinal 4, se puede asegurar que los
neutros son α y δ, porque si β o γ fueran neutros, alguna de las operaciones, ya sea "+" o "·", aplicada
a estos elementos, hubiese dado como resultado a sí mismos, así que no pueden ser neutros, y al quedar
únicamente dos elementos disponibles, se concluye que son α y δ. Como δ es el resultado de la operación
"+" en el dato que se tiene, debe ser el neutro de "·", ya que el neutro solo se obtiene si al operar consigo
mismo, y lo contrario ocurre con α, que es el neutro de "+". Con esta información, aplicando idempotencia
y conmutativa, se pueden completar las tablas:
+ α β γ δ
α α β γ δ
β β β δ δ
γ γ δ γ δ
δ δ δ δ δ
· α β γ δ
α α α α α
β α β α β
γ α α γ γ
δ α β γ δ
(α+ w(x+ y + z) = δ)⇔ ((w = δ) ∧ ((x = δ) ∨ (y = δ) ∨ (z = δ)))
(βγz + xyw + αδ = αγ)⇔ ((x = α) ∨ (y = α) ∨ (w = α))
(δxy + xz + α = yw) = y)⇔ (x(y + z) = y)
Si y = δ, xδ = δ, y no pueden ser ambos δ ya que se daría δδδ = α, entonces y = α. z depende de x para
que x + y + z = α sea cierta, y z debe ser distinto a x por xz = α, así que z = x′. Así que la solución a la
ecucación es (x, α, x′, δ) ∈ B4. En D10 es (x, 1, x′, 10) ∈ D410, con el mismo procedimiento.
26
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
Ejercicio 28.
(c) y (d), y, (h) y (g), son duales, así que solo hay que probar la equivalencia de una de las dos en cada caso.
• (a) ⇔ (b):
x+ y =
= xy + y (Por (a)) =
= xy + 1y (Por neutros) =
= (x+ 1)y (Por distributiva) =
= 1y (Por acotación) =
= y (Por neutros)
xy =
= x(x+ y) (Por (b)) =
= xx+ xy (Por distributiva) =
= x+ xy (Por idempotencia) =
= x1 + xy (Por neutros) =
= x(1 + y) (Por distributiva) =
= x1 (Por acotación) =
= x (Por neutros)
• (a) ⇔ (c):
xy′ =
= (xy)y′ (Por (a)) =
= x(yy′) (Por asociativa) =
= x0 (Por complemento) =
= 0 (Por acotación)
xy =
= xy + 0 (Por neutros) =
= xy + xy′ (Por (c) =
= x(y + y′) (Por distributiva) =
= x1 (Por complemento) == x (Por neutros)
• (e) ⇔ (f):
x′ =
= (x)′ =
= (y)′ (Por (e)) =
= y′
x =
= (x′)′ (Por involución) =
= (y′)′ (Por (f)) =
= y (Por involución)
• (e) ⇔ (g):
x′y + xy′ =
= x′x+ xx′ (Por (e)) =
= 0 + 0 (Por complemento) =
= 0
x =
= xy (Por (g) ⇒ (c) ⇒ (a)) =
= y (Por (g) ⇒ (c) ⇒ (a))
X ⊂ Y
27
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
Ejercicio 29.
• Reflexiva:
xx = x⇔ x = x (Por idempotencia) �
• Antisimétrica:
xy = x ∧ yx = y ⇔ x = xy = yx = y (Por conmutativa) �
• Transitiva:
xy = x ∧ yz = y ⇔ xz = (xy)z = x(yz) = xy = x (Por asociativa) �
Ejercicio 30.
A)
(Por acotación y neutros) 0x = 0 ∧ 1x = x⇔ 0 ≤ x ≤ 1 (Por def. de ≤)
B)
(Por conmutativa, asociativa e idempotencia) ((xy)x = (xx)y = xy)⇔ xy ≤ x (Por def. de ≤)
(Por distributiva, idempotencia y absorción) (x(x+ y) = x+ xy = x)⇔ x ≤ x+ y (Por def. de ≤)
C) Es corolario de (b).
D)
y′x′ = y′(xy)′ = y′(x′ + y′) = y′x′ + y′ = y′ ⇔ ((x ≤ y)⇒ (y′ ≤ x′) (Por def. de ≤)
Por involución, se puede obtener a partir de lo recién demostrado que (y′ ≤ x′)⇒ (x ≤ y).
E) Un elemento a distinto de cero es átomo si y solo si ∀x ∈ B : (x ≤ a)⇒ (x = 0∨x = a), y considerando
un x = b 6= a, se debe dar que ab = 0 o ab = a, pero este segundo caso es un absurdo ya que b es
distinto de a, por lo que ab = 0.
42
6 14 21
2 3 7
1
En D24, ≤ es |, y en P(A) es ⊂.
A) 1|x|42 — ∅ ⊂ X ⊂ A
B) (xy)|x|(x+ y) — (X ∩ Y ) ⊂ X ⊂ (X ∪ Y )
C) Quedan igual.
D) (x|y)⇔ (x′|y′) — (X ⊂ Y )⇔ (X ′ ⊂ Y ′)
E) ab = 1 — A ∪B = ∅
Hay 4 subálgebras y solo una está bien ordenada.
28
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
Isomorfismo entre D42 y P(A): f : D42 → P(A).
• f(1) = ∅
• f(2) = {α}
• f(3) = {β}
• f(7) = {γ}
• f(6) = {α, β}
• f(14) = {α, γ}
• f(21) = {β, γ}
• f(42) = A
A
{α, β} {α, γ} {β, γ}
{α} {β} {γ}
∅
Ejercicio 31.
Ejercicio repetido (es igual al 29).
Ejercicio 32.
84
12 28 42
4 6 14 21
2 3 7
1
1 ≤ 1 + 6x ≤ 84(2 + 7)
1 ≤ mcm(1, 6x) ≤ mcd(mcm(2, 7), 84)
1 ≤ 6x ≤ mcd(14, 84)
1 ≤ 6x ≤ 14
6x ≤ 14 (1 es mínimo, trivial)
mcd(mcd(6, x), 14) = mcd(6, x)
6x|14 ∨ 14|6x
x1 = 1, x2 = 2, x3 = 4, x4 = 7, x5 = 24, x6 = 28
6x = 6
mcd(6, x) = 6
6x|6 ∨ 6|6x
x1 = 6, x2 = 12, x3 = 42, x4 = 84
29
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
Ejercicio 33.
Por definición de isomorfismo, se sabe que:
• f(x+1 y) = f(x) +2 f(y) (Preservación de "+")
• f(x ·1 y) = f(x) ·2 f(y) (Preservación de "·")
• f(x′1) = f(x)′2 (Preservación del complemento)
Con estas 3 preservaciones, se pueden demostrar las demás.
Sea f : B1 → B2 un isomorfismo entre álgebras de Boole, con f(x1) = x2, f(y1) = y2.
• Preservación de los neutros:
x2 +2 f(01) =
= f(x1) +2 f(01) (Por f(x1) = x2) =
= f(x1 +1 01) (Por preservación de "+") =
= f(x1) (Por neutros) =
= x2 (Por f(x1) = x2)
Entonces, x2 +2 f(01) = x2, y para garantizar esto, por neutros, debe darse que f(01) = 02. �
x2 ·2 f(11) =
= f(x1) ·2 f(11) (Por f(x1) = x2) =
= f(x1 ·1 11) (Por preservación de "·") =
= f(x1) (Por neutros) =
= x2 (Por f(x1) = x2)
Entonces, x2 ·2 f(01) = x2, y para garantizar esto, por neutros, debe darse que f(11) = 12. �
• Preservación del orden:
x1 ≤1 y1 ⇔
⇔ x1 ·1 y1 = x1 (Por definición de ≤) ⇔
⇔ f(x1 ·1 y1) = f(x1) ⇔
⇔ f(x1) ·2 f(y1) = f(x1) (Por preservación de "·") ⇔
⇔ x2 ·2 y2 = x2 (Por f(x1) = x2 ∧ f(y1) = y2 ) ⇔
⇔ x2 ≤2 y2 (Por definición de ≤) �
• Preservación de los átomos:
Si a 6= 0 es un átomo de B1, debe ser f(a) 6= 02 = f(01) (ya que de no darse esto, f no sería inyectiva).
Dado 02 6= x2 ≤2 f(a). existe un único y no nulo x1 en B1 tal que f(x1) = x2, de modo que que
f(x1) ≤2 f(a) y entonces, por preservación del orden, x1 ≤1 a, y de allí resulta que x1 = a, de modo
que x2 = f(x1) = f(a), así que f(a) es un átomo en B2.
• Preservación de las subálgebras:
La preservación de las mismas se observa de forma directa a partir de la definición de isomorfismo, al
preservarse "+", "·" y el complemento, todas las subálgebras seguirán siendo cerradas bajo las tres
operaciones.
30
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
Para definir un isomorfismo entre álgebras de Boole, alcanza con definir las imágenes de los átomos, ya que
todos los elementos se pueden construir a través de operaciones (que se preservan) con los mismos. Pueden
definirse entonces, por combinatoria básica, n! isomorfismos, siendo n el número de átomos, que puede ser
calculado como log2(|B|).
Alcanza con que se preserven "+" y el complemento o "·" y el complemento, por la misma razón por la
que en el ejercicio 10 se mostró que (+,′ ) y (·,′ ) son juegos completos. Básicamente, la operación restante
puede ser construida con las otras dos y entonces con traducirla a las otras operaciones, se demuestra que
se preserva por la preservación de estas otras.
6
2 3
1
15
3 5
1
En el caso de (D6,mcm,mcd,′ , 1, 6) y (D15,mcm,mcd,′ , 1, 15), que tienen dos átomos cada una, se puede
definir 2! = 2 isomorfismos, que son:
• f : D6 → D15, f(2) = 3, f(3) = 5.
• f : D6 → D15, f(2) = 5, f(3) = 3.
Ejercicio 34.
A) (Extraído del circuito) (xy)′ + y′z =
(Por De Morgan) = x′ + y′ + y′z =
(Por absorción) = x′ + y′ =
(Por neutros) = x′11 + 1y′1 =
(Por complemento) = x′(y + y′)(z + z′) + (x+ x′)y′(z + z′) =
(Por distributiva) = x′yz + x′yz′ + x′y′z + x′y′z′ + xy′z + xy′z′ + x′y′z + x′y′z′ =
(Por idempotencia) = x′yz + x′yz′ + x′y′z + x′y′z′ + xy′z + xy′z′ F.N.D.
F.N.C: (x′ + y′ + z′)(x′ + y′ + z)
31
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
B)
Los circuitos NAND y NOR más simples, son:
x↑y ((x↓x)↓(y↓y))↓((x↓x)↓(y↓y))
C)
f(x, y, z) ≤ z′ ⇔
⇔ ((xy)′ ≤ z′)⇔
⇔ z ≤ xy (Demostrado en el ejercicio 30)⇔
⇔ xyz = z
z′f(x, y, z) + z(f(x, y, z))′ = 0⇔
⇔ z′(xy)′ + z((xy)′)′ = 0⇔
⇔ z′(xy)′ + zxy = 0
Entonces,
z = xyz = 0
(xy)′ = 0⇔ x′ + y′ = 0⇔ x = 1 ∧ y = 1
S = {(1, 1, 0)}
Ejercicio 35.
(Extraído del circuito) ((uv)′ + (v′(w + x)′))′ =
(Por De Morgan) = (uv)(v′(w + x)′)′ =
(Por De Morgan) = (uv)(v + (w + x)) =
(Por distributiva) = uvv + uv(w + x) =
(Por idempotencia) = uv + uv(w + x) =
(Por absorción) = uv
32
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
f(u, v, w, x) + uvw′x = w
uv + uvw′x = w
uv = w
u′f(u, v, w, x) + w + v = x
u′uv + w + v = x
u′uv + uv + v = x (uv = w)
v = x
Entonces,
S = {(v, v, uv, v)} con u, v ∈ B
Si B tiene cardinal 4, u y v pueden tomar 4 valores cada una, entonces hay 42 = 16 soluciones posibles.
Ejercicio 36.
• Maximales:
– Primera:
∗ A - h, g
∗ A1 - g
∗ A2 - e, d
∗ A3 - h
– Segunda:
∗ A - h, g, i
∗ A1 - g
∗ A2 - e, d
∗ A3 - i, h
• Cotas superiores:
– Primera:
∗ A - No hay
∗ A1 - g
∗ A2 - h, f, g
∗ A3 - h
– Segunda:
∗ A - No hay
∗ A1 - g
∗ A2 - h, f, g
∗ A3 - No hay
• Supremos:
– Primera:
∗ A - No hay
∗ A1 - g
∗ A2 - f
∗ A3 - h
– Segunda:
∗ A - No hay
∗ A1 - g
∗ A2 - f
∗ A3 - No hay
• Minimales:
– Primera:
∗ A - i, a
∗ A1 - b
∗ A2 - c, e
∗ A3 - i, a
– Segunda:
∗ A - a
∗ A1 - b
∗ A2 - c, e
∗ A3 - a
• Cotas inferiores:
– Primera:
∗ A - No hay
∗ A1 - i, b, a
∗ A2 - a
∗ A3 - No hay
– Segunda:
∗ A - a
∗ A1 - b, a
∗ A2 - a
∗ A3 - a
• Ínfimos:
– Primera:
∗ A - No hay
∗ A1 - b
∗ A2 - a
∗ A3 - No hay
– Segunda:
∗ A - a
∗ A1 - b
∗ A2 - a
∗ A3 - a
33
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
• Máximos:
– Primera:
∗ A - No hay
∗ A1 - g
∗ A2 - No hay
∗ A3 - h
– Segunda:
∗ A - No hay
∗ A1 - g
∗ A2 - No hay
∗ A3 - No hay
• Mínimos:
– Primera:
∗ A - No hay
∗ A1 - b
∗ A2 - No hay
∗ A3 - No hay
– Segunda:
∗ A - a
∗ A1 - b
∗ A2 - No hay
∗ A3 - a
• Acotados:
– Primera:
∗ A - No
∗ A1 - Sí
∗ A2 - Sí
∗ A3 - No
– Segunda:
∗ A - No
∗ A1 - Sí
∗ A2 - Sí
∗ A3 - No
Ejercicio 37.
Para que (B,+, .,′ , 0, 1) resulte un álgebra de Boole, es necesario que 1 sea el supremo del conjunto (para
garantizar x1 = x) y que 0 sea el ínfimo (para garantizar x + 0 = x), entonces, 0 = α y 1 = ω.Para el
complemento, se debe cumplir que x+x′ = ω y que xx′ = α, por lo que hay que buscar, para cada elemento,
su par que cumpla con estas dos ecuaciones. En la siguiente tabla queda definida la operación:
α a b c d e f ω
′ ω f e d c b a α
Las subálgebras son:
• {α, a, f, ω}
• {α, b, e, ω}
• {α, c, d, ω}
• {α, ω} (Trivial)
• {α, a, b, c, d, e, f, ω} (Trivial)
En el sistema de ecuaciones, la tercera no aporta nada, ya que α ≤ x se cumple para todo x, por ser α el
ínfimo. Luego, por la primera ecuación:
ax′ ≤ b+ af + eb
ax′ ≤ b+ α+ α
ax′ ≤ b
(ax′)b = (ax′)
b′ax′ = α (Demostrado en el ejercicio 15)
Y por la segunda:
b′x+ c = ω + c
b′x+ c = ω
(b′x+ c)′ = ω′
34
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
(b′x)′c′ = α
(b+ x′)c′ = α
bc′ + x′c′ = α
α+ x′c′ = α
x′c′ = α
Entonces, combinando los resultados obtenidos:
(ab′ + c′)x′ = α
ex′ = α
e ≤ x (Demostrado en el ejercicio 15)
S = {e, ω}
Ejercicio 38.
A1 = {x ∈ A : x+ 1 ≤ 12} = {1, 2, 3}
A2 = {x ∈ A : 6 ≤ x} = {6, 12, 18, 24}
A3 = {x ∈ A : x ≤ x+ 3} = {1, 3}
A4 = {x ∈ A : 4 ≤ x ≤ 8} = {4, 8}
• Maximales:
– A - 24, 18
– A1 - 2, 3
– A2 - 24, 18
– A3 - 3
– A4 - 8
• Cotas superiores:
– A - No hay
– A1 - 6, 12, 16, 24
– A2 - No hay
– A3 - 3, 6, 9, 12, 18, 24
– A4 - 8, 24
• Minimales:
– A - 1
– A1 - 1
– A2 - 6
– A3 - 1
– A4 - 4
• Cotas inferiores:
– A - 1
– A1 - 1
– A2 - 1, 2, 3, 6
– A3 - 1
– A4 - 1, 2, 4
24
8 12 18
4 6 9
2 3
1
35
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
• Supremos:
– A - No hay
– A1 - 6
– A2 - No hay
– A3 - 3
– A4 - 8
• Ínfimos:
– A - 1
– A1 - 1
– A2 - 6
– A3 - 1
– A4 - 4
• Máximos:
– A - No hay
– A1 - No hay
– A2 - No hay
– A3 - 3
– A4 - 8
• Mínimos:
– A - 1
– A1 - 1
– A2 - 6
– A3 - 1
– A4 - 4
Son acotados: A1, A3 y A4.
La ecuación de incógnita X ⊂ A, se resuelve así:
(A1 +A4)X = A3
((A1 +A4)X)
′A3 + ((A1 +A4)X)A
′
3 = ∅ (Demostrado en el ejercicio 16)
((A1 +A4)
′ +X ′)A3 + ((A1 +A4)X)A
′
3 = ∅ (Por De Morgan)
(A′1A
′
4 +X
′)A3 + ((A1 +A4)X)A
′
3 = ∅ (Por De Morgan)
A′1A3A
′
4 +A3X
′ + ((A1 +A4)A
′
3)X = ∅ (Por distributiva y asociativa)
∅ +A3X ′ + ((A1 +A4)A′3)X = ∅ (A′1A3A′4 = ∅)
∅ +A3X ′ + (((A1 +A4)A′3)′)′X = ∅ (Por involución)
A3X
′ = ∅ ∧ (((A1 +A4)A′3)′)′X = ∅ (Demostrado en el ejercicio 14)
A3 ⊂ X ∧X ⊂ ((A1 +A4)A′3)′ (Demostrado en el ejercicio 15)
A3 ⊂ X ⊂ ((A1 +A4)A′3)′
{1, 3} ⊂ X ⊂ {1, 3, 6, 9, 12, 18, 24}
Dos soluciones son: {1, 3} (minimal) y {1, 3, 6, 9, 12, 18, 24} (maximal). Para calcular la cantidad de solu-
ciones para esta ecuación, por combinatoria básica se puede afirmar que se pueden generar m!p!(m−p)! conjun-
tos distintos de p elementos, seleccionando entre m elementos. Como se quiere contar cuantos conjuntos se
pueden generar con los elementos que el maximal tiene y el minimal no:
n∑
i=0
n!
i!(n− i)!
Siendo n la diferencia entre los cardinales de los conjuntos maximal y minimal, que en este caso es 5, por lo
que la cantidad de soluciones es
5∑
i=0
5!
i!(5− i)!
= 32
Ejercicio 39.
A)
A partir de la matriz de adyacencia de T , es sencillo construir el digrafo de S + T , ya que bastará con tomar
el digrafo de S y agregarle las relaciones que muestra la matriz de T . Luego, para construir R = (S + T )−1
se invierte la dirección de las relaciones en el digrafo obtenido.
36
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
a3 a5
a2 a1 a4
R−1 = S + T
a3 a5
a2 a1 a4
R = (S + T )−1
a5
a3
a4
a2
a1
Como se puede observar, todos los elementos tienen relación consigo
mismos, así que R es reflexiva. No hay relaciones bidireccionales, por
lo que también es antisimétrica. Lo mismo ocurre con la transitividad,
puesto que en el diagrama se la puede observar en todos los casos
(por ejemplo a1Ra4 ∧ a4Ra5 ⇒ a1Ra5 y a1Ra2 ∧ a2Ra3 ⇒ a1Ra3).
Entonces, por ser reflexiva, antisimétrica y transitiva, R es una relación
de orden, y gracias a esto, se puede dibujar su diagrama de Hasse.
xy + x = a3
sup(inf(x, y), x)) = a3
El ínfimo de x e y será un elemento que estará relacionado a ambos, entonces el supremo de ese elemento
con x debe ser x, ya que x es el menor elemento con el que x se relaciona, lo que hará que siempre sea la
menor de las cotas superiores.
x = a3
(a3 + y)R(a3a5)
sup(a3, y)R(a3)
y = a1 ∨ y = a2 ∨ y = a3
Entonces,
S = {(a3, a1), (a3, a2), (a3, a3)}
B)
Tal como se puede observar en el digrafo deR−1, los elementos a distancia 1 de a1 que forman la circunferencia
son a2, a3, a4 y a5.
37
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
Ejercicio 40.
A) • Reflexiva: ∀x ∈ D24, xRx, pues x = x · 1⇒ x|x
• Antisimétrica: ∀x∀y ∈ D24, (xRy ∧ yRx)⇒ x = y, pues:
xRy ∧ yRx⇒
⇒ y = xk ∧ x = yk′ (con k, k′ ∈ N)⇒
⇒ y = yk′k ⇒ k′k = 1⇒ k = 1 ∧ k′ = 1⇒ x = y
• Transitiva: ∀x∀y∀z ∈ D24, (xRy ∧ yRz)⇒ xRz, pues:
xRy ∧ yRz ⇒
⇒ y = xk ∧ z = yk′ (con k, k′ ∈ N)⇒
⇒ z = xkk′ ⇒ xRz
Entonces, R es una relación de orden en el conjunto finito D24.
AR =

1 1 1 1 1 1 1 1
0 1 0 1 1 1 1 1
0 0 1 0 1 0 1 1
0 0 0 1 0 1 1 1
0 0 0 0 1 0 1 1
0 0 0 0 0 1 0 1
0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 1

24
8 12
4 6
2 3
1
B) • Reflexiva: ∀x ∈ N, xRx, pues x = x⇒ x = x1
• Antisimétrica: ∀x∀y ∈ N, (xRy ∧ yRx)⇒ x = y, pues:
xRy ∧ yRx⇒
⇒ y = xn ∧ x = yn
′
(con n, n′ ∈ N)⇒
⇒ y = (yn
′
)n ⇒ y = yn
′n ⇒ n′n = 1⇒ n = 1 ∧ n′ = 1⇒ x = y
• Transitiva: ∀x∀y∀z ∈ N, (xRy ∧ yRz)⇒ xRz, pues:
xRy ∧ yRz ⇒
⇒ y = xn ∧ z = yn
′
(con n, n′ ∈ N)⇒
⇒ z = (xn)n
′
⇒ z = xnn
′
⇒ xRz
Entonces, R es una relación de orden en el conjunto infinito N.
38
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
C) R no es una relación de orden en el conjunto finito A porque no es antisimétrica, esto se puede probar
con el contraejemplo x = 1, y = −1, donde (−1)|1 y 1|(−1) pero 1 6= −1.
AR =

1 0 0 1
1 1 1 1
1 1 1 1
1 0 0 1

1 -1
2 -2
D) • Reflexiva: ∀(x1, x2) ∈ A2, (x1, x2)R(x1, x2), pues x1 = x1 ∧ x2 = x2 ⇒ x1 ≤ x1 ∧ x2 ≥ x2
• Antisimétrica: ∀(x1, x2)∀(y1, y2) ∈ A2, ((x1, x2)R(y1, y2) ∧ (y1, y2)R(x1, x2))⇒
⇒ (x1, x2) = (y1, y2), pues:
(x1, x2)R(y1, y2) ∧ (y1, y2)R(x1, x2)⇒
⇒ (x1 ≤ y1 ≤ x1) ∧ (x2 ≥ y2 ≥ x2)⇒ x1 = y1 ∧ x2 = y2 ⇒
⇒ (x1, x2) = (y1, y2)
• Transitiva: ∀(x1, x2)∀(y1, y2)∀(z1, z2) ∈ A2, ((x1, x2)R(y1, y2) ∧ (y1, y2)R(z1, z2))⇒
⇒ (x1, x2)R(z1, z2), pues:
(x1, x2)R(y1, y2) ∧ (y1, y2)R(z1, z2)⇒
⇒ (x1 ≤ y1 ≤ z1) ∧ (x2 ≥ y2 ≥ z2)⇒ x1 ≤ z1 ∧ x2 ≥ z2 ⇒
⇒ x1, x2)R(z1, z2)
Entonces, R es una relación de orden en el conjunto finito A2.
AR =

1 1 1 1 1 1 1 1 1
0 1 0 1 0 1 1 1 1
0 0 1 0 1 1 1 1 1
0 0 0 1 0 0 1 0 1
0 0 0 0 1 0 0 1 1
0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 1 0 1
0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 1

(2,0)
(1,0) (2,1)
(0,0) (1,1) (2,2)
(0,1) (1,2)
(0,2)
39
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
E) R no es una relación de orden en el conjunto infinito Z porque no es antisimétrica, esto se puede probar
con el contraejemplo x = 1, y = 2, donde |2− 1| es impar y |1− 2| es impar, pero 1 6= 2.
F) R no es una relación de orden en el conjunto infinito Z porque no es antisimétrica, esto se puede probar
con el contraejemplo x = −1, y = 1, donde (−1)2 ≤ (1)2 y (1)2 ≤ (−1)2, pero −1 6= 1.
G) • Reflexiva: ∀(x1, x2) ∈ A2, (x1, x2)R(x1, x2), pues (x1 = x1 · 1 ∧ x2 = x2 · 1)⇒ (x1|x1 ∧ x2|x2)
• Antisimétrica: ∀(x1, x2)∀(y1, y2) ∈ A2, ((x1, x2)R(y1, y2) ∧ (y1, y2)R(x1, x2))⇒
⇒ (x1, x2) = (y1, y2), pues:
(x1, x2)R(y1, y2) ∧ (y1, y2)R(x1, x2)⇒
⇒ (y1 = x1k1 ∧ x1 = y1k′1) ∧ (x2 = y2k2 ∧ y2 = x2k′2) (con k1, k2, k′1k′2 ∈ N)⇒
⇒ (y1 = y1k′1k1 ∧ x2 = x2k′2k2)⇒ (k′1k1 = 1 ∧ k′2k2 = 1)⇒
⇒ (k1 = 1 ∧ k′1 = 1) ∧ (k2 = 1 ∧ k′2 = 1)⇒ x1 = y1 ∧ x2 = y2 ⇒
⇒ (x1, x2) = (y1, y2)
• Transitiva: ∀(x1, x2)∀(y1, y2)∀(z1, z2) ∈ A2, ((x1, x2)R(y1, y2) ∧ (y1, y2)R(z1, z2))⇒
⇒ (x1, x2)R(z1, z2), pues:
(x1, x2)R(y1, y2) ∧ (y1, y2)R(z1, z2)⇒
⇒ (y1 = x1k1 ∧ z1 = y1k′1) ∧ (x2 = y2k2 ∧ y2 =z2k′2) (con k1, k2, k′1k′2 ∈ N)⇒
⇒ (z1 = x1k1k′1 ∧ x2 = z2k′2k2)⇒
⇒ (x1, x2)R(z1, z2)
Entonces, R es una relación de orden en el conjunto finito A2.
AR =

1 0 1 1 1 0 0 1 1
0 1 0 0 1 1 1 1 1
0 0 1 0 0 0 0 1 0
0 0 0 1 0 0 0 0 1
0 0 0 0 1 0 0 1 1
0 0 0 0 0 1 0 1 0
0 0 0 0 0 0 1 0 1
0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1

(3,1)(2,1)
(3,3)(2,3)(1,1)(3,2)(2,2)
(1,3)(1,2)
Ejercicio 41.
AX ′ ⊂ B
AB′X ′ = ∅
AB′ ⊂ X
B′X + C = I
(B′X + C)′ = ∅
(B +X ′)C ′ = ∅
BC ′ +X ′C ′ = ∅
BC ′ = ∅ ∧X ′C ′ = ∅
B ⊂ C ∧ C ′ ⊂ X
Entonces, combinando los resultados obtenidos:
B ⊂ C ∧AB′ + C ′ ⊂ X
40
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
A1 = {x ∈ A : 6 ≤ x} = {6, 12, 18}
A2 = {x ∈ A : x ≤ x+ 3} = {1, 3}
A3 = {x ∈ A : x+ 1 ≤ 12} = {1, 2, 3}
AB′ + C ′ ⊂ X ⊂ I
{4, 6, 8, 9, 12, 18} ⊂ X ⊂ {1, 2, 3, 4, 6, 8, 9, 12, 18}
Entonces, la solución minimal es {4, 6, 8, 9, 12, 18}, que no es aco-
tada.
8 12 18
4 6 9
2 3
1
Ejercicio 42.
A) • Simétrica
• Antisimétrica
• Transitiva
a2
a1
B) • Reflexiva
• Simétrica
• Antisimétrica
• Transitiva
a2
a1
C) • Simétrica
• Clausura transitiva: F)
a2
a1
41
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
D) • Antisimétrica
• Transitiva
a2
a1
E) • Reflexiva
• Antisimétrica
• Transitiva
a2
a1
F) • Reflexiva
• Simétrica
• Transitiva
a2
a1
R = R2 para todas las que son transitivas. En el caso de C), R2 es F).
Ejercicio 43.
A) Ra no es reflexiva ni simétrica ni antisimétrica ni transitiva. R′a es reflexiva, y no es simétrica ni
antisimétrica ni transitiva.
a1 a2
a3 a4
Ra
a1 a2
a3 a4
R′a
a1 a2
a3 a4
R?at
a1 a2
a3 a4
(R′a)?t
42
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
B) Rb es antisimétrica, y no es reflexiva ni simétrica ni transitiva. R′b no es reflexiva ni simétrica ni
antisimétrica ni transitiva.
a1 a2
a3 a4
Rb
a1 a2
a3 a4
R′b
a1 a2
a3 a4
R?bt
a1 a2
a3 a4
(R′b)?t
C) Rc es antisimétrica, y no es reflexiva ni simétrica ni transitiva. R′c es reflexiva, y no es simétrica ni
antisimétrica ni transitiva.
a1 a2
a3 a4
Rc
a1 a2
a3 a4
R′c
a1 a2
a3 a4
R?ct
a1 a2
a3 a4
(R′c)?t
D) Rd es reflexiva, simétrica y transitiva, y no es antisimétrica. R′d es simétrica, y no es reflexiva ni
antisimétrica ni transitiva.
a1 a2
a3 a4
Rd y R?dt
a1 a2
a3 a4
R′d
a1 a2
a3 a4
(R′d)?t
a1 a2
a3 a4
La única relación de equivalencia es Rd, y su con-
junto cociente es A/Rd = {[a1], [a3]}, con las clases
de equivalencia [a1] = {a1, a2, a4} y [a3] = {a3}.
43
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
(A+B)R =

1 1 0 1
1 0 1 1
1 0 0 0
0 1 1 0
 (AB)R =

0 0 0 0
0 0 1 0
0 0 0 0
0 0 1 0
 (A ◦B)R =

1 0 1 0
1 0 1 0
0 0 0 0
1 0 1 0

R(a+b) no es reflexiva ni simétrica ni antisimétrica ni transitiva. R′(a+b) es antisimétrica, y no es reflexiva ni
simétrica ni transitiva.
a1 a2
a3 a4
R(a+b)
a1 a2
a3 a4
R′(a+b)
a1 a2
a3 a4
R?(a+b)t
a1 a2
a3 a4
(R′(a+b))
?
t
R(ab) es antisimétrica y transitiva, y no es reflexiva ni simétrica. R′(ab) es reflexiva, y no es simétrica ni
antisimétrica ni transitiva.
a1 a2
a3 a4
R(ab) y R?(ab)t
a1 a2
a3 a4
R′(ab)
a1 a2
a3 a4
(R′(ab))
?
t
R(a◦b) es antisimétrica y transitiva, y no es reflexiva ni simétrica. R′(a◦b) es transitiva, y no es reflexiva ni
simétrica ni antisimétrica.
a1 a2
a3 a4
R(a◦b) y R?(a◦b)t
a1 a2
a3 a4
R′(a◦b) y (R
′
(a◦b))
?
t
44
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
Ejercicio 44.
A) ∀R relación binaria de X en Y , R = (R−1)−1. Esto es equivalente a decir, que ∀u ∈ X,∀v ∈ Y, (u, v) ∈
R ⇔ (u, v) ∈ (R−1)−1.
(u, v) ∈ R ⇔ (v, u) ∈ R−1 (Por definición de −1)
(v, u) ∈ R−1 ⇔ (u, v) ∈ (R−1)−1 (Por definición de −1)
�
B) ∀R relación binaria de X en Y , (R′)−1 = (R−1)′. Esto es equivalente a decir, que ∀u ∈ Y,∀v ∈
X, (u, v) ∈ (R′)−1 ⇔ (u, v) ∈ (R−1)′.
(u, v) ∈ (R′)−1 ⇔ (v, u) ∈ R′ (Por definición de −1)
(v, u) ∈ R′ ⇔ (v, u) /∈ R (Por definición de ′)
(v, u) /∈ R ⇔ (u, v) /∈ R−1 (Por definición de −1)
(u, v) /∈ R−1 ⇔ (u, v) ∈ (R−1)′ (Por definición de ′)
�
C) ∀R∀S relaciones binarias de X en Y , (R + S)−1 = R−1 + S−1. Esto es equivalente a decir, que
∀u ∈ Y,∀v ∈ X, (u, v) ∈ (R+ S)−1 ⇔ (u, v) ∈ (R−1 + S−1).
(u, v) ∈ (R+ S)−1 ⇔ (v, u) ∈ (R+ S) (Por definición de −1)
(v, u) ∈ (R+ S)⇔ ((v, u) ∈ R ∨ (v, u) ∈ S) (Por definición de "+")
((v, u) ∈ R ∨ (v, u) ∈ S)⇔ ((u, v) ∈ R−1 ∨ (u, v) ∈ S−1) (Por definición de −1)
((u, v) ∈ R−1 ∨ (u, v) ∈ S−1)⇔ (u, v) ∈ (R−1 + S−1) (Por definición de "+")
�
D) ∀R∀S relaciones binarias de X en Y , (R · S)−1 = R−1 · S−1. Esto es equivalente a decir, que
∀u ∈ Y,∀v ∈ X, (u, v) ∈ (R · S)−1 ⇔ (u, v) ∈ (R−1 · S−1).
(u, v) ∈ (R · S)−1 ⇔ (v, u) ∈ (R · S) (Por definición de −1)
(v, u) ∈ (R · S)⇔ ((v, u) ∈ R ∧ (v, u) ∈ S) (Por definición de "·")
((v, u) ∈ R ∧ (v, u) ∈ S)⇔ ((u, v) ∈ R−1 ∧ (u, v) ∈ S−1) (Por definición de −1)
((u, v) ∈ R−1 ∧ (u, v) ∈ S−1)⇔ (u, v) ∈ (R−1 · S−1) (Por definición de "·")
�
E) ∀R∀S relaciones binarias de X en Y , R−1 ⊂ S−1 ⇔ R ⊂ S. Esto es equivalente a decir, que
(∀u ∈ Y,∀v ∈ X, (u, v) ∈ R−1 → (u, v) ∈ S−1)⇔ (∀u ∈ X,∀v ∈ Y, (u, v) ∈ R → (u, v) ∈ S).
(u, v) ∈ R ⇒ (v, u) ∈ R−1 (Por definición de −1)
(v, u) ∈ R−1 ⇒ (v, u) ∈ S−1 (Por hipótesis)
(v, u) ∈ S−1 ⇒ (u, v) ∈ S (Por definición de −1)
(u, v) ∈ R−1 ⇒ (v, u) ∈ R (Por definición de −1)
(v, u) ∈ R ⇒ (v, u) ∈ S (Por hipótesis)
(v, u) ∈ S ⇒ (u, v) ∈ S−1 (Por definición de −1)
�
45
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
F) ∀R∀S relaciones binarias de X en Y , R−1 = S−1 ⇔ R = S. Esto es equivalente a decir, que
(∀u ∈ Y,∀v ∈ X, (u, v) ∈ R−1 ↔ (u, v) ∈ S−1)⇔ (∀u ∈ X,∀v ∈ Y, (u, v) ∈ R ↔ (u, v) ∈ S).
(u, v) ∈ R ⇔ (v, u) ∈ R−1 (Por definición de −1)
(v, u) ∈ R−1 ⇔ (v, u) ∈ S−1 (Por hipótesis)
(v, u) ∈ S−1 ⇔ (u, v) ∈ S (Por definición de −1)
(u, v) ∈ R−1 ⇔ (v, u) ∈ R (Por definición de −1)
(v, u) ∈ R ⇔ (v, u) ∈ S (Por hipótesis)
(v, u) ∈ S ⇔ (u, v) ∈ S−1 (Por definición de −1)
�
G) ∀S relación binaria de X en Y , ∀T relación binaria de Y en Z, (S ◦ T )−1 = T −1 ◦ S−1. Esto es
equivalente a decir, que ∀u ∈ X,∀w ∈ Z, (w, u) ∈ (S ◦ T )−1 ⇔ (w, u) ∈ (T −1 ◦ S−1).
(w, u) ∈ (S ◦ T )−1 ⇔ (u,w) ∈ (S ◦ T ) (Por definición de −1)
(u,w) ∈ (S ◦ T )⇔ (∃v ∈ Y : ((u, v) ∈ S ∧ (v, w) ∈ T )) (Por definición de "◦")
(∃v ∈ Y : ((u, v) ∈ S ∧ (v, w) ∈ T ))⇔ (∃v ∈ Y : ((v, u) ∈ S−1 ∧ (w, v) ∈ T −1)) (Por definición de −1)
(∃v ∈ Y : ((v, u) ∈ S−1 ∧ (w, v) ∈ T −1))⇔ (w, u) ∈ (T −1 ◦ S−1) (Por definición de "◦")
�
En el lenguaje de matrices de adyacencia se escriben:
A) (ATR)
T = AR
B) (J −AR)T = J − (ATR)
C) (AR +AS)T = ATR +A
T
S
D) (AR �AS)T = ATR �ATS
E) ATR ≤ ATS ⇔ AR ≤ AS
F) ATR = A
T
S ⇔ AR = AS
G) (ASAT )T = ATSA
T
T
Ejercicio 45.
(S ◦ T )−1 = T −1 ◦ S−1 ya fue demostrado en el punto anterior.
(S ◦ T )? = T ? ◦ S? es invalida, esto se puede observar con los siguientes digrafos:
a1 a2
a3 a4
S?
a1 a2
a3 a4
T ?
a1 a2
a3 a4
(S ◦ T )?
a1 a2
a3 a4
T ? ◦ S?
46
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
Ejercicio 46.
Una relación R es de equivalencia sii es reflexiva, simétrica y transitiva, y es de orden sii es reflexiva,
antisimétrica y transitiva. Las propiedades indicadas en el ejercicio son idénticas a las mencionadas, y esta
es la razón por la cual son relaciones de equivalencia u orden. A continuación se explica la igualdad de cada
una de estas propiedades con las del ejercicio:
• ∆ ⊂ R significa que R contiene a la relación identidad, la cual únicamente relaciona a cada elemento
consigo mismo, es decir, contiene exclusivamente a los pares que garantizan la reflexividad. Por lo que
contener a ∆, es condición necesaria y suficiente para que una relación sea reflexiva. En lenguaje
matricial, esto es que la matriz de adyacencia de la relación identidad sea menor o igual a la de R, lo
que garantizaque R tenga la diagonal que la hace reflexiva. Esto se escribe como Id ≤ AR.
• R−1 = R significa que R es igual a su inversa, es decir, ya que los pares invertidos tienen que
pertenecer a ambas, que si un elemento a se relaciona con un elemento b, b se relaciona con a, la cual es
la condición necesaria y suficiente para que una relación sea simétrica. En lenguaje matricial, esto es
que las matrices de adyacencia de una relación y su inversa sean iguales, lo que significa que la matriz
es simétrica. Esto se escribe como ATR = AR.
• RR−1 ⊂ ∆ significa que R y su inversa solo pueden tener en común pares de elementos iguales, es
decir, ya que de lo contrario habría elementos no pertenecientes a la relación identidad, que si un
elemento a se relaciona con un elemento b, y b se relaciona con a, esto es porque son iguales, la cual
es la condición necesaria y suficiente para que una relación sea antisimétrica. En lenguaje matricial,
esto es que la matriz de adyacencia de R no tenga 1’s en lugares donde la matriz de su inversa los
tenga y no sean la diagonal reflexiva. Esto se escribe como AR �ATR ≤ Id.
• (R◦R) ⊂ R significa que R se contiene a sí misma compuesta de sí misma, es decir que si un elemento
a está relacionado con un elemento b, y b con un elemento c, por definición de composición, a se
relacionará con c, la cual es la condición necesaria y suficiente para que una relación sea transitiva.
En lenguaje matricial, esto es que la matriz de adyacencia de la relación sea mayor o igual a su cuadrado.
Esto se escribe como A2R ≤ AR.
Ejercicio 47.
A) • Reflexiva: ∀x ∈ Z, xRx, pues x− x = 0 = n · 0⇒ x = x (mod n)
• Simétrica: ∀x∀y ∈ Z, xRy ⇒ yRx, pues:
xRy ⇒ x = y (mod n)⇒ x− y = nk (con k ∈ Z)⇒
⇒ y − x = n(−k)⇒ y = x (mod n)⇒ yRx
• Transitiva: ∀x∀y∀z ∈ Z, (xRy ∧ yRz)⇒ xRz, pues:
(xRy ∧ yRz)⇒ (x = y (mod n) ∧ y = z (mod n))⇒
⇒ (x− y = nk ∧ y − z = nk′) (con k, k′ ∈ Z)⇒ x− z = n(k + k′)⇒ x = z (mod n)⇒ xRz
Entonces, R es una relación de equivalencia en el conjunto Z. Su conjunto cociente es Z/R =
{[1], [2], ..., [n]}.
47
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
B) • Reflexiva: ∀x ∈ BA, xRx, pues x = x⇒ f(x) = f(x)
• Simétrica: ∀x∀y ∈ BA, xRy ⇒ yRx, pues:
xRy ⇒ f(x) = f(y)⇒ f(y) = f(x)⇒ yRx
• Transitiva: ∀x∀y∀z ∈ BA, (xRy ∧ yRz)⇒ xRz, pues:
(xRy ∧ yRz)⇒ (f(x) = f(y) ∧ f(y) = f(z))⇒ f(x) = f(z)⇒ xRz
Entonces, R es una relación de equivalencia en el conjunto BA. Su conjunto cociente es BA/R =
{[x], [y], ...} con [x] = f−1(f(x)).
C) • Reflexiva: ∀x ∈ R, xRx, pues x = x⇒ x2 + 2x = 2x+ x2
• Simétrica: ∀x∀y ∈ R, xRy ⇒ yRx, pues:
xRy ⇒ x2 + 2y = 2x+ y2 ⇒ y2 + 2x = 2y + x2 ⇒ yRx
• Transitiva: ∀x∀y∀z ∈ R, (xRy ∧ yRz)⇒ xRz, pues:
(xRy∧yRz)⇒ (x2+2y = 2x+y2∧y2+2z = 2y+z2)⇒ (x2−2x = y2−2y∧y2−2y = z2−2z)⇒
⇒ x2 − 2x = z2 − 2z ⇒ x2 + 2z = 2x+ z2 ⇒ xRz
Entonces, R es una relación de equivalencia en el conjunto R. Su conjunto cociente es R/R =
{[x], [y], ...f} con [x] = {x, 2− x}.
D) • Reflexiva: ∀x ∈ Z, xRx, pues x2 − x2 = 0 = 7 · 0⇒ x2 = x2 (mod 7)
• Simétrica: ∀x∀y ∈ Z, xRy ⇒ yRx, pues:
xRy ⇒ x2 = y2 (mod 7)⇒ x2 − y2 = 7k (con k ∈ Z)⇒
⇒ y2 − x2 = 7(−k)⇒ y2 = x2 (mod 7)⇒ yRx
• Transitiva: ∀x∀y∀z ∈ Z, (xRy ∧ yRz)⇒ xRz, pues:
(xRy ∧ yRz)⇒ (x2 = y2 (mod 7) ∧ y2 = z2 (mod 7))⇒
⇒ (x2−y2 = 7k∧y2−z2 = 7k′) (con k, k′ ∈ N)⇒ x2−z2 = 7(k+k′)⇒ x2 = z2 (mod 7)⇒ xRz
Entonces, R es una relación de equivalencia en el conjunto Z. Su conjunto cociente es Z/R =
{[1], [2], [3], [7]}.
E) R no es una relación de equivalencia en el conjunto Z porque no es transitiva, esto se puede probar
con el contraejemplo x = 1, y = 0, z = (−1) donde 1 · 0 ≥ 0 y 0 · (−1) ≥ 0 pero 1 · (−1) < 0.
F) R es una relación de equivalencia en el conjunto P(X), esto es un caso especial de lo que se probará que
en ítem H), ya que representa un álgebra de Boole. Hay una clase de equivalencia por cada elemento
del conjunto, ya que solo relaciona a cada uno únicamente consigo mismo.
G) R no es una relación de equivalencia en el conjunto P(X) porque no es simétrica, esto se puede probar
con el contraejemplo X1 = X, X2 = ∅ donde X + ∅′ = X pero ∅ +X ′ 6= X.
H) R es una relación de equivalencia en un álgebra de Boole, ya que (x+y = xy)⇔ (x = y), entonces, esta
relación asocia a cada elemento exclusivamente consigno mismo, es decir, que se trata de la relación
identidad (∆). Por la razón enunciada recién, habrá una clase de equivalencia por cada elemento del
conjunto.
48
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
I) • Reflexiva: ∀f ∈ RI , fRf , pues f = f ⇒
∫
I
f(t) =
∫
I
f(t)
• Simétrica: ∀f∀g ∈ RI , fRg ⇒ gRf , pues:
fRg ⇒
∫
I
f(t) =
∫
I
g(t)⇒
∫
I
g(t) =
∫
I
f(t)⇒ gRf
• Transitiva: ∀f∀g∀h ∈ RI , (fRg ∧ gRh)⇒ fRh, pues:
(fRg ∧ gRh)⇒ (
∫
I
f(t) =
∫
I
g(t) ∧
∫
I
g(t) =
∫
I
h(t))⇒
∫
I
f(t) =
∫
I
h(t)⇒ fRh
Entonces, R es una relación de equivalencia en el conjunto RI . Su conjunto cociente es RI/R =
{[f ], [g], ...} siendo cada clase el conjunto de funciones cuya integral vale lo mismo en el intervalo.
J) R es una relación de equivalencia en el conjunto Z, su prueba es similar a la del ítem A), duplicando
cada paso para (mod m). Su conjunto cociente es Z/R = {[1], [2], ..., [mcm(n,m)]}.
Ejercicio 48.
Los elementos de la clase de equivalencia [α] son de la forma α + mk (con k ∈ Z), por lo que, para un
elemento genérico de la clase, si fuera una solución debería darse que:
a(α+mk)− b = mk′ (con k′ ∈ Z)⇔
⇔ aα− b+ amk = mk′ ⇔
⇔ aα− b = mk′ − amk ⇔
⇔ aα− b = m(k′ − ak)
Lo cual se sabe que es verdad porque α es una solución. �
6x = 12 (mod 9)
Se puede reducir a módulo 9.
6x = 3 (mod 9)
3 soluciones, mcd(6, 9) = 3, que divide a 3.
2x = 1 (mod 3)⇒ x0 = 2, x1 = x0 + 1
9
3
= 5, x2 = x0 + 2
9
3
= 8
12x = 24 (mod 18)
Se puede reducir a módulo 18.
12x = 6 (mod 18)
6 soluciones, mcd(12, 18) = 6, que divide a 6.
2x = 1 (mod 3)⇒
⇒ x0 = 2, x1 = x0+1
18
6
= 5, x2 = x0+2
18
3
= 8, x3 = x0+3
18
6
= 11, x4 = x0+4
18
3
= 14, x5 = x0+5
18
6
= 17
Entonces, X = [2] + [5] + [8], siendo estas clases de congruencia en Z9.
49
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
Ejercicio 49.
La relación R, es reflexiva, porque cada ai está conectado consigo mismo a través del camino nulo. También
es simétrica, ya que por definición, ai se relaciona con aj sii hay camino de ai hasta aj y de aj hasta ai, por
lo que se pueden invertir. Y a su vez es transitiva, puesto que si hay un camino de ai hasta aj y de aj hasta
ai, y hay un camino de aj hasta ah y de aj hasta ah, se puede construir un camino de ai hasta ah y de ah
hasta ai, porque se unen los caminos desde y hasta aj . Al cumplir las tres propiedades, se puede garantizar
que R es de equivalencia.
V (G)/R = {[a1], [a3], [a6]}, con
• [a1] = {a1, a2, a4, a5}
• [a3] = {a3, a10}
• [a6] = {a6, a7, a8, a9, a11, a12}
[a2]X = ([a6] + [a9])X
[a1]X = [a6]X
X ⊂ [a1]′[a6]′
X ⊂ [a3]
S = P([a3])
a12a11a10
a9a8
a7a6a5
a4
a3
a2 a1
Se puede suprimir cualquier arista y la relación seguirá siendo de equivalencia, ya que esta lo es por definición,
no por el digrafo en sí. Incluso, si se quita alguna de las coloreadas en rojo, no cambiará absolutamente
nada, y si se quita alguna de las otras, pueden cambiar las clases de equivalencia. Por ejemplo, si se suprime
la que une a a11 con a12:
a12a11a10
a9a8
a7a6a5
a4
a3
a2 a1
50
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
Ejercicio 50.
M1: Observando este autómata finito determinista, lo primero que se puede ver es que para que una palabra
sea reconocida, una vez que llegó al estado de aceptación q1, no debe avanzar a otro estado ya que
nunca podrá volver a un estado de aceptación. Como el estado inicial, con la letra a, lleva nuevamente
al estado inicial, esta puede repetirse cualquiera cantidad de veces en el inicio de palabra (o no estar),
luego, debe estar seguida por una única b (que lleva a q1), y terminar allí.
q0 q1 q2
a q0 q2 q2
b q1 q2 q2
L(M1) = {x ∈ Σ?: x = anb, n ∈ N0}
E1 = a
?b
M2: En este caso lo que ocurre con el autómata también puede observarse a simple vista, pero es un poco
más complejo que en el anterior, por lo que es una buena idea linealizarlo y utilizar el método de
eliminación de estados para encontrar una expresión regular.
q2q3q1q0in
a
b
a
b
a
b
a
b
q2q1q0in
a b
a
b
q2q0in
ab
a
b
q0 q1 q2 q3
a q1 q3 q2 q3
b q3 q2 q2 q3
L(M2) = {x ∈ Σ? : x = abw,w ∈ Σ?}
E2 = ab(a+ b)
∗
51
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
M3: Aunque a simple vista pueda no parecerlo, el comportamiento de este autómata es bastante sencillo,
b siempre lleva a q0, y a siempre acerca al estado de aceptación q2. Las palabras reconocidas pueden
empezar de cualquier forma, siempre y cuando tengan al menos dos a’s al final para ir de q0 a q1 y de
q1 a q2.
q0 q1 q2
a q1 q2 q2
b q0 q0 q0
L(M3) = {x ∈ Σ? : x = waa,w ∈ Σ?}
E3 = (a+ b)
?aa
M4: Se linealiza y se utiliza el método de eliminación de estados.
q2q3q1q0in
a
b
a
b a
b
a
b
q2q1q0in
a
a
b a
b
q2q0in
ab?a
a
bb?a
q0 q1 q2 q3
a q1 q2 q2 q3
b q3 q1 q1 q3
L(M4) = {x ∈ Σ? : x = awa,w ∈ Σ?}
E4 = ab
?a(a+ bb?a)? = a(a+ b)?a
M5: Este es otro autómata que sigue un comportamiento bastante simple. Primero, se puede ver que como
en casos anteriores, para que una palabra sea reconocida nunca debe llevar al autómata al estado q3, ya
que no se puede salir del mismo, entonces la primera letra debe ser una a. Luego, los estados q1 y q2 se
comportan de forma muy similar a q4 y q5, necesitan una a para acercarse a un estado de aceptación.
q0 q1 q2 q3 q4 q5
a q1 q2 q4 q3 q5 q5
b q3 q1 q1 q3 q4 q4
L(M5) = {x ∈ Σ? : x = avaawa, v, w ∈ Σ?}
E5 = a(a+ b)
?aa(a+ b)?a
52
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
M6: Este autómata es bastante similar a M3, con la diferencia de que el rol de la segunda a lo cumple una
b, por lo que para ser reconocida, una palabra simplemente debe terminar con ab. Ya que la letra a
siempre lleva a q1, que es el único estado que puede llegar a uno de aceptación, y lo hace con b.
q0 q1 q2
a q1 q1 q1
b q0 q2 q0
L(M6) = {x ∈ Σ? : x = wab,w ∈ Σ?}
E6 = (a+ b)
?ab
M7: Observado este autómata, queda claro que una vez que llegue a su estado de aceptación q1, no debe
haber nuevas b’s para que una palabra sea reconocida, ya que llevan a q2, estado que nunca llevará a
un estado de aceptación nuevamente. Estas palabras solo pueden contener una b (que lleva a q1), y
pueden tener tantas a’s como se quiera (o ninguna), antes y después de de esta b.
q0 q1 q2
a q0 q1 q2
b q1 q2 q2
L(M7) = {x ∈ Σ? : x = amban,m, n ∈ N0}
E7 = a
?ba?
M8: En este caso, las a’s mantienen el estado actual, y las b’ llevan de q0 a q1, de q1 a q2 y de q2 a q0,
haciendo una especie de circulo. Para una palabra reconocida, siendo q0 el único estado de aceptación
del autómata, es necesario que la cantidad de b’s en la palabra sea un múltiplo de 3, así recorre el
circulo entero y vuelve a q0, como las a’s no cambian el estado, puede tenerlas en cualquier lugar.
q0 q1 q2
a q0 q1 q2
b q1 q2 q0
L(M8) = {x ∈ Σ? : |x|b = 0 (mod 3)}
E8 = a
?(a?ba?ba?ba?)?
M9: Es idéntico a M3.
M10: Este autómata tiene dos estados de aceptación, q3 y q4, si la primera letra de una palabra reconocida
es a, el estado final deberá ser q4, si es b, q3. Por como está estructurado, la primera letra deberá
aparecer dos veces para llegar al estado de aceptación, y después cualquier cantidad de veces porque
se quedará en dicho estado. La otra letra no puede aparecer nunca.
q0 q1 q2 q3 q4 q5
a q2 q5 q4 q5 q4 q5
b q1 q3 q5 q3 q5 q5
L(M10) = {x ∈ Σ? : x = cccn, c ∈ Σ, n ∈ N0}
E10 = aaa
? + bbb?
M11: Aquí se repite el mismo esquema circular que en M8, con la diferencia de que hay dos estados de
aceptación válidos, y son necesarias dos b’s para llegar del uno al otro, y como las a’s no modifican el
estado actual, solamente es necesario que la cantidad de b’s sea un múltiplo de 2.
q0 q1 q2 q3
a q0 q1 q2 q3
b q1 q2 q3 q0
L(M11) = {x ∈ Σ? : |x|b = 0 (mod 2)}
E11 = a
?(a?ba?ba?)?
53
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
Ejercicio 51.
M1: L(M1) = {x ∈ Σ? : x = ubbb, u ∈ Σ?}
q0in q1 q2 q3
a
b
a
b
a
b
a
b
M2: L(M2) = {x ∈ Σ? : x = abu, u ∈ Σ?}
q0in
q1
q2 q3
a
b
a
b a
b
a
b
M3: L(M3) = {x ∈ Σ? : x = uba, u ∈ Σ?}
q0in q1 q2
a
b
a
b
a
b
M4: L(M4) = {x ∈ Σ? : |x|b = 2}
q0in q1 q2 q3
a
b
a
b
a
b
a
b
54
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
M5: L(M5) = {x ∈ Σ? : x ∈ Σ? : x = uabav, u, v ∈ Σ?}
q0in q1 q2 q3
a
b a
b a
b
a
b
M6: E6 = a?b(a?b?)?
q0in q1
a
b
a
b
M7: E7 = a?(baaba?)?
q0in q1 q2 q3
q4
a
b a
b
a
b
a
b
a, b
M8: E8 = b(a+ b)?aa
q0in q1 q2 q3
q4
a
b
a
b
a
b
a
b
a
b
55
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
M9: L(M9) = {x ∈ Σ? : |x|b = 1 (mod 2)}
q0in q1
a
b
a
b
Ejercicio 52.
M1: • Clases 0-equivalentes: {q0, q2}, {q1, q3}
• Clases 1-equivalentes: {q0, q2}, {q1, q3}
• Clases ?-equivalentes: {q0, q2}, {q1, q3}
• q̄0 = [q0] = {q0, q2}
• Q̄ = Q/R? = {q̄0, q̄1}
• F̄ = F/R? = {q̄0}
q̄0 q̄1
a q̄0 q̄1
b q̄1 q̄0
q̄0in
q̄1
a
b
a
b
M2: • Clases 0-equivalentes: {q0, q1, q4}, {q2, q3}
• Clases 1-equivalentes: {q0}, {q1, q4}, {q2, q3}
• Clases 2-equivalentes: {q0}, {q1, q4}, {q2, q3}
• Clases ?-equivalentes: {q0}, {q1, q4}, {q2, q3}
• q̄0 = [q0] = {q0}
• Q̄ = Q/R? = {q̄0, q̄1, q̄2}
• F̄ = F/R? = {q̄2}
q̄0 q̄1 q̄2
a q̄0 q̄2 q̄2
b q̄1 q̄1 q̄1
q̄0in
q̄1 q̄2
a
b
a
b
a
b
56
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
M3: • Clases 0-equivalentes: {q0, q1}, {q2, q3}
• Clases 1-equivalentes: {q0}, {q1}, {q2, q3}
• Clases 2-equivalentes: {q0}, {q1}, {q2, q3}
• Clases ?-equivalentes: {q0}, {q1}, {q2, q3}
• q̄0 = [q0] = {q0}
• Q̄ = Q/R? = {q̄0, q̄1, q̄2}
• F̄ = F/R? = {q̄0, q̄1}
q̄0 q̄1 q̄2
a q̄0 q̄2 q̄1
b q̄1 q̄2 q̄0
q̄0in q̄1
q̄2
a
b
a, ba
b
M4: • Clases 0-equivalentes: {q0, q2, q3}, {q1}
• Clases 1-equivalentes: {q0, q3}, {q2}, {q1}
• Clases 2-equivalentes: {q0, q3}, {q2}, {q1}
• Clases ?-equivalentes: {q0, q3}, {q2}, {q1}
• q̄0 = [q0] = {q0, q3}
• Q̄ = Q/R? = {q̄0, q̄2, q̄1}
• F̄ = F/R? = {q̄0, q̄2}
q̄0 q̄1 q̄2
a q̄0 q̄2 q̄1
b q̄2 q̄0 q̄1
q̄0in q̄1
q̄2
a
b
a
b
a, b
M5: • Clases 0-equivalentes: {q0, q1, q3, q4}, {q2, q5}
• Clases 1-equivalentes: {q0, q3}, {q1, q4}, {q2, q5}
• Clases 2-equivalentes: {q0, q3}, {q1, q4}, {q2, q5}
• Clases ?-equivalentes: {q0, q3}, {q1, q4}, {q2, q5}
• q̄0 = [q0] = {q0, q3}
• Q̄ = Q/R? = {q̄0, q̄1, q̄2}
• F̄ = F/R? = {q̄2}
q̄0 q̄1 q̄2
a q̄0 q̄2 q̄2
b q̄1 q̄1 q̄0
q̄0in
q̄1 q̄2
a
b
a
b a
b
57
61.07 Matemática Discreta Joaquín Singer (josinger@fi.uba.ar) Trabajo Práctico 1
M6: • Clases 0-equivalentes: {q0, q1, q2}, {q3, q4, q5}
• Clases 1-equivalentes: {q0, q1, q2}, {q3, q5}, {q4}
• Clases 2-equivalentes: {q0, q2}, {q1}, {q3, q5}, {q4}
• Clases 3-equivalentes: {q0, q2}, {q1}, {q3, q5}, {q4}
• Clases ?-equivalentes: {q0, q2}, {q1}, {q3, q5}, {q4}
• q̄0 = [q0] = {q0, q2}
• Q̄ = Q/R? = {q̄0, q̄1, q̄3, q̄4}
• F̄ = F/R? = {q̄3, q̄4}
q̄0 q̄1 q̄3 q̄4
a q̄1 q̄0 q̄0 q̄3
b q̄3 q̄4 q̄4 q̄3
q̄0in
q̄1
q̄3
q̄4
a
b
a
b
a
ba, b
M7: • Clases 0-equivalentes: {q0, q1, q2}, {q3}
• Clases 1-equivalentes: {q0, q2}, {q1}, {q3}
• Clases 2-equivalentes: {q0, q2}, {q1}, {q3}
• Clases ?-equivalentes: {q0, q2}, {q1}, {q3}
• q̄0 = [q0] = {q0, q2}
• Q̄ = Q/R? = {q̄0, q̄1, q̄3}
• F̄ = F/R? = {q̄3}
q̄0 q̄1 q̄3
a q̄3 q̄1 q̄0
b q̄1 q̄0 q̄3
q̄0in
q̄1
q̄3
a
b
a
b
a
b
Ejercicio 53.
x011 = 011x
Para que se cumpla la igualdad, lo primero que se puede observar es que la palabra x debe, o bien ser λ, o
empezar con 011, por lo que es de la forma:
x = 011y (y ∈ Σ?)
Entonces,
011y011 = 011011y
Y como x también debe terminar con 011, esto se cumple sii:
x = y011
Entonces,
y011 = 011y
Lo que pone a y en la misma situación