1

1.1 Statements

Notation

• $\N$ - Natural numbers ($1, 2, 3, 4, \dots$), with zero: ($\Z_0$)
• $\Z$ - ints
• $\mathbb{Q}$ - Rational
• $\R$ - Real
• $\forall$ - for all
• $\exists$ - there exists

Definition

An axiom is a mathematical truth that we accept without without question

Definition

A statement (or proposition) is a sentence that is either true or false (not both)

1.2 Implications

Definition

Statements that can be symbolised as a single letter are called primitive propositions. A symbol $\circ$ that can be put between two primitive propositions is called a connective. A statement constructed from other statements using connectives is a called a compound statement.

Definition

Let $p$ and $q$ be primitive propositions. The compound statement $p \implies q$ is called an implication or an if-then statement.

$p$ is "hypothesis" or "sufficient condition"
$q$ is "conclusion" or "necessary condition"

The implication is false only when the hypothesis is true and the conclusion is false

Definition

the converse of $p \implies q$ is $q \implies p$

Truth table of $p \implies q$

When does an implication and its converse have the same truth value?

When both PPs have the same true value

Definition

let $p$ and $q$ be PPs. The compound statement $p \iff q$ ($p$ iff $q$) and is true exactly when $p$ and $q$ have the same truth values. This is called a biconditional statement.

Proposition

let $p$ and $q$ be primitive propositions. Then $p \iff q$ is true iff the implications $p \implies q$ and $q \implies p$ are true.

Sketch of Proof

• Assume $p \iff q$ is true. Prove $p \implies q$ and $q \implies p$ are both true
• Assume both $p \implies q$ and $q \implies p$ are true. Prove $p \iff q$ is true

Proof

Assume $p \iff q$ is true. Then by definition, $p$ and $q$ have the same truth values, thus there are two cases:

1. Both $p$ and $q$ are true. Therefore, $p \implies q$ and $q \implies p$ are both true by definition.
2. Both $p$ and $q$ are false. Therefore $p \implies q$ and $q \implies p$ are both true by definition. Since in all possible cases, both implications are true, we have shown if $p \iff q$ is true, then $p \implies q$ and $q \implies p$.

Now, assume both $p \implies q$ and $q \implies p$ are true. SFAC, $p$ and $q$ have different truth values. Then, there are two cases.

1. If $p$ is true and $q$ is false, $p \implies q$ is false. Contradiction.
2. If $p$ is false and $q$ is true, $q \implies p$ is false. Contradiction. Thus, $p$ and $q$ have the same truth values, and $p \iff q$ is true.

Then, we have shown if $p \implies q$ and $q \implies p$ are true, then $p \iff q$ is true.

Therefore, $p \iff q$ is true iff $p \implies q$ and $q \implies p$ are true.
$\square$

1.3 Conjunction, Disjunction, and Negation

Definition (Conjunction, Disjunction, Negation)

Let $p$ and $q$ be statements.

1. Conjunction: $p \land q$ - reads "P AND Q" and is true iff $p$, $q$ are true.
2. Disjunction: $p \lor q$ - reads "P OR Q" and is true iff at least one one of $p$, $q$ is true.
3. Negation: $\neg p$ - reads "NOT P" and has the opposite truth value of $p$.

$p$	$q$	$p \land q$	$p \lor q$	$\neg p$
F	F	F	F	T
F	T	F	T	T
T	F	F	T	F
T	T	T	T	F

Example

use a T.T. to show $p \iff q \equiv (p \implies q) \land (q \implies p)$

$p$	$q$	$p \implies q$	$q \implies p$	$(p \implies q) \land (q \implies p)$	$q \iff p$
F	F	T	T	T	T
F	T	T	F	F	F
T	F	F	T	F	F
T	T	T	T	T	T

Switch diagrams:

• $p \land q$: two switches in series
• $p \lor q$: two switches in parallel

Theorem (1.20 in text)

