Logic programming lecture assignments

  1. [Exercises 11.3–11.5, p.28] (02 Sept 2016, deadline 09 Sept)

    1. Referring to the example in the Theme, how many ways are there of associating the constants with the given domain? How many ways are there of choosing the relation associated with 'likes' over the domain? How many possible interpretations are there altogether over the domain?

    2. For each of the sentences below, find an interpretation which makes it true:

      (i) (∀X)likes(chris,X)
      (ii) (∃X)likes(X,chris) if (∀X)likes(X,X)
      (iii) ¬(∃X)likes(X,X)

    3. For each of the sentences below, find an interpretation which makes it false:

      (i) (∀X)(even(X) or odd(X))
      (ii) ¬(∃X)(even(X) & odd(X))
      (iii) ¬(∃X)(0=s(X))
      (iv) (∀X)(even(X) if odd(s(X)))
      (v) (∀X)(even(X) iff ¬even(X))

  2. [Exercises 15.1–15.3, p.40] (09 Sept, deadline 16 Sept)

    1. Classify the following clauses according to whether they are definite, indefinite or negative:

      (i) definite(X) or indefinite(X) or negative(X) or ¬clause(X)
      (ii) ¬happy(chris) or ¬unhappy(chris)
      (iii) happy(chris) or ¬happy(chris) or indifferent(chris)
      (iv) ¬perfect(X)
      (v) likes(X,Y) or ¬friends(X,Y)

    2. Classify the same clauses above according to whether they are Horn or non-Horn.

    3. Classify the same clauses above according to whether they are rules, facts or queries.

  3. [Exercises 16.1–2, p.44; 17.1, p.48] (16 Sept, deadline 23 Sept)

    1. Rewrite each of the following clauses as a sentence in conditional format:

      (i) vertebrate(X) or invertebrate(X)
      (ii) omniscient(god)
      (iii) ¬True

    2. Rewrite each of the following sentences as a clause in standard (disjunctive) format:

      (i) I've_seen(X) if I've_seen(Y) & elephant(Y) & flies(Y)
      (ii) will_be_saved(X) or ¬repents(X) if True

    3. Express each of the statements in unrestricted first-order logic. Convert the answers into a set of clauses.

      (i) If X is a parent and X is a female then X is someone's mother.
      (ii) If X is a father or X is a mother then someone is someone's parent.
      (iii) If everyone is a parent then somebody is a child.

  4. [Exercises 23.1–3, p.66] (23 Sept, deadline 30 Sept)

    1. Give an indication of the Herbrand domain when the language has

      (i) two constants 'a' and 'b' and two 1-ary function symbols 'f' and 'g';
      (ii) one constant 'a' and one 2-ary function symbol 't';
      (iii) no constants but one 1-ary function symbol 'f'.

    2. Using modus ponens, prove the proposition int(s(s(0))) from the 'int' program and identify the ground terms involved in the proof.

    3. For the same 'int' program, suggest an interpretation of it based upon the domain of all strings whose members belong to {a,b}.

  5. [Exercises 24.1–2, p.69] (30 Sept, deadline 07 Oct)

    1. Give an indication of G(P) for this clause-set P:
           last(f(U,nil),U)
           last(f(U,Z),V) if last(Z,V)
           
      assuming that the language has just two constants 'nil' and 'a', and just one 2-ary function symbol 'f'.

    2. Taking G(P) from the exercise above, construct a proof, using modus ponens only, of the proposition
           last(f(a,f(a,nil)),a) 
           
  6. [Exercises 26.2 and 26.4, p.75] (07 Oct, deadline 14 Oct)

    1. Use resolution to establish the validity of the sentence ((A if B) if A).

    2. Show that resolution is not affirmation-complete by virtue of the logical implication {A,B} ⊨ A if B.

      Note—an inference system is affirmation-complete if it can derive Q from P whenever Q is implied by P.

  7. [Exercises 27.1–4, p.78] (14 Oct, deadline 21 Oct)

    1. Determine, in each case, the result of applying the given set of replacements to the given formula:

      (i) apply {X/mum(Y), Y/chris} to likes(X,dad(Y))
      (ii) apply {X/mum(chris), Y/chris} to likes(X,dad(Y))
      (iii) apply {X/t(U,U), Y/U} to tree(t(X,t(Y,Y)))
      (iv) apply {X/elizabeth} to (∃X)wife(X,Y) if man(Y) & married(Y,X)

    2. Comment upon the legality of the following as substitutions:

      (i) {X/mum(Y), Y/chris}
      (ii) {X/X}
      (iii) ø
      (iv) {X/2, X/3}
      (v) {X/2, X/2}
      (vi) {X/Y, Y/X}
      (vii) {X/2, Y/2, Y/X}
      (viii) {f(X)/f(Y)}

    3. Given the set of replacements
      σ = {X/f(a,Y), Y/f(b,Z), Z/c}
      determine the least value of n>0 for which σn is idempotent.

    4. Evaluate the composition σ* = σ1 ∘ σ2 where
      σ1 = {X/f(a,Y), W/f(U,Z)}
      σ2= {X/f(a,a), Y/b, V/c}
      and confirm that Wσ* = (Wσ1)σ2 when W = p(V,X,Y,W).

  8. [Exercises 28.5 p.82 and 29.1, p.86] (21 Oct, deadline 28 Oct)

    1. Convert to clausal form the sentences
      path(X,Y) iff (go(Y) if go(X))
      go(c) if go(b)
      go(b) if go(a)
      Use resolution to refute ¬path(a,c).

    2. The following query is posed to the 'append' program
          C1: append(nil,W,W)
          C2: append(U•X,Y,U•Z) if append(X,Y,Z)
          Q: ? append(a•X•nil,Y•nil,Z)
          
      (i) rewrite Q in standard clause notation, showing all the relevant quantifiers;
      (ii) sketch a resolution graph which solves Q;
      (iii) say what answer you think should be computed for Q.

  9. [Exercises 30.1 p.89 and 31.2, p.93] (28 Oct, deadline 04 Nov, extended 11 Nov)

    1. For each of the following queries Q posed to the 'append' program, say whether the search tree generated from Q is finite and successful, or infinite and successful, or finitely failed or infinitely failed.

      (i) ? append(a•X•nil,Y•nil,Z)
      (ii) ? append(a•X,Y,Z)
      (iii) ? append(a•X,Y,b•Z)
      (iv) ? append(X,a•Y,b•Z)
      (v) ? append(X,nil,X•nil)
      (vi) ? append(X,a•b•nil,Z) & append(a•b•nil,X,Z)
      (vii) ? append(a•X,Y,Z) & append(Z,V,b•W)

      Note—there is a trap in part (v).

    2. The following program can be used to compute certain lists containing alternating ones and zeros:
          one-and-zero(X) if ones(X) & zeros(X)
          
          ones(nil)
          ones(1•U•Y) if ones(Y)
          
          zeros(nil)
          zeros(U•0•Y) if zeros(Y)
          
      (i) Show the SLD-tree for the query ?one-and-zero(1•0•1•0•nil) under the computation rule which selects the lefmost literal. Would the computation rule which selects the rightmost literal be more efficient for the same query?

      (ii) Which of those two computation rules is least efficient for executing the query ?one-and-zero(1•2•1•0•nil), and why?

      (iii) If the interpreter can easily access and compare the lengths of arguments in calls, what new computation rule can you suggest which deals satisfactorily with both the above queries?

  10. [Exercise 33.2, p.101] (04 Nov, deadline 18 Nov)

    1. For each of the following pairs of atoms, determine whether or not they can be unified; if they can, state both (the idempotent form of) their m.g.u. and, if possible, some less-general unifier for them:

      (i) p(a,X) and p(Y,b)
      (ii) p(X,X) and p(Y,Z)
      (iii) p(X,Y) and p(Y,X)
      (iv) p(t(X,t(X,b))) and p(t(a,Z))
      (v) p(t(X,t(X,b))) and p(t(a,t(Z,Z)))
      (vi) p(X,f(Y)) and p(f(Y),X)
      (vii) p(X,f(X)) and p(f(Z),f(Z))

  11. [Exercises 34.2 p.103 and 38.1, p.121] (18 Nov, deadline 25 Nov)

    1. A difference-list is a term of the form diff(e1•...•en•X,X) where X is a variable and n≥0, and is viewed as an abstract representation of the concrete list e1•...•en•nil. The term diff(a•b•X,X), for instance, represents the list a•b•nil.

      An element can be appended to the end of a list in a single step provided that the given list is represented by a difference-list. In particular, the following query

              ? put_on_end(c,diff(a•b•X,X),L)
          
      can be solved to give the output binding L/a•b•c•nil by invoking a single assertion of the form
              A: put_on_end(U,?,L)
          
      What do you suggest the assertion's second argument should be in order to produce this outcome? Investigate whether your suggested assertion also correctly solves the queries
                 Q1: ? put_on_end(c,diff(X,X),Y)
            and  Q2: ? put_on_end(X,diff(X,X),Y)
          
      when the occur-check is in force. What happens when it is not?

    2. The interchange-sort program below is suitable for executing standard queries of the form ?-sort(list,Y) where list denotes any ground list:
          S1: sort(Y,Y) if ord(Y)
          S2: sort(X,Y) if append3(X1,U•V•nil,X2,X) & V<U & 
                           append3(X1,V•U•nil,X2,Z) &
                           sort(Z,Y)
          
      It works by repeatedly seeking disordered pairs of adjacent elements of the current list and correcting them. Here, ord(Y) means that Y is a list of numbers arranged in strictly ascending order, whilst append3(L1,L2,L3,L) means that L is the result of appending L3 to the result of appending L2 to L1. Assume that 'ord', 'append3' and '<' are defined correctly by further clauses supplementing S1 and S2. The intended meaning of sort(X,Y) is that Y is some permutation of X for which ord(Y) holds.

      Comment upon the efficiency of this program for executing the standard query ?sort(3•1•4•2•nil,Y) under the standard strategy.

      For the same query comment upon the correctness and efficiency of each of the three following adaptations of the above program:

      (i) a cut inserted before the call V<U;
      (ii) the cut inserted instead immediately after the call V<U;
      (iii) as in (ii) but with S1 deleted and a new clause

             S3: sort(Y,Y)
          
      placed after the clause S2.

      Are there any standard queries which adaption (iii) would solve incorrectly relative to the intended meaning?

  12. [Exercises 40.1–3 and 5–8, p.130–131] (25 Nov, deadline 02 Dec)

    Note—in Questions 2–4 assume that P is definite.

    1. If B(P) has n members, how many H-interpretations does P have?
    2. Which subset of B(P) is always an H-model for P?
    3. What form must P take in order that ø shall be an H-model?
    4. What form must P take in order that every subset of B(P) shall be an H-model?
    5. Assuming that H={A,B,C,D}, identify all the H-models of the following clause-set:
      A if ¬B & C
      D if ¬C
      ¬D
    6. Identify the smallest H-model for the program
      list(nil)
      list(a•X) if list(X)
    7. Taking H to be {1,2}, identify all the H-interpretations for the clause
      p(X) if ¬p(Y)
      and say which, if any, are H-models for the clause.

  13. [Exercises 48.1–3, p.157] (02 Dec, deadline 09 Dec)

    1. Use partial evaluation to obtain a specialized append program for queries of the form ?append(U•nil,Y,Z) starting with the program
      append(nil,Z,Z)
      append(U•X,Y,U•Z) if append(X,Y,Z)
    2. Use partial evaluation to obtain a specialized append program for queries of the form ?append(X,Y,X) starting with the same program as above. Construct an argument to show that your result could be specialized further to just the clause
      append(X,nil,X)
      provided that X is a list.

    3. Given the program
      num(0)
      num(s(U)) if num(U)
      twice(0,0)
      twice(s(U),s(s(Z))) if twice(U,Z)
      even(Y) if num(X) & twice(X,Y)
      use partial evaluation to derive the clause
      even(s(s(Z))) if num(U) & twice(U,Z)
  14. [Exercises 49.1–3, p.162] (09 Dec, deadline 16 Dec)

    1. (i) Starting with the program
      even(0)
      odd(s(0))
      even(s(X)) if odd(X)
      odd(s(X)) if even(X)
      use unfolding to show that this is computationally equivalent to the program
      even(0)
      even(s(s(0)))
      even(s(s(X))) if even(X)
      odd(s(0))
      odd(s(s(X))) if odd(X)

      (ii) By partially evaluating the query ?even(X) show that the second clause of this new program is redundant.

    2. (i) Unfold 'one-and-zero' through two steps using the program
      one-and-zero(X) if ones(X) & zeros(X)
      ones(nil)
      ones(1•V•Y) if ones(Y)
      zeros(nil)
      zeros(U•0•Y) if zeros(Y)

      (ii) Hence construct an argument to show that, for querying the predicate 'one-and-zero', this program is computationally equivalent to the program

      one-and-zero(nil)
      one-and-zero(1•0•Y) if one-and-zero(Y)
    3. Figure 49.2 in the Theme shows how the SLD tree becomes simplified after a complete one-step unfolding. What would the tree look like after a complete two-step unfolding?

  15. [Exercises 50.1–2, pp.165–166] (16 Dec, deadline 23 Dec)

    1. Construct CWA(P) for each of the following clause-sets P and say whether or not it is consistent.

      Note—assume in each case that H={dov,chris}.

      (i) likes(chris,X) if likes(dov,X)

      (ii) likes(chris,X) if ¬likes(X,chris)

      (iii) likes(dov,X) or likes(X,chris)

      (iv)

      likes(dov,X)
      likes(X,chris)
      (v)
      ¬likes(dov,dov)
      likes(X,dov) if likes(chris,X)
      likes(chris,X)

    2. Assume that H={chris,dov}. If we then have, for definite P,
      CWA(P) = P ∪ {¬likes(chris,dov),¬likes(chris,chris)}
      identify the simplest possible P which consists of

      (i) two clauses;
      (ii) one clause.