Lógica para Programação - ULisboa

Lógica para Programação

João Pavão Martins

• Mecanismo para construir tipos de dados estruturados

• O termo composto é o tipo básico para a construção de novos tipos de dados

• As listas correspondem a uma estrutura, representada internamente por um termo composto cujo functor é o ponto “.”

• Representação interna da lista [a, b, c]

Estruturas

• Definir o tipo data, agregando um dia, um mês e um ano

• Usamos o functor data/3 cujos argumentos representam respetivamente o ano, o mês e o dia dessa data

• data(A, M, D) representa a data cujo ano é A, cujo mês é M e cujo dia é D

• Um termo corresponde a uma entidade, ou seja, data(A, M, D) não faz nenhuma afirmação, mas sim corresponde a uma data (data(2021,4,16)é hoje)

Estruturas – tipo data

bissexto(A) :- number(A), A mod 4 =:= 0, A mod 100 =\= 0.bissexto(A) :- number(A), A mod 4 =:= 0,

A mod 100 =:= 0, A mod 400 =:= 0.

Estruturas – tipo data operações básicas

bissexto(A) :- number(A), A mod 4 =:= 0, A mod 100 =\= 0.bissexto(A) :- number(A), A mod 4 =:= 0,

A mod 100 =:= 0, A mod 400 =:= 0.

faz_data(A, M, D, data(A, M, D)) :- number(A), number(M),number(D), membro(M, [1, 3, 5, 7, 8, 10, 12]), D >= 1, D =< 31.

...faz_data(A, M, D, data(A, M, D)) :- number(A), number(M), number(D),

M =:= 2, bissexto(A), D >= 1, D =< 29.

...


ano_de(data(A, _, _), A).mes_de(data(_, M, _), M).dia_de(data(_, _, D), D).


ano_de(data(A, _, _), A).mes_de(data(_, M, _), M).dia_de(data(_, _, D), D).

muda_ano(A, data(_, M, D), Dt) :- faz_data(A, M, D, Dt).muda_mes(M, data(A, _, D), Dt) :- faz_data(A, M, D, Dt).muda_dia(D, data(A, M, _), Dt) :- faz_data(A, M, D, Dt).

eh_data(X) :- X = data(A, M, D), faz_data(A, M, D, _).


O puzzle dos missionários e canibais

• Técnica de Inteligência Artificial

• Conceito de estado uma possível configuração do problema

• Exemplo na margem esquerda estão os três missionários, os três canibais e o barco e na margem direita não está nada

• A passagem de um estado para outro estado, chamado o sucessor é feita aplicando uma operação legal do problema (expansão de um estado)

• Exemplo uma travessia de barco com pessoas

Procura em espaço de estados

• Representação de estado (estado inicial)


• Representação de estado (estado inicial)

• Sucessores de estado


b, c, c, c, m, m, m

M. Esq. M. Dir.

c, c, m, m b, c, m c, c, c, m b, m, mc, m, m, m b, c, c

M. Esq. M. Dir. M. Esq. M. Dir. M. Esq. M. Dir. M. Esq. M. Dir.

c, c, m, m, m b, c

M. Esq. M. Dir.

c, c, c, m, m b, m

• Remoção de estados inválidos


b, c, c, c, m, m, m

M. Esq. M. Dir.

c, c, m, m b, c, m c, c, c, m b, m, mc, m, m, m b, c, c

M. Esq. M. Dir. M. Esq. M. Dir. M. Esq. M. Dir. M. Esq. M. Dir.

c, c, m, m, m b, c

M. Esq. M. Dir.

c, c, c, m, m b, m

• Representação de estados – estruturas

• estado(ME, MD)

• ME e MD são listas ordenadas, representado as entidades que estão nas margens esquerda e direita

• Seletores

• margem_esq(estado(ME, _), ME).

• margem_dir(estado(_, MD), MD).

• Estado inicial: estado([b, c, c, c, m, m, m], [])

• Estado final: estado([], [b, c, c, c, m, m, m])


% O barco e duas pessoas movem-se da margem esquerda para a margem direitasucessor(estado(ME1, MD1), estado(ME2, MD2)) :-

membro(b, ME1),

remove(ME1, [b], ME_s_b),

escolhe(ME_s_b, P1, ME_s_P1),

escolhe(ME_s_P1, P2, _),

junta(MD1, [b, P1, P2], MD2D),

ordena(MD2D, MD2),

remove(ME1, [b, P1, P2], ME2),

nao_se_comem(ME2),

nao_se_comem(MD2).


?- resolve_mc.[b,c,c,c,m,m,m] [][c,m,m,m] [b,c,c][b,c,c,m,m,m] [c][m,m,m] [b,c,c,c][b,c,m,m,m] [c,c]

[c,m] [b,c,c,m,m][b,c,c,m,m] [c,m][c,c] [b,c,m,m,m][b,c,c,c] [m,m,m][c] [b,c,c,m,m,m][b,c,c] [c,m,m,m][] [b,c,c,c,m,m,m]true.


