4 Syntax

The primitive vocabulary of the language $L$ of propositional logic includes:

a countable set of propositional variables $p$ , $q$ , $r$ , … with or without numerical subscripts.
a monadic sentential operator: $\neg$
a binary sentential operator: $\to$
two parentheses: $($ , $)$

The use of $\neg$ and $\to$ as basic connectives is a departure from common presentations of the language, which generally include $\land$ , $\lor$ , and $⊥$ . These connectives will be defined in terms of $\neg$ and $\to$ .

Certain strings of symbols in the vocabulary of propositional logic qualify as well-formed formulas (wff) of the language. Those are the strings constructed in accordance to the following rules:

Definition 4.1 (Well-Formed Formula) We define what is for a string of symbols of the language to be a well-formed formula of $L$ :

All propositional variables are well-formed formulas of $L$ .
If $φ$ is a well-formed formula of $L$ , then $\neg φ$ is a well-formed formula of $L$ .
If $φ$ and $ψ$ are well-formed formulas of $L$ , then $(φ \to ψ)$ is a well-formed formula of $L$ .
Nothing else is a well-formed formula of $L$ .

The set of well-formed formulas is constructed inductively from an initial set of atomic formulas. The set $F o r m (L)$ of well-formed formulas of propositional logic is the $\subseteq$ -least set containing every propositional variable and closed under applications of negation and conditional.

We now define familiar connectives in terms of $\neg$ and $\to$ , where $:=$ is read as: `abbreviates’.

Definition 4.2 (Connectives) $\begin{array}{lll} ⊤ & := & (p \to p) \\ ⊥ & := & \neg ⊤ \\ (φ \lor ψ) & := & (\neg φ \to ψ) \\ (φ \land ψ) & := & \neg (φ \to \neg ψ) \\ (φ \leftrightarrow ψ) & := & (φ \to ψ) \land (ψ \to φ) \end{array}$

The inductive definition of well-formed formula vindicates a principle of induction for well-formed formulas, which will help us prove different generalizations over them.

Proposition 4.1 (Induction on the Complexity of Well-Formed Formulas) Given a condition $Φ$ on formulas of $L$ , if

every atomic formula satisfies $Φ$ ,
if a formula $φ$ satisfies $Φ$ , $\neg φ$ satisfies $Φ$ , and
if two formulas $φ$ and $ψ$ satisfy $Φ$ , $(φ \to ψ)$ satisfies $Φ$ ,

then every formula satisfies $Φ$ .

We will use the method of induction on the complexity of a formula to prove that every formula satisfies a certain condition __________.

We proceed in three steps. The base case is a proof that every propositional variable satisfies the condition.

Base Case Every propositional variable is __________

The next two steps establish each a generalization of a conditional statement:

Inductive Step for $\neg$ If a formula $φ$ is __________, then its negation $\neg φ$ is __________
Inductive Step for $\to$ If a formula $φ$ is __________ and a formula $ψ$ is __________, then the conditional $(φ \to ψ)$ is __________

Once the three steps are completed, we are entitled to conclude:

Every formula is __________

Here is an example of a simple induction on the complexity of formulas:

Example 4.1 Call a well-formed formula $φ$ balanced if, and only if, it contains the same number of left and right parentheses. We will use an induction to establish the proposition:

Every well-formed formula is balanced.

We use an induction on the complexity of formulas.

Base Case. A propositional variable contains an equal number of left and right parentheses, namely, zero.
Inductive Step for $\neg$ . If a formula $φ$ is balanced, then the negation $\neg φ$ will be balanced.

Let $φ$ be a balanced well-formed formula. Since $\neg φ$ contains exactly as many left and right parentheses as $φ$ , we have that it contains an equal number of left and right parentheses. So, $\neg φ$ is balanced.
Inductive Step for $\to$ . If a formula $φ$ and a formula $ψ$ are each balanced, then the conditional $(φ \to ψ)$ is balanced as well.

Let $φ$ and $ψ$ be two balanced well-formed formulas and let $n$ and $m$ be the number of left and right parentheses each formula has. $(φ \to ψ)$ will contain $n + m + 1$ left parentheses, that is the number of left parentheses in $φ$ plus that of left parentheses in $ψ$ plus the initial left parenthesis of the formula. $(φ \to ψ)$ will similarly contain $n + m + 1$ right parentheses, that is the number of right parentheses in $φ$ plus that of right parentheses in $ψ$ plus the final right parenthesis of the formula. So, $(φ \to ψ)$ will contain exactly the same number of left and right parentheses, which means that it will be a balanced well-formed formula.

We conclude that a well-formed formula is balanced.