Matemática Discreta - Conjuntos

Matemático alemão G. Cantorintroduziu o conceito de conjuntos. Ele definiu um conjunto como uma coleção de objetos definidos e distinguíveis selecionados por meio de certas regras ou descrição.

Seta teoria forma a base de vários outros campos de estudo, como teoria da contagem, relações, teoria dos grafos e máquinas de estado finito. Neste capítulo, cobriremos os diferentes aspectos daSet Theory.

Conjunto - Definição

Um conjunto é uma coleção não ordenada de diferentes elementos. Um conjunto pode ser escrito explicitamente listando seus elementos usando colchetes. Se a ordem dos elementos for alterada ou qualquer elemento de um conjunto for repetido, ele não fará nenhuma alteração no conjunto.

Alguns exemplos de conjuntos

  • Um conjunto de todos os inteiros positivos
  • Um conjunto de todos os planetas do sistema solar
  • Um conjunto de todos os estados da Índia
  • Um conjunto de todas as letras minúsculas do alfabeto

Representação de um Conjunto

Os conjuntos podem ser representados de duas maneiras -

  • Lista ou Formulário Tabular
  • Definir notação do construtor

Lista ou Formulário Tabular

O conjunto é representado listando todos os elementos que o compõem. Os elementos são colocados entre colchetes e separados por vírgulas.

Example 1 - Conjunto de vogais no alfabeto inglês, $ A = \ lbrace a, e, i, o, u \ rbrace $

Example 2 - Conjunto de números ímpares menor que 10, $ B = \ lbrace 1,3,5,7,9 \ rbrace $

Definir notação do construtor

O conjunto é definido especificando uma propriedade que os elementos do conjunto têm em comum. O conjunto é descrito como $ A = \ lbrace x: p (x) \ rbrace $

Example 1 - O conjunto $ \ lbrace a, e, i, o, u \ rbrace $ é escrito como -

$ A = \ lbrace x: \ text {x é uma vogal do alfabeto inglês} \ rbrace $

Example 2 - O conjunto $ \ lbrace 1,3,5,7,9 \ rbrace $ é escrito como -

$ B = \ lbrace x: 1 \ le x \ lt 10 \ e \ (x \% 2) \ ne 0 \ rbrace $

Se um elemento x é membro de qualquer conjunto S, ele é denotado por $ x \ em S $ e se um elemento y não é membro do conjunto S, ele é denotado por $ y \ notin S $.

Example- Se $ S = \ lbrace1, 1,2, 1,7, 2 \ rbrace, 1 \ em S $ mas $ 1,5 \ não em S $

Alguns conjuntos importantes

N - o conjunto de todos os números naturais = $ \ lbrace1, 2, 3, 4, ..... \ rbrace $

Z - o conjunto de todos os inteiros = $ \ lbrace ....., -3, -2, -1, 0, 1, 2, 3, ..... \ rbrace $

Z+ - o conjunto de todos os inteiros positivos

Q - o conjunto de todos os números racionais

R - o conjunto de todos os números reais

W - o conjunto de todos os números inteiros

Cardinalidade de um conjunto

A cardinalidade de um conjunto S, denotada por $ | S | $, é o número de elementos do conjunto. O número também é conhecido como número cardinal. Se um conjunto possui um número infinito de elementos, sua cardinalidade é $ \ infty $.

Example- $ | \ lbrace 1, 4, 3, 5 \ rbrace | = 4, | \ lbrace 1, 2, 3, 4, 5, \ dots \ rbrace | = \ infty $

Se houver dois conjuntos X e Y,

  • $ | X | = | Y | $ denota dois conjuntos X e Y com a mesma cardinalidade. Ocorre quando o número de elementos em X é exatamente igual ao número de elementos em Y. Nesse caso, existe uma função bijetiva 'f' de X a Y.

  • $ | X | \ le | Y | $ denota que a cardinalidade do conjunto X é menor ou igual à cardinalidade do conjunto Y. Ocorre quando o número de elementos em X é menor ou igual ao de Y. Aqui, existe uma função injetiva 'f' de X a Y.

  • $ | X | \ lt | Y | $ denota que a cardinalidade do conjunto X é menor que a cardinalidade do conjunto Y. Ocorre quando o número de elementos em X é menor que Y. Aqui, a função 'f' de X para Y é injetiva, mas não bijetiva.

  • $ If \ | X | \ le | Y | $ e $ | X | \ ge | Y | $ depois $ | X | = | Y | $. Os conjuntos X e Y são comumente chamados de conjuntos equivalentes.

