Discrete and Combinatorial

Mathematics

Chapter 2
Fundamentals of Logic

1
 Logic
Logic = the study of correct reasoning

Use of logic
In mathematics:
to prove theorems.

In computer science:
to prove that programs do what they are supposed to do.

2
 Propositions

A proposition or statement is a declarative sentence that

may be assigned a ‘true’ or ‘false’ value, but not both.

This value is the truth value of the proposition.

Propositions: “1+2=3”, “Peter is a programmer”,
“It is snowing”.
“Toronto is the capital of Canada”.

Not Propositions: “Is 1+2=3?”, “What a beautiful evening!”,

“The number x is an integer”.

Also Propositions: “There exists no ghost”. 3

 Examples of propositions

 September 6 2007 is a Thursday.

 September 6 2007 is a Friday.
 3+2 equals 7.
 There is no gravity.

The following are not propositions.

• Do your homework.
• What is the time?
• 3+4.
4
 True or False, That’s All
The proposition “There exists no ghost” is on equal footing
with the “1+2=3” proposition.

The only thing that matters is the fact that a proposition is

‘True’ or ‘False’.
Because of this, we will often label our propositions simply
p,q, etc. Sometimes we use 0 for False and 1 for True.

Things become interesting if we combine propositions…

5
Propositional Logic
 Propositional Logic – the area of logic that deals with
propositions.

 Propositional Variables – variables that represent

propositions: p, q, r, s.

◼ E.g. Proposition p – “Today is Friday.”

 Truth values – T, F

6
Propositional logic
 Logic of compound statements built from simpler
statements using Boolean connectives.

 Building block for mathematics and computing.

 Direct applications
◼ Design of digital circuits.
◼ Expressing conditions in programs.
◼ Database queries.

7
 Connectives
If p and q are propositions, new compound propositions
can be formed by using connectives.

Most common connectives:

Conjunction AND Symbol ^
Disjunction OR Symbol v
Exclusive disjunction OR Symbol v
Negation NOT Symbol 
Implication Symbol →
Biconditional Symbol 

The truth values of compound propositions can be described

by truth tables. 8
DEFINITION 1

Let p and q be propositions. The conjunction of p

and q, denoted by p Λ q, is the proposition “p and
q”. The conjunction p Λ q is true when both p and q
are true and is false otherwise.

 Examples
◼ Find the conjunction of the propositions p and q where p is the
proposition “Today is Friday.” and q is the proposition “It is raining
today.”, and the truth value of the conjunction.

Solution: The conjunction is the proposition “Today is Friday and it is

raining today.” The proposition is true on rainy Fridays.

9
 Truth table of conjunction
Truth table of conjunction:

p q p^q
1 1 1
1 0 0
0 1 0
0 0 0
p ^ q is true only when both p and q are true.

Example: p = "Tigers are animals", q = "Lions are plants"

p ^ q = "Tigers are animals and Lions are plants" 10
DEFINITION 2
Let p and q be propositions. The disjunction of p
and q, denoted by p ν q, is the proposition “p or q”.
The conjunction p ν q is false when both p and q are
false and is true otherwise.
 Note:
inclusive or : The disjunction is true when at least one of the two
propositions is true.

◼ E.g. “Students who have taken calculus or computer science can

take this class.” – those who take one or both classes.

exclusive or : The disjunction is true only when one of the

proposition is true.
◼ E.g. “Students who have taken calculus or computer science, but
not both, can take this class.” – only those who take one of them.
◼
 Definition 2 uses inclusive or.
11
 Truth table of disjunction
The truth table of disjunction:

p q pvq
1 1 1
1 0 1
0 1 1
0 0 0
p  q is false only when both p and q are false

Example: p = "John is a programmer", q = "Mary is a lawyer“

p v q = "John is a programmer or Mary is a lawyer"
12
 Exclusive disjunction
“Either p or q” (but not both), in symbols p  q
p q pvq
1 1 0
1 0 1
0 1 1
0 0 0
p  q is true only when p is true and q is false, or p is false
and q is true.

