Algebra booleana

Instituto Tecnológico de Orizaba

Materia:
Matemáticas Discretas

Maestro:

Alumno:
Raúl Martínez Luna

Trabajo:
Unidad V

Producto Cartesiano

Si A y B son dos conjuntos no vacíos, el conjunto producto o producto cartesiano
A x B se define como el conjunto de todos los pares ordenados (a,b) con a ∈ A y b ∈ B.
Así:

A x B = { (a,b) | a ∈ A y b ∈ B}

Por ejemplo: Sean A ={x,y,z} y B = {1,2}

entonces:
A x B = {(x,1), (x,2), (y,1), (y,2), (z,1),
(z,2)}

Los elementos de A x B pueden representarse convenientemente de forma tabular o usando el sistema cartesiano:

Para el ejemplo: A = {x,y,z} y B = {1,2}

A x B = {(x,1), (x,2), (y,1), (y,2), (z,1), (z,2)}

Y

B x A = {(1,x), (1,y), (1,z), (2,x), (2,y), (2,z)}

Por ejemplo:

Sea A = {a,b}

entonces:A x A = {(a,a), (a,b), (b,a), (b,b)}

El número de elementos del producto cartesiano de A x B es igual al número de elementos del conjunto A por el número de elementos del conjunto B.

Ejemplo: Una fabrica de memorias portátiles proporciona tres características para cada uno de los modelos que vende:

Megas: 256 (1), 512 (2), 1024 (3)
Tamaño: mini (m), estándar (e)
Color: blanco (b),gris (g), negro (n)

Una partición o conjunto cociente de un conjunto no vacío A es una colección ℘ de subconjuntos no vacíos de A tales que:

1. Cada elemento de A pertenece a uno de
los conjuntos en ℘.

2. Si A1 y A2 son elementos distintos de ℘,
entonces A1 ∩ A2 =/ O.

Relación binaria

Sean A y B dos conjuntos. Una relación (binaria) R
de A en B es un subconjunto de A × B. Si (x, y)2 R
diremos que x está relacionado con y por R. Note
que en la definición R es simplemente un
subconjunto de parejas ordenadas de A × B.
Notación Infija:

Muy frecuentemente usaremos
x R y

para indicar que:

(x, y) 2 R

Diagrama de Flechas de una Relación
Sean A = {a, b, c}, B = {1, 2, 3} y R la relación de A
en B:
R = {(a, 1), (b, 2), (b, 3), (c, 1)}
El diagrama de fechas de Res:

Un nodo para cada elemento de A y de B. Una flecha de a a b si la pareja (a, b) está en R.

Representación Matricial

Sean A = {a1, a2, . . . , an} y B = {b1, b2, . . . , bm} conjuntos y R una relación de A en B. La representación matricial de R consiste de una matriz n × m (observe que A tiene n elementos y B tiene m) de ceros y unos. Habrá un 1 en la posición (i, j) si y sólo si lapareja (ai, bj) está en R, cero en caso contrario. La matriz se conoce como matriz de adyacencia.

Ejemplo:
Si A = {a, b, c} y B = {1, 2, 3} y si se mantiene el orden mostrado en
ambos conjuntos, identifique en orden cada relación:
a) {(c, 2) , (a, 1) , (a, 2) , (b, 2) , (c, 3)}
b) {(b, 1) , (a, 1) , (c, 3) , (b, 3) , (b, 2)}
c) {(a, 1) , (b, 2) , (c, 3) , (b, 3) , (a, 2)}
Con su matriz deadyacencia:

Solución
a) con 1), b) con 2), y c) con 3)

Propiedades de las relaciones.

Las relaciones se pueden clasificar de acuerdo al tipo de asociación que hay en sus elementos como: uno-a-uno 1–1, uno-a-mucho 1-M, muchos-a-uno M-1 o muchos-a-muchos M-M.
Recordemos que una relación es un conjunto de pares ordenados. Ver sección 2. Relaciones Introduccion.
‘Definición:’ Una relación Rde A a B es:
Muchos-a-uno, M-1 .
si existen dos pares con el mismo segundo elemento, esto es 
existen (x,y), (z,y) distintas en la relación, con símbolos 
(∃ x ∈ A)(∃ y ∈
B)(∃ z ∈ A) ((x,y) ∈ R ^ (z,y) ∈ R ^ x ≠ z)
Uno-a-muchos ‘1-M’ .
si existen dos pares con el mismo primer elemento, esto es 
existen (x,y), (x,z) distintas en la relación, con símbolos 
(∃ x ∈ A)(∃ y ∈ B)(∃ z ∈ B) ((x,y)∈ R ^ (x,z) ∈ R ^ y ≠ z)
Muchos-a-muchos ‘M-M’ .
 si es muchos-a-uno y uno-a-muchos. \O sea que hay al menos dos pares con el mismo primer elemento y también hay dos pares con el mismo segundo elemento.\ O sea que cumple las dos definiciones anteriores.
Uno-a-uno ‘1–1′ .
 si no es muchos-a-uno ni uno-a-muchos, o sea que no hay dos pares con el mismo primer elemento y no hay dos pares con el...