Artificial IntelligenceAIMA Exercises

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

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

Submit Solution