História da Álgebra Booleana, Teoremas e Postulados, Exemplos

Ele álgebra booleana Ó álgebra de Boole é a notação algébrica usada para o tratamento de variáveis ​​binárias. Abrange estudos de qualquer variável que tenha apenas 2 resultados possíveis, complementares e exclusivos. Por exemplo, as variáveis ​​cuja única possibilidade é verdadeira ou falsa, correta ou incorreta;.

Álgebra booleana constitui a base da eletrônica digital, o que a torna bastante presente na contemporaneidade. É governado pelo conceito de portões lógicos, onde as operações conhecidas na álgebra tradicional são notavelmente afetadas.

Fonte: pexels.com

[TOC]

História

A álgebra booleana foi introduzida em 1854 pelo matemático inglês George Boole (1815 - 1864), que era um estudioso auto -levantado da época. Sua preocupação surgiu de uma disputa existente entre Augustus de Morgan e William Hamilton, sobre os parâmetros que definem esse sistema lógico.

George Boole argumentou que a definição de valores numéricos 0 e 1 corresponde, no campo da lógica, para a interpretação Nada e universo respectivamente.

A intenção de George Boole era definir, através das propriedades da álgebra, as expressões da lógica proposicional necessária para lidar com variáveis ​​binárias.

Em 1854, as seções mais significativas da álgebra booleana são publicadas no livro "Uma investigação das leis de pensamento sobre as teorias matemáticas da lógica e da probabilidade se baseiam ”.

Este título curioso seria resumido mais tarde como "As leis do pensamento "(" as leis do pensamento "). O título saltou para a fama devido à atenção imediata que tinha da comunidade matemática da época.

Em 1948. Isso serviu como uma introdução à aplicação da álgebra booleana em todo o esquema de digital eletrônico.

Estrutura

Os valores elementares nesse tipo de álgebra são 0 e 1, que correspondem a falsos e verdadeiros, respectivamente. As operações fundamentais na álgebra booleana são 3:

- E operação de conjunção. Representado por um ponto ( . ). Sinônimo do produto.

- Ou ou operação de disjunção. Representado por uma cruz ( +) .Sinônimo da soma.

- Sem operação ou negação. Representado pelo prefixo não (não a). Também é conhecido como complemento.

Se em um conjunto, 2 leis de composição interna denotadas como produto e soma forem definidas ( .  + ), diz -se que a lista (um . + ) É uma álgebra booleana se e somente se a referida lista atender à condição de ser um retículo distributivo.

Pode atendê -lo: números racionais: propriedades, exemplos e operações

Para definir um retículo distributivo, as condições de distribuição entre as operações fornecidas devem ser atendidas:

. é distributivo em relação à soma +                   para . (B + C) = (A . b) + (A . c)

+ é distributivo em relação ao produto.                  A + (B . c) = (a +b) . (A + c)

Os elementos que compõem o conjunto devem ser binários, tendo valores de Universo ou vazio.

Formulários

Seu maior cenário de aplicação é a filial digital, onde serve para estruturar os circuitos que compõem as operações lógicas envolvidas. A arte da simplicidade dos circuitos para otimizar os processos é o resultado da aplicação e prática corretas da álgebra booleana.

Desde a elaboração de quadros elétricos, através da transmissão de dados, até atingir a programação em diferentes idiomas, podemos frequentemente encontrar a álgebra de Boole em todos os tipos de aplicações digitais.

As variáveis ​​booleanas são muito comuns na estrutura de programação. Dependendo da linguagem de programação usada, haverá operações estruturais do código que usam essas variáveis. Os argumentos condicionais e de cada idioma admitem variáveis ​​booleanas para definir os processos.

Postulados

Existem teoremas que governam as leis lógicas estruturais da álgebra booleana. Da mesma forma, eles são postulados para saber os possíveis resultados em diferentes combinações de variáveis ​​binárias, de acordo com a operação realizada.

Soma (+)

O operador Ou cujo elemento lógico é Union (U) é definido para variáveis ​​binárias da seguinte forma:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 1

Produtos (.)

