109
edits
Changes
Jump to navigation
Jump to search
no edit summary
Enquanto é possível usar Maple para provar uma identidade pela força bruta, isto é, checando cada valor possível das variáveis, o pacote '''logic''' oferece uma solução mais elegante.
Como um exemplo disto, vamos usar o Maple para provar a identidade
[[File:imagemimagem2.png|200px]]
e formular nossas expressões usando operadores inertes.
<pre>with(logic): # don't forget to define 'bequal'.
== '''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 [[File:imagem.png|100px]].
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''' ==
Nesta seção, vamos olhar para Problemas 2 e 6 da seção de computações e explorações do texto, e ver como podemos usar Maple para resolver alguns deles.
Construa a tabela da função booleana de grau 3.
'''Solução'''
Primeiro, nós devemos notar que existem <math>2^{2^{3}}</math> funções booleana de grau 3, então a saída da nossa computação será longa. Podemos usar a função '''SumOfProductExpansion''' que desenvolvemos anteriormente para nos ajudar com esse cálculo. Lembre que a expansão da soma dos produtos, ou forma normal disjuntiva, da função booleana dará uma correspondência bijetiva entre funções booleanas e certas expressões booleanas.
Embora haja um número infinito de expressões booleanas, há precisamente <math>2^{2^{n}}</math> formas normais disjuntivas com n variáveis, e elas estão em bijetiva correspondência com o conjunto de todas as funções boolenas de n variáveis, portanto essa é a conveniente representação de uso.
Para gerar a lista inteira nós precisamos especificar todas as possibilidades distintas de listas de argumentos de '''SumOfProductsExpansion'''. Isso significa que nós devemos gerar o subconjunto do domínio de todas as funções boolenas de três variáveis. Agora, a função booleana f de três variáveis tem domínio igual a
<pre>Dom3 := [false,false,false],
[false,false,true],
[false,true,false],
[true,false,false],
[true,false,true],
[true,true,false],
[false,true,true],
[true,true,true];</pre>
Podemos gerar esse subconjunto usando o procedimento '''powerset''' no pacote '''combinat'''. Portanto, devemos primeiro carregar o pacote '''combinat'''.
<pre>with(combinat):</pre>
Note o formulário de saída. Nós obtemos o conjunto dos conjuntos, enquanto nosso procedimento '''SumOfProductsExpansion''' requer uma expressão sequência de listas booleanas. Isso significa que precisamos usar a função '''op''' do Maple também. Agora podemos gerar a lista de funções booleanas em três variáveis usando um loop de '''for''' simples: Você pode querer escrever a saída para um arquivo para ter melhores condições de examiná-lo. Você pode fazer isso usando a função '''printf''' no lugar de '''print'''. Alternativamente, você pode usar as funções '''writeto''' ou '''appendto''' para redirecionar a saída Maple para um arquivo. Assim que estiver pronto, você pode restaurar a saída do terminal, emitindo a chamada
<pre>writeto(terminal);</pre>
Use a facilidade help do Maple para saber mais sobre essas funções, se necessário.
Randomicamente, gere dez expressões de grau 4 e determine a média do número de passos para minimizá-los.
'''Solução'''
Há realmente duas partes para este problema: Primeiro, precisamos encontrar uma maneira de gerar expressões booleanas aleatórias. Em segundo lugar, temos de encontrar algum método de examinar o processo de minimização para que possamos contar os passos.
Maple oferece uma solução fácil para a primeira parte do problema. No pacote '''logic''', existe um procedimento chamado '''randbool''' que gera uma expressão booleana aleatória. Uma vez que é parte do pacote de lógica, ele poderá ser definido antes de ser utilizado.
<pre>with(logic):</pre>
Para usar '''randbool''', você precisa especificar um alfabeto sobre o qual construir expressões booleanas. Por exemplo, para gerar uma expressão booleana aleatória no símbolos '''a''' e '''b''', você pode digitar
<pre>randbool(a,b);</pre>
ou
<pre>randbool([a,b]);</pre>
Ou seja, o alfabeto pode ser especificado como um conjunto ou como uma lista. Note que os resultados das duas chamadas acima são diferentes - as expressões são geradas randomicamente. (Isso é verdade mesmo após o '''restart'''. Você pode tentar isso também, mas não se esqueça de carregar o pacote '''logic''' novamente). Agora, para gerar dez expressões booleanas aleatórias, podemos simplesmente usar um “loop” '''for''':
<pre>for i from 1 to 10 do
randbool(a,b);
od;</pre>
Note também que as expressões são gerados na forma normal disjuntiva, isto é, uma soma de produtos de expansão. Também é possível especificar um segundo argumento '''randbool''' de que afeta a forma das expressões geradas. O segundo argumento pode ser qualquer um entre os valores '''DNF''', '''CNF''' ou '''MOD2''', assim como o procedimento '''canon''' que nos conhecemos antes.
<pre>randbool(x,y,z, CNF);
randbool(u,v, MOD2);</pre>
Tendo resolvido a primeira parte do problema, precisamos encontrar uma maneira de contar o número de passos dados durante o processo de minimização. Existem três abordagens que podemos tomar para esta parte do problema.
A primeira é a de medir o tempo necessário para executar um procedimento. Você já viu isso antes em capítulos anteriores.
O segundo é a facilidade de rastreamento para monitorar o número de passos dados para executar uma minimização. Você pode rastrear um procedimento de bordo emitindo a chamada
<pre>readlib(trace);</pre>
Agora, se gerarmos um expressão aleatória booleana com quatro variáveis
<pre>e := randbool(a,b,c,d);</pre>
poderemos observar o número de passos necessários para simplificá-lo simplesmente chamando '''bsimp''' depois de rastreá-lo
<pre>bsimp(e);</pre>
O traçado de '''bsimp''' irá imprimir uma série de declarações do formulário B: = < algo >, que você pode contar. Nós não os temos mostrado aqui.
O procedimento '''trace''' na verdade faz com que a execução de '''bsimp''' para imprimir mais informações do que precisamos. Algumas dessas informações podem ser ignorados para este problema. Cada instrução executada é impressa, como são os argumentos e valores de retorno de qualquer sub-rotinas chamadas. Nós queremos apenas contar o número de instruções executadas, de modo que a outra informação pode ser simplesmente ignorada.
Para anular o efeito do procedimento '''trace''', você pode desfazer a função '''trace''' simplesmente com o procedimento '''untrace''':
<pre>untrace(bsimp); # 'bsimp' deixará de ser rastreada</pre>
Finalmente, para obter o máximo de informações, podemos definir a variável '''printlevel'''. A variável '''printlevel''' é um pouco confusa, ou seja, não se sabe se ela é global ou local. Como qualquer variável global, é visível no nível superior do Maple. No entanto, o seu valor é alterado cada vez que entra em uma estrutura de controle, como um loop, ou no corpo do procedimento e, em seguida, reseta para seu valor original depois de sair da estrutura. Normalmente, '''printlevel''' é definido como 1.
<pre>Printlevel;</pre>
Mas é possível atribuir um valor a '''printlevel''' que afetará o quanto é impresso dentro das estruturas de controle.
<pre>for i from 1 to 5 do
sqrt(i);
od;</pre>
Experimente o ciclo anterior depois de definir o valor de '''printlevel''' para algo como 16. Cada nível aninhado de invocação do procedimento '''printlevel''' é decrementado por 5. Assim, a criação '''printlevel''' a 6 no nível superior é muito parecido com o rastreamento (usando '''trace''') de todos os procedimentos do Maple.
Para fazer Maple mostrar o que se está fazendo a ainda maiores níveis de chamadas de função, simplesmente defina '''printlevel''' para um valor alto.
<pre>for i from 1 to 5 do
sqrt(sin(abs(i)));
od;</pre>
Por razões tipográficas, a volumosa produção foi suprimida neste manual impresso, mas você pode ver os resultados espetaculares na tela do computador. Tente fazer esse último exemplo com '''printlevel''' definindo um valor muito grande como 100000.
Agora, para realmente ver o que está acontecendo quando você invocar '''bsimp''' para minimizar a expressão booleana, você pode definir '''printlevel''' a um enorme valor, e observar os resultados.
<pre>with(logic): # esteja certo que 'bsimp' está definida
e := x &and y &or ¬ z;
bsimp(e);</pre>
Para interpretar os resultados de saída, é aconselhável ser capaz de olhar para o código-fonte do procedimento '''bsimp''' e as sub-rotinas da biblioteca que ele chama. Você pode fazer isso emitindo o seguinte
<pre>interface(verboseproc = 2);
eval(bsimp); # assuma 'bsimp' carregada</pre>
Isso mostra o código fonte real para a função '''bsimp''', embora comentários estão faltando. (Não pode haver comentários porque Maple desmonta o código objeto na biblioteca do Maple, a partir do qual a compilação foi despojado de todos os comentários, para produzir o código de Maple que você vê aqui).
Para entender a saída, você deve perceber que o Maple não fornece acesso a operações de nível de bits, de modo que o algoritmo usado em '''bsimp''' é um pouco diferente do que a descrita em seu livro. Em vez de cadeias de bits, Maple usa conjuntos para representar expressões booleanas.
Com essas ferramentas em mãos, agora você pode escrever um procedimento para gerar, aleatoriamente, dez expressões booleanas em quatro variáveis, e contar o número de passos necessários para minimizar cada um, finalmente a tomar uma média.
== '''Exercícios e Projetos''' ==
01) Use o Maple para verificar a Lei DeMorgan e as leis de comutatividade e associatividade:
.: Leis de DeMorgan :.
Equivalent(`¬`(`&or`(A, B)), `&and`(`¬`(A), `¬`(B)));
true
Equivalent(`¬`(`&and`(A, B)), `&or`(`¬`(A), `¬`(B)));
true
.: Comutatividade :.
Equivalent(`&and`(A, B), `&and`(B, A));
true
Equivalent(`&or`(A, B), `&or`(B, A));
true
.: Associatividade :.
exp1 := `&and`(A, `&and`(B, C));
exp2 := `&and`(`&and`(A, B), C);
Equivalent(exp1, exp2);
true
exp3 := `&or`(A, `&or`(B, C));
exp4 := `&or`(`&or`(A, B), C);
Equivalent(exp3, exp4);
true
02) Use Maple para construir as tabelas verdades para cada um dos seguintes pares de expressões booleanas.
a) a -> b and b -> a
with(Logic):
TruthTable(((a &implies b)&and(b &implies a)), [a,b], output = Matrix);
table([
(true, true) = true,
(false, true) = false,
(false, false) = true,
(true, false) = false ])
b) a -> ¬b and b -> ¬a
with(Logic):
TruthTable(`&and`(`&implies`(a, `¬`(b)), `&implies`(b, `¬`(a))), [a, b], output = Matrix);
table([
(true, true) = false,
(false, true) = true,
(false, false) = true,
(true, false) = true ])
c) a + (b(¬c)) and (a + b +d)(a + c + d)
with(Logic):
TruthTable(`&and`(`&or`(a, `&and`(b, `¬`(c))), (`&or`(`&or`(a, b), c))*(a+c+d)), [a, b, c, d], output = Matrix);
table([
(false, false, true, true) = false,
(true, false, false, true) = false,
(false, false, false, false) = false,
(true, false, true, true) = false,
(false, false, false, true) = false,
(true, true, false, true) = false,
(false, false, true, false) = false,
(true, true, false, false) = false,
(true, false, false, false) = false,
(false, true, true, false) = false,
(true, true, true, true) = false,
(false, true, true, true) = false,
(true, true, true, false) = false,
(false, true, false, false) = false,
(true, false, true, false) = false,
(false, true, false, true) = false ])
== Referências ==
[http://www.mhhe.com/math/advmath/rosen/r5/student/ch10/maple.html Maple: Chapter 10. Boolean Algebra, Kenneth H. Rosen]