Remoção de elementos repetidosRemove/2: o literal rem_rep(L1, L2) afirma que a lista L2 tem os mesmos elementos que a lista L1 mas sem elementos repetidos

O operador de corte

Remoção de elementos repetidosRemove/2: o literal rem_rep(L1, L2) afirma que a lista L2 tem os mesmos elementos que a lista L1 mas sem elementos repetidos

rem_rep([], []).

rem_rep([P | R], L) :- membro(P, R), rem_rep(R, L).

rem_rep([P | R], [P | L]) :- rem_rep(R, L).

O operador de corte

?- rem_rep([a, c, a, b, c], X).

X = [a, b, c] .

O operador de corte

?- rem_rep([a, c, a, b, c], X).

X = [a, b, c] .

?- rem_rep([a, c, a, b, c], X).

X = [a, b, c] ;

X = [c, a, b, c] ;

X = [a, a, b, c] ;

X = [a, c, a, b, c] ;

false.

O operador de corte

O operador de corte

rem_rep([], []).

rem_rep([P | R], L) :-

membro(P, R),

rem_rep(R, L).

rem_rep([P | R], [P | L]) :-

rem_rep(R, L).

O operador de corte

rem_rep([], []).

rem_rep([P | R], L) :-

membro(P, R),

rem_rep(R, L).

rem_rep([P | R], [P | L]) :-

rem_rep(R, L).

• É possível dizer ao PROLOG que a partir de certo ponto não deve procurar mais soluções

• O operador de corte altera a semântica procedimental do PROLOG, reduzindo o espaço de procura através de um controle explícito sobre o mecanismo de retrocesso

• Vantagem• Possibilidade de indicar que certos ramos da árvore SLD que se sabe que não

produzem soluções, não devem ser explorados (corte verde)

• Desvantagem• Possibilidade de alterar inadvertidamente a semântica declarativa de um

programa (corte vermelho)

O operador de corte

• Representado por “!”

• Átomo especial, utilizado como um literal numa cláusula• O objetivo “!” tem sempre sucesso

• Como efeito secundário, a avaliação deste átomo origina a introdução de uma “barreira” no ramo da árvore SLD em que a cláusula com o operador de corte aparece

• Essa barreira não pode ser ultrapassada durante o retrocesso

O operador de corte

rem_rep([], []).

rem_rep([P | R], L) :- membro(P, R),

!,

rem_rep(R, L).

rem_rep([P | R], [P | L]) :- rem_rep(R, L).

O operador de corte

• Semântica do operador de corte• Seja G um objetivo que utiliza uma cláusula C cujo corpo contém o operador

de corte. • O operador de corte compromete o PROLOG com todas as escolhas que

foram feitas desde a unificação com a cláusula C até ao operador de corte. O operador compromete também o PROLOG com a escolha de C para responder ao objetivo G.

• É possível explorar outras alternativas utilizando o objetivo G.

O operador de corte

O operador de cortea(X, Y) :- q(X, Y).

a(0, 0).

q(X, Y) :- i(X), !, j(Y).

q(5, 5).

i(1).

i(2).

j(1).

j(2).

j(3).

Corte verdeparte/4: sendo N um inteiro, e L, L1 e L2 listas de inteiros, o literal parte(L, N, L1, L2) afirma que a lista L1 contém todos os elementos de L menores que N e a lista L2 todos os elementos de L maiores ou iguais a N

parte([], _, [], []).

parte([P | R], N, [P | R1], L2) :- P < N, parte(R, N, R1, L2).

parte([P | R], N, L1, [P | R2]) :- P >= N, parte(R, N, L1, R2).

Corte verdeparte/4: sendo N um inteiro, e L, L1 e L2 listas de inteiros, o literal parte(L, N, L1, L2) afirma que a lista L1 contém todos os elementos de L menores que N e a lista L2 todos os elementos de L maiores ou iguais a N

parte([], _, [], []).

parte([P | R], N, [P | R1], L2) :- P < N, parte(R, N, R1, L2).

parte([P | R], N, L1, [P | R2]) :- P >= N, parte(R, N, L1, R2).

parte([], _, [], []) :- !.

parte([P | R], N, [P | R1], L2) :- P < N, !, parte(R, N, R1, L2).

parte([P | R], N, L1, [P | R2]) :- P >= N, !, parte(R, N, L1, R2).

Corte vermelhoparte([], _, [], []) :- !.






parte([], _, [], []).


parte([P | R], N, L1, [P | R2]) :- parte(R, N, L1, R2).




parte([], _, [], []).


parte([P | R], N, L1, [P | R2]) :- parte(R, N, L1, R2).

?- parte([4, 8, 1, 10], 7, [], [4, 8, 1, 10]).

true.

Documents

Lógica para Programação - ULisboa