11/14/2020

Let’s get started with...

Logic!

Fall 2020 CSE 173 - Discrete Mathematics 1

Let’s play with logic...

 All Philosophers are immoral
 Socrates is a philosopher
 Conclusion: Therefore Socrates is immoral

 If one is crazy one drills teeth

 My dentist drills teeth
 Conclusion: Therefore my dentist is crazy

Fall 2020 CSE 173 - Discrete Mathematics 2

1
 11/14/2020

Logic
 Crucial for mathematical reasoning
 Important for program design
 Used for designing electronic circuitry

 (Propositional) Logic is a system based on

propositions.
 A proposition is a (declarative) statement that is
either true or false (not both).
 We say that the truth value of a proposition is
either true (T) or false (F).
 Corresponds to 1 and 0 in digital circuits

Fall 2020 CSE 173 - Discrete Mathematics 3

The Statement/Proposition Game

“Elephants are bigger than mice.”

Is this a statement? yes

Is this a proposition? yes

What is the truth value

of the proposition? true

Fall 2020 CSE 173 - Discrete Mathematics 4

2
 11/14/2020

The Statement/Proposition Game

“520 < 111”

Is this a statement? yes

Is this a proposition? yes

What is the truth value

of the proposition? false

Fall 2020 CSE 173 - Discrete Mathematics 5

The Statement/Proposition Game

“y > 5”

Is this a statement? yes

Is this a proposition? no

Its truth value depends on the value of y,

but this value is not specified.
We call this type of statement a
propositional function or open sentence.
sentence.

Fall 2020 CSE 173 - Discrete Mathematics 6

3
 11/14/2020

The Statement/Proposition Game

“This statement is false”

Is this a statement? yes

Is this a proposition? no

What is the truth value

of the proposition? ??

Fall 2020 CSE 173 - Discrete Mathematics 7

The Statement/Proposition Game

“Today is January 27 and 99 < 5.”

Is this a statement? yes

Is this a proposition? yes

What is the truth value

of the proposition? false

Fall 2020 CSE 173 - Discrete Mathematics 8

4
 11/14/2020

The Statement/Proposition Game

“Please do not fall asleep.”

Is this a statement? no
It’s a request.

Is this a proposition? no

Only statements can be propositions.

Fall 2020 CSE 173 - Discrete Mathematics 9

The Statement/Proposition Game

“If the moon is made of cheese,
then I will be rich.”

Is this a statement? yes

Is this a proposition? yes

What is the truth value

of the proposition? probably true

Fall 2020 CSE 173 - Discrete Mathematics 10

5
 11/14/2020

The Statement/Proposition Game

“x < y if and only if y > x.”
Is this a statement? yes
Is this a proposition? yes
… because its truth value
does not depend on
specific values of x and y.
What is the truth value
of the proposition? true

Fall 2020 CSE 173 - Discrete Mathematics 11

Combining Propositions

As we have seen in the previous examples,

one or more propositions can be combined to
form a single compound proposition.

We formalize this by denoting propositions

with letters such as p, q, r, s, and introducing
several logical operators or logical
connectives.

Fall 2020 CSE 173 - Discrete Mathematics 12

6
 11/14/2020

Logical Operators (Connectives)

We will examine the following logical operators:
 Negation (NOT, )
 Conjunction (AND, )
 Disjunction (OR, )
 Exclusive-or (XOR,  )
 Implication (if – then,  )
 Biconditional (if and only if,  )

Truth tables can be used to show how these

operators can combine propositions to compound
propositions.

Fall 2020 CSE 173 - Discrete Mathematics 13

Negation (NOT)

Unary Operator, Symbol:  or ~

P  P
true (T) false (F)
false (F) true (T)

Fall 2020 CSE 173 - Discrete Mathematics 14

7
 11/14/2020

Exercises
 P: It rained on July 4, 1983
 P: It didn’t rain on July 4, 1983

 P: All Primes are odd

 P: Some primes are not odd

 P: Some even numbers are prime

 P: No even number is prime

Fall 2020 CSE 173 - Discrete Mathematics 15

Conjunction (AND)
Binary Operator, Symbol: 
P Q P Q
T T T
T F F
F T F
F F F

Fall 2020 CSE 173 - Discrete Mathematics 16

8
 11/14/2020

Exercises
 P: It is snowing
 Q: It is dark outside
 P Q:
It is snowing and dark outside
  (P Q):
Either it is not snowing or it is dark outside

Fall 2020 CSE 173 - Discrete Mathematics 17

Disjunction (OR)
Binary Operator, Symbol: 
P Q P Q
T T T
T F T
F T T
F F F

Fall 2020 CSE 173 - Discrete Mathematics 18

9
 11/14/2020

Exercises
 P: The roof is red
 Q: The wall is white
 P  Q:
The roof is red or the wall is white (or both)

Fall 2020 CSE 173 - Discrete Mathematics 19

Exclusive Or (XOR)
Binary Operator, Symbol: 
P Q PQ
T T F
T F T
F T T
F F F

Fall 2020 CSE 173 - Discrete Mathematics 20

10
 11/14/2020

Exercises
 P: I shall sleep tonight
 Q: I shall study whole night
 P  Q:
I shall sleep tonight or I shall study whole night
(but not both)

Fall 2020 CSE 173 - Discrete Mathematics 21

Implication (if - then)

Binary Operator, Symbol: 
P Q PQ
T T T
T F F
F T T
F F T

Fall 2020 CSE 173 - Discrete Mathematics 22

11
 11/14/2020

Exercises

 P: You get an A in the class

 Q: I will give you fifty dollars
 P  Q:
If you get an A in the class, I will give you fifty dollars.

Fall 2020 CSE 173 - Discrete Mathematics 23

Conditional statement
 To understand the logic behind the truth table for the conditional statement,
consider the following statement.

 “If you get an A in the class, I will give you five bucks.”
 Let p = statement “ You get an A in the class”
 Let q = statement “ I will give you five bucks.”
 Now, if p is true (you got an A) and I give you the five bucks, the truth value of
 p q is true. The contract was satisfied and both parties fulfilled the
