Lógica Computacional

Licenciatura em Ciências da Computação - 2º ano

Tópicos

Avisos

22/07/2009: Disponíveis notas da época de recurso.

07/05/2009: Disponível enunciado do projecto prático.

06/03/2009: Já disponível o guião da primeira aula prática (aqui).

Aulas Práticas


Aula 8: Predicados de Segunda Ordem

Existem meta-predicados que permitem coleccionar todas as soluções para um dado objectivo de prova (ver User's Manual ou o help).

  • findall(?Template,:Goal,?Bag) : Bag é a lista de instâncias de Template encontradas nas provas de Goal. A ordem da lista corresponde à ordem em que são encontradas as respostas. Se não existirem instanciações para Template, Bag unifica com a lista vazia.
  • bagof(?Template,:Goal,?Bag) : Semelhante a findall, mas se Goal falhar, bagof falha.
  • setof(?Template,:Goal,?Set) : Semelhante a bagof, mas a lista é ordenada e sem repetições.

Exemplo:

| ?- findall(X, member(X,[1,2,3]), L).
L = [1,2,3]
yes

  • Utilize o predicado findall para determinar todas as soluções para o problema das N rainhas com N=8.


Aula 7: Estratégia Gerar e Testar.

Estratégia Gerar e Testar

O mecanismo de backtracking do PROLOG torna possível codificar, de forma directa, a estratégia de gerar e testar para encontrar a solução de um determinado problema. Segundo esta estratégia, o problema é decomposto em duas fases:

  • Gera-se "soluções cadidatas" para o problema.
  • Verifica-se se a "solução candidata" satisfaz os requisitos do problema (e é, portanto, uma "solução efectiva").

Podemos assim identificar o padrão com a seguinte regra PROLOG:

resolve(X) :- gera(X), testa(X).
Note-se o papel preponderante do backtracking para encontrar uma dada solução para resolve(X): o predicado gera(X) instancia X com uma possível solução. No caso de testa(X) falhar (a solução proposta não satisfaz os requisitos impostos pelo problema), o mecanismo de backtracking permite que gera(X) instancie uma nova alternativa, até que se encontre a solução pretendida.

O predicado gera acaba normalmente por se revelar o ponto crítico na aplicação desta estratégia: por um lado, pretende-se que ele cubra todas as possíveis soluções para o problema (caso contrário, podemos nunca gerar a solução requerida). Por outro, e por questões de eficiência, vamos pretender que ele produza o mínimo de soluções erradas (para minimizar o espaço de busca) -- na prática, este esforço de minimização traduz-se por eliminar candidatos notoriamente errados e por encontrar codificações apropriadas para as possíveis soluções.

Vejamos um exemplo concreto: pretende-se encontrar um divisor para um dado número N (diferente de 1 e N).

fromToL(L,U,[]) :- U < L, !.
fromToL(L,U,[L|X]) :- L1 is L+1, fromToL(L1,U,X).

gera(N,X) :- fromToL(2,N-1,L), member(X,L).

testa(N,X) :- N mod X =:= 0.

divisor(N,X) :- gera(N,X), testa(N,X).

Mas o programa apresentado pode ser consideravelmente optimizado se observarmos que nos é suficiente encontrar um divisor entre 2 e sqrt(N) (se X>sqrt(N) é um divisor de N, então também será N/X<sqrt(N)). Dessa forma teríamos:

divisor2(N,X) :- fromtoL(2,sqrt(N),L), member(X,L), N mod X =:= 0.
 

  • Verifique ambos os programas para um número primo elevado (e.g. 209953, 331777, 472393, ...)
  • Utilize a estratégia generate & test para determinar a raiz de um natural, definida da seguinte forma: um número natural X é a raiz de N quando X2<=N e (X+1)2>N

Problema das N rainhas.

Um exemplo clássico de programação em PROLOG consiste em escrever um predicado que permita resolver o problema das n rainhas. Esse problema consiste em dispor n rainas num tabuleiro de damas com dimensão n*n, sem que qualquer rainha se encontre ameaçada por outra. Como um exemplo de uma solução temos (num tabuleiro 4*4):

    Q  
Q      
      Q
  Q    

Note que cada linha e cada coluna deve conter uma, e só uma, rainha (porquê?). Dito isto, verificamos que uma forma expedita de representar as soluções para este problema consiste em utilizar uma lista que informe qual a coluna em que é colocada a rainha de cada uma das linhas (a solução do exemplo seria [3,1,4,2], querendo dizer que a rainha da primeira linha aparece na terceira coluna, a da segunda linha na primeira coluna, etc.) -- desta forma, aparece uma rainha em cada linha "por construção". A restrição de aparecer uma única rainha por cada coluna é traduzida por deverem aparecer na lista todos os números de 1 a 4, ou seja, a lista deve ser uma permutação de [1,2,3,4]. Temos assim resolvido o sub-problema de gerar soluções candidatas: são simplesmente permutações da lista [1..N].

Na fase de teste, falta unicamente verificar que nenhuma rainha está no alcance da diagonal de uma outra. Para isso notamos que:

  • Duas rainhas estão numa diagonal / sse a soma da linha e coluna da posição de cada uma delas for igual;
  • Duas rainhas estão numa diagonal \ sse a diferença da linha e coluna da posição de cada uma delas for igual.

Com base no que foi referido, codifique um predicado nrainhas(+N,?X) que determine uma solução para o problema das N-rainhas.


Aula 6: Manipulação de fórmulas lógicas proposicionais em Prolog.

Definição de Operadores em Prolog.

O Prolog permite definir operadores prefixos, sufixos ou infixos. Para tal devemos utilizar o predicado pré-definido op(=_Prec_,=_Type_=,=_Name_=)=. O argumento Name é o nome do operador definido; Prec é um número entre 0 e 1200 que determinará a sua precedência e Type determina o seu tipo e associatividade. Por exemplo, o operador de soma binário + está definido como op(700, yfx, +). A precedência 700 irá determinar que tenha menos precedência do que a multiplicação (definida com precedência 500 - note que um número menor indica maior precedência do operador), e o tipo yfx caracteriza o operador como infixo e associativo à esquerda. Outras possibilidades para o tipo dos operadores são: xfy, xfx para operadores infixos associativos à direita e sem associatividade; fx, fy para operadores prefixos e xf, yf para operadores sufixos.

Alguns dos operadores pré-definidos do Prolog são:

:- op( 1200, xfx, [ :-, --> ]).
:- op( 1200,  fx, [ :-, ?- ]).
:- op( 1100, xfy, [ ; ]).
:- op( 1000, xfy, [ ',' ]).
:- op(  700, xfx, [ =, is, =.., ==, \==, =:=, =\=, <, >, =<, >= ]).
:- op(  500, yfx, [ +, -]).
:- op(  500,  fx, [ +, - ]).
:- op(  300, xfx, [ mod ]).
:- op(  200, xfy, [ ^ ]).

  • Faça um pequeno predicado que lhe permita confirmar a maior precedência do operador * face ao operador +.

Manipulação de fórmulas lógicas proposicionais em Prolog.

A definição de operadores permite que a sintaxe do Prolog se aproxime do domínio onde se está a trabalhar. Considere que se pretendem representar fórmulas da Lógica Proposicional em Prolog. Em vez de considerar termos como or(not(p), and( and(p, r), not(q))), podemos utilizar operadores que nos permitam aproximar a sua representação da utilizada habitualmente. Assim definimos:

:- op(1130, xfy, <=>). % equivalencia
:- op(1110, xfy, =>).  % implicação
%:- op( 1100, xfy, [ ; ]). % disjunção
%:- op( 1000, xfy, [ ',' ]). % conjunção
:- op( 500, fy, ~).    % negação

Estamos a utilizar os operadores de conjunção e disjunção do Prolog (se preferir, pode definir os operadores /\ e \/). Assim, a fórmula apresentada atrás pode ser escrita como (~p ;  p , r, ~q) (note o papel da precedência e associatividade).

  • Defina um predicado que, dado uma fórmula proposicional, determine a Forma Normal Negativa (FNN).
  • Pretende-se definir um programa que permita verificar se uma dada fórmula é uma contradição pelo método de Davis Putnam. Para o efeito, considere os seguintes predicatos que convertem uma FNN na respectiva Forma Normal Conjuntiva (FNC), e que colocam esta última na sua forma matricial (como uma lista de listas) :
% -----------------------------------------------------------------
%  fnc(+NNF,?FNC)
%
% NNF é uma forma normal negatiiva e FNC a respectiva forma normal conjuntiva
cnf(((A,B);C), (F1,F2)) :- !, cnf((A;C),F1), cnf((B;C),F2).
cnf((A;(B,C)), (F1,F2)) :- !, cnf((A;B),F1), cnf((A;C),F2).
cnf((A;B), F) :- !, cnf(A, A1), cnf(B, B1),
  (/*IF*/ (A1=(C,D); B1=(C,D)) ->
   /*THEN*/ cnf((A1;B1), F) ; 
   /*ELSE*/ F=(A1;B1) ).
cnf((A,B), (A1,B1)) :- !, cnf(A, A1), cnf(B, B1).
cnf(Lit, Lit).

% -----------------------------------------------------------------
%  matCNF(+FNC,?MAT)
%
% FNC é uma forma normal conjuntiva e MAT é a sua representação sob a forma
% de matriz (lista de listas de literais).
matCNF((A,B),M) :- !, matCNF(A,MA), matCNF(B,MB), append(MA,MB,M).
matCNF((A;B),C) :- !, matCNF(A,[CA]), matCNF(B,[CB]), union2(CA,CB,C).
matCNF(~Lit, [[-Lit]]) :- !.
matCNF(Lit, [[Lit]]).

union2([],L,[L]).
union2([X|L1],L2,L3) :- member2(X,L2), !, union2(L1,L2,L3).
union2([X|_],L2,[])  :- (-Xn=X;-X=Xn), member2(Xn,L2), !.
union2([X|L1],L2,L3) :- union2(L1,[X|L2],L3).

member2(X,[Y|_]) :- X==Y, !.
member2(X,[_|T]) :- member2(X,T).


Aula 5: Utilização de cut e negação por falha.

O predicado pré-definido cut (!) permite eliminar ramos nas árvores de derivação de predicados Prolog. Operacionalmente, o cut pode ser caracterizado da seguinte forma: _"Durante o processo de prova, a 1a passagem pelo cut é sempre verdadeira (com sucesso). Se por backtracking se voltar ao cut, então o cut faz falhar o predicado que está na cabeça da regra."_

A utilização do cut está normalmente associada a questões de eficiência: os ramos da árvore que são eliminados acabariam eventualmente por falhar, e assim poupamos trabalho ao motor de inferência do Prolog. Esta utilização do cut é considerada benigna, porque não se afecta o significado dos predicados. Tomemos como exemplo um predicado que verifique se o terceiro argumento é o mínimo dos dois primeiros. Podería ser definido como:

minimo(X,Y,Y) :- X >= Y.
minimo(X,Y,X) :- X < Y.
Mas podemos facilmente observar que, uma vez verificado que X>=Y, não faz sentido tentar verificar que X<Y. Assim sendo, faz sentido colocar um cut no final da primeira cláusula:
minimo(X,Y,Y) :- X >= Y, !.
minimo(X,Y,X) :- X < Y.

  • Estaria correcto eliminar também o predicado X<Y na segunda cláusula? Justifique com exemplos apropriados.

É importante referir que certas utilizações do cut alteram propositadamente o comportamento do programa (tipicamente para impedir que a execução do programa entre em ciclo). Essas utilizações são normalmente consideradas "mais perigosas" porque obriga a que o programador detenha uma ideia muito precisa sobre o processo de construção da derivação por parte do Prolog.

  • Relembre as seguintes alternativas para calcular o multiplicação de naturais:
a(zero, Y, Y).
a(suc(X), Y, suc(Z)) :- a(X,Y,Z).

m1(zero, _, zero).
m1(suc(X), Y, Z) :- a(Y, W, Z), m1(X,Y,W).

m2(zero, _, zero).
m2(suc(X), Y, Z) :- m2(X,Y,W), a(Y, W, Z).
    • Seria possível impedir a computação infinita de m2 por intermédio da introdução de cuts?
    • A introdução de cuts também faria sentido para m1? Onde? Justifique.

  • Considere o seguinte programa que pretende inserir o primeiro argumento (um número) na lista ordenada passada no segundo argumento.
insert(X,[H|T],[H|T1]) :- X>H, !, insert(X,T,T1).
insert(X,L,[X|L]).
    • Mostre, avaliando um objectivo apropriado, que o programa está incorrecto.
    • Como o poderá corrigir?

Negação por falha.

Por vezes pretende-se garantir que um dado predicado não é válido. A utilização do cut (em conjunção com o predicado pré-definido fail que falha sempre) permite codificar uma forma restrita de negação: a "negação por falha". Considere o seguinte predicado:

neg(X) :- X, !, fail.
neg(X).
Note que neg(X) falha sempre que o Prolog consiga construir uma derivação para X. Por outro lado, sucede se falhar na construção dessa derivação (entra na segunda cláusula, que é trivialmente satisfeita). Obs.: o predicado pré-definido do Prolog \+ corresponde ao predicado neg apresentado.

  • Verifique o resultado de neg em predicados já definidos.
  • Considere o seguinte programa:
estudante(paulo). 
casado(joao). 
estudante_solteiro(X) :- \+ casado(X), estudante(X).
    • Como explica a resposta às questões estudante_solteiro(paulo) e estudante_solteiro(X)


Aula 4: Árvores de Prova. Tipos algébricos

Árvores de Prova em Prolog

Operacionalmente, o Prolog segue uma estratégia top down, depth-first para encontrar soluções das questões colocadas. O processo de Unificação permite concretizar as questões colocadas definindo as condições em que a questão inicial é satisfeita (a substituição obtida). Quando o motor de inferência se depara com uma situação de "falha", retrocede na árvore de prova por forma a tentar novas alternativas.

  • Relembre o predicado member que verifica se um elemento pertence a uma lista. Construa a árvore de procura de soluções para a questão member(X,[1,2,3]).
  • Considere agora o predicado takeout/3 referido na última aula. Construa a árvore de procura de soluções para a questão takeout(X,[1,2,3],Y).

Tipos algébricos em Prolog

A utilização de termos permite a manipulação em Prolog de valores de tipos algébricos (que em Haskell seriam declarados com data). Por exemplo, árvores binárias podem ser representadas por termos como vazia, nodo(vazia, vazia), etc.

  • Defina um predicado que verifique se uma lista é uma travessia in-order de uma árvore.
  • Defina predicados que determinem:
    • uma árvore é uma Árvore Binária de Procura
    • uma lista está ordenada.

Note no entanto que em Prolog não existe a noção de tipo. De facto nada nos impede de considerar termos como vazia(nodo,vazia(nodo)).


Aula 3: Continuação da manipulação de listas

  • Defina last/2 que verifique se o último elemento de uma lista é um dado.
  • Defina append/3 que concatene duas listas.
  • Utilize o predicado append para definir os predicados prefixo e sufixo que verificam se uma lista é prefixo ou sufixo doutra.
  • Defina split/4 que separe os elementos de uma lista nos menores e maiores que um dado valor.
  • Considere o predicado:
takeout(X,[X|R],R).
takeout(X,[F|R],[F|S]) :- takeout(X,R,S).
O que faz este predicado?
  • Utilize o predicado takeout para definir um predicado que determine se uma lista é permutação de uma outra.


Aula 2: Utilização de termos, introdução à manipulação de Listas.

Termos Estruturados

Para além dos tipos primitivos, o Prolog admite termos estruturados da forma f(t1,t2,...,tn), onde f é o functor do termo e t1,...tn são sub-termos.

Uma aplicação típica de termos estruturados é para organizar a informação contida num programa. Por exemplo, podemos armazenar datas com termos da forma "data(25,abril,2007)". O seguinte predicado extrai o dia duma data armazenada dessa forma:

diaData(D,data(D,_,_)).

  • Defina o predicado valData/1 que verifique se uma data é correcta.

Nada nos impede de considerarmos termos arbitrariamente complicados. Em particular, podemos considerar termos de natureza recursiva como a representação dos naturais com os construtores zero e suc (i.e. zero, suc(zero), suc(suc(zero)), etc.).

  • Defina o predicado nat/1 que verifique se um termo é um natural na representação referida.
  • Defina soma/3 que verifique se o terceiro argumento é a soma dos dois primeiros.
  • Mostre como usar o predicado soma/3 para calcular a subtração de dois naturais.
  • Defina predicados int2nat/2 e nat2int/2 que convertam naturais em inteiros e vice-versa.

Introdução às Listas em Prolog

Um exemplo de um tipo estruturado que está pré-definido no Prolog são as listas. A sintaxe mais prática é [] que denota a lista vazia e [H|T] que denota a lista com cabeça H e cauda T.

  • Defina member/2 que verifica se um elemento pertence a uma lista.
  • Utilize o predicado member para determinar quais dos elementos da lista [3,5,4,6,5,7] são pares.


Aula 1: Apresentação da linguagem PROLOG

Exemplo de apresentação

Tipos Primitivos

  • Variáveis:
  • Átomos:
  • Inteiros:
  • Reais:

Unificação, Igualdade, Atribuição

  • =
  • ==
  • is


r9 - 29 May 2007 - 10:39:30 - JoseBacelarAlmeida
This site is powered by the TWiki collaboration platform Copyright © by the contributing authors. Ideas, requests, problems? Send feedback.
Syndicate this site RSSATOM