This exercise concerns the expressiveness of
decision lists (SectionÂ learning-theory-section).

1. Show that decision lists can represent any Boolean function, if the size of the tests is not limited.

2. 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$.

1. Show that decision lists can represent any Boolean function, if the size of the tests is not limited.

2. 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$.

1. Show that decision lists can represent any Boolean function, if the
size of the tests is not limited.

2. 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$.