Example: p = "John is programmer, q = "Mary is a lawyer“

p v q = "Either John is a programmer or Mary is a lawyer but
13
not both."
 Negation
Negation of p: in symbols p

p p
1 0

0 1

 p is false when p is true,  p is true when p is false.

Example: p = "John is a programmer“

 p = "It is not true that John is a programmer"
14
DEFINITION 3

Let p be a proposition. The negation of p, denoted by

¬p, is the statement
“It is not the case that p.”

The proposition ¬p is read “not p.” The truth value of

the negation of p, ¬p is the opposite of the truth value
of p.

 Examples
◼ Find the negation of the proposition “Today is Friday.” and express
this in simple English.

Solution: The negation is “It is not the case that today is Friday.”
In simple English, “Today is not Friday.” or “It is not
Friday today.” 15
 Examples
◼ Find the negation of the proposition “At least 10 inches
of rain fell today in Miami.” and express this in simple
English.

Solution: The negation is “It is not the case that at least 10

inches of rain fell today in Miami.”

In simple English, “Less than 10 inches of rain fell today in

Miami.”

16
 Implication
A conditional proposition is of the form “p implies q”,
denoted by p → q, where p is the hypothesis and q is the
conclusion .

Also “If p then q”.“p is sufficient for q”, “p is a sufficient

condition for q”, “q is necessary for p”, “q is a necessary
condition for p”, “p only if q”.

Example:
p = " John is a programmer "
q = " Mary is a lawyer "
p → q = “If John is a programmer then Mary is a lawyer"
17
 Truth table of p → q

p q p→q
1 1 1
1 0 0

0 1 1
0 0 1

p → q is true when both p and q are true or

when p is false
18
19
20
 Biconditional
The biconditional proposition is of the form “p if and only if q” or “ p iff q ”,
denoted by p  q.
p q pq
1 1 1
1 0 0
0 1 0
0 0 1
p  q is true when both p → q and q → p are true.

Example:
p = " John is a programmer "
q = " Mary is a lawyer "
p  q = “John is a programmer iff Mary is a lawyer" 21
More compound propositions

Let p, q, r be primitive propositions.

We can form other compound propositions,
such as
(pq)^r

p(q^r)

( p)( q)

(pq)^( r)
and many others… 22
Example: truth table of (pq)^r
p q r (p  q) ^ r
1 1 1 1
1 1 0 0
1 0 1 1
1 0 0 0
0 1 1 1
0 1 0 0
0 0 1 0
0 0 0 0
23
 Truth Tables of Compound Propositions
 We can use connectives to build up complicated compound propositions
involving any number of propositional variables, then use truth tables to
determine the truth value of these compound propositions.

 Example: Construct the truth table of the compound proposition

(p ν ¬q) → (p Λ q).

The Truth Table of (p ν ¬q) → (p Λ q).

p q ¬q p ν ¬q pΛq (p ν ¬q) → (p Λ q)

T T F T T T
T F T T F F
F T F F F T
F F T T F F
24
 Precedence of Logical Operators

 We can use parentheses to specify the order in which logical

operators in a compound proposition are to be applied.

 To reduce the number of parentheses, the precedence order is

defined for logical operators.

Precedence of Logical Operators.

E.g. ¬p Λ q = (¬p ) Λ q
Operator Precedence
p Λ q ν r = (p Λ q ) ν r
¬ 1
p ν q Λ r = p ν (q Λ r)
Λ 2
ν 3
→ 4
5 25
 Translating English Sentences

 English (and every other human language) is often ambiguous.

Translating sentences into compound statements removes the
ambiguity.

 Example: How can this English sentence be translated into a logical

expression?
“You cannot ride the roller coaster if you are under 4 feet
tall unless you are older than 16 years old.”

Solution: Let q, r, and s represent “You can ride the roller coaster,”

“You are under 4 feet tall,” and “You are older than
16 years old.” The sentence can be translated into:
26
(r Λ ¬ s) → ¬q.
 Example: How can this English sentence be translated into a logical
