1.(b) Prog 1: yes; Prog 2: loop; Prog 3: loop
  (c) The search procedure would be complete if it succeeds
      whenever the query is a logical consequence of the program.
      Prolog proof search is incomplete because this does not happen.
      In the examples, Prog 1 does not illustrate incompleteness because
      it succeeds. Prog 2 does not illustrate incompleteness because
      the query is not a logical consequence of the program. (This can
      be shown using truth tables.) Prog 3 does illustrate incompleteness.
      The query is a logical consequence, but Prolog proof search does not
      find it.
  (d) A decision procedure is an algorithm that returns "yes" in the case
      of a logical consequence, and returns "no" otherwise. It never loops.
      The propositional Prolog proof search can be modified by
      backtracking whenever a goal in the search tree is reached
      with the same head atom as a previous goal in the search tree.
      The search returns "no" if the search is completed without
      finding a leaf consisting of the empty list of goals.

2.(a) The underscore needs to be give a variable name.
  (b) S_1 is a model, S_2 is not (the first clause of the program fails),
      S_3 is a model.
  (c) i. False in all three structures. Not a logical consequence.
      ii. True in S_1 and S_3. False in S_2. A logical consequence.
         (It is a consequence of the first clause alone._
      iii. False in S_1 and S_2. True in S_3. Not a logical consequence.
      1v. True in S_1, S_2 and S_3. Nonetheless not a logical consequence.
         A countermodel is to modify structure S_1 by taking the
         interpretation of lessthan to be the less-than-or-equal-to
         relation.

3.(b) p is a logical consequence in both cases. This is easily verified
      by truth tables.
  (c) Two issues are:
      * As illustrated by Program 1, p can be a logical consequence even
        when p does not appear either as a fact or on the right-hand-side
        of a rule in a program.
      * As illustrated by Program 2, even when p appears as the
        right-hand-side of an implication, it can be a logical consequence
        without any of the formulas on the left-hand-side of the implication
        being provable (since not logical consequences themselves)