agreement.
 Now, suppose p is true (you got the A) and q is false (you did not get the five
bucks). You fulfilled your part of the bargain, but weren’t rewarded with the five
bucks.
 So p q is false since the contract was broken by the other party.
 Now, suppose p is false. You did not get an A but received five bucks anyway. (q
is true) No contract was broken. There was no obligation to receive 5 bucks, so
truth value of p q cannot be false, so it must be true.
 Finally, if both p and q are false, the contract was not broken. You did not receive
the A and you did not receive the 5 bucks. So p q is true in this case.

12
 11/14/2020

Variations of the conditional

 Converse: The converse of p q is
q p

 Contrapositive: The contrapositive of

p q is ┐q ┐p

Examples
 Let p = you receive 90%
 Let q = you receive an A in the course
 p q?

 If you receive 90%, then you will receive an A in the course.

 Converse: q p
 If you receive an A in the course, then you receive 90%
 Is the statement true? No. What about the student who
receives a score greater than 90? That student receives an A
but did not achieve a score of exactly 90%.

13
 11/14/2020

Example 2
 State the contrapositive in an English sentence:
 Let p = you receive 90%
 Let q = you receive an A in the course
 p q?
 If you receive 90%, then you will receive an A in the course

 ┐q ┐p
 If you don’t receive an A in the course, then you didn’t
receive 90%.
 The contrapositive is true not only for these particular
statements but for all statements , p and q.

Biconditional (if and only if)

Binary Operator, Symbol: 
P Q PQ
T T T
T F F
F T F
F F T

Fall 2020 CSE 173 - Discrete Mathematics 28

14
 11/14/2020

Statements and Operators

Statements and operators can be combined in any
way to form new statements.

P Q P Q (P)
P)(Q)
T T F F F
T F F T T
F T T F T
F F T T T

Fall 2020 CSE 173 - Discrete Mathematics 29

Statements and Operations

Statements and operators can be combined in any way
to form new statements.

P Q PQ (PQ) (P)

P)(Q)
T T T F F
T F F T T
F T F T T
F F F T T

Fall 2020 CSE 173 - Discrete Mathematics 30

15
 11/14/2020

Exercises
To take discrete mathematics, you must have
taken calculus or a course in computer science.
When you buy a new car from Acme Motor
Company, you get $2000 back in cash or a 2%
car loan.
School is closed if more than 2 feet of snow falls
or if the wind chill is below -100.

Fall 2020 CSE 173 - Discrete Mathematics 31

Exercises

• To take discrete mathematics, you must have

taken calculus or a course in computer science.
 P: take discrete mathematics
 Q: take calculus
 R: take a course in computer science

P QR

Fall 2020 CSE 173 - Discrete Mathematics 32

16
 11/14/2020

Exercises
• When you buy a new car from Acme Motor
Company, you get $2000 back in cash or a 2%
car loan.
 P: buy a car from Acme Motor Company
 Q: get $2000 cash back
 R: get a 2% car loan

P QR
Why use XOR here? – example of ambiguity of
natural languages

Fall 2020 CSE 173 - Discrete Mathematics 33

Exercises
• School is closed if more than 2 feet of snow
falls or if the wind chill is below -100.
 P: School is closed
 Q: 2 feet of snow falls
 R: wind chill is below -100

Q RP
Precedence among operators:
, , , , 

Fall 2020 CSE 173 - Discrete Mathematics 34

17
 11/14/2020

De Morgan’s Law

The statements (PQ) and (P)  (Q) are

logically equivalent

Fall 2020 CSE 173 - Discrete Mathematics 35

Equivalent Statements
P Q (PQ) (P)
P)(Q) (PQ)
Q)(P)
P)(Q)

T T F F T
T F T T T
F T T T T
F F T T T
The statements (PQ) and (P)  (Q) are logically equivalent, since they
have the same truth table, or put it in another way, (PQ) (P)  (Q)
is always true.

Fall 2020 CSE 173 - Discrete Mathematics 36

18
 11/14/2020

De Morgan’s Law

The statements (P  Q) and (P)  (Q) are

logically equivalent

Fall 2020 CSE 173 - Discrete Mathematics 37

Equivalent Statements
P Q (PQ) (P)
P)(Q) (PQ)
Q)(P)
P)(Q)

T T F F T
T F F F T
F T F F T
F F T T T
The statements (P  Q) and (P)  (Q) are logically equivalent, since they
have the same truth table, or put it in another way, (P  Q) (P)  (Q)
is always true.

Fall 2020 CSE 173 - Discrete Mathematics 38

19
 11/14/2020

Tautologies and Contradictions

A tautology is a statement that is always true.
Examples:
 R(R)
 (PQ)  (P)( Q)
A contradiction is a statement that is always false.
Examples:
 R(R)
 ((P  Q)  (P)  (Q))
The negation of any tautology is a contradiction, and the
negation of any contradiction is a tautology.

Fall 2020 CSE 173 - Discrete Mathematics 39

Equivalence
Definition: two propositional statements S1
and S2 are said to be (logically)
equivalent, denoted S1  S2 if
 They have the same truth table, or
 S1  S2 is a tautology

Equivalence can be established by

 Constructing truth tables
 Using equivalence laws

Fall 2020 CSE 173 - Discrete Mathematics 40

20
 11/14/2020

Equivalence
Equivalence laws
 Identity laws, P  T  P,
 Domination laws, P  F  F,
 Idempotent laws, P  P  P,
 Double negation law,  ( P)  P
 Commutative laws, P  Q  Q  P,
 Associative laws, P  (Q  R) (P  Q)  R,
 Distributive laws, P  (Q  R) (P  Q)  (P  R),
 De Morgan’s laws,  (PQ)  ( P)  ( Q)
 Law with implication PQPQ

Fall 2020 CSE 173 - Discrete Mathematics 41

