Circuitos Digitais - Álgebra Booleana

Boolean Algebraé uma álgebra que lida com números binários e variáveis ​​binárias. Por isso, também é chamado de Álgebra Binária ou Álgebra lógica. Um matemático chamado George Boole desenvolveu esta álgebra em 1854. As variáveis ​​usadas nesta álgebra também são chamadas de variáveis ​​booleanas.

A faixa de tensões correspondente à lógica 'Alta' é representada por '1' e a faixa de tensões correspondente à lógica 'Baixa' é representada por '0'.

Postulados e leis básicas da álgebra booleana

Nesta seção, vamos discutir sobre os postulados booleanos e as leis básicas que são usados ​​na álgebra booleana. Eles são úteis para minimizar funções booleanas.

Postulados Booleanos

Considere os números binários 0 e 1, a variável booleana (x) e seu complemento (x '). A variável booleana ou o complemento dela é conhecido comoliteral. Os quatro possiveislogical OR operações entre esses literais e números binários são mostradas abaixo.

x + 0 = x

x + 1 = 1

x + x = x

x + x '= 1

Da mesma forma, os quatro possíveis logical AND operações entre esses literais e números binários são mostradas abaixo.

x.1 = x

x.0 = 0

xx = x

x.x '= 0

Esses são os postulados booleanos simples. Podemos verificar esses postulados facilmente, substituindo a variável booleana por '0' ou '1'.

Note- O complemento de complemento de qualquer variável booleana é igual à própria variável. ou seja, (x ')' = x.

Leis Básicas da Álgebra Booleana

A seguir estão as três leis básicas da Álgebra Booleana.

  • Lei comutativa
  • Lei associativa
  • Lei distributiva

Lei comutativa

Se qualquer operação lógica de duas variáveis ​​booleanas der o mesmo resultado, independentemente da ordem dessas duas variáveis, então essa operação lógica é considerada Commutative. As operações lógicas OR & lógicas AND de duas variáveis ​​booleanas x e y são mostradas abaixo

x + y = y + x

xy = yx

O símbolo '+' indica operação lógica OR. Da mesma forma, o símbolo '.' indica operação lógica AND e é opcional para representar. A lei comutativa obedece para operações lógicas OR e AND lógicas.

Direito Associativo

Se uma operação lógica de quaisquer duas variáveis ​​booleanas é realizada primeiro e, em seguida, a mesma operação é realizada com a variável restante dá o mesmo resultado, então essa operação lógica é considerada Associative. As operações lógicas OR e AND lógicas de três variáveis ​​booleanas x, y e z são mostradas abaixo.

x + (y + z) = (x + y) + z

x. (yz) = (xy) .z

A lei associativa obedece a operações lógicas OR e AND lógicas.

Lei Distributiva

Se qualquer operação lógica pode ser distribuída para todos os termos presentes na função booleana, então essa operação lógica é considerada Distributive. A distribuição das operações lógicas OR e AND lógico de três variáveis ​​booleanas x, y e z são mostradas abaixo.

x. (y + z) = xy + xz

x + (yz) = (x + y). (x + z)

A lei distributiva obedece a operações lógicas OR e AND lógicas.

Estas são as leis básicas da álgebra booleana. Podemos verificar essas leis facilmente, substituindo as variáveis ​​booleanas por '0' ou '1'.

Teoremas da Álgebra Booleana

Os dois teoremas a seguir são usados ​​na álgebra booleana.

  • Teorema da dualidade
  • Teorema de DeMorgan

Teorema da Dualidade

Este teorema afirma que o dualda função booleana é obtido trocando o operador lógico AND com o operador lógico OR e zeros com uns. Para cada função booleana, haverá uma função Dual correspondente.

Vamos fazer as equações booleanas (relações) que discutimos na seção de postulados booleanos e leis básicas em dois grupos. A tabela a seguir mostra esses dois grupos.

Grupo 1 Grupo 2
x + 0 = x x.1 = x
x + 1 = 1 x.0 = 0
x + x = x xx = x
x + x '= 1 x.x '= 0
x + y = y + x xy = yx
x + (y + z) = (x + y) + z x. (yz) = (xy) .z
x. (y + z) = xy + xz x + (yz) = (x + y). (x + z)

Em cada linha, existem duas equações booleanas e são duais entre si. Podemos verificar todas essas equações booleanas do Grupo1 e Grupo2 usando o teorema da dualidade.

Teorema de DeMorgan

Este teorema é útil para encontrar o complement of Boolean function. Ele afirma que o complemento do OR lógico de pelo menos duas variáveis ​​booleanas é igual ao AND lógico de cada variável complementada.

O teorema de DeMorgan com 2 variáveis ​​booleanas x e y pode ser representado como

(x + y) '= x'.y'

O dual da função booleana acima é

(xy) '= x' + y '

Portanto, o complemento do AND lógico de duas variáveis ​​booleanas é igual ao OR lógico de cada variável complementada. Da mesma forma, podemos aplicar o teorema de DeMorgan para mais de 2 variáveis ​​booleanas também.

Simplificação de funções booleanas

Até agora, discutimos os postulados, leis básicas e teoremas da álgebra booleana. Agora, vamos simplificar algumas funções booleanas.

Exemplo 1

Deixe-nos simplify a função booleana, f = p'qr + pq'r + pqr '+ pqr

Podemos simplificar essa função em dois métodos.

Method 1

Dada a função booleana, f = p'qr + pq'r + pqr '+ pqr.

Step 1- No primeiro e segundo termos r é comum e no terceiro e quarto termos pq é comum. Então, pegue os termos comuns usandoDistributive law.

⇒ f = (p'q + pq ') r + pq (r' + r)

Step 2- Os termos presentes no primeiro parêntese podem ser simplificados para a operação Ex-OR. Os termos presentes no segundo parêntese podem ser simplificados para '1' usandoBoolean postulate

⇒ f = (p ⊕q) r + pq (1)

Step 3- O primeiro termo não pode ser mais simplificado. Mas, o segundo termo pode ser simplificado para pq usandoBoolean postulate.

⇒ f = (p ⊕q) r + pq

Portanto, a função booleana simplificada é f = (p⊕q)r + pq

Method 2

Dada a função booleana, f = p'qr + pq'r + pqr '+ pqr.

Step 1 - Use o Boolean postulate, x + x = x. Isso significa que a operação lógica OR com qualquer variável booleana 'n' vezes será igual à mesma variável. Então, podemos escrever o último termo pqr mais duas vezes.

⇒ f = p'qr + pq'r + pqr '+ pqr + pqr + pqr

Step 2 - Use Distributive lawpara 1º e 4º termos, 2º e 5º termos, 3º e 6º termos.

⇒ f = qr (p '+ p) + pr (q' + q) + pq (r '+ r)

Step 3 - Use Boolean postulate, x + x '= 1 para simplificar os termos presentes em cada parêntese.

⇒ f = qr (1) + pr (1) + pq (1)

Step 4 - Use Boolean postulate, x.1 = x para simplificar os três termos acima.

⇒ f = qr + pr + pq

⇒ f = pq + qr + pr

Portanto, a função booleana simplificada é f = pq + qr + pr.

Portanto, obtivemos duas funções booleanas diferentes após simplificar a função booleana fornecida em cada método. Funcionalmente, essas duas funções booleanas são iguais. Portanto, com base no requisito, podemos escolher uma dessas duas funções booleanas.

Exemplo 2

Deixe-nos encontrar o complement da função booleana, f = p'q + pq '.

O complemento da função booleana é f '= (p'q + pq') '.

Step 1 - Use o teorema de DeMorgan, (x + y) '= x'.y'.

⇒ f '= (p'q)'. (Pq ')'

Step 2 - Use o teorema de DeMorgan, (xy) '= x' + y '

⇒ f '= {(p') '+ q'}. {P '+ (q') '}

Step3 - Use o postulado booleano, (x ')' = x.

⇒ f '= {p + q'}. {P '+ q}

⇒ f '= pp' + pq + p'q '+ qq'

Step 4 - Use o postulado booleano, xx '= 0.

⇒ f = 0 + pq + p'q '+ 0

⇒ f = pq + p'q '

Portanto, o complement da função booleana, p'q + pq 'é pq + p’q’.