Álgebra Booleana

Muitas situações podem ser, e são, modeladas usando um sistema que tem-se um de dois estados quaisquer. Dependendo do contexto, o par de estados pode ser conhecido por verdadeiro e falso, ou ligado e desligado ou bom e mau, e assim por diante. Exemplos teóricos que vêm à mente ao mesmo tempo são as afirmações precisas que são feitas em ciências matemáticas e físicas, que são considerados como sendo verdadeiro ou falso. Entre as aplicações mais importantes está a modelagem de circuitos digitais em computadores, em que interruptores eletronicos podem também ser ligados ou desligados. Agora, veremos como Maple pode ser usado para manipular sistemas algébricos aritméticos, e para modelar as suas leis, ou regras, simbolicamente. Assim também, podemos modelar a aritmética da álgebra booleana. Na verdade, álgebra booleana é de certo modo mais simples que álgebra numérica, por isso é mais fácil. (Pelo menos, será, uma vez que ela se torne familiar para você).

Funções Booleanas

No Maple, há um construtor do tipo booleano, isto é, um tipo de variável que pode ser usada para representar valores booleanos. Existem apenas dois valores booleanos e no Maple eles são representados pelos literais true e false. Para o Maple, estes são dois valores constantes, assim como o numero 2 ou a matriz identidade 3x3 são constantes. Se você atribuir alguma dessas duas constantes para uma variável então o valor da variável será um valor constante.

a := true;
b := false;

Dois valores constantes por si só não são muito interessantes. Para fazer coisas úteis, nós precisamos ser capazes de realizar operações significativas sobre elas. Para tal, Maple oferece dois conjuntos de operadores booleanos para realizar operações em variáveis booleanas e literais. O primeiro conjunto consiste nos operadores and, or e not. Em Maple também é disponibilizado os operadores &and, &or e &not para operar sobre literais booleanos e variáveis com simplicidade. Eles estão disponíveis no pacote logic da linguagem. A diferença entre os dois conjuntos esta na forma em que as expressões formadas usando eles são simplificadas, por exemplo:

true and false;
true &and false;

O primeiro operador and produz seu valor imediato, enquanto que o segundo &and é mais útil para trabalhar simbolicamente com expressões booleanas, ou seja, para estudar a forma de uma expressão ao invés de seu valor. Um pequeno cuidado é necessário em como usar o operador &not. É muito importante que as expressões sejam suficientemente definidas com parenteses (Primeiramente, retiramos qualquer valor de a)

a := 'a';

Enquanto

not not a;

é um código Maple perfeitamente válido, a construção

&not &not a;

conduz, como podemos ver, a um erro de sintaxe. Ao invés disso, a ultima expressão deve ser escrita como

&not (&not a);

provendo nível extra com os parênteses. O operador booleano and é um operador binário, ele modela a semântica lógica and.

true and true;
true and false;
false and true;
false and false;

Estes quatro exemplos, exaure todos os possíveis argumentos do operador and. Nos veremos que o resultado de aplicamos and para dois valores booleanos é true, precisamente quando o valor de ambos os operandos é true. Da mesma forma, o exemplo acima mostra que and é um operador comutativo. De fato, o segundo e o terceiro exemplo acima constituem uma prova deste fato. Do mesmo modo, nós podemos mostrar que o operador or é comutativo. Seu comportamento pode ser completamente determinado pela aplicação dele sobre todos os possíveis pares de seus argumentos. (Faça isto agora!) O operador not, é um pouco diferente dos dois operadores binários &and e or, no fato que not é um operador (prefixo) unário. Seu efeito é alternar entre os dois valores booleanos.

not true;
not false;

Os resultados não são muito surpreendentes. Os operadores booleanos no Maple tem uma série de outras propriedades das quais você deve estar ciente. Ambos, and e or são operadores associativos. Por exemplo, dizer que and é um operador binário significa que sobre ele é aplicado dois argumentos de uma vez. Se nós desejarmos computar o valor de and para três valores ditos a, b e c, então duas expressões distintas serão formadas: (a and b) and c assim como a and (b and c). A propriedade associativa do operador and assegura que ambas expressões mencionadas tem o mesmo valor. Na verdade, tendo isso sido estabelecido, um argumento indutivo pode ser dado para mostrar que para qualquer sequência do tipo a1, a2...an de valores booleanos, todas as formas de colocação de parênteses nessa sequência tem o mesmo valor. O resultado disso é que parênteses podem ser descartados. O resumo de essa discussão é que as expressões do Maple, tais como

a and b and c and d;

