10/15/10 Representação de Funções
Mário Serafim Nunes
Guilherme Silva Arroz
Sistemas Digitais - Taguspark
 
 
 
 
Conceitos básicos
Forma canónica normal disjuntiva
Forma canónica normal conjuntiva
Representação usando apenas um tipo de
função
Mário Serafim Nunes
Guilherme Silva Arroz
2010/2011
2
1 10/15/10 Sistemas Digitais - Taguspark
 
Há, como já se referiu, várias formas de
representar uma função:
 
 
 
 
Expressão lógica
Tabela de Verdade
Logigrama
Consideremos um exemplo:
 
A função está aqui representada pela sua expressão
lógica ou algébrica.
Mário Serafim Nunes
Guilherme Silva Arroz
2010/2011
3
Sistemas Digitais - Taguspark
 
 
A função está aqui representada como uma
soma de produtos.
Esta não é única expressão lógica possível.
 
 
Modificando a expressão obtém-se esta expressão
equivalente que está agora na forma de produto de
somas.
A primeira expressão é uma Forma normal
disjuntiva e a segunda, uma Forma normal
conjuntiva. Na última expressão o b está entre parêntesis para
chamar a atenção que, em geral, estaria uma soma
naquela posição
Mário Serafim Nunes
Guilherme Silva Arroz
2010/2011
4
2 10/15/10 Sistemas Digitais - Taguspark
 
Outra forma de representar a função é através
da sua Tabela de Verdade.
Mário Serafim Nunes
Guilherme Silva Arroz
2010/2011
5
Sistemas Digitais - Taguspark
 
A função também pode ser representada por
um logigrama. Como o logigrama está ligado à
expressão algébrica há vários logigramas
possíveis. Exemplifica-se um deles.
Mário Serafim Nunes
Guilherme Silva Arroz
2010/2011
6
3 10/15/10 Sistemas Digitais - Taguspark
 
A tabela de uma função é constituída por um
conjunto de linhas a 1 e as restantes a 0. Os 1s
podem ser isolados em tabelas específicas:
Considere-se a
função
anteriormente
referida:
 
É fácil ver que:
Mário Serafim Nunes
Guilherme Silva Arroz
2010/2011
7
Sistemas Digitais - Taguspark
 
 
É fácil perceber que
As duas restantes não são tão óbvias mas
analisando-as, resulta:
Mário Serafim Nunes
Guilherme Silva Arroz
2010/2011
8
4 10/15/10 Sistemas Digitais - Taguspark
 
 
 
Portanto:
Esta expressão não é tão simplificada como as
anteriores mas é sempre possível e fácil, para
qualquer função de qualquer número de
variáveis, usar o método descrito para obter, a
partir de uma tabela, uma expressão da função
com este tipo de estrutura.
Repare-se que se utilizam apenas as funções
AND, OR e NOT.
Mário Serafim Nunes
Guilherme Silva Arroz
2010/2011
9
Sistemas Digitais - Taguspark
 
 
 
 
Esta expressão tem a particularidade de ter um
produto por cada 1 na tabela da função e de
todos os produtos serem produtos de todas as
variáveis da função, usadas directamente ou
negadas.
Esta expressão é a Forma canónica normal
disjuntiva
Este tipo de produto tem o nome de mintermo.
Esta expressão é única (a menos da
comutatividade). A tabela é única. A cada 1 da
tabela corresponde um produto na soma.
Mário Serafim Nunes
Guilherme Silva Arroz
2010/2011
10
5 10/15/10 Sistemas Digitais - Taguspark
 
 
Como cada mintermo corresponde ao 1 de uma
das linhas da tabela, podemos designar o
mintermo com o número da linha.
Assim,
Mário Serafim Nunes
Guilherme Silva Arroz
2010/2011
11
Sistemas Digitais - Taguspark
 
 
A obtenção da expressão de um mintermo a
partir do seu número realiza-se fazendo a
correspondência do número em binário com as
diversas variáveis ou as suas negações.
O mintermo m2, por exemplo, corresponde à
posição da linha 2 da tabela, isto é, à linha em
que a=0, b=1 e c=0 (configuração 010 em
binário). Daqui se conclui que
0 1 0
Mário Serafim Nunes
Guilherme Silva Arroz
2010/2011
12
6 10/15/10 Sistemas Digitais - Taguspark
 
 
A uma forma canónica normal disjuntiva
corresponde um logigrama que, claro, não é,
em geral, o mais simples possível.
Trata-se de uma estrutura a dois níveis (não
contando com as negações)
Mário Serafim Nunes
Guilherme Silva Arroz
2010/2011
13
Sistemas Digitais - Taguspark
Mário Serafim Nunes
Guilherme Silva Arroz
2010/2011
14
7 10/15/10 Sistemas Digitais - Taguspark
 
