A subformula beginning at the first opening parenthesis equals the whole logical formula by prefix-freeness of fully parenthesized formulas. Every other subformula is the logical formula of a proper syntax subtree, by the parsing argument in part (iii). The two children of the root are precisely and , so such a subtree lies entirely inside one of those children. In particular no logical formula substring can begin in and cross the principal logical implication symbol into .
Conversely, each subformula of either child is visibly a substring of the whole expression, as is the whole expression itself. ThusTogether these cases identify the substring definition of a subformula with its usual syntax-tree definition.
Articles by others on the same topic
There are currently no matching articles.