The primitive vocabulary of the language \(\mathcal{L}\) of propositional logic includes:
The use of \(\neg\) and \(\to\) as basic connectives is a departure from common presentations of the language, which generally include \(\wedge\), \(\vee\), and \(\bot\). 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 \(\mathcal{L}\):
The set of well-formed formulas is constructed inductively from an initial set of atomic formulas. The set \(Form(\mathcal{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} \top & := & (p \to p)\\ \bot & := & \neg \top \\ (\varphi \vee \psi) & := & (\neg \varphi \to \psi)\\ (\varphi \wedge \psi) & := & \neg (\varphi \to \neg \psi)\\ (\varphi \leftrightarrow \psi) & := & (\varphi \to \psi) \wedge (\psi \to \varphi) \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 \(\Phi\) on formulas of \(\mathcal{L}\), if
then every formula satisfies \(\Phi\).
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.
The next two steps establish each a generalization of a conditional statement:
Inductive Step for \(\neg\) If a formula \(\varphi\) is __________, then its negation \(\neg \varphi\) is __________
Inductive Step for \(\to\) If a formula \(\varphi\) is __________ and a formula \(\psi\) is __________, then the conditional \((\varphi \to \psi)\) is __________
Once the three steps are completed, we are entitled to conclude:
Here is an example of a simple induction on the complexity of formulas:
Example 4.1 Call a well-formed formula \(\varphi\) balanced if, and only if, it contains the same number of left and right parentheses. We will use an induction to establish the proposition:
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 \(\varphi\) is balanced, then the negation \(\neg \varphi\) will be balanced.
Let \(\varphi\) be a balanced well-formed formula. Since \(\neg \varphi\) contains exactly as many left and right parentheses as \(\varphi\), we have that it contains an equal number of left and right parentheses. So, \(\neg \varphi\) is balanced.
Inductive Step for \(\to\). If a formula \(\varphi\) and a formula \(\psi\) are each balanced, then the conditional \((\varphi \to \psi)\) is balanced as well.
Let \(\varphi\) and \(\psi\) be two balanced well-formed formulas and let \(n\) and \(m\) be the number of left and right parentheses each formula has. \((\varphi \to \psi)\) will contain \(n+m +1\) left parentheses, that is the number of left parentheses in \(\varphi\) plus that of left parentheses in \(\psi\) plus the initial left parenthesis of the formula. \((\varphi \to \psi)\) will similarly contain \(n+m +1\) right parentheses, that is the number of right parentheses in \(\varphi\) plus that of right parentheses in \(\psi\) plus the final right parenthesis of the formula. So, \((\varphi \to \psi)\) 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.