Length of the well formed formula $(((p_0)\rightarrow ((p_1)∧(p_{32}))) \rightarrow ((((p_{13})∧(p_6))∨(p_{317})) \rightarrow (p_{26})))$

158 Views Asked by At

How is the length of this well formed formula defined as $5$?

$\big(((p_{0})\rightarrow ((p_1) \land (p_{32}))) \rightarrow ((((p_{13}) \land (p_6)) \lor (p_{317})) \rightarrow (p_{26}))).$

(from Epstein’s textbook: Classical Mathematical Logic: the Semantic Foundations of Logic, p. 10)

According to the inductive definition, the number associated to $((p_1) \land (p_{32}))$ is $2$, and that associated to $(p_0)$ is $1$.

The rule for associating a number to a compound wff says (p. 7):

If $A$ (call LHS) and $B$ (call RHS) are wffs and the maximum of the numbers assigned to $A$ and to $B$ is $n$, then each of $( \lnot A)$, $(A \rightarrow B)$, $(A∧B)$, $(A∨B)$ is a compound wff to which we assign the number $n + 1$.

For the part $(((p_0)\rightarrow ((p_1) \land (p_{32})))$, it is seen that $(p_0)$ has length 1 and $((p_1) \land (p_{32}))$ has length $1+1=2$, since it is a compound wff and both $(p_1)$ and $(p_{32})$ has length 1. But for the compound wff $(((p_0)\rightarrow ((p_1) \land (p_{32})))$,$(p_0)$ has length $1$ and $((p_1)∧(p_{32}))$ has length $2$. How do I now find this length, when the lengths of LHS and RHS of the compound wff are not equal?

1

There are 1 best solutions below

1
On BEST ANSWER

When the lengths of LHS and RHS of the compound well formed formula are not equal you have to take the maximum among them, according to Epstein's definition of the length $\mathrm{len}(\varphi)$ of a well formed formula $\varphi$ (in Classical Mathematical Logic: The Semantic Foundations of Logic, pp. 7-9). More precisely, given a binary connective $\circ$, then $\mathrm{len}(A \circ B) = \max\{\mathrm{len}(A),\mathrm{len}(B)\}+1$.

Concretely, the length of \begin{align} (((p_0) \to ((p_1) \land (p_{32}))) \to ((((p_{13}) \land (p_6)) \lor (p_{317})) \to (p_{26}))) \end{align} is \begin{align} \max \{\mathrm{len}((p_0) \to ((p_1) \land (p_{32}))), \mathrm{len}((((p_{13}) \land (p_6)) \lor (p_{317})) \to (p_{26})) \} + 1. \end{align}

Now, \begin{align} \mathrm{len}((p_0) \to ((p_1) \land (p_{32}))) &= \max \{\mathrm{len}(p_0), \mathrm{len}((p_1) \land (p_{32})) \} + 1 \\ &= \max\{1,2\} + 1 = 3 \\ \mathrm{len}((((p_{13}) \land (p_6)) \lor (p_{317})) \to (p_{26})) &= \max\{\mathrm{len}(((p_{13}) \land (p_6)) \lor (p_{317})), \mathrm{len} (p_{26})\} + 1 \\ &=\max\{ 3, 1\} + 1 = 4 \end{align} because \begin{align} \mathrm{len}(((p_{13}) \land (p_6)) \lor (p_{317}) &= \max\{\mathrm{len}((p_{13}) \land (p_6)) , \mathrm{len}(p_{317})\} + 1 \\ &= \max \{2,1\} + 1 = 3. \end{align}

Therefore, the length of \begin{align} (((p_0) \to ((p_1) \land (p_{32}))) \to ((((p_{13}) \land (p_6)) \lor (p_{317})) \to (p_{26}))) \end{align} is

\begin{align} \max \{\mathrm{len}((p_0) \to ((p_1) \land (p_{32}))), \mathrm{len}((((p_{13}) \land (p_6)) \lor (p_{317})) \to (p_{26})) \} + 1 \\ = \max\{4,3\} + 1 = 5 \end{align} as correctly stated in Epstein's book (p. 10).