O operador E cujo elemento lógico é a interseção (∩) é definida para variáveis ​​binárias da seguinte forma:

0 . 0 = 0

0 . 1 = 0

1 . 0 = 0

1 . 1 = 1

Oposto (não)

O operador Não cujo elemento lógico é o complemento (x) 'é definido para variáveis ​​binárias da seguinte forma:

Não 0 = 1

Não 1 = 0

Muitos dos postulados diferem de seus equivalentes na álgebra convencional. Isto é devido ao domínio das variáveis. Por exemplo, a adição de elementos do universo na álgebra booleana (1 + 1) não pode produzir o resultado convencional de 2, porque não pertence aos elementos do complexo binário.

Teoremas

Regra e unidade zero

Qualquer operação simples que envolva um elemento com variáveis ​​binárias é definida:

0 + a = a

1 + a = 1

0 . A = 0

1 . A = a

Poderes iguais ou idemploynce

As operações entre variáveis ​​iguais são definidas como:

Pode servir a você: congruência: figuras congruentes, critérios, exemplos, exercícios

A + A = A

PARA . A = a

Complementação

Qualquer operação entre uma variável e seu complemento é definida como:

A + não a = 1

PARA . Não a = 0

Involução ou dupla negação

Toda a dupla negação será considerada a variável natural.

Não (não a) = a

Comutativo

A + b = b + a; Verão da soma.

PARA . B = b . PARA ; Comutividade do produto.

Associativo

A + (b + c) = (a + b) + c = a + b + c; Soma Associatividade.

PARA . (B . C) = (A . B) . C = a . B . C; Associatividade do produto.

Distributivo

A + (B . C) = (a + b) . (A + c); Distribua a soma em relação ao produto.

PARA . (B + C) = (A . B) + (a + c); Distributividade do produto em relação à soma.

Leis de absorção

Existem muitas leis de absorção entre várias referências, algumas das mais conhecidas são:

PARA . (A + b) = a

PARA . (Não a + b) = a . B

Não a (a + b) = não um . B

(A + b) . (A + não b) = a

A + a . B = a

A + não um . B = a + b

Não A + A . B = não a + b

PARA . B + a . Não B = A

Teorema de Morgan

São leis de transformação, que gerenciam pares de variáveis ​​que interagem entre as operações definidas da álgebra booleana ( + . ).

OBSERVAÇÃO . B) = não a + não b

Não (a +b) = não um . Não ser

A + b = não (não a + não b)

PARA . B = não (não um . Não ser)

Dualidade

Todos os postulados e teoremas têm o poder da dualidade. Isso implica que, ao trocar as variáveis ​​e operações, a proposição resultante é verificada. Isto é, ao trocar 0 por 1 e e / ou vice -versa; É criada uma expressão que também será completamente válida.

Por exemplo, se você pegar o postulado

1 . 0 = 0

E a dualidade é aplicada

0 + 1 = 1

Outro postulado perfeitamente válido é obtido.

Mapa de Karnaugh

O mapa de Karnaugh é um diagrama usado na álgebra booleana para simplificar as funções lógicas. Consiste em um arranjo bidimensional semelhante às tabelas da verdade da lógica proposicional. Os dados de tabelas reais podem ser diretamente incorporados no mapa de Karnaugh.

O mapa de Karnaugh pode abrigar processos de até 6 variáveis. Para funções com um número maior de variáveis, o uso de software para simplificar o processo é recomendado.

Proposto em 1953 por Maurice Karnaugh, foi estabelecido como uma ferramenta fixa no campo de Boole.

Exemplos

A álgebra booleana serve para reduzir as portas lógicas em um circuito, onde a prioridade é trazer a complexidade ou nível do circuito à sua expressão mínima possível. Isso se deve ao atraso computacional que cada porta supõe.

No exemplo a seguir, observaremos a simplificação de uma expressão lógica até sua expressão mínima, usando os teoremas e postulados da álgebra booleana.

Não (ab + a + b) . Não (a + não b)

Não [a (b + 1) + b] . Não (a + não b); Considerando o A com fator comum.