Exercises
Show that P  Q   P  Q: by truth table
Show that (P  Q)  (P  R)  P  (Q  R): by
equivalence laws :
 Law with implication on both sides
 Distribution law on LHS

Fall 2020 CSE 173 - Discrete Mathematics 42

21
 11/14/2020

Summary, Sections 1.1, 1.2

Proposition
 Statement, Truth value,
 Proposition, Propositional symbol, Open proposition
Operators
 Define by truth tables
 Composite propositions
 Tautology and contradiction
Equivalence of propositional statements
 Definition
 Proving equivalence (by truth table or equivalence
laws)

Fall 2020 CSE 173 - Discrete Mathematics 43

Propositional Functions & Predicates

Propositional function (open sentence):
statement involving one or more variables,
e.g.: x-3 > 5.
Let us call this propositional function P(x), where P
is the predicate and x is the variable.
What is the truth value of P(2) ? false
What is the truth value of P(8) ? false
What is the truth value of P(9) ? true
When a variable is given a value, it is said to be
instantiated
Truth value depends on value of variable

Fall 2020 CSE 173 - Discrete Mathematics 44

22
 11/14/2020

Propositional Functions
Let us consider the propositional function
Q(x, y, z) defined as:
x + y = z.
Here, Q is the predicate and x, y, and z are the
variables.
What is the truth value of Q(2, 3, 5) ? true
What is the truth value of Q(0, 1, 2) ? false
What is the truth value of Q(9, -9, 0) ? true
A propositional function (predicate) becomes a
proposition when all its variables are instantiated
instantiated..

Fall 2020 CSE 173 - Discrete Mathematics 45

