CS3342 Organization of Programming Languages - Assignment 4: Prolog
CS3342 – Assignment 4
1. (50pt) Consider the following Prolog facts and rules:
member(H, [H|_]).
member(H, [_|T]) :- member(H, T).
unique(H, [H|T]) :- not(member(H, T)).
unique(H, [_|T]).
Draw the Prolog tree corresponding to each of the following queries, explaining the effect of each cut:
-
(a) (15pt)
?- member(a, [a,b,a]). true ; true ; false. -
(b) (17pt)
?- unique(a, [b,a,c]). true ; false. -
(c) (18pt)
?- unique(a, [a,b,a]). false.
2. (50pt) Knights and Knaves puzzles: You are on an island where every inhabitant is either a knight or a knave. Knights always tell the truth, and knaves always lie. Implement the following puzzles in a Prolog program, kk.pl, which finds the correct answer(s); the program behaves as indicated below:
-
(a) Puzzle 1: You are approached by two people. The first one says: “We are both knaves”. What are they actually?
puzzle_1 :- ....?- puzzle_1. [a=Knave,b=Knight] false. -
(b) Puzzle 2: You are approached by two people. The first one says: ”At least one of us is a knave”. What are they actually?
puzzle_2 :- .... ?- puzzle_2. [a=Knight,b=Knave] false.
1
Notes:
(c) Puzzle 3: You are approached by two people. The first one says: ”Either I am a knave or B is a knight.”. What are they actually?
puzzle_3 :- ....
?- puzzle_3.
[a=Knight,b=Knight]
false.
(d) Puzzle 4: You are approached by two people. The first one says: ”We are the same”. Is the other person a knight or a knave?
puzzle_4 :- ....
?- puzzle_4.
[a=Knave,b=Knight]
[a=Knight,b=Knight]
false.
!!! Submit two files: one pdf file with responses to Assignment 4 Q1 and one source code file, kk.pl, with code as required above to Assignment 4 Q2 (code); anything else receives 0pt. Solutions should be typed but high-quality hand-written solutions are acceptable.
Tools: You are allowed to use web resources, such as JFLAP, LLMs (e.g., ChatGPT), online Lambda calculators, etc., to help you solve the assignments. You still need to explain clearly your solution. Also, make sure you understand the answers as these tools will not be available during exams!
LATEX: For those interested, the best program for scientific writing is LATEX. It is far superior to all the other programs, it is free, and you can start using it in minutes; here is an introduction: https://tobi.oetiker.ch/lshort/lshort.pdf. It is also available online at https://www.overleaf.com/.
2
