3 Basic Language
We introduce the syntax and semantics of a basic propositional language with an eye to the study of its metatheory. We will for example prove that propositional validity aligns with provability in an axiomatic deductive system for propositional logic.
3.1 Syntax
We first specify the syntax of a propositional language:
We choose a stock of propositional variables or atoms:
\[ AT := p, q, r, \cdots \]
We define the formulas of a propositional language \(\mathcal{L}\) recursively:
\[ \varphi ::= AT \ | \ \neg \varphi \ | \ (\varphi \to \psi) \]
Here is how to read the last line:
All atoms are formulas.
If \(\varphi\) is a formula, then \(\neg \varphi\) is a formula.
If \(\varphi\) and \(\psi\) are formulas, then \((\varphi \to \psi)\) is a formula.
Nothing else is a formula.
That is, a string of symbols is a formula if, and only if, it arises from atoms from negation or the conditional in a finite number of steps.
We follow common practice and omit outer parentheses when there is no risk of confusion. That is, we will treat a string of the form \(\varphi \to \psi\) as an abbreviation for the formula \((\varphi \to \psi)\).
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\).
We now define familiar connectives in terms of \(\neg\) and \(\to\):
Definition 3.1 (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.
Given a condition \(\Phi(\alpha)\) on formulas of \(\mathcal{L}\), if
- all atoms satisfy \(\Phi(\alpha)\),
- whenever a formula \(\varphi\) satisfies \(\Phi(\alpha)\), \(\neg \varphi\) satisfies \(\Phi(\alpha)\), and
- whenever two formulas \(\varphi\) and \(\psi\) satisfy \(\Phi(\alpha)\), \((\varphi \to \psi)\) satisfies \(\Phi(\alpha)\),
then every formula satisfies \(\Phi(\alpha)\)
Call a formula \(\varphi\) balanced iff \(\varphi\) contains the same number of left and right parentheses. We will use an induction to establish the proposition:
- Every formula is balanced.
We use an induction on the complexity of formulas.
Base Case. An atom, e.g., \(p\), contains an equal number of left and right parentheses, namely, zero.
Inductive Step for \(\neg\). Whenever a formula \(\varphi\) is balanced, its negation \(\neg \varphi\) is similarly balanced.
Let \(\varphi\) be a balanced formula. Since \(\neg \varphi\) contains exactly as many left and right parentheses as \(\varphi\), it still contains an equal number of left and right parentheses. So, \(\neg \varphi\) is balanced.
Inductive Step for \(\to\). Whenever formula \(\varphi\) and a formula \(\psi\) are balanced, the conditional \((\varphi \to \psi)\) is balanced as well.
Let \(\varphi\) and \(\psi\) be two balanced formulas and let \(n\) and \(m\) respectively be the number of left and right parentheses each formula has. \((\varphi \to \psi)\) contains \(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)\) similarly contains \(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)\) contains exactly the same number of left and right parentheses, which means that it will be a balanced formula.
We conclude that every formula is balanced.
3.2 Semantics
The role of a semantics for propositional logic is to explain how to interpret the formal language in order to provide fruitful definitions of validity and logical consequence. We do this by means of assignments of truth values to atomic formulas of the language.
An assignment for a propositional language \(\mathcal{L}\) is a function \(v\) from \(AT\) into \(\{0, 1\}\), which maps a propositional variable to a truth value.
A valuation \(V\) based on an assignment \(v\) is a function from the set of formulas into \(\{0, 1\}\) such that:
\[ \begin{array}{lll} V(p) & = & v(p)\\ & & \\ V(\neg \varphi) & = & \begin{cases}1 \ \ \ \text{if} \ V(\varphi) =0\\ 0 \ \ \ \text{if} \ V(\varphi) = 1 \end{cases}\\ & & \\ V(\varphi \to \psi) & = & \begin{cases}1 \ \ \ \text{if} \ V(\varphi) =0 \ \text{or} \ V(\psi) = 1\\ 0 \ \ \ \text{if} \ V(\varphi) = 1 \ \text{and} \ V(\psi) = 0\end{cases}\\ \end{array} \]
A valuation \(V\) satisfies a formula \(\varphi\) if, and only if, \(V(\varphi) = 1\).
A set of formulas \(\Gamma\) is satisfiable if, and only if, some valuation \(V\) satisfies every element of \(\Gamma\).
We write that a formula \(\varphi\) is satisfiable as shorthand for the claim that \(\{\varphi\}\) is satisfiable.
We write that a set \(\Gamma\) is unsatisfiable if \(\Gamma\) is not satisfiable.
A formula \(\varphi\) is propositionally valid, written \(\models \varphi\), if, and only if, every valuation satisfies \(\varphi\).
If \(\Gamma\) is a set of formulas, a formula \(\varphi\) is a logical consequence of \(\Gamma\), written \(\Gamma \models \varphi\), if, and only if, every valuation satisfying every element of \(\Gamma\) satisfies \(\varphi\).
True or false?
A formula \(\varphi\) is unsatisfiable if, and only if, \(\neg \varphi\) is valid.
A conjunction \(\varphi \wedge \psi\) is unsatisfiable if, and only if, \(\neg \varphi\) is valid or \(\neg \psi\) is valid.
\(\Gamma \models \varphi\) if, and only if, \(\Gamma \cup \{\varphi\}\) is satisfiable.
\(\Gamma \models \varphi\) if, and only if, \(\Gamma \cup \{\neg \varphi\}\) is unsatisfiable.