Á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

Forma Normal Disjuntiva