são inteiramente não ambíguos. Exatamente a mesma coisa é verdadeira para o operador or. Outra propriedade da qual você deve atentar é que not não é uma involução. Isto é,

not not  a;

Em outras palavras, a segunda aplicação de not desfaz o efeito da primeira. Você pode fazer exatamente a mesma coisa com as tão faladas variantes inertes desses operadores (aquelas com o & prefixado em seus nomes). No entanto, nenhuma simplificação automática ocorrerá. Isto porque operadores booleanos inertes são usados primeiramente para trabalhar simbolicamente com operações booleanos; eles são operadores sobre os quais as ferramentas do pacote logic do Maple são baseados. Por exemplo, usando o operador inerte &not, nós veremos que a expressão

&not( &not ( a ) );

Não é simplesmente a.

Um Avaliador Booleano

Antes de prosseguir, será conveniente introduzir uma nova função do Maple evalb. Este é um avaliador geral para expressões booleanas . A expressão booleana é simplesmente uma expressão válida no Maple construída a partir de valores booleanos, variáveis ​​e operadores. No entanto, também é possível produzir valores booleanos a partir de outros tipos de expressões no Maple, como nas expressões aritméticas. Por exemplo, a expressão 2 = 3 e 3.14 = 3.14 são duas expressões aritméticas cujos valores são booleanos, isto é, true ou false. A função evalb permite avaliar expressões como estas como expressões booleanas valoradas no Maple.

evalb(2 = 3);
evalb(3.14 = 3.14);

É geralmente a partir de expressões como estas (ou seja, práticas) que usualmente são gerados valores booleanos. Você já viu isso ser usado, muitas vezes, nas cláusulas de teste de condicional ( if ... then ... else ) e delarações de looping ( for, while ) no Maple.

Antes de irmos muito adiante, vale salientar que Maple realmente compreende um terceiro valor booleano, ‘fail’. Este é um pouco diferente do discutido no livro, onde apenas dois valores booleanos são reconhecidos. O valor fail é uma adição útil em uma linguagem de programação como Maple, uma vez que pode ser utilizado para indicar que um determinado cálculo não foi completamente processado com êxito. Não deve se confundir fail com false; fail é um valor usado para indicar um erro de cálculo, não um valor booleano normal.

Representando Funções Booleanas

Vamos ver agora como nós podemos representar funções booleanas no Maple. Estas são exatamente como qualquer outra função e pode ser criada usando o comando proc. Por exemplo, a função booelana escrita (usando a notação do livro) como:

F(z,y,z) = xy + yz + zx

pode ser escrita no Maple com o seguinte procedimento

F := proc(x, y, z)
      RETURN((x and y) or (y and z) or (z and x));
    end:

A tradução como você pode ver é bastante simples. Um produto como xy é traduzido diretamente para expressões no Maple como x and y, enquanto a sum x+y é traduzida como x or y. Se vocẽ imaginar que cada produto xy tem um ponto infixo como x.y, então uma simples regra de substituir cada ponto ( . ) por um operador and e também trocar cada + pelo operador or. Os parênteses na hora de definir F acima não são realmente necessários mas ajudam na leitura do programa. (Porque parênteses bem usados nunca doem).

Verificando Identidades Booleanas

É relativamente simples usar Maple para verificar identidades booleanas. Para este tipo de trabalho, nós podemos usar os operadores booleanos inertes. Por exemplo, nós podemos checar as leis distributivas como a seguir:

with(logic);  # for 'bequal()'
left := x &or (y &and z);
right := (x &or y) &and (x &or z);
bequal(left, right);

Aqui, nós usamos a biblioteca Maple bequal, que testa se duas expressões booleanas são equivalentes (retornando um dos valores booleanos true ou false conformemente). Você precisa ter o pacote logic carregado para usar essa função. Se duas expressões booleanas não são logicamente equivalentes, isto pode ser interessante para determinar algumas atribuições de valor para as variáveis que estão nas duas expressões as quais determinam a identidade inputável a falhar. A procedure bequal pode ser dada como um terceiro argumento optativo sob o qual irá ser dado uma tal atribuição se o valor falso for o resultado.

Dual

No Maple, existe uma procedure para encontrar a dupla de uma explressão booleana. Lembre-se que a dupla de uma expressão booleana é obtida trocando cada ocorrência de and e or por or e and respectivamente. Para usar essa procedure você deve carregar o pacote logic;

with(logic):

A procedure é chamada dual (naturalmente) e recebe como argumentos a expressão booleana formada usando as versões inertes dos operadores booleanos.

dual(false);
dual(true);
dual(x &and y);
dual(x &or (&not y &or &not x and &not (&not z)));

