Inteligência Artificial

Aula Prática 5 – Modelos estáveis e programação por conjuntos de resposta

Matéria das aulas T10 (programação em lógica não-monotónica: factos, regras, negação por omissão, modelos estáveis, restrições de integridade) e T11 (programação por conjuntos de resposta: variáveis e instanciação, CLINGO, gerar-e-testar, regras de escolha, agregados, problemas clássicos). Os exercícios são para trabalho autónomo, individualmente ou em grupos de dois, ao longo de duas aulas; os que ficarem por resolver devem ser resolvidos em casa. A parte da lógica de primeira ordem do T10 não é tratada aqui.

Para os exercícios que pedem o CLINGO, instale-o com pip install clingo (fica disponível o comando clingo) ou use a versão online em https://potassco.org/clingo/run/. A referência da sintaxe é o Potassco User Guide (https://potassco.org/doc/).

Exercício 1 – A relva molhada

Considere o programa P₁, sobre os átomos chuva, rega e molhado:

chuva.
molhado :- chuva.
molhado :- rega.

(a) Quantas interpretações (conjuntos de átomos) há sobre estes três átomos? Quais são modelos clássicos de P₁ (cada regra lida como a implicação corpo ⇒ cabeça)? Qual é o modelo mínimo? Calcule Cn(P₁) por iteração.

(b) Troque o facto chuva. por duas regras com negação por omissão — «se não se concluir que chove, regou-se; se não se concluir que se regou, choveu»:

rega  :- not chuva.
chuva :- not rega.
molhado :- chuva.
molhado :- rega.

Quais são os modelos clássicos de P₂? Verifique, pela redução de Gelfond–Lifschitz, quais deles são modelos estáveis. Há algum modelo clássico minimal que não seja estável?

(c) Acrescente a P₂, uma de cada vez, as restrições de integridade :- rega., :- not molhado. e :- molhado.. Em cada caso, que modelos estáveis ficam? Explique a diferença entre «eliminar» e «exigir», e o que significa um programa sem modelos estáveis.

(d) Escreva P₂ num ficheiro relva.lp e corra clingo relva.lp 0. O que significa o 0? O que diz a saída? Acrescente #show molhado/0. e volte a correr — o que mudou? Agora acrescente o facto chuva.: que conclusão desapareceu? Que propriedade da semântica é esta?

(e) Generalize P₂ a vários jardins: jardim(a; b). e as regras com uma variável J — rega(J) :- jardim(J), not chuva(J)., etc. Quantas regras tem ground(P)? Quantos modelos estáveis há, e porquê? Acrescente a restrição «ou chove em todos os jardins ou em nenhum» e confirme no CLINGO.

Exercício 2 – Modelos estáveis à mão

Para cada um dos programas seguintes indique todos os modelos estáveis. Para os programas positivos, calcule Cn(P) por iteração; para os outros, identifique os candidatos razoáveis e verifique-os pela redução.

(a) P₁ (positivo):

cafe.
limao  :- cha.
acucar :- cafe.
leite  :- cafe, acucar.
cha    :- limao.
cha    :- dieta.

Além de Cn(P₁), indique os outros modelos clássicos de P₁ e diga porque é que não são estáveis.

(b) P₂, o mesmo com duas regras trocadas:

dieta  :- not acucar.
cafe   :- not cha.
limao  :- cha.
acucar :- cafe.
leite  :- cafe, acucar.
cha    :- limao.
cha    :- dieta.

Mostre que {acucar, cha, limao} é um modelo clássico minimal de P₂ mas não é estável. Que átomo não está «justificado»?

(c) P₃:

r :- not s.
p :- not q, r.
q :- not p, not s.

(d) P₄:

r :- not s.
s :- not r.
p :- s, not p.

Verifique explicitamente os candidatos {r}, {s} e {p, s}. Qual é o papel da terceira regra?

(e) P₅:

a :- b.
b :- a.
c :- d.
d :- c.

{a, b, c, d} é modelo clássico de P₅. Porque é que não é estável?

(f) P₆:

r :- not s, not q.
s :- not r, not q.
q :- not r, not s.
t :- not t, not r.

Compare com o programa só com as três primeiras regras. O que faz a quarta?

Exercício 3 – Propriedades dos modelos estáveis

(a) Existe um programa em lógica normal cujos modelos estáveis sejam exactamente {a} e {a, b}? E {a}, {b} e {a, b}? Justifique com a propriedade dos modelos estáveis que está em causa, e prove-a: se X ⊂ Y são ambos estáveis, então Pʸ ⊆ Pˣ e portanto Y = Cn(Pʸ) ⊆ Cn(Pˣ) = X … (complete o argumento).

