MAC0329 - Álgebra Booleana e Aplicações

Cronograma das aulas --- 1o. semestre de 2007

(26/02) : aula 01
• Introdução à disciplina

(28/02) : aula 02
• Conjuntos, operações sobre conjuntos, propriedades das operações sobre conjuntos, relações binárias, funções.
  [ Notas de aula 1 ]

(05/03) : aula 03
• Cálculo proposicional
  [ Notas de aula 2 ]
  
• Referência adicional: notas de aula disponíveis na página de P. Kahn da Cornell University. Indicado para aqueles que têm interesse em entender melhor a relação entre cálculo proposicional e métodos de prova.
• OBS: este assunto é visto na disciplina MAC239 (Métodos Formais em Programação). Por isso, aqui veremos superficialmente, apenas como exemplo de álgebra booleana. Atentem em aspectos comuns com a teoria elementar dos conjuntos vista na aula anterior.

(07/03) : aula 04
• Álgebra Booleana: postulados de Huntington, exemplos, propriedades.
  [ Notas de aula 3 ] pág. 1 a 6
  
• Lista de exercícios 1: enunciado, entrega até 21/03

(12/03) : aula 05
• Relações de ordens parciais; posets; elementos notáveis de posets; exemplos; reticulados.
  [ Notas de aula 3 ] pág. 7 a 11
  

(14/03) : aula 06
• Reticulado booleano; álgebra booleana e relações de ordem parciais.
  [ Notas de aula 3 ] pág. 11 e 12
  ERRATA nas notas de aula 3: exercício 7 da página 12 deveria ser exercício 0 na página 15.
• Exercícios.

(19/03) : aula 07
• De que forma a álgebra Booleana está relacionada com problemas práticos reais?
  Projeto de circuitos lógicos (Quais funções podem ser realizadas via circuitos lógicos? Qual a realização mais "barata" de uma função via circuitos lógicos? Qual a realização mais "barata" de várias funções simultaneamente via um circuito lógico? Que propriedades possuem as funções que podem ser realizadas se restringimos o conjunto de operações básicas a serem utilizadas?)
  Essas são perguntas a serem respondidas nas próximas aulas.
  Mapeamento entre imagens binárias (Como eles se relacionam com funções Booleanas? Qual é a representação que permite uma avaliação rápida da saída de um mapeamento, dada a entrada? Como determinar o mapeamento, dados exemplos de entradas e respectivas saídas de um mapeamento desconhecido?)
  [ Notas de aula 4 ] (disponibilizada em 22/03)
  

(21/03) : aula 08 -- Data máxima para entrega da lista 1
• Expressões e funções booleanas. Teorema de expansão de Boole. Forma soma canônica de produtos.
  [ Notas de aula 5 ] (disponibilizada em 25/03)
• Lista de exercicios 2: enunciado -- entrega ate 09/04 (disponibilizada em 25/03)

(26/03) : aula 09
• Átomos. Expressão de elementos de uma álgebra booleana como supremo de átomos. Relação dessa expressão com a soma canônica de produtos.
  [ Notas de aula 3 ] pág.12 a 14, [ Notas de aula 5 ] pág. 7
  
• Produto de somas (dual dos conceitos vistos na última aula).
• Breve comentário sobre representação computacional de funções booleanas: expressões, tabelas-verdade, BDD (Binary Decisision Diagram).
  [ Notas de aula 5 ] pág. 6 até fim
  

(28/03) : aula 10
• Produtos, cubos, intervalos.
• Implicantes, implicantes primos (cubos ou intervalos maximais)
• Forma SOP minimal
• Mapas de Karnaugh
  [ Notas de aula 6 ] pág. 1 a 8

(02/04) : Break 1
(04/04) : Break 1

(09/04) : aula 11 -- Data máxima para entrega da Lista 2
• Revisão de definições e conceitos via exercícios
  (Forma SOP e POS minimal; cubos, intervalos, produtos; implicantes e implicantes primos de uma função; cálculo da forma SOP e POS minimal via mapas de Karnaugh.)
  [ Notas de aula 6 ] pág. 1 a 8

(11/04) : aula 12
• Minimização lógica 2-níveis de funções booleanas (formas SOP, SOP canônica e SOP minima)
  Cálculo de implicantes primos via QM
  [ Notas de aula 6 ] pág. 1 a 12

(16/04) : aula 13
• Minimização lógica 2-níveis de funções booleanas
  Cálculo de cobertura mínima: criação da matriz de implicantes primos, escolha de implicantes primos essenciais, eliminação de linhas dominadas, eliminação de colunas dominantes, resolução de tabela cíclica (método de Petrick).
  [ Notas de aula 6 ] pág.10 a 15

(18/04) : aula 14
Aula de exercícios

Gabarito da lista 2 (disponibilizada em 19/04)

