Changes

É 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.

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.