(b) Escreva um programa em lógica normal, sem regras de escolha e com no máximo seis regras, cujos modelos estáveis sejam exactamente {a, b} e {c, d}.

(c) Explique, com um exemplo de duas regras, porque é que a semântica dos modelos estáveis é não-monotónica: uma conclusão que se perde ao acrescentar um facto. Que relação tem isto com a hipótese do mundo fechado e com o problema da qualificação?

(d) Sejam P₁ e P₂ dois programas sobre os átomos {a, b}, nenhum deles com modelos estáveis. P₁ ∪ P₂ também não tem modelos estáveis? Prove ou dê um contra-exemplo.

(e) Qual é a diferença entre not p e ¬p? Dado o programa

ave(tweety).  ave(piu).  pinguim(tweety).
voa(X)     :- ave(X), not anormal(X).
anormal(X) :- pinguim(X).

qual é o modelo estável? O que aconteceria, em lógica clássica, com ∀x Ave(x) ⇒ Voa(x), Ave(tweety), Pinguim(tweety) e ∀x Pinguim(x) ⇒ ¬Voa(x)?

(f) Um programa positivo tem sempre exactamente um modelo estável. Porquê? E um programa normal, quantos pode ter? Dê um exemplo de cada caso (zero, um, vários) com no máximo duas regras.

Exercício 4 – Restrições de integridade

Considere o programa P, em que cada aluno escolhe um de dois ramos:

aluno(ana; rui).
curso(ia; redes).
ramo(X, ia)    :- aluno(X), not ramo(X, redes).
ramo(X, redes) :- aluno(X), not ramo(X, ia).

(a) Quantos modelos estáveis tem P? Indique-os (só os átomos ramo/2).

(b) Para cada uma das restrições seguintes, acrescentada sozinha a P, diga que modelos estáveis ficam e escreva, em português, o que a restrição exige:

:- ramo(ana, redes).
ok :- ramo(X, redes). :- not ok.
:- ramo(X, R1), ramo(Y, R2), R1 != R2.
:- ramo(X, R1), ramo(Y, R2), X != Y, R1 != R2.

Neste programa, iii e iv têm o mesmo efeito. Porquê? E se o gerador fosse { ramo(X, R) : curso(R) } :- aluno(X). (cada aluno em qualquer subconjunto dos ramos), quais seriam os modelos de P e que diferença haveria entre iii e iv?

(c) A restrição :- ramo(ana, redes). abrevia a regra f :- ramo(ana, redes), not f. com f um átomo novo. Verifique, pela redução, que com esta regra nenhum conjunto que contenha ramo(ana, redes) é modelo estável — nem com f, nem sem f. Porque é que f nunca aparece em nenhum modelo estável?

(d) Escreva, só com regras normais e restrições (sem regras de escolha nem agregados), a condição «todos os alunos estão em IA», usando a compilação do ∀ com duas negações (um átomo auxiliar falta e a restrição :- falta.). Depois escreva «existe um ramo em que estão todos os alunos» — compare com a alínea (b)(iii).

(e) Num enigma, quatro crianças fizeram cada uma um desenho com um de quatro instrumentos e apresentaram-nos por uma certa ordem. O programa começa por

crianca(anibal; beatriz; carla; daniel).
instr(marcador; pincel; lapis; caneta).
ordem(1..4).
1 { desenho(C, I, O) : instr(I), ordem(O) } 1 :- crianca(C).

e um aluno escreveu, para a pista «o Daniel mostrou o seu desenho em quarto lugar»:

ic1 :- not desenho(daniel, I, 4), instr(I).
:- not ic1.

O que é que estas regras exigem, de facto? Quantos modelos eliminam? Corrija-as. Escreva ainda a mesma pista como uma única restrição, sem átomo auxiliar. Que informação do programa é que usou para responder à primeira pergunta? O que exigiriam as regras do aluno se só houvesse um instrumento, instr(lapis).?

(f) Num programa sobre fardamentos, com pessoa/1, baixo/1 (as peças) e coloca(X, P) («a pessoa X usa a peça P»), explique por palavras o efeito das quatro regras seguintes e escreva a condição que impõem com os quantificadores ∃ e ∀ limitados aos domínios baixo e pessoa:

:- not r.
r       :- baixo(P), aux1(P).
aux1(P) :- baixo(P), not aux2(P).
aux2(P) :- pessoa(X), baixo(P), not coloca(X, P).

