Álgebra booleana: história, teoremas e postulados, exemplos - Ciência - 2023

Contente

o álgebra booleana o Álgebra booleana é a notação algébrica usada para o tratamento de variáveis binárias. Abrange os estudos de qualquer variável que tenha apenas 2 desfechos possíveis, complementares e mutuamente exclusivos. Por exemplo, variáveis cuja única possibilidade é verdadeira ou falsa, correta ou incorreta, ativada ou desativada são a base do estudo da álgebra booleana.

A álgebra booleana é a base da eletrônica digital, o que a torna bastante presente hoje. É regido pelo conceito de portas lógicas, onde operações conhecidas na álgebra tradicional são afetadas de forma notável.

História

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

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

A intenção de George Boole era definir, por meio das propriedades da álgebra, as expressões da lógica proposicional necessárias para lidar com variáveis do tipo binário.

Em 1854, as seções mais significativas da álgebra booleana foram publicadas no livro “Uma investigação das leis do pensamento nas quais se baseiam as teorias matemáticas da lógica e da probabilidade ”.

Este curioso título seria resumido mais tarde como “As leis do pensamento ”(“ As leis do pensamento ”). O título ganhou fama devido à atenção imediata que recebeu da comunidade matemática da época.

Em 1948, Claude Shannon aplicou-o ao projeto de circuitos elétricos de comutação biestáveis. Isso serviu como uma introdução à aplicação da álgebra booleana em todo o esquema eletrônico-digital.

Estrutura

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

- Operação AND ou conjunção. Representado por um ponto (.). Sinônimo do produto.

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

- NÃO operação ou negação. Representado pelo prefixo NÃO (NÃO A). Também é conhecido como complemento.

Se em um conjunto A 2 leis de composição interna são definidas denotadas como produto e soma (. +), Diz-se que o triplo (A. +) é uma álgebra booleana se e somente se o referido triplo atende à condição de ser uma rede distributiva.

Para definir uma rede distributiva, as condições de distribuição devem ser atendidas entre as operações dadas:

. é distributiva em relação à soma + a. (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 A devem ser binários, tendo, portanto, valores de universo ou vazio.

Formulários

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

Desde a elaboração de painéis elétricos, passando pela transmissão de dados, até chegar à programação em diferentes linguagens, podemos frequentemente encontrar a álgebra booleana em todos os tipos de aplicações digitais.

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

Postulados

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

Soma (+)

O operadorOUcujo elemento lógico é a união (U) é definido para variáveis binárias da seguinte forma:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 1

Produtos (.)

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

0 . 0 = 0

0 . 1 = 0

1 . 0 = 0

1 . 1 = 1

Oposto (NÃO)

O operadorNÃ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 suas contrapartes na álgebra convencional. Isso se deve 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 conjunto binário.

Teoremas

Regra zero e unidade

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

0 + A = A

1 + A = 1

0 A = 0

1 A = A

Poderes iguais ou idempotência

Operações entre variáveis iguais são definidas como:

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

Qualquer dupla negação será considerada como variável natural.

NÃO (NÃO A) = A

Comutativo

A + B = B + A; Comutatividade da soma.

PARA . B = B. PARA ; Comutatividade do produto.

Associativo

A + (B + C) = (A + B) + C = A + B + C; Associatividade da soma.

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

Distributiva

A + (B. C) = (A + B). (A + C); Distributividade da 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 A. B

(A + B). (A + NÃO B) = A

A + A. B = A

A + NÃO A. 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 tratam de pares de variáveis que interagem entre as operações definidas da álgebra booleana (+.).

NÃO (A. B) = NÃO A + NÃO B

NÃO (A + B) = NÃO A. NÃO SER

A + B = NÃO (NÃO A + NÃO B)

PARA . B = NÃO (NÃO A. NÃO B)

Dualidade

Todos os postulados e teoremas possuem a faculdade da dualidade. Isso implica que, trocando as variáveis e operações, a proposição resultante é verificada. Ou seja, ao trocar 0 por 1 e AND por OR ou vice-versa; uma expressão é criada que também será completamente válida.

Por exemplo, se o postulado é tomado

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 funções lógicas. Consiste em um arranjo bidimensional semelhante às tabelas de verdade da lógica proposicional. Os dados das tabelas de verdade podem ser capturados diretamente no mapa de Karnaugh.

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

Proposto em 1953 por Maurice Karnaugh, estabeleceu-se como uma ferramenta fixa no campo da álgebra booleana, pois sua implementação sincroniza o potencial humano com a necessidade de simplificar as expressões booleanas, aspecto fundamental na fluidez dos processos digitais.

Exemplos

A álgebra booleana é usada para reduzir as portas lógicas em um circuito, onde a prioridade é trazer a complexidade ou nível do circuito para sua expressão mais baixa 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 à 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); Fatorando A com um fator comum.

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

