MTH 110: Discrete Mathematics

A Comprehensive Overview

e-jja

Ryerson University
 Preface
Welcome students, this is going to be a written guide from the perspective of a student. From this, you
will be able to learn the basics of the course. This was primarily done to improve my writing while trying
to create something useful. I may never use these notes again, but they are really pretty. Please follow
along with these notes, and mark any corrections as I am only human.

1
Chapter 2.1
Definition: A statement is anything that is True or False

This can be simple statements such as:

• The sky is blue

• 3·2=1

Notice the statement above does not need to be correct, but it has to have a defined state of true or false.
By this logic, we know that any expressions such as 2x + 1 = 4 are not statements as they are true for
some values of x and are false for others. Similarly, any question is not a statement as we cannot answer
it with true or false.

The following bellow are not statements:

• X is greater than Y

• He is not a student

• Was her name Sally?

A compound statement is constructed with multiple statements joined by operators such as “not”, “and”,
“or”, “if then”. In order to simply logic, we use variables like p, q, and r to represent statements. This is
useful for compound statements as we are able to break up the problems into smaller pieces.

Definition: The negation of a statement p; denoted as ¬p; is the logical compliment of p.

In other words if p is true, then ¬p is false. If you have use logic gates, it is similar to a not gate.

p ¬p
T F
F T

Definition: The conjunction of p and q; denoted by p ∧ q; is True if and only if both p and q are True.

In other words, it’s similar to an and gate. If either p or q is false or both are false then p ∧ q is false.
Remember, in the English language, “but” means “and”. For example, Tom is a student but he is not
smart.

p q p∧q
T T T
T F F
F T F
F F F

2
For example, we have already seen conjunctions in math:
a≤x≤b means a ≤ x and x ≤ b
But this is not a statement since we said that statements cannot have variables.

Definition: The disjunction of p and q; denoted by p ∨ q; is True if and only if both p and q are False.

A disjunction is also known as inclusive or. This makes sense, as the output is false if p or q is true, or
both.
p q p∨q
T T T
T F T
F T T
F F F

Definition: The conditional statement of q by p; denoted p =⇒ q; is False iff p is True and q is False.

Notice that the phase “if and only if” is shortened to iff. In the conditional statement p =⇒ q, we refer
to p as the hypothesis and q as the conclusion. Notice that if you have a False hypothesis, your conclusion
True or False, will always be true. But if your hypothesis is True, then your conclusion has to be True.

p q p =⇒ q
T T T
T F F
F T T
F F T

Now that we have developed a few basic ways to speak mathematically, we will try to focus our attention
on finding the truth tables for two statements.
(p ∨ q) ∧ ¬(p ∧ q)
First set up the input statements and their various states and solve the statement in pieces.

p q p∧q ¬(p ∧ q) p∨q (p ∨ q) ∧ ¬(p ∧ q)

T T T F T F
T F F T T T
F T F T T T
F F F T F F

The statement above is commonly known as exclusive or, denoted by p ⊕ q

An important note to keep in mind is the order of operations: brackets, negation, conjunction, disjunction,
conditional. In a more simple manner, if we think of logic gates it is: brackets (), not ¬, and ∧, or ∨,
implies =⇒ .

3
 (p ∧ q) ∨ (¬r)
Notice for this we have 3 inputs. Therefore, we known that there will be a total of 23 different combinations
in our truth table.
p q r p∧q ¬r (p ∧ q) ∨ (¬r)
T T T T F T
F T T F F F
T F T F F F
F F T F F F
T T F T T T
F T F F T T
T F F F T T
F F F F T T

Definition: Two statements are logically equivalent if their truth tables match on input and output.

¬(¬p) and p
p ¬p ¬(¬p) p
T F T T
F T F F
Notice that the columns are identical for ¬(¬p) and p. Therefore, ¬(¬p) ≡ p. The triple line equal sign is
use to show logical equivalence.

We can apply our understanding logical equivalence to show that, ¬(p ∨ q) ≡ ¬p ∧ ¬q

p q ¬(p ∨ q) ¬p ∧ ¬q
T T F F
T F F F
F T F F
F F T T

Therefore we see in the truth table that the columns are identical for ¬(p ∨ q) and ¬p ∧ ¬q. Notice, this
is the use of DeMorgan’s Law,“
¬(p ∨ q) ≡ ¬p ∧ ¬q

Definition: DeMorgan’s Law

• ¬(p ∧ q) ≡ ¬p ∨ ¬q

• ¬(p ∨ q) ≡ ¬p ∧ ¬q

4
For DeMorgan’s Law, it’s easier to think of negation acting as a linear operator, and it returns the inverse
of any operator. If L is a linear operator, then L(x + y) = Lx + Ly. Similarly, if L was a linear operator
which returns an inverse operator, L(x + y) = Lx − Ly.

This is going to be a very important logical equivalence, show that p =⇒ q ≡ ¬p ∨ q

