Let S be a list representing a set of atomic values (integers or symbols). Let PS be a list of lists. Let the Prolog relation subsets(S,PS) be true when PS represents the power set of S (that is, the set of all subsets of S).
(a) The most common way to use the subsets relation is to fix S to a known value, and let PS be free (a variable). Then Prolog will set PS to be the power set of S. Give facts and rules for the subsets relation that will allow PS to be correctly computed given S. For example,
subsets([],PS). => PS = [[]]
subsets([1],PS). => PS = [[],[1]]
subsets([a,b],PS). => PS = [[],[b],[a],[a,b]]
Hint: We did this problem in class in Scheme, and the same approach is useful. Think about peeling off the first element of S, finding all subsets of the rest of S, and then constructing your answer as the combination of both the subsets of the rest of S and also what you get when you append the first element of S onto each of those subsets you've generated.
(b) Another way the subsets relation might be used is to fix both S and PS to known values. Then the relation would test whether PS really is a power set of S. For example,
subsets([],[[]]). => yes
subsets([1],[[],[1]]). => yes
subsets([1],[[1],[]]). => yes
subsets([1],[[1]]). => no
Does your solution to part (a) correctly handle the case in which both S and PS are fixed to known values (that is, ground)? If so, you are done with this part. If not, extend your solution to part (a) to handle this case. Be sure to note that the set values that are bound to PS need not be in the same order as the values that would be computed by subsets given S (though they must represent the same set).
Hint: Use part (a) to determine the powersets of S, then see if what you get is equal to PS using the set equality predicate you wrote for the last assignment. If you didn't succeed in making that work, email me and I'll send you a working version.
(c) This part is just for fun: you don't need to do it to get full credit on the assignment. It may also happen that the subsets relation is used when both S and PS are free (that is variables, not bound to any values). In this case the relation would generate pairs of possible values for S and PS, starting with the simplest (the empty list), and then the list with one element, then two elements, etc. Since the actual list elements that will be used are unknown, Prolog generates ``anonymous variables'' of the form _integer (e.g., _G123). For example, in this case we might generate
subsets(S,PS). =>
S = [], PS = [[]] ;
S = [_G737],PS = [[],[_G737]] ;
S = [_G737,_G739], PS = [[],[_G739],[_G737],[_G737,_G739]]
Does your solution to part (b) correctly handle the case in which both S and PS are not fixed (that is, free)? If so, you are done with this part. If not, extend your solution to part (b) to handle this case.
Hint: the philosophy from part (a) works here as well. Try your code from part (a) when S and PS are unknown, and see what modifications need to be made. The basic framework should be fairly similar.
(d) This part is just for fun: you don't need to do it to get full credit on the assignment. Finally, it may happen that the subsets relation is used when S is free, but PS is bound to fixed value. In this case the relation must generate a value for S such that PS is S's power set. It may happen that no such S exists, in which case the relation should answer no. For example,
subsets(S,[[]]). => S = []
subsets(S,[[],[a]]). => S = [a]
subsets(S,[[a],[]]). => S = [a]
subsets(S,[[a]]). => no
Does your solution to part (c) correctly handle the case in which S is free and PS is fixed? If so, you are done with this part. If not, extend your solution to part (c) to handle this case.
Hint: since that there is no direct way to compute S from PS, you can use your solution to part (c) to "guess" possible solutions and match them with the known value of PS. Be careful though; in the case that no solution exists, you must be sure to stop guessing possible solutions when they become too large to possibly match the value of PS.
Submit your code in a file called subsets.prolog.