let $\circ$ be a connective and $p$, $q$ be primitive propositions. Then, $p \circ q$ can be represented as a disjunction(s) of conjunctions of the statements $p$, $q$, $\neg p$, $\neg q$.

$p$	$q$	$\neg p$	$\neg q$	$p \land q$	$p \land \neg q$	$\neg p \land q$	$\neg p \land \neg q$
F	F	T	T	F	F	F	T
F	T	T	F	F	F	T	F
T	F	F	T	F	T	F	F
T	T	F	F	T	F	F	F

Example

Consider $p \land \neg p$. It's always false.

Example

Consider $p \implies q$.

$$p \implies q \equiv (\neg p \land q) \lor (\neg p \land q) \lor (p \land q)$$

Definition

The exclusive or: $p \oplus q$ is true, iff exactly one of $p$, $q$ is true.

$p$	$q$	$p \oplus q$
F	F	F
F	T	T
T	F	T
T	T	F

Exercise: write $p \oplus q$ as disjunctions of conjunctions and prove it using a T.T.

Theorem

Boolean algebra:

1. $p \lor q \equiv q \lor p$ - Commutativity
2. $p \land q \equiv q \land p$ - Commutativity
3. $(p \lor q) \lor r \equiv p \lor (q \lor r)$ - Associativity
4. $(p \land q) \land r \equiv p \land (q \land r)$ - Associativity
5. $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$ - Distributivity
6. $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$ - Distributivity

