This exercise concerns the expressiveness of decision lists (Section 18.5). a. Show that decision lists can represent any Boolean function, if the size of the tests is not limited. - b. Show that if...

This exercise concerns the expressiveness of decision lists (Section 18.5).
a. Show that decision lists can represent any Boolean function, if the size of the tests is not limited.
- b. Show that if the tests can contain at most k literals each, then decision lists can represent any function that can be represented by a decision tree of depth k.