Matemática Discreta - Teoria de Grupo
Semigrupo
Um conjunto finito ou infinito $ 'S' $ com uma operação binária $ '\ omicron' $ (Composição) é chamado de semigrupo se ele se mantiver seguindo duas condições simultaneamente -
Closure - Para cada par $ (a, b) \ in S, \ :( a \ omicron b) $ deve estar presente no conjunto $ S $.
Associative - Para cada elemento $ a, b, c \ in S, (a \ omicron b) \ omicron c = a \ omicron (b \ omicron c) $ deve conter.
Exemplo
O conjunto de inteiros positivos (excluindo zero) com operação de adição é um semigrupo. Por exemplo, $ S = \ lbrace 1, 2, 3, \ dots \ rbrace $
Aqui, a propriedade de fechamento é válida para cada par $ (a, b) \ in S, (a + b) $ está presente no conjunto S. Por exemplo, $ 1 + 2 = 3 \ in S] $
A propriedade associativa também é válida para cada elemento $ a, b, c \ in S, (a + b) + c = a + (b + c) $. Por exemplo, $ (1 + 2) + 3 = 1 + (2 + 3) = 5 $
Monóide
Um monóide é um semigrupo com um elemento de identidade. O elemento de identidade (denotado por $ e $ ou E) de um conjunto S é um elemento tal que $ (a \ omicron e) = a $, para cada elemento $ a \ em S $. Um elemento de identidade também é chamado deunit element. Então, um monóide possui três propriedades simultaneamente -Closure, Associative, Identity element.
Exemplo
O conjunto de inteiros positivos (excluindo zero) com operação de multiplicação é um monóide. $ S = \ lbrace 1, 2, 3, \ dots \ rbrace $
Aqui, a propriedade de fechamento vale para cada par $ (a, b) \ in S, (a \ times b) $ está presente no conjunto S. [Por exemplo, $ 1 \ times 2 = 2 \ in S $ e assim por diante]
A propriedade associativa também é válida para cada elemento $ a, b, c \ in S, (a \ vezes b) \ vezes c = a \ vezes (b \ vezes c) $ [Por exemplo, $ (1 \ vezes 2) \ vezes 3 = 1 \ vezes (2 \ vezes 3) = 6 $ e assim por diante]
A propriedade de identidade também é válida para cada elemento $ a \ em S, (a \ vezes e) = a $ [Por exemplo, $ (2 \ vezes 1) = 2, (3 \ vezes 1) = 3 $ e assim por diante]. Aqui, o elemento de identidade é 1.
Grupo
Um grupo é um monóide com um elemento inverso. O elemento inverso (denotado por I) de um conjunto S é um elemento tal que $ (a \ omicron I) = (I \ omicron a) = a $, para cada elemento $ a \ em S $. Portanto, um grupo possui quatro propriedades simultaneamente - i) Fechamento, ii) Associativo, iii) Elemento de identidade, iv) Elemento inverso. A ordem de um grupo G é o número de elementos em G e a ordem de um elemento em um grupo é o número inteiro menos positivo n, de modo que an é o elemento de identidade desse grupo G.
Exemplos
O conjunto de matrizes $ N \ vezes N $ não singulares forma um grupo sob a operação de multiplicação de matrizes.
O produto de duas matrizes não singulares $ N \ times N $ também é uma matriz não singular $ N \ times N $ que contém a propriedade de fechamento.
A multiplicação da matriz em si é associativa. Conseqüentemente, a propriedade associativa é mantida.
O conjunto de matrizes não singulares $ N \ times N $ contém a matriz de identidade que contém a propriedade do elemento de identidade.
Como todas as matrizes são não singulares, todas têm elementos inversos que também são matrizes não singulares. Conseqüentemente, a propriedade inversa também é válida.
Grupo Abeliano
Um grupo abeliano G é um grupo para o qual o par de elementos $ (a, b) \ in G $ sempre possui lei comutativa. Portanto, um grupo possui cinco propriedades simultaneamente - i) Fechamento, ii) Associativo, iii) Elemento de identidade, iv) Elemento inverso, v) Comutativo.
Exemplo
O conjunto de inteiros positivos (incluindo zero) com operação de adição é um grupo abeliano. $ G = \ lbrace 0, 1, 2, 3, \ dots \ rbrace $
Aqui a propriedade de fechamento é válida para cada par $ (a, b) \ em S, (a + b) $ está presente no conjunto S. [Por exemplo, $ 1 + 2 = 2 \ em S $ e assim por diante]
A propriedade associativa também é válida para cada elemento $ a, b, c \ in S, (a + b) + c = a + (b + c) $ [Por exemplo, $ (1 +2) + 3 = 1 + (2 + 3) = 6 $ e assim por diante]
A propriedade de identidade também é válida para cada elemento $ a \ em S, (a \ vezes e) = a $ [Por exemplo, $ (2 \ vezes 1) = 2, (3 \ vezes 1) = 3 $ e assim por diante]. Aqui, o elemento de identidade é 1.
A propriedade comutativa também é válida para cada elemento $ a \ em S, (a \ vezes b) = (b \ vezes a) $ [Por exemplo, $ (2 \ vezes 3) = (3 \ vezes 2) = 3 $ e assim em]
Grupo cíclico e subgrupo
UMA cyclic groupé um grupo que pode ser gerado por um único elemento. Cada elemento de um grupo cíclico é uma potência de algum elemento específico que é chamado de gerador. Um grupo cíclico pode ser gerado por um gerador 'g', de modo que todos os outros elementos do grupo podem ser escritos como uma potência do gerador 'g'.
Exemplo
O conjunto de números complexos $ \ lbrace 1, -1, i, -i \ rbrace $ sob operação de multiplicação é um grupo cíclico.
Existem dois geradores - $ i $ e $ –i $ as $ i ^ 1 = i, i ^ 2 = -1, i ^ 3 = -i, i ^ 4 = 1 $ e também $ (- i) ^ 1 = -i, (–i) ^ 2 = -1, (–i) ^ 3 = i, (–i) ^ 4 = 1 $ que cobre todos os elementos do grupo. Portanto, é um grupo cíclico.
Note - A cyclic groupé sempre um grupo abeliano, mas nem todo grupo abeliano é um grupo cíclico. Os números racionais sob adição não são cíclicos, mas abelianos.
UMA subgroup H é um subconjunto de um grupo G (denotado por $ H ≤ G $) se ele satisfaz as quatro propriedades simultaneamente - Closure, Associative, Identity elemente Inverse.
Um subgrupo H de um grupo G que não inclui todo o grupo G é chamado de subgrupo adequado (indicado por $ H <G $). Um subgrupo de um grupo cíclico é cíclico e um subgrupo abeliano também é abeliano.
Exemplo
Seja um grupo $ G = \ lbrace 1, i, -1, -i \ rbrace $
Então, alguns subgrupos são $ H_1 = \ lbrace 1 \ rbrace, H_2 = \ lbrace 1, -1 \ rbrace $,
Este não é um subgrupo - $ H_3 = \ lbrace 1, i \ rbrace $ porque $ (i) ^ {- 1} = -i $ não está em $ H_3 $
Conjunto parcialmente ordenado (POSET)
Um conjunto parcialmente ordenado consiste em um conjunto com uma relação binária que é reflexiva, antissimétrica e transitiva. "Conjunto parcialmente ordenado" é abreviado como POSET.
Exemplos
O conjunto de números reais sob operação binária menor ou igual a $ (\ le) $ é um poset.
Deixe o conjunto $ S = \ lbrace 1, 2, 3 \ rbrace $ e a operação é $ \ le $
As relações serão $ \ lbrace (1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (2, 3) \ rbrace $
Esta relação R é reflexiva como $ \ lbrace (1, 1), (2, 2), (3, 3) \ rbrace \ em R $
Esta relação R é anti-simétrica, pois
$ \ lbrace (1, 2), (1, 3), (2, 3) \ rbrace \ in R \ e \ \ lbrace (1, 2), (1, 3), (2, 3) \ rbrace ∉ R$
Esta relação R também é transitiva como $ \ lbrace (1,2), (2,3), (1,3) \ rbrace \ em R $.
Portanto, é um poset.
O conjunto de vértices de um gráfico acíclico direcionado sob a operação 'alcançabilidade' é um poset.
Diagrama de Hasse
O diagrama de Hasse de um poset é o gráfico direcionado cujos vértices são o elemento desse poset e os arcos cobrem os pares (x, y) no poset. Se no poset $ x <y $, então o ponto x aparece abaixo do ponto y no diagrama de Hasse. Se $ x <y <z $ no poset, então a seta não é mostrada entre x e z porque está implícita.
Exemplo
O poset de subconjuntos de $ \ lbrace 1, 2, 3 \ rbrace = \ lbrace \ emptyset, \ lbrace 1 \ rbrace, \ lbrace 2 \ rbrace, \ lbrace 3 \ rbrace, \ lbrace 1, 2 \ rbrace, \ lbrace 1 , 3 \ rbrace, \ lbrace 2, 3 \ rbrace, \ lbrace 1, 2, 3 \ rbrace \ rbrace $ é mostrado pelo seguinte diagrama de Hasse -
Conjunto ordenado linearmente
Um conjunto ordenado linearmente ou um conjunto ordenado total é um conjunto de ordem parcial em que cada par de elementos é comparável. Os elementos $ a, b \ in S $ são considerados comparáveis se $ a \ le b $ ou $ b \ le a $ forem válidos. A lei da tricotomia define esse conjunto ordenado total. Um conjunto totalmente ordenado pode ser definido como uma rede distributiva tendo a propriedade $ \ lbrace a \ lor b, a \ land b \ rbrace = \ lbrace a, b \ rbrace $ para todos os valores de aeb no conjunto S.
Exemplo
O conjunto de poderes de $ \ lbrace a, b \ rbrace $ ordenado por \ subseteq é um conjunto totalmente ordenado com todos os elementos do conjunto de potência $ P = \ lbrace \ emptyset, \ lbrace a \ rbrace, \ lbrace b \ rbrace, \ lbrace a, b \ rbrace \ rbrace $ são comparáveis.
Exemplo de conjunto de pedido não total
Um conjunto $ S = \ lbrace 1, 2, 3, 4, 5, 6 \ rbrace $ sob a operação x divide y não é um conjunto ordenado total.
Aqui, para todos os $ (x, y) \ em S, x | y $ tem que ser mantido, mas não é verdade que 2 | 3, como 2 não divide 3 ou 3 não divide 2. Portanto, não é um conjunto ordenado total.
Malha
Uma rede é um poset $ (L, \ le) $ para o qual cada par $ \ lbrace a, b \ rbrace \ em L $ tem um menor limite superior (denotado por $ a \ lor b $) e um maior limite inferior ( denotado por $ a \ land b $). LUB $ (\ lbrace a, b \ rbrace) $ é chamado de junção de a e b. GLB $ (\ lbrace a, b \ rbrace) $ é chamado de encontro de a e b.
Exemplo
A figura acima é uma rede porque para cada par $ \ lbrace a, b \ rbrace \ em L $, existe um GLB e um LUB.
A figura acima não é uma rede porque $ GLB (a, b) $ e $ LUB (e, f) $ não existem.
Algumas outras redes são discutidas abaixo -
Malha limitada
Um reticulado L torna-se um reticulado limitado se tiver um maior elemento 1 e um menor elemento 0.
Malha Complementada
Um reticulado L torna-se um reticulado complementado se for um reticulado limitado e se cada elemento do reticulado tiver um complemento. Um elemento x tem um complemento x 'se $ \ existe x (x \ land x' = 0 e x \ lor x '= 1) $
Malha distributiva
Se uma rede satisfaz as duas propriedades de distribuição a seguir, ela é chamada de rede distributiva.
$ a \ lor (b \ land c) = (a \ lor b) \ land (a \ lor c) $
$ a \ land (b \ lor c) = (a \ land b) \ lor (a \ land c) $
Malha Modular
Se uma rede satisfaz a seguinte propriedade, ela é chamada de rede modular.
$ a \ land (b \ lor (a \ land d)) = (a \ land b) \ lor (a \ land d) $
Propriedades de reticulados
Propriedades Idempotentes
$ a \ lor a = a $
$ a \ land a = a $
Propriedades de Absorção
$ a \ lor (a \ land b) = a $
$ a \ land (a \ lor b) = a $
Propriedades Comutativas
$ a \ lor b = b \ lor a $
$ a \ land b = b \ land a $
Propriedades Associativas
$ a \ lor (b \ lor c) = (a \ lor b) \ lor c $
$ a \ land (b \ land c) = (a \ land b) \ land c $
Dual of a Lattice
O dual de uma rede é obtido trocando as operações '$ \ lor $' e '$ \ land $'.
Exemplo
O dual de $ \ lbrack a \ lor (b \ land c) \ rbrack \ é \ \ lbrack a \ land (b \ lor c) \ rbrack $