1. Definition The set of linked lists of natural numbers L is defined by: Basis Step: Recursive Step: lEL Ifle L and n E N, then (nl) EL Definition The function length: L + N that computes the length of a list is: length : L + N Basis Step: length(I) = 0 Recursive Step: If I EL and n e N, then length((n,1)) = 1 + length(1) Consider this incomplete) definition: Definition The function increment : defined by: that adds 1 to each element of a linked list is increment: Basis Step: increment(I) Recursive Step: If le Lin EN increment((n,1)) = (1 + n, increment(1)) Consider this incomplete) definition: Definition The function sum: L + N that adds together all the elements of the list is defined by: sum: L + N Basis Step: sum([]) = 0 Recursive Step: If I EL, EN sum((n,1)) = _ (d) Choose only and all of the following statements that are well-defined; that is, they correctly reflect the domains and codomains of the functions and quantifiers, and respect the notational conventions we use in this class. Note that a well-defined statement may be true or false. i. V E L (sum(1)) ii. 31 L (sum(1) A length(1)) iii. VI E L (sum( increment(1)) = 10) iv. 31 E L (sum(increment(1)) = 10) v. VI ELVn N((n xl) CL) vi. V ELE, E L (increment(sum(11)) = 12) vii. V E L (length(increment(1)) = length(1)) 1. Definition The set of linked lists of natural numbers L is defined by: Basis Step: Recursive Step: lEL Ifle L and n E N, then (nl) EL Definition The function length: L + N that computes the length of a list is: length : L + N Basis Step: length(I) = 0 Recursive Step: If I EL and n e N, then length((n,1)) = 1 + length(1) Consider this incomplete) definition: Definition The function increment : defined by: that adds 1 to each element of a linked list is increment: Basis Step: increment(I) Recursive Step: If le Lin EN increment((n,1)) = (1 + n, increment(1)) Consider this incomplete) definition: Definition The function sum: L + N that adds together all the elements of the list is defined by: sum: L + N Basis Step: sum([]) = 0 Recursive Step: If I EL, EN sum((n,1)) = _ (d) Choose only and all of the following statements that are well-defined; that is, they correctly reflect the domains and codomains of the functions and quantifiers, and respect the notational conventions we use in this class. Note that a well-defined statement may be true or false. i. V E L (sum(1)) ii. 31 L (sum(1) A length(1)) iii. VI E L (sum( increment(1)) = 10) iv. 31 E L (sum(increment(1)) = 10) v. VI ELVn N((n xl) CL) vi. V ELE, E L (increment(sum(11)) = 12) vii. V E L (length(increment(1)) = length(1))
