De acuerdo, resolvamos cada una de las relaciones dadas:
b) R1 = {(x, y) ∈ ℕ × ℕ: 2x + y = 9}
1. Expresión por extensión:
R1 = {(0, 9), (1, 7), (2, 5), (3, 3), (4, 1)}
2. Dominio y recorrido:
Dom(R1) = {0, 1, 2, 3, 4}
Rec(R1) = {1, 3, 5, 7, 9}
3. Matriz booleana asociada:
0∧0∧0∧0∧1 ¿
0∧0∧0∧1∧0 ¿
0∧0∧1∧0∧0 ¿
0∧1∧0∧0∧0 ¿
1∧0∧0∧0∧0
Ahora, construimos la matriz booleana M(R1) de 5x5, donde las filas
recorrido, en el orden establecido. Si (x, y) ∈ R1, entonces M(R1)_xy = 1, de
representan los elementos del dominio y las columnas los elementos del
lo contrario, M(R1)_xy = 0.
M(R1) =
0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 1 & 0\\
0 & 0 & 1 & 0 & 0\\
0 & 1 & 0 & 0 & 0\\
1&0&0&0&0
4. Relación inversa y su matriz booleana:
R1^(-1) = {(y, x) ∈ N x N: (x, y) ∈ R1} = {(9, 0), (7, 1), (5, 2), (3, 3), (1, 4)}
La matriz booleana de la relación inversa, M(R1^(-1)), se obtiene
transponiendo M(R1):
M(R1^{-1}) =
0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 1 & 0\\
0 & 0 & 1 & 0 & 0\\
0 & 1 & 0 & 0 & 0\\
1&0&0&0&0
d) R2 = {(a, b) ∈ A x A: ab > 0}, A = {-2, -1, 0, 1, 2, 3}
1. Expresión por extensión:
R2 = {(-2, -2), (-2, -1), (-1, -2), (-1, -1), (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2,
3), (3, 1), (3, 2), (3, 3)}
2. Dominio y recorrido:
Dom(R2) = {-2, -1, 1, 2, 3}
Rec(R2) = {-2, -1, 1, 2, 3}
3. Matriz booleana asociada:
1∧1∧0∧0∧0∧0 ¿
1∧1∧0∧0∧0∧0 ¿
0∧0∧0∧0∧0∧0 ¿
0∧0∧0∧1∧1∧1 ¿
0∧0∧0∧1∧1∧1 ¿
0∧0∧0∧1∧1∧1
4. Relación inversa (R2^(-1)):
R2^(-1) = {(-2, -2), (-1, -2), (-2, -1), (-1, -1), (1, 1), (2, 1), (3, 1), (1, 2), (2, 2),
Para determinar la relación que representa la matriz booleana dada,
seguiremos estos pasos:
Paso 1: Asignar a cada fila y columna un elemento del conjunto {a, b, c, d,
e} respetando el orden.
abcde
a11000
b00110
c00011
d01100
e10000
Paso 2: Identificar las parejas ordenadas (x, y) donde x corresponde a la fila
e y a la columna, y el valor en la posición (x, y) es 1.
Las parejas ordenadas que cumplen esta condición son:
(a, a), (a, b), (b, c), (b, d), (c, d), (c, e), (d, b), (d, c), (e, a)
Paso 3: Escribir la relación en forma de conjunto utilizando las parejas
ordenadas identificadas.
R = {(a, a), (a, b), (b, c), (b, d), (c, d), (c, e), (d, b), (d, c), (e, a)}
Por lo tanto, la relación R representada por la matriz booleana dada es:
R = {(a, a), (a, b), (b, c), (b, d), (c, d), (c, e), (d, b), (d, c), (e, a)} en el
conjunto {a, b, c, d, e}.
Paso 1: Entender la relación S. La relación S se cumple si y solo si la
intersección de los conjuntos A y B es diferente del conjunto vacío. En otras
palabras, A y B están relacionados por S si tienen al menos un elemento en
común.
Ahora, respondamos cada pregunta:
a) ¿Es {a}S{c}? Paso 2a: Verificar si {a} y {c} tienen elementos en común.
{a} ∩ {c} = Ø Como la intersección de {a} y {c} es el conjunto vacío, {a}
no está relacionado con {c} por S. Por lo tanto, {a}S{c} es falso.
b) ¿Es {a,b}S{a,b,c}? Paso 2b: Verificar si {a,b} y {a,b,c} tienen elementos
en común. {a,b} ∩ {a,b,c} = {a,b} Como la intersección de {a,b} y {a,b,c}
no es el conjunto vacío, {a,b} está relacionado con {a,b,c} por S. Por lo
tanto, {a,b}S{a,b,c} es verdadero.
c) ¿Es {a,b}S{b,c}? Paso 2c: Verificar si {a,b} y {b,c} tienen elementos en
común. {a,b} ∩ {b,c} = {b} Como la intersección de {a,b} y {b,c} no es el
conjunto vacío, {a,b} está relacionado con {b,c} por S. Por lo tanto,
{a,b}S{b,c} es verdadero.
d) ¿Hay algún elemento de P(X) relacionado con Ø? Paso 2d: Verificar si
algún subconjunto de X tiene elementos en común con el conjunto vacío.
Para cualquier subconjunto A de X, A ∩ Ø = Ø Como la intersección de
cualquier subconjunto de X con el conjunto vacío siempre es el conjunto
vacío, ningún elemento de P(X) está relacionado con Ø por S.
Dadas dos cadenas c y d pertenecientes a E, denotemos por H(c, d) a la
distancia de Hamming entre c y d, que es la cantidad de dígitos que se
deben cambiar en la cadena c para que quede idéntica a d. Definimos la
relación Z en E de la siguiente manera:
cZd <-> H(c,d) es par
Para cada par de cadenas, calcularemos la distancia de Hamming y
determinaremos si cZd es verdadero o falso.
a) ¿Es 0121 Z 2200? Paso 1a: Calcular H(0121, 2200). 0121 → 2200: Se
deben cambiar 3 dígitos. H(0121, 2200) = 3 Paso 2a: Verificar si H(0121,
2200) es par. Como 3 es impar, 0121 no está relacionado con 2200 por Z.
Por lo tanto, 0121 Z 2200 es falso.
b) ¿Es 2212 Z 2121? Paso 1b: Calcular H(2212, 2121). 2212 → 2121: Se
deben cambiar 2 dígitos. H(2212, 2121) = 2 Paso 2b: Verificar si H(2212,
2121) es par. Como 2 es par, 2212 está relacionado con 2121 por Z. Por lo
tanto, 2212 Z 2121 es verdadero.
c) ¿Es 1011 Z 2101? Paso 1c: Calcular H(1011, 2101). 1011 → 2101: Se
deben cambiar 2 dígitos. H(1011, 2101) = 2 Paso 2c: Verificar si H(1011,
2101) es par. Como 2 es par, 1011 está relacionado con 2101 por Z. Por lo
tanto, 1011 Z 2101 es verdadero.
d) ¿Es 1220 Z 2111? Paso 1d: Calcular H(1220, 2111). 1220 → 2111: Se
deben cambiar 3 dígitos. H(1220, 2111) = 3 Paso 2d: Verificar si H(1220,
2111) es par. Como 3 es impar, 1220 no está relacionado con 2111 por Z.
Por lo tanto, 1220 Z 2111 es falso.
e) ¿Es 2212 Z 2111? Paso 1e: Calcular H(2212, 2111). 2212 → 2111: Se
debe cambiar 1 dígito. H(2212, 2111) = 1 Paso 2e: Verificar si H(2212, 2111)
es par. Como 1 es impar, 2212 no está relacionado con 2111 por Z. Por lo
tanto, 2212 Z 2111 es falso.
f) ¿Es 1221 Z 1121? Paso 1f: Calcular H(1221, 1121). 1221 → 1121: Se debe
cambiar 1 dígito. H(1221, 1121) = 1 Paso 2f: Verificar si H(1221, 1121) es
par. Como 1 es impar, 1221 no está relacionado con 1121 por Z. Por lo
tanto, 1221 Z 1121 es falso.
a) Rec(R∩S) ⊆ RecR ∩ RecS
Paso 1: Tomemos un elemento arbitrario (x, x) ∈ Rec(R∩S). Paso 2: Por
definición de Rec(R∩S), (x, x) ∈ (R∩S). Paso 3: Por definición de intersección,
(x, x) ∈ R y (x, x) ∈ S. Paso 4: Por definición de RecR y RecS, (x, x) ∈ RecR y
(x, x) ∈ RecS. Paso 5: Por definición de intersección, (x, x) ∈ RecR ∩ RecS.
Por lo tanto, Rec(R∩S) ⊆ RecR ∩ RecS.
b) RecR - RecS ⊆ Rec(R-S)
Paso 1: Tomemos un elemento arbitrario (x, x) ∈ RecR - RecS. Paso 2: Por
definición de diferencia, (x, x) ∈ RecR y (x, x) ∉ RecS. Paso 3: Por definición
de RecR, (x, x) ∈ R. Paso 4: Como (x, x) ∉ RecS, entonces (x, x) ∉ S. Paso 5:
Por definición de diferencia, (x, x) ∈ R-S. Paso 6: Por definición de Rec(R-S),
(x, x) ∈ Rec(R-S). Por lo tanto, RecR - RecS ⊆ Rec(R-S).
c) (R∩S)^(-1) = R^(-1) ∩ S^(-1)
Paso 1: Tomemos un elemento arbitrario (y, x) ∈ (R∩S)^(-1). Paso 2: Por
definición de inversa, (x, y) ∈ (R∩S). Paso 3: Por definición de intersección,
(x, y) ∈ R y (x, y) ∈ S. Paso 4: Por definición de inversa, (y, x) ∈ R^(-1) y (y,
x) ∈ S^(-1). Paso 5: Por definición de intersección, (y, x) ∈ R^(-1) ∩ S^(-1).
Por lo tanto, (R∩S)^(-1) ⊆ R^(-1) ∩ S^(-1).
Ahora, tomemos un elemento arbitrario (y, x) ∈ R^(-1) ∩ S^(-1). Por un
razonamiento similar al anterior, podemos demostrar que (y, x) ∈ (R∩S)^(-
1). Por lo tanto, R^(-1) ∩ S^(-1) ⊆ (R∩S)^(-1).
Dado que hemos demostrado ambas inclusiones, concluimos que (R∩S)^(-1)
= R^(-1) ∩ S^(-1).