Pelo Princípio da Dualidade pode-se
considerar agora privilegiar os 0s da tabela:
Considere-se
ainda a função
anteriormente
referida:
 
Os termos Mi são agora designados por
maxtermos e são somas. Por exemplo
Mário Serafim Nunes
Guilherme Silva Arroz
2010/2011
15
Sistemas Digitais - Taguspark
 
É fácil perceber que
Mário Serafim Nunes
Guilherme Silva Arroz
2010/2011
16
8 10/15/10 Sistemas Digitais - Taguspark
 
 
 
Repare-se que, da mesma forma, se utilizam
apenas as funções AND, OR e NOT.
Esta expressão tem a particularidade de ter
uma soma por cada 0 na tabela da função e de
todas as somas serem somas de todas as
variáveis da função, usadas directamente ou
negadas.
Esta expressão é a Forma canónica normal
conjuntiva
Mário Serafim Nunes
Guilherme Silva Arroz
2010/2011
17
Sistemas Digitais - Taguspark
 
 
A obtenção da expressão do maxtermo a partir
do seu número é semelhante ao que se
observou no caso dos mintermos com as
alterações impostas pelo princípio da
dualidade.
O mintermo m3 só assume o valor 1 quando
a=0 e b=1 e c=1 e, portanto
Mário Serafim Nunes
Guilherme Silva Arroz
2010/2011
18
9 10/15/10 Sistemas Digitais - Taguspark
 
A função M3 só assume, por seu lado, o valor 0
quando se está na configuração 011, e portanto
assume o valor 1 quando a=1 ou b=0 ou c=0.
Daí que
0 1 1
Note-se que os valores das variáveis estão negados
em relação á forma canónica disjuntiva
Mário Serafim Nunes
Guilherme Silva Arroz
2010/2011
19
Sistemas Digitais - Taguspark
Mário Serafim Nunes
Guilherme Silva Arroz
2010/2011
20
10 10/15/10 Sistemas Digitais - Taguspark
 
 
 
Um conjunto completo é um conjunto de
funções que são suficientes para representar
todas as outras. Viu-se que o conjunto {NOT,
AND, OR} é um conjunto completo.
Outros conjuntos completos são o conjunto
formado só pelo NAND ou o conjunto formado
só pelo NOR.
Se for possível construir um NOT, um AND e
um OR com um NAND, então {NAND} é um
conjunto completo.
Mário Serafim Nunes
Guilherme Silva Arroz
2010/2011
21
Sistemas Digitais - Taguspark
NOT
Mas
é um
NAND
AND
OR
Usam-se 3
NANDs
Usam-se 3
NANDs
Ou, graficamente no slide seguinte
Mário Serafim Nunes
Guilherme Silva Arroz
2010/2011
22
11 10/15/10 Sistemas Digitais - Taguspark
XY
X Y
Mário Serafim Nunes
Guilherme Silva Arroz
X Y
2010/2011
23
Sistemas Digitais - Taguspark
 
 
 
 
O que foi feito para os NANDs podia ser
replicado para os NORs.
É, portanto, possível utilizar apenas NANDs
ou NORs usando as regras que se observaram.
Isso conduz a expressões de grande
complexidade.
Há formas mais simples. Por exemplo para a
utilização de NANDs pode-se partir da
representação numa forma normal disjuntiva
(soma de produtos).
Mário Serafim Nunes
Guilherme Silva Arroz
2010/2011
24
12 10/15/10 Sistemas Digitais - Taguspark
 
 
 
Tome-se como exemplo:
A função negação pode ser considerada uma forma
particular de NAND, o NAND com uma entrada.Virá
então:
De igual modo se poderia proceder com um produto
de somas para obter uma expressão com NORs.
Mário Serafim Nunes
Guilherme Silva Arroz
2010/2011
25
Sistemas Digitais - Taguspark
 
 
 
 
Livro recomendado, secção 2.2
Carlos Sêrro: Sistemas Digitais – fundamentos
algébricos, ISTPress 2003, Capítulo 5
Existem muitos livros com capítulos sobre o
assunto.
A Internet é, como de costume, uma fonte que,
explorada com espírito crítico, tem muito para
dar.
Mário Serafim Nunes
Guilherme Silva Arroz
2010/2011
26
13