Write Prolog rules as described in the questions below. You may use any Prolog builtin predicates. You may need to write auxiliary "helper" rules in some cases.

Your code may be tested by an automated script, so be sure to do as follows:

• Place all definitions in a single file that can be read without error by a Prolog interpreter.
If you add comment lines, prefix them with a % (prolog comment symbol)

• Submit just this text file electronically as directed on the course Study Desk page.
(Do not submit a word processed or PDF file.)

• Use the rule name and arguments exactly as specified.

• Do NOT submit your test facts. Do not submit (say) a set of parent facts that you used to test your work.

Questions

1. Assume the Prolog knowledge base contains a set of facts:

parent(parent,child) describes biological parent-child relationships. Assume that the Prolog knowledge base describes only families where all siblings share the same two parents. You are required to write rules that describe the cousin relationship. Consider the following definitions.

• First cousins are the children of two siblings. First cousins have grandparents in
common.

• Second cousins are the children of first cousins. Second cousins have great grandparents
in common.

(a)  Write the rule cousin1(Child1,Child2) that is true if Child1 and Child2 are first cousins.

(b) [1 mark] Write the rule cousin2(Child1,Child2) that is true if Child1 and Child2 are second cousins.

(c) [1 mark] Write the general rule cousin(N,Child1,Child2) that is true if Child1 and Child2 are Nth cousins. So

cousin1(Child1,Child2) ≡ cousin(1,Child1,Child2) and
cousin2(Child1,Child2) ≡ cousin(2,Child1,Child2) and so on for third and fourth
and even higher level cousins.
Hint: start by writing a sibling(Child1,Child2) rule.

2.  Write the rule single that removes duplicate entries from a list. single(L1,L2) if every value in L2 is in L1 and every value in L1 is in L2 and there is at most one occurrence of any value in L2. The order of values in L1 is unsorted, and no ordering of values in L2 is required.
?- single([a,a,b,2,1,a,2,3],L).
L = [b, 1, a, 2, 3].

3. Write the tr rule to translate all occurrences of a list element value to another
value.
tr(A,B,L,M) if list M is the same as list L, except that every occurrence of A in L is replaced
by B. For instance:
?- tr(1,2,[1,4,1,5],L).
L = [2, 4, 2, 5].

4. A time, in hours and minutes, is described by the time structure. For example, 9 hours and 33 minutes would be encoded as time(9,33).
Write the rule tgreater that compares two times. tgreater(T1,T2) if time T1 is a bigger value (is later than) time T2. For example:
?- tgreater(time(9,33), time(10,42)).
false.
?- tgreater(time(11,33), time(10,42)).
true.
?- tgreater(time(11,33), time(11,33)).
false.

5. A binary tree is defined by the structure node(left,right), where left and right can be either another node or any Prolog data item.

(a) Write the rule size(Tree,Size) that takes as input a tree and returns the number of leaf items in the tree. For example:
?- size(node(1,2),X).
X = 2.
?- size(node(1,[2,3,4]),X).
X = 2.
?- size(node(node(a,b),[2,3,4]),X).
X = 3.

(b) Write the rule isBalanced(Tree) that determines if the tree is balanced. A binary tree is balanced if, at every node, the difference between the number of leaves appearing in the left and right subtree is at most one. (A tree which contains just one leaf is considered balanced.)
For example:
?- isBalanced(1).
true.
?- isBalanced(node(1,2)).
true.
?- isBalanced(node(1,node(1,node(1,2)))).
false.

(c) Write the rule trav(Tree,List) that performs a left to right tree traversal; List is the list of leaf node values in the tree.
For example:
?- trav(x,L).
L = [x].
?- trav(node(1,node(2,node(a,b))),L).
L = [1, 2, a, b] .