Propositional logic is the study of the five logical connectives not, or, and, if ... then ... & ... if and only if ... . In this chapter we describe a language for propositional logic, assign truth functions to the five logical connectives, and define the fundamental concept tautological consequence. In Chapter 3 we will introduce a formal system whose intended interpretation is propositional logic. Thus, one may regard Chapter 2 as a discussion of the language of the formal system that we propose to study in Chapter 3; alternatively, Chapter 2 is a semantic approach to propositional logic.
The only time that we can be confident that the conclusion of an argument is true, is when the argument is valid and all hypotheses of the argument are true. This is the basis for the definition of a valid argument - more about this later.
Symbols: The symbols of the language are
The letters $p_1, p_2, p_3, \dots$ are called propositional variables and are interpreted as simple propositions. The list is infinite to ensure that we never run out of propositional variables when constructing formulas. The two symbols ( and ) are used for punctuation. Finally, the remaining symbols are called logical connectives. Their names and interpretations are as follows:
| Symbol | Name | Interpretation |
|---|---|---|
| $\neg$ | Negation | not |
| $\lor$ | Disjunction | or |
| $\land$ | Conjunction | and |
| $\rightarrow$ | Conditional | if ... then ... |
| $\leftrightarrow$ | Biconditional | ... if and only if ... |
The symbols $(, \space ), \space \neg, \space \lor, \space \land, \rightarrow$ and $\leftrightarrow$ are often called logical symbols. In translating English sentences into the language of propositional logic, these symbols are always interpreted in the same way
Formulas: The formulas are defined inductively by these three rules:
In other words, the formulas of propositional logic either are propositional variables or are built up from simpler formulas using the operators $\neg$, $\lor$, $\land$, $\rightarrow$ and $\leftrightarrow$. The formula $\neg A$ is called the negation of $A$; the formula $(A \lor B)$ is called the disjunction with disjuncts $A$ and $B$; the formula $(A \land B)$ is called the conjunction with disjuncts $A$ and $B$; the formula $(A \rightarrow B)$ is called the conditional (or implication) with antecedent $A$ and consequent $B$; the formula $(A \leftrightarrow B)$ is called the biconditional of $A$ and $B$.
Each of the following expressions is a formula:
For example, to justify (4), $p_1$, $p_2$ and $p_6$ are formulas by F1; $(p_1 \rightarrow p_2)$ and $\neg p_6$ are formulas by F2; $((p_1 \rightarrow p_2) \land \neg p_6)$ is a formula by F2.
We will show that the expression $(p_1 \land \neg(\neg p_3))$ is not a formula. Suppose that $(p_1 \land \neg(\neg p_3))$ is a formula. By F3, $(p_1 \land \neg(\neg p_3))$ is obtained by a finite number of applications of F1 and F2. In particular, F2 applies and $p_1$ and $\neg (\neg p_3)$ are both formulas. Now if $\neg (\neg p_3)$ is a formula, then, again by F2, $(\neg p_3)$ must be a formula. Moreover, $(\neg p_3)$ is the result of an application of F2. But according to F2, parentheses are not placed about the negation symbol. So $(p_1 \land \neg (\neg p_3))$ is not a formula, as required.
Convention: It is convenient to make some conventions on the writing of formulas. First of all, the letters $p$, $q$, $r$, $s$, and so on are often used or propositional variables instead of the more precise $p_1$, $p_2$, $p_3$, ... Also, outer parentheses in formulas are usually omitted since no ambiguity can occur. With these conventions, formula (2), (3) and (4) of Example 2.1.1 become
When $\lor$ is used more than twice in succession without parentheses, it is understood that the parentheses are associated to the right. For example, $p \lor q \lor r$ is used for $(p \lor (q \lor r))$, and $p \lor q \lor r \lor s$ is used for $(p \lor (q \lor (r \lor s)))$. A similar remark applies to $\land$. Finally, brackets are occasionally used in place of parentheses to imporve readability. For example, $$[p \rightarrow (q \rightarrow r)] \leftrightarrow [(p \land q) \rightarrow r]$$ is acceptable as a formula.
We express the following argument in the language of propositional logic:
Assign propositional variables to simple propositions as follows: $p = \text{The quartet will play Haydn}$; $q = \text{The quartet will play Mozart}$. We then have $\neg (p \land q)$, $\neg p$, $\therefore q$. A more relaxed and suggestive translation is $\neg (H \land M)$, $\neg H$, $\therefore M$. The reader is encouraged to use this more informal symbolism when translating English sentences into the language of propositional logic.
The letters $A$, $B$, $C$ $D$ and $E$ are used to denote formulas; $\Gamma$ and $\Delta$ are used to denote sets of formulas. It should be stressed that while $(p_1 \rightarrow p_2)$ is an official formula of our language, $(A \rightarrow B)$ is not. Rather, $(A \rightarrow B)$ represents an infinite number of formulas and is an example of what is known as a formula scheme. To illustrate, $(p_1 \rightarrow p_2)$ and $(p_3 \rightarrow p_1)$, as well as more complicated formulas such as $(\neg p_2 \rightarrow (p_3 \land p_4))$, are all instances of $(A \rightarrow B)$.
In the study of formal languages, it is customary to call the language under study the object language and the language used to talk about the object language, the metalanguage. For example, in this section, the object language is the language of propositional logic and the metalanguage is English (supplemented with some additional symbols). In this situation, the letters $A$, $B$, $C$, $D$ and $E$, which stand for formulas, are called metavariables. They are not a part of the object language but instead stand for certain concepts of the object language, namely formulas.
We will end this section with an inductive procedure for showing that every formula of propositional logic has some property $Q$. This procedure is often called induction on the number of connectives in a formula.
Let $Q$ be a property of formulas. To show that every formula $A$ of propositional logic has property $Q$, it suffices to prove the following:
Let $S(n)$ say: Every formula with $n$ occurances of the logical connectives $\neg$, $\lor$, $\land$, $\rightarrow$ and $\leftrightarrow$ has property $Q$. We use complete induction to show that $S(n)$ holds for all $n \geq 0$. Since every formula has $n$ connectives for some $n \geq 0$, it follows that every formula has propery $Q$, as required.
Beginning step $S(0)$ states that every formula with no connectives has property $Q$. A formula with no connectives is a propositional variable, and each propositional variable has property $Q$ by (1)
Induction step Let $n \geq 0$ and assume that $S(0), \space S(1), \space \dots, \space S(n)$ all hold. $S(n+1)$ states that every formula $A$ with $n+1$ connectives has property $Q$. There are five cases: $A$ is $\neg B$, $(B \lor C)$, $(B \land C)$, $(B \rightarrow C)$ and $(B \leftrightarrow C)$. Consider the case in which $A$ is $(B \lor C)$. Both $B$ and $C$ have fewer than $n+1$ connectives, so by the induction hypotheses $S(0), \space S(1), \space \dots, \space S(n)$, it follows that both $B$ and $C$ have property $Q$. Now apply (3) to conclude that $(B \lor C)$ has property $Q$. The remaining four cases, namely that $A$ is $\neg B$, $(B \land C)$, $(B \rightarrow C)$ or $(B \leftrightarrow C)$, are similar and left to the reader.
In a proof by induction on formulas. (1) corresponds to the beginning step of an induction proof, and (2) & (3) correspond to the induction step. In (2) & (3), the assumption that $B$ and $C$ have property $Q$ is the induction hypothesis.
We show that each formula of propositional logic has the same number of left parentheses as right parentheses. Given a formula $A$, let $$L(A) = \text{# of left parentheses in} \space A$$ $$R(A) = \text{# of right parentheses in} \space A$$
We use induction on formulas to show that $L(A) = R(A)$ for each formula $A$. First of all, $L(p) = 0 = R(p)$ for any propositional variable $p$. Now suppose that $A$ is $(B \lor C)$. By induction hypothesis, $L(B) = R(B)$ and $L(C) = R(C)$. Moreover, $$L((B \lor C)) = L(B) + L(C) + 1$$ $$R((B \lor C)) = R(B) + R(C) + 1$$
hence $L(A) = R(A)$, as required. The case in which $A$ is $\neg B$, $(B \land C)$, $(B \rightarrow C)$, or $(B \leftrightarrow C)$ are similar and are left to the reader.
1. Use induction to prove De Moivre's Theorem which states that $(\cos(\theta) + i \sin(\theta))^n = \cos(n \theta) + i \sin(n \theta)$.
2. The Fibonnaci numbers are recursively defined: $$ \begin{cases} F_0 & = F_1 = 0 \\ F_{n+1} & = F_n + F_{n-1} \quad \forall n \geq 1 \end{cases} $$
Thus, the first few numbers are $1, \space 1, \space 2, \space 3, \space 5, \space 8, \space 13, \space \dots$
Let $\phi = \frac{1+\sqrt{5}}{2}$ and $\psi = \frac{1-\sqrt{5}}{2} = \overline{\phi}$
2.1. Show that $\phi^2 = 1 + \phi$ and $\psi^2 = 1 + \psi$
2.2. Use induction to show that $$F_n = \frac{\phi^{n+1} - \psi^{n+1}}{\sqrt{5}} \quad \forall n \geq 0$$
3. Derive complete induction from induction.
4. Use complete induction to prove the well-ordering principle.
5. Use the well-ordering principle to prove induction.
We begin with two basic properties of propositions: (1) Every simple proposition (e.g. "Snow is white") is either true or false but not both; in other words, every simple proposition has a unique truth value. (2) A proposition built up from simple propositions using connectives (e.g. "If it snows, then we will not have a picnic") is either true or false but not both; this unique truth value depends on the connectives used and the the truth value of the simple propositions that make up the proposition.
Actually, we are more interested in the formulas of propositional logic than in propositions, but our approach is motivated by (1) and (2). Select two distinct symbols $T$ and $F$, called truth and false. Each propositional variable has two possible truth values, namely $T$ or $F$. Informally, $T$ stands for true, $F$ stands for false, This step is based on (1). To each connective we assign a function called its truth function; these truth functions are used to asign truth values to formulas. This step is based on (2). We will begin with a general discussion of truth functions.
An $n$-ary truth function is a function $H: \{ T, F \} \rightarrow \{ T, F \}$
We are primarily interested in $1$-ary and $2$-ary truth functions. A truth table is simply a tabular description of a truth function. More generally, truth tables are used to display calculations with truth functions.
Define $H: \{ T, F \} \rightarrow \{ T, F \}$ by $H(T,T) = H(T,F) = T$ and $H(F,T) = H(F,F) = F$; $H$ is a $2$-ary truth function with the following truth table:
| $T$ | $T$ | $T$ |
| $T$ | $F$ | $T$ |
| $F$ | $T$ | F |
| $F$ | $F$ | F |
The first two columns systematically list all elements of the domain $\{T, F\}^2$ of $H$; the third column gives the value of $H$ at each given $2$-tuple.
We now assign truth functions to each of the five connectives. In each case, the truth table description is given first.
Negation (Not): truth function denoted by $H_{\neg}$
| $A$ | $\neg A$ |
| $T$ | $F$ |
| $F$ | $T$ |
$$H_{\neg} (T) = F \quad \text{&} \quad H_{\neg} (F) = T$$
Informally, $\neg A$ is false when $A$ is true and vice versa. The column headings $A$ and $\neg A$ are not an official part of the truth table; rather, their purpose is to emphasisze or highlight the effect of the truth function on a formula.
Conjunction (And): turth function denoted by $H_{\land}$
| $A$ | $B$ | $A \land B$ |
| $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ |
| $F$ | $T$ | $F$ |
| $F$ | $F$ | $F$ |
$$H_{\land} (T, T) = T$$ $$H_{\land} (T, F) = H_{\land} (F, T) = H_{\land} (F, F) = F$$
Informally, the only time $A \land B$ is true, is when in the case in which both $A$ and $B$ are true. This is the commonly accepted use of and.
Disjunction (Or): turth function denoted by $H_{\lor}$
| $A$ | $B$ | $A \lor B$ |
| $T$ | $T$ | $T$ |
| $T$ | $F$ | $T$ |
| $F$ | $T$ | $T$ |
| $F$ | $F$ | $F$ |
$$H_{\lor} (T, T) = H_{\lor} (T, F) = H_{\lor} (F, T) = T$$ $$H_{\lor} (F, F) = F$$
Informally, the only time $A \lor B$ is false, is when both $A$ and $B$ are false. This is the commonly accepted use of or in mathematics and corresponds to the inclusive or in English.
Conditional (if ... then ... or implies): turth function denoted by $H_{\rightarrow}$
| $A$ | $B$ | $A \rightarrow B$ |
| $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ |
| $F$ | $T$ | $T$ |
| $F$ | $F$ | $T$ |
$$H_{\rightarrow} (T, T) = H_{\rightarrow} (F, T) = H_{\rightarrow} (F, F) = T$$ $$H_{\rightarrow} (T, F) = F$$
Informally, the only time $A \rightarrow B$ is false, is when $A$ is true but $B$ is false. The choice of the "proper" truth function for the conditional is not as straightforward as in the previous cases. The connective if ... then ... is used in a wider variety of ways in everyday discourse. There is, however, a common core to all of these meanings; namely, "if $A$, then $B$" is false whenever the antecedent $A$ is true but the consequent $B$ is false. This corresponds to row 2 of the truth table for $\rightarrow$ (disregard the column headings $A$, $B$, $A \rightarrow B$). One must still choose a truth value for the other three cases (row 1, 3 & 4), and $T$ is chosen for each case. This choice reflects the use of "if ... then ... " in mathematics. For a mathematician, a statment of the form if $***$ the $+++$ is true except in the one case in which the hypothesis $***$ is true but the conclusion $+++$ is false. A mathematician, confronted with a statement of the form if $***$ the $+++$, proceeds as follows: Assume $***$ is true; prove $+++$ must also be true. This mathematical proof shows that in the case in which the antecedent is true, it is row 1 and not row 2 that applies; the mathematician may safely and conveniently ignore the case in which the antecedent is false (rows 3 & 4).
The conditional $\rightarrow$ is sometimes referred to as material implication or truth-functional implication. There are uses of if ... then ... in ordinary discourse that are not truth-functional; consequently, we cannot expect to find a truth function that completely captures this connective. But we can say that the truth table for $\rightarrow$ has three properties; (1) It is the best truth-functional approximation of if ... then ... ; (2) it captures the use of if ... then ... in mathematics. For a further discussion of these ideas, see the book If P then Q: Conditionals and the Foundations of Reasoning by David Sanford.
Given rows 1 and 2 of the truth table for the conditional, there are three other ways in which one could assign a truth value to $A \rightarrow B$ in rows 3 and 4. But these choices give conjunction or biconditional, or else repeat the truth balue of $B$.
Biconditional (... if and only if ... ): turth function denoted by $H_{\leftrightarrow}$
| $A$ | $B$ | $A \leftrightarrow B$ |
| $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ |
| $F$ | $T$ | $F$ |
| $F$ | $F$ | $T$ |
$$H_{\leftrightarrow} (T, T) = H_{\leftrightarrow} (F, F) = T$$ $$H_{\leftrightarrow} (T, F) = H_{\leftrightarrow} (F, T) = F$$
Informally, $A \leftrightarrow B$ is true whenever $A$ and $B$ have the same truth value and false whenever $A$ and $B$ have opposite truth values.
Now let us show how truth functions are used. Let $A$ be a formula, and assume that the propositional variables that occur in $A$ are among $p_1, p_2, \dots p_n$. Assign truth values (either $T$ or $F$) to each of the propositional variables $p_1, p_2, \dots, p_n$. Then $A$ has a truth value that can be calculated using the truth functions $H_{\neg}$, $H_{\lor}$, $H_{\land}$, $H_{\rightarrow}$, $H_{\leftrightarrow}$. This truth value for $A$ is unique and can be computed in a mechanical way. We illustrate with an example.
The formula $(p \rightarrow q) \leftrightarrow \neg (p \land \neg q)$ has truth value $T$ for every possible assignment of truth values to the propositional variables $p$ and $q$. The table below is used to calculate the truth value of $(p \rightarrow q) \leftrightarrow \neg (p \land \neg q)$ for various assignments of truth values to $p$ and $q$. Note that column 1 and 2 systematically list all possible truth assignments to the propositional variables $p$ and $q$ and column 7 gives the corresponding truth value of $(p \rightarrow q) \leftrightarrow \neg (p \land \neg q)$. Columns 3-6 are intermediate calculations; for example, column 3, with heading $p \rightarrow q$, is obtained using the truth function $H_{\neg}$
| $p$ | $q$ | $p \leftrightarrow q$ | $\neg q$ | $p \land \neg q$ | $\neg (p \land \neg q)$ | $(p \rightarrow q) \leftrightarrow \neg (p \land \neg q)$ |
| $T$ | $T$ | $T$ | $F$ | $F$ | $T$ | $T$ |
| $T$ | $F$ | $F$ | $T$ | $T$ | $F$ | $T$ |
| $F$ | $T$ | $T$ | $F$ | $F$ | $T$ | $T$ |
| $F$ | $F$ | $T$ | $T$ | $F$ | $T$ | $T$ |