CS3342 – Assignment 4
due Apr. 7, 2021; latest to submit: Apr. 9, 2021
Note: The two-day extension (with no penalty) already achieves the effect of an SRA. SRAs cannot be used to extend the deadline past Apr. 9.
1. (50pt) Consider the following set of rules:
append([], Y, Y).
append([H|X], Y, [H|Z]) :- append(X, Y, Z).
prefix(P, L) :- append(P, _, L).
suffix(S, L) :- append(_, S, L).
sublist(S,L) :- suffix(L1,L), prefix(S,L1).
(1) (10pt) Translate the set of rules into clausal form. The variables in different rules are unrelated so they should be different. (I changed the slides 15-19 in Predicate Calculus to reflect this.)
(2) (20pt) Show how resolution enables Prolog to obtain the following answer:
?- sublist([b,c],[a,b,c]).
true.
You don’t have to work with all clauses simultaneously. Pick only the two clauses to which you are applying resolution, indicate the terms that unify, the substitution (most general unifier) used, and the result. Note that you may have to use the same rule more than once.
(3) (20pt) Draw the search tree (include the rule used and the substitution) that shows the fol- lowing computation (the names of the variables can be different):
?- sublist([a],L).
L = [a|_932] ;
L = [_1570, a|_1584] ;
L = [_1570, _2222, a|_2236].
2. (50pt) Write a Prolog program multiset.pl, that implements multisets using lists. Multisets are mathematical objects similar with sets but allowing multiple occurrences of the same element. Rather than giving formal mathematical definitions for the operations on multisets, we give exam- ples to illustrate them. Consider two multisets:
A = {a,a,b,b,b,c,d,d},B = {b,b,c,c,c,d,d,e} . The operations of union, intersection, sum, and difference are:
A ∪ B = {a, a, b, b, b, c, c, c, d, d, e}
A ∩ B = {b, b, c, d, d}
A + B = {a, a, b, b, b, b, b, c, c, c, c, d, d, d, d, e}
A − B = {a, a, b} (elements with higher counts in A, difference of counts)
Also, inclusion is defined as: A ⊆ B iff all elements of A appear in B with equal or higher counts; here are some examples:
{a,b,b,d} ⊆ {a,b,b,c,c,d,d} {a,b,b,b,d} ̸⊆ {a,b,b,c,c,d,d} {b,d,e} ̸⊆ {a,b,b,c,c,d,d}
1
(all elements, maximum count) (common elements, minimum count) (all elements, sum of counts)
READ ME!
You are required to implement multisets as lists with the following predicates for the operations above, in the same order: union, intersection, sum, difference, inclusion.
The examples above have the multisets sorted for clarity. Your program should handle correctly multisets that are not necessarily sorted. The order of elements in your answers is not important. Only the first answer is considered; that is, the user is not asking for more solutions.
(When testing with long lists, Prolog will show only a prefix of the list. To force it output the entire list, append nl to your goal, e.g.: sum([a,a,b,b,b,c,d,d],[b,b,c,c,c,d,d,e],L), nl. .
Submit all your answers as a single pdf file on OWL. Solutions should be typed but high quality hand written solutions are acceptable. Source code, if required, is submitted separately, with the appropriate extension: .py, .rkt, .pl, etc.
The solutions should provide sufficient detail to support your claim. A simple yes/no answer without any supporting arguments is not given any marks. Note also that understanding the questions is part of solving the assignment. You are encouraged to ask questions when necessary, but try your best first. It is much more important to learn than merely getting the assignment done.
2