Tipos de Conjuntos

Os conjuntos podem ser classificados em vários tipos. Alguns dos quais são finitos, infinitos, subconjuntos, universais, próprios, conjuntos singleton, etc.

Conjunto Finito

Um conjunto que contém um número definido de elementos é chamado de conjunto finito.

Example- $ S = \ lbrace x \: | \: x \ in N $ e $ 70 \ gt x \ gt 50 \ rbrace $

Conjunto Infinito

Um conjunto que contém um número infinito de elementos é chamado de conjunto infinito.

Example- $ S = \ lbrace x \: | \: x \ in N $ e $ x \ gt 10 \ rbrace $

Subconjunto

Um conjunto X é um subconjunto do conjunto Y (escrito como $ X \ subseteq Y $) se cada elemento de X for um elemento do conjunto Y.

Example 1- Seja, $ X = \ lbrace 1, 2, 3, 4, 5, 6 \ rbrace $ e $ Y = \ lbrace 1, 2 \ rbrace $. Aqui o conjunto Y é um subconjunto do conjunto X, já que todos os elementos do conjunto Y estão no conjunto X. Portanto, podemos escrever $ Y \ subseteq X $.

Example 2- Seja, $ X = \ lbrace 1, 2, 3 \ rbrace $ e $ Y = \ lbrace 1, 2, 3 \ rbrace $. Aqui, o conjunto Y é um subconjunto (não é um subconjunto adequado) do conjunto X, pois todos os elementos do conjunto Y estão no conjunto X. Portanto, podemos escrever $ Y \ subseteq X $.

Subconjunto próprio

O termo “subconjunto adequado” pode ser definido como “subconjunto de, mas não igual a”. Um Conjunto X é um subconjunto adequado do conjunto Y (escrito como $ X \ subconjunto Y $) se cada elemento de X for um elemento do conjunto Y e $ | X | \ lt | Y | $.

Example- Seja, $ X = \ lbrace 1, 2, 3, 4, 5, 6 \ rbrace $ e $ Y = \ lbrace 1, 2 \ rbrace $. Aqui, defina $ Y \ subset X $, pois todos os elementos em $ Y $ também estão contidos em $ X $ e $ X $ tem pelo menos um elemento a mais do que o conjunto $ Y $.

Conjunto universal

É uma coleção de todos os elementos em um determinado contexto ou aplicativo. Todos os conjuntos nesse contexto ou aplicativo são essencialmente subconjuntos desse conjunto universal. Os conjuntos universais são representados como $ U $.

Example- Podemos definir $ U $ como o conjunto de todos os animais da terra. Nesse caso, o conjunto de todos os mamíferos é um subconjunto de $ U $, o conjunto de todos os peixes é um subconjunto de $ U $, o conjunto de todos os insetos é um subconjunto de $ U $ e assim por diante.

Conjunto vazio ou conjunto nulo

Um conjunto vazio não contém elementos. É denotado por $ \ emptyset $. Como o número de elementos em um conjunto vazio é finito, o conjunto vazio é um conjunto finito. A cardinalidade do conjunto vazio ou conjunto nulo é zero.

Example- $ S = \ lbrace x \: | \: x \ in N $ e $ 7 \ lt x \ lt 8 \ rbrace = \ emptyset $

Conjunto de singleton ou conjunto de unidades

Conjunto de singleton ou conjunto de unidades contém apenas um elemento. Um conjunto singleton é denotado por $ \ lbrace s \ rbrace $.

Example- $ S = \ lbrace x \: | \: x \ in N, \ 7 \ lt x \ lt 9 \ rbrace $ = $ \ lbrace 8 \ rbrace $

Conjunto igual

Se dois conjuntos contêm os mesmos elementos, eles são considerados iguais.