(NÃO A. NÃO B). [NÃO A. NÃO (NÃO B)];

Pelo teorema de Morgan NÃO (A + B) = NÃO A. NÃO SER

(NÃO A. NÃO B). (NÃO A. B); Pelo teorema de negação dupla NOT (NOT A) = A

NÃO A. NÃO SER. NÃO A. B; Agrupamento algébrico.

NÃO A. NÃO A. NÃO SER. B; Comutatividade do produto A. B = B. PARA

NÃO A. NÃO SER. B; Pelo teorema A. A = A

NÃO A. 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; Fatoração (A. C) com um fator comum.

PARA . C. (1) + NÃO A; Pelo teorema A + NÃO A = 1

PARA . C + NÃO A; Pela regra do teorema zero e da unidade 1. A = A

NÃO A + C ; Pela lei do Morgan A + NOT A. 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 NOT (NOT A) = A por involução.

Simplifique a função lógica

NÃO A. NÃO SER. NÃO C + NÃO A. NÃO SER. C + NÃO A. NÃO C até sua expressão mínima

NÃO A. NÃO SER. (NÃO C + C) + NÃO A. NÃO C; Fatoração (NÃO A. NÃO B) com fator comum

NÃO A. NÃO SER. (1) + NÃO A. NÃO C; Pelo teorema A + NÃO A = 1

(NÃO A. NÃO B) + (NÃO A. NÃO C);Pela regra do teorema zero e da unidade 1. A = A

NÃO A (NÃO B + NÃO C); Fatorando NÃO A com um fator comum

NÃO A. NÃO (B. C); Pelas leis de Morgan, NÃO (A. B) = NÃO A + NÃO B

NÃO [A + (B. C)] Pelas leis de Morgan, NÃO (A. B) = NÃO A + NÃO B

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

Simplifique a função lógica em sua forma mais simples

(A. NÃO B. C + A. NÃO B. B. D + NÃO A. NÃO B). C

(A. NÃO B. C + A. 0. D + NÃO A. NÃO B). C; Pelo teorema A. NÃO A = 0

(A. NÃO B. C + 0 + NÃO A. NÃO B). C; Pelo teorema A. 0 = 0

(A. NÃO B. C + NÃO A. NÃO B). C; Pelo teorema A + 0 = A

PARA . NÃO SER. C. C + NÃO A. NÃO SER. C; Pela distributividade do produto em relação à soma

PARA . NÃO SER. C + NÃO A. NÃO SER. C; Pelo teorema A. A = A

NÃO SER. C (A + NÃO A) ; Fatoração (NÃO B. C) com fator comum

NÃO SER. C (1); Pelo teorema A + NÃO A = 1

NÃO SER. C; Pela regra do teorema zero e da unidade 1. A = A

Referências

Álgebra booleana e suas aplicações J. Eldon Whitesitt. Continental Publishing Company, 1980.
Matemática e Engenharia em Ciência da Computação. Christopher J. Van Wyk. Instituto de Ciências e Tecnologia da Computação. National Bureau of Standards. Washington, D.C. 20234
Matemática para Ciência da Computação. Eric Lehman. Google Inc.
F Thomson Leighton Departamento de Matemática e Ciência da Computação e Laboratório de IA, Massachussetts Institute of Technology; Akamai Technologies.
Elementos de análise abstrata. Mícheál O’Searcoid PhD. Departamento de matemática. Faculdade universitária Dublin, Beldfield, Dublind.
Introdução à Lógica e à Metodologia das Ciências Dedutivas. Alfred Tarski, New York Oxford. Imprensa da Universidade de Oxford.