expression?

“You can access the Internet from campus only if you are a computer
science major or you are not a freshman.”

Solution: Let a, c, and f represent “You can access the Internet from
campus,” “You are a computer science major,” and “You are
a freshman.” The sentence can be translated into:
a → (c ν ¬f).

27
 Logical equivalence
Two propositions are said to be logically
equivalent () if their truth tables are identical.

Example:  p  q  p → q

p q pq p→q

1 1 1 1
1 0 0 0
0 1 1 1
0 0 1 1 28
 Biconditional vs. Equivalence
Don’t confuse the equivalence  with the
biconditional  (only the biconditional has a truth table).

example:
p  p is a proposition, a statement within logic,
p  p is mathematically correct, … about logic.

p  p is a False, p  p is incorrect

Hence pp  (pp), and so on.

29
 Example

Proposition p:Alice is smart.

Proposition q:Alice is honest.

¬p∧q: Alice is not smart but honest.

p∨(¬p∧q): Either Alice is smart, or she is not smart but honest.

p→¬q: f Alice is smart, then she is not honest.

OR
Alice is either smart or honest, but Alice is not honest if she is
smart: (p∨q)∧(p→¬q).

That Alice is smart is necessary and sufficient for Alice to be

honest: (p→q)∧(q→p).

(This is often written as p q). 30

 Converse
The converse of p → q is q → p

p q p→q q→p
1 1 1 1
1 0 0 1
0 1 1 0
0 0 1 1

These two propositions

are not logically equivalent
31
 Contrapositive
The contrapositive of the proposition p → q is
 q →  p.

p q p→q q→p
1 1 1 1
1 0 0 0
0 1 1 1
0 0 1 1

They are logically equivalent.

32
Five friends (Abby, Heather, Kevin, Randy and Vijay) have
access to an on-line chatroom.

We know the following are true:

1 Either K or H or both are chatting.

2 Either R or V but not both are chatting.

3 If A is chatting, then R is chatting.

4 V is chatting if and only if K is chatting.

5 If H is chatting, then both A and K are chatting.

Determine who is chatting.

33
There are two rooms: A and B. Each room has a sign.

SignatroomA:“There is a lady in room A, and a tiger in

room B.”
Sign at room B:“There is a lady in one room,and a tiger in
another room.”

Assume that: Exactly one sign is true and another sign is

false.

Exactly one thing(lady or tiger) in each room.

Determine which room contains what?

34
 Tautology
A proposition is a tautology (T0) if its truth table
contains only true values for every case.

p q p→pvq
1 1 1
1 0 1
0 1 1
0 0 1

35
Definitions:

A compound proposition that is always True is called a

tautology.

Two propositions p and q are logically equivalent if their

truth tables are the same.

Namely, p and q are logically equivalent if p q is a

tautology.

If p and q are logically equivalent, we write p ≡ q.

36
 Contradiction
A proposition is a contradiction (F0) if its truth table
contains only false values for every case.

p p ^ ( p)
1 0
0 0

37
 Proving Things in Logic
The standard approach is to use truth
tables.

If we deal with n simple propositions p1,…,pn,

our truth table will have size at least 2n.
This becomes a substantial disadvantage if n is big.

Sometimes there is a much more efficient way

to prove equivalences.

First, look at some very simple equivalences…

38
 The Laws of Logic
1) Double negation law: If we do the negation of a negated
statement, then the resultant statement will be the statement
itself. p  p

2) De Morgan’s laws: If we combine two statements with the

symbol ∧(AND) and then do the negation of these combined
statements, then the resultant statement will be the same
even if we combine the negation of both statements
separately with the symbol ∨(OR).
(pq)  pq,
(pq)  pq
3)Commutative laws:If we combine two statements with the
symbol ∧(and) or ∨(or), then the resultant statement will be the
same even if we change the position of the statements.
pqqp and 39
pq  qp
 The Laws of Logic
