Breaking down statements

Many mathematical statements contain predicates that are rather complicated. Consider the following examples:

1. There exists an integer \(x\) such that \(x\) is odd and \(x\) is the cube of an integer.

2. For every natural number \(x\), either \(x\) is a prime power or \(x\) has two distinct prime factors.

In the first example, the predicate “\(x\) is odd and \(x\) is the cube of an integer”, which we call \(P(x)\), can be broken down into two smaller pieces:

• “\(x\) is odd”, which we call \(Q(x)\)

• “\(x\) is the cube of an integer”, which we call \(R(x)\)

Then \(P(x)\) holds whenever both \(Q(x)\) and \(R(x)\) hold and vice versa.

In the second example, the predicate “either \(x\) is a prime power or \(x\) has two distinct prime factors” can also be broken down into two smaller pieces:

• “\(x\) is a prime power”, which we call \(Q(x)\)

• “\(x\) has two distinct prime factors”, which we call \(R(x)\)

This time, however, \(P(x)\) holds whenever either \(Q(x)\) or \(R(x)\) holds and vice versa.

For every integer \(n\), \(n \equiv 3 (\text{ mod } 4)\) implies that \(n\) is not the square of an integer.

To study complex predicates, we first introduce the language of propositional logic (a.k.a. sentential logic) that allow us to look at the truth and falsehood of sentences built up using logical connectives in abstract terms.

Propositional logic

Propositional logic deals only with propositions (also called sentences or statements) that are either true or false.

Propositions are formed inductively using a number of rules. (In other words, not everything that we can write down can be a proposition.)

Before we look at the rules for constructing valid propositions, we need to spell out the ingredients. There are three types of symbols that we can use:

1. Propositional variable symbols; usually capital letters of the English alphabet, with or without natural number subscripts (e.g. \(A\), \(B\), \(A_0\), \(A_1\), etc.)

2. Logical connectives: \(\wedge\), \(\vee\), \(\Rightarrow\), \(\Leftrightarrow\), \(\neg\),

3. Auxiliary symbols: \((\), \()\), \(\top\), \(\bot\),

A proposition (or a sentence) can be defined inductively as follows:

1. Every propositional variable symbol is a propostion (i.e. \(A\) is a proposition).

2. \(\top\) and \(\bot\) are propositions.

3. If \(\phi\) and \(\psi\) are propositions, then so are \((\phi \wedge \psi)\), \((\phi \vee \psi)\), \((\phi \Rightarrow \psi)\), \((\phi \Leftrightarrow \psi)\).

4. If \(\phi\) is a proposition, then so is \((\neg \phi)\).

No other arrangements of the symbols is a proposition.

For example, \(((A \wedge B) \vee (\neg C))\) is a proposition. To see this, note that \(A\), \(B\), \(C\) are propositional variable symbols and so they are all propositions. Then by the second rule above, \((A \wedge B)\) is a proposition. By the third rule above, \((\neg C)\) is a proposiiton. Finally, applying the second rule to \((A \wedge B)\) and \((\neg C)\) gives us the proposition \(((A \wedge B) \vee (\neg C))\).

Exercises

For each of the following, determine if it is a proposition.

1. \((A \wedge \vee B)\)

2. \(((\neg A) \wedge A)\)

3. \(((\neg A) \wedge (B \Rightarrow C))\)

4. \((A \Leftrightarrow (\neg A)\)

Remark

The logical connectives have names.

Note. The phrase “if and only if” is often abbreviated as “iff”.

Truth tables

Loosely speaking, propositional logic is the study of when propositions are true or false. In order to make this possible, we need to be know how the logical connectives affect the truth values. Using “1” to denote true and ”0” to denote false, the following tables defines the effects of the logical connectives:

In plain English, \((A \wedge B)\) is true if both \(A\) and \(B\) are true and is false otherwise.

In plain English, \((A \vee B)\) is false if both \(A\) and \(B\) are false and is true otherwise.

In plain English, the only way \((A \Rightarrow B)\) can be false is when \(B\) is false but \(A\) is true. What this means is that when we read \((A \Rightarrow B)\) as “\(A\) implies \(B\)”, it does not really correspond to our notion of “if \(A\) then \(B\)” because in everyday usage of “if \(A\) then \(B\)”, the case when \(B\) holds but \(A\) doesn't seems a bit weird. For example, “if \(1 \neq 2\), then \(1 \geq 0\)” is such a sentence. As a result, one should simply memorize this table and not try to interpret \((A \Rightarrow B)\) as “if \(A\) then \(B\)” no matter how tempting.

\(\top\) always evaluates to 1 and \(\bot\) always evaluates to 0. Thus, \((A \vee \top) = 1\) and \((A \wedge \bot) = 0\) no matter what \(A\) is.

Remarks

1. Note that some books use “T” for true and “F” for false. Also, some books use “\(\sim\)” instead of “\(\neg\)” for negation.

2. Why do we need \(\top\) and \(\bot\) when they are always \(1\) and \(0\), respectively? One reason is to avoid using the symbols \(1\) and \(0\) for both values and propositions. This is a subtle point that logicians like to observe.

Examples

The truth table for \(((\neg A) \Rightarrow (B \wedge C))\) is

Exercises

For each of the following propositions, obtain its truth table:

1. \((A\vee (\neg B))\)

2. \(((A\wedge B)\vee C)\)