109
edits
Changes
Jump to navigation
Jump to search
→Condições Indiferentes
== '''Condições Indiferentes''' ==
É possível usar o nosso procedimento '''SumOfProductsExpansion''' para lidar com as chamadas condições indiferentes. Aqui, vamos desenvolver um procedimento Maple que nos permite calcular uma soma de produtos em expansão (forma normal disjuntiva), de comprimento mínimo, para uma função booleana especificada juntamente com condições indiferentes.
Informalmente, um conjunto de condições indiferentes para uma função booleana f é um conjunto de pontos no domínio de f cujas imagens em f nós não estamos interessados. Em outras palavras, somos indiferentes a respeito para onde f envia esses pontos. Há provavelmente alguns pontos do domínio de f, no entanto cujas imagens sob f são importantes para nós. Estes pontos em que f é bem definida forma um subconjunto A do domínio de f, e a restrição de f para A é uma função bem definida (no sentido de que não existe ambiguidade em relação ao valor de f em qualquer destes pontos). Nota-se que, se f é para ser uma função de n variáveis, então o domínio D é simplesmente o conjunto {0, 1}^n de todos n-tuplas de 0's e 1's (ou, em sintaxe Maple, o conjunto {true, false}. Se pensarmos em f como uma função totalmente definida neste subconjunto A de D, então, o que nos interessa é a família de todas as extensões de f a D. Que é o conjunto de todas as funções booleana valorada g de D, cuja restrição a A é igual a f. Agora, cada uma destas funções g é completamente definida em D, de modo que a técnica usada anteriormente para calcular a expansão da soma dos produtos pode ser aplicada a qualquer um deles. Assim, para encontrar uma expansão da soma de produtos ideal (que, aqui, significa menor) de f, podemos calcular a unica expansão de soma de produtos para cada extensão g de f para D, e procurar entre eles por um de tamanho mínimo.
Devemos parar para considerar o tamanho desse problema. O subconjunto A de D em que f é bem-definida, e o subconjunto DC de pontos indiferentes (don’t care points), em que f não é especificada na partição o domínio D, isto é, D deve ser escrito como uma união disjunta ______
Se temos d como um ponto indiferente (isto é, se |D| = d), então temos <math>2^{d}</math> extensões g de f para D. Cada extensão corresponde a uma escolha de um subconjunto de DC para incluir entre ele e as pré-imagens de 1. Então, o problema cresce muito rapidamente com o número de pontos indiferentes, ou condições.
A ótica que adotamos aqui faz com que seja muito fácil ver um algorítmo que calcula uma expansão da soma de produtos, de tamanho mínimo, para uma função determinada com condições indiferentes. Podemos simplesmente fazer uma pesquisa exaustiva sobre o conjunto de todas as extensões bem definidas.
Para fazer isso, rescreveremos o procedimento Maple '''dcmin''' (Don’t Care Minimizer - Minimizador Indiferente) para construir todas as <math>2^{d}</math> funções, chame nosso procedimento '''SumOfProductsExpansion''' sobre cada, e depois olhe para um que tenha o comprimento mínimo. Aqui está o código Maple para fazer isso.
<pre>dcmin := proc(pt::set,list, dc::set,list)
local e, # expression to return
te, # temporary expression
i, # index
s, # the size of the smallest expression so far
PT, # pt as a set
DC, # dc as a set
PDC, # power set of DC
T, # temporary set (loop variable)
S; # temporary domain for well-defined functions
PT := op(pt);
DC := op(dc);
PDC := combinat[powerset](DC);
s := infinity;
for T in PDC do
S := T union PT;
te := SumOfProductsExpansion(op(S));
if evalb(length(te) < s) then
e := te;
s := length(e);
fi;
od;
if s = infinity then
ERROR(`can't happen`);
else
RETURN(e);
fi;
end:</pre>
Isto é simplesmente uma solução de força bruta para o problema. Rodamos em loop sobre todos os conjuntos possíveis de valores no conjunto de indiferentes '''DC''' que, com efeito, nos permite especificar uma função bem definida exclusiva para a entrada de '''SumOfProductsExpansion'''. Examinemos o comprimento da expressão '''te''' retornada para cada entrada, e, se essa se revelar como menor do que qualquer outra expressão vista até o momento, gravamos como o novo valor de '''e'''. Quando todas as possibilidades forem esgotadas, a variável '''e''' irá conter uma expressão de menor comprimento que representa a função de entrada.
Perceba que existe, de fato, várias expressões que o comprimento é igual a este valor mínimo. Nosso procedimentos retorna a primeira expressão que é encontrada com esse tamanho.
Temos feito este procedimento um pouco mais amigável, projetando-o para que ele aceite ou um par de listas ou um par de conjuntos como entrada.
Note que, como adotado aqui, o comprimento de uma expressão é simplesmente uma medida da sua complexidade. Você pode, por exemplo, desejar contar o número de operadores booleanos na expressão e minimizar esse número. Você poderia mudar este procedimento simplesmente substituindo a função '''length''' por alguma outra medida de complexidade de expressões.
Agora que temos um procedimento para minimização de funções Booleanas, vamos usá-la com alguns exemplos. Considere uma função ''f (x, y, z)'' booleana com a seguinte tabela verdade, em que um d na coluna mais a direita indica uma condição indiferente.
<pre>
x
y
z
false
false
false
true
false
false
true
false
false
true
false
d
true
false
false
d
false
true
true
true
true
false
true
false
true
true
false
false
true
true
true
true</pre>
A entrada é o conjunto
<pre>\{false, false, false, false, true, true, true, true, true\}</pre>
De pontos mapeados para '''true''' (a pré-imgem '''pt''' de '''true'''), e o conjunto
<pre>\{false, true, false, true, false, false\}</pre>
de pontos que nós não nos importamos, ou seja, conjunto de indiferentes. Podemos calcular a expansão da soma de produtos para esta função como pode ver a seguir.
<pre>dcmin(
[false, false, false],
[false, true, true],
[true, true, true],
[false, true, false],
[true, false, false]);</pre>
Como mencionado acima, poderíamos muito bem ter representado a entrada como duas listas:
<pre>dcmin(
[[false, false, false],
[false, true, true],
[true, true, true]],
[[false, true, false],
[true, false, false]]);</pre>
(O primeiro é mais legível, enquanto o último é mais consistente com a entrada para '''SumOfProductsExpansion''').
== '''Cálculos e Explorações''' ==
== '''Exercícios e Projetos''' ==