Exercício 5 – Variáveis, instanciação e contagens

(a) Para o programa

pessoa(pedro; ana; rui).
amigo(pedro, ana).  amigo(ana, rui).
contente(X) :- pessoa(X), amigo(X, Y).

indique o universo de Herbrand, a base de Herbrand (quantos átomos?), as instâncias da regra em ground(P) (quantas?) e o modelo estável. Quais das instâncias é que o instanciador (gringo) pode descartar logo, e porquê?

(b) Diga quais das regras seguintes são seguras. Para as que não são, explique o problema e corrija-as com um predicado de domínio.

inocente(X) :- not culpado(X).
maior(X, Y) :- numero(X), X > Y.
p(X) :- q(Y).
tem_amigo(X) :- amigo(X, _).
:- not pintado(R, C).
{ pintado(R, C) : cor(C) } = 1 :- regiao(R).

(c) Com atleta(1..3). e ordem(1..3)., quantos modelos estáveis tem cada um dos programas seguintes? Confirme no CLINGO e dê a fórmula geral para n atletas e n ordens.

1 { class(A, O) : ordem(O) } 1 :- atleta(A).
{ class(A, O) : ordem(O) } :- atleta(A).
1 { class(A, O) : ordem(O) } :- atleta(A).
1 { class(A, O) : ordem(O) } 1 :- atleta(A). 1 { class(A, O) : atleta(A) } 1 :- ordem(O).
o programa i com :- class(A1, O), class(A2, O), A1 != A2.

(d) Num enigma com 5 postos de vacinação, 5 pessoas e 5 vacinas, usaram-se os predicados postoP(X, P) e postoV(X, V). Seria boa ideia substituí-los por um único postoPV(X, P, V)? Compare o número de átomos da base de Herbrand, o número de alternativas de cada gerador e o número de instâncias de uma restrição que só fale de postos e pessoas, como :- postoP(5, ana). ou :- postoP(X, P), idade(P, I), I > 65, X < 3., nas duas versões.

(e) Uma regra com 4 variáveis sobre um domínio de 100 constantes tem quantas instâncias? Indique duas técnicas para controlar o tamanho de ground(P).

Exercício 6 – O torneio

Pretende-se organizar um torneio com 6 equipas (a, b, c, d, e, f) com uma fase de grupos (dois grupos de três equipas) e uma final entre os vencedores dos grupos. A pedido de certas equipas, pretende-se assegurar, na fase de grupos, o seguinte:

a equipa a não quer ficar no grupo 1;
as equipas a e e não querem ficar no mesmo grupo;
as equipas e e f não querem ficar no mesmo grupo;
as equipas b e c querem ficar no mesmo grupo.

Especifique uma codificação uniforme deste problema em ASP tal que os átomos do predicado in/2 em cada modelo estável correspondam à distribuição das equipas pelos grupos.

(a) Escreva os factos (equipas e grupos).

(b) Escreva um gerador para in/2 que ponha cada equipa em exactamente um grupo, de duas maneiras: só com regras normais (um par in/n_in e as restrições necessárias) e com uma regra de escolha com limites. Quantos modelos estáveis tem o programa até aqui?

(c) Acrescente «cada grupo tem três equipas», com #count ou com uma regra de escolha. Quantos modelos ficam? (Qual é o número combinatório correspondente?)

(d) Acrescente as restrições i a iv, uma de cada vez, e indique quantos modelos estáveis ficam em cada passo e qual é a distribuição final. Confirme no CLINGO com #show in/2..

(e) Alguém propõe acrescentar também :- in(E, G1), in(E, G2), G1 != G2. e tem_grupo(E) :- in(E, G). :- equipa(E), not tem_grupo(E). É necessário? Depende da versão do gerador de (b)?

(f) Se não houvesse a condição «três por grupo», quantos modelos estáveis teria o programa com as restrições i a iv? Que mudava no #count para «no máximo quatro por grupo»?

Exercício 7 – Quem chegou primeiro?

Quatro amigos — a Ana, o Bruno, a Carla e o Diogo — chegaram a um jantar um de cada vez, e cada um trouxe uma bebida diferente: água, cerveja, sumo ou vinho. Sabe-se que:

a Ana não chegou em último lugar;
a Ana chegou duas posições depois do Bruno;
o Diogo chegou antes da Carla;
quem trouxe a cerveja chegou antes de quem trouxe o sumo;
a Ana ou o Diogo trouxeram o sumo;
se o Bruno chegou em primeiro lugar, então o Diogo trouxe o vinho.

