AB-Algebra-Boole-Simplificacao-Circuitos
123 pág.

AB-Algebra-Boole-Simplificacao-Circuitos


DisciplinaOrganização de Computadores4.212 materiais77.468 seguidores
Pré-visualização7 páginas
José Augusto Baranauskas
Departamento de Computação e Matemática \u2013 FFCLRP-USP
augusto@usp.br
http://dcm.fmrp.usp.br/~augusto
Álgebra de Boole e Simplificação 
de Circuitos Lógicos
\ufffd Nesta apresentação serão 
vistos os postulados e 
propriedades e formas 
canônicas de expressões 
booleanas
\ufffd Além disso, serão vistas 
duas forma de simplificar 
circuitos
\ufffd Fatoração
\ufffd Diagramas de Veitch-
Karnaugh
2
Motivação
\ufffdComo visto, os circuitos lógicos 
correspondem (executam) expressões 
booleanas, as quais representam 
problemas no mundo real
\ufffdPorém, os circuitos gerados por tabelas 
verdade muitas vezes admitem 
simplificações, o que reduz o número de 
portas lógicas; essa redução diminui o grau 
de dificuldade na montagem e custo do 
sistema digital
3
Motivação
\ufffdO estudo da simplificação de circuitos 
lógicos requer o conhecimento da álgebra 
de Boole, por meio de seus postulados, 
propriedades, equivalências, etc
\ufffdDe fato, na álgebra de Boole encontram-se 
os fundamentos da eletrônica digital de 
circutos
4
Constantes, Variáveis e 
Expressões
\ufffd Existem apenas duas constantes booleanas
\ufffd 0 (zero)
\ufffd 1 (um)
\ufffd Uma variável booleana é representada por letra e pode 
assumir apenas dois valores (0 ou 1)
\ufffd Exemplos: A, B, C
\ufffd Uma expressão booleana é uma expressão matemática 
envolvendo constantes e/ou variáveis booleanas e seu 
resultado assume apenas dois valores (0 ou 1)
\ufffd Exemplos: 
\ufffd S = A.B
\ufffd S = A+B.C
5
\ufffd Na álgebra booleana há postulados (axiomas) a 
partir dos quais são estabelecidas várias 
propriedades
\ufffd Existem várias propriedades da negação 
(complemento, inversor), adição (porta E) e soma 
(porta OU)
\ufffd Estas propriedades podem ser verificadas como 
equivalências lógicas
\ufffd Para demonstrar cada uma, basta utilizar as 
tabelas-verdade, constatando a equivalência
Postulados & Propriedades
6
Postulados
\ufffd Complemento
\ufffd Se A=0 então \u100=1
\ufffd Se A=1 então \u100=0
\ufffd Notações alternativas
\ufffd \u100 = A\u2019
\ufffd \u100 = ¬ A
\ufffd B.C = (B.C)\u2019
\ufffd Adição
\ufffd 0 + 0 = 0
\ufffd 0 + 1 = 1
\ufffd 1 + 0 = 1
\ufffd 1 + 1 = 1
\ufffd Multiplicação
\ufffd 0 . 0 = 0
\ufffd 0 . 1 = 0
\ufffd 1 . 0 = 0
\ufffd 1 . 1 = 1
7
Propriedades
Propriedade Complemento Adição Multiplicação
Identidade \u100 = A
A + 0 = A A . 0 = 0
A + 1 = 1 A . 1 = A
A + A = A A . A = A
A + \u100 = 1 A . \u100 = 0
Comutativa A + B = B + A A . B = B . A
Associativa
A+(B+C) = (A+B)+C
= A+B+C
A.(B.C) = (A.B).C = 
A.B.C
Distributiva
A+(B.C) 
= 
(A+B) . (A+C)
A.(B+C) 
= 
A.B + A.C
8
Propriedades 
\ufffd Absorção
\ufffd A + (A.B) = A
\ufffd A . (A+B) = A
\ufffd Outras Identidades
\ufffd A + \u100.B = A + B
\ufffd (A+B).(A+C) = A + B.C
\ufffd De Morgan
\ufffd (A.B)\u2019 = \u100 + \ufffd
\ufffd (A+B)\u2019 = \u100 . \ufffd
\ufffd De Morgan se estende para n variáveis
\ufffd (A.B. ... . n)\u2019 = \u100 + \ufffd + ... + \ufffd
\ufffd (A+B+ ... +n)\u2019 = \u100 . \ufffd . ... . \ufffd
9
Exercício
\ufffd Mostre, usando simplificação por postulados e 
propriedades, ou seja, por transformações 
algébricas que:
\ufffd A+A.B = A
\ufffd A.(A+B) = A
10
Solução
\ufffd A+A.B = A
\ufffd A + A.B
\ufffd = A.(1+B) distributiva
\ufffd = A.(1) identidade da adição
\ufffd = A identidade da multiplicação
\ufffd A.(A+B) = A
\ufffd A.(A+B)
\ufffd = (A.A) + (A.B) distributiva
\ufffd = A + (A.B) identidade da multiplicação
\ufffd = A pela prova do exercício acima
11
Exercício
\ufffd Idem ao exercício anterior
\ufffd A + \u100.B = A + B
\ufffd (A+B).(A+C) = A + B.C
12
Solução
\ufffd A + \u100.B = A + B
\ufffd A + \u100.B = (A + \u100.B)\u2019\u2019 identidade do complemento
\ufffd = (\u100 . (\u100.B)\u2019)\u2019 = (\u100 . (A + \ufffd))\u2019 De Morgan
\ufffd = (\u100.A + \u100.\ufffd)\u2019 distributiva
\ufffd = (0 + \u100.\ufffd)\u2019 identidade da multiplicação
\ufffd = (\u100.\ufffd)\u2019 identidade da adição
\ufffd = A + B De Morgan
\ufffd A + \u100.B = A + B
\ufffd A + \u100.B = (A + \u100).(A+ B) distributiva \u3b1+\u3b2.\u3b3= (\u3b1+\u3b2) .(\u3b1+\u3b3)
\ufffd = 1.(A+B) identidade da adição
\ufffd = A + B identidade da multiplicação
13
Solução
\ufffd (A+B).(A+C) = A + B.C
\ufffd (A+B).(A+C)
\ufffd = A.A + A.C + B.A + B.C distributiva
\ufffd = A.A + A.C + A.B + B.C comutativa
\ufffd = A + A.C + A.B + B.C identidade da multiplicação
\ufffd = A + A.(C+B) + B.C distributiva
\ufffd = A.(1 + (C+B)) + B.C distributiva
\ufffd = A.(1) + B.C identidade da adição
\ufffd = A + B.C identidade da multiplicação
14
Simplificação de Expressões 
Booleanas
\ufffdUsando a álgebra booleana é possível 
simplificar expressões
\ufffdComo cada circuito corresponde a uma 
expressão, simplificações de expressões 
significam em simplificações de circuitos
\ufffdHá duas formas para simplificar expressões
\ufffd Fatoração
\ufffd Mapas de Veitch-Karnaugh
\ufffdVeremos, a seguir, o processo de fatoração
15
Fatoração
\ufffd Consiste na aplicação dos postulados e propriedades da 
álgebra booleana, com o objetivo de simplificar a 
expressão
\ufffd Por exemplo
\ufffd S = A.B.C + A.C\u2019 + A.B\u2019
\ufffd = A.(B.C + C\u2019 + B\u2019) distributiva
\ufffd = A.(B.C + (C\u2019 + B\u2019)) associativa
\ufffd = A.(B.C + ( (C\u2019 + B\u2019)\u2019 )\u2019) identidade do complemento
\ufffd = A.(B.C + (C.B)\u2019) De Morgan
\ufffd = A.(B.C + (B.C)\u2019 ) comutativa
\ufffd = A.(1) identidade da adição (D+ð=1)
\ufffd = A identidade da multiplicação
16
Fatoração
\ufffd Portanto, 
\ufffd A.B.C + A.C\u2019 + A.B\u2019 = A
\ufffd Essa expressão 
mostra a importância 
da simplificação de 
expressões e a 
consequente 
minimização do 
circuito, sendo o 
resultado final igual ao 
da variável A
\ufffd Circuito antes da simplificação
\ufffd Circuito após simplificação
A
B
C
A
C
A
B
S
A S
17
Exercício
\ufffdSimplifique as expressões
\ufffd S = A\u2019.B\u2019.C\u2019 + A\u2019.B.C\u2019 + A.B\u2019.C
\ufffd S = \u100.\ufffd + \u100.B
18
Solução
\ufffdSimplifique as expressões
\ufffd S = A\u2019.B\u2019.C\u2019 + A\u2019.B.C\u2019 + A.B\u2019.C
\ufffd= A\u2019.C\u2019.B\u2019 + A\u2019.C\u2019.B + A.B\u2019.C
\ufffd= A\u2019.C\u2019.(B\u2019 + B) + A.B\u2019.C
\ufffd= A\u2019.C\u2019.(1) + A.B\u2019.C
\ufffd= A\u2019.C\u2019 + A.B\u2019.C
\ufffd S = \u100.\ufffd + \u100.B
\ufffd= \u100.(\ufffd+B)
\ufffd= \u100.(1)
\ufffd= \u100
19
Exercício
\ufffdSimplifique as expressões
\ufffd S = A\u2019.B\u2019.C\u2019 + A\u2019.B.C + A\u2019.B.C\u2019 + A.B\u2019.C\u2019 + 
A.B.C\u2019
\ufffd S = (A+B+C).(\u100+\ufffd+C)
20
Solução
\ufffd S = A\u2019.B\u2019.C\u2019 + A\u2019.B.C + A\u2019.B.C\u2019 + A.B\u2019.C\u2019 + A.B.C\u2019
\ufffd = A\u2019.B\u2019.C\u2019 + A\u2019.B.C + A\u2019.B.C\u2019 + A.B\u2019.C\u2019 + A.B.C\u2019
\ufffd = A\u2019.B.C + (A\u2019.B\u2019 + A\u2019.B + A.B\u2019 + A.B).C\u2019
\ufffd = A\u2019.B.C + (A\u2019.B\u2019 + A\u2019.B + A.B\u2019 + A.B).C\u2019
\ufffd = A\u2019.B.C + (A\u2019.(B\u2019 + B) + A.(B\u2019 + B)).C\u2019
\ufffd = A\u2019.B.C + (A\u2019.(1) + A.(1)).C\u2019
\ufffd = A\u2019.B.C + (A\u2019 + A).C\u2019
\ufffd = A\u2019.B.C + (1).C\u2019
\ufffd = A\u2019.B.C + C\u2019 identidade X+(X\u2019.Y) = X+Y
\ufffd = A\u2019.B + C\u2019
\ufffd S = (A+B+C).(\u100+\ufffd+C)
\ufffd = A.\u100 + A.\ufffd + A.C + B.\u100 + B.\ufffd + B.C + C.\u100 + C.\ufffd + C.C
\ufffd = 0 + A.\ufffd + A.C + B.\u100 + 0 + B.C + C.\u100 + C.\ufffd + C
\ufffd = A.\ufffd + B.\u100 + A.C + B.C + C.\u100 + C.\ufffd + C
\ufffd = A.\ufffd + B.\u100 + C.(A + B + \u100 + \ufffd + 1)
\ufffd = A.\ufffd + B.\u100 + C.(1)
\ufffd = A.\ufffd + B.\u100 + C
21
Formas Normais (Canônicas)
\ufffdToda expressão booleana pode ser escrita 
em uma forma padronizada, denominada 
forma normal ou forma canônica
\ufffdDuas formas normais são
\ufffd Forma Normal Conjuntiva (FNC), Produto de 
Somas ou Produto de Maxtermos
\ufffd Forma Normal Disjuntiva (FND), Soma de 
Produtos ou Soma de Mintermos
22
Maxtermos e Mintermos
\ufffd Maxtermos (ou maxitermos)
\ufffd Variável com valor 0 é deixada 
intacta
\ufffd Variável com valor 1 é alterada 
pela sua negação
\ufffd Variáveis de uma mesma linha 
são conectadas por + (adição)
\ufffd Mintermos (ou minitermos)
\ufffd Variável com valor 1 é deixada 
intacta
\ufffd Variável com valor 0 é alterada 
pela sua negação
\ufffd Variáveis de uma mesma linha 
são conectadas por .
(multiplicação)
A B C Maxtermo Mintermo
0 0 0 A+B+C \u100.\ufffd.\ufffd
0 0 1 A+B+\ufffd \u100.\ufffd.C
0 1 0 A+\ufffd+C \u100.B.\ufffd
0 1 1 A+\ufffd+\ufffd \u100.B.C
1 0 0 \u100+B+C A.\ufffd.\ufffd
1 0 1 \u100+B+\ufffd A.\ufffd.C
1 1 0 \u100+\ufffd+C A.B.\ufffd
1 1 1 \u100+\ufffd+\ufffd A.B.C
23
Forma Normal Disjuntiva
\ufffd Mintermo (ou minitermo) é o termo produto associado 
à cada linha da tabela verdade, no qual todas as variáveis 
de entrada estão presentes
\ufffd Dado um dado mintermo, se substituirmos os valores das 
variáveis associadas, obteremos 1