(23/04) : aula 15 -- Prova 1
Prova terá inícios às 13:30hs e término às 16hs. Será permitida a entrada até às 14hs. Não será permitida a saída antes das 14hs.
Matéria para a prova: tudo que foi visto desde o início das aulas até mapas de Karnaugh (inclusive), aulas 1 a 11.

(25/04) : aula 16
• Minimização lógica dois-níveis de funções booleanas incompletamente especificadas
  [ Notas de aula 6 ] pág. 16
• Minimização lógica dois-níveis de múltiplas funções
  [ Notas de aula 6 ] pág.21 a 34

(01/05) : Break 2
(03/05) : Break 2

(07/05) : aula 17
• Minimização lógica dois-níveis de múltiplas funções
  [ Notas de aula 6 ] pág.21 a 34
• PLA

(09/05) : aula 18
• Minimização SOP heurística: Algoritmo ESPRESSO
  (Ref.: Cap. 6 e 7 de G. De Micheli. Synthesis and Optimization of Digital Circuits. McGraw-Hill, 1994.)
  OBS.: esse é um tópico extra. Não será cobrado em prova.

Lista de exercicios 3: enunciado, entrega ate 28/05 (disponibilizada em 12/05)

(14/05) : aula 19
• Exercícios sobre minimização lógica dois-níveis de múltiplas funções, com don't cares.

(16/05) : aula 20
• Mais exercícios!

(21/05) : aula 21
• Minimização de funções booleanas aplicada ao aprendizado de operadores de imagens binárias.
  Alguns exemplos.
  

(23/05) : aula 22
Circuitos seqüenciais
• Exemplos de dispositivos seqüenciais: fechaduras com segredo, elevadores
• Unidades de memória: flip-flops SR e JK
  
  [ Notas de aula 7 ] (disponibilizada em 12/06)

(28/05) : aula 23
• Aula cancelada por falta de quorum. (Nas próximas aulas, isso não acontecerá.)
  Data máxima para a entrega da L3: adiada para 30/05

(30/05) : aula 24
• Flip-flops D, flip-flops T
• Situação desejável: flip-flops devem mudar de estado apenas uma vez a cada pulso do clock e todos eles devem mudar de estado simultaneamente. Por quê? Exemplo.
• Edge-triggered flip-flops; flip-flops mestre-escravo.
• Registrador: exemplo de implementação de um registrador-deslocador (uma direção), usando flip-flops D.
  
  [ Notas de aula 7 ] (disponibilizada em 12/06)

(04/05) : Break 3
(06/05) : Break 3

(11/06) : aula 25
• Contadores
• Exemplo de análise de circuito seqüencial: equação das entradas e saídas dos flip-flops, equação da saída do circuito, tabela de estados e diagrama de estados.
  
  [ Notas de aula 7 ]

(13/06) : aula 26
• Exemplo de projeto de circuitos seqüenciais: identificador de início de mensagem
  
  [ Notas de aula 7 ] Pág. 15 a 19
  ERRATA Na versão de 12/06/2007, há um erro na figura do diagrama de estados da página 15 (na aresta que liga q0 e q4, a seta deve estar apontando para q4) e um outro erro na tabela minimal de estados da página 16 (na segunda linha da tabela devemos ter "b a/0 d/1" e na terceira linha "c a/0 b/0"). A versão de 13/06 já está corrigida.

(18/06) : aula 27
• Decodificadores, codificadores.
• Exemplos de uso: memória ROM, teclado.
• Multiplexadores.
  
  [ Notas de aula 8 ] (Decodificadores, codificadores, multiplexadores e demultiplexadores)

(20/06) : aula 28
Multiplexadores, demultiplexadores, exercícios

Lista de exercícios 4 sobre circuitos seqüenciais e circuitos combinacionais modulares (não é para entrega)

(25/06) : aula 29
Exercícios

(27/06) : aula 30 -- Prova 2
Matéria da prova: minimização de funções booleanas (individual nas formas SOP e POS, via mapas de Karnaugh e via o algoritmo de Quine-McCluskey), minimização SOP conjunta de funções booleanas, PLA, projeto de circuitos combinacionais, flip-flops, análise de circuitos seqüenciais (projeto de circuitos seqüenciais não), decodificadores, codificadores, multiplexadores.


04/07: Prova substitutiva (PSUB)
Não há garantias de que a P2 estará corrigida até a PSUB. Todos podem fazer a PSUB, mas ela só será corrigida se o(a) aluno(a) tiver perdido uma das provas (P1 ou P2) ou se não tiver média pelo menos 5.0 nas duas. Excessões podem ser abertas, mas isso será considerado caso a caso, mediante manifestação do(a) interessado(a).
Matéria para a PSUB: tudo que foi visto durante o semestre (exceto aplicação no contexto de imagens digitais, algoritmo Espresso e projeto de circuitos sequenciais).