MAC0329 - Álgebra Booleana e Aplicações

Primeiro semestre de 2003 --- 23/junho/2003

Nina S. T. Hirata / sala 300-A / nina at ime . usp . br

Resumão do curso

O que se espera ao final do curso

• aprendido a manipular expressões booleanas (aplicar os axiomas e leis da álgebra) para colocá-las em alguma forma padrão, para minimizá-las ou para provar equivalências de expressões
• entendido a relação entre álgebra booleana e os circuitos lógicos
• dada uma função, aprendido a desenhar um circuito que a realiza, ou então, verificar quantas portas lógicas são necessárias para a realização da função.
• dada uma descrição funcional de um sistema relativamente simples, projetar (especificar) funções booleanas que satisfazem a descrição.
• aprendido a minimizar expressões booleanas na forma SOP ou POS, usando o algoritmo QM e também a sua interpretação do ponto de vista algébrico.
• ficado consciente de que há outras formas/algoritmos de se minimizar funções (mapa de Karnaugh, algoritmo ISI, Espresso, BOOM, etc), mas não se espera que o aluno entenda como cada um deles funciona
• entendido que minimização de funções booleanas é um problema difícil do ponto de vista computacional e importante do ponto de vista econômico
• minimizar múltiplas funções, PLA
• adquirido alguma idéia sobre minimização multi-níveis. Por que multi-níveis em vez de 2 níveis ou vice-versa?
• entendido o funcionamento dos circuitos "caixa-preta" tais como decodificador, multiplexador, codificador e seu uso na memória ROM, teclado, realização de funções quaisquer.
• adquirido uma visão geral sobre circuitos seqüenciais: flip-flops, por que seqüenciais e não combinacinais ou vice-versa (nesta parte em particular, não será exigido que o aluno projete um flip-flop ou um circuito seqüencial. O máximo que se espera é que dado um circuito seqüencial, o aluno saiba interperetar o seu funcionamento).

Conteúdo visto antes da P1

• álgebra dos conjuntos (Parte 1)
• lógica proposicional (Parte 2)
• álgebra booleana (Parte 3)
• introdução a circuitos de chaveamento / circuitos lógicos (NÃO há notas de aula). Ref.[1]

Conteúdo visto depois da P1

• Minimização lógica 2 níveis de funções boolenas
  • algoritmo QM + método de Petrick (Parte 5 + [2])
  • minimização na forma SOP (e/ou POS [2])
  • minimização de funções incompletamente especificadas (Parte 5 + [2])
  • algoritmo ISI (aplicação do ISI não cai na prova) (Parte 5)
  • minimização de múltiplas funções (Parte 6 + [2])
  • PLA (Parte 6 + [2])
  • O programa para minimização Espresso ([2], não cai na prova)
• Minimização lógica mlti-níveis de funções boolenas [4]
  • Decodificadores
  • Multiplexadores
  • Codificadores
  • Implementação de função usando decodificadores/multiplexadores
  • Exemplos: teclado, (P)ROM
• Circuitos sequenciais [4]
  • Flip-flops (não é necessário decorar os tipos de flip-flops, mas é bom saber analisá-los se um deles é dado)
  • Exemplos: verificador de paridade, contador
  • Projeto de circuitos seqüenciais (não cai na prova) --> não há notas nem material no xerox (quem tiver interesse, favor me procurar)

Referências

1. "Mendelson, E. (1977). Álgebra Booleana e Circuitos de Chaveamento. Mcgraw-Hill."

2. "Hill, F. J. and Peterson, G. R. (1981). Introduction to Switching Theory and Logical Design. John Wiley, 3rd edition."

3. Notas de aula

4. Material disponível na "Xerox do bloco B" (não tem equivalente nas notas de aula) --- Pasta 12

• Funções booleanas e unicidade da forma SOP (pág. 402 a 417 do livro do Garnier & Taylor
• Decodificadores, multiplexadores, memória (flip-flops), um pouco sobre circuitos seqüenciais -- pág.193-209 e 226-241 do livro de Hill & Peterson (4th edição)