Matemáticas discretas - Conjuntos
Matemático alemán G. Cantorintrodujo el concepto de conjuntos. Había definido un conjunto como una colección de objetos definidos y distinguibles seleccionados por medio de ciertas reglas o descripciones.
SetLa teoría forma la base de varios otros campos de estudio como la teoría del conteo, las relaciones, la teoría de grafos y las máquinas de estados finitos. En este capítulo, cubriremos los diferentes aspectos deSet Theory.
Conjunto - Definición
Un conjunto es una colección desordenada de diferentes elementos. Un conjunto se puede escribir explícitamente enumerando sus elementos utilizando corchetes de conjuntos. Si se cambia el orden de los elementos o se repite cualquier elemento de un conjunto, no realiza ningún cambio en el conjunto.
Algunos ejemplos de conjuntos
- Un conjunto de todos los enteros positivos
- Un conjunto de todos los planetas del sistema solar.
- Un conjunto de todos los estados de la India.
- Un conjunto de todas las letras minúsculas del alfabeto.
Representación de un conjunto
Los conjuntos se pueden representar de dos formas:
- Formulario de lista o tabular
- Establecer notación de constructor
Formulario de lista o tabular
El conjunto se representa enumerando todos los elementos que lo componen. Los elementos están encerrados entre llaves y separados por comas.
Example 1 - Conjunto de vocales en el alfabeto inglés, $ A = \ lbrace a, e, i, o, u \ rbrace $
Example 2 - Conjunto de números impares menores que 10, $ B = \ lbrace 1,3,5,7,9 \ rbrace $
Establecer notación de constructor
El conjunto se define especificando una propiedad que los elementos del conjunto tienen en común. El conjunto se describe como $ A = \ lbrace x: p (x) \ rbrace $
Example 1 - El conjunto $ \ lbrace a, e, i, o, u \ rbrace $ se escribe como -
$ A = \ lbrace x: \ text {x es una vocal en el alfabeto inglés} \ rbrace $
Example 2 - El conjunto $ \ lbrace 1,3,5,7,9 \ rbrace $ se escribe como -
$ 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 denota por $ x \ en S $ y si un elemento y no es miembro del conjunto S, se denota por $ y \ not en S $.
Example- Si $ S = \ lbrace1, 1.2, 1.7, 2 \ rbrace, 1 \ in S $ pero $ 1.5 \ notin S $
Algunos conjuntos importantes
N - el conjunto de todos los números naturales = $ \ lbrace1, 2, 3, 4, ..... \ rbrace $
Z - el conjunto de todos los enteros = $ \ lbrace ....., -3, -2, -1, 0, 1, 2, 3, ..... \ rbrace $
Z+ - el conjunto de todos los enteros positivos
Q - el conjunto de todos los números racionales
R - el conjunto de todos los números reales
W - el conjunto de todos los números enteros
Cardinalidad de un conjunto
La cardinalidad de un conjunto S, denotado por $ | S | $, es el número de elementos del conjunto. El número también se conoce como número cardinal. Si un conjunto tiene un número infinito de elementos, su cardinalidad es $ \ infty $.
Example- $ | \ lbrace 1, 4, 3, 5 \ rbrace | = 4, | \ lbrace 1, 2, 3, 4, 5, \ dots \ rbrace | = \ infty $
Si hay dos conjuntos X e Y,
$ | X | = | Y | $ denota dos conjuntos X e Y que tienen la misma cardinalidad. Ocurre cuando el número de elementos en X es exactamente igual al número de elementos en Y. En este caso, existe una función biyectiva 'f' de X a Y.
$ | X | \ le | Y | $ denota que la cardinalidad del conjunto X es menor o igual que la cardinalidad del conjunto Y. Ocurre cuando el número de elementos en X es menor o igual al de Y. Aquí, existe una función inyectiva 'f' de X a Y.
$ | X | \ lt | Y | $ denota que la cardinalidad del conjunto X es menor que la cardinalidad del conjunto Y. Ocurre cuando el número de elementos en X es menor que el de Y. Aquí, la función 'f' de X a Y es una función inyectiva pero no biyectiva.
$ Si \ | X | \ le | Y | $ y $ | X | \ ge | Y | $ luego $ | X | = | Y | $. Los conjuntos X e Y se denominan comúnmente conjuntos equivalentes.
Tipos de conjuntos
Los conjuntos se pueden clasificar en muchos tipos. Algunos de los cuales son finitos, infinitos, subconjuntos, universales, propios, conjuntos de singleton, etc.
Conjunto finito
Un conjunto que contiene un número definido de elementos se denomina conjunto finito.
Example- $ S = \ lbrace x \: | \: x \ in N $ y $ 70 \ gt x \ gt 50 \ rbrace $
Conjunto infinito
Un conjunto que contiene un número infinito de elementos se llama conjunto infinito.
Example- $ S = \ lbrace x \: | \: x \ in 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.
Example 1- Sea, $ X = \ lbrace 1, 2, 3, 4, 5, 6 \ rbrace $ y $ Y = \ lbrace 1, 2 \ rbrace $. Aquí el conjunto Y es un subconjunto del conjunto X, ya que todos los elementos del conjunto Y están en el conjunto X. Por tanto, podemos escribir $ Y \ subseteq X $.
Example 2- Sea, $ X = \ lbrace 1, 2, 3 \ rbrace $ y $ Y = \ lbrace 1, 2, 3 \ rbrace $. Aquí el conjunto Y es un subconjunto (no un subconjunto propio) del conjunto X ya que todos los elementos del conjunto Y están en el conjunto X. Por tanto, podemos escribir $ Y \ subseteq X $.
Subconjunto propio
El término "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 | $.
Example- Sea, $ X = \ lbrace 1, 2, 3, 4, 5, 6 \ rbrace $ y $ Y = \ lbrace 1, 2 \ rbrace $. Aquí establezca $ Y \ subconjunto X $ ya que todos los elementos en $ Y $ también están contenidos en $ X $ y $ X $ tiene al menos un elemento que es más que el establecido $ Y $.
Conjunto universal
Es una colección de todos los elementos en un contexto o aplicación particular. Todos los conjuntos en ese contexto o aplicación son esencialmente subconjuntos de este conjunto universal. Los conjuntos universales se representan como $ U $.
Example- Podemos definir $ U $ como el conjunto de todos los animales de la tierra. En este caso, el conjunto de todos los mamíferos 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 así sucesivamente.
Conjunto vacío o conjunto nulo
Un conjunto vacío no contiene elementos. Se denota con $ \ emptyset $. Como el número de elementos de un conjunto vacío es finito, el conjunto vacío es un conjunto finito. La cardinalidad del conjunto vacío o del conjunto nulo es cero.
Example- $ S = \ lbrace x \: | \: x \ in N $ y $ 7 \ lt x \ lt 8 \ rbrace = \ emptyset $
Conjunto Singleton o Conjunto de unidades
El conjunto singleton o conjunto de unidades contiene solo un elemento. Un conjunto singleton se denota por $ \ lbrace s \ rbrace $.
Example- $ S = \ lbrace x \: | \: x \ in N, \ 7 \ lt x \ lt 9 \ rbrace $ = $ \ lbrace 8 \ rbrace $
Conjunto igual
Si dos conjuntos contienen los mismos elementos, se dice que son iguales.
Example - Si $ A = \ lbrace 1, 2, 6 \ rbrace $ y $ B = \ lbrace 6, 1, 2 \ rbrace $, son iguales ya que 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 iguales, se denominan conjuntos equivalentes.
Example- Si $ A = \ lbrace 1, 2, 6 \ rbrace $ y $ B = \ lbrace 16, 17, 22 \ rbrace $, son equivalentes ya que la cardinalidad de A es igual a la cardinalidad de B. es decir, $ | A | = | B | = 3 $
Conjunto superpuesto
Dos conjuntos que tienen al menos un elemento común se denominan conjuntos superpuestos.
En caso de conjuntos superpuestos:
$ n (A \ taza B) = n (A) + n (B) - n (A \ cap B) $
$ n (A \ taza B) = n (A - B) + n (B - A) + n (A \ cap B) $
$ n (A) = n (A - B) + n (A \ cap B) $
$ n (B) = n (B - A) + n (A \ cap B) $
Example- Sea, $ A = \ lbrace 1, 2, 6 \ rbrace $ y $ B = \ lbrace 6, 12, 42 \ rbrace $. Hay un elemento común '6', por lo que estos conjuntos son conjuntos superpuestos.
Conjunto disjunto
Dos conjuntos A y B se denominan conjuntos disjuntos si no tienen ni siquiera un elemento en común. Por lo tanto, los conjuntos disjuntos tienen las siguientes propiedades:
$ n (A \ cap B) = \ conjunto vacío $
$ n (A \ taza B) = n (A) + n (B) $
Example - Sea, $ A = \ lbrace 1, 2, 6 \ rbrace $ y $ B = \ lbrace 7, 9, 14 \ rbrace $, no hay un solo elemento común, por lo tanto, estos conjuntos son conjuntos superpuestos.
Diagramas de Venn
El diagrama de Venn, inventado en 1880 por John Venn, es un diagrama esquemático que muestra todas las posibles relaciones lógicas entre diferentes conjuntos matemáticos.
Examples
Establecer operaciones
Las operaciones de conjuntos incluyen Unión de conjuntos, Intersección de conjuntos, Diferencia de conjuntos, Complemento de conjunto y Producto cartesiano.
Establecer unión
La unión de los conjuntos A y B (denotada por $ A \ cup B $) es el conjunto de elementos que están en A, en B, o tanto en A como en B. Por lo tanto, $ A \ cup B = \ lbrace x \: | \: x \ en A \ O \ x \ en B \ rbrace $.
Example- Si $ A = \ lbrace 10, 11, 12, 13 \ rbrace $ y B = $ \ lbrace 13, 14, 15 \ rbrace $, entonces $ A \ cup B = \ lbrace 10, 11, 12, 13, 14 , 15 \ rbrace $. (El elemento común ocurre solo una vez)
Establecer intersección
La intersección de los conjuntos A y B (denotado por $ A \ cap B $) es el conjunto de elementos que están tanto en A como en B. Por lo tanto, $ A \ cap B = \ lbrace x \: | \: x \ en A \ AND \ x \ en B \ rbrace $.
Example - Si $ A = \ lbrace 11, 12, 13 \ rbrace $ y $ B = \ lbrace 13, 14, 15 \ rbrace $, entonces $ A \ cap B = \ lbrace 13 \ rbrace $.
Establecer diferencia / complemento relativo
La diferencia de conjuntos de los conjuntos A y B (denotado por $ A - B $) es el conjunto de elementos que están solo en A pero no en B. Por lo tanto, $ A - B = \ lbrace x \: | \: x \ en A \ AND \ x \ notin B \ rbrace $.
Example- 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, 15 \ rbrace $. Aquí, 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 están en el conjunto A. Por tanto, $ A' = \ lbrace x | x \ notin A \ rbrace $.
Más específicamente, $ A '= (U - A) $ donde $ U $ es un conjunto universal que contiene todos los objetos.
Example- Si $ A = \ lbrace x \: | \: x \ \: {pertenece \: a \: conjunto \: de \: impares \: enteros} \ rbrace $ luego $ A '= \ lbrace y \: | \: y \ \: {no \: no \: pertenece \: a \: conjunto \: de \: números \: impares} \ rbrace $
Producto cartesiano / producto cruzado
El producto cartesiano de n número de conjuntos $ A_1, A_2, \ dots A_n $ denotado como $ A_1 \ times A_2 \ dots \ times A_n $ se puede definir como todos los pares ordenados posibles $ (x_1, x_2, \ dots x_n) $ donde $ x_1 \ en A_1, x_2 \ en A_2, \ puntos x_n \ en A_n $
Example - 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 \ times B = \ lbrace (a, 1), (a, 2), (b, 1), (b, 2) \ rbrace $
El producto cartesiano de B y A se escribe como - $ B \ times A = \ lbrace (1, a), (1, b), (2, a), (2, b) \ rbrace $
Set de poder
El conjunto de potencia de un conjunto S es el conjunto de todos los subconjuntos de S, incluido el conjunto vacío. La cardinalidad de un conjunto de potencias de un conjunto S de cardinalidad n es $ 2 ^ n $. El conjunto de potencia se denota como $ P (S) $.
Example −
Para un conjunto $ S = \ lbrace a, b, c, d \ rbrace $ calculemos los subconjuntos -
Subconjuntos con 0 elementos - $ \ lbrace \ emptyset \ rbrace $ (el conjunto vacío)
Subconjuntos con 1 elemento - $ \ 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 tanto, $ P (S) = $
$ \ lbrace \ quad \ lbrace \ emptyset \ 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 $
Note - El conjunto de potencia de un conjunto vacío también es un conjunto vacío.
$ | P (\ lbrace \ emptyset \ rbrace) | = 2 ^ 0 = 1 $
Partición de un conjunto
La partición de un conjunto, digamos S , es una colección de n subconjuntos disjuntos, digamos $ P_1, P_2, \ dots P_n $ que satisface las siguientes tres condiciones:
$ P_i $ no contiene el conjunto vacío.
$ \ lbrack P_i \ ne \ lbrace \ emptyset \ rbrace \ para \ todos \ 0 \ lt i \ le n \ rbrack $
La unión de los subconjuntos debe ser igual al conjunto original completo.
$ \ lbrack P_1 \ cup P_2 \ cup \ dots \ cup P_n = S \ rbrack $
La intersección de dos conjuntos distintos está vacía.
$ \ lbrack P_a \ cap P_b = \ lbrace \ emptyset \ rbrace, \ for \ a \ ne b \ donde \ n \ ge a, \: b \ ge 0 \ rbrack $
Example
Sea $ S = \ lbrace a, b, c, d, e, f, g, h \ rbrace $
Una partición probable es $ \ lbrace a \ rbrace, \ lbrace b, c, d \ rbrace, \ lbrace e, f, g, h \ rbrace $
Otra partición probable es $ \ lbrace a, b \ rbrace, \ lbrace c, d \ rbrace, \ lbrace e, f, g, h \ rbrace $
Números de campana
Los números de campana dan el recuento de la cantidad de formas de dividir un conjunto. Se denotan por $ B_n $ donde n es la cardinalidad del conjunto.
Example -
Sea $ S = \ lbrace 1, 2, 3 \ rbrace $, $ n = | S | = 3 $
Las particiones alternativas son:
1. $ \ emptyset, \ 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 $