Exercícios de LP - Aulas Práticas

Resoluções Incorretas?

Caso encontres incorreções nas resoluções abaixo, por favor reporta-as para serem corrigidas.

Fichas Aulas Práticas

tip

Para além dos exercícios das aulas práticas, o livro de exercícios indicado abaixo tem uma coleção de exercícios bastante vasta. Se quiserem treinar e estar ainda melhor preparados, aconselho vivamente a que deem uma vista de olhos!

  • Semana 1: Lógica Proposicional II

  • Semana 2: Lógica Proposicional IIII

  • Semana 3: Lógica de Primeira Ordem II

  • Semana 4: Lógica de Primeira Ordem IIII

  • Semana 5: Programação em Lógica

  • Semana 6: Prolog - Conceitos Gerais/Árvores SLD em Prolog

  • Semana 7: Prolog - Listas II

    Resolução

    Exercício 1

    % nao_membro(X, L) - X não unifica com nenhum elemento de L
    
    % qualquer variável não é membro da lista vazia
    nao_membro(_, []).
    % caso X não unifique com Y e X não seja membro de R, X não é membro da lista
    % com primeiro elemento Y e resto R
    nao_membro(X,[Y | R]) :-
      X \= Y,
      nao_membro(X,R).
    % de notar que \= é equivalente a not(A = B), ou seja, não unificam

    Exercício 2

    % insere_ordenado(X, L1, L2) - L2 é o resultado de inserir, ordenadamente, X em L1
    
    %  introduzir um elemento numa lista vazia não requer ordenação
    insere_ordenado(X, [], [X]).
    % caso X seja menor que o primeiro elemento P de uma lista com resto R
    % X passará a ser o primeiro elemento dessa mesma lista
    insere_ordenado(X, [P|R], [X, P|R]) :- X < P.
    % caso X seja maior ou igual que o primeiro elemento P de uma lista com resto R
    % a lista passará a ser P|Res, onde tentaremos inserir, desta feita,
    % X na lista resto (R)
    insere_ordenado(X, [P|R], [P|Res]) :-
      X >= P,
      insere_ordenado(X, R, Res).

    Exercício 3

    % junta_novo_aleatorio(L1, L_Inf, L_Sup, L2)
    
    % começamos por criar um numero aleatorio entre LI e LS, N;
    % depois, verificamos se não é membro de L1 - se for, para e retorna false
    % caso contrário, insere-o ordenadamente em L1, sendo L2 o resultado
    junta_novo_aleatorio(L1, LI, LS, L2) :-
      random_between(LI, LS, N),
      nao_membro(N, L1),
      insere_ordenado(N, L1, L2).

    Exercício 4 (obrigado Tomás)

    
    % n_aleatorios(N, LI, LS, L) :- n_aleatorios(N, LI, LS, [], L).
    
    % condição de paragem
    n_aleatorios(0, _, _, []).
    
    n_aleatorios(N, LI, LS, L) :-
      N > 0,
      NewN is N - 1,
      n_aleatorios(NewN, LI, LS, AuxL),
      junta_novo_aleatorio(AuxL, LI, LS, L).

    Exercício 5

    
    % chave_euromilhoes(N, E)
    
    chave_euromilhoes(N, E) :-
      n_aleatorios(5, 1, 50, N),
      n_aleatorios(2, 1, 12, E).
    

    Exercício 6

    % comp_maior_lista(L, C)
    
    comp_maior_lista([P | R], C) :-
      length(P, Len),
      comp_maior_lista(R, Len, C).
    
    comp_maior_lista([],C,C).
    
    comp_maior_lista([P | R], Curr, C) :-
      length(P, Len),
      Len > Curr,
      comp_maior_lista(R, Len, C).
    
    comp_maior_lista([P | R], Curr, C) :-
      length(P, Len),
      Len =< Curr,
      comp_maior_lista(R, Curr, C).

    Exercício 7

    % duplica_elementos(L1, L2)
    
    % a) - RECURSIVO
    
    duplica_elementos([], []).
    
    duplica_elementos([P|R], [P, P | Aux]) :-
      duplica_elementos(R, Aux).
    
    % b) - ITERATIVO
    
    % desafio ao leitor pls no quiero mas ;-;
  • Semana 8: Prolog - Listas IIII

    Nota importante: Os exercícios desta secção devem ser realizados com predicados de ordem superior (sem recursão, portanto). A secção dos meta-predicados sobre listas poderá ser útil para este propósito.

    Resolução

    Exercício 1

    % insere_ordenado(E, L1, L2)
    
    insere_ordenado(E, L1, L2) :-
      findall(X, (member(X, L1), X < E), Menores),
      findall(X, (member(X, L1), X > E), Maiores),
      append(Menores, [E|Maiores], L2).

    Exercício 2

    % junta_novo_aleatorio(L1, LI, LS, L2)
    
    % o predicado subtract retira todas as instâncias de um ou mais elementos
    % da lista argumento - subtract(L1, L_E, L2); o(s) elementos(s) a verificar
    % têm de vir sob a forma de lista
    
    junta_novo_aleatorio(L1, LI, LS, L2) :-
      findall(X, between(LI, LS, X), Todas),
      subtract(Todas, L1, Possiveis),
      length(Possiveis, Len),
      random_between(1, Len, IndiceAleatorio),
      nth1(IndiceAleatorio, Possiveis, El),
      insere_ordenado(El, L1, L2).

    Exercício 3

    % repete_el(E, N, L)
    
    repete_el(E, N, L) :-
      % afirmar que L, desconhecida, tem comprimento N
      length(L, N),
      % o predicado fará com que todos os espaços vazios sejam "unificados" com E
      maplist(=(E), L).

    Exercício 4

    % duplica_elementos(L1, L2)
    
    duplica_elementos(L1, L2) :-
      findall([E, E], member(E, L1), AuxL),
      append(AuxL, L2).

    Exercício 5

    % num_occ(L, E, N)
    
    num_occ(L, E, N) :-
      findall(X, (member(X, L), E =:= X), AuxL),
      length(AuxL, N).

    Exercício 6

    % substitui_maiores(N, Sub, L1, L2)
    
    substitui_maiores_N(N, Subst, L1, L2) :-
      maplist(substitui_maiores_N_aux(N, Subst), L1, L2).
    substitui_maiores_N_aux(N, Subst, El, Subst) :-
      El > N.
    substitui_maiores_N_aux(N, _, El, El) :-
      El =< N.
  • Semana 9: Prolog - Aritmética, I/O

    • Aritmética
    Resolução

    Exercício 1

    (Tentem fazer primeiro vocês próprios e verifiquem as respostas no fim)

    a) X = 3+2.
    b) X = 5.
    c) true.
    d) false.
    e) Erro - argumentos não suficientemente instanciados.
    f) X = 3, Y = 8.
    g) false.
    h) true.

    Exercício 2

    % suc(N, M)
    
    suc(N, M) :-
      M is N + 1.
    
    % ant(N, M)
    
    ant(N, M) :-
      M is N - 1.

    Exercício 3

    % perimetro(R, P)
    
    perimetro(R, P) :-
      P is 2 * pi * R.

    Exercício 4

    % divisor(D, N)
    
    divisor(D, N) :-
      N mod D =:= 0.

    Exercício 5

    % aplica_op(Op, V1, V2, R)
    aplica_op(+, V1, V2, R) :-
      R is V1 + V2.
    
    aplica_op(-, V1, V2, R) :-
      R is V1 - V2.
    
    aplica_op(*, V1, V2, R) :-
      R is V1 * V2.
    
    aplica_op(/, V1, V2, R) :-
      R is V1 / V2.
    
    % Solução alternativa não hardcoded:
    aplica_op(Op, V1, V2, R) :-
      Lit =.. [Op, V1, V2],
      R is Lit.

    Exercício 6

    % soma_digitos_rec(N, S)
    
    soma_digitos_rec(0, 0).
    
    soma_digitos_rec(N, NewSum) :-
      AddedSum is N mod 10,
      NewN is N // 10,
      soma_digitos_rec(NewN, S),
      NewSum is S + AddedSum.
    
    % soma_digitos_it(N, S)
    
    soma_digitos_it(N, S) :-
      soma_digitos_it(N, S, 0).
    
    soma_digitos_it(0, Res, Res).
    
    soma_digitos_it(N, S, Ac) :-
      N > 0,
      NewAc is Ac + (N mod 10),
      NewN is N // 10,
      soma_digitos_it(NewN, S, NewAc).

    Exercício 7

    % inverte(N, I)
    
    inverte(0, 0).
    
    inverte(N, NewI) :-
      AuxI is N mod 10,
      NewN is N // 10,
      inverte(NewN, I),
      NewI is (I * 10) + AuxI.

    Exercício 8

    % triangular(N)
    
    triangular(N) :-
      triangular(1, 0, N).
    
    triangular(_, N, N) :-
      % verifica se o acumulador é igual a ele próprio (exceto zero)
      N \== 0,
      !.
    
    triangular(M, Ac, N) :-
      NewAc is Ac + M,
      NewAc =< N,
      NewM is M + 1,
      triangular(NewM, NewAc, N).
    • Instruções de Leitura e Escrita
    Resolução

    Exercício 1

    Objetivo Termo Introduzido Resposta
    read(X) f(a, b) X = f(a, b).
    read(a) f(a, b) false.
    read(f(X, Y)), R is Y mod X f(2, 8) X = 2, Y = 8, R = 0.
    X = 3, read(X + 1) 3 + 1 X = 3.
    X = 3, read(X + 1) 2 + 1 false.
    read(X + 3) +(9, 3) X = 9.

    Exercício 2

    Objetivo Escrito
    X = +(2,3), write(X) 2+3.
    X is +(2,3), write(X) 5.
    X = 3, write(X + 1) 3+1.
    X = 3, Y = X + 1, write(Y) 3+1.
    X = 3, Y is X + 1, write(Y) 4.
  • Semana 10: Prolog - Corte e Negação

    Resolução

    7.11.1

    a) Respostas ao objectivo p(X,Y)
    X=1, Y=a
    X=1, Y=b
    X=2,Y=a
    X=2,Y=b
    X=5, Y=z
    
    b) " " " mas com !
    X=1, Y=a
    X=1, Y=b
    X=2,Y=a
    X=2,Y=b
    
    c) " " " mas com ! depois do q(X)
    X=1, Y=a
    X=1, Y=b
    
    d) " " " mas com ! depois do r(Y)
    X=1, Y=a

    7.11.2

    a) Resposta ao objectivo p(X,Y)
    X=2,Y=3
    X=1, Y=1
    X=1, Y=3
    X=2,Y=1
    X=2,Y=3
    X=3,Y=1
    X=3,Y=3
    
    b)
    p1(2,3) :- !.
    
    c)
    q1(1) :- !.
    
    d)
    q1(1) :- !.
    (...)
    r1(1) :- !.
    
    e)
    q1(2) :- !.

    7.11.3

    classe(0, zero) :- !.
    classe(N, positivo) :- N > 0, !.
    classe(N, negativo) :- N < 0.

    7.13.4

    pertence(E, [P|_]) :- E == P.
    pertence(E, [_|R]) :- pertence(E, R).
    
    intersecao1(L1, L2, I) :- intersecao(L1, L2, [], I).
    intersecao([], _, Acu, Acu):-!.
    intersecao([P|R], L2, Acu, I) :-
        pertence(P, L2) -> append(Acu, [P], Novo_acu), intersecao(R, L2, Novo_acu, I)
        ; intersecao(R, L2, Acu, I).
    
    intersecao(_,[],[]):- !.
    intersecao(L1,[P|L2],I):-
        \+ member(P,L1),!,
    intersecao(L1,L2,I).
    intersecao(L1,[P|L2],[P|I]):-
        intersecao(L1,L2,I).
    
    intersecao2([], _, []) :- !.
    intersecao2(_, [], []) :- !.
    intersecao2([P | R], L, [P | IRL]) :-
        membro(P, L),
        !,
        intersecao(R, L, IRL).
    intersecao2([P | R], L, IRL) :-
        \+ membro(P, L),
        intersecao(R, L, IRL).

    7.13.5

    disjuntas([], _) :- !.
    disjuntas(_, []) :- !.
    disjuntas([El | _], L2) :-
        member(El, L2), !,
        fail.
    disjuntas([_ | L1], L2) :-
        disjuntas(L1, L2).
    
    %Usando a negação.
    disjuntas_n([],_):-!.
    disjuntas_n([P|L1], L2) :-
        \+member(P, L2),
        disjuntas_n(L1, L2).
    
    disjuntas2(L1,L2) :-
        \+ (member(E,L1),member(E,L2)).

    7.13.6

    a) false.
    b) [Objetivo: pessoa(P), \+temJust(P, _). ]
       P = jaime;
       P = joana.
  • Semana 11: Lógica Proposicional II - Tabelas de verdade

    Resolução

    2.3.1

    A afirmação A torna a afirmação incorreta. Temos que Δ\Delta, um conjunto de cláusulas, é satisfazível se houver uma interpretação que satisfaça todas as suas fbfs. Não precisamos que não satisfaça nenhuma em nenhum caso, apenas que, para qualquer interpretação, haja sempre uma fbf falsa segundo a mesma. Assim sendo, B é uma afirmação que faz sentido, visto que, de facto, α1α2α3\alpha_1 \wedge \alpha_2 \wedge \alpha_3 apenas precisa de uma falsa para ser toda falsa. Além disso, a afirmação C também faz sentido neste contexto, pois caso Δ\Delta seja satisfazível não podemos dizer que a negação de uma das suas fbfs é consequência semântica das outras.

    2.3.2

    (As resoluções em si estão marcadas como spoiler)

    a) Sempre Falsa

    Uma fbf tautológica é verdadeira para qualquer interpretação, o que vai diretamente contra a definição de fbf falsificável (falsa para pelo menos uma interpretação).

    b) Possivelmente Verdadeira

    Não é certo que toda a fbf satisfazível seja falsificável (nem vice-versa), mas é possível que aconteça.

    c) Sempre falsa

    Uma fbf contrária é falsa para qualquer interpretação, indo diretamente contra a definição de fbf satisfazível (verdadeira para pelo menos uma intepretação).

    d) Sempre Verdadeira

    Uma fbf tem de ser ou falsa ou verdadeira para uma dada interpretação, pelo que terá sempre de ser ou falsificável ou satisfazível.

    e) Possivelmente Verdadeira

    Pode acontecer ser tautológica ou contraditória, mas não tem de acontecer sempre.

    2.3.3

    Neste tipo de exercícios podemos optar por procurar modelos de Δ\Delta que não satisfaçam a fbf em causa.
    Aqui, querendo PRP \to R falsa (para ajudar na prova que não é consequência semântica) só temos um caminho por onde ir - I(P)=VI(P) = V e I(R)=FI(R) = F. Agora resta escolher uma interpretação para QQ tal que QRQ \to R seja verdadeira, pois assim a fbf de Δ\Delta seria verdadeira segundo esta interpretação mas PRP \to R não - para tal, escolhemos I(Q)=FI(Q) = F. Temos, portanto, que a interpretação I(P)=V,I(Q)=F,I(R)=FI(P) = V, I(Q) = F, I(R) = F é um modelo de Δ\Delta que não satisfaz PRP \to R, e PRP \to R não é, portanto, consequência semântica de Δ\Delta.

    2.3.4

    a)

    Interpretação PP QQ ¬P\neg P ¬PQ\neg P \to Q ¬Q\neg Q
    I1I_1 V V F V F
    I2I_2 V F F V V
    I3I_3 F V V V F
    I4I_4 F F V F V

    Esta fbf só tem, portanto, um modelo (I2I_2), para o qual a única fbf atómica que é sua consequência semântica é PP (é a fbf atómica verdadeira segundo esta interpretação).

    b)

    Interpretação PP QQ RR (PQ)R(P \wedge Q) \to R ¬R\neg R
    I1I_1 V V V V F
    I2I_2 V V F F V
    I3I_3 V F V V F
    I4I_4 V F F V V
    I5I_5 F V V V F
    I6I_6 F V F V V
    I7I_7 F F V V F
    I8I_8 F F F V V

    Esta fbf tem, portanto, apenas um modelo, I4I_4 (interpretação para a qual ambas as fbfs do conjunto são verdadeiras). A partir desse modelo, podemos aferir que apenas PP é uma fbf atómica que é consequência semântica do conjunto.

    c)

    Interpretação PP QQ RR PRP \to R QRQ \to R PQP \vee Q
    I1I_1 V V V V V V
    I2I_2 V V F F F V
    I3I_3 V F V V V V
    I4I_4 V F F F V V
    I5I_5 F V V V V V
    I6I_6 F V F V F V
    I7I_7 F F V V V F
    I8I_8 F F F V V F

    Esta fbf tem, portanto, 3 modelos: I1,I3,I5I_1, I_3, I_5, interpretações para as quais as 3 fbfs do conjunto são verdadeiras. Podemos, a partir delas, aferir que apenas RR é uma fbf atómica consequência semântica do conjunto, visto que é a única que se mantém constantemente verdadeira segundo os 3 modelos.

    2.3.5

    PP QQ RR (PQ)R(P \wedge Q) \to R PRP \to R QRQ \to R ((PQ)R)((PR)(QR))((P \wedge Q) \to R) \to ((P \to R) \vee (Q \to R))
    V V V V V V V
    V V F F F F V
    V F V V V V V
    V F F V F V V
    F V V V V V V
    F V F V V V V
    F F V V V V V
    F F F V V V V

    A fbf é verdadeira segundo qualquer interpretação, pelo que podemos afirmar que esta é tautológica.

    2.3.6

    Interpretação PP QQ RR PRP \to R QRQ \to R PQP \vee Q (PQ)R(P \vee Q) \to R
    I1I_1 V V V V V V V
    I2I_2 V V F F
    I3I_3 V F V V V V V
    I4I_4 V F F F
    I5I_5 F V V V V V V
    I6I_6 F V F V F
    I7I_7 F F V V V F V
    I8I_8 F F F V V F V

    (De notar que só foram marcados os espaços necessários, os outros não foram necessários porque é possível chegar à conclusão que a interpretação em questão não será modelo do conjunto, visto que uma das suas fbfs já foi aferida como falsa segundo essa interpretação)

    Podemos notar que, para todos os modelos do conjunto, (PQ)R(P \vee Q) \to R é verdadeira, pelo que é consequência semântica do conjunto.

    2.3.7

    Se Δ\Delta não for satisfazível, não tem modelos, pelo que não há nenhum modelo de Δ\Delta que não satisfaça α\alpha.

  • Semana 12: Lógica Proposicional IIII - OBDDs

  • Semana 13: Lógica Proposicional IIII - Algoritmos de SAT