109
edits
Changes
Jump to navigation
Jump to search
→Representação de Funções Booleanas
== '''Representação de Funções Booleanas''' ==
Vimos anteriormente como, dada uma expressão booleana, é muito fácil escrever um procedimento Maple que é representado por essa expressão booleana. É uma questão simples de envolver uma expressão em uma chamada de procedimento. Nesta seção, vamos olhar para o que pode ser considerado, em certo sentido, o problema oposto. Isto é, dada uma função booleana, expressa como uma tabela de valores, como podemos encontrar uma expressão booleana que a representa? Agora, precisamos entender primeiro que, uma vez que a álgebra booleana lida com um domínio de apenas dois valores, certas simplificações são possíveis, o que não estaria presente se estivéssemos lidando com, digamos, funções reais.
Agora podemos ver por que álgebra booleana é, de certa forma, mais simples do que algumas outras áreas da álgebra. A fim de especificar uma função booleana-valorizada f (qualquer que seja seu domínio), é necessário apenas especificar que valores do domínio de f são mapeados para 1. O resto do domínio de f deve ser mapeado para 0! (De mesmo modo, pode-se especificar que valores de f são mapeados para 0, e o restante seria necessariamente mapeados para 1.)
Isso funciona porque as pré-imagens dos pontos no contradomínio de qualquer função de partição de domínio da função. Para as funções booleano-valorizado, existe exatamente dois conjuntos na partição, um para cada um dos valores booleanos em seu contradomínio. (Um dos dois conjuntos pode estar vazio.)
Esta ideia é a chave para o método descrito no texto para determinar a expressão booleana representando uma dada função booleana, e é o princípio sobre o qual devemos basear nosso procedimento Maple para computar tais expressões.
Vamos escrever um programa Maple que, quando alimentada a pré-imagem sob uma função booleana do valor '''true''', computará uma expressão booleana que representa aquela função. Depois, devemos ver uma técnica para achar uma boa expressão que represente uma determinada função. O procedimento que devemos escrever aqui computará a chamada representação da '''soma de produtos'''.
O primeiro passo é projetar a(s) entrada(s) do procedimento. Como foi discutido acima, apenas é necessário especificar a pré-imagem de (digamos) '''true''' (isto é, de 1) de acordo com nossa função. Isso significa que precisamos entrar com os valores como n-tuplas que, baseado na aplicação de nossa função, produz o valor '''true'''.
Vamos considerar uma função bem simples ''f(x,y,z)'', de três variáveis, com a seguinte tabela de verdade.
x y z
0 0 0 1
0 0 1 0
0 1 0 1
1 0 0 0
0 1 1 1
1 0 1 0
1 1 0 1
1 1 1 1
Temos que especificar que a tripla ''(a,b,c)'', no domínio de ''f'', são mapeadas para 1. No caso, esta é a lista
(0 0 0), (0 1 0), (0 1 1), (1 1 0), (1 1 1)
de triplas. Então, este é o tipo de entrada que devemos fornecer ao noso procedimento. Uma vez que isso é feito, resulta que os pontos restantes
(0 0 1), (1 0 0), (1, 0, 1)
no domínio de ''f'' são mapeados para 0 - não é necessário especificar isso diretamente.
Agora, uma vez que sabemos quais n-tuplas no domínio de nossa função são mapeados por ela para 1, precisamos encontrar um '''MinTerm''' (termo mínimo) correspondente para cada uma dessas n-tuplas. Vamos escrever isso como uma subrotina para nosso procedimento principal
<pre>getMinTerm := proc(ll)
local e, # the minterm, to be returned
t, # temporary variable
i; # loop index</pre>
checar argumento,
<pre> if not type(ll, list(boolean)) then
ERROR(`expecting a list of boolean values`);
fi;</pre>
fazer a construção,
<pre> for i from 1 to nops(ll) do
if ll[i] = true then
t := `x`.i;
else
t := `not x`.i;
fi;
if i = 1 then
e := t;
else
e := cat(e, ` and `, t);
fi;
od;</pre>
e adicionar parênteses para melhorar a legibilidade.
<pre>RETURN(cat(`(`, e, `)`));
end:</pre>
Este procedimento implementa o algorítmo do texto para computação de um minitermo para representar uma pré-imagem de 1 (representada no Maple como '''true'''). Para encontrar o minitermo correspondente para uma tripla (1,0,1) que, no Maple é escrita como ''true, false, true'', computamos
<pre>getMinTerm([true, false, true]);</pre>
Ao ter determinado '''MinTerm''' para cada uma das pré-imagens de 1, tudo que resta a fazer é determinar a soma desses '''MinTerm'''. Isto será realizado pelo procedimento principal de nosso programa
<pre>SumOfProductsExpansion := proc()
local e, # expression to return
i; # loop variable</pre>
se não há argumentos, a função é identicamente ‘false’
<pre> if nargs = 0 then
RETURN(`false`);
fi;
for i from 1 to nargs do
if not type(args[i], list(boolean)) then
ERROR(`arguments must be lists of booleans`);
fi;
if i = 1 then
e := getMinTerm(args[i]);
else
e := cat(e, ` or `, getMinTerm(args[i]));
fi;
od;
RETURN(e);
end:</pre>
Podemos usar este programa para encontrar uma expressão booleana que representa a nossa função de exemplo a seguir.
<pre>SumOfProductsExpansion(
[false, false, false],
[false, true, false],
[false, true, true],
[true, true, false],
[true, true, true]
);</pre>
== '''Minimização de Expressões Booleanas e Circuitos''' ==
== '''Condições Indiferentes''' ==
== '''Cálculos e Explorações''' ==
== '''Exercícios e Projetos''' ==
