Gerador de tabelas verdade
Vamos construir um programa capaz de calcular e mostrar tabelas verdade para expressões booleanas envolvendo and, or e not. Vejamos um exemplo do comportamento esperado do programa. Dada a pergunta
?- gerador_de_tabelas(x or (not y and z)).
O programa deve responder
|
[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 |
Vamos imaginar como uma pessoa resolveria este problema. A primeira coisa que esta pessoa faria é localizar as varíaveis presentes na expressão. Com estas variáveis em mãos ela escreveria em uma folha de papel todos os possíveis valores que estas variáveis poderiam asumir. Para cada conjunto de valores que as varíaveis pudessem assumir ela substituiria-as por seus valores verdade dentro de uma expressão. Após isto começaria a avaliação da expressão assim obtida. Esta avaliação iniciaria por avaliar as expressões entre parenteses primeiro, depois as expressões com o operador not, finalmente avaliar as expressões com or e and. Encontrando um valor verdade para esta expressão ela o anotaria na folha e seguiria para a próxima linha onde está um um novo conjunto de valores para as variáveis, então todo o processo anterior seria repetido até que todos os conjuntos de valores para as variáveis fossem avaliados e o valor verdade da expressão resultante encontrado.
Vamos enumerar os passos, baseados na descrição acima, de tal forma que pudéssemos construir um programa que simule as ações descritas.
Passo 1. Encontrar as variáveis presentes na Expressão. Chamaremos o conjunto formado por estas variáveis de Vars.
Passo 2. Enumerar todas as combinações possíveis de valores binários que Vars pode assumir. Chamaremos este conjunto de ValoresBinarios.
Passo3. Para cada elemento V pertencente a ValoresBinarios faça:
3.1. Substitua todas as variáveis Vars na Expressão pelos valores encontrados em V. À nova expressão encontrada chamar-se-á Expressao1.
3.2. Avalie Expressao1 e anote o resultado R na tabela.
Passo 4. Mostre a tabela encontrada no passo 3.
Com o algoritmo dado acima podemos passar à construção de um programa que o realize. Vamos descrever o programa de maneira top-down. O programa inteiro é dado na listagem 1 e no arquivo prog1.pl
Inicialmente descreveremos os operadores and, or e not :
:- op(300,xfx,[and,or]).
:- op(200,fy,[not]).
Nesta declaração vemos que os operadores and e or possuem notação infixa ( o operador vem entre os operandos) e o operador not possui notação prefixa ( o operador vem antes do operando). Vemos também que not é associativo a direita e possui prioridade maior do que and e or.
O predicado no nível superior do nosso programa é
gerador_de_tabelas( Expressao ):- nl,
isole_variaveis( Expressao,Vars ), % Passo 1
length( Vars, N ), % número total de variáveis em Vars.
gerador_binario( N, ValoresBinarios ), % Passo 2
avalie_expr( ValoresBinarios, Vars, Expressao, Tabela ), % Passo 3
imprima_tabela( Expressao, Vars, Tabela ). % Passo 4
O predicado isole_variaveis tem a função de pegar uma expressão booleana , encontrar as variáveis nela presentes e devolver um conjunto sem repetição com estas variáveis. Este predicado é dado abaixo. Note a recursão na estrutura da expressão boolena para obter as variáveis e também o uso do predicado uniao que faz a união entre dois conjuntos.
isole_variaveis(Expr1 or Expr2,Vars):-
isole_variaveis(Expr1,Vars1),
isole_variaveis(Expr2,Vars2),
uniao(Vars1,Vars2,Vars).
isole_variaveis(Expr1 and Expr2,Vars):-
isole_variaveis(Expr1,Vars1),
isole_variaveis(Expr2,Vars2),
uniao(Vars1,Vars2,Vars).
isole_variaveis(not Expr,Vars):-
isole_variaveis(Expr,Vars).
isole_variaveis(X,[X]).
O segundo passo do algoritmo acima é implementado pelo predicado gerador_binario que na verdade é um contador binário de N bits que começa em 0 e segue até 111...1 onde o número de 1's é N.
O passo 3 do algoritmo é feito pelo predicado avalie_expr que é responsável pela geraração da tabela verdade para a expressão dada. Vejamos a sua definição.
avalie_exp([],_,_,[]).
avalie_exp([V|Vs],Vars,Expressao,[(V,R)|Tab]):-
associe(V,Vars,Expr,Expressao1), % Passo 3.1
tabela_verdade(Expressao1,R), % Passo 3.2
avalie_exp(Vs,Vars,Expressao,Tab).
Por último o passo 4 do algoritmo é feito pelo predicado imprima_tabela cuja implementação é encontrada na listagem 1.
Considere a implementação do predicado tabela_verdade, dado abaixo.
tabela_verdade(1 or _Expr,1).
tabela_verdade(0 or Expr,R):-
tabela_verdade(Expr,R).
tabela_verdade(Expr1 or Expr2,R):-
tabela_verdade(Expr1,R1),
tabela_verdade(Expr2,R2),
tabela_verdade(R1 or R2,R).
tabela_verdade(0 and _Expr,0).
tabela_verdade(1 and Expr,R):-
tabela_verdade(Expr,R).
tabela_verdade(Expr1 and Expr2,R):-
tabela_verdade(Expr1,R1),
tabela_verdade(Expr2,R2),
tabela_verdade(R1 and R2,R).
tabela_verdade(not Expr,R):-
tabela_verdade(Expr,R1),
nao(R1,R).
tabela_verdade(X,X).
Neste predicado usamos algumas simplificações dadas pela lógica entre estas estão:
1 - 1 or X = 1 , isto é se a primeiro argumento de or for 1 então não precisamos avaliar o segundo argumento para sabermos que o resultado será 1.
2 - 0 and X = 0. Argumento análogo ao anterior.
3 - Expr1 Op Expr2. Temos neste caso que pelo menos um dos argumentos do operador Op é uma expressão. Neste caso o resultado final da avaliação será igual à aplicação do operador Op ao resultado da avaliação de Expr1 e ao resultado da avaliação de Expr2.
O programa dado na listagem 1 foi executado usando SWI - Prolog versão 3.2 .4 em uma máquina PC 486 DX4 com 100 Mhz. Note que na seção intutulada "Dados de Teste", existem algumas definições de predicados. Alguns destes são exemplos de utilização do programa enquanto outros são utilizados como estatísticas de execução. Estes últimos talvez não executem na sua máquina se a versão de Prolog que você estiver usando diferir da nossa. Entretanto procure o manual de referência para o seu Prolog e tente encontrar predicados similares.
Agora que temos um programa que realiza a tarefa requerida, vamos melhorá-lo, torná-lo mais eficiente. A orientação tomada aqui é aquela encontrada em [STERLING 86]. Porém antes de fazermos isto vamos colher algumas estatísticas sobre as quais nos basear para testarmos se as mudanças feitas melhoraram ou não o nosso programa. Para faremos a seguinte pergunta
?- estatisticas(6).
A qual o sistema responderá
[y, x, z] (x and (y or z))and ( (x and y)or (x and z))
---------------------------------------------
[0, 0, 0] 0
[0, 0, 1] 0
[0, 1, 0] 0
[0, 1, 1] 1
[1, 0, 0] 0
[1, 0, 1] 0
[1, 1, 0] 1
[1, 1, 1] 1
---------------------------------------------
708 inferences in 0.06 seconds (11800 Lips)
Numero total de definicoes de atomos = 2384
Numero total de pares nome/aridade definidos = 1110
Numero total de definicoes de predicados = 1395
Numero total de byte codes em todas as clausulas 33598
A velocidade de programas escritos em linguagens de programação lógica como Prolog é usualmente medido em LIPS (Logical Inferences per Second), ou inferências lógicas por segundo. Uma inferência lógica corresponde a uma redução na computação.
O livro indicado possui o seguintes conselhos para a obtenção de melhores programas Prolog:
Vejamos como poderemos utilizar estas regras para otimizar o nosso programa.
A regra 1 pode ser utilizada em predicados que fazem recursão em listas reduzindo-as em tamanho até a lista vazia. Assim predicados do tipo
pred([],Arg1,..ArgN).
pred([X|Xs],Arg1,...ArgN):-
pred_1(X,Arg1,...,ArgM),
pred(Xs,Arg1,...,ArgN).
Podem ser transformados em
pred([X|Xs],Arg1,...ArgN):-
pred_1(X,Arg1,...,ArgM),
pred(Xs,Arg1,...,ArgN).
pred([],Arg1,..ArgN).
Apenas com uma reordenação de cláusulas, isto faz com que o programa fique mais eficiente pois no primeiro trecho cada chamada de pred invoca uma unificação com a primeira cláusula esta unificação somente será bem sucedida apenas uma vez, a saber, quando a lista estiver vazia todas as demais unificações significam perda de tempo.
Bem façamos estas modificações na listagem l , o resultado encontra-se no arquivo prog2.pl . Chamaremos o sistema com a mesma pergunta anterior, isto é
?- estatisticas(6).
Ao que o sistema agora responderá
[y, x, z] (x and (y or z))and ( (x and y)or (x and z))
---------------------------------------------
[0, 0, 0] 0
[0, 0, 1] 0
[0, 1, 0] 0
[0, 1, 1] 1
[1, 0, 0] 0
[1, 0, 1] 0
[1, 1, 0] 1
[1, 1, 1] 1
---------------------------------------------
708 inferences in 0.05 seconds (14160 Lips)
Numero total de definicoes de atomos = 1422
Numero total de pares nome/aridade definidos = 956
Numero total de definicoes de predicados = 1296
Numero total de byte codes em todas as clausulas 22402
Compare os números dados acima com aqueles dados na primeira chamada. Nada mal, hein! Aumentamos o número de LIPS em aproximadamente 20 %.
Vamos tentar usar a regra 2 e ver se conseguimos melhorar ainda mais o nosso programa. Esta regra diz-nos para eliminar o não-determininismo. Uma computação é determinística quando existe somente um ponto de escolha no programa, uma vez feita esta escolha nenhuma outra será possível.
Para tornar uma computação não-determinística em determinística podemos usar o corte (!). O uso indiscriminado do corte pode causar lesões irreversíveis em seu programa, assim devemos considerar alguns casos de aplicação dele.
Situação 1: Temos uma cláusula do tipo A:- B1,B2,...,Bn,A. Os bons compiladores Prolog possuem um mecanismo chamado recursão de cauda que podem otimizar cláusulas do tipo acima gerando código mais eficiente. Entretanto para garantir esta otimização podemos transformar a cláusula anterior em A:- B1,B2,...,Bn,!,A.
Situação 2: Em um predicado
A.
A:- B1,B2,...,Bn.
Podemos colocar o corte na primeira cláusula de A. Entretanto isto pode alterar totalmente a semântica do programa e pode levar um programa correto mas ineficiente em um programa altamente eficiente e totalmente incorreto. Portanto cuidado neste tipo de uso.
Bem, aplicando a regra dois ao programa anterior obtemos o programa dado na listagem 2 abaixo e no arquivo prog3.pl.
|
:- op(300,xfx,[and,or]). :- op(200,fy,[not]).
gerador_de_tabelas( Expressao ):- nl, isole_variaveis( Expressao, Vars ), % Vars é o conjunto de variáveis em Expressão. length( Vars, N ), % número de variaveis em Vars. gerador_binario( N, ValoresBinarios ), % gera todas as combinacoes binarias possiveis para as N variaveis binarias avalie_expr( ValoresBinarios, Vars, Expressao, Tabela ), imprima_tabela( Expressao, Vars, Tabela ).
isole_variaveis(Expr1 or Expr2,Vars):- !, isole_variaveis(Expr1,Vars1), isole_variaveis(Expr2,Vars2), uniao(Vars1,Vars2,Vars). isole_variaveis(Expr1 and Expr2,Vars):- !, isole_variaveis(Expr1,Vars1), isole_variaveis(Expr2,Vars2), uniao(Vars1,Vars2,Vars). isole_variaveis(not Expr,Vars):- !, isole_variaveis(Expr,Vars). isole_variaveis(X,[X]). imprima_tabela(Expr, Vars, Tabela):- write(Vars), tab(7), write(Expr),nl, write('---------------------------------------------'),nl, imprime_tab(Tabela). imprime_tab([(V,R)|Tab]):- write(V),tab(15),write(R),nl, !, imprime_tab(Tab). imprime_tab([]):- write('---------------------------------------------'),nl. gerador_binario(N,[Zeros|Vs]):- vetor(N,0,Zeros), % gera uma lista com N zeros gera(N,Zeros,Vs).
avalie_expr([V|Vs],Vars,Expressao,[(V,R)|Tab]):- associe(V,Vars,Expressao,Expressao1), % associa os valores binarios em V as variaveis Vars em Expr tabela_verdade(Expressao1,R), % usa a tabela verdade para determinar o valor da expressao Expr1 !, avalie_expr(Vs,Vars,Expressao,Tab). avalie_expr([],_,_,[]).
associe([V|Vs],[Var|Vars],Expr1,Expr):- substituir(Var,V,Expr1,Expr2), !, associe(Vs,Vars,Expr2,Expr). associe([],[],Expr,Expr).
tabela_verdade(1 or _Expr,1):- !. tabela_verdade(0 or Expr,R):- !, tabela_verdade(Expr,R). tabela_verdade(Expr1 or Expr2,R):- tabela_verdade(Expr1,R1), tabela_verdade(Expr2,R2), !, tabela_verdade(R1 or R2,R). tabela_verdade(0 and _Expr,0):- !. tabela_verdade(1 and Expr,R):- !, tabela_verdade(Expr,R). tabela_verdade(Expr1 and Expr2,R):- tabela_verdade(Expr1,R1), tabela_verdade(Expr2,R2), !, tabela_verdade(R1 and R2,R). tabela_verdade(not Expr,R):- tabela_verdade(Expr,R1), !, nao(R1,R). tabela_verdade(X,X).
nao(0,1). nao(1,0).
substituir(Var, V, Expr1 or Expr2, Expr1_s or Expr2_s ):- substituir(Var, V, Expr1, Expr1_s), substituir(Var, V, Expr2, Expr2_s), !. substituir(Var, V, Expr1 and Expr2, Expr1_s and Expr2_s ):- substituir(Var, V, Expr1, Expr1_s), substituir(Var, V, Expr2, Expr2_s), !. substituir(Var,V,not Expr,not Expr_s):- !, substituir(Var,V,Expr,Expr_s). substituir(Var,V,Var,V). substituir(_,_,Var,Var).
gera(N,Anterior,[]):- vetor(N,1,Anterior). % Anterior é uma lista com N 1's. gera(N,Anterior,[Atual|Proximos]):- sucessor(Anterior,Atual), !, gera(N,Atual,Proximos).
vetor(1,X,[X]). vetor(N,X,[X|Zs]):- N > 1, !, N1 is N - 1, vetor(N1,X,Zs).
sucessor(Xs,Ys):- inverte(Xs,Sx), % inverte uma lista soma_1(Sx,Sx1), inverte(Sx1,Ys).
soma_1([0|Xs],[1|Xs]). soma_1([1|Xs],[0|Ys]):- soma_1(Xs,Ys).
inverte(Xs,Sx):- inverte(Xs,[],Sx).
inverte([X|Xs],Ac,Sx):- !, inverte(Xs,[X|Ac],Sx). inverte([],Ac,Ac).
uniao([X|Xs],Y,[X|Zs]):- not (member(X,Y)), !, uniao(Xs,Y,Zs). uniao([X|Xs],Y,Zs):- member(X,Y), !, uniao(Xs,Y,Zs). uniao([],Y,Y).
member(X,[X|_]):- !. member(X,[_|Y]):- member(X,Y).
concatena([X|Xs],Ys,[X|Zs]):- !, concatena(Xs,Ys,Zs). concatena([],Ys,Ys).
%%% Dados de Teste
% O predicado abaixo foi feito para medir algumas caracteristiscas deste % programa em tempo de execucao estatisticas(N):- time(teste(N)), statistics(atoms,A), statistics(functors,F), statistics(predicates,P), statistics(codes,C), write('Numero total de definicoes de atomos = '),write(A),nl, write('Numero total de pares nome/aridade definidos = '),write(F),nl, write('Numero total de definicoes de predicados = '),write(P),nl, write('Numero total de byte codes em todas as clausulas '),write(C),nl.
teste(N):- expressao(N,Expr),gerador_de_tabelas(Expr).
expressao(1,x or (not y and z)). expressao(2,not x and y). expressao(3,x or not x). expressao(4,x and not y). expressao(5, (x and y) and not(not x or not y)). % lei de De Morgan expressao(6, (x and (y or z)) and ((x and y) or (x and z))). % distributiva |
Consultaremos novamente o sistema Prolog.
?- estatisticas(6).
[y, x, z] (x and (y or z))and ( (x and y)or (x and z))
---------------------------------------------
[0, 0, 0] 0
[0, 0, 1] 0
[0, 1, 0] 0
[0, 1, 1] 1
[1, 0, 0] 0
[1, 0, 1] 0
[1, 1, 0] 1
[1, 1, 1] 1
---------------------------------------------
708 inferences in 0.00 seconds (Infinite Lips)
Numero total de definicoes de atomos = 1422
Numero total de pares nome/aridade definidos = 956
Numero total de definicoes de predicados = 1296
Numero total de byte codes em todas as clausulas 22428
Uma vez mais, comparando os dados anteriores com estes vemos que o tempo gasto pelo computador caiu de 0.05 para algo em torno de 0.00 , o que significa que o tempo total gasto é menor que 0.01. Infelizmente não podemos mais obter as LIPS do sistema pois o tempo gasto está além de sua precisão. Contudo esta nova versão representa uma melhora em relação à anterior.
Os operadores and e not, assim como or e not formam um conjunto completo do cálculo de primeira ordem. Isto é, dados um dos operados binários e not podemos construir tabelas verdades para os demais operadores de primeira ordem como -> (if), <-> (equivalência) baseados nas tabelas dos dois escolhidos. Por exemplo se escolhermos or e not , podemos usar as seguintes fórmulas para obter as tabelas verdade de -> e de <->
x -> y == not x or y
x <-> y == x -> y and y -> x
Como um exercício será deixado para o leitor ampliar o programa dado de maneira a termos um gerador de tabelas verdade para qualquer expressão na lógica de primeira ordem. Indo um pouco mais longe podemos usar avalie_expr para checar se uma expressão é uma tautologia (uma expressão em que todas as avaliações possíveis levam a um 1 como resposta) ou uma contradição (uma expressão em que todas as avaliações possíveis levam a um 0 como resposta). Construa tal programa.
Conclusão
Partindo de uma visão declarativa do problema construimos um programa inicial que era claro e correto. A partir deste fizemos algumas transformações que preservaram a semântica, ao menos no uso pretendido, e obtivemos um programa bem mais eficiente do aquele.
[STERLING 86] STERLING, L. e SHAPIRO, E., "The Art of Prolog", MIT Press series in logic programming, 1986.