1. The equality operation on naturals is correctly computed bythe following pseudo-Java method:
boolean equals (natural x, natural y) {
if (zero(x)) return zero(y);
return equals(pred(x), pred(y));
}
2. Suppose we define a function f from naturals to naturals asfollows. We define f(0) to be 0, and for any natural x we definef(Sx) to be 1. Then this function satisfies the equation f(x · y) =f(x) · f(y), for any naturals x and y.
3.
Suppose I want to prove \"for all x: S0 + x = Sx\". The followingis valid:
Ordinary induction on all naturals x.
Base case: x = 0, the desired formula becomes \"S0 + 0 = S0\".This is true by the base case of the definition of addition.
Inductive hypothesis: S0 + x = Sx
Inductive goal: S0 + Sx = S(Sx)
Proof of inductive step: By the inductive case of the definitionof addition, S(S0 + x) = S0 + Sx. By the inductive hypothesis,applied inside the parentheses, the left-hand side of this equationis equal to S(Sx)). So the inductive goal is true.
Please help with True or False Questions
