9/10/2013
Objetivo
Universidade Estadual de Campinas
FEEC - DEMIC
Exame de Qualificação
Projeto de um Aplicativo para Síntese
de Funções Multi-Valores em
Ambiente Windows
Projetar e desenvolver uma ferramenta
automatizada com interface amigável que
possa realizar a tarefa de gerar a expressão
minimizada relativa à tabela verdade
fornecida pelo usuário.
Autor: Marco Aurélio Seluque Fregonezi
Orientador: Prof. Dr. Alberto Martins Jorge
22/08/01
Tese de mestrado
L.M.V.S.
1
Tese de mestrado
Ambiente de desenvolvimento
L.M.V.S.
2
Janela de entrada
Atualmente, dispõe-se de versões beta.
A versão 1.0 será lançada na data da defesa de tese.
Tese de mestrado
L.M.V.S.
3
Tese de mestrado
Como mostrar uma função
L.M.V.S.
4
Tarefa
Tabela verdade
intuitivo
Tabela
verdade
Expressão
algébrica
l éb i
Expressão algébrica
manipulável
Tese de mestrado
L.M.V.S.
5
Tese de mestrado
L.M.V.S.
6
1
9/10/2013
Opções de funções:
•
•
•
•
•
•
•
Tese de mestrado
Área de entrada (tabela-verdade)
Dois valores e uma entrada
Dois valores e duas entradas
Dois valores e três entradas
Três valores e uma entrada
Três valores e duas entradas
Quatro valores e uma entrada
Quatro valores e duas entradas
L.M.V.S.
7
Lógica empregada
3x1
B=B(A)
4x1
B=B(A)
3x2
C=C(A,B)
4x2
C=C(A,B)
Tese de mestrado
L.M.V.S.
Lógica ciclicamente fechada
1
0
1
2
0
3
Conectivos de dois valores
Tese de mestrado
 0 1
0 0 0
0 0 1
1 0 1
1 1 1
L.M.V.S.
1
2
9
 0 1
0
Quatro valores
Extensão de A.M.Jorge:
Vários deslocadores
Vários conectivos
Mais do que três valores
L.M.V.S.
Três valores
Dois valores
Lógica MVL de Post:
1 deslocador horário – Topo
1 conectivo – Mínimo
Três valores
Tese de mestrado
8
Tese de mestrado
L.M.V.S.
10
Conectivos de três valores
11
 0 1 2
 0 1 2
 0 1 2
0 0 0 0
0 0 1 2
0 0 0 2
1 0 1 1
1 1 1 1
1 0 1 2
2 0 1 2
2 2 1 2
2 2 2 2
Tese de mestrado
L.M.V.S.
12
2
9/10/2013
Deslocadores
Conectivos de quatro valores
shifters

0
1
2
3

0
1
2
3
0
0
0
0
0
0
0
1
2
3
1
0
1
1
1
1
1
1
1
1
2
3
0
0
1
1
2
2
2
3
2
3
2
3
1
1
2
2
2
3
0
1
2
3
0
1
2
3
0
0
2
3
0
1
2
3
2
2
2
2
3
3
2
3L.M.V.S.
0
0
0
3
0
1
1
3
0
1
2
3
3
3
3
3

0
1
2
3
Tese de mestrado

