Consider the following definitions: Definition The set of linked lists of natural numbers L is defined by: Basis Step: EL Recursive Step: If I EL and n E N, then (n.) EL Definition The function length: L N that computes the length of a list is: Basis Step: Recursive Step: Ifl E L and n E N, then length: L length(I) length((n,)) N = 0 = 1 + length(1) Definition The function sum: L N that sums all the elements of a list is defined by: sum: L N sum(I) = 0 Recursive Step: If I EL.NEN sum((n.1)) = n + sum(I) Basis Step: Definition The function append : LXN + L that adds an element at the end of a linked list is defined by: append: LxNL Basis Step: If meN then append(1),m) = (m, I) Recursive Step: IfLEL and n E N and m N , then append(n.), m) =(n, append(I, m)) Definition The function nodes : L P (N) that is defined by: Basis Step: Recursive Step: If LEL, EN, then nodes: L nodes(I) nodes((n.1)) + P(N) = = {n} U nodes(l) (a) Disprove the following statement. That is specify a candidate counterexample, confirm it is in the domain of quantification, and evaluate the predicate being quantified to confirm it is F for this element. VEL - sum(1) = length()) (b) Fill in the basis step in the proof by mathematical induction of the following statement: VnEN SIEL sum(I) = 2n A length(1) = n) For reference, we include the recursive step in the proof below. Proof We proceed by mathematical induction on n. Basis Step This is what you need to provide. Recursive Step: Consider an arbitrary natural number n. We will prove that 316L (sum(I) = 2n A length(I) = n) + BIEL ( sum(I) = 2(n+1) A length(I) = n+1) Assume (as the induction hypothesis) that there is a witness linked list of natural numbers, call it w, such that sum() = 2n and length() = n. We need to produce a witness list to prove that the property holds for n + 1 as well. Consider 1 = (2,). Then I E L because 2 E N and I EL (by IH), so I is in the domain of quantification. We now evaluate the predicate, which is a conjunction so we evaluate each conjunct: sum(t) = sum( (2.)) del af rum 2 + sum(1) *2 + 2n = 2(n+1). as required; and length(t) = length( (2.1)) de defeath 1 + length(l.) 1+n=n+1, as required. Thus, both required conjuncts have been proved and (2.) is a witness Since the basis step and the recursive step have both been proved, the mathematical induction is complete. (e) Fill in the recursive step in the proof by structural induction of the following statement: VELVEN (nodes(l) Snodes( append(1,1))) For reference, we include the basis step in the proof below. Proof We proceed by structural induction on I. Basis Step We need to show that Vn EN nodes(I) Snodes append(I)..))). Towards universal generalization, let n be an arbitrary natural number. Using the recursive definition of each of the functions, we can evaluate the two sides of the desired subset inclusion and then compare. nodes(I) = 0 nodes( append(1),n)) = nodes((n,)) = {n} U nodes(l) = {n} by basis step in definition of nodes by basis step in definition of append by recursive step in definition of nodes by basis step in definition of nodes by definition of union and definition of Since the empty set is a subset of all other sets, the subset inclusion holds and the universal generalization is complete. Recursive Step: This is what you need to provide. Since the basis step and the recursive step have both been proved, the structural induction is complete. (d) (Graded for fair effort completeness) Define two functions: (1) the function remove: LXN L that removes one node containing a given value (if present) from a linked list and (2) the function remove All: LXN L that removes all nodes containing a given value (if present) from a linked list. Here are some sample function applications that your definition should produce: remove( (1,1),3 ) = (1,1) removeAll( (1,[]),3 ) = (1,1) remove( (3, 1,(3, 1))), 3) = (1,(3.)) removeAll( (3. (1.(3,1))), 3 ) = (1,1) Consider the following definitions: Definition The set of linked lists of natural numbers L is defined by: Basis Step: EL Recursive Step: If I EL and n E N, then (n.) EL Definition The function length: L N that computes the length of a list is: Basis Step: Recursive Step: Ifl E L and n E N, then length: L length(I) length((n,)) N = 0 = 1 + length(1) Definition The function sum: L N that sums all the elements of a list is defined by: sum: L N sum(I) = 0 Recursive Step: If I EL.NEN sum((n.1)) = n + sum(I) Basis Step: Definition The function append : LXN + L that adds an element at the end of a linked list is defined by: append: LxNL Basis Step: If meN then append(1),m) = (m, I) Recursive Step: IfLEL and n E N and m N , then append(n.), m) =(n, append(I, m)) Definition The function nodes : L P (N) that is defined by: Basis Step: Recursive Step: If LEL, EN, then nodes: L nodes(I) nodes((n.1)) + P(N) = = {n} U nodes(l) (a) Disprove the following statement. That is specify a candidate counterexample, confirm it is in the domain of quantification, and evaluate the predicate being quantified to confirm it is F for this element. VEL - sum(1) = length()) (b) Fill in the basis step in the proof by mathematical induction of the following statement: VnEN SIEL sum(I) = 2n A length(1) = n) For reference, we include the recursive step in the proof below. Proof We proceed by mathematical induction on n. Basis Step This is what you need to provide. Recursive Step: Consider an arbitrary natural number n. We will prove that 316L (sum(I) = 2n A length(I) = n) + BIEL ( sum(I) = 2(n+1) A length(I) = n+1) Assume (as the induction hypothesis) that there is a witness linked list of natural numbers, call it w, such that sum() = 2n and length() = n. We need to produce a witness list to prove that the property holds for n + 1 as well. Consider 1 = (2,). Then I E L because 2 E N and I EL (by IH), so I is in the domain of quantification. We now evaluate the predicate, which is a conjunction so we evaluate each conjunct: sum(t) = sum( (2.)) del af rum 2 + sum(1) *2 + 2n = 2(n+1). as required; and length(t) = length( (2.1)) de defeath 1 + length(l.) 1+n=n+1, as required. Thus, both required conjuncts have been proved and (2.) is a witness Since the basis step and the recursive step have both been proved, the mathematical induction is complete. (e) Fill in the recursive step in the proof by structural induction of the following statement: VELVEN (nodes(l) Snodes( append(1,1))) For reference, we include the basis step in the proof below. Proof We proceed by structural induction on I. Basis Step We need to show that Vn EN nodes(I) Snodes append(I)..))). Towards universal generalization, let n be an arbitrary natural number. Using the recursive definition of each of the functions, we can evaluate the two sides of the desired subset inclusion and then compare. nodes(I) = 0 nodes( append(1),n)) = nodes((n,)) = {n} U nodes(l) = {n} by basis step in definition of nodes by basis step in definition of append by recursive step in definition of nodes by basis step in definition of nodes by definition of union and definition of Since the empty set is a subset of all other sets, the subset inclusion holds and the universal generalization is complete. Recursive Step: This is what you need to provide. Since the basis step and the recursive step have both been proved, the structural induction is complete. (d) (Graded for fair effort completeness) Define two functions: (1) the function remove: LXN L that removes one node containing a given value (if present) from a linked list and (2) the function remove All: LXN L that removes all nodes containing a given value (if present) from a linked list. Here are some sample function applications that your definition should produce: remove( (1,1),3 ) = (1,1) removeAll( (1,[]),3 ) = (1,1) remove( (3, 1,(3, 1))), 3) = (1,(3.)) removeAll( (3. (1.(3,1))), 3 ) = (1,1)