Unique Readability and a Parsing Algorithm

The truth recursion assigns $\overset{v}{ˉ} (φ)$ by climbing the formation tree of $φ$ , which makes sense only if $φ$ has one formation tree. It does: the parentheses in the definition of a wff leave no formula ambiguous.

Without parentheses, ambiguity is immediate. The string $A_{1} \lor A_{2} \land A_{3}$ can be assembled two ways, as $((A_{1} \lor A_{2}) \land A_{3})$ or as $(A_{1} \lor (A_{2} \land A_{3}))$ . Under $v (A_{1}) = T$ , $v (A_{3}) = F$ the two readings disagree — the first is $F$ (its conjunction has a false right conjunct), the second $T$ (its disjunction has a true left disjunct) — so $\overset{v}{ˉ}$ would have no well-defined value. The parentheses in every $E_{□} (α, β)$ exist to forbid exactly this.¹

The parenthesis lemmas

Two facts about how parentheses distribute in a wff are used throughout. The first was proved in the formation lesson.

The consequence follows from the lemma with the parenthesis-balance lemma: a wff is balanced, but a proper initial segment is left-heavy, so a proper initial segment cannot be a wff.

Proof of the initial-segment lemma. Apply the induction principle to the set $S$ of wffs all of whose proper initial segments are left-heavy. A sentence symbol has no proper initial segments, so it lies in $S$ vacuously. For closure under $E_{\land}$ , take $α, β \in S$ and list the proper initial segments of $(α \land β)$ :

$($ — one excess left parenthesis;
$(α_{0}$ where $α_{0}$ is a proper initial segment of $α$ — the leading $($ plus the excess $α_{0}$ carries by the inductive hypothesis;
$(α$ — the leading $($ over the balanced $α$ ;
$(α \land$ — same, with a connective added;
$(α \land β_{0}$ with $β_{0}$ a proper initial segment of $β$ — leading $($ , balanced $α$ , excess in $β_{0}$ ;
$(α \land β$ — leading $($ over two balanced pieces.

Every case is left-heavy. The other operations are handled the same way, so $S$ is closed and, by induction, contains all wffs. $■$

The running count of unmatched left parentheses makes the lemma visual. Scan a wff left to right, adding $1$ at each $($ and subtracting $1$ at each $)$ . The parenthesis-balance lemma says the count returns to $0$ at the end; the initial-segment lemma says it stays strictly positive at every proper initial segment along the way.

Unmatched left parentheses while scanning a wff left to right. The count ends at zero (balanced) but is strictly positive at every proper initial segment, so no prefix closes off into a wff of its own.

The parsing algorithm

The initial-segment lemma forces every choice a parser could make. The algorithm reads an expression and either rejects it or builds its formation tree from the top down, splitting each compound at its principal connective.

Algorithm:

\textsc{Parse}(\varepsilon)

— build the formation tree of an expression, or reject

1
place $\varepsilon$ at the root; mark it the only vertex
2
repeat
3
if every minimal vertex holds a sentence symbol then
4
return the tree
$\varepsilon$ is a wff
5
select a minimal vertex whose expression $\mu$ is not a sentence symbol
6
if the first symbol of $\mu$ is not "(" then reject
7
if the second symbol of $\mu$ is " $\neg$ " then
8
$\mu$ must be $(\neg\, \beta)$ with $\beta$ an expression
9
attach one child holding $\beta$
10
else
11
scan from the left to the shortest $(\alpha$ with $\alpha$ balanced and nonempty
12
the next symbol must be a binary connective
the principal connective
13
the remainder must be $\beta)$ with $\beta$ an expression
14
attach children holding $\alpha$ and $\beta$
15
until the tree is complete

Four observations establish correctness.¹

Termination. Each child holds a strictly shorter expression than its parent, so the tree depth is bounded by the length of $ε$ .
Forced choices. In the binary case the first constituent must be exactly $α$ : any shorter prefix is unbalanced (violating the parenthesis-balance lemma applied to a would-be constituent), and any longer one contains the balanced $α$ as a proper initial segment (violating the initial-segment lemma). The principal connective and the second constituent are then determined.
Rejection is sound. If the algorithm rejects, the only possible attempt to build a tree has failed, so $ε$ was no wff.
Acceptance is sound. If it succeeds, working up the finished tree shows every vertex holds a wff, the root included.

The parsing decision flow for one non-atomic vertex; every branch is forced, so the tree it produces is the only tree the expression admits.

Unique readability

Because every choice the parser makes is forced, it constructs the only possible tree for the given wff. This is the central syntactic fact of the language.

The language is unambiguous, and the parser exhibits the tree — what the truth recursion needed. For any wff $φ$ there is one tree; propagating values up it assigns $\overset{v}{ˉ} (φ)$ without ambiguity, and the resulting function meets the recursion clauses. So $\overset{v}{ˉ}$ exists, completing the half of the unique-extension theorem left open under truth assignments. The general form of this unique readability licenses recursion argument is the recursion theorem.

An almost-ambiguous string is pinned to a single reading by its parentheses: the outer conjunction, not the disjunction, is the principal connective, so only the left tree is a legal parse.

The figure shows the two readings of $((A \lor B) \land C)$ : only the tree whose root is the conjunction is a legal parse, because the outermost matched pair of parentheses encloses $(A \lor B) \land C$ with $\land$ as its principal connective.

Polish notation

Parentheses are one way to avoid ambiguity; they are not the only way. Polish (prefix) notation writes the connective before its arguments and drops the parentheses entirely. In place of $(α \land β)$ one writes $\land α β$ , and the P-wffs are generated from the sentence symbols by

D_{\neg} (α) = \neg α, D_{\land} (α, β) = \land α β, D_{\lor} (α, β) = \lor α β, D_{\to} (α, β) = \to α β, D_{\leftrightarrow} (α, β) = \leftrightarrow α β .

The same formula parenthesized (infix) and in parenthesis-free Polish prefix notation; the connective moves ahead of its operands, and no punctuation is needed to recover the structure.

Polish notation is well suited to machine processing; compilers routinely convert input formulas into it. Its own unique readability theorem is proved in the first-order parsing lesson, where the parenthesis-free case reappears.

Omitting parentheses

For readability, some parentheses are dropped by convention when naming wffs, with precedence rules restoring them.

Outermost parentheses are omitted: $A \land B$ names $(A \land B)$ .
Negation binds tightest: $\neg A \land B$ is $((\neg A) \land B)$ , not $(\neg (A \land B))$ .
Conjunction and disjunction bind tighter than the conditional and biconditional: $A \land B \to \neg C \lor D$ is $((A \land B) \to ((\neg C) \lor D))$ .
Repeated connectives group to the right: $α \to β \to γ$ is $(α \to (β \to γ))$ .

These abbreviations violate the strict naming rules on purpose; the license is harmless because only wffs are ever named, and each abbreviation restores to exactly one wff.

Enderton, §1.3 — the ambiguity of unparenthesized strings, Lemmas 13A and 13B, the top-down parsing algorithm with its four correctness observations, unique readability, Polish notation, and the parenthesis-omission conventions. ↩ ↩²

The parenthesis lemmas

The parsing algorithm

Unique readability

Polish notation

Omitting parentheses

Footnotes