A beleza da dualidade é que, uma vez que você provar uma identidade booleana, você pode usar o dual a vontade! 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 e formular nossas expressões usando operadores inertes.

with(logic):  # don't forget to define 'bequal'.
left := (x &and &not y)
	&or (y &and &not z)
	&or (z &and &not x);
right := (&not x &and y)
	&or (&not y &and z)
	&or (&not z &and x);
bequal(left, right);

Agora, nos usamos esta afirmação à vontade.

dual(left);
dual(right);
bequal(%, %%);

Forma Normal Disjuntiva

O Maple provem, em seu pacote logic, uma função para computar a disjunção normal para uma expressão booleana. Esta função é chamada canon (de canônico). Os exemplos a seguir tipificam a chamada sintaxe

with(logic):
canon((a &or b) &and (c &and d), a,b,c,d);
canon((a &or b) &and (&not a &or b), a,b);
canon((a &or b) &and (&not a &or b), b);

O último exemplo mostra que deve haver pelo menos variáveis suficientes ​​para explicar as que figuram no primeiro argumento. O primeiro argumento para canon é a expressão a ser transformada, e o segundo argumento é o conjunto de variáveis ​​que aparecem na forma normal disjuntiva . É possível especificar as variáveis ​​que não aparecem na equação original.

canon(a, a,b);

Na verdade, há um terceiro argumento, opcional para canon, que especifica qual forma canônica produzir. Tanto em um dos três valores DNF (forma normal disjuntiva, o padrão), CNF (forma normal conjuntiva), ou MOD2, que direciona canon para converter o seu primeiro argumento para uma expressão aritmética modulo 2 equivalente (na forma canônica).

canon((a &or b) &and (&not a &or &not b), a,b, DNF);
canon((a &or b) &and (&not a &or &not b), a,b, CNF);
canon((a &or b) &and (&not a &or &not b), a,b, MOD2);

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

getMinTerm    :=  proc(ll)
  local   e,  # the minterm, to be returned
      t,  # temporary variable
      i;  # loop index

checar argumento,

 if not type(ll, list(boolean)) then
      ERROR(`expecting a list of boolean values`);
  fi;

fazer a construção,

 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;

e adicionar parênteses para melhorar a legibilidade.

RETURN(cat(`(`, e, `)`));
end:

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

getMinTerm([true, false, true]);

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

SumOfProductsExpansion    :=  proc()
  local   e,  # expression to return
      i;  # loop variable

se não há argumentos, a função é identicamente ‘false’

 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:

Podemos usar este programa para encontrar uma expressão booleana que representa a nossa função de exemplo a seguir.

SumOfProductsExpansion(
  [false, false, false],
  [false, true, false],
  [false, true, true],
  [true, true, false],
  [true, true, true]
);

Minimização de Expressões Booleanas e Circuitos

Nossa função para encontrar a soma da expansão de produtos de uma função booleana pode levar a circuitos ineficientes, porque o número de portas requeridas para implementá-los diretamente pode ser muito bem superior ao número que é realmente necessário. No entanto, o número de funções booleanas distintas de n variáveis (em que n é um inteiro positivo) é finito - de fato, é igual a $2^{2^{n}}$, como mostrado no texto - é fácil visualizar que o número de expressões booleanas distintas sobre n variáveis é infinito. Algumas formas do Princípio da Casas dos Pombos nos obriga a concluir que algumas funções booleanas têm muitas - na verdade, infinitamente muitas - representações distintas através de expressões booleanas. Da perspectiva de projeto de circuito, portanto, o que é necessário é um método para minimizar um circuito, no sentido em que se deseja, dado um circuito, encontrar um circuito equivalente que usa o menor número de portas quanto possível. A fim de fazer o Maple fazer isso para nós, devemos traduzir o problema da linguagem pictórica de diagramas de circuitos para uma descrição algébrica envolvendo expressões booleanas, reconhecendo que um diagrama de circuito é uma representação pictórica de uma expressão booleana equivalente, onde em uma porta lógica simples representa-se um dos operadores padrões booleanos: and, or e not. Para tornar isso um pouco mais concreto, vamos ver um exemplo simples. A expressão booleana xy + xȳ que, representada na sintaxe de Maple, parece

e := (x &and y) &or (x &and &not y);

pode ser minimizada atarvés da utilização de Maple da seguinte forma

with(logic):
distrib(x &and (y &or &not y));

que mostra que as expressões x ( y + ȳ ) and xy + xȳ representam a mesma função booleana. Porém y + ȳ = 1, para qualquer y

