Negação como falha
O predicado de negação-como-falha 'not' pode ser definido no Prolog da seguinte forma:
not(P) :- call(P), !, fail.
not(P).O objetivo ?-call(P) força uma tentativa de satisfazer o objetivo P. A maioria dos interpretadores Prolog tem uma versão embutida deste predicado. Quintus, SWI e muitos outros prólogos usam '\+' em vez de 'not'.
A seção 3.2 discute o predicado de corte do Prolog '!'.
Outra maneira de escrever a definição 'not' é usando o operador de implicação Prolog '->':
not(P) :- (call(P) -> fail ; true)
O corpo pode ser lido como "se a chamada (P) for bem-sucedida (ou seja, se P for bem-sucedido como um objetivo), então falhar, caso contrário, terá sucesso". O ponto e vírgula ';' aparecendo aqui tem o significado de lógico de um 'ou-exclusivo'.
Haverá vários usos de 'not' em programas subsequentes neste capítulo.
É importante perceber que em um objetivo ?-not(g), se g tem variáveis, e alguma instância dessas variáveis leva à satisfação de g, então ?-not(g) falha. Por exemplo, considere o seguinte 'programa bachelor':
bachelor(P) :- male(P), not(married(P)).
male(henry).
male(tom).
married(tom).Então...
?- bachelor(henry).
yes
?- bachelor(tom).
no
?- bachelor(Who).
Who= henry ;
no
?- not(married(Who)).
no.As três primeiras respostas estão corretas e conforme o esperado. A resposta à quarta pergunta pode ter sido inesperada no início mas considere que o objetivo ?-not(married(Who)) falha porque para a ligação variável Who=tom, married(Who) é bem-sucedida, e então o objetivo negativo falha. Assim, não se pode esperar que objetivos negativos ?-not(g) com variáveis produzam ligações das variáveis para as quais o objetivo g falha.
A definição da árvore de cláusulas do programa nas seções anteriores foi planejada para programas sem negação como falha. Para programas que têm negação como falha nos corpos das cláusulas do programa, a definição de uma árvore de cláusulas do programa e a definição de uma consequência com base nessas árvores precisam ser cuidadosamente formuladas. Vamos motivar isso com exemplos cuidadosamente escolhidos aqui, e deixar mais considerações teóricas na Seção 8.8.
Para o exemplo, considere o programaFor the example, consider the program
p(X) :- q(X), not(r(X)).
r(X) :- w(X), not(s(X)).
q(a). q(b). q(c).
s(a). s(c).
w(a). w(b).Considere os três conjuntos de árvores de cláusulas a seguir.
Agora, o primeiro conjunto (transversal) é usado para mostrar que p(a) é uma consequência do programa, o segundo conjunto pode ser usado para mostrar que p(b) não é uma consequência do programa, e o terceiro conjunto mostra que p(c) é uma consequência do programa. Observe que as árvores de cláusulas agora são desenhadas de forma que os nós negativos not(g) sejam folhas, e novas árvores com raízes em g são investigadas.
Exercício 2.5.1 Carregue o programa exemplo no Prolog e verifique se o Prolog computará as respostas de acordo com nossa determinação de consequências.
Exercício 2.5.2 Considere a seguinte modificação do programa exemplo.
p(X) :- q(X), not(r(X)).
r(X) :- w(x), not(s(X)).
q(a). q(b). q(c).
s(a) :- p(a). s(c).
w(a). w(b).O que acontece agora se alguém tentar argumentar se p(a) é ou não uma consequência deste programa? Isso mostra que as dificuldades são encontradas se houver recursão por meio da negação. O que acontecerá se permitirmos que o Prolog tente o objetivo ?-p(a).?
Exercício 2.5.3 Considere o seguinte programa.
u(X) :- not(s(X)).
s(X) :- s(f(X)).
O que acontece com este exemplo se alguém tentar determinar as consequências com base em árvores de cláusulas? O que o Prolog faz quando recebe o objetivo ?-u(1).? s(1) é uma consequência do programa?
Os dois últimos exercícios mostram que programas com negação como falha podem ser problemáticos se houver recursão por meio de negação ou se a negação de algum literal ilimitado for considerada. Consulte a Seção 8.8 para uma discussão mais aprofundada deste tópico.