Considere o seguinte programa, que captura parte da informação:

pessoa(ana; bruno; carla; diogo).
bebida(agua; cerveja; sumo; vinho).
ordem(1..4).
1 { chegou(P, B, O) : bebida(B), ordem(O) } 1 :- pessoa(P).

(a) Quantos modelos estáveis tem este programa? Explique como obteve o valor.

(b) Para cada uma das restrições seguintes, diga se é necessário acrescentá-la ao programa, explicando porquê.

:- chegou(P1, B1, O), chegou(P2, B2, O), P1 != P2.
:- chegou(P, B1, O1), chegou(P, B2, O2), B1 != B2.
:- chegou(P1, B, O1), chegou(P2, B, O2), P1 != P2.
:- pessoa(P), bebida(B), ordem(O), not chegou(P, B, O).

Quantos modelos estáveis ficam depois de acrescentar as que são necessárias?

(c) Escreva as regras/restrições que capturam as pistas 1 a 6. Indique quantos modelos estáveis ficam depois de cada pista, e a solução.

(d) A pista 4 tem duas codificações naturais: uma restrição que proíbe a ordem errada e um par «ok :- … :- not ok.» que exige a ordem certa. Escreva as duas e diga se são equivalentes neste programa. E para a pista «quem trouxe o vinho chegou imediatamente depois de quem trouxe a cerveja» (que não é uma das pistas dadas), as codificações :- chegou(_, cerveja, O), not chegou(_, vinho, O+1). e ok :- chegou(_, cerveja, O), chegou(_, vinho, O+1). :- not ok. são equivalentes? E se a cerveja pudesse não ter sido trazida por ninguém?

Exercício 8 – Recursão e codificações uniformes

(a) Para o programa P com variáveis e cada um dos conjuntos de factos F₁ e F₂, use o CLINGO para encontrar os modelos estáveis e responda: quantas soluções há? Quantas há sem a restrição? Explique a diferença.

1 { cycle(X, Y) : edge(X, Y) } 1 :- node(X).
reach(Y) :- cycle(1, Y).
reach(Y) :- reach(X), cycle(X, Y), X != 1.
:- node(Y), not reach(Y).

F₁: node(1..3). edge(1,2). edge(2,3). edge(3,1). edge(3,2).

F₂: node(1..4). edge(1,2). edge(1,3). edge(2,3). edge(2,4). edge(3,2). edge(3,4). edge(4,1). edge(4,2).

Que problema resolve P? Porque é que a restrição também exige reach(1), e o que é que isso garante? A condição X != 1 na segunda regra de reach faz alguma diferença? (Tire-a e confirme.) Porque é que não é preciso dizer «a cada nó chega exactamente um arco»? Porque é que a alcançabilidade não se escreve com um número fixo de restrições sem recursão?

(b) Dada uma colecção de conjuntos, o problema Exact Hitting Set consiste em seleccionar exactamente um elemento de cada conjunto. Por exemplo, os conjuntos {a, b, c}, {a, c, d} e {b, c} têm dois exact hitting sets: {b, d} e {c}. Representamos esta instância pelos factos

set(1). element(1,a). element(1,b). element(1,c).
set(2). element(2,a). element(2,c). element(2,d).
set(3). element(3,b). element(3,c).

Especifique uma codificação uniforme em ASP tal que os átomos de select/1 em cada modelo estável correspondam a exact hitting sets, para instâncias arbitrárias — primeiro com #count, depois só com regras normais e restrições. Confirme que obtém {select(b), select(d)} e {select(c)}.

(c) Dado um grafo não dirigido, o problema Vertex Cover consiste em seleccionar um subconjunto dos vértices tal que cada arco contenha um vértice seleccionado e o número de vértices seleccionados não exceda um dado limiar. O grafo ({1, …, 6}, {{1,2}, {1,3}, {2,4}, {3,5}, {4,5}, {4,6}}) tem três vertex covers com no máximo três vértices: {1, 3, 4}, {1, 4, 5} e {2, 3, 4}. Instância:

vertex(1..6).
edge(1,2). edge(1,3). edge(2,4). edge(3,5). edge(4,5). edge(4,6).
threshold(3).

Especifique uma codificação uniforme tal que os átomos de select/1 correspondam aos vertex covers dentro do limiar. Como se pediria, em vez disso, um vertex cover de tamanho mínimo?

Exercício 9 – Verdadeiro ou falso