Propositional Functions
Other examples of propositional functions
Person(x), which is true if x is a person
Person(Socrates) = T
Person(dolly--the
Person(dolly the--sheep) = F
CSCourse(x), which is true if x is a
computer science course
CSCourse(CSE173)
CSCourse (CSE173) = T
CSCourse(MATH155) = F
How do we say
All humans are mortal
Some CS course
Fall 2020 CSE 173 - Discrete Mathematics 46

23
 11/14/2020

Universal Quantification

Let P(x) be a predicate (propositional function).

Universally quantified sentence:

For all x in the universe of discourse P(x) is true.

Using the universal quantifier :

x P(x) “for all x P(x)” or “for every x P(x)”

(Note: x P(x) is either true or false, so it is a

proposition, not a propositional function.)

Fall 2020 CSE 173 - Discrete Mathematics 47

Universal Quantification
Example: Let the universe of discourse be all people
S(x): x is a NSU student.
G(x): x is a genius.
What does x (S(x)  G(x)) mean ?
“If x is a NSU student, then x is a genius.” or
“All NSU students are geniuses.”
If the universe of discourse is all NSU students, then
the same statement can be written as
x G(x)

Fall 2020 CSE 173 - Discrete Mathematics 48

24
 11/14/2020

Universal Quantification

Another example:
Let the universe of discourse be the real numbers.
Let Q(x) be the x.1 = x
What does x Q(x) mean ?
“For every x, x.1 = x”

Is it true? yes

Is it true for the natural numbers? yes

Fall 2020 CSE 173 - Discrete Mathematics 49

Universal Quantification

Another example:
Let the universe of discourse be the real numbers.
Let P(x) be the x.0 = x
What does x P(x) mean ?
“For every x, x.0 = x”

Is it true? no

Is it true for the natural numbers? no

Fall 2020 CSE 173 - Discrete Mathematics 50

25
 11/14/2020

Universal Quantification
Another example:
Let the universe of discourse be the integers’ set.
Let Q(x) be the x is an even integer
Let R(x) be the x2 is a multiple of 4
What does x [Q(x)  R(x)] mean ?
“For every x, if x is an even integer then x2 is
multiple of 4 and if x2 is multiple of 4 then x is even”

Is it true? yes

Fall 2020 CSE 173 - Discrete Mathematics 51

Existential Quantification
Existentially quantified sentence:
There exists an x in the universe of discourse for
which P(x) is true.

Using the existential quantifier :

x P(x) “There is an x such that P(x).”
“There is at least one x such that P(x).”
“For some x P(x).”

(Note: x P(x) is either true or false, so it is a

proposition, but no propositional function.)

Fall 2020 CSE 173 - Discrete Mathematics 52

26
 11/14/2020

Existential Quantification
Example:
P(x): x is a NSU professor.
G(x): x is a genius.

What does x (P(x)  G(x)) mean ?

“There is an x such that x is a NSU professor and x

is a genius.”
or
“At least one NSU professor is a genius.”
“Some NSU professor is a genius.”

Fall 2020 CSE 173 - Discrete Mathematics 53

Existential Quantification

Another example:
Let the universe of discourse be the real numbers.
Let Q(x) be the x.1 = x
What does x Q(x) mean ?
“There exists a value of x such that, x.1 = x”

Is it true? yes

Is it true for the natural numbers? yes

Fall 2020 CSE 173 - Discrete Mathematics 54

27
 11/14/2020

Existential Quantification

Another example:
Let the universe of discourse be the real numbers.
Let P(x) be the x.0 = x
What does x P(x) mean ?
“There exists a value of x such that x, x.0 = x”

Is it true? yes

Is it true for the natural numbers? no

Fall 2020 CSE 173 - Discrete Mathematics 55

Existential Quantification

Another example:
Let the universe of discourse be the real numbers.
Let P(x) be the x2 ≥ 0
Let Q(x) be the 3.x > 10

x P(x) is it true? yes

x P(x) is it true? yes
x Q(x) is it true? no
x Q(x) is it true? yes
Fall 2020 CSE 173 - Discrete Mathematics 56

28
 11/14/2020

Quantification

Another example:
Let the universe of discourse be the real numbers.

What does xy (x + y = 320) mean ?

“For every x there exists a y so that x + y = 320.”

Is it true? yes

Is it true for the natural numbers? no

Fall 2020 CSE 173 - Discrete Mathematics 57

Quantification
Another example:
Let the universe of discourse be the real numbers.
Let P(x,y) be x > y
What does xy P(x, y) mean?
“We can find a value of x such that no matter what
the value of y, we have x >y”

Is it true? no
What does yx P(x, y) mean?
“For all y there is an x such that x > y”
Is it true? yes
Fall 2020 CSE 173 - Discrete Mathematics 58

29
 11/14/2020

Disproof by Counterexample

A counterexample to x P(x) is an object c so that

P(c) is false.

Statements such as x (P(x)  Q(x)) can be

disproved by simply providing a counterexample.

Statement: “All birds can fly.”

Disproved by counterexample: Penguin.

Fall 2020 CSE 173 - Discrete Mathematics 59

Negation

What does (x P(x)) means?

It is not the case that for all value of x, P(x) is true

That means for some value of x, P(x) is false

(x P(x)) is logically equivalent to x (P(x)).

This is de Morgan’s law for quantifiers

Fall 2020 CSE 173 - Discrete Mathematics 60

30
 11/14/2020

Negation
Let the universe of discourse be the integers.
Let Q(x) be the predicate x2 > 1
What does xQ(x) mean ?
“For every x, x2 > 1.”

Is it true? no

~xQ(x) is equivalent to x (Q(x)).

x (Q(x))  “For some x, x2 ≤ 1.”

Is it true? yes
Fall 2020 CSE 173 - Discrete Mathematics 61

Negation
What does (x P(x)) means?

It is not the case that for some x, P(x) is true

That means for all value of x, P(x) is false

(x P(x)) is logically equivalent to x (P(x)).

This is de Morgan’s law for quantifiers

Fall 2020 CSE 173 - Discrete Mathematics 62

31
 11/14/2020

Negation
Let the universe of discourse be the integers.
Let Q(x) be the predicate 2x is odd
What does xQ(x) mean ?
“For some value of x, 2x is odd”

Is it true? no

~ xQ(x) is equivalent to x (Q(x)).

“It is not the case that for some value of x, 2x is odd”
“For all values of x, 2x is not odd”
Is it true? yes
Fall 2020 CSE 173 - Discrete Mathematics 63

Negation Summary
(x P(x)) is logically equivalent to x (P(x)).

(x P(x)) is logically equivalent to x (P(x)).

Let universe of discourse all real numbers

Let P(x, y) be the predicate x.y = 1
xyP(x, y) means:
For all x there is some y such that x.y = 1
Is it true or false?
False (think about x = 0)
xyP(x, y) is equivalent to xy(P(x, y) )
For some x, no matter what value of y is x.y ≠ 1
Fall 2020 CSE 173 - Discrete Mathematics 64

32
 11/14/2020

Negation
More Examples
Not all roses are red
x (Rose(x)  Red(x))
x (Rose(x)  Red(x))

Nobody is perfect
x (Person(x)  Perfect(x))
x (Person(x)  Perfect(x))

Fall 2020 CSE 173 - Discrete Mathematics 65

Equivalency
Let universe of discourse be set of integers
E(X) be the predicate x is even
O(x) be the predicate x is odd
x[E(x)  O(x)] is true
x[E(x)
xE(x)
xE (x)  xxO(x) is also true

Thus x[P(x)
x[P(x)  Q(x)] and xP
xP(x)
(x)  x
xQ(x) are equivalent

But x[P(x)
x[P(x)  Q(x)] and xP
xP(x)
(x)  x
xQ(x) are not equivalent
Example:
x[E(x)  O(x)] and xE
x[E(x) xE(x)
(x)  xxO(x) are not equivalent

Fall 2020 CSE 173 - Discrete Mathematics 66

33
 11/14/2020

Equivalency
Let universe of discourse be set of integers

E(X) be the predicate x is even

O(x) be the predicate x is odd
x[E(x)  O(x)] is true
x[E(x)
xE(x)
xE (x)  xxO(x) is false

Thus x[P(x)
x[P(x)  Q(x)] and xP
xP(x)
(x)  x
xQ(x) are not equivalent

But x[P(x)
x[P(x)  Q(x)] and xP
xP(x)
(x)  x
xQ(x) are equivalent

Fall 2020 CSE 173 - Discrete Mathematics 67

Summary, Sections 1.3

 Propositional functions (predicates)
 Universal and existential quantifiers, and the
duality of the two
 When predicates become propositions
 All of its variables are instantiated
 All of its variables are quantified
 Nested quantifiers
 Quantifiers with negation
 Logical expressions formed by predicates,
operators, and quantifiers

Fall 2020 CSE 173 - Discrete Mathematics 68

34
 11/14/2020

Let’s proceed to…

Mathematical Reasoning

Fall 2020 CSE 173 - Discrete Mathematics 69

Valid Argument...
 All Philosophers are immoral
 Socrates is a philosopher
 Conclusion: Therefore Socrates is immoral

 If the Security Guard is guilty of the

crime, his shoes will be covered with
mud.
 Security Guard’s shoes are indeed
covered with mud.
 Conclusion: Therefore the Security
Guard is guilty
Fall 2020 CSE 173 - Discrete Mathematics 70

35
 11/14/2020

Mathematical Reasoning
We need mathematical reasoning to
 determine whether a mathematical argument is
correct or incorrect and
 construct mathematical arguments.

Mathematical reasoning is not only important for

conducting proofs and program verification, but
also for artificial intelligence systems (drawing
logical inferences from knowledge and facts).

We focus on deductive proofs

Fall 2020 CSE 173 - Discrete Mathematics 71

Terminology
An axiom is a basic assumption about mathematical
structure that needs no proof.
- Things known to be true (facts or proven theorems)
- Things believed to be true but cannot be proved

We can use a proof to demonstrate that a particular

statement is true. A proof consists of a sequence of
statements that form an argument.
The steps that connect the statements in such a
sequence are the rules of inference.
Cases of incorrect reasoning are called fallacies.

Fall 2020 CSE 173 - Discrete Mathematics 72

36
 11/14/2020

Terminology
A theorem is a statement that can be shown to be
true.

A lemma is a simple theorem used as an

intermediate result in the proof of another theorem.

A corollary is a proposition that follows directly from

a theorem that has been proved.

A conjecture is a statement whose truth value is

unknown. Once it is proven, it becomes a theorem.

Fall 2020 CSE 173 - Discrete Mathematics 73

Proofs
A theorem often has two parts
- Conditions (premises, hypotheses)
- conclusion

A correct (deductive) proof is to establish that

- If the conditions are true then the conclusion is true
- I.e., Conditions  conclusion is a tautology

Often there are missing pieces between conditions

and conclusion. Fill it by an argument
- Using conditions and axioms
- Statements in the argument connected by proper rules of
inference

Fall 2020 CSE 173 - Discrete Mathematics 74

37
 11/14/2020

Rules of Inference
Rules of inference provide the justification of the
steps used in a proof.

One important rule is called modus ponens or the

law of detachment. It is based on the tautology
(p  (p  q))  q. We write it in the following way:

p The two hypotheses p and p  q are

p q written in a column, and the conclusion
____
below a bar, where  means “therefore”.
q

Fall 2020 CSE 173 - Discrete Mathematics 75

Rules of Inference

The general form of a rule of inference is:

p1 The rule states that if p1 and p2 and …

p2 and pn are all true, then q is true as well.
.
.
.
pn Each rule is an established tautology of
____ p 1  p2  …  pn  q
q
These rules of inference can be used in
any mathematical argument and do not
require any proof.
Fall 2020 CSE 173 - Discrete Mathematics 76

38
 11/14/2020

Rules of Inference
p
_____ q
Addition
 pq p  q Modus
_____ tollens
p q p
_____
Simplification pq
p Hypothetical
p qr
_____ syllogism
q Conjunction
_____  p r (chaining
chaining))
 p q
p q
p Disjunctive
p
pq Modus _____ syllogism
_____ ponens q (resolution
resolution))
q
Fall 2020 CSE 173 - Discrete Mathematics 77

Arguments
Just like a rule of inference, an argument consists of
one or more hypotheses (or premises) and a
conclusion.
We say that an argument is valid, if whenever all its
hypotheses are true, its conclusion is also true.
However, if any hypothesis is false, even a valid
argument can lead to an incorrect conclusion.

Proof: show that hypotheses  conclusion is true

using rules of inference

Fall 2020 CSE 173 - Discrete Mathematics 78

39
 11/14/2020

Rules of Inference
Rules of inference provide the justification of the
steps used in a proof.

One important rule is called modus ponens or the

law of detachment. It is based on the tautology
(p  (p  q))  q. We write it in the following way:

p The two hypotheses p and p  q are

p q written in a column, and the conclusion
____
below a bar, where  means “therefore”.
q

Fall 2020 CSE 173 - Discrete Mathematics 79

Arguments
Example:
“If John has a B in calculus, he will graduate. John
does have a B in calculus. Therefore he will
graduate.”

Is the argument is valid, and its conclusion is

correct?

Fall 2020 CSE 173 - Discrete Mathematics 80

40
 11/14/2020

Arguments
Which rule of inference was used in the last argument?
“If John has a B in calculus, he will graduate. John does
have a B in calculus. Therefore he will graduate.”
p: “John has a B in calculus.”
q: “he will graduate.”
pq
p Modus
_____ ponens
q

All of the hypotheses (p) are true.

Therefore, the conclusion q is correct.

Fall 2020 CSE 173 - Discrete Mathematics 81

Arguments
Example:
“If 101 is divisible by 3, then 1012 is divisible by 9.
101 is divisible by 3. Consequently, 1012 is divisible
by 9.”

Although the argument is valid, its conclusion is

incorrect, because one of the hypotheses is false
(“101 is divisible by 3.”).

If in the above argument we replace 101 with 102,

we could correctly conclude that 1022 is divisible by
9.

Fall 2020 CSE 173 - Discrete Mathematics 82

41
 11/14/2020

Arguments
Which rule of inference was used in the last
argument?

p: “101 is divisible by 3.”

q: “1012 is divisible by 9.”
pq
p Modus
_____ ponens
q

Unfortunately, one of the hypotheses (p) is false.

Therefore, the conclusion q is incorrect.

Fall 2020 CSE 173 - Discrete Mathematics 83

Arguments
Example:
“If Harvey is a dentist, then Harvey drills teeth.
Hervey does not drill teeth. Therefore, Harvey is not
a dentist.”

Is the argument is valid, and its conclusion is

correct?

Fall 2020 CSE 173 - Discrete Mathematics 84

42
 11/14/2020

Arguments Example:
p: “Harvey is a dentist.”
“If Harvey is a
q: “Harvey drills teeth.” dentist, then Harvey
drills teeth. Hervey
pq does not drill teeth.
~q Therefore, Harvey is
_____
not a dentist.”
 ~p

From (i
(i)
Modus
~q  ~p.
ponens
~q
_____
~p
Therefore, the conclusion p is correct.
Fall 2020 CSE 173 - Discrete Mathematics 85

Rules of Inference

p q
Disjunctive
p
_____ syllogism
q (resolution
resolution))

Fall 2020 CSE 173 - Discrete Mathematics 86

43
 11/14/2020

Arguments
Example:
“Either elephant are blue or monkeys are green.
Elephants are grey (not blue).
Therefore, monkeys are green.”

Is the argument is valid, and its conclusion is

correct?

Fall 2020 CSE 173 - Discrete Mathematics 87

Arguments
Example:
“Either elephant are
p: “Either elephants are blue.” blue or monkeys are
q: “Monkeys are green.” green. Elephants are
grey (not blue).
pq Therefore, monkeys
~p Disjunctive are green.”
_____ syllogism
q

Therefore, the conclusion q is correct.

Fall 2020 CSE 173 - Discrete Mathematics 88

44
 11/14/2020

Rules of Inference

pq
Hypothetical
qr
_____ syllogism
 p r (chaining
chaining))

Fall 2020 CSE 173 - Discrete Mathematics 89

Arguments

Another example:
“If it rains today, then we will not have a barbeque
today. If we do not have a barbeque today, then we
will have a barbeque tomorrow.
Therefore, if it rains today, then we will have a
barbeque tomorrow.”

This is a valid argument: If its hypotheses are true,

then its conclusion is also true.

Fall 2020 CSE 173 - Discrete Mathematics 90

45
 11/14/2020

Arguments
Let us formalize the previous argument:
p: “It is raining today.”
q: “We will not have a barbecue today.”
r: “We will have a barbecue tomorrow.”
So the argument is of the following form:

pq “If it rains today, then we will not have

qr Hypothetical a barbeque today. If we do not have a
______ syllogism barbeque today, then we will have a
pr barbeque tomorrow.
Therefore, if it rains today, then we will
have a barbeque tomorrow.”

Fall 2020 CSE 173 - Discrete Mathematics 91

Arguments
Another example:

Gary is either intelligent or a good actor.

If Gary is intelligent, then he can count
from 1 to 10.
Gary can only count from 1 to 3.
Therefore, Gary is a good actor.

i: “Gary is intelligent.”
a: “Gary is a good actor.”
c: “Gary can count from 1 to 10.”

Fall 2020 CSE 173 - Discrete Mathematics 92

46
 11/14/2020

Arguments
Gary is either intelligent (i) or a good actor (a).
If Gary is intelligent (i), then he can count from 1 to 10 (c).
Gary can only count from 1 to 3 (~c).
Therefore, Gary is a good actor (a)..

Step 1: ai Hypothesis

Step 2: i c Hypothesis
Step 3: c Hypothesis
Step 4: i Modus tollens Steps 2 & 3
Step 5: ai Hypothesis
Step 6: a Disjunctive Syllogism
Steps 4 & 5
Conclusion: a (“Gary is a good actor.”)

Fall 2020 CSE 173 - Discrete Mathematics 93

Arguments
Yet another example:

If you listen to me, you will pass CSE 173.

You passed CSE 173.
Therefore, you have listened to me.

Is this argument valid?

No, it assumes ((p  q) q)  p.

This statement is not a tautology. It is false if p is
false and q is true.

Fall 2020 CSE 173 - Discrete Mathematics 94

47
 11/14/2020

Arguments
A  (B  C)
C
BA
_________
__________
A

Step 1: A  (B  C) Hypothesis
Step 2: (B  C) Simplification (from 1)
Step 3: C Disjunctive Syllogism
Step 4: B Disjunctive Syllogism (from 3 & 4)
Step 5: B   A Hypothesis
Step 6:  A Modus ponens

Fall 2020 CSE 173 - Discrete Mathematics 95

Arguments PQ
RP
RI
I
_________
__________
Q
Step 1: R  I Hypothesis
Step 2: I Hypothesis
Step 3: R Disjunctive Syllogism
Step 4: R  P Hypothesis
Step 5: P Modus ponens (from 3 & 4)
Step 6: P  Q Hypothesis
Step 7: Q Modus ponens (from 5 & 6)
Fall 2020 CSE 173 - Discrete Mathematics 96

48
 11/14/2020

Arguments (P  Q)  S
SR
 (R  Q)
_________
__________
P
Step 1: (R  Q) Hypothesis
Step 2: R  Q De Morgan’s Law
Step 3: R Simplification
Step 4: (P  Q)  S Hypothesis
Step 5: S  R Hypothesis
Step 6: (P  Q)  R Disjunctive Syllogism
Step 7: (P  Q) Modus ponens (from 3 & 6)
Step 8: P  Q De Morgan’s Law
Step 9: P Simplification
Fall 2020 CSE 173 - Discrete Mathematics 97

Rules of Inference for Quantified Statements

x P(x)
__________ Universal
 P(c) if cU instantiation

P(c) for an arbitrary c

cU Universal
___________________
 x P(x) generalization

x P(x) Existential
______________________
 P(c) for some element c
cU instantiation

P(c) for some element c

cU Existential
____________________
 x P(x) generalization

Fall 2020 CSE 173 - Discrete Mathematics 98

49
 11/14/2020

Rules of Inference for Quantified Statements

Example:

Every NSU student is a genius.

George is a NSU student.
Therefore, George is a genius.

U(x): “x is a UMB student.”

G(x): “x is a genius.”

Fall 2020 CSE 173 - Discrete Mathematics 99

Rules of Inference for Quantified Statements

The following steps are used in the argument:

Step 1: x (N(x)  G(x)) Hypothesis
Step 2: N(George)  G(George) Univ. instantiation
using Step 1
Step 3: N(George) Hypothesis
Step 4: G(George) Modus ponens
using Steps 2 & 3

x P(x) Universal
__________
 P(c) if c
cU instantiation

Fall 2020 CSE 173 - Discrete Mathematics 100

50
 11/14/2020

Proof methods
 We will discuss six proof methods:
1. Direct proofs
2. Proof by cases
3. Indirect proofs
4. The Bi-conditional
5. Proof by contradiction
6. Counterexamples

101

Definition even and odd numbers

 We call n is even if n is divisible by 2
 i.e., n = 2*m for some integer m
 n= 2 n = 2.1
 n = 4 n = 2.2
 ….
 ….
 N is odd if n is not divisible by 2
 i.e., n = 2*m +1 for some integer m
 n = 3 n = 2.1 + 1
 n = 5 n = 2.2 + 1
 ….
 ….
102

51
 11/14/2020

Proving Theorems
Direct proof:
An implication p  q can be proved by showing that
if p is true, then q is also true.
Example: Give a direct proof of the theorem
“If n is odd, then n2 is odd.”
Idea: Assume that the hypothesis of this implication
is true (n is odd). Then use rules of inference and
known theorems of math to show that q must also be
true (n2 is odd).

Fall 2020 CSE 173 - Discrete Mathematics 103

Proving Theorems

n is odd.

Then n = 2k + 1, where k is an integer.

Consequently, n2 = (2k + 1)2.

= 4k2 + 4k + 1
= 2(2k2 + 2k) + 1
= 2m + 1

Since n2 can be written in this form, it is odd.

Fall 2020 CSE 173 - Discrete Mathematics 104

52
 11/14/2020

Proving Theorems
Direct proof:
An implication p  q can be proved by showing that if
p is true, then q is also true.

Example: Give a direct proof of the theorem

Show that the square of an even number is an
even number
 Rephrased: if n is even, then n2 is even

Idea: Assume that the hypothesis of this implication is

true (n is even). Then use rules of inference and
known theorems of math to show that q must also be
true (n2 is even).
Fall 2020 CSE 173 - Discrete Mathematics 105

Proving Theorems

n is even.

Then n = 2k, where k is an integer.

Consequently, n2 = (2k)2.
= 4k2
= 2(2k2)
= 2m

Since n2 can be written in this form, it is even.

Fall 2020 CSE 173 - Discrete Mathematics 106

53
 11/14/2020

Proving Theorems
Direct proof:
An implication p  q can be proved by showing that if
p is true, then q is also true.

Example: Give a direct proof of the theorem

For all integers x and y, if x, y are both odd, then x
+ y is even
Idea: Assume that the hypothesis of this implication is
true (x, y are both odd). Then use rules of inference
and known theorems of math to show that q must also
be true (x + y is even).

Fall 2020 CSE 173 - Discrete Mathematics 107

Proving Theorems

x and y are odd.

Then x = 2k+1, and y = 2m +1 where k, m integers.

Consequently, x + y = 2k+1 + 2m +1.

= 2k + 2m + 2
= 2(k+m+1)
= 2p

Since x + y can be written in this form, it is even.

Fall 2020 CSE 173 - Discrete Mathematics 108

54
 11/14/2020

Proving Theorems
Direct proof:
An implication p  q can be proved by showing that if
p is true, then q is also true.

Example: Give a direct proof of the theorem

For all integers x and y, if x, y are both odd, then
x.y is also odd
Idea: Assume that the hypothesis of this implication is
true (x, y are both odd). Then use rules of inference
and known theorems of math to show that q must also
be true (x.y is odd).

Fall 2020 CSE 173 - Discrete Mathematics 109

Proving Theorems

x and y are odd.

Then x = 2k+1, and y = 2m +1 where k, m integers.

Consequently, x.y = (2k+1).(2m +1)

= 2km + 2k + 2m + 1
= 2(km+k+m) +1
= 2p + 1

Since x.y can be written in this form, it is odd.

Fall 2020 CSE 173 - Discrete Mathematics 110

55
 11/14/2020

Proof methods
 We will discuss six proof methods:
1. Direct proofs
2. Proof by cases
3. Indirect proofs
4. The Bi-conditional
5. Proof by contradiction
6. Counterexamples

111

Proving Theorems
Direct proof using cases:
Example: If q is not divisible by 3 then q2 mod 3 = 1

Idea: Assume that the hypothesis of this implication is

true (q is not divisible by 3). Then you will see there
could be 2 cases. Use rules of inference and known
theorems of math to show that q2 mod 3 = 1 in both
the cases.

Fall 2020 CSE 173 - Discrete Mathematics 112

56
 11/14/2020

Proving Theorems

q is not divisible by 3. Then either q mode 3 = 1 or q

mod 3 = 2 (for example 7 mod 3 = 1 and 8 mod 3 = 2)

Case 1: Suppose q mod 3 = 1. Then q = 3k+1, where

k is an integer.

Consequently, q2 = (3k+1).(3k +1)

= 9k2 + 6k + 1
= 3(3k2+2k) +1
= 3p + 1

Since q2 can be written in this form, q2 mode 3 = 1 .

Fall 2020 CSE 173 - Discrete Mathematics 113

Proving Theorems
q is not divisible by 3. Then either q mode 3 = 1 or q
mod 3 = 2 (for example 7 mod 3 = 1 and 8 mod 3 = 2)

Case 2: Suppose q mod 3 = 2. Then q = 3k+2, where

k is an integer.

Consequently, q2 = (3k+2).(3k +2)

= 9k2 + 12k + 4
= 9k2 + 12k + 3 + 1
= 3(3k2+4k + 1) +1
= 3p + 1
Since q2 can be written in this form, q2 mode 3 = 1 .
Fall 2020 CSE 173 - Discrete Mathematics 114

57
 11/14/2020

Proof methods
 We will discuss six proof methods:
1. Direct proofs
2. Proof by cases
3. Indirect proofs
4. The Bi-conditional
5. Proof by contradiction
6. Counterexamples

115

Proving Theorems
Indirect proof:
An implication p  q is equivalent to its contra-
positive q  p. Therefore, we can prove p  q
by showing that whenever q is false, then p is also
false.
Example: Give an indirect proof of the theorem
“If 3n + 2 is odd, then n is odd.”
Idea: Assume that the conclusion of this implication
is false (n is even). Then use rules of inference and
known theorems to show that p must also be false
(3n + 2 is even).

Fall 2020 CSE 173 - Discrete Mathematics 116

58
 11/14/2020

Proving Theorems
n is even.

Then n = 2k, where k is an integer.

It follows that 3n + 2 = 3(2k) + 2

= 6k + 2
= 2(3k + 1)

Therefore, 3n + 2 is even.

We have shown that the contrapositive of the

implication is true, so the implication itself is also true
(If 3n + 2 is odd, then n is odd).

Fall 2020 CSE 173 - Discrete Mathematics 117

Which to use
 When do you use a direct proof versus
an indirect proof?

 If it’s not clear from the problem, try

direct first, then indirect second
 If indirect fails, try the other proofs

118

59
 11/14/2020

Example of which to use

 Prove that if n is an integer and n3+5 is odd,
then n is even

 Via direct proof

 n3+5 = 2k+1 for some integer k (definition of odd
numbers)
 n3 = 2k+6

n  3 2k  6
 Umm…

 So direct proof didn’t work out. Next up: indirect

proof

119

Example of which to use

 Prove that if n is an integer and n3+5 is odd, then
n is even

 Via indirect proof

 Contra-positive: If n is odd, then n3+5 is even
 Assume n is odd, and show that n3+5 is even
 n=2k+1 for some integer k (definition of odd numbers)
 n3+5 = (2k+1)3+5 = 8k3+12k2+6k+6 = 2(4k3+6k2+3k+3)
 As 2(4k3+6k2+3k+3) is 2 times an integer, it is even

120

60
 11/14/2020

Proof methods
 We will discuss six proof methods:
1. Direct proofs
2. Proof by cases
3. Indirect proofs
4. The Bi-conditional
5. Proof by contradiction
6. Counterexamples

121

Proving Theorems
The Bi-conditional proof:
If a theorem is of the form p  q is equivalent to p
 q and q  p. You have to prove both
Example: Give a proof of the theorem
“An integer x is even if and only if x2 is even.”
Idea: Prove two things:-- (1) If x is even then x2 is
even , and (2) if x2 is even then x is even. We have
already proved both in previous slides.

Fall 2020 CSE 173 - Discrete Mathematics 122

61
 11/14/2020

Proof methods
 We will discuss six proof methods:
1. Direct proofs
2. Proof by cases
3. Indirect proofs
4. The Bi-conditional
5. Proof by contradiction
6. Counterexamples

123

Proof by contradiction
 Given a statement p, assume it is false
 Assume ¬p

 Prove that ¬p cannot occur

 A contradiction exists

 Given a statement of the form p→q

 To assume it’s false, you only have to consider
the case where p is true and q is false

124

62
 11/14/2020

Proof by contradiction example 1

 Theorem (by Euclid): There are infinitely many
prime numbers.

 Proof. Assume there are a finite number of

primes
 List them as follows: p1, p2 …, pn.
 Consider the number q = p1p2 … pn + 1
 This number is not divisible by any of the listed primes
○ If we divided pi into q, there would result a remainder of 1
 We must conclude that q is a prime number, not among
the primes listed above
○ This contradicts our assumption that all primes are in the list
125 p1, p2 …, pn.

Proof by contradiction example 2

 Prove that if n is an integer and n3+5 is odd, then n is
even
 Rephrased: If n3+5 is odd, then n is even

 Assume p is true and q is false

 Assume that n3+5 is odd, and n is odd

 n=2k+1 for some integer k (definition of odd numbers)

 n3+5 = (2k+1)3+5 = 8k3+12k2+6k+6 = 2(4k3+6k2+3k+3)
 As 2(4k3+6k2+3k+3) is 2 times an integer, it must be
even
 Contradiction!
126

63
 11/14/2020

Proof by contradiction example 3

If 3n + 2 is odd, then n is odd

Suppose n is even (negation of the conclusion).

Then n = 2k, where k is an integer.
It follows that 3n + 2 = 3(2k) + 2
= 6k + 2
= 2(3k + 1)
Therefore, 3n + 2 is even.

However, this is a contradiction since 3n + 2 is given to

be odd, so the conclusion (n is odd) holds.

Fall 2020 CSE 173 - Discrete Mathematics 127

Proof methods
 We will discuss six proof methods:
1. Direct proofs
2. Proof by cases
3. Indirect proofs
4. The Bi-conditional
5. Proof by contradiction
6. Counterexamples

128

64
 11/14/2020

The counter example

 Sometimes we wish to show that a
proposition x (P(x) is false

 Prove that for a single example x = x0 the

proposition cannot occur, i.e., P(x0) is false

129

Another Example on Proof

STATEMENT: All multiples of 3 are odd.
COUNTER EXAMPLE: The number 6 is multiple of 3
but it is not odd.

STATEMENT: All triangles are equilateral.

COUNTER EXAMPLE: The 3-4-5 is not equilateral.

STATEMENT: The product of any two irrational numbers is

irrational.
COUNTER EXAMPLE: Let x = √12 AND y = √3. Both x and y
are irrational. But √12. √3 = √36 = 6

Fall 2020 CSE 173 - Discrete Mathematics 130

65
 11/14/2020

Another Example on Proof

Hypotheses:
1. Anyone performs well is either intelligent or a good actor.
x (P(x)  I(x)  A(x))
2. If someone is intelligent, then he/she can count
from 1 to 10.
x (I(x)  C(x) )
3. Gary performs well.
P(G)
4. Gary can only count from 1 to 3.
C(G)
Conclusion: not everyone is both intelligent and a good actor
x(I(x)  A(x))

Fall 2020 CSE 173 - Discrete Mathematics 131

Another Example on Proof

Direct proof:
Step 1: x (P(x)  I(x)  A(x)) Hypothesis
Step 2: P(G)  I(G)  A(G) Univ. Inst. Step 1
Step 3: P(G) Hypothesis
Step 4: I(G)  A(G) Modus ponens Steps 2 & 3
Step 5: x (I(x)  C(x)) Hypothesis
Step 6: I(G)  C(G) Univ. inst. Step5
Step 7: C(G) Hypothesis
Step 8: I(G) Modus tollens Steps 6 & 7
Step 9: I(G)  A(G) Addition Step 8
Step 10: (I(G)  A(G)) Equivalence Step 9
Step 11: x(I(x)  A(x)) Exist. general. Step 10
Step 12: x (I(x)  A(x)) Equivalence Step 11
Conclusion: x (I(x)  A(x)), not everyone is both intelligent
and a good actor.

Fall 2020 CSE 173 - Discrete Mathematics 132

66
 11/14/2020

Summary, Section 1.5

 Terminology (axiom, theorem, conjecture,
argument, etc.)
 Rules of inference (Tables 1 and 2)
 Valid argument (hypotheses and conclusion)
 Construction of valid argument using rules of
inference
 For each rule used, write down and the statements
involved in the proof
 Direct and indirect proofs
 Other proof methods (e.g., induction, pigeon hole)
will be introduced in later chapters

Fall 2020 CSE 173 - Discrete Mathematics 133

67