Álgebra de Boole e Simplificação

Álgebra de Boole e Simplificação de Circuitos Lógicos
Nesta apresentação serão vistos os postulados e propriedades e formas canônicas de expressões booleanas Além disso, serão vistas duas forma de simplificar circuitos Fatoração
Diagramas de VeitchKarnaugh
José Augusto Baranauskas
Departamento de Computação e Matemática – FFCLRP-USP

[e-mail] http://dcm.fmrp.usp.br/~augusto Motivação
Como visto, os circuitos lógicos correspondem (executam) expressões booleanas, as quais representam problemas no mundo real
Poré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
2

Motivação
O estudo da simplificação de circuitos lógicos requer o conhecimento da álgebra de Boole, por meio de seus postulados, propriedades, equivalências, etc
De fato, na álgebra de Boole encontram-se os fundamentos da eletrônica digital de circutos 3

Constantes, Variáveis e
Expressões
Existem apenas duas constantes booleanas
0 (zero)
1 (um)

Uma variável booleana é representada por letra e pode assumir apenas dois valores (0 ou 1)
Exemplos: A, B, C

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)
Exemplos:
S = A.B
S = A+B.C
4

Postulados & Propriedades
Na álgebra booleana há postulados (axiomas) a partir dos quais são estabelecidas várias propriedades Existem várias propriedades da negação
(complemento, inversor), adição (porta E) e soma
(porta OU)
Estas propriedades podem ser verificadas como equivalências lógicas
Para demonstrar cada uma, basta utilizar as tabelas-verdade, constatando a equivalência
5

Postulados
Complemento
Se A=0 então Ā=1
Se A=1 então Ā=0

Notações alternativas
Ā = A’
Ā=¬A
B.C = (B.C)’

Adição
0+0=0
0+1=1
1+0=1
1+1=1

Multiplicação