25

TEORÍA DE CONJUNTOS

CAPÍTULO II TEORÍA DE CONJUNTOS

2.2 INTRODUCCIÓN Denotaremos los conjuntos con letras mayúsculas y sus elementos con letras minúsculas, si un elemento p pertenece a un conjunto A escribiremos p A en caso de que el elemento no pertenezca al conjunto se escribirá p A . Un conjunto es finito si su número de elementos es finito e infinito si tiene infinitos elementos. Para especificar un conjunto dado se puede usar las siguientes notaciones:

A {1,2,3,4,5,6,7,8,9,0, } A {x : x es un digito} Las dos notaciones representan el mismo conjunto, la primera se denomina expresión por extensión de un conjunto, la segunda por comprensión. Dos conjuntos A y B son iguales si tienen los mismos elementos. Si A {2,3} y B {x / x 2 5 x 6 0} Entonces A = B ya que las raíces de la ecuación del conjunto B son 2 y 3 Un conjunto B es subconjunto de A si todos los elementos del conjunto B pertenecen al conjunto A, esto se escribe como B A En cualquier aplicación de la teoría de conjuntos, todos los conjuntos que se investigan son subconjuntos de un conjunto dado al que se denomina conjunto universal y se representa por U. El conjunto que no tiene elementos se denomina conjunto vacío y se representa por Ø.

26

ÁLGEBRA I

2.3 UNIÓN La unión de conjuntos está definida como:

A  B {x : x

A o

x

A

B} B

A B

2.4 INTERSECCIÓN La intersección de conjuntos está dada por:

A B

{x : x

A

y

x

B}

A B BB

A A

A∩B

2.5 COMPLEMENTO RELATIVO O DIFERENCIA El complemento relativo o diferencia de conjuntos está dado por:

A\ B

A B {x : x

A

y

x

B}

27

TEORÍA DE CONJUNTOS

A

B

A\ B

A B

2.6 DIFERENCIA SIMÉTRICA La diferencia simétrica de los conjuntos A y B viene dada por:

A

B

( A B)  ( B

A

A)

B

A

B

2.7 COMPLEMENTO ABSOLUTO El complemento de un conjunto está dado por los elementos que se encuentran fuera del conjunto, se define como:

AC

x:x

A

28

ÁLGEBRA I

AC A A

2.8 LEYES DEL ÁLGEBRA DE CONJUNTOS Los conjuntos satisfacen las siguientes leyes 2.8.1 LEYES DE IDEMPOTENCIA

A A

A ;

A A

A

2.8.2 LEYES ASOCIATIVAS

A  (B  C)

( A  B)  C ;

A  (B  C)

( A  B)  C

2.8.3 LEYES CONMUTATIVAS

A B

BA ;

A B

B A

2.8.4 LEYES DISTRIBUTIVAS

A  (B  C) A  (B  C)

( A  B)  ( A  C ) ( A  B)  ( A  C )

2.8.5 LEYES DE IDENTIDAD

A A U

A ; A U U ; A

A

2.8.6 LEYES DE COMPLEMENTO

A  AC

U

; A  AC

( AC ) C

A ; UC

;

C

U

29

TEORÍA DE CONJUNTOS

2.8.7 LEYES DE MORGAN

( A  B)C

AC  B C

; ( A  B)C

AC  B C

2.9 DIAGRAMAS DE VENN Es una representación gráfica en la cual se sombrean las áreas que corresponden a las operaciones que se pueden realizar entre conjuntos Ejemplo 1 En los siguientes diagramas de Venn sombrear el área que corresponde a) AC  ( B  C C ) A

A

B

B

C V

A

C VC

A

B

C V

(B  C C )

A

B

C V

AC  ( B  C C )

30

ÁLGEBRA I

b) AC  ( B  C C ) A

B

C

A

B

C

B

C

AC A

B

C

(B  C C )

A

AC  ( B  C C )

Ejemplo 2 Sombrear el área que corresponde a la siguiente operación a)

A DC

BC C

A

B

A

B

C

D

C

D

A DC

31

TEORÍA DE CONJUNTOS

A

B

A

B

C

D

C

D

A DC

BC C

b)

A DC

BC C

BC C B

B

A

A

C

D

D

C

A DC

32

ÁLGEBRA I

B

B

A

A

D

C

D

C

A DC

BC C

BC C

2.10 CONJUNTOS PRODUCTO 2.10.1 PARES ORDENADOS (a,b) Un par ordenado (a,b) consta de dos elementos denominados primer y segundo elemento. Dos pares ordenados (a,b) (c,d) son iguales si y sólo si a=c y b=d. Los puntos del plano cartesiano son pares ordenados de números reales. 2.10.2 CONJUNTOS PRODUCTO El conjunto producto o producto cartesiano A × B consta de todos los pares ordenados (a,b) donde a Є A y b Є B

A B {(a, b) : a

A, b

B}

