« Section 1.1: Problem 5 Solution

# Section 1.1: Problem 6-A Solution

Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.
James R. Munkres
(Additional) If we know that a wff has a construction sequence of length 5, what is the largest possible length of the wff?
Suppose $L_{n}$ is the largest possible length of a wff having a construction sequence of length $n$ . Then, $L_{1}=1$ , and $L_{n}\le L_{n+1}$ . Now, in any construction sequence of length $n$ , the last expression is either a symbol, an expression of length $1$ , or the negation of an earlier expression, having the maximum length of $L_{n-1}+3$ , or a combination of two earlier expressions and a binary connective, having the maximum length of $2L_{n-1}+3$ . Therefore, the maximum possible length of a wff having a construction sequence of $n$ is $L_{n}=2^{n+1}-3$ , which also works for $n=1$ . In particular, $L_{5}=61$ . For example, $((((A\vee A)\vee(A\vee A))\vee((A\vee A)\vee(A\vee A)))$ $\vee(((A\vee A)\vee(A\vee A))\vee((A\vee A)\vee(A\vee A))))$ has a construction sequence $ $,(((A\vee A)\vee(A\vee A))\vee((A\vee A)\vee(A\vee A)))$ $,((((A\vee A)\vee(A\vee A))\vee((A\vee A)\vee(A\vee A)))$ $\vee(((A\vee A)\vee(A\vee A))\vee((A\vee A)\vee(A\vee A))))>$ .