Gerador de Tabela Verdade

O objetivo desta seção é desenvolver um programa Prolog para calcular e exibir tabelas verdade para expressões booleanas envolvendo 'e', 'ou' e 'não'. Procuramos o seguinte tipo de comportamento de programa:

?- tt(x or (not y  and z)).

  [x,y,z]          x or (not y and z)
-----------------------------------
  [0,0,0]                0
  [0,0,1]                1
  [0,1,0]                0
  [0,1,1]                0
  [1,0,0]                1
  [1,0,1]                1
  [1,1,0]                1
  [1,1,1]                1
-----------------------------------

Portanto, o programa deverá fazer o seguinte:

reconhecer expressões booleanas infixas envolvendo operações booleanas 'and', 'or' e 'not'
encontrar as variáveis em uma expressão booleana
gerar uma atribuição de verdade inicial para tantas variáveis quantas houver na expressão
avaliar a expressão em uma atribuição de verdade particular
gerar a próxima atribuição de verdade na ordem de contagem binária

Para usar 'and' e 'or' como operadores infixos, declarações como as seguintes serão suficientes

:- op(1000,xfy,'and').
:- op(1000,xfy,'or').

O operador 'not' pode já ser reconhecido pelo Prolog (como negação como falha), mas se não, então a declaração

:- op(900,fy,'not').

fará 'not' vincular mais firmemente do que 'and' e 'or'. Em geral, provavelmente será melhor usar parênteses nas expressões booleanas, em vez de tentar descobrir um esquema de precedência infalível que o usuário do programa precise conhecer.

Para encontrar as variáveis em uma expressão booleana, propomos uma definição Prolog cujo perfil é

find_vars(+The_Expression,+Previously_Found_Variables,-Answer)

indicando que a expressão e as variáveis encontradas anteriormente são fornecidas em uma chamada e que a resposta é "limitada" pelo programa.

find_vars(N,V,V) :- member(N,[0,1]),!.    /* Boolean constants in expression */
find_vars(X,Vin,Vout) :- atom(X), 
                         (member(X,Vin) -> Vout = Vin ;   /* already have  */
                            Vout = [X|Vin]).                 /* include           */
find_vars(X and Y,Vin,Vout) :- find_vars(X,Vin,Vtemp),
                               find_vars(Y,Vtemp,Vout).
find_vars(X or Y,Vin,Vout) :-  find_vars(X,Vin,Vtemp),
                               find_vars(Y,Vtemp,Vout).
find_vars(not X,Vin,Vout) :-   find_vars(X,Vin,Vout).

Por exemplo,

?- find_vars(x and (y or x), [], V).
V = [y,x]

Observe que 'find_vars' produzirá uma lista de variáveis em sua ordem de ocorrência da direita para a esquerda na expressão original. Por quê? Reverteremos essa lista de variáveis no programa principal.

Para gerar a atribuição de verdade inicial, use a lista de variáveis como guia:

initial_assign([],[]).
initial_assign([X|R],[0|S]) :- initial_assign(R,S).

Por exemplo,

?- initial_assign([w,x,y,z],A).
A = [0,0,0,0]

O programa para gerar a atribuição de verdade sucessora é o seguinte:

successor(A,S) :- reverse(A,R),
                  next(R,N),
                  reverse(N,S).

Por exemplo, o que é proposto deve funcionar assim...

[0,1,0,1] == reverse ==> [1,0,1,0] ==next==> [0,1,1,0] ==reverse==>[0,1,1,0]

onde o ponto de reversão é que seria mais fácil descrever a adição binária no início de uma lista, em vez de no final de uma lista. O predicado 'next' será um somador binário de N-bits recursivo, onde N é o número de variáveis na expressão booleana.

next([0|R],[1|R]).
next([1|R],[0|S]) :- next(R,S).

Agora, para avaliar a expressão booleana, um avaliador descendente recursivo deve ser fácil de definir. Propomos o seguinte perfil:

truth_value(+Expression,+Variable_List,+Assign_List,-Truth_Value)

de modo que podemos esperar ser capazes de usar isso da seguinte maneira.

?- truth_value(not x or y, [x,y],[1,0],V.
V = 0

Aqui está uma definição para 'true_value'.

truth_value(N,_,_,N) :- member(N,[0,1]).
truth_value(X,Vars,A,Val) :- atom(X),
                             lookup(X,Vars,A,Val).
truth_value(X and Y,Vars,A,Val) :- truth_value(X,Vars,A,VX),
                                   truth_value(Y,Vars,A,VY),
                                   boole_and(VX,VY,Val).
truth_value(X or Y,Vars,A,Val) :-  truth_value(X,Vars,A,VX),
                                   truth_value(Y,Vars,A,VY),
                                   boole_or(VX,VY,Val).
truth_value(not X,Vars,A,Val) :-   truth_value(X,Vars,A,VX),
                                   boole_not(VX,Val).

O predicado 'lookup' usa associação posicional.

lookup(X,[X|_],[V|_],V).
lookup(X,[_|Vars],[_|A],V) :- lookup(X,Vars,A,V).

Agora precisamos do controlador para forçar a geração de toda a tabela verdade. A intenção é construir a tabela verdade por meio de primeiro encontrar as variáveis (já discutidas), calcular uma atribuição de verdade inicial (também já discutida) e, em seguida, preencher a tabela linha por linha, ou, em uma imagem

tt(E) :- find_vars(E,[],V),
         reverse(V,Vars),
         initial_assign(Vars,A),
         write('  '), write(Vars), write('    '), write(E), nl,
         write('-----------------------------------------'), nl,
         write_row(E,Vars,A),
         write('-----------------------------------------'), nl.

onde 'write-row' se chamará para escrever a próxima linha da tabela verdade (se houver uma próxima linha na tabela).

write_row(E,Vars,A) :- write('  '), write(A), write('        '), 
                       truth_value(E,Vars,A,V), write(V), nl,
                       (successor(A,N) -> write_row(E,Vars,N) ; true).

A definição de 'write_row' depende da falha do sucessor quando A == [1,1,1,...,1]. Por último, fornecemos as tabelas de verdade.

boole_and(0,0,0).      boole_or(0,0,0).      boole_not(0,1).
boole_and(0,1,0).      boole_or(0,1,1).      boole_not(1,0).
boole_and(1,0,0).      boole_or(1,0,1).
boole_and(1,1,1).      boole_or(1,1,1).

Exercício 2.13.1 Adicione as operações booleanas 'nand', 'nor' e 'xor' ao programa.

Exercício 2.13.2 Modifique o programa de tabela verdade para que ele grave a tabela em um arquivo com o nome do arquivo fornecido pelo usuário.

Veja Também

Gerador de Tabela Verdade

Veja Também

Menu de navegação

Pesquisa