Prolog Assignment: Rules for Family Relationships, List Manipulation, and Tree Traversal

The assignment content includes five problems related to Prolog programming language. The first problem is about a list single that has sub-lists L1 and L2 where all members in List 2 are in List 1. The second problem is about removing alternate elements from a list, starting with the second element. The third problem is about calculating the difference between two times described by the time structure. The fourth problem is about determining if a binary tree is balanced, and the fifth problem is about performing a left to right tree traversal.

Prolog
Assignment
Prolog
Student Name-
Student Number-
Submission Date-
1

Prolog
Table of Contents
Rule for question1 1
Rule for question 2 2
Rule for question 3 3
Rule for question 4 4
Rule for question 5 5
References 6
2

Prolog
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 de_nitions1:
_ First cousins are the children of two siblings. First cousins have
grandparents in common.
_ Second cousins are the children of _rst cousins. Second cousins
have great grandparents in common.
(a) [1 mark] Write the rule cousin1(Child1,Child2) that is true if
Child1 and Child2 are first cousins.
Rule
Cousin 1(Child 1 , Child2) :- grandparent ( Child1) , grandparent( Child 2)
3

Prolog
/* Child 1 and Child 2 will be first cousin if both have common grandparent*\
(b) [1 mark] Write the rule cousin2(Child1,Child2) that is true if
Child1 and Child2 are second cousins
Rule
Cousins 2( Child1 , Child 2) :- great grandparent( Cousin1), great grand parent( Cousin1)
\* Child 1 and Child 2 will be second cousins if they have same great grandparent*\
(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.
Rule
Sibling ( Child 1 , Child2) :- Parent ( Child 1) , Parent ( Child 2)
\* child 1 and child 2 are sibling if they have same parent )
Cousin 1(Child 1 , Child2) :- grandparent ( Child1) , grandparent( Child 2)
4

Prolog
/* Child 1 and Child 2 will be first cousin if both have common grandparent*\
Cousins 2( Child1 , Child 2) :- great grandparent( Cousin1), great grand parent( Cousin1)
\* Child 1 and Child 2 will be second cousins if they have same great grandparent*\
Similarly it is written-
cousin1(Child1,Child2) :- cousin(1,Child1,Child2)
*\ Child 1 and child 2 are first cousin if they have same grandparent *\
cousin2(Child1,Child2) :- cousin(2,Child1,Child2)
\* Child 1 and Child 2 will be second cousins if they have same great grandparent*\
In the same manner it can be formulated
Cousin 3( Child 1 , Child 2) :- cousin( 3 , Child 1, Child 2)
\* Child 1 and Child 2 will be second cousins if they have same great great grandparent*\
The analogy can be formulated in same manner.
2. [2 marks] 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].
5

Prolog
Rule
Predicate – Set ( in List , out List)
Single ( L1 ,L2) :- L2 ( in List ( L1))
\* A list single has sub-lists L1, L2 such that all members in List 2 are in List 1)
Sort Single ( L1, L2 ) :- sort ( L1 ) , unsort ( L2)
/* Sort only L1 in Single as L2 is already in Order*\
Set ( in list ( Single (L1 ,L2))) :- Set (in List ( L1) , set ( out List ( L2)
\* Take the values of sorted L1 and discard List L2 as all the elements of L2 are in L1 and now
L1 is in sorted form*\
Here
Single - ([a,a,b,2,1,a,2,3],L).
L = [b, 1, a, 2, 3]
So according to the above rule the output will be –
Single – [ a , a a , b, 1, 2 , 3]
3. [2 marks] Write the rule alt that removes alternate elements from
a list, starting with the second element. That is, the second, fourth,
sixth, etc. elements are removed. For instance:
?- alt([1,2,3,4,5,6,7],L).
L = [1, 3, 5, 7].
6

Prolog
?- alt([1,[2,3,4,5],6,7],L).
L = [1, 6].
Solution
Rule
drop [X|Xs ], X _ ] ) :- index of ([X|Xs], X , A)
Z is A mod Y ,
Z \= = 0.
\*According to this rule the list will drop the element from second position, then in next stage at
fourth , sixth and so on*\
4. [2 marks] 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 tdelta that computes the difference between two times,
reported in hours and minutes. The absolute value of the time difference is
computed (that is, time differences calculated are always
positive values).
tdelta(T1,T2,T3) if time T3 is equal to the absolute value of the
7

Prolog
difference between time T1 and time T2. For example:
?- tdelta(time(10,10),time(12,20),D).
D = time(2, 10).
?- tdelta(time(10,30),time(12,20),D).
D = time(1, 50).
?- tdelta(time(14,30),time(12,20),D).
D = time(2, 10).
Solution
Rule
Define time ( T) :- T[ hr , min]
\* the time for a structure is defined by giving the value of hours in first column and minutes in
second column*\
tdelta ( T1, T2) :-[T (diff ( T1, T2, T3 ) )]
where T3 :- [ T ( T1-T2) ]
*\ Tdelta defines the difference between any given time T1 and T2 where T3 stores the
difference between the T1 and T2*\
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) [1 mark] 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).
8

Prolog
X = 2.
?- size(node(1,[2,3,4]),X).
X = 2.
?- size(node(node(a,b),[2,3,4]),X).
X = 3.
Rule
[ binary tree ( node ( left , right ) )] :- [binary tree( left ) , binary tree( right)]
\* A binary tree with node having left and right node where there can be node or any item in the
tree*\
[Size (Tree , Size) ] :- [ Size ( node ( left , right ) , X]
\* It takes the input as tree and returns the size of node X*\
(b) [1 mark] Write the rule is Balanced(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 sub-tree is
at most one. (A tree which contains just one leaf is considered
balanced.)
For example:
?- isBalanced(1).
true.
9

Prolog
?- isBalanced(node(1,2)).
true.
?- isBalanced(node(1,node(1,node(1,2)))).
false.
Rule
[ diff ( tree) ] :- [ diff node ( left , right , X) ]
Where [ X] :- [ node (left ) –node (right)]
\* here diff defines the difference between the number of leaves in the left and right node*\
[ isBalanced ( tree) ]:- [ diff (node ( X)) _ 1 )]
*\ A tree is balanced if the difference between left and right node is at most 1 *]
(c) [1 mark] 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] .
Rule
10

Prolog
[ trav ( tree , L )] :- [ Trav(tree ( node ( left , right ) , L )]
Where[ L ] :- [ list node ( left, right)]
[ trav ( L ) ] :- [tree ( right , left ) ]
*\ the trav function tranverse the left node leaf to the right node tree *\
References
Conard Briski , ( 2011) , Land of prolog : learn to program in prolog, No starch press
David.S , (2011), Common Prolog: A gentle Introduction to symbolic computation, courier
publication
Robin.J, Clive .M, Ian.S , (2012) , The Art of prologProgramming, Springer Publication
Garry.D , (2017) , Interpreting prolog: Programming and data Structure , Apress publication
Geraduos .B , (2018) , Prolog Programming , Create Space Publication
11

Prolog
12