Álgebra dos Conjuntos e Álgebra de Boole

Prévia do material em texto

<p>Álgebra dos Conjuntos e Álgebra de Boole</p><p>Jean Marcos Lima Santos</p><p>Edson Carlos Gomes de Souza</p><p>Aracaju, Junho de 2024</p><p>Álgebra dos Conjuntos e Álgebra de Boole</p><p>Pesquisa Bibliográfica realizada na</p><p>disciplina de Lógica Matemática orientado</p><p>pelo professor Luiz Gomes da Cunha Neto</p><p>como pré-registro para obtenção da nota da</p><p>Atividade Prática Supervisionada que</p><p>compõem parte da nota da 2ª unidade.</p><p>Aracaju, Junho de 2024</p><p>SUMÁRIO</p><p>1. Álgebra dos Conjuntos e Exemplos de Aplicação:........................................................ 4</p><p>1.1. Operações com Conjuntos e Propriedades:............................................................... 4</p><p>1.2. Diagramas de Venn:....................................................................................................4</p><p>1.3. Identidades e Leis de Conjuntos:................................................................................5</p><p>2. Álgebra de Boole................................................................................................................6</p><p>2.1. Operações...................................................................................................................6</p><p>2.2. Leis de booleana.........................................................................................................7</p><p>2.3. Funções Booleanas.....................................................................................................7</p><p>2.4. Expressões Booleanas................................................................................................7</p><p>2.5. Circuitos Lógicos......................................................................................................... 8</p><p>3. Referências.......................................................................................................................10</p><p>1. Álgebra dos Conjuntos e Exemplos de Aplicação:</p><p>Um conjunto é como uma coleção não ordenada de coisas diferentes, chamadas de</p><p>elementos do conjunto. Dizemos que um elemento "x" pertence a um conjunto "A" se "x" é</p><p>um dos elementos de "A". Isso é denotado por "x ∈ A". Se "x" não pertence a "A",</p><p>escrevemos "x ∉ A" [1].</p><p>Se "x" pertence a "A", podemos dizer que "A" tem ou possui "x", o que é escrito</p><p>como "A ∋ x". Para dizer que "A" não tem ou não possui "x", escrevemos "A ∌ x". Não é</p><p>correto dizer que "A" "contém" "x", porque esse termo é usado de forma diferente na</p><p>matemática [1].</p><p>1.1. Operações com Conjuntos e Propriedades:</p><p>Podemos descrever um conjunto de diferentes maneiras. Se um conjunto tem</p><p>apenas alguns elementos, podemos listar cada um deles, sem uma ordem específica, entre</p><p>chaves '{}'. Por exemplo, o conjunto contendo os números inteiros 2, 3 e 5 pode ser</p><p>representado como {2, 3, 5}. Assim, por exemplo, afirmamos que 3 pertence ao conjunto {2,</p><p>3, 5}, mas 4 não [1].</p><p>Outra maneira de especificar um conjunto é através das propriedades de seus</p><p>elementos. Para fazer isso, usamos a notação { a : P(a) }, onde "a" é uma variável arbitrária e</p><p>"P(a)" é uma afirmação matemática que depende do valor de "a". Por exemplo, { a : a é um</p><p>número inteiro e -5 < a < 5 } é uma forma de definir o conjunto {−4, −3, −2, −1, 0, +1, +2,</p><p>+3, +4} [1].</p><p>Existem conjuntos de números frequentemente utilizados na matemática, e eles têm</p><p>notações convencionais bem estabelecidas:</p><p>• o conjunto dos números inteiros Z,</p><p>• o conjunto dos números naturais N = { x : x∈ Z e x ≥ 0 },</p><p>• o conjunto dos números racionais Q ={ : a,b∈ Z e b 0}, e𝑎</p><p>𝑏 ≠</p><p>• o conjunto dos números reais R.</p><p>1.2. Diagramas de Venn:</p><p>Na lógica, podemos ter proposições mais complexas que estabelecem relações entre</p><p>características usando palavras como "todo", "algum" e "nenhum". Por exemplo, "alguns</p><p>oceanos estão poluídos" é uma proposição que envolve dois conjuntos de coisas: o conjunto</p><p>de partes do planeta Terra que são oceanos e o conjunto de coisas que estão poluídas.</p><p>Para entender melhor essas relações, podemos usar Diagramas de Venn, que são</p><p>representações visuais que mostram a interseção entre conjuntos. Cada conjunto é</p><p>representado por um círculo, e a sobreposição dos círculos mostra onde os conjuntos</p><p>compartilham elementos, como no caso dos oceanos poluídos [3].</p><p>O círculo que representa o conjunto S refere-se aos elementos desse conjunto, assim</p><p>como o círculo que representa o conjunto P reporta-se aos elementos do mesmo. A relação</p><p>entre ambos torna-se graficamente visível na intersecção dos círculos, já que há elementos</p><p>comuns aos dois conjuntos (oceanos poluídos): uma vez que alguns elementos de S são</p><p>também elementos de P, na representação gráfica da intersecção de S e P existirá, em termos</p><p>de notação lógica, um x (FIGURA 1) [3].</p><p>Figura 1: Intersecção de S e P.</p><p>Fonte: CARVALHO, 2017.</p><p>É importante usar os Diagramas de Venn corretamente para evitar distorções. Por</p><p>exemplo, usá-los para representar conceitos como sonho e pesadelo ou luz e escuridão pode</p><p>ser confuso, pois esses conceitos não podem ser facilmente quantificados ou representados</p><p>por meio da lógica dos conjuntos. Os Diagramas de Venn são mais úteis para representar</p><p>propriedades e relações específicas entre conjuntos de coisas.</p><p>1.3. Identidades e Leis de Conjuntos:</p><p>Identidades de conjuntos são expressões que são verdadeiras para qualquer</p><p>conjunto de elementos. Elas são úteis para simplificar expressões e demonstrar relações</p><p>entre conjuntos. As leis de conjuntos são regras que descrevem como as operações entre</p><p>conjuntos se comportam. Conjuntos sob operações de união, interseção e complementar</p><p>satisfazem a várias leis (identidades) que são listadas na Tabela 1. De fato, estabelecemos</p><p>isso formalmente como [7]:</p><p>Tabela 1: Leis da álgebra de conjuntos.</p><p>Fonte: LIPSCHUTZ, 2013.</p><p>Cada lei na Tabela 1-1 segue a partir de uma lei lógica equivalente. Considere, por</p><p>exemplo, a demonstração da Lei de DeMorgan 10(a):</p><p>Aqui usamos a lei lógica equivalente (DeMorgan):</p><p>¬(p∨ q) = ¬p∧ ¬q</p><p>onde ¬ significa “não”,∨ significa “ou” e∧ significa “e”. (Às vezes diagramas de Venn são</p><p>empregados para ilustrar as leis na Tabela 1.</p><p>As identidades na Tabela 1 são arranjadas em pares como, por exemplo, (2a) e (2b).</p><p>Consideramos agora o princípio por trás desse arranjo. Suponha que E é uma equação de</p><p>álgebra conjuntista. O dual E∗ de E é a equação obtida pela substituição de cada ocorrência</p><p>de∪, ∩, U e ∅ em E por ∩,∪, ∅ e U, respectivamente. Por exemplo, o dual de</p><p>(U ∩ A)∪ (B ∩ A) = A é (∅ ∪ A) ∩ (B∪ A) = A</p><p>Observe que os pares de leis na Tabela 1-1 são duais um do outro. É um fato da</p><p>álgebra conjuntista, conhecido como princípio de dualidade, que se uma equação E é uma</p><p>identidade, então seu dual E* também é uma identidade.</p><p>2. Álgebra de Boole</p><p>Na álgebra booleana existem apenas três operadores lógicos conhecidos também por</p><p>operadores booleanos: AND, OR e NOT (E, OU e NÃO). Estas três funções são as únicas</p><p>operações necessárias para somar, subtrair, multiplicar e dividir, ou ainda, executar ações tais</p><p>como comparar símbolos ou números. Para tanto, BOOLE introduziu o conceito de portas</p><p>lógicas que só processa dois tipos de entidades - verdade ou falsidade, sim ou não, aberto ou</p><p>fechado, um ou zero.</p><p>2.1. Operações</p><p>x∧ y = xy (conjunção)</p><p>x∨ y = x + y - xy (disjunção)</p><p>¬ x = 1 – x (negação)</p><p>Os valores podem ser obtidos através da tabela verdade, Tabela 2.</p><p>Tabela 2: Resultado da tabela verdade.</p><p>Fonte: GONÇALVES, 2014.</p><p>Ou com equações gerando os valores explicitamente, Figura 2:</p><p>Figura 2: Equações com valores explícitos.</p><p>Fonte: GONÇALVES, 2014.</p><p>2.2. Leis de booleana</p><p>Involução (a’)’ = a</p><p>Associatividade (a+b)+c = a+(b+c) (a.b).c = a.(b.c)</p><p>De Morgan (ab)’ = a’ + b’ (a + b)’ = a’ b’</p><p>As leis de De Morgan são muito importantes para fazer inferências válidas em</p><p>provas e argumentos dedutivos;</p><p>(i) (a+b+c+...)’= a’.b’.c’....</p><p>(ii) (a.b.c....)’=a’+b’+c’+...</p><p>2.3. Funções Booleanas</p><p>Dada uma álgebra booleana hA, +, ·, , 0, 1i, uma expressão booleana em n variáveis</p><p>x1, x2, . . ., xn define uma função booleana f : An → A. O valor da função f para um</p><p>elemento a = (a1, a2, . . . , an) ∈ An é calculado substituindo-se cada ocorrência de xi na</p><p>expressão por ai , para i = 1, 2, . . . , n, e calculando-se o valor da expressão.</p><p>Seja A(n) o conjunto de todas as funções booleanas em A com n variáveis e seja ≤</p><p>uma relação definida em A(n) da seguinte forma: f ≤ g ⇐⇒ f(a) ≤ g(a), ∀a ∈ A n . (3.1)</p><p>Seja (f · g)(a) = f(a) · g(a), (f + g)(a) = f(a) + g(a), e f(a) = f(a),∀a∈ An . Fazendo 0(a) = 0</p><p>e 1(a) = 1 para todo a ∈ An , o conjunto (A(n), +, ·, , 0, 1) também uma álgebra booleana.</p><p>Note que nem todas as funções f : An → A podem ser definidas por uma expressão booleana;</p><p>funções booleanas são aquelas que podem ser definidas por uma expressão booleana.</p><p>2.4. Expressões Booleanas</p><p>Variáveis e literais: Dada uma álgebra booleana hA, +, ·, , 0, 1i, uma variável</p><p>booleana é uma variável que toma valores em A. Dada uma variável booleana x, o</p><p>complemento de x, denotado x, é uma variável booleana tal que x = a sempre que x = a para</p><p>qualquer a ∈ A. Um literal é uma variável booleana x ou o seu complemento x. Expressões</p><p>booleanas: Dada uma álgebra booleana hA, +, ·, , 0, 1i, as seguintes são expressões booleanas</p><p>em n variáveis x1, x2, . . . , xn: • os elementos 0 e 1, • as variáveis booleanas x1, x2, . . . , xn,</p><p>• x + y, x · y, x, onde x e y são expressões booleanas nas variáveis x1, x2, . . . , xn. Observe</p><p>que uma expressão booleana em n variáveis x1, x2, . . . , xn não necessariamente precisa</p><p>conter todas as n variáveis. Se uma expressão pode ser derivada a partir de outra aplicando-se</p><p>um número finito de vezes as regras (leis/propriedades) da álgebra booleana, então elas são</p><p>ditas equivalentes. O valor de expressões equivalentes, para cada atribuição de valores às</p><p>variáveis booleanas, é o mesmo. Expressões booleanas definem uma função. Expressões</p><p>equivalentes definem uma mesma função.</p><p>2.5. Circuitos Lógicos</p><p>Para contornar o fan-out, uma possível solução são as realizações em estruturas de</p><p>árvores. A Figura 5 mostra a realização de um decodificador 3:8 em uma estrutura de árvore.</p><p>Em vez de termos todas as variáveis alimentando portas no primeiro nível, temos variáveis</p><p>que alimentam portas nos outros não níveis, como o exemplo mostrado na Figura 3 [6].</p><p>Figura 3: Circuito de um decodificador 2:4.</p><p>Fonte: HIRATA, 2005.</p><p>Usando este esquema, pode-se reduzir o número de portas no próximo nível que</p><p>precisam ser alimentadas pela saída de uma porta no nível anterior. Mesmo assim, o problema</p><p>de fan-out não é totalmente eliminado pois as variáveis introduzidas nos níveis posteriores do</p><p>circuito precisam alimentar muitas portas. No entanto, é mais fácil controlar o sinal de</p><p>algumas poucas entradas (variáveis) para que eles sejam capazes de alimentar um maior</p><p>número de portas do que fazer o mesmo com as saídas das portas lógicas. Esta solução possui</p><p>um maior número de níveis e um maior número de portas lógicas do que o esquema mostrado</p><p>na Figura 4, mas para decodificadores de muitas entradas pode ser a única solução [6].</p><p>Figura 4: Realização três-níveis de um decodificador 12: .212</p><p>Fonte: HIRATA, 2005.</p><p>Figura 5: Decodificador em estrutura de árvore.</p><p>Fonte: HIRATA, 2005.</p><p>3. Referências</p><p>[1] GOMIDE, Anamaria; STOLFI, Jorge. Elementos de Matemática Discreta para</p><p>Computação, 2011.</p><p>[2] VIEIRA, Fábia Magali Santos. Álgebra booleana. Educação & Tecnologia, [S.l.], v. 5, n.</p><p>1, maio 2012.</p><p>[3] CARVALHO, Magda Costa; SANTOS, Ana Isabel; SEQUEIRA, Renata. Os diagramas</p><p>de Venn como recurso filosófico no jardim de infância. Educação e Filosofia, v. 31, n. 62, p.</p><p>727-750, 2017.</p><p>[4] SANTOS, P. D. B. Relação entre o máximo divisor comum, o mínimo múltiplo comum e</p><p>o diagrama de Venn. 2017. 83 f. Dissertação (Mestrado em Matemática em Rede Nacional) -</p><p>Universidade Federal de Goiás, Goiânia, 2017.</p><p>[5] GONÇALVES, Bernardo. "Álgebra Booleana." Universidade Federal de Espírito Santo:</p><p>Laboratório de Informática. Vitória (2014).</p><p>[6] HIRATA, Nina ST. Algebra Booleana e Aplicações, 2005.</p><p>[7] LIPSCHUTZ, Seymour; LIPSON, Marc. Matemática discreta: Coleção schaum.</p><p>Bookman Editora, 2013.</p>