Indique se cada afirmação é verdadeira ou falsa e justifique numa frase.

Todo o modelo estável de um programa normal P é um modelo clássico de P.
Todo o modelo clássico mínimo de um programa normal P é um modelo estável de P.
Um programa positivo tem exactamente um modelo estável.
Um programa normal pode não ter modelos estáveis.
Se X e Y são modelos estáveis distintos do mesmo programa normal, então X ⊄ Y.
Se P tem um modelo estável X e se acrescenta a P um facto a, então X ∪ {a} é modelo estável do novo programa.
Se P₁ e P₂ não têm modelos estáveis, P₁ ∪ P₂ também não tem.
Acrescentar uma restrição de integridade a um programa nunca aumenta o número de modelos estáveis nem altera os que ficam.
Uma restrição de integridade :- a, not b. pode fazer com que b passe a ser verdadeiro nalgum modelo estável.
not a significa que a é falso no mundo.
Numa regra segura, toda a variável ocorre em algum literal positivo do corpo.
ground(P) tem sempre o mesmo número de regras que P.
O número de modelos estáveis de { p(X) : d(X) }. com n factos d/1 é 2ⁿ.
Decidir se um programa sem variáveis tem um modelo estável é NP-completo.
Em ASP, a alcançabilidade num grafo escreve-se com uma definição recursiva; em SAT ou num CSP, com um número fixo de restrições independente do grafo, não.
Se o CLINGO responde UNSATISFIABLE, o programa tem exactamente um modelo estável, o vazio.

Exercício 10 (extra) – De quem é o gato?

Para quem acabar antes do tempo. Existe uma rua com cinco casas, cada uma com uma cor diferente (vermelha, azul, branca, amarela e verde), habitadas por homens diferentes mas da mesma família (Miguel, João, Pedro, Marco e Carlos), adeptos de clubes diferentes (Académica, Benfica, Vitória de Setúbal, F. C. Porto e Sporting) e onde se bebe uma bebida diferente (sumo, chá, café, leite e água). Os cinco homens são casados com cinco mulheres (Maria, Carla, Paula, Cristina e Ana), sendo cada uma delas dona de um animal de estimação diferente (cão, raposa, tartaruga, cavalo e gato). Desta história sabe-se que:

O Miguel é filho do João.
O João é filho do Pedro.
O Marco é filho do Pedro.
O Carlos é filho do Marco.
O pai do Carlos vive na casa vermelha.
A mulher do Miguel é dona do cão.
O avô do Carlos vive na primeira casa à esquerda.
Na casa amarela é-se adepto do F. C. Porto.
O adepto da Académica vive na casa ao lado da dona da raposa.
O Pedro vive ao lado da casa azul.
A mulher do adepto do Sporting tem uma tartaruga.
O adepto do Benfica bebe sumo.
O pai do Miguel bebe chá.
O filho do Marco é adepto do Vitória de Setúbal.
É adepto do F. C. Porto o morador da casa ao lado da casa onde mora a mulher que é dona do cavalo.
Na casa verde bebe-se café.
A casa verde fica imediatamente à direita da casa branca.
Na casa do meio bebe-se leite.
O Pedro é casado com a Ana.
O Carlos não é casado com a Maria.

Sabe-se ainda que os homens e as mulheres desta história têm preferências em relação aos elementos do sexo oposto, dadas no ficheiro gato-factos.lp por factos pref(X, Y, N) — N é a posição de Y na lista de preferências de X, de 5 (a mais preferida) a 1 (a menos). Por exemplo, a mais preferida do Miguel é a Paula, seguida da Ana, da Maria e da Carla; a menos preferida é a Cristina. Todos os casamentos são estáveis: um casamento é instável se existe um homem e uma mulher, não casados um com o outro, que se preferem mutuamente aos seus cônjuges.

Um belo dia é encontrado o gato no meio da rua. Os serviços camarários pretendem saber quem é a dona do gato e em que casa é que ela mora. Resolva o problema em ASP: escreva um programa onde a informação disponível esteja codificada e cujo(s) modelo(s) estável(is) contenha(m) a solução. O ficheiro gato-factos.lp tem os factos (pessoas, clubes, animais, bebidas, cores, casas e preferências).

Não é recomendável modelar este problema com um predicado do tipo tuplo(T, U, V, W, X, Y, Z) significando que a casa número T é habitada pela personagem U, adepta do clube V, com o animal de estimação W, etc. Porquê?

Desafio

Agora é altura de resolver o 1.º Desafio, disponível aqui.