4)Associative laws:If we combine three statements with the
help of brackets by the symbol ∧(and) or ∨(or), then the
resultant statement will be the same even if we change the
order of brackets.
p(qr)(pq)r,
p(qr)  (pq)r

5)Distributive laws: If we combine a statement by the ∨(OR)

symbol with the two other statements which are joined with the
symbol ∧(AND), then the resultant statement will be the same
even if we are separately combining the statements with the
symbol ∨(OR) and combining the joined statements with
∧(AND).
p(qr)(pq)(pr),
p(qr)  (pq)(pr) 40
 The Laws of Logic
6) Idempotent laws:If we combine two same statements with
the symbol ∧(and) and ∨(or), then the resultant statement will
be the statement itself.
ppp,
pp  p

7)Identity laws: If we combine a statement and a True value

with the symbol ∨(or), then it will generate the True value. If
we combine a statement and a False value with the symbol
∧(and), then it will generate the statement itself. Similarly, we
will do this with the opposite symbols.
pFalsep,
pTrue  p
41
 The Laws of Logic (Cont.)
8)Inverse laws:ppTrue,
pp  False

9)Domination laws:pTrueTrue,
pFalse  False

10)Absorption laws:If we combine a statement P by ∨(OR)

symbol with the same statement P and one other statement Q,
which are joined with the symbol ∧(AND), then the resultant
statement will be the first statement P. The same result will be
generated if we interchange the symbols. p(pq)p,
p(pq)  p
42
 Proving Equivalences
Prove (p  q )  (p  q)  p.

(p  q )  (p  q)
 (p  q )  (p  q) [DeMorgan’s Law]
 (p  q )  (p  q) [Double Negation]
 p  (q  q) [Distributive Law]
 p  F0 [Inverse Law]
 p [Identity Law]

43
 Proving Equivalences
Example 1 : p → q ? ¬p ∨ q

We will prove this with the help of a truth table.

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

44
 Proving Equivalences
Example 2 : P Q ? (P → Q) ∧ (Q → P)

P Q P→Q Q→P P Q (P → Q) ∧ (Q → P)
T T T T T T
T F F T F F
F T T F F F
F F T T T T

3. use the equivalent property to prove the following

statement:p q ? ( p ∧ q ) ∨ ( ¬ p ∧ ¬q)
45
 Simplify Statements
Simplify “(p  q  r)  (p  t  q)  (p  t  r)”.

(p  q  r)  (p  t  q)  (p  t  r)
 p  [(q  r)  (t  q)  (t  r)] [Distributive Law]
 p  [(q  r)  (t  r)  (t  q )] [Commutative Law]
 p  [((q  t)  r)  (t  q )] [Distributive Law]
 p  [((q  t)  r)  (t  q )] [Double Negation]
 p  [((q  t)  r)  (t  q )] [DeMorgan’s Law]
 p  [(t  q )  ((q  t)  r)] [Commutative Law]
 p  [((t  q )  (q  t))  ((t  q )  r)]
[Distributive Law]
 p  [F0  ((t  q )  r)] [s  s  F0  s]
 p  [(t  q )  r] [F0 is the identity for ]
46
 Simplify Statements (Cont.)

p  [(t  q )  r]
 p  [(t  q )  r] [DeMorgan’s Law]
 p  [(t  q )  r] [Double Negation]
 p  [r  (t  q )] [Commutative Law]

Hence (p  q  r)  (p  t  q)  (p  t  r) 
p  [r  (t  q )].

47
 Valid arguments
Argument – A sequence of statements, and premises,
that end with a conclusion.
Validity – A deductive argument is said to be valid if
and only if it takes a form that makes it impossible for
the premises to be true and the conclusion
nevertheless to be false.
Deductive reasoning:The process of reaching a
conclusion q from a sequence of propositions p1,
p2, …, pn.

The propositions p1, p2, …, pn are called premises or

hypothesis.
The proposition q that is logically obtained through the
48
process is called the conclusion.
 Rules of inference