0
1
2
3
Dois valores
Três valores
Quatro valores
13
Tese de mestrado
Grafia
A
A
0
1
1
0
A
A
A
0
1
2
1
2
2
0
0
1
A
A
A
A
0 1
1 2
2 3
3L.M.V.S.0
2
3
0
1
3
0
1
2
14
Menus
ASC
Expressão
ELOmv
L.M.V.S.
AB
A B
AB
AB
A* B
A+ B
A– B
A/ B
At
Ad
Ab
Aa B
Ab B
Ac B
Ad B
/A
//A
A/
A
A
A
Tese de mestrado
L.M.V.S.
15
Tese de mestrado
Menu Arquivo
•
•
•
•
•
L.M.V.S.
16
Função binária
O conceito de função binária é particularizado
para este contexto:
Abrir
Salvar
C i
Copiar
Imprimir
Sair
Função binária é aquela que fornece apenas dois
valores consecutivos.
Valor analisado
Dominante  Verdadeiro
termo  ocorrência do valor dominante
Secundário  Falso
Tese de mestrado
L.M.V.S.
17
Tese de mestrado
L.M.V.S.
18
3
9/10/2013
Conversão para binário
Comandos de manipulação
Operação com o secundário elimina o terciário e
o indiferente, restando apenas o dominante e o
secundário.
•
•
•
•
•
•
•
Quatro valores
A1
A2
A3
A0
Três valores
A1
A2
A0
A substituição do terciário e do indiferente pelo
dominante também gera função binária.
Tese de mestrado
L.M.V.S.
19
0,1,2,3
a1,b2,c3,d0
a2,b3,c0,d1
TH TV
TH,
TV, TN
Deslocar
Aleatório
A (uma entrada)
Tese de mestrado
Técnica de síntese
L.M.V.S.
20
Técnica de síntese
Transformar a função MVL fornecida em sub-funções binárias.
A função MVL corresponde a uma junção de funções binárias.
Tabela
MVL
Expressão
MVL
Técnica ideal
Nomenclatura:
Tabelas
binárias
Letra maiúscula: Função MVL.
Letra minúscula: Sub-função binária.
Expressões
binárias
Asterisco: Uso de irrelevantes.
Tese de mestrado
L.M.V.S.
21
Sub-funções binárias
22
Sub-funções binárias
Duas entradas C=C(A,B)
Três valores
Três valores
Sem irrelevantes
(uma ou duas entradas)
S b tit i ã
Substituição
Dominante Dominante
Secundário Secundário
Indiferente Irrelevante
Tese de mestrado
L.M.V.S.
Duas entradas C=C(A,B)
Com irrelevantes
(duas entradas)
(opcional)
c*
Tese de mestrado
Com irrelevantes
(duas entradas)
(opcional)
S b tit i ã
c* Substituição
Substituição
S
b tit i ã
Dominante Dominante
Secundário Secundário
Indiferente Dominante
L.M.V.S.
c
23
c0
c1
c2
Tese de mestrado
2X
0X
1X
Sem irrelevantes
(uma ou duas entradas)
b tit i ã
c SSubstituição
c0 2  0
c1 0  1
c2 1  2
L.M.V.S.
24
4
9/10/2013
Sub-funções binárias
Sub-funções binárias
Duas entradas C=C(A,B)
Duas entradas C=C(A,B)
Quatro valores
Quatro valores
c**
Subst.
c*
Subst.
c
Subst.
1o
1o
1o
1o
1o
1o
2o
3o
4o
2o
X
X
2o
3o
4o
2o
X
1o
2o
3o
4o
2o
1o
1o
Tese de mestrado
L.M.V.S.
c** Substituição
c0
c1
c2
c3
25
2,3  X
3,0  X
0,1  X
1,2  X
c*
Substituição
c0
c1
c2
c3
2X 30
3X 01
0X 12
1X 23
Tese de mestrado
c Substituição
c0 2,3  0
c1 3,0  1
c2 0,1  2
c3 1,2  3
L.M.V.S.
Conectivos
26
Conectivos
Unicidade
Duas entradas:
Dois valores
Cada termo da tabela binária refere-se a uma expressão que só é
verdadeira se e somente se o termo em questão for verdadeiro.
c0 disjuntivo
c1 conjuntivo
Entre as coordenadas, usar o operador para o qual o valor
analisado é o indiferente
Uma e Duas entradas:
A tabela binária refere-se a uma expressão que é verdadeira se
pelo menos um dos termos for verdadeiro.
Entre os termos, usar o operador para o qual o valor analisado é
o dominante
L.M.V.S.
Entre
Entre
termos
 (+)
 (*)
 (*)
 (+)
Três valores
Entre
Entre
coordenadas
termos
Existência
Tese de mestrado
coordenadas
27
c0
c1
c2






Tese de mestrado
Quatro valores
Entre
Entre
coordenadas
termos
c0
c1
c2
c3
L.M.V.S.