Example - Se $ A = \ lbrace 1, 2, 6 \ rbrace $ e $ B = \ lbrace 6, 1, 2 \ rbrace $, eles são iguais, pois cada elemento do conjunto A é um elemento do conjunto B e cada elemento do conjunto B é um elemento do conjunto A.

Conjunto Equivalente

Se as cardinalidades de dois conjuntos são iguais, eles são chamados de conjuntos equivalentes.

Example- Se $ A = \ lbrace 1, 2, 6 \ rbrace $ e $ B = \ lbrace 16, 17, 22 \ rbrace $, eles são equivalentes, pois a cardinalidade de A é igual à cardinalidade de B. ie $ | A | = | B | = 3 $

Conjunto Sobreposto

Dois conjuntos que possuem pelo menos um elemento comum são chamados de conjuntos sobrepostos.

Em caso de conjuntos sobrepostos -

  • $ n (A \ cap B) = n (A) + n (B) - n (A \ cap B) $

  • $ n (A \ xícara 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- Seja, $ A = \ lbrace 1, 2, 6 \ rbrace $ e $ B = \ lbrace 6, 12, 42 \ rbrace $. Há um elemento comum '6', portanto, esses conjuntos são conjuntos sobrepostos.

Conjunto Disjunto

Dois conjuntos A e B são chamados de conjuntos disjuntos se não tiverem nem mesmo um elemento em comum. Portanto, os conjuntos separados têm as seguintes propriedades -

  • $ n (A \ cap B) = \ emptyset $

  • $ n (A \ xícara B) = n (A) + n (B) $

Example - Sejam $ A = \ lbrace 1, 2, 6 \ rbrace $ e $ B = \ lbrace 7, 9, 14 \ rbrace $, não há um único elemento comum, portanto, esses conjuntos são conjuntos sobrepostos.

Diagramas venn

O diagrama de Venn, inventado em 1880 por John Venn, é um diagrama esquemático que mostra todas as relações lógicas possíveis entre diferentes conjuntos matemáticos.

Examples

Operações de conjunto

As operações de conjunto incluem União de conjuntos, Intersecção de conjuntos, Diferença de conjuntos, Complemento de conjunto e Produto cartesiano.

Definir União

A união dos conjuntos A e B (denotados por $ A \ cup B $) é o conjunto de elementos que estão em A, em B, ou em A e B. Portanto, $ A \ cup B = \ lbrace x \: | \: x \ em A \ OU \ x \ em B \ rbrace $.

Example- Se $ A = \ lbrace 10, 11, 12, 13 \ rbrace $ e B = $ \ lbrace 13, 14, 15 \ rbrace $, então $ A \ cup B = \ lbrace 10, 11, 12, 13, 14 , 15 \ rbrace $. (O elemento comum ocorre apenas uma vez)

Definir interseção

A interseção dos conjuntos A e B (denotada por $ A \ cap B $) é o conjunto de elementos que estão em A e B. Portanto, $ A \ cap B = \ lbrace x \: | \: x \ in A \ AND \ x \ em B \ rbrace $.

Example - Se $ A = \ lbrace 11, 12, 13 \ rbrace $ e $ B = \ lbrace 13, 14, 15 \ rbrace $, então $ A \ cap B = \ lbrace 13 \ rbrace $.

Definir Diferença / Complemento Relativo

A diferença de conjunto dos conjuntos A e B (denotada por $ A - B $) é o conjunto de elementos que estão apenas em A, mas não em B. Portanto, $ A - B = \ lbrace x \: | \: x \ in A \ AND \ x \ notin B \ rbrace $.

Example- Se $ A = \ lbrace 10, 11, 12, 13 \ rbrace $ e $ B = \ lbrace 13, 14, 15 \ rbrace $, então $ (A - B) = \ lbrace 10, 11, 12 \ rbrace $ e $ (B - A) = \ lbrace 14, 15 \ rbrace $. Aqui, podemos ver $ (A - B) \ ne (B - A) $

Complemento de um Conjunto

O complemento de um conjunto A (denotado por $ A '$) é o conjunto de elementos que não estão no conjunto A. Portanto, $ A' = \ lbrace x | x \ notin A \ rbrace $.

Mais especificamente, $ A '= (U - A) $ onde $ U $ é um conjunto universal que contém todos os objetos.

Example- Se $ A = \ lbrace x \: | \: x \ \: {pertence \: a \: conjunto \: de \: ímpar \: inteiros} \ rbrace $ então $ A '= \ lbrace y \: | \: y \ \: {não \: não \: pertence \: a \: definir \: de \: ímpar \: inteiros} \ rbrace $

Produto cartesiano / produto cruzado

O produto 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 $ pode ser definido como todos os pares ordenados possíveis $ (x_1, x_2, \ dots x_n) $ onde $ x_1 \ em A_1, x_2 \ em A_2, \ dots x_n \ em A_n $

Example - Se tomarmos dois conjuntos $ A = \ lbrace a, b \ rbrace $ e $ B = \ lbrace 1, 2 \ rbrace $,

O produto cartesiano de A e B é escrito como - $ A \ vezes B = \ lbrace (a, 1), (a, 2), (b, 1), (b, 2) \ rbrace $

O produto cartesiano de B e A é escrito como - $ B \ vezes A = \ lbrace (1, a), (1, b), (2, a), (2, b) \ rbrace $

Conjunto de força

O conjunto de potência de um conjunto S é o conjunto de todos os subconjuntos de S, incluindo o conjunto vazio. A cardinalidade de um conjunto de potência de um conjunto S de cardinalidade n é $ 2 ^ n $. O conjunto de potência é denotado como $ P (S) $.

Example −

Para um conjunto $ S = \ lbrace a, b, c, d \ rbrace $ vamos calcular os subconjuntos -

  • Subconjuntos com 0 elementos - $ \ lbrace \ emptyset \ rbrace $ (o conjunto vazio)

  • Subconjuntos com 1 elemento - $ \ lbrace a \ rbrace, \ lbrace b \ rbrace, \ lbrace c \ rbrace, \ lbrace d \ rbrace $

  • Subconjuntos com 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 com 3 elementos - $ \ lbrace a, b, c \ rbrace, \ lbrace a, b, d \ rbrace, \ lbrace a, c, d \ rbrace, \ lbrace b, c, d \ rbrace $

  • Subconjuntos com 4 elementos - $ \ lbrace a, b, c, d \ rbrace $

Portanto, $ 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 - O conjunto de potência de um conjunto vazio também é um conjunto vazio.

$ | P (\ lbrace \ emptyset \ rbrace) | = 2 ^ 0 = 1 $

Particionamento de um conjunto

A partição de um conjunto, digamos S , é uma coleção de n subconjuntos disjuntos, digamos $ P_1, P_2, \ dots P_n $ que satisfaz as seguintes três condições -

  • $ P_i $ não contém o conjunto vazio.

    $ \ lbrack P_i \ ne \ lbrace \ emptyset \ rbrace \ for \ all \ 0 \ lt i \ le n \ rbrack $

  • A união dos subconjuntos deve ser igual a todo o conjunto original.

    $ \ lbrack P_1 \ xícara P_2 \ xícara \ dots \ xícara P_n = S \ rbrack $

  • A interseção de quaisquer dois conjuntos distintos está vazia.

    $ \ lbrack P_a \ cap P_b = \ lbrace \ emptyset \ rbrace, \ para \ a \ ne b \ onde \ n \ ge a, \: b \ ge 0 \ rbrack $

Example

Seja $ S = \ lbrace a, b, c, d, e, f, g, h \ rbrace $

Um particionamento provável é $ \ lbrace a \ rbrace, \ lbrace b, c, d \ rbrace, \ lbrace e, f, g, h \ rbrace $

Outro particionamento provável é $ \ lbrace a, b \ rbrace, \ lbrace c, d \ rbrace, \ lbrace e, f, g, h \ rbrace $

Números de Sino

Os números das campainhas fornecem a contagem do número de maneiras de particionar um conjunto. Eles são denotados por $ B_n $ onde n é a cardinalidade do conjunto.

Example -

Seja $ S = \ lbrace 1, 2, 3 \ rbrace $, $ n = | S | = 3 $

As partições alternativas são -

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 $

Portanto, $ B_3 = 5 $