1. Modus ponens (from Latin 'method of putting by placing'),
implication elimination, or affirming the antecedent, is a
deductive argument form and rule of inference. It can be
summarized as "P implies Q. P is true.
◼ p→q
◼ p
◼ Therefore, q
◼
Example:
◼ Insects have six legs.
◼ Beetles are insects.
◼ Therefore beetles have six legs.

49
 Rules of inference (Cont.)
2. Modus tollens ( fromLatin"method of removing
by taking away") and denying the consequent, is
a deductive argument form and a rule of
inference. It can be summerizwd "If P, then Q.
Not Q. Therefore, not P."
◼ p→q
◼ ~q
◼ Therefore, ~p

Example:
◼ Insects have six legs.
◼ Spiders have eight legs.
50
◼ Therefore spiders are not insects.
 Rules of inference (Cont.)
3. Rule of disjunctive 5. Rule of conjunction
amplification ◼ p
◼ p ◼ q
◼ Therefore, p  q ◼ Therefore, p ^ q
Let P be the proposition,  Let P − “He studies very hard”
“He studies very hard” is true  Let Q − “He is the best boy in the
Therefore − "Either he studies very hard class”
Or he is a very bad student."  Therefore − "He studies very hard
Here Q is the proposition and he is the best boy in the
class"
“he is a very bad student”.
4. Rule of conjunctive simplification
◼ p^q
◼ Therefore, p
◼ P∧Q "He studies very hard and he is the best boy in the class",
51
Therefore − "He studies very hard“.
Rules of inference (Cont.)
6. Law of the syllogism
◼p→q
◼q→r
◼ Therefore, p → r

Example:
◼ 72 is divisible by 6.
◼ 6 is divisible by 3.
◼ Therefore 72 is divisible by 3.

52
 Rules of inference (Cont.)
7. Rule of disjunctive syllogism
◼pq
◼ p
◼ Therefore, q

Example
Example:
"The ice cream is not vanilla flavored",
◼ John is studying or sleeping. ¬P
◼ John is not studying.
◼ Therefore John is sleeping. "The ice cream is either vanilla
flavored or chocolate flavored", P∨Q

Therefore − "The ice cream is

chocolate flavored”
53
 Rules of inference (Cont.)
8. Rule of contradiction
◼ p → F0
◼ Therefore, p

If we want to establish the validity of the argument

(p1  p2  …  pn) → q, we can establish the
validity of the logically equivalent argument
(p1  p2  …  pn  q ) → F0.

54
 Example
Demonstrate the validity of the argument
((p → r)  (p → q)  (q → s)) → (r → s)

(1) p → r
(2) r → p
(3) p → q
(4) r → q (Law of the Syllogism)
(5) q → s
(6) Therefore r → s (Law of the Syllogism)

55
 Example
Demonstrate the validity of the argument
(((p  q) → (r  s))  (r → t)  (t)) → p
(1) r → t
(2) t
(3) r (Rule of disjunctive syllogism)
(4) r  s (Rule of disjunctive amplification)
(5) (r  s) (De Morgan’s law)
(6) (p  q) → (r  s)
(7)  (p  q) (Rule of disjunctive syllogism)
(8) p  q (De Morgan’s law)
(9) Therefore p (Rule of conjunctive simplification)

Using the rules of inference, and given the following premises: p  (q  r)

p  s t  q s Show that r  t must be true.
56
 Quantifiers
A quantifier is an expression that indicates the scope of
something, specifically in terms of quantity.

A quantifier is “an operator that limits the variables of a

proposition”

In logic, the two quantifiers we are concerned about are all or

every, and some, an, or at least one.

Two types:
Universal
Existential 57
 For every and for some
Most statements in mathematics and computer science use
terms such as for every and for some.

For example:
For every triangle T, the sum of the angles of T is 180
degrees.

For every integer n, n is less than p, for some prime

number p.

58
 Universal quantifier

Sometimes the mathematical statements assert that if the

given property is true for all values of a variable in a given
domain, it will be known as the domain of discourse.

Using the universal quantifiers, we can easily express these

statements.

The universal quantifier symbol is denoted by the ∀, which

means "for all".

“” is called the universal quantifier.

59
 Universal quantifier
Suppose P(x) is used to indicate predicate, and D is used to
indicate the domain of x. The universal statement will be in

the form "∀x ∈ D, P(x)".

The statement x P(x) is

True if P(x) is true for every x  D
False if P(x) is not true for some x  D

Example: Let P(n) be the propositional function n2 + 2n is an

odd integer n  D = {all integers}

P(n) is True only when n is an odd integer, False if n is an

60
even integer.
 Existential quantifier

Sometimes the mathematical statements assert that we have

an element that contains some properties.

Using existential quantifiers, we can easily express these

statements.

“” is called the existential quantifier.

The existential quantifier symbol is denoted by the ∃, which

means "there exists".

61
 Existential quantifier

Suppose P(x) is used to indicate predicate, and D is used to

indicate the domain of x.

The existential statement will be in the form "∃x ∈ D such that

P(x)". is true if there exists an element x in the domain D
for which P(x) is true.

In symbols: x, P(x)

62
Example :"x ≤ 5 ∧ x > 3“

This statement is false for x= 6 and true for x = 4.

Now we will compare the above statement with the following

statement
"For every x, x ≤ 5 ∧ x > 3“

This statement is definitely false. Now we will again define a

statement
"There exists an x such that "x ≤ 5 ∧ x > 3“
This statement is definitely true.

The phrase "there exists an x such that" is known as the

existential quantifier, and "for every x" phrase is known
as the universal quantifier.
The variables in a formula cannot be simply true or false63

unless we bound these variables by using the quantifier.

 Quantifier Examples
 Let P(x)=“x must take a discrete mathematics course,” and
S(x)=“x is a computer science student,”

 where the universe of discourse for both is all students in a

particular college.

 The statement “Every computer science student must take a

discrete mathematics course” can be expressed as
x (S(x)→P(x))

 The statement “Everybody must take a discrete mathematics

course or be a computer science student” can be expressed
64
as x (S(x)P(x))
 Counter example

The universal statement x P(x) is false if x  D such that

P(x) is false.

The value x that makes P(x) false is called a counter

example to the statement x P(x).

Example:
P(x) = "every x is a prime number", for every integer x.
But if x = 4 (an integer) this x is not a primer number.

Then 4 is a counter example to P(x) being true.

65
 Generalized De Morgan’s Laws

If P(x) is a propositional function, then each pair of

propositions in a) and b) below have the same truth
values:

