TABLAS DE PERTENENCIA
Prof .Juan Cabral - UTU Maldonado
Una técnica para probar igualdades entre conjuntos es la
tabla de pertenencia. Se observa que para los conjuntos
A y B ⊆ U , un elemento x ∈ U cumple exactamente una de
la cuatro situaciones siguientes:
a) x ∉ A, x ∉ B; b) x ∉ A, x ∈ B; c) x ∈ A, x ∉ B;
d) x ∈ A, x ∈ B.
Asignando el valor de verdad 1 (verdadero) si x ∈ A y 0
(falso) si x ∉ A quedan determinadas cuatro regiones en el
Universal de acuerdo con la siguiente tabla:
REGIONES DEL UNIVERSAL
x A x B Región
0 0 (1)
0 1 (2)
1 0 (3)
1 1 (4)
A B
(1)
(3) (4) (2)
U
Prof .Juan Cabral - UTU Maldonado
¿Cuántas operaciones tenemos para dos conjuntos?
Como son dos conjuntos tenemos 4 entradas posibles por lo que la cantidad de operaciones que se pueden definir son:
24 = 16
La tabla siguiente nos muestra las 16 operaciones posibles
Prof .Juan Cabral - UTU Maldonado
Operaciones entre dos conjuntos:
A B 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
(A B)A BA B A B ABA-B B-A A B (A B)(B-A) )(A-B UA
A B
B
Conjunto vacíoIntersección
AB: Región (4)
Identidad
Conjunto A: Regiones (3) (4)
Unión AB : Regiones (2) (3) (4)Complemento de la Unión
Región (1)
Complemento de laIntersección
Regiones (1) (2) (3)
UniversalRegiones (1) (2) (3) (4)
Complemento
: Regiones (1) (2)A
A BA BA BA BA B
U
Prof .Juan Cabral - UTU Maldonado
(3) (4) (2)
(1)
Complemento de la Diferencia Simétrica
Regiones (1) (4)A B
Complemento de la Diferencia:
: Regiones (1) (2) (4)(A-B)
Diferencia Simétrica Regiones (2) (3)
DiferenciaA-B Región (3)
Complemento
: Regiones (1) (3)B
Diferencia
B-A Región (2)
Identidad
Conjunto B: Regiones (2) (4)
Complemento de la Diferencia:
: Regiones (1) (3) (4)(B-A)
R
E
G
I
O
N
1
2
3
4
Unión Intersección y Complemento
A B AB AB
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 1
A A
0 1
1 0
Prof .Juan Cabral - UTU Maldonado
Las tablas de pertenencia nos permiten verificar propiedades del álgebra de conjuntos:
Por ejemplo:
A (BC) = (AB) (AC)(Propiedad Distributiva de la intersección respecto de la unión)
Prof .Juan Cabral - UTU Maldonado
A (BC)
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
La tabla de pertenencia nos queda:
Se verifica la propiedad
(AB) (AC)
0 0 0 0
0 0 0 1
0 1 0 0
0 1 0 1
1 0 1 0
1 0 1 1
1 1 1 0
1 1 1 1
A (BC)
0 0 0 0
0 0 1 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 1 0
1 1 1 1
0
0
0
0
0
1
1
1
(AB) (AC)
0 0 0 0 0
0 0 0 0 1
0 0 1 0 0
0 0 1 0 1
1 0 0 1 0
1 0 0 1 1
1 1 1 1 0
1 1 1 1 1
(AB) (AC)
0 0 0 0 0 0
0 0 0 0 0 1
0 0 1 0 0 0
0 0 1 0 0 1
1 0 0 1 0 0
1 0 0 1 1 1
1 1 1 1 0 0
1 1 1 1 1 1
(AB) (AC)
0 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 1 0 0 0 0
0 0 1 0 0 0 1
1 0 0 0 1 0 0
1 0 0 1 1 1 1
1 1 1 1 1 0 0
1 1 1 1 1 1 1
?=
Prof .Juan Cabral - UTU Maldonado
Aplicación: Representación de conjuntos en un computador Existen varias formas de representar conjuntos en una computadora. Una
forma sería almacenar los elementos del conjunto de manera
desordenada.
Sin embargo si se hace de esta manera las operaciones para calcular la
unión, intersección o diferencia serían demasiado costos en tiempo y
recursos. Un método que simplificaría el cálculo es el siguiente:
Consideremos un conjunto (arbitrariamente ordenado)
U={1,2,3,4,5,6,7,8,9,10} y el conjunto A={ 1,3,5,6,7,9} incluido en él.
Utilizando el concepto de pertenencia se podría sustituir el conjunto A
por una cadena de bits de longitud igual al cardinal del Universal, de tal
manera que si el elemento pertenece al conjunto A lo indicamos con 1 y
si no pertenece con 0.
Así el conjunto A quedaría representado mediante la cadena de bits con
respecto al Universal: 10 1011 1010 al universal le correspondería 11
1111 1111 y al conjunto vacío la cadena 00 0000 0000.Prof .Juan Cabral - UTU Maldonado
En un computador, las operaciones con bits se corresponden con los
conectivos lógicos. Por ejemplo, los conectivos lógicos , ,son las operaciones AND, OR, XOR. Las operaciones están bien
definidas para cadenas de bits de la misma longitud, que usualmente, se
separan de a cuatro para “leerlas” mejor.
Sean las cadenas de bits 0100 1010 1110 y 1101 1010 0010 aplicando
las operaciones con bits AND, OR y XOR nos resulta:
0100 1010 1110 0100 1010 1110 0100 1010 1110
AND 1101 1010 0010 OR 1101 1010 0010 XOR 1101 1010 0010
0100 1010 0010 1101 1010 1110 1001 0000 1100
Operaciones con cadenas de bits:
Prof .Juan Cabral - UTU Maldonado
Operaciones entre conjuntos utilizando cadena de bits:
Volviendo al ejemplo anterior sean los conjuntos:
U={1,2,3,4,5,6,7,8,9,10} , A={ 1,3,5,6,7,9} y B{1,2,5,6,8,10}
Hallar mediante cadenas de bits: AB , AB, A, B, A-B y BA
Las cadenas que representan cada conjunto son:
U: 11 1111 1111 A: 10 1011 1010 B: 11 0011 0101
AB = (10 1011 1010 11 0011 0101) = 10 0011 0000
10 1011 1010AND 11 0011 0101 O sea que AB ={1,5,6} como era de esperarse.
10 0011 0000
AB= (10 1011 1010 11 0011 0101)= 11 1011 1111
10 1011 1010
OR 11 0011 0101 O sea que AB ={1,2,3,4,5,6,7,8,9,10}
11 1011 1111 Prof .Juan Cabral - UTU Maldonado
U={1,2,3,4,5,6,7,8,9,10} , A={ 1,3,5,6,7,9} y B{1,2,5,6,8,10}
Los complementos los obtenemos negando las cadenas de bits respectivas:
A = (10 1011 1010 ) = 01 0100 0101 O sea A ={2,4,8,10}
B =not (11 0011 0101) = 00 1100 1010 O sea B ={3,4,7,9}
A-B = (10 1011 1010 - 11 0011 0101) = 00 1000 1010
10 1011 1010
- 11 0011 0101 O sea que A-B ={3,7,9}
00 1000 1010
AB= (10 1011 1010 ∨ 11 0011 0101) = 01 1000 1111
10 1011 1010XOR 11 0011 0101 O sea que AB ={2,3,7,8,9,10}
01 1000 1111
Prof .Juan Cabral - UTU Maldonado