bequal(y &or &not y, true);

de modo que x ( y + ȳ ) simplifica ainda mais para x. O truque consiste em detectar, para uma determinada expressão booleana, as oportunidades para eliminar variáveis, ou reduzir o número de MinTerm, usando as propriedades algébricas de operadores booleanos. Para o exemplo simples acima, este foi muito fácil, e Maple apenas nos permitiu provar que nossas suposições estavam corretas. Mas expressões que são apenas um pouco mais complicadas podem exigir muito mais para detectar tais simplificações. O que precisamos é algo que vai nos permitir trabalhar na direção oposta à que foi tomada acima, ou seja, dada a expressão original, podemos realmente encontrar uma expressão mais simples a que é equivalente? Além disso, podemos encontrar uma que é mínima? Felizmente, o pacote de logic de Maple proporciona um minimizador de circuito que cuida de tudo isso para nós. Ele é chamado bsimp. Para usar esse método, você deve carregar o pacote logic primeiro em sua sessão Maple, ou chamá-lo pelo nome completo logic[bsimp]. Claro, o Maple não fala diretamente em termos de portas e circuitos. Para solicitar ao Maple para minimizar um circuito, você deve falar a linguagem algébrica de Maple, especificando a expressão booleana equivalente. Por exemplo, para simplificar o exemplo anterior

e := (x &and y) &or (x &and &not y);

você pode digitar

with(logic):  # load 'bsimp'
bsimp(e);

Você pode aplicar bsimp a qualquer expressão booleana formada usando os operadores booleanos inertes do pacote logic. Vamos ver como Maple lida com alguns exemplos mais complicados.

with(logic):
e := (w &and x &and y &and (&not z))
	&or (w &and (&not x) &and y &and z)
	&or (w &and (&not x) &and y &and (&not z))
	&or ((&not w) &and x (&not y) &and z)
	&or ((&not w) &and (&not x) &and y &and z)
	&or ((&not w) &and (&not x) &and (&not y) &and z);

O procedimento bsimp é muito complexo, e usa um algoritmo de Quine-McCluskey baseado na representação de expressões booleanas como conjuntos. Estas estruturas de dados, embora muito natural para Maple, não correspondem muito bem com a descrição dada no texto.

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 $2^{d}$ 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 $2^{d}$ 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.

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:

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.

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

A entrada é o conjunto

\{false, false, false, false, true, true, true, true, true\}

De pontos mapeados para true (a pré-imgem pt de true), e o conjunto

\{false, true, false, true, false, false\}

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.

dcmin(
  [false, false, false],
   [false, true, true],
   [true, true, true],
 [false, true, false],
  [true, false, false]);

Como mencionado acima, poderíamos muito bem ter representado a entrada como duas listas:

dcmin(
  [[false, false, false],
   [false, true, true],
   [true, true, true]],
  [[false, true, false],
   [true, false, false]]);

(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 $2^{2^{3}}$ 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 $2^{2^{n}}$ 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

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];

Podemos gerar esse subconjunto usando o procedimento powerset no pacote combinat. Portanto, devemos primeiro carregar o pacote combinat.

with(combinat):

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

writeto(terminal);

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.

with(logic):

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

randbool(a,b);

ou

randbool([a,b]);

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:

for i from 1 to 10 do
  randbool(a,b);
od;

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.

randbool(x,y,z, CNF);
randbool(u,v, MOD2);

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

readlib(trace);

Agora, se gerarmos um expressão aleatória booleana com quatro variáveis

e := randbool(a,b,c,d);

poderemos observar o número de passos necessários para simplificá-lo simplesmente chamando bsimp depois de rastreá-lo

bsimp(e);

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:

untrace(bsimp); # 'bsimp' deixará de ser rastreada

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.

Printlevel;

Mas é possível atribuir um valor a printlevel que afetará o quanto é impresso dentro das estruturas de controle.

for i from 1 to 5 do
  sqrt(i);
od;

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.

for i from 1 to 5 do
  sqrt(sin(abs(i)));
od;

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.

with(logic):  # esteja certo que 'bsimp' está definida
e := x &and y &or &not z;
bsimp(e);

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

interface(verboseproc = 2);
eval(bsimp);  # assuma 'bsimp' carregada

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(`&not`(`&or`(A, B)), `&and`(`&not`(A), `&not`(B)));
                             true
Equivalent(`&not`(`&and`(A, B)), `&or`(`&not`(A), `&not`(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, `&not`(b)), `&implies`(b, `&not`(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, `&not`(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

Maple: Chapter 10. Boolean Algebra, Kenneth H. Rosen