28
Necessidade de conversão
para binário
Exemplo: termos para c0
três valores e duas entradas
0
A= 0
A= 1
A= 2
termo  ocorrência do valor dominante
B=0
AB
AB
AB
Na tabela anterior,um termo isolado é uma função MVL
devendo, por isso, sofrer a conversão para binário.
B=1
A B
A B
A B
Para simplificar, a conversão para binário é escrita apenas
expressão binária completa.
B=2
A B
A B
A B
A expressão binária completa, formada por vários termos,
pode ou não precisar da conversão para binário.
Tese de mestrado
L.M.V.S.
29
Tese de mestrado
L.M.V.S.
30
5
9/10/2013
Formas
Formas
Duas entradas C=C(A,B)
Duas entradas C=C(A,B)
Dois valores: Duas formas C1,C2
Três
ê valores:
l
Três
ê formas
f
C1,C
C2,C
C3
Quatro valores: Quatro formas C1,C2,C3,C4
Tese de mestrado
L.M.V.S.
31
Dois valores:
C1=C1(c0)
C2=C2(c1)
c0=c0(A,B)
c1=c1(A,B)
Três valores:
C1=C1(c0,c1)
C2=C2(c1,c2)
C3=C3(c2,c0)
c0=c0(A,B)
c1=c1(A,B)
c2=c2(A,B)
Quatro valores:
C1=C1(c0,c1,c2)
C2=C2(c1,c2,c3)
C3=C3(c2,c3,c0)
C4=C4(c3,c0,c1)
c0=c0(A,B)
c1=c1(A,B)
c2=c2(A,B)
c3=c3(A,B)
Tese de mestrado
L.M.V.S.
Conectivos
Conectivos
Três ou Quatro valores
Três ou Quatro valores
1o
2o
forma
c0()
c1()
c0  c1
c1()
c2()
c1  c2
c2()
c0()
c2  c0
Três valores
C1
C2
C3
Entre as sub-funções binárias
(termos), usar o operador que não foi
utilizado entre os termos das duas
sub-funções, ou seja, o operador para
o qual os valores analisados nos dois
termos são o secundário e o
indiferente, respectivamente.
Tese de mestrado
L.M.V.S.
2o
3o
C1
C2
C3
C4
forma
c0()
c1()
c2()
(c0c1)  c2
33
c1()
c2()
c3() (c1c2)  c3
c2()
c3()
c0() (c2c3)  c0
c3()
c0()
c1()
Tese de mestrado
(c3c0)  c1
L.M.V.S.
34
Formas
Origem dos irrelevantes
Exemplo para C1
Quatro valores
Sem
Com
C irrelevantes irrelevantes
C
C1
C2
C3
C1
C2
C3
C4
Tese de mestrado
1o
Quatro valores
Duas entradas C=C(A,B)
Três valores
c0 c c1
c1 a c2
c2 b c0
32
c0* c c1
c1* a c2
c2* b c0
C1
(
c0

c1
)

c2
0
(
0

1
)

2
1
(
1

1
)

2
(c2 a c3) b c0 (c2** a c3*) b c0
2
(
X
0

2
)

2
(c3 b c0) c c1 (c3** b c0*) c c1
3
(
X
0

X
1
)

3
Sem
irrelevantes
Com irrelevantes
( 0 c c1)
(c0
1) d c2
2 (c0**
( 0** c c1*)
1*) d c22
(c1 d c2) a c3 (c1** d c2*) a c3
L.M.V.S.
35
Tese de mestrado
L.M.V.S.
36
6
9/10/2013
Formação de
linhas e colunas completas
Etapas da minimização
1. Uso de irrelevantes*
2. Formação de linhas e
colunas completas**
3 Eliminação
3.
Eli i ã da
d conversão
ã
para binário
4. Escolha da menor forma**
A formação de linhas e colunas completas é a técnica
de minimização mais intuitiva de todas, exigindo
“ i í i ” por parte
“raciocínio”
t da
d máquina.
á i
Utiliza o algorítimo mais sofisticado do programa, que
requeriu grande parte do tempo total de
desenvolvimento do produto.
* Somente para 3x2 e 4x2
** Somente para duas ou mais entradas
Tese de mestrado
L.M.V.S.
37
Tese de mestrado
L.M.V.S.
Exemplo
C
Exemplo – C1
A= 0 A= 1 A= 2 A= 3
B=0
0
1
1
2
3
2
3
B=2
0
0
1
3
B=3
3
0
1
3
Tese de mestrado
C
2
B=1
0
2
0
3
L.M.V.S.
39
1
3
0
0
c0**
1
2
1
1
C
1
3
0
0
Tese de mestrado
2
3
3
3
1 1
2 X
1 1
X 1
L.M.V.S.
0 1 1 X
X X X X
0 0 1 X
X 0 1 X
L.M.V.S.
40
Exemplo – C1
C
c1*
1
2
1
1
2
3
3
3
Tese de mestrado
Exemplo – C1
0
2
0
3
38
1
2
1
1
0
2
0
3
2
X
X
X
41
1
3
0
0
Tese de mestrado
c2
1
2
1
1
2
3
3
3
2
2
2
3
L.M.V.S.
2
3
2
2
2
2
2
2
2
3
3
3
42
7
9/10/2013
Exemplo – C1
Exemplo – C1
substituição dos irrelevantes
tabelas binárias
c0**
c0**
c1*
0 1 1 X
1
X
0 X
1 X
1 X
1
0 0 1 X
1
X
0 0 1 X
1
Tese de mestrado
1 1
2 X
1
1 1
X
1 1
1
2
1
1
2
X
2
X
1
X
1
L.M.V.S.
43
1
1
0
0
1
1
1
1
1
2
1
1
Tese de mestrado
1
1
1
1
1
2
1
1
c2
2
2
1
1
2
2
2
3
2
3
2
2
formação das sub-expressões binárias
1
1
1
1
A
A
A/ b //B
1
1
1
1
c1*
1
2
1
1
A/ b /B
Tese de mestrado
L.M.V.S.
1
1
1
1
/A c B/
1
2
1
1
2
2
1
1
/A c /B
B/
/B
c1*=(/A c /B) b (A/ c /B) b A b B/ b //B b 2
45
Tese de mestrado
L.M.V.S.
46
Exemplo – C1
Exemplo – C1
formação das sub-expressões binárias
conversão para binário
//B
2
3
2
2
2
2
2
2

