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)

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	1	x'y'z	m ₁
0	1	0	x'yz '	m ₂
0	1	1	x'yz	m ₃
1	0	0	xy'z '	m ₄
1	0	1	xy'z	m ₅
1	1	0	xyz '	m ₆
1	1	1	xyz	m ₇

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).

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	1	x + y + z '	M ₁
0	1	0	x + y '+ z	H ₂
0	1	1	x + y '+ z'	M ₃
1	0	0	x '+ y + z	M ₄
1	0	1	x '+ y + z'	M ₅
1	1	0	x '+ y' + z	M ₆
1	1	1	x '+ y' + z '	M ₇

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