construction of well-formed formulas
Ways of Forming a Single Well-formed Formula
A well-formed formula, or wff for short, is then a special kind of finite string, sometimes called a term, formed in a specific, pre-determined manner:
First, any propositional variable is always a wff. A wff that is a propositional variable is sometimes called an atom.
The above two rules are the only rules of forming wffs.
Using the first method, therefore, finite strings such as
are well-formed formulas, while
are not, where and are binary and ternary connectives respectively, and are atoms.
Notice that in the last two methods, auxiliary symbols, such as the parentheses and the comma, are introduced to help the comprehensibility of wffs. Therefore, the third wff above becomes
using the second method, and
using the third method.
Remark. It is customary is to infix the connective between the two wffs, when the connective is binary, so that or becomes . Parentheses become necessary when using the infix notations, so as to avoid ambiguity. For example, is
constructed from and via , or and via ? Both are possible!
Formation of All Well-formed Formulas
Pick a method of forming wffs above, say, the first method. Rules 1 and 2 above suggest that if we were to construct the set of all wffs, we need to start with the set of atoms. From , we next form the set of wffs of the form , where each is an atom, and where (-ary) ranges over the entire set . This will go one indefinitely. In other words, we construct inductively as follows:
Notice that constants are in every where .
It can be shown that every wff can be uniquely written as for some -ary connective and wffs in . This is called the unique readability of wffs.
Furthermore, has a natural algebraic structure, as we may associate each a finitary operation on , given by . By defining , we see that is closed under each operation in , or that is an inductive set over with respect to . In fact, it is the smallest inductive set over (See Rule 3 above).
Finally, if is finite, it is not hard to see that is effectively enumerable, and there is an algorithm deciding whether a string is a wff or not.
|Title||construction of well-formed formulas|
|Date of creation||2013-03-22 18:52:20|
|Last modified on||2013-03-22 18:52:20|
|Last modified by||CWoo (3771)|