Pode atendê -lo: cálculo de abordagens usando diferenciais

Não [a (1) + b] . Não (a + não b); Pelo teorema A + 1 = 1.

Não (a + b) . Não (a + não b); Pelo teorema a . 1 = a

( OBSERVAÇÃO . Não ser) . [ OBSERVAÇÃO . Não (não b)];

Pelo teorema de Morgan não (a + b) = não um . Não ser

( OBSERVAÇÃO . Não ser) .  ( OBSERVAÇÃO . B); Por teorema de dupla negação não (não a) = a

OBSERVAÇÃO . Não ser . OBSERVAÇÃO . B; Grupo algébrico.

OBSERVAÇÃO . OBSERVAÇÃO . Não ser . B; Comutividade do produto para . B = b . PARA

OBSERVAÇÃO . Não ser . B; Pelo teorema a . A = a

OBSERVAÇÃO . 0; Pelo teorema a . Não a = 0

0; Pelo teorema a . 0 = 0

PARA . B . C + não A + A . Não ser . C

PARA . C . (B + não b) + não a; Fatorização (a . C) com fator comum.

PARA . C . (1) + não a; Pelo teorema A + não A = 1

PARA . C + não a; Por zero teorema da regra e unidade 1 . A = a

Não A + C ; Por lei de Morgan para + não um . B = a + b

Para esta solução, a lei de Morgan deve ser estendida para definir:

Não (não a) . C + não a = não a + c

Porque não (não a) = a por involução.

Simplifique a função lógica

OBSERVAÇÃO . Não ser . Não C + não é um . Não ser . C + não um . Não C até sua expressão mínima

OBSERVAÇÃO . Não ser . (Não C + C) + não é um . Não c; Fatorização (não um . Não b) com fator comum

OBSERVAÇÃO . Não ser . (1) + não um . Não c; Pelo teorema A + não A = 1

(OBSERVAÇÃO . Não b) + (não um . Não c);  Por zero teorema da regra e unidade 1 . A = a

Não a (não b + não c); Conseguir não um com fator comum

OBSERVAÇÃO . Não ser . C); Por leis de Morgan não (um . B) = não a + não b

Não [a + (b . C)] Por leis de Morgan não (um . B) = não a + não b

Qualquer uma das 4 opções em negrito representa uma solução possível para reduzir o nível do circuito

Simplifique a função lógica até sua expressão mínima

( PARA . Não ser .  C + a . Não ser . B . D+ não um . Não ser) . C

( PARA . Não ser . C + a . 0 . D + não um . Não ser) . C; Pelo teorema a . Não a = 0

( PARA . Não ser . C + 0 + não um . Não ser) . C; Pelo teorema a . 0 = 0

( PARA . Não ser . C + não um . Não ser) . C; Pelo teorema A + 0 = A

PARA . Não ser . C . C + não um . Não ser . C; Por distributividade do produto em relação à soma

PARA . Não ser . C + não um . Não ser . C; Pelo teorema a . A = a

Não ser . C (a + não a) ; Fatorização (não b . C) com fator comum

Não ser . C (1); Pelo teorema A + não A = 1

Não ser . C; Por zero teorema da regra e unidade 1 . A = a

Referências

1. Álgebra Booleana e seus J Applications. Eldon Whitesitt. Companhia Editorial Continental, 1980.
2. Matemática e Engenharia em Ciência da Computação. Christopher J. Van Wyk. Instituto de Ciências e Tecnologia de Computador. Bureau Nacional de Padrões. Washington, d. C. 20234
3. Matemática para Ciência da Computação. Eric Lehman. Google Inc.
   F Thomson Leighton Departamento de Matemática e Laboratório de Ciência da Computação e AI, Instituto de Tecnologia de Massachussetts; Akamai Technologies.
4. Elementos da análise abstrata. MÍCHEL O'SEARCOID PhD. Departamento de Matemática. University College Dublin, Beldfield, Dublind.
5.  Introdução à lógica e à metodologia das ciências dedutivas. Alfred Tarski, Nova York Oxford. imprensa da Universidade de Oxford.