Programming Languages Homework 5

Ed Smart
CSC 340
Homework 5

4.2 A tautology is a statement that is always true, no matter what the truth values of its components. Use a truth table to show that false → p is a tautology for any statement p.

false  |     p    |   false → p
F       |     T    |       T
F       |     F    |       T

4.3 A refutation system is a logical system that proves a statement by assuming it is false and deriving a contradiction. Show that Horn clause logic with resolution is a refutation system. (Hint: The empty clause is assumed to be false, so a goal ← a is equivalent to a → false. Show that this is equivalent to not(a).)

a    |   false   |    a → false   |    ¬a
T    |     F      |         F           |     F
F    |     F      |         T           |     T

4.4 Write the following statements in the first-order predicate calculus:

If it is raining or snowing, then there is precipitation.

precipitation => raining or snowing.

If it is freezing and there is precipitation, then it is snowing.

snowing => freezing and precipitation.

If it is not freezing and there is precipitation, then it is raining.

raining => not freezing and precipitation.

It is snowing.

snowing.

4.5 Write the statements in Exercise 4.4 as Prolog clauses, in the order given. What answer does Prolog give when given the query “Is it freezing?” The query “Is it raining?” Why? Can you rearrange the clauses so that Prolog can give better answers?

:- dynamic freezing/0, precipitation/0, snowing/0, raining/0.
precipitation :- raining.
precipitation :- snowing.
snowing :- freezing, precipitation.
raining :- \+ freezing, precipitation.
snowing.

When the queries are input, Prolog gives the following answers:

freezing. no.
raining. out of stack.

Prolog returns these incorrect answers because the fact that it is snowing is not added until the last line if the statements are added in the order given, while “precipitation :- raining.” is added before “precipitation :- snowing.” Due to this, Prolog is incapable of determining that it is snowing, which means “\+ freezing” is read as true, resulting in Prolog answering that it is not freezing, leading it to the conclusion that it is raining.

You can rearrange the first two clauses so that “precipitation :- snowing.” comes before “precipitation :- raining.” and move “snowing.” before the clauses “snowing :- freezing, precipitation.” and “raining :- \+ freezing, precipitation.” in order to obtain better answers.

4.7 Translate the definition of the gcd in Exercise 4.6 into Prolog. Compare its efficiency to Euclid’s gcd algorithm as given in Figure 4.1.

4.20 Rewrite the factorial Prolog program
 
fact(0, 1).
fact(N, R) :-
     N > 0, N1 is N – 1, fact(N1, R1), R is N * R1.

to make it tail recursive (see Exercise 4.17).

fact(0, 1).
fact(N, R) :-
    N > 0, N1 is N – 1, fact(N1, R1), !, R is N * R1.

Adding a cut before the last call prevents backtracking, which leads to a result that represents tail recursion.

4.31 The following is a possible implementation of a for loop construct in Prolog, similar to the statement for(I = L; I <= H;I++) in C:

    for(I, I, I) : – !.
    for(I, I, H) .
    for(I, L, H) :- L1 is L + 1, for(I, L1, H).

Using this definition, we can repeat operations over I, such as printing all integers between L and H as follows:

    printint(L, H) :- for(I, L, H), write(I), nl, fail.

Explain how backtracking causes the for predicate to behave like a loop.

4.38 Unification can be described as a substitution process that substitutes more specific values for variables so that equality of two expressions is achieved. For example, in Prolog the lists [1|Y] = [X] can be unified by substituting 1 for X and [] for Y. It is possible for different substitutions to cause equality. For instance, if [1|Y] is unified with X, one could set X = [1] and Y = [], or one could set X = [1|Y] and leave Y uninstantiated. This latter substitution is more general than the first because the additional substitution Y = [] transforms the first into the second. A substitution is a most general unifier of two expressions if it is more general than every other substitution that unifies the two expressions. Why does the unification algorithm of Prolog produce a most general unifier? Would it be useful for a logic programming language to have a unification algorithm that does not produce a most general unifier? Why?