Ejemplo 3 Sean A={ a,b,c } y B={ x,y } Entonces el conjunto producto será:

A B {(a, x), (a, y), (b, x),b, y), (c, x), (c, y)}

33

TEORÍA DE CONJUNTOS

2.10.3 CONJUNTOS PRODUCTO EN GENERAL El producto de tres conjuntos A × B × C estará formado por triplas ordenadas, definiéndose el triple producto de la siguiente manera:

A B C {(a, b, c) : a

A, b B, c C}

El producto cartesiano de n conjuntos estará formado por n-uplas ordenadas de la forma:

A B C ..........N {(a, b, c........n) : a

A, b B, c C,.....n N}

Ejemplo 4 Sean los conjuntos A = { 1,2,3 }; B = { a,b }; C={ x,y,z } Hallar a) A x B x C

b) C x A x B

c) B x C x A

La solución en ambos casos estará formada por triplas ordenadas de la forma. a) A x B x C = {(1,a,x)(1,a,y)(1,a,z)(1,b,x)(1,b,y)(1,b,z) (2,a,x)(2,a,y(2,a,z)(2,b,x)(2,b,y)(2,b,z) (3,a,x)(3,a,y)(3,a,z)(3,b,x)(3,b,y)(3,bz)} b) C x A x B ={(x,1,a)(x,1,b)(x,2,a)(x,2,b)(x,3,a)(x,3,b) (y,1,a)(y,1,b)(y,2,a)(y,2,b)(y,3,a)(y,3,b) (z,1,a)(z,1,b)(z,2,a)(z,2,b)(z,3,a)(z,3,b)} Puede resultar conveniente construir un diagrama de árbol como el siguiente para evitar cualquier confusión en la formación de las triplas ordenadas c) B x C x A

34

ÁLGEBRA I

Para hallar este conjunto producto, se pueden escribir en una primera columna los elementos del conjunto B, a continuación de cada uno de ellos los elementos del conjunto C y finalmente al lado de cada uno de estos últimos, los elementos del conjunto A

a 1 b a 2 b a 3 b

x y z x y z x y z x y z x y z x y z

Las triplas ordenadas se pueden formar siguiendo cada una de las direcciones de las líneas trazadas B x C x A = {(1,a,x)(1,a,y)(1,a,z)(1,b,x)(1,b,y)(1,b,z) (2,a,x)(2,a,y)(2,a,z)(2,b,x)(2,b.y)(2,b,z) (3,a,x)(3,a,y)(3,a,z)(3,b,x)(3,b,y)(3,b,z)} 2.10.4 CONJUNTOS DE VERDAD DE PROPOSICIONES El conjunto de verdad de una proposición P, denotado por τ(P) consta de n-uplas ordenadas con los valores de verdad de cada uno de los enunciados para los cuales la proposición P es verdadera.

35

TEORÍA DE CONJUNTOS

Ejemplo 5 Encuentre el conjunto de verdad de la siguiente proposición:

P V V F F

q V F V F

[( p

q)

~ q]

[(p V V F F

↔ V F V V

q) V F V F

→ F V F V

~q] F V F V

El conjunto de verdad estará formado por duplas ordenadas de la forma: τ(P)={VF, FF} Ejemplo 6 Encuentre el conjunto de verdad de la siguiente proposición:

[( p

q)

(~ r

s)] (~ q r )

La tabla de verdad es: p

q

r

s

V V V V V V V V F F F F F F F F

V V V V F F F F V V V V F F F F

V V F F V V F F V V F F V V F F

V F V F V F V F V F V F V F V F

[(p V V V V V V V V F F F F F F F F

→ V V V V F F F F V V V V V V V V

q) V V V V F F F F V V V V F F F F

↔ F F V F V V F V F F V F F F V F

(~r F F V V F F V V F F V V F F V V

^ F F V F F F V F F F V F F F V F

s)] V F V F V F V F V F V F V F V F

V V V V F F F V F V V V F V V F V

(~q F F F F V V V V F F F F V V V V

V V V F F V V V V V V F F V V V V

r) V V F F V V F F V V F F V V F F

36

ÁLGEBRA I

El conjunto de verdad de esta proposición esta formado por 4-uplas ordenadas para los cuales la proposición es verdadera τ(P)={VVVV, VVVF, VVFV, VFFV, FVVV, FVVF, FVFV, FFVV, FFVF, FFFF} Las n-uplas se han escrito sin la separación de comas y sin los paréntesis para simplificar su representación. 2.11 ÁLGEBRA DE BOOLE Se denomina así en honor a George Boole, (2 de noviembre de 1815 al 8 de diciembre de 1864), matemático inglés que fue el primero en definirla como parte de un sistema lógico a mediados del siglo XIX. Específicamente, el álgebra de Boole fue un intento de utilizar las técnicas algebraicas para tratar expresiones de la lógica proposicional. En la actualidad, el álgebra de Boole se aplica de forma generalizada en el ámbito del diseño electrónico. Claude Shannon fue el primero en aplicarla en el diseño de circuitos de conmutación eléctrica biestables, en 1938. Un álgebra booliana es un conjunto B de elementos a,b,…. Dotado de dos operaciones binarias llamadas suma y producto, que se denotan respectivamente por + y * tal que:1

