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 VF.

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 αF, and wffs p1,,pn, there are several methods to represent the newly formed wff, some of the common ones are:

    • αp1pn

    • p1pnα

    • (αp1pn)

    • α(p1,,pn)

    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

v2,αv1v2,and  βv3αv2βv1v1v3v2

are well-formed formulas, while

v2v3,v1αv2v1,and  βv2v3

are not, where α and β are binary and ternary connectives respectively, and vi 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

(βv3(αv2(βv1v1v3))v2)

using the second method, and

β(v3,α(v2,β(v1,v1,v3)),v2)

using the third method.

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

pqr

constructed from pq and r via , or p and qr 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 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 αp1pn, where each pi is an atom, and where α (n-ary) ranges over the entire set F. This will go one indefinitely. In other words, we construct V¯ inductively as follows:

  1. 1.

    V0:=V,

  2. 2.

    Vi+1:=ViαF{αp1pnα is n-ary and each pjVi},

  3. 3.

    V¯:=i=0Vi.

Notice that constants are in every Vi where i>0.

It can be shown that every wff can be uniquely written as αp1pn for some n-ary connective and wffs pi in V¯. This is called the unique readability of wffs.

Furthermore, V¯ has a natural algebraic structurePlanetmathPlanetmath, as we may associate each αF a finitary operation [α] on V¯, given by [α](p1,,pn)=αp1pn. By defining [F]:={[α]αF}, we see that V¯ is closed underPlanetmathPlanetmath each operation in [F], or that V¯ is an inductive setMathworldPlanetmath 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 V¯ is effectively enumerable, and there is an algorithm deciding whether a string is a wff or not.

Title construction of well-formed formulas
Canonical name ConstructionOfWellformedFormulas
Date of creation 2013-03-22 18:52:20
Last modified on 2013-03-22 18:52:20
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 10
Author CWoo (3771)
Entry type Feature
Classification msc 03B05