# construction of well-formed formulas

Given a countable set $V$ of propositional variables, and a set $F$ of logical connectives disjoint from $V$, one can create the set of all finite strings (or words) over $V\cup F$.

## 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:

1. 1.

First, any propositional variable is always a wff. A wff that is a propositional variable is sometimes called an atom.

2. 2.

Once we have formed a set wffs, we may form new ones. Given an $n$-ary connective $\alpha\in F$, and wffs $p_{1},\ldots,p_{n}$, there are several methods to represent the newly formed wff, some of the common ones are:

• $\alpha p_{1}\cdots p_{n}$

• $p_{1}\cdots p_{n}\alpha$

• $(\alpha p_{1}\cdots p_{n})$

• $\alpha(p_{1},\cdots,p_{n})$

In particular, every nullary connective (constant) is a wff (with no additional wffs attached).

3. 3.

The above two rules are the only rules of forming wffs.

Using the first method, therefore, finite strings such as

 $v_{2},\qquad\alpha v_{1}v_{2},\qquad\mbox{and}\qquad\beta v_{3}\alpha v_{2}% \beta v_{1}v_{1}v_{3}v_{2}$

are well-formed formulas, while

 $v_{2}v_{3},\qquad v_{1}\alpha v_{2}v_{1},\qquad\mbox{and}\qquad\beta v_{2}v_{3}$

are not, where $\alpha$ and $\beta$ are binary and ternary connectives respectively, and $v_{i}$ 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

 $(\beta v_{3}(\alpha v_{2}(\beta v_{1}v_{1}v_{3}))v_{2})$

using the second method, and

 $\beta(v_{3},\alpha(v_{2},\beta(v_{1},v_{1},v_{3})),v_{2})$

using the third method.

Remark. It is customary is to infix the connective between the two wffs, when the connective is binary, so that $(\alpha pq)$ or $\alpha(p,q)$ becomes $(p\alpha q)$. Parentheses become necessary when using the infix notations, so as to avoid ambiguity. For example, is

 $p\vee q\wedge r$

constructed from $p\vee q$ and $r$ via $\wedge$, or $p$ and $q\wedge r$ via $\vee$? 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 $\overline{V}$ of all wffs, we need to start with the set $V$ of atoms. From $V$, we next form the set of wffs of the form $\alpha p_{1}\cdots p_{n}$, where each $p_{i}$ is an atom, and where $\alpha$ ($n$-ary) ranges over the entire set $F$. This will go one indefinitely. In other words, we construct $\overline{V}$ inductively as follows:

1. 1.

$V_{0}:=V$,

2. 2.

$V_{i+1}:=V_{i}\cup\bigcup_{\alpha\in F}\{\alpha p_{1}\cdots p_{n}\mid\alpha% \mbox{ is }n\mbox{-ary and each }p_{j}\in V_{i}\}$,

3. 3.

$\overline{V}:=\bigcup_{i=0}^{\infty}V_{i}$.

Notice that constants are in every $V_{i}$ where $i>0$.

It can be shown that every wff can be uniquely written as $\alpha p_{1}\cdots p_{n}$ for some $n$-ary connective and wffs $p_{i}$ in $\overline{V}$. This is called the unique readability of wffs.

Furthermore, $\overline{V}$ has a natural algebraic structure, as we may associate each $\alpha\in F$ a finitary operation $[\alpha]$ on $\overline{V}$, given by $[\alpha](p_{1},\ldots,p_{n})=\alpha p_{1}\cdots p_{n}$. By defining $[F]:=\{[\alpha]\mid\alpha\in F\}$, we see that $\overline{V}$ is closed under each operation in $[F]$, or that $\overline{V}$ is an inductive set over $V$ with respect to $[F]$. In fact, it is the smallest inductive set over $V$ (See Rule 3 above).

Finally, if $F$ is finite, it is not hard to see that $\overline{V}$ is effectively enumerable, and there is an algorithm deciding whether a string is a wff or not.

Title construction of well-formed formulas ConstructionOfWellformedFormulas 2013-03-22 18:52:20 2013-03-22 18:52:20 CWoo (3771) CWoo (3771) 10 CWoo (3771) Feature msc 03B05