A
c2






2
3
3
3
Pelas regras para eliminação da conversão para binário,
binário pode-se
pode se
concluir, que c1* e c2 não precisam de conversõa para binário.
c0**=(A/ b //B)a(A/ b /B)aAa1
c2=(//A d /B) c (//A d B) c (/A d B) c
(/A d B/) c A c //B c3
Tese de mestrado
2
3
3
3
44
formação das sub-expressões binárias
1
1
0
0
2
2
2
2
L.M.V.S.
Exemplo – C1
c0**=(A/ b //B)a(A/ b /B)aAa1
2
2
2
3
c1*
1
1
1
1
Exemplo – C1
c0**
0
0
0
0
0
0
0
0
L.M.V.S.
c1*=(/A c /B) b (A/ c /B) b A b B/ b //B
c2=(//A d /B) c (//A d B) c (/A d B) c (/A d B/) c A c //B
47
Tese de mestrado
L.M.V.S.
48
8
9/10/2013
Exemplo – C1
Exemplo – C1
escolha da menor forma
c0**=(A/ b //B)a(A/ b /B)aAa1
c1*=(/A c /B) b (A/ c /B) b A b B/ b //B
c2=(//A d /B) c (//A d B) c (/A d B) c (/A d B/) c A c //B
C1 = { [ (A/ b //B) a (A/ b /B) a A a 1 ] c [ (/A c /B) b (A/ c /B) b A b B/
b //B ] } d [ (//A d /B) c (//A d B) c (/A d B) c (/A d B/) c A c //B ]
C2 = { [ (A/ c /B) b A b B/ b //B ] d [ (//A d /B) c A c //B ] } a [ (//A a
B/) d (A/ a B) d /A d A d //B ]
C3 = { [ (//A d /B) c A c //B ] a [ (A/ a B) d A d //B ] } b [ (A/ b //B) a
(A/ b /B) a A a /A a B/ ]
C4 = { [ (A/ a B) d A d //B ] b [ (A/ b //B) a (A/ b /B) a A a /A a B/ ] } c
[ (/A c /B) b (A/ c /B) b (//A c B) b A b B/ b //B ]
Tese de mestrado
L.M.V.S.
49
Tese de mestrado
Cores
Padrão 1
Tese de mestrado
L.M.V.S.
50
Cores
Padrão 2
L.M.V.S.
51
Tese de mestrado
Conclusão
L.M.V.S.
52
Perspectivas
O programa realiza exatamente o procedimento
determinado pela técnica de síntese empregada, fornecendo
a expressão minimizada de maneira intuitiva e fácil de
compreender, permitindo ao usuário, caso deseje, obter
mais informações sobre as etapas da síntese.
• Interação com ELOmv
• Opção por grafia do ELOmv
• Possibilidade de uso de
i l
irrelevantes
MVL
• Possibilidade de uso de apenas
um tipo de conectivo
A execução da síntese é feita em tempo real, ou seja,
durante a digitação da tabela, levando apenas algumas
frações de segundo.
O aplicativo funciona bem nos ambientes Windows95™,
Windos98™ e Windows2000™ e requer poucos recursos
de hardware, podendo ser utilizado em equipamentos
antigos, como por exemplo, 80486 100MHz.
Tese de mestrado
L.M.V.S.
53
Tese de mestrado
L.M.V.S.
54
9