2.11.1 LEY DE CLAUSURA Para cualesquiera a, b ε B, la suma a + b y el producto a * b existen y son elementos únicos de B. 2.11.2 LEY CONMUTATIVA a+b=b+a

;

a*b= b*a

2.11.3 LEYES ASOCIATIVAS (a + b) + c = a + (b + c)

;

(a * b) * c = a * (b * c)

1 Seymour Lipschutz. TEORIA DE CONJUNTOS, Edit. Schaum 1969 Pag. 216

37

TEORÍA DE CONJUNTOS

2.11.4 LEYES DISTRIBUTIVAS a * (b + c) = (a * b) + (a * c) ;

a + (b * c) = (a + b) * (a + c)

2.11.5 ELEMENTOS NEUTROS Existen elementos, neutro aditivo 0 y neutro multiplicativo U tales que, para todo a ε B a+0=a ; a*U=a

2.11.6 COMPLEMENTO Para todo a ε B existe un a’ε B llamado complemento de a tal que: a + a’ = U ;

a * a’ = 0

Como veremos las operaciones se realizarán mediante relaciones lógicas, lo que en el álgebra convencional son las sumas y multiplicaciones. Las variables con las que opera son las binarias 1 y 0 (verdadero o falso). Los signos 1 y 0 no expresan cantidades, sino estados de las variables. Podemos decir, que el sistema de numeración binario y el álgebra de Boole constituyen la base matemática para el diseño y construcción de sistemas digitales. Ejemplo 7 Sean B = {1, 0} y sean las dos operaciones + y * definidas como sigue: + 1 0 1 1 1 0 1 0

* 1 0 1 1 0 0 0 0

Entonces la terna ( B, +, * ) es un álgebra booliana. Ejemplo 8 Sea A una familia de conjuntos cerrada respecto a las operaciones de

38

ÁLGEBRA I

unión, intersección y complemento, Entonces (A, ∩, U ) es un álgebra booliana, el conjunto universal es el conjunto unidad e el conjunto vacío es el elemento cero. Ejemplo 9 Sea F el conjunto de las proposiciones generadas por las variables p, q, r, … Entonces ( F, V, Λ ) es un álgebra booliana.

2.12 DUALIDAD DE UN ÁLGEBRA BOOLIANA El dual de un enunciado en un álgebra booliana ( B, +, * ) es el anunciado que resulta intercambiando + y * y los elementos neutros U y 0 en el anunciado original; El dual de: ( U + a ) * ( b + 0 )= b Es:

(0*a)+(b*U)=b

El dual de cada axioma de un álgebra booliana es también un axioma. El dual de un teorema de un álgebra booliana es también un teorema. 2.13 LEYES FUNDAMENTALES 2.13.1 LEYES DE IDEMPOTENCIA a+a=a a+U=U

; ;

a*a=a a*0=0

2.13.2 LEYES DE INVOLUCIÓN (a’)’ = a

;

U’ = 0

;

0’=U

2.13. 3 LEYES DE DE MORGAN ( a + b )’ = a’ * b’

;

( a * b )’ = a’ + b’

2.14 ORDEN DE UN ÁLGEBRA BOOLIANA TEOREMA

39

TEORÍA DE CONJUNTOS

Sea a, b ε B un álgebra booliana. Entonces las siguientes condiciones son equivalentes: a * b’ = 0

a’ + b = U

a+b=b

a*b=a

Demostración de a * b’ = 0

implica

a+b=b

( a + b ) = ( a + b ) * U = ( a + b ) * ( b + b’ ) = ( b + a ) * ( b + b’ ) = ( b + b ) * ( a + b’ )= b * ( a + b’ ) = ( b * a ) + ( b * b’ )= b + 0 = b Demostración de a + b = b implica

a’ + b = U

a’ + b = a’ + ( a + b )= ( a’ + a )+ b = U + b = U Demostración de a’ + b = U implica a * b’ = 0 a’ + b = U implica ( a’ + b )’ = U’ implica a’’ * b’ = U’ implica a * b’ = 0 Sea a, b ε B un álgebra booliana. Se dice que a es anterior a b denotado por a ≤ b si es válida una de las propiedades del teorema anterior. Ejemplo 10 Considerando un álgebra booliana de conjuntos ( A, ∩, U ) , entonces A es anterior a B significa que A B verificándose que:

A B' A B B

; A' B U ; A B A

40

ÁLGEBRA I

A B

El diagrama de Venn permite apreciar claramente las identidades descritas.