Expressões e funções booleanas
Álgebra booleana é álgebra da lógica. Trata-se de variáveis que podem ter dois valores discretos, 0 (Falso) e 1 (Verdadeiro); e operações que têm significado lógico. O método mais antigo de manipulação da lógica simbólica foi inventado por George Boole e posteriormente veio a ser conhecido como Álgebra Booleana.
A álgebra booleana agora se tornou uma ferramenta indispensável na ciência da computação por sua ampla aplicabilidade na teoria de comutação, construção de circuitos eletrônicos básicos e projeto de computadores digitais.
Funções Booleanas
A Boolean functioné um tipo especial de função matemática $ f: X ^ n \ rightarrow X $ de grau n, onde $ X = \ lbrace {0, 1} \ rbrace $ é um domínio booleano en é um inteiro não negativo. Ele descreve como derivar a saída booleana de entradas booleanas.
Example- Seja, $ F (A, B) = A'B '$. Esta é uma função de grau 2 do conjunto de pares ordenados de variáveis booleanas para o conjunto $ \ lbrace {0, 1} \ rbrace $ onde $ F (0, 0) = 1, F (0, 1) = 0, F (1, 0) = 0 $ e $ F (1, 1) = 0 $
Expressões Booleanas
A Boolean expressionsempre produz um valor booleano. Uma expressão booleana é composta de uma combinação das constantes booleanas (verdadeiro ou falso), variáveis booleanas e conectivos lógicos. Cada expressão booleana representa uma função booleana.
Example - $ AB'C $ é uma expressão booleana.
Identidades Booleanas
Lei do Duplo Complemento
$ \ sim (\ sim A) = A $
Lei Complementar
$ A + \ sim A = 1 $ (forma OR)
$ A. \ sim A = 0 $ (forma E)
Lei Idempotente
$ A + A = A $ (formulário OR)
$ A. A = A $ (formulário E)
Lei da Identidade
$ A + 0 = A $ (formulário OR)
$ A. 1 = A $ (formulário E)
Lei de Dominância
$ A + 1 = 1 $ (forma OR)
$ A. 0 = 0 $ (forma E)
Lei comutativa
$ A + B = B + A $ (forma OR)
$ A. B = B. A $ (formulário E)
Direito Associativo
$ A + (B + C) = (A + B) + C $ (forma OR)
$ A. (B. C) = (A. B). C $ (formulário E)
Lei de Absorção
$ A. (A + B) = A $
$ A + (A. B) = A $
Lei de Simplificação
$ A. (\ sim A + B) = A. B $
$ A + (\ sim A. B) = A + B $
Lei Distributiva
$ A + (B. C) = (A + B). (A + C) $
$ A. (B + C) = (A. B) + (A. C) $
Lei De Morgan
$ \ sim (A. B) = \ sim A + \ sim B $
$ \ sim (A + B) = \ sim A. \ sim B $
Formas Canônicas
Para uma expressão booleana, existem dois tipos de formas canônicas -
- A forma de soma de mintermos (SOM)
- O produto de maxtermos (POM) formulário
A forma de Soma de Mintermos (SOM) ou Soma de Produtos (SOP)
Um mintermo é o produto de todas as variáveis tomadas em sua forma direta ou complementada. Qualquer função booleana pode ser expressa como uma soma de seus 1-mintermos e o inverso da função pode ser expressa como uma soma de seus 0-mintermos. Conseqüentemente,
F (lista de variáveis) = ∑ (lista de índices de 1 minuto)
e
F '(lista de variáveis) = ∑ (lista de índices de 0-mintermo)
| UMA | B | C | Prazo | Minterm |
|---|---|---|---|---|
| 0 | 0 | 0 | x'y'z ' | m 0 |
| 0 | 0 | 1 | x'y'z | m 1 |
| 0 | 1 | 0 | x'yz ' | m 2 |
| 0 | 1 | 1 | x'yz | m 3 |
| 1 | 0 | 0 | xy'z ' | m 4 |
| 1 | 0 | 1 | xy'z | m 5 |
| 1 | 1 | 0 | xyz ' | m 6 |
| 1 | 1 | 1 | xyz | m 7 |
Example
Seja $ F (x, y, z) = x 'y' z '+ xy' z + xyz '+ xyz $
Ou $ F (x, y, z) = m_0 + m_5 + m_6 + m_7 $
Conseqüentemente,
$ F (x, y, z) = \ sum (0, 5, 6, 7) $
Agora encontraremos o complemento de $ F (x, y, z) $
$ F '(x, y, z) = x' yz + x 'y' z + x 'yz' + xy 'z' $
Ou $ F '(x, y, z) = m_3 + m_1 + m_2 + m_4 $
Conseqüentemente,
$ F '(x, y, z) = \ sum (3, 1, 2, 4) = \ sum (1, 2, 3, 4) $
O formulário Produto de Maxtermos (POM) ou Produto de Soma (POS)
Um maxterm é a adição de todas as variáveis tomadas em sua forma direta ou complementada. Qualquer função booleana pode ser expressa como um produto de seus 0-maxtermos e o inverso da função pode ser expresso como um produto de seus 1-maxtermos. Conseqüentemente,
F (lista de variáveis) = $ \ pi $ (lista de índices 0-maxterm).
e
F '(lista de variáveis) = $ \ pi $ (lista de índices 1-maxterm).
| UMA | B | C | Prazo | Maxterm |
|---|---|---|---|---|
| 0 | 0 | 0 | x + y + z | M 0 |
| 0 | 0 | 1 | x + y + z ' | M 1 |
| 0 | 1 | 0 | x + y '+ z | H 2 |
| 0 | 1 | 1 | x + y '+ z' | M 3 |
| 1 | 0 | 0 | x '+ y + z | M 4 |
| 1 | 0 | 1 | x '+ y + z' | M 5 |
| 1 | 1 | 0 | x '+ y' + z | M 6 |
| 1 | 1 | 1 | x '+ y' + z ' | M 7 |
Exemplo
Seja $ F (x, y, z) = (x + y + z). (x + y + z '). (x + y '+ z). (x '+ y + z) $
Ou $ F (x, y, z) = M_0. M_1. M_2. M_4 $
Conseqüentemente,
$ F (x, y, z) = \ pi (0, 1, 2, 4) $
$ F '' (x, y, z) = (x + y '+ z'). (x '+ y + z'). (x '+ y' + z). (x '+ y' + z ') $
Ou $ F (x, y, z) = M_3. M_5. M_6. M_7 $
Conseqüentemente,
$ F '(x, y, z) = \ pi (3, 5, 6, 7) $
Portões lógicos
As funções booleanas são implementadas usando portas lógicas. A seguir estão as portas lógicas -
NOT Gate
Uma porta NOT inverte uma única entrada de bit em um único bit de saída.
| UMA | ~ A |
|---|---|
| 0 | 1 |
| 1 | 0 |
AND Gate
Uma porta AND é uma porta lógica que fornece uma saída alta apenas se todas as suas entradas forem altas, caso contrário, ela fornece uma saída baixa. Um ponto (.) É usado para mostrar a operação AND.
| UMA | B | AB |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
OR Gate
Uma porta OR é uma porta lógica que fornece alta saída se pelo menos uma das entradas for alta. Um sinal de mais (+) é usado para mostrar a operação OR.
| UMA | B | A + B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
NAND Gate
Uma porta NAND é uma porta lógica que fornece uma saída baixa apenas se todas as suas entradas forem altas, caso contrário, ela fornece uma saída alta.
| UMA | B | ~ (AB) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Portão NOR
Uma porta NOR é uma porta lógica que fornece uma saída alta se ambas as entradas forem baixas, caso contrário, ela fornece uma saída baixa.
| UMA | B | ~ (A + B) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
Portão XOR (OU Exclusivo)
Uma porta XOR é uma porta lógica que fornece uma saída alta se as entradas forem diferentes, caso contrário, ela fornece uma saída baixa.
| UMA | B | A⊕B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Portão X-NOR (NOR exclusivo)
Uma porta EX-NOR é uma porta lógica que fornece uma saída alta se as entradas são as mesmas, caso contrário, ela fornece uma saída baixa.
| UMA | B | A X-NOR B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |