unique readability of parenthesized formulas
Given a set of propositional variables, and a set of logical connectives, one may form the set of well-formed formulas, or wffs. The appearance of a wff depends on the formation rule of a well-formed formula. Auxiliary symbols may or may not be used in the construction of a wff. In the parent entry, we proved that every well-formed formula constructed without the aid of auxiliary symbols has a unique appearance. In this entry, we show that, with the aid of auxiliary symbols such as parentheses, specifically, unique readability is achieved as well. The specific formation rule we have in mind is the following: if are existing wffs, and is -ary, then so is a wff.
Wffs constructed using the formation rule above have unique readability.
We will only give a partial proof here, since the portion not proved can be easily produced by closely following the proof from the parent entry.
Sketch of Proof.
A wff has one of the following three forms: , , or , where is atomic (propositional variable), and are nullary and -ary connectives respectively, with , and all are existing wffs.
First, it is easy to see that every wff has the same number of left parentheses as right parentheses, and every proper non-trivial initial segment of a wff has more left than right parentheses.
Now, suppose and are wffs and . We look at the following cases:
If is atomic, then so must be , and vice versa.
If , then is either where is nullary, or , where is -ary with . However, the second choice is not possible, as the length of the word is longer than . So we are left with . Canceling the parentheses in the equation , we have .
In all three cases, we have unique readability, the proof is complete. ∎
Commas are also often used as auxiliary symbols in forming wffs to improve comprehensibility without violating unique readability.
Wffs constructed using the following formula formation rule have unique readability: if are existing wffs, and is -ary, then so is a wff.
Sketch of Proof.
Like the last proof, a wff also has one of the three forms: , , or , where is atomic (propositional variable), and are nullary and -ary connectives respectively, with , and all are existing wffs.
The rest of the proof goes pretty much the same as the last one. The last case deserves a little more attention:
If , and has the form . We again have and , after equating and . Eliminating the parentheses, we get . So is a suffix of , which means that it is either a suffix of , or has the form , where is a suffix of , and . In the latter case, if is the empty word, then , which is impossible because no wffs begins with a comma. So is a non-trivial suffix of . Using (see the parent entry) modified so that , we again show that can not be . Therefore, is a suffix of . We will let the reader finish the rest. ∎
Finally, another common practice is to infix a connective when it is binary. We again have unique readability:
Wffs constructed using the following formula formation rule have unique readability: if are existing wffs, and is -ary, then so is a wff if , and so is a wff if .
Sketch of Proof.
The proof is very much the same as before. A wff in this case has four forms: , , , or . We only need to observe the following:
if has the form , and , then can not have the form , for otherwise begins with , which is impossible, because a wff never begins with a connective symbol, as it either begins with a left parenthesis , or is an atom.
so has the form and has the form , which means that is a prefix of . Then is either a prefix of , or has the form , where is a prefix of . Let us look at the latter case. can not be the empty word, for otherwise , and no wffs end with a connective symbol. can not be or , for otherwise is longer (in length) than . So is a proper non-trivial prefix of , but this is also impossible, for then has more left than right parentheses, which means , or , a wff, has more left than right parentheses. This shows that is a prefix of .
The rest of the proof is now easy. ∎
|Title||unique readability of parenthesized formulas|
|Date of creation||2013-03-22 18:52:44|
|Last modified on||2013-03-22 18:52:44|
|Last modified by||CWoo (3771)|