1. (10 points) We say that L is a B-decision list (base case) if either T is a number y ez, or (induction step) T is equal to (f,, L') where f: Z {0,1}, v E Z, and L is a B decision list. We can also define the value val(L.I) of a B-decision list L at IEZ. (base case) If L is a number y, then val(L, 2) = y, and (induction step) if L = (f.v, L'), then val(L, 1) = if f(x) = 1 val(L', 2) otherwise Similarly one may define the length (L) of a B-decition list L. (base case) If L is a number y, then (L) = 1, and (induction step) if L = (f.v, L'), then (L) = f(L') +1. Assume that val(L, ) = for any r [1000) show that (L) > 1000. 1. (10 points) We say that L is a B-decision list (base case) if either T is a number y ez, or (induction step) T is equal to (f,, L') where f: Z {0,1}, v E Z, and L is a B decision list. We can also define the value val(L.I) of a B-decision list L at IEZ. (base case) If L is a number y, then val(L, 2) = y, and (induction step) if L = (f.v, L'), then val(L, 1) = if f(x) = 1 val(L', 2) otherwise Similarly one may define the length (L) of a B-decition list L. (base case) If L is a number y, then (L) = 1, and (induction step) if L = (f.v, L'), then (L) = f(L') +1. Assume that val(L, ) = for any r [1000) show that (L) > 1000