p q ¬p p =⇒ q ¬p ∨ q
T T F T T
T F F F F
F T T T T
F F T T T

Therefore, we have shown p =⇒ q ≡ ¬p ∨ q. This logical equivalence allows us to switch between the two
compound statements without restriction.

Definition: A tautology is a statement that is always True regardless of truth table input. Represented
by t.
Simple example of tautological statements is p ∨ ¬p.

p ¬p p ∨ ¬p
T F T
F T T

On the other hand we have the opposite of a tautology.

Definition: A contradiction is a statement which is always False regardless of truth table input. Rep-
resented by c.
Simple example of a contradictory statement is p ∧ ¬p

p ¬p p ∧ ¬p
T F F
F T F

Some useful facts about tautology and contradiction,

p t p∧t p∨t p c p∧c p∨c

T T T T T F F T
F T F T F F F F

From this, we find p ∧ t ≡ p, p ∧ c ≡ c, p ∨ t ≡ t, and p ∨ c ≡ p. There are more logical equivalences which
are commonly used, they are tabulated on the following page.

5
Given any statement variables p, q, r, a tautology t and a contradiction c, the following logical equivalences
hold,

Commutative Laws p∨q ≡q∨p p∧q ≡q∧p

Associative Laws (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
Distributive laws p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Identity Laws p∨t≡p p∧c≡p
Negation Laws p ∨ ¬p ≡ t p ∧ ¬p ≡ c
Double Negative Law ¬(¬p) ≡ p
Idempotent Laws p∧p≡p p∨p≡p
Universal Bound Laws p∨t≡t p∧c≡c
De Morgan’s Laws ¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q
Absorption Laws p ∧ (q ∨ r) ≡ p p ∨ (q ∧ r) ≡ p
Negations of t and c ¬t ≡ c ¬c ≡ t

An important equivalence is the absorption law, p ∨ (p ∧ q) ≡ p.

p ∨ (p ∧ q)
(p ∨ p) ∧ (p ∨ q)
p ∧ (p ∨ q)
p ∧ (p ∨ q) ≡ p ∨ (p ∧ q)

We applied the distributive law which will be shown later in order to rearrange the statement. Using a
truth table we can show the absorption equivalence is true,

p q p∧q p ∨ (p ∧ q)
T T T T
T F T T
F T T F
F F F F

Therefore, by logical equivalence we can see p ∨ (p ∧ q) ≡ p ∧ (p ∨ q) ≡ p

Now we can go further to show, p =⇒ (q ∨ r) ≡ (p =⇒ q) ∨ (p =⇒ r). But before we do recall that,

p =⇒ q ≡ ¬p ∧ q.

p =⇒ (q ∨ r) ≡ (p =⇒ q) ∨ (p =⇒ r)
¬p ∧ (q ∨ r) ≡
(¬p ∧ q) ∨ (¬p ∧ r) ≡
(p =⇒ q) ∨ (p =⇒ r) ≡

Write the negation for the following statement, −2 < x < 7.

¬(−2 < x and x < 7) ≡ −2 ≥ x or x ≥ 7

6
Verify the following logical equivalence,

¬(p ∨ ¬q) ∨ (¬p ∧ ¬q) ≡ ¬p

Using the left hand side since it is easier to expand.

(¬p ∧ q) ∨ (¬p ∧ ¬q) ≡ ¬p

((¬p ∧ q) ∨ ¬p) ∧ ((¬p ∧ q) ∨ ¬q) ≡
¬p ∧ (¬q ∨ (¬p ∧ q)) ≡
¬p ∧ ((¬q ∨ ¬p) ∧ (¬q ∨ q)) ≡
¬p ∧ ((¬q ∨ ¬p) ∧ t) ≡
¬p ∧ (¬q ∨ ¬p) ≡
¬p ≡ ¬p

Therefore, we have shown they are equivalent. Now we can introduce the idea of contrapositive, converse,
and inverse of a statement.

Given a conditional statement p =⇒ q

• The contrapositive of p =⇒ q is ¬q =⇒ ¬p

• The converse of p =⇒ q is q =⇒ p

• The inverse of p =⇒ q is ¬p =⇒ ¬q

Things to remember,

• A conditional statement and it’s contrapositive statement are logically equivalent.

p =⇒ q ≡ ¬q =⇒ ¬p

• A conditional statement is not logically equivalent to it’s converse or inverse.

p =⇒ q 6≡ q =⇒ p ≡ ¬p =⇒ ¬q

• The converse and inverse of a statement is logically equivalent.

q =⇒ p ≡ ¬p =⇒ ¬q

As an additional note, you must remember that the negation of a conditional statement cannot begin with
an “if”

¬(p =⇒ q) = ¬(¬p ∨ q) = p ∧ ¬q

In words, a negation of a conditional statement would be:

• p =⇒ q : if my car is in the shop, then I can’t go to school

• ¬(p =⇒ q) ≡ p ∧ ¬q : my car is in the repair shop, and I can go to school.