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]]
(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).
(c) 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.
(d) 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. Note that 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.