Homework #4 Solution

Part 1. In the graph below you see the possible flights between some of the cities in Turkey. Write the




predicate “route(X,Y) – a route between X and Y exists” that returns true of if there is a route between




any given two cities.







Istanbul Rize




Van




Edirne






Izmir
Ankara




Edremit
Isparta
Konya



Gaziantep

Erzincan Burdur Antalya




Your program should have all the facts and predicates/rules. See the following:




knowledge base



…




flight(istanbul,antalya). % the fact that Istanbul and Antalya has a flight.




…




rules



…




route(X,Y) :- flight(X,Y). % a predicate indicating there exist a route between % X and Y if there is flight between X and Y.




…




A single query to complete your program should check if there is a direct route between two given cities. Alternatively, it can list all the connected cities for a given city. See the following:




?- route(edirne,X).




X = erzincan ;




X = edremit ;




Make sure that your predicate implementation handles cycles properly avoiding infinite loops.




Part 2. Continuing with the previous problem, you are asked to write a program that checks if a route exists between two cities and if so, provides the shortest route.




In the first step, you are to expand the knowledge by adding distances for the direct flights. E.g.,




knowledge base



…




flight(istanbul, antalya). % the fact that Istanbul and Antalya has a flight. distance(istanbul, antalya, 481). % flight distance – calculated using




https://www.distancecalculator.net



complete all the flights and distances …



…




A single query to complete your program should check if there is a direct route between two given cities and the shortest distance between them. See the following example:




?- sroute(edremit,erzincan,X).




X=1044;







Part 3. You are given the following database about classes, classrooms and student enrollment.






Classes




Enrollment
















Class
Time
Room


Student


Class














102
10
z23


a


102














108
12
z11


a


108














341
14
z06


b


102














455
16
207


c


108














452
17
207


d


341






















e


455























Write the predicates “when(X,Y) – time of the course X is Y”, “where(X,Y) – place of the course X is Y”, and “enroll(X,Y) – student X is enrolled in course Y”. For example:




facts.. when(102,10).
3.1. Define/write a predicate “schedule(S,P,T)” that associates a student to a place and time of class.




See the example query and its result.




?- schedule(a,P,T).




P=102




T=10;







P=108




T=12;




3.2. Define/write another predicate “usage(P,T)” that gives the usage times of a classroom. See the example query and its result.




?- usage(207,T).




T=455;




T=456;




3.3. Define/write another predicate “conflict(X,Y)” that gives true if X and Y conflicts due to classroom or time.




3.4. Define/write another predicate “meet(X,Y)” that gives true if student X and student Y are present in the same classroom at the same time.




Part 4. Write the following predicates operating on sets.




4.1. Define a Prolog predicate “element(E,S)” that returns true if E is in S.




4.2. Define a Prolog predicate “union(S1,S2,S3)” that returns true if S3 is the union of S1 and S2.




4.3. Define a Prolog predicate “intersect(S1,S2,S3)” that returns true if S3 is the intersection of of S1 and S2.




4.3. Define a Prolog predicate “equivalent(S1,S2)” that returns true if S1 and S2 are equivalent sets.