Copyright HébergementWebs.com - License GPL

Matemáticas discretas - Conjuntos

Tutorial de matemáticas discretas   2020-11-18 03:15:52

Matematicas discretas - Conjuntos El matematico aleman G. Cantor introdujo el concepto de conjuntos. Habia definido un conjunto como una coleccion de objetos definidos y distinguibles seleccionados por medio de ciertas reglas o deiones. La teoria de conjuntos forma la base de varios otros campos de estudio, como la teoria del conteo, las relaciones, la teoria de grafos y las maquinas de estados finitos. En este capitulo, cubriremos diferentes aspectos de la Teoria de conjuntos . Conjunto - Definicion Un conjunto es una coleccion desordenada de diferentes elementos. Un conjunto se puede escribir explicitamente enumerando sus elementos utilizando corchetes de conjuntos. Si se cambia el orden de los elementos o si se repite un elemento de un conjunto, esto no modifica el conjunto. Algunos ejemplos de conjuntos Un conjunto de todos los enteros positivoss Un conjunto de todos los planetas del sistema solar Un conjunto de todos los estados de la India Un conjunto de todas las letras minusculas de el alfabeto Representacion de un conjunto Los conjuntos se pueden representar de dos formas: Lista o forma tabular Notacion del generador de juegos Lista o forma tabular El conjunto se representa mediante una lista todos los elementos que lo componen. Los elementos estan rodeados por llaves y separados por comas. Ejemplo 1 : conjunto de vocales en el alfabeto ingles, $ A = lbrace a, e, i, o, u rbrace $ Ejemplo 2 - Conjunto de numeros impares menores que 10, $ B = lbrace 1,3,5,7,9 rbrace $ Notacion del generador de juegos El conjunto se define especificando una propiedad que los elementos del conjunto tienen en comun. El conjunto se describe como $ A = lbrace x:p (x) rbrace $ Ejemplo 1 : el conjunto $ lbrace a, e, i, o, u rbrace $ s esta escrito - $ A = lbrace x: text {x es una vocal en el alfabeto ingles} rbrace $ Ejemplo 2 - L "set $ lbrace 1,3,5,7,9 rbrace $ esta escrito - $ B = lbrace x: 1 le x lt 10 y (x% 2) ne 0 rbrace $ Si un elemento x es miembro de cualquier conjunto S, se indica con $ x en S $ y si un elemento y no es miembro del conjunto "conjunto S, se denota por $ y no en S $. Ejemplo - Si $ S = lbrace1, 1.2, 1.7, 2 rbrace, 1 en S $ pero $ 1, 5 notin S $ Algunos conjuntos importantes N - el conjunto de todos los numeros naturales = $ lbrace1, 2, 3 , 4, ..... rbrace $ Z - el conjunto de todos los enteros = $ lbrace ....., -3, -2, - 1, 0, 1, 2, 3, ..... rbrace $ Z + - l "ensemblema de todos los enteros positivos Q - el conjunto de todos los numeros racionales R - l "conjunto de todos los numeros reales W - el conjunto de todos los enteros Cardinalidad de un conjunto Cardinalidad de un conjunto S, denotado por $ | S | $, es el numero de elementos del conjunto. El numero tambien se llama numero cardinal. Si un conjunto tiene un numero infinito de elementos, su cardinalidad es $ infty $. Ejemplo - $ | lbrace 1, 4, 3, 5 rbrace | = 4, | lbrace 1, 2, 3, 4, 5, puntos rbrace | = infty $ Si hay dos conjuntos X e Y, $ | X | = | Y | $ denota dos conjuntos X e Y que tienen la misma cardinalidad. Esto sucede cuando el numero de elementos en X es exactamente igual al numero de elementos en Y. En este caso, hay una funcion uno a uno "f " de X a Y. $ | X | el | Y | $ indica que la cardinalidad del enparece que X es menor o igual que la cardinalidad del conjunto Y. Esto sucede cuando el numero de elementos en X es menor o igual que el de Y. Aqui hay una funcion inyectiva "f " de X a Y. $ | X | lt | Y | $ indica que la cardinalidad del conjunto X es menor que la cardinalidad del conjunto Y. Esto sucede cuando el numero de elementos en X es menor que el de Y. Aqui, la funcion "f "de X a Y es una funcion inyectiva pero no biyectiva. $ If | X | el | Y | $ y $ | X | ge | Y | $ luego $ | X | = | Y | PS Los conjuntos X e Y se denominan comunmente conjuntos equivalentes. Tipos de conjuntos Los conjuntos se pueden clasificar en varios tipos. Algunos de ellos son finitos, infinitos, subconjuntos, universales, propios, singleton, etc. Conjunto finito Un conjunto que contiene un numero definido de elementos se denomina conjunto finito. Ejemplo - $ S = lbrace x: |: x en N $ y $ 70 gt x gt 50 rbrace $ Conjunto infinito Un conjunto que contiene un numero infinito de elementos se denomina conjunto infinito. Ejemplo - $ S = lbrace x: |: x en N $ y $ x gt 10 rbrace $ Subconjunto Un conjunto X es un subconjunto del conjunto Y (escrito como $ X subseteq Y $) si cada elemento de X es un elemento del conjunto Y. Ejemplo 1 - Sea, $ X = lbrace 1, 2, 3, 4, 5, 6 rbrace $ y $ Y = lbrace 1, 2 rbrace $. Aqui, el conjunto Y es un subconjunto de conjunto X porque todos los elementos del conjunto Y estan en el conjunto X. Por lo tanto, podemos escribir $ Y subseteqX $. Ejemplo 2 - Sea, $ X = lbrace 1, 2, 3 rbrace $ y $ Y = lbrace 1, 2, 3 rbrace $. Aqui, el conjunto Y es un subconjunto ( no es un subconjuntopropiamente dicho) del conjunto X porque todos los elementos del conjunto Y estan en el conjunto X. Por lo tanto, podemos escribir $ Y subconjunto X $. Subconjunto adecuado El termino "subconjunto adecuado" se puede definir como "subconjunto de pero no igual a". Un conjunto X es un subconjunto propio del conjunto Y (escrito como $ X subconjunto Y $) si cada elemento de X es un elemento del conjunto Y y $ | X | lt | Y | PS Ejemplo : $ X = lbrace 1, 2, 3, 4, 5, 6 rbrace $ y $ Y = l llave 1, 2 r llave $. Aqui el conjunto $ Y subconjunto X $ porque todos los elementos de $ Y $ tambien estan contenidos en $ X $ y $ X $ tiene al menos un elemento que es mas que el conjunto $ Y $. Conjunto universal Es una coleccion de todos los elementos en un contexto o aplicacion en particular. Todos los conjuntos en este contexto o aplicacion son esencialmente subconjuntos de este conjunto.e universal. Los conjuntos universales estan representados por $ U $. Ejemplo : podemos definir $ U $ como el conjunto de todos los animales de la tierra. En este caso, el conjunto de todos los mamiferos es un subconjunto de $ U $, el conjunto de todos los peces es un subconjunto de $ U $, el conjunto de todos los insectos es un subconjunto de $ U $, y asi sucesivamente. Conjunto vacio o conjunto nulo Un conjunto vacio no contiene elementos. Se indica con $ emptyset $. Dado que el numero de elementos en un conjunto vacio es finito, el conjunto vacio es un conjunto finito. La cardinalidad de un conjunto vacio o un conjunto nulo es cero. Ejemplo - $ S = lbrace x: | : x en N $ y $ 7 lt x lt 8 rbrace = emptyset $ Conjunto de singleton o conjunto de unidades Conjunto o unidad de singleton que el conjunto no contiene solo un elemento. Un conjunto de singleton essenalo $ lbrace s rbrace $. Ejemplo - $ S = lbrace x: | : x en N, 7 lt x lt 9 rbrace $ = $ lbrace 8 rbrace $ Conjunto igual Si dos conjuntos contienen los mismos elementos, se dice que son iguales. Ejemplo : si $ A = lbrace 1, 2, 6 $ rbrace y $ B = lbrace 6, 1, 2 rbrace $, son iguales porque cada elemento del conjunto A es un elemento del conjunto B y cada elemento del conjunto B es un elemento del conjunto A. Conjunto equivalente Si las cardinalidades de dos conjuntos son identicas, se denominan conjuntos equivalentes. Ejemplo : si $ A = lbrace 1, 2, 6 $ rbrace y $ B = lbrace 16, 17, 22 rbrace $, son equivalentes porque la cardinalidad de A es igual a la cardinalidad de B. Sea $ | A | = | B | = 3 $ Conjunto superpuesto Dos conjuntos que tienen al menos un elemento comunse llaman conjuntos superpuestos. En caso de conjuntos superpuestos - $ n (A cup B) = n (A) + n ( B) - n (A limite B) $ $ n (A taza B) = n (A - B) + n (B - A) + n (A limite B) $ $ n (A) = n (A - B) + n (A cap B) $ $ n (B) = n (B - A) + n (A cap B) $ Ejemplo - Sea, $ A = lbrace 1, 2, 6 rbrace $ y $ B = lbrace 6, 12, 42 rbrace $. Hay un elemento comun "6 ", por lo que estos conjuntos son conjuntos superpuestos. Conjunto disjunto Dos conjuntos A y B se denominan conjuntos disjuntos si ni siquiera tienen un elemento en comun. Por lo tanto, los conjuntos disjuntos tienen las siguientes propiedades: $ n (A cap B) = emptyset $ $ n (A taza B) = n (A) + n (B) $ Ejemplo - Sea, $ A = lbrace 1, 2, 6 rbrace $ y $ B = lbrace 7, 9, 14 rbrace $, no hay una solaelemento comun, por lo que estos conjuntos son conjuntos superpuestos. Diagramas de Venn El diagrama de Venn, inventado en 1880 por John Venn, es un diagrama esquematico que muestra todas las posibles relaciones logicas entre diferentes conjuntos matematicos. Ejemplos Operaciones de conjunto Las operaciones de conjunto incluyen conjuntos de conjuntos, conjuntos de interseccion, conjuntos de diferencias, complemento de conjunto y producto cartesiano. Union de conjuntos La union de conjuntos A y B (denotado $ A taza B $) es el conjunto de elementos que estan en A, en B o en el veces en A y B., $ A corta B = lbrace x: |: x en A O x en B rbrace $. Ejemplo - Si $ A = lbrace 10, 11, 12, 13 rbrace $ y B = $ lbrace 13, 14, 15 rbrace $, luego $ A taza B = lbrace 10, 11, 12, 13, 14, 15 rbrace $. (El elemento comun aparece solo una vez) Interseccion de conjuntos La interseccion de los conjuntos A y B (denotado $ A cap B $) es el conjunto de elementos que estan ambos en A y B. Por lo tanto, $ A cap B = lbrace x: |: x en A Y x en B rbrace $. Ejemplo - Si $ A = lbrace 11, 12, 13 rbrace $ y $ B = lbrace 13, 14 , 15 rbrace $, luego $ A cap B = lbrace 13 rbrace $. Diferencia de conjunto / Complemento relativo La diferencia de conjunto de los conjuntos A y B (denotados $ A - B $) es l conjunto de elementos que estan solo en A pero no en B. Por lo tanto, $ A - B = lbrace x: |: x en A AND x notin B rbrace $. Ejemplo - Si $ A = lbrace 10, 11, 12, 13 rbrace $ y $ B = lbrace 13, 14, 15 rbrace $, entonces $ (A - B) = lbrace 10, 11, 12 rbrace $ y $ (B - A) =lbrace 14, rbrace $ 15. Aqui podemos ver $ (A - B) ne (B - A) $ Complemento de un conjunto El complemento de un conjunto A (denotado por $ A "$) es el conjunto de elementos que no estan en el conjunto A. Por lo tanto, $ A "= lbrace x | x notin A rbrace $. Mas precisamente, $ A "= (U - A) $ donde $ U $ es un conjunto universal que contiene todos los objetos. Ejemplo : si $ A = lbrace x: | : x: {pertenece: a: conjunto: de: impar: enteros} rbrace $ luego $ A "= lbrace y: | : y: {no: no: pertenece: a: conjunto: de: impar: enteros} rbrace $ Producto cartesiano / Producto cruzado El producto cartesiano de n numero de conjuntos $ A_1, A_2, puntos A_n $ denotado por $ A_1 multiplicado por A_2 puntos multiplicado por A_n $ se puede definir como todos los pares ordenados posibles $ (x_1, x_2, puntos x_n) $ donde $ x_1 en A_1, x_2en A_2, puntos x_n en A_n $ Ejemplo - Si tomamos dos conjuntos $ A = lbrace a, b rbrace $ y $ B = lbrace 1, 2 rbrace $, El producto cartesiano de A y B se escribe como - $ A por B = lbrace (a, 1), (a, 2), (b, 1), (b, 2) rbrace $ El producto cartesiano de B y A se escribe - $ B por A = lbrace (1, a), (1, b), (2, a), (2, b) rbrace $ Conjunto de potencia El conjunto de potencia de un conjunto S es el conjunto de todos los subconjuntos de S, incluido el conjunto vacio . La cardinalidad de un conjunto de potencias de un conjunto S de cardinalidad n es $ 2 ^ n $. El conjunto de potencia se denota $ P (S) $. Ejemplo - Para un conjunto $ S = lbrace a, b, c, d rbrace $ calcular los subconjuntos - Subconjuntos con elemento 0 - $ lbrace emptyset rbrace $ (el conjunto vacio) Subconjuntos con 1 articulo - $ lbrace a rbrace, lbrace b rbrace, lbrace c rbrace, lbrace d rbrace $ Subconjuntos con 2 elementos - $ lbrace a, b rbrace, lbrace a, c rbrace, lbrace a, d rbrace, lbrace b , c rbrace, lbrace b, d rbrace, lbrace c, d rbrace $ Subconjuntos con 3 elementos - $ lbrace a, b, c rbrace, lbrace a, b , d rbrace, lbrace a, c, d rbrace, lbrace b, c, d rbrace $ Subconjuntos con 4 elementos - $ lbrace a, b, c, d rbrace $ Por lo tanto, $ P (S) = $ $ lbrace quad lbrace vacio rbrace, lbrace a rbrace, lbrace b rbrace, lbrace c rbrace, lbrace d rbrace, lbrace a, b rbrace, lbrace a, c rbrace, lbrace a, d rbrace, lbrace b, c rbrace, lbrace b, d rbrace, lbrace c, d rbrace, lbrace a, b, c rbrace, lbrace a, b, d rbrace, lbrace a, c, d rbrace, lbrace b, c, d rbrace, lbrace a, b, c, d rbrace quad rbrace $ $ | P (S) | = 2 ^ 4 = $ 16 Nota - L "eEl conjunto de potencia de un conjunto vacio tambien es un conjunto vacio. $ | P (lbrace conjunto vacio rbrace) | = 2 ^ 0 = 1 $ Particionar un conjunto La particion de un conjunto, digamos S , es una coleccion de n subconjuntos disjuntos, digamos $ P_1, P_2, puntos P_n $ que satisfacen las siguientes tres condiciones: $ P_i $ no contiene el conjunto vacio. $ lbrack P_i ne lbrace emptyset rbrace para todos 0 lt i le n rbrack $ L La union de los subconjuntos debe ser igual al conjunto original. $ lbrack P_1 taza P_2 taza puntos taza P_n = S rbrack $ La seccion iThe de dos juegos separados esta vacio. $ lbrack P_a cap P_b = lbrace emptyset rbrace, para un ne b donde n ge a ,: b ge 0 rbrack $ Ejemplo Sea $ S =lbrace a, b, c, d, e, f, g, h rbrace $ Una particion probable es $ lbrace a rbrace, lbrace b, c, d rbrace, lbrace e, f, g, h rbrace $ Otra posible particion es $ lbrace a, b rbrace, lbrace c, d rbrace, lbrace e, f, g, h rbrace $ Numeros de campana Los numeros de campana dan un recuento de la cantidad de formas de particionar un conjunto. Se denotan $ B_n $ donde n es la cardinalidad del conjunto. Ejemplo - Sea $ S = lbrace 1, 2, 3 rbrace $, $ n = | S | = 3 $ Las particiones alternativas son - 1. $ conjunto vacio, lbrace 1, 2, 3 rbrace $ 2. $ lbrace 1 rbrace, lbrace 2, 3 rbrace $ 3. $ lbrace 1, 2 rbrace, lbrace 3 rbrace $ 4. $ lbrace 1, 3 rbrace, lbrace 2 rbrace $ 5. $ lbrace 1 rbrace, lbrace 2 rbrace, lbrace 3 rbrace $ Por lo tanto $ B_3 = $ 5