a) ~(x P(x)) and x: ~P(x)

"It is not true that for every x, P(x) holds" is equivalent to
"There exists an x for which P(x) is not true“

b) ~(x P(x)) and x: ~P(x)

"It is not true that there exists an x for which P(x) is true" is
equivalent to "For all x, P(x) is not true"
66
 Rules of inference for
quantified statements
2. Universal generalization
 If p(x) is proved to be true for a
 generic element in the universe of discourse, then ∀x p(x)
is true; i.e.:
 p(x)
 ∴∀x p(x)

4. Existential generalization
 If p(a) is true for some specific element a in the universe of
discourse, then ∃x p(x) is true; i.e.:
 p(a)
 ∴∃x p(x)
67
 Rules of inference for
quantified statements
1. Universal instantiation
 If ∀x p(x) is true, then p(a) is true for
 each specific element a in the universe of discourse; i.e.:
 ∀x p(x)
 ∴p(a)
 For instance, from ∀x(x+1 = 1+x) we can derive 7+1 = 1+7.

3. Existential instantiation
 If ∃x p(x) is true, then p(a) is true for
 some specific element a in the universe of discourse; i.e.:
 ∃x p(x)
 ∴p(a) 68
 Equivalences and Implications
for quantified statements
For a prescribed universe and any open statements
P(x) and q(x) in the variable x:
x [p(x)  q(x)]  [x p(x)  x q(x)]

