You are here
Homeconstruction of wellformed formulas
Primary tabs
construction of wellformed 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 Wellformed Formula
A wellformed formula, or wff for short, is then a special kind of finite string, sometimes called a term, formed in a specific, predetermined manner:
1. First, any propositional variable is always a wff. A wff that is a propositional variable is sometimes called an atom.
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. 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 wellformed 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 Wellformed 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. $V_{0}:=V$,
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. $\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.
Mathematics Subject Classification
03B05 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections
Comments
Proposition : Sign or Object?
There's a generic issue that comes up here, so I thought I'd open it up for discussion.
Most of the time we can get away with using the word "proposition" in an ambiguous way  to mean either a syntactic expression or a mathematical object, but there are times when we have to observe the distinction between a string in a formal language and one or another formal objects that we probably have in mind denoting with that string.
The simplest tactic I know for dealing with that is the one I learned in programming, which is to use words like "function" or "proposition" to describe the objects denoted and to use phrases like "function name" or "propositional expression" when we want to be clear that we are talking about a syntactic thingy.
The same issue arises with respect to a term like "connective", which is properly speaking a syntactic thing, and that is not itself a mathematical operation, but only used, when interpreted, to denote one.
Re: Proposition : Sign or Object?
I agree that "proposition" isn't the optimal choice in this context. It has been used to denote so many diverse concepts that it inevitably brings with it considerable historical baggage. In addition, the consensus holds propositions to be intensional entities and, therefore, outside the realm of settheoretic mathematics.
Re: Proposition : Sign or Object?
Maybe I should just use "wellformed formulas" or "terms" to denote such strings, or, like you said, "propositional expressions"... and connectives should really be "logical symbols"? What is your preference?
Re: Proposition : Sign or Object?
Actually my preference is the same as yours  it's just that there are expository situations that force us to draw the distinction between the syntax denoting and the object denoted a little more clearly, especially in pedagogy or in translating between different conventions of usage.
Any extra bit phrasing like "expression", "formula", or "sentence" works well enough when you need to emphasize that you are talking about a string in a specific calculus or language. That was the computer science strategy, and it worked well enough with the least bit of fuss. We don't really want to get all modeltheoretic in writing an intro to rudiments of logic.
Probably best to avoid "term" as many writers in logic use that for noun phrases like "x" and "f(x)" as opposed to clauses and sentences that have truth values, and some sources even use "term" for the denoted entity(!)
Re: Proposition : Sign or Object?
It's a handy enough word, just so long as we make it clear what tradition of usage we are following in what context.
I don't think there's any chance we'll reform the usage of any tradition that has an established following  about all we can do is navigate this or that passage between the various conventions.
I must have missed the vote on that intensional entity proposition  maybe my absentee ballot got lost in the post?
Re: Proposition : Sign or Object?
Jon Awbrey wrote:
"I must have missed the vote on that intensional entity proposition  maybe my absentee ballot got lost in the post?"
I had in mind the vast literature associated with "propositional attitudes", etc.: http://plato.stanford.edu/entries/propositions/ .
Re: Proposition : Sign or Object?
Sure, I was just trying to avoid wandering too far afield from the expository issue at hand.
It's not really all that necessary to discuss here, not just yet, but Peircean pragmatists take a different attitude toward propositional attitudes than what we get from the FregeRussell school of thought. Pragmatists formalize interpretive attitudes in the medium of of triadic sign relations, and the more rudimentary properties of these can be handled moderately well in set theory or even in a more categorical style of relation theory.