Proof (for #6)

$p$	$q$	$r$	$q \lor r$	$p \land (q \lor r)$	$p \land q$	$p \land r$	$(p \land q) \lor (p \land r)$
F	F	F	F	F	F	F	F
F	F	T	T	F	F	F	F
F	T	F	T	F	F	F	F
F	T	T	T	F	F	F	F
T	F	F	F	F	F	F	F
T	F	T	T	T	T	T	T
T	T	F	T	T	T	F	T
T	T	T	T	T	T	T	T

1.4 Negation

$T$ - true
$F$ - false
$AT$ - always true
$AF$ - always false

$p \land T \equiv p$
$p \lor F \equiv p$
$p \land F \equiv F$
$p \lor T \equiv T$

thm: (DeMorgan's Laws)

1. $\neg(p \land q) \equiv (\neg p) \lor (\neg q)$ - DeMorgan's law
2. $\neg(p \lor q) \equiv (\neg p) \land (\neg q)$ - DeMorgan's law

Proof by truth table is trivial.

Verbal Proof:

Prove both sides are true (or false) in exactly the same cases. (use iff)

Proof

We see $\neg (p \land q)$ is false iff $p \land q$ is true. $p \land q$ is true iff both $p$, $q$ are true. $p$, $q$ are true iff $\neg p$, $\neg q$ are both false. $\neg p$, $\neg q$ are both false iff $\neg p \lor \neg q$ is false.

Thus, $\neg(p \land q)$ and $\neg p \lor \neg q$ are false in exactly the same cases and are equivalent.

Definition (Algebraic Proof)

Write one side as a disjunction of conjunctions and simplify to the other side.

Example (Algebraic Proof)

$$\begin{align} \neg (p \land q) &\equiv (\neg p \land \neg q) \lor (\neg p \land q) \lor (p \land \neg q) \\ &\equiv \left[(\neg p \land \neg q) \lor (\neg p \land q)\right] \lor (p \land \neg q) \\ &\equiv \neg p \land \left[\neg q \lor q\right] \lor (p \land \neg q) \\ &\equiv \neg p \lor (p \land \neg q) \\ &\equiv (\neg p \lor p) \land (\neg p \lor \neg q) \\ &\equiv \neg p \lor \neg q \\ \square \end{align}$$

Example

Write $p \oplus q$ as a disjunction of conjunctions and show $p \oplus q \equiv (p \lor q) \land \neg (q \land p)$

$$\begin{align} p \oplus q &\equiv (p \land \neg q) \lor (\neg p \land q) \\ &\equiv [p \lor (\neg p \land q)] \land [\neg q \lor (\neg p \land q)] \\ &\equiv [(p \lor \neg p) \land (p \lor q)] \land [(\neg q \lor \neg p) \land (\neg q \lor q)] \\ &\equiv (p \lor q) \land (\neg q \lor \neg p) \\ &\equiv (p \lor q) \land \neg (q \land p) \\ \square \end{align}$$

Proposition

$\neg(\neg p) \equiv p$

Definition

let $p$, $q$ be primitive statements. The contrapositivie of $p \implies q$ is $\neg q \implies \neg p$

Theorem

$p \implies q \equiv \neg q \implies \neg p$

Proof

$p$	$q$	$p \implies q$	$\neg p$	$\neg q$	$\neg q \implies \neg p$
F	F	T	T	T	T
F	T	T	T	F	T
T	F	F	F	T	F
T	T	T	F	F	T

Example

Write the contrapositive of: "if $a$ is even, then $ab$ is even".
cp: If $ab$ is odd, then $a$ is odd.

Theorem

$\neg (p \implies q) \equiv p \land \neg q$

Proof (verbal)

$\neg(p \implies q)$ is true iff $p \implies q$ is false. $p \implies q$ is false iff $p$ is true AND $q$ is false. $p$ is true and $q$ is false iff both $p$ and $\neg q$ are true, i.e. iff $p \land \neg q$ is true.
$\square$

Example

Disprove: if $a$ is even, then $ab$ is odd

Consider $a = 2$ ($p$ is true)
Then, let $b = 3$ $ab = 6 \neq$ odd ($q$ is false)

To disprove an implication, all we need is a counterexample.

1.5 Variables and Quantifiers

Definition (Open Sentence)

An open sentence is a sentence that includes variables which becomes a statement once the variables are replaced with objects from a given set.

Definition

let $p(x)$ be some open sentence that depends on the variable $x$. Let $S$ be a set. Then:

1. The statement: $\forall x \in S : p(x)$ reads "for all $x$ in $s$"

   • "Universal statement" and is true iff $p(x)$ holds for every elt of $S$

2. The statement: $\exists x \in S : p(x)$ reads "there exists an $x$ in $S$"

   • "Existence statement" and is true iff $p(x)$ holds for at least one elt of $S$

Example (determine if each is true or false)

1. $\forall x \in \R, x^2 \ge 0$ - false, $x = 0$ (counterexample)
2. $\forall x \in \N, x^2 \gt 0$ - true
3. $\exists x \in \mathbb{C}, x^2 = -1$ - true, $x = i$ is example
4. Every man born in Brazil became the president of Brazil - false
5. Every man born on the moon became president of moon - true

Consider $\forall x \in S, p(x) \equiv$if $x \in S$, then $p(x)$

If $S = \emptyset$, the universal is "vacuously true".

Example

Every odd number divisible by 2 is even. - vacuously true

Nested Quantifiers

Example

State true/false: $$\forall x \in [0, \infty) : \left[\exists r \in [0, \infty) : r^2 = x\right]$$ true

Theorem

Let $p(x)$ be an open sentence that depends on $x$ and let $S$ be a set.

1. $$\neg\left[\forall x \in S : p(x)\right] \equiv \exists x \in \neg p(x)$$
2. $$\neg\left[\exists x \in S : p(x)\right] \equiv \forall x \in \neg p(x)$$

Example (negate)

1. $\neg \left[ \forall x \in \mathbb{C} : x^2 \in [0, \infty) \right]$ -> $\exists x \in \mathbb{C} : x^2 \not \in [0, \infty)$
2. $\neg \left[ \exists x, y \in \R^+: xy \gt 0\infty) \right]$ -> $\forall x,y \in \R^+ : xy \le 0$
3. $\neg \left[ \forall x \in \N: \left[\exists y \in \N : \frac{x}{y} \in \N \right]\right]$ -> $\exists x \in \N : \left[\forall y \in \N : \frac{x}{y} \not \in \N \right]$

1.6 Proofs

Definition (Tautology)

A compound statement is called a tautology iff for all truth values of the primitive statements, the compound statement is true.

Definition (Absurdity)

A compound statement is called an absurdity iff for all truth values of the primitive statements, the compound statement is false.

Example

• $p \lor \neg p$: tautology
• $p \land \neg p$: absurdity

Three main proof techniques:

1. Direct Proof: "Modus Ponens"
2. Proof by Contradiction: "Reductio ad Absurdum"
3. Case distrinction - Proof by exhaustion

Direct Proof

Theorem (Rule of Inference)

$\left[p \land (p \implies q)\right] \implies q$ is a tautology

Proof (by truth table)

$p$	$q$	$p \implies q$	$p \land (p \implies q)$	$\left[p \land (p \implies q)\right] \implies q$
F	F	T	F	T
F	T	T	F	T
T	F	F	F	T
T	T	T	T	T

Example

Prove that the sum of two odd numbers is even.

Consider two odd numbers, $2n + 1$ and $2m + 1$. Then, $2n + 1 + 2m + 1 = 2n + 2m + 2 = 2(n + m + 1)$ which is divisible by $2$ and thus even.
$\square$

Rule of inference: $x$ is divisible by $2$, x is divisible by $2 \implies$even

Proof by Contradiction

Theorem (Proof by Contradiction)

$\left[p \land (p \land \neg q) \implies F\right] \implies q$

Proof

Recall: $p \implies q$ = $\neg(p \land \neg q) \equiv \neg p \lor q$

$$\begin{align} &\left[p \land \left[(p \land \neg q) \implies F\right]\right] \implies q \\ &\equiv \neg \left[p \land \left[(p \land \neg q) \implies F\right]\right] \lor q \\ &\equiv \left[\neg p \lor \neg \left[(p \land \neg q) \implies F\right]\right] \lor q \\ &\equiv \left[\neg p \lor \left[(p \land \neg q) \land T\right]\right] \lor q \\ &\equiv \left[\neg p \lor (p \land \neg q)\right] \lor q \\ &\equiv \left[(\neg p \lor p) \land (\neg p \lor \neg q)\right] \lor q \\ &\equiv \left[\neg p \lor \neg q\right] \lor q \\ &\equiv \neg p \lor \left[\neg q \lor q\right] \\ &\equiv \neg p \lor T \\ &\equiv T \implies \text{Tautology} \\ \end{align}$$

Example

Prove $\sqrt{2}$ is irrational

Proof

SFAC that $\sqrt{2}$ is a rational number. Then $\exists n, d \in \Z : \sqrt{2} = \frac{n}{d}$, such that, $n$ and $d$ have no common factors. Then:

$$\begin{align} \sqrt{2}d &= n \\ 2d^2 &= n^2 \implies \end{align}$$

$2$ is a factor of $n^2$ and since $2$ is prime, 2 is a factor of $n$

$$\begin{align} &\implies \exists k \in \Z : n = 2k \\ &\implies n^2 = (2k)^2 = 4k^2 \\ &\implies d^2 = 2k^2 \implies \end{align}$$

$2$ is a factor of $d^2$ and since $2$ is prime, 2 is a factor of $d$

However, we claimed that $n$ and $d$ have no common factors. Contradiction. Thus, $\sqrt{2}$ is irrational.
$\square$

Proof by Case Distinction

Theorem (Proof by Case Distinction)

The statement: $\left[p \land (A \lor B) \land \left[(p\land A) \implies q\right] \land \left[(p\land B) \implies q\right]\right] \implies q$

(Prove with a truth table as an exercise)

Note

To prove a universal statement, choose an arbitrary but fixed element $x \in S$, and show $p(x)$ is true.

Example

Prove $\forall x \in \R, x + |x - 7| \ge 7$

Let $x \in \R$ be arbitrary but fixed. There are two distinct cases, 1: $x \ge 7$ and 2: $x \lt 7$

$$\begin{align} x + |x - 7| &= x + x - 7 \\ &= 2x - 7 \ge 2(7) - 7 = 7 \end{align}$$

Thus, $x + |x - 7| \ge x$

$$\begin{align} x + |x - 7| &= x - (x - 7) \\ &= 7 \ge 7 \end{align}$$

Thus, $x + |x - 7| \ge 7$

Since the inequality holds in all cases, the statement is proven.
$\square$

Theorem (Biconditional Law)

$p \iff q \equiv (p \implies q) \land (q \implies p)$

Exercise: Prove by truth table

Example

A natural number $x$ is even and prime iff $x = 2$

Proof

($\implies$) Assume $x \in \N$ is even and prime. Since $2$ is the only even prime, $x = 2$

($\impliedby$) Assume $x = 2$. Then $x$ is divisible by $2 \implies$even and $2$ is prime.

Thus, the biconditional holds.
$\square$

Proof by Contrapositive

Theorem (Proof by Contrapositive)

$p \implies q \equiv \neg q \implies \neg p$

1.7 Using Tautologies to Analyse Arguments

To show an argument is invalid, we must show that it is possible for all assumptions to be true and for the conclusion to be still be false.

Example

Consider the following argument:

If the floor is dirty, then I must mop. ($p \implies q$)
The floor is dirty. ($p$)
I mop. ($q$)

($p \implies q$ and $q$ are the hypothesis, $q$ is conclusion)

Is this a valid argument?

$p$	$q$	$p \implies q$	$p \land (p \implies q)$	$[p \land (p \implies q)] \implies q$
F	F	T	F	T
F	T	T	F	T
T	F	F	F	T
T	T	T	T	T

Example

Consider the argument

If the (Doctor fights the Daleks)[$D$], (Earth will be safe.)[$E$]
If (he finds Rose)[$R$] and (gets into the TARDIS)[$S$], then he will fight the Daleks.
He found rose. ($R$)
Earth is safe. ($E$)

$[[D \implies E] \land [[R \land S] \implies D] \land R] \implies E$

Argument: $[R \land (D \implies E) \land ([R \land S] \implies D)] \implies E$

R	S	D	E	$D \implies E$	$R\land S$	$(R\land S)\implies D$	$R \land (D \implies E) \land ((R\land S) \implies D)$	$H \implies E$
F	F	F	F	T	F	T	F	T
F	F	F	T	T	F	T	F	T
F	F	T	F	F	F	T	F	T
F	F	T	T	T	F	T	F	T
F	T	F	F	T	F	T	F	T
F	T	F	T	T	F	T	F	T
F	T	T	F	F	F	T	F	T
F	T	T	T	T	F	T	F	T
T	F	F	F	T	F	T	T	F
T	F	F	T	T	F	T	T	T
T	F	T	F	F	F	T	F	T
T	F	T	T	T	T	T	T	T
T	T	F	F	T	T	F	F	T
T	T	F	T	T	T	F	F	T
T	T	T	F	F	T	T	F	T
T	T	T	T	T	T	T	T	T

1.8 Russel's Paradox

Consider the following three assumptions:

1. Sets and objects have been defined and can be identified using their definition
2. For any object and any set, we can determine if the object is in the set. If an object $x$ is in a set $A$, we write $x \in A$.
3. Sets $A$ can be formed by specifying their elements with o[en sentences $p(x)$ so that $x \in A \iff p(x)$ we write $A = \{x : p(x)\}$.

The Problem

Consider the set $B$ whose elements are the sets which do not contain themselves

$$B = \{ A : A \text{ is a set} \land A \not\in A \}$$

Is $B \in B$?

Suppose $B \in B$, then $B$ is a set and $B \not\in B$. Contradiction.
Thus, $B \not\in B$ but then, $B$ does not contain itself as an element and $B \in B$.

Therefore, $B \in B \land B \not\in B \implies$Absurdity