x [p(x)  q(x)]  [x p(x)  x q(x)]

x [p(x)  q(x)]  [x p(x)  x q(x)]

[x p(x)  x q(x)]  x [p(x)  q(x)]

69
 Demonstrate Universally Quantified
Statement
In order to prove the In order to prove the
universally quantified universally quantified
statement x P(x) is true statement x P(x) is false
◼ It is not enough to show ◼ It is enough to exhibit
P(x) true for some x  D. some x  D for which
P(x) is false.
◼ You must show P(x) is
true for every x  D. ◼ This x is called the
counterexample to the
statement x P(x) is true.

70
 Axioms
An axiom is a proposition accepted as true without proof
within the mathematical system.

There are many examples of axioms in mathematics:

Example: In Euclidean geometry the following are axioms

Given two distinct points, there is exactly one line that

contains them.

Given a line and a point not on the line, there is exactly

one line through the point which is parallel to the line.
71
 Axioms
AXIOM OF EXTENSION AXIOM OF REPLACEMENT
If two sets have the same If we apply a function to
elements, then they are every element in a set, the
equal. answer is still a set.

POWER SET AXIOM

UNION AXIOM
Given any set, we can form
We can form the union of two
the set of all subsets (the
or more sets.
power set).

72
 Theorems

A theorem is a proposition of the form p → q which

must be shown to be true by a sequence of logical
steps that assume that p is true, and
use definitions,
axioms and
previously proven theorems.

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

73
 Lemmas and corollaries

A lemma is a small theorem which is used to prove a

bigger theorem.

A corollary is a theorem that can be proven to be a

logical consequence of another theorem.

Example from Euclidean geometry:

"If the three sides of a triangle have equal length, then its
angles also have equal measure."

74
 Lemmas and corollaries

Less important theorems are sometimes called propositions.

A conjecture is a statement that is being proposed to be true.

Once a proof of a conjecture is found, it becomes a theorem.

It may turn out to be false.

75
 Types of proof

A proof is a logical argument that consists of a series of

steps using propositions in such a way that the truth of
the theorem is established.

◼ Direct proof
◼ Indirect proof

76
 Direct proof
Direct proof: p → q
A direct method of attack that assumes the truth of
proposition p, axioms and proven theorems so that the truth
of proposition q is obtained.
Example: For all real numbers d, d1, d2, and x, if d=min{d1,d2}
and xd, then xd1 and xd2.

Proof. From the definition of min, it follows that dd1 and

dd2.
From xd and dd1, we may derive xd1 by the
transitive property of .
From xd and dd2, we may derive xd2 by the same
property.
Therefore, xd1 and xd2. 77
 Direct proof

In direct proof, we show that conditional 𝑝 → 𝑞 is true.

We assume that 𝑝 is true and show that 𝑞 must be true.

Definition: The integer 𝑛 is even if there exists an integer 𝑘

such that 𝑛 = 2𝑘, and 𝑛 is odd if there exists an integer 𝑘,
such that 𝑛 = 2𝑘 + 1.

Note that every integer is either even or odd and no integer is

both even and odd.

Example: −21 is odd since −21 = 2(−11) + 1;

0 is even since 0 = 2(0)
78
 Indirect proof
The method of proof by contradiction of a theorem p → q
consists of the following steps:
1. Assume p is true and q is false.

2. Show that ~p is also true.

3. Then we have that p ^ (~p) is true.

4. But this is impossible, since the statement p ^ (~p) is

always false. There is a contradiction!

[Link], q cannot be false and therefore it is true.

Or show that the contrapositive (~q)→(~p) is true.
Since (~q) → (~p) is logically equivalent to p → q, then 79the
theorem is proved.
 Example of Indirect proof

For all real numbers x and y, if x+y2, then either x1 or y1.

Proof. Assume that x + y  2, x < 1 and y < 1.

Then it follows that x + y < 1 + 1 = 2. It contradicts to the

assumption x + y  2.

Thus, we conclude that x1 or y1.

80