Prolog-Exame-Tipo-00-Gabarito

Prévia do material em texto

— Fundamentos e prática de Prolog —
Disciplina: Lógica Aplicada à Computação
Nome: Matŕıcula:
1. Considere a seguinte base de conhecimentos Prolog:
filho(paulo,pedro). % "Paulo é filho de Pedro"
filho(paulo,marcela).
filho(pedro,josé).
filho(pedro,isabel).
filho(josé,luiz).
filho(josé,ana).
filho(tiago,luiz).
filho(tiago,gabriela).
filha(lúcia,ana). % "Lúcia é filha de Ana"
filha(lúcia,luiz).
filha(carol,luiz).
filha(carol,fernanda).
filha(isabel,jo~ao).
filha(isabel,fernanda).
filha(maria,luiz).
filha(maria,gabriela).
sexo(marcela,‘feminino’). % "Marcela é do sexo feminino"
sexo(ana,‘feminino’).
sexo(fernanda,‘feminino’).
sexo(gabriela,‘feminino’).
sexo(luiz,‘masculino’).
sexo(jo~ao,‘masculino’).
Estenda esta base de conhecimentos acrescentando regras para os predicados irm~aos/2 (filhos de pelo menos um progenitor comum, qualquer que
seja o sexo), tiaavó/2 (irmã de um dos avós) e trifamı́lia/3 (dois homens e uma mulher, onde a mulher tem filhos com cada um dos homens, ou
duas mulheres e um homem, onde o homem tem filhos com cada uma das mulheres). Escreva sempre um comentário com o significado de cada novo
predicado introduzido.
Nota. Você pode estender os predicados primitivos da base de conhecimentos acima, caso necessite, mas somente pela adição de novas regras, nunca
de novos fatos. Você também pode utilizar predicados auxiliares para facilitar a tarefa acima —mas não poderá se referir a eles nas tarefas abaixo.
Lógica Aplicada à Computação Fundamentos e prática de Prolog
Soluções.
% regras para a relaç~ao irm~aos/2
% (filhos, de qualquer sexo, com pelo menos um progenitor em comum)
% predicado auxiliar, que será usado aqui e novamente logo adiante:
filhoa(X,Y) :- filho(X,Y). % "X é filho ou filha de Y"
filhoa(X,Y) :- filha(X,Y).
% definiç~ao principal
irm~aos(X,Y) :- filhoa(X,Z), % "X é irm~ao ou irm~a de Y"
filhoa(Y,Z),
X \== Y.
% para usar tiaavó/2 (irm~a de um dos avós) de forma a cobrir
% toda a base de conhecimento, devemos antes de mais nada estender
% o predicado primitivo sexo/2 pela adiç~ao de novas regras:
sexo(X,‘masculino’) :- filho(X,_). %"X é do sexo masculino"
sexo(X,‘feminino’) :- filha(X,_).
% um predicado auxiliar que pode ser útil adiante é o seguinte:
netoa(U,V) :- filhoa(U,Z), % "U é neto ou neta de V"
filhoa(Z,V).
% definiç~ao principal
tiaavó(X,Y) :- netoa(Y,W), % "X é tia-avó de Y"
irm~aos(W,X),
sexo(X,‘feminino’).
% regras para trifamı́lia/3
% (dois homens e uma mulher, onde a mulher tem filhos com cada um dos homens,
% ou duas mulheres e um homem, onde o homem tem filhos com cada uma das mulheres)
% predicado auxiliar:
filhocasal(T,U,V) :- filhoa(T,U), "T é filho ou filha da m~ae U com o pai V"
filhoa(T,V),
sexo(U,‘feminino’),
sexo(V,‘masculino’).
% definiç~ao principal
trifamı́lia(X,Y,Z) :- filhocasal(_,Z,X), "X e Y têm filhos em comum com Z"
filhocasal(_,Z,Y),
X \== Y.
trifamı́lia(X,Y,Z) :- filhocasal(_,X,Z),
filhocasal(_,Y,Z),
X \== Y.
Prof. João Marcos 2
Lógica Aplicada à Computação Fundamentos e prática de Prolog
Em seguida, formule as seguintes consultas à base de conhecimentos, usando somente os predicados supra-mencionados de forma expĺıcita (sejam eles
primitivos, definidos ou estendidos ao longo da solução da tarefa anterior):
(a) Quais são os filhos de Luiz ou de João que não são filhos de Fernanda?
(b) Quem é a avó paterna de Paulo?
(c) Paulo tem tias-avós por parte de pai? Em caso afirmativo, quem são elas?
(d) Quais são os irmãos dos irmãos de Tiago que são eles próprios irmãos de Tiago?
Apresente todas as respostas relevantes, na mesma ordem mas sem repetição, que o compilador Prolog daria a cada uma destas consultas.
Soluções.
(a) ?- (filho(X,luiz);filha(X,luiz);filho(X,jo~ao);filha(X,jo~ao)),
not(filho(X,fernanda);filha(X,fernanda)).
X = josé ;
X = tiago ;
X = lúcia ;
X = maria ;
false.
Nota: observe que puramente a partir da sintaxe não temos por que concluir que Paulo seria do sexo masculino e que não poderia portanto ser
“filha” de ninguém — de fato, tudo que sabemos sobre o significado da string “filha” é o que a base de conhecimentos nos informa; a “interpretação
pretendida” desta string como um predicado é sempre algo extra-lingúıstico, e alheio assim ao campo de conhecimento do compilador Prolog.
(b) ?- (filho(paulo,X) ; filha(paulo,X)), sexo(X,’masculino’),
filho(X,Y), sexo(Y,’feminino’).
X = pedro
Y = isabel ;
false.
Nota: a resposta procurada é o termo atribúıdo a Y.
(c) ?- tiaavó(_,paulo).
true .
?- setof(X,tiaavó(X,paulo),Z).
Z = [carol, lúcia, maria].
(d) ?- irm~aos(X,tiago),irm~aos(X,Y),irm~aos(Y,tiago).
Y = lúcia ;
Y = carol ;
Y = maria ;
Y = josé ;
false.
Nota: fica exclúıda assim Isabel, que é irmã de Carol, uma das irmãs de Tiago. . . Com efeito, a relação de irmandade não é transitiva.
Prof. João Marcos 3
Lógica Aplicada à Computação Fundamentos e prática de Prolog
No caso da consulta (b) acima, apresente em detalhe o procedimento de resolução usado pelo compilador na obtenção da resposta.
Solução.
A consulta que fizemos foi a seguinte:
:- (filho(paulo,X);filha(paulo,X)), sexo(X,‘masculino’), filho(X,Y), sexo(Y,‘feminino’).
Note que esta consulta inicial, que contém uma disjunção, é equivalente em Prolog às duas consultas seguintes, nesta ordem:
:- filho(paulo,X), sexo(X,‘masculino’), filho(X,Y), sexo(Y,‘feminino’).
:- filha(paulo,X), sexo(X,‘masculino’), filho(X,Y), sexo(Y,‘feminino’).
Mostraremos assim o processo de resolução para estas duas cláusulas. Começamos o processo percorrendo a base de conhecimentos da esquerda para
a direita e de cima para baixo, buscando alguma regra (ou fato) cuja cabeça contenha uma expressão que unifique com o literal filho(paulo,X). Dáı,
segue o [Passo 1]:
:- filho(paulo,X), sexo(X,‘masculino’), filho(X,Y), sexo(Y,‘feminino’). filho(paulo,pedro).
σ1 = [X 7→ pedro]
:- filho(paulo,pedro), sexo(pedro,‘masculino’), filho(pedro,Y), sexo(Y,‘feminino’). filho(paulo,pedro).
:- sexo(pedro,‘masculino’), filho(pedro,Y), sexo(Y,‘feminino’).
Em seguida, buscaremos na base de conhecimentos alguma regra (ou fato) cuja cabeça unifique com o
literal sexo(pedro,‘masculino’). A tarefa terminaria neste ponto se não tivéssemos estendido o predicado
primitivo sexo de modo a obter respostas completas para o predicado tiaavó/2, na primeira tarefa acima.
Nestas condições, temos então o seguinte [Passo 1.1]:
:- sexo(pedro,‘masculino’), filho(pedro,Y), sexo(Y,‘feminino’). sexo(X1,‘masculino’) :- filho(X1, ).
σ1.1 = [X1 7→ pedro]
:- sexo(pedro,‘masculino’), filho(pedro,Y), sexo(Y,‘feminino’). sexo(pedro,‘masculino’) :- filho(pedro, ).
:- filho(pedro,Y), sexo(Y,‘feminino’), filho(pedro, ).
Continuando, no [Passo 1.1.1]:
:- filho(pedro,Y), sexo(Y,‘feminino’), filho(pedro, ). filho(pedro,josé).
σ1.1.1 = [Y 7→ josé]
:- filho(pedro,josé), sexo(josé,‘feminino’), filho(pedro, ). filho(pedro,josé).
:- sexo(josé,‘feminino’), filho(pedro, ).
Prof. João Marcos 4
Lógica Aplicada à Computação Fundamentos e prática de Prolog
Seguimos no [Passo 1.1.1.1]:
:- sexo(josé,‘feminino’), filho(pedro, ). sexo(X2,‘feminino’) :- filha(X2, ).
σ1.1.1.1 = [X2 7→ josé]
:- sexo(josé,‘feminino’), filho(pedro, ). sexo(josé,‘feminino’) :- filha(josé, ).
:- filho(pedro, ), filha(josé, ).
Os passos seguintes, 1.1.1.1.1 e 1.1.1.1.1.1, envolvem variáveis anônimas, para as quais não há unificação
envolvida, mas apenas uma resposta booleana determińıstica do Prolog:
:- filho(pedro, ), filha(josé, ). filho(pedro,josé).
:- filha(josé, ).
:- filha(josé, ).
fail
Como a avaliação da consulta acima não foi bem sucedida em eliminar todos os literais, dadas as regras
e unificações escolhidas, força-se um backtracking até o último ponto em que houve uma escolha, a saber,
a unificação σ1.1.1.1. Como não há nova opção de escolha, neste ponto, o backtracking continuaaté o
[Passo 1.1.1.1], e aqui também não há nova opção de escolha. Backtrackings até a unificação σ1.1.1 e em
seguida ao correspondente [Passo 1.1.1] que nos dá finalmente uma opção, que chamaremos de [Passo 1.1.2]:
:- filho(pedro,Y), sexo(Y,‘feminino’), filho(pedro, ). filho(pedro,isabel).
σ1.1.2 = [Y 7→ isabel]
:- filho(pedro,isabel), sexo(isabel,‘feminino’), filho(pedro, ). filho(pedro,isabel).
:- sexo(isabel,‘feminino’), filho(pedro, ).
Continuamos agora pelo [Passo 1.1.2.1]:
:- sexo(isabel,‘feminino’), filho(pedro, ). sexo(X3,‘feminino’) :- filha(X3, ).
σ1.1.2.1 = [X3 7→ isabel]
:- sexo(isabel,‘feminino’), filho(pedro, ). sexo(isabel,‘feminino’) :- filha(isabel, ).
filho(pedro, ), filha(isabel, ).
Dáı seguem, deterministicamente, de forma abreviada, os seguintes passos 1.1.2.1.1 e 1.1.2.1.1.1:
filho(pedro, ), filha(isabel, ). filho(pedro,isabel).
filha(isabel, ). filha(isabel,jo~ao).
⊥
Prof. João Marcos 5
Lógica Aplicada à Computação Fundamentos e prática de Prolog
Atingimos assim por fim à cláusula vazia. Conclusão do [Passo 1.1.2.1.1.1], com relação à consulta original:
X = pedro
Y = isabel
Forçando agora um backtracking para obter outras eventuais respostas à consulta original, retornamos
sucessivamente à unificação σ1.1.2.1, à regra escolhida no [Passo 1.1.2.1], à unificação σ1.1.2, ao literal
escolhido no [Passo 1.1.2], à unificação σ1.1, à regra escolhida no [Passo 1.1], à unificação σ1 e ao literal
escolhido no [Passo 1]. Como todos estes backtrackings falham, acabamos retornando portanto à segunda
regra de nossa consulta original, naquele que podeŕıamos denominar [Passo 2]:
:- filha(paulo,X), sexo(X,‘masculino’), filho(X,Y), sexo(Y,‘feminino’).
:- filha(paulo,X), sexo(X,‘masculino’), filho(X,Y), sexo(Y,‘feminino’).
fail
A nova avaliação não é bem-sucedida pois não há expressão que unifique com o literal filha(paulo,X). Logo, não há essencialmente novas respostas
à consulta original (a rigor, o Prolog apresentará outras vezes a mesma resposta anterior, antes de falhar) senão aquela já exibida ao fim do [Passo
1.1.2.1.1.1].
Prof. João Marcos 6