Propositional Logic

and
Proof
Nakib Hayat Chowdhury
Assistant Professor, Dept. of CSE, BAUST

Every extraordinary feet began in ordinary circumstances. I will start my journey of success from where I am 1now.
 License

Your are free –

– to Share – to copy, distribute and transmit the work
– to Remix – to adapt the work

For non commercial and educational purpose.

2
 References

Discrete Mathematics and its Applications by Kenneth H. Rosen

• Chapter 1 : The Foundation : Logic and Proof

Discrete Mathematics by Seymour Lipschutz, Marc Lipso

• Chapter 4 : Logic and Propositional Calculas

3
 Today’s Topics

• Basic Propositional Logic

• Variable Based Propositional Logic
• Rules of Inference
• Proof Technique

4
 Proposition
Definition
A proposition is a declarative sentence (that is, a sentence that
declares a fact) that is either true or false, but not both.

Example
• Washington, D.C., is the capital of the United States of America
• Dhaka is the capital of Bangladesh
• Dhaka is the capital of India
• 8 + 2 = 10
• 4 + 4 = 10
5
Proposition or Not?

• What time is it?

• Read this carefully.
• a + 2 = 10
• x+y =z

6
 Propositional Variable
Definition
variables that represent propositions, just as letters are used to denote
numerical variables.

The conventional letters used for propositional variables are p, q, r, s, ... .

Example :
p = Dhaka is the capital of Bangladesh.

7
 Some common terms
The truth value
The truth value of a proposition is true, denoted by T, if it is a true
proposition, and the truth value of a proposition is false, denoted by F, if
it is a false proposition.

p = Dhaka is the capital of Truth value : T

Bangladesh.
p = Dhaka is the capital of Truth value : F
Pakistan.

8
 Some common terms
Propositional Calculus or Propositional Logic.
The area of logic that deals with propositions is called the propositional
calculus or propositional logic.

Compound Propositions
New propositions formed from existing propositions using logical
operators are called compound propositions.

9
Introduction to Logical Operators
• About a dozen logical operators
• Similar to algebraic operators + * - /

Basic Operators

1. Negation (NOT)

2. Conjunction (AND)

3. Disjunction (OR)

10
 Logical operators: Not
Definition
A “not” operation switches (negates) the truth value.
Symbol:  or ~

Truth table
• If
P p
• ?
T F
F T

11
 Logical operators: And
Definition
An “and” operation is true if both operands are true.
Symbol: 

p q pq
p = “Today is Friday”
T T T
q = “Today is my birthday”
T F F
pq = ?
F T F
pq = “Today is Friday and today is my birthday”
F F F
12
 Logical operators: Or
Definition

An “or” operation is true if either operands or both are true.

Symbol: 
p q pq
p = “Today is Friday”
T T T
q = “Today is my birthday”
T F T
pq=?
F T T
p  q = “Today is Friday or today is my birthday”
F F F
13
More Logical Operators

More Operators

1. Exclusive OR

2. Conditional

3. Bicondition

14
Logical operators: Exclusive Or
Definition
Let p and q be propositions. The exclusive or of p and q, denoted by
p⊕q, is the proposition that is true when exactly one of p and q is true
and is false otherwise.

• Symbol:  p q pq
• Often called XOR T T F
• pq  (p  q)  ¬(p  q)
T F T
F T T
pq = “Today is Friday or today is my birthday, but not both”
F F F
15
Logical operators: Conditional
Definition
Let p and q be propositions. The conditional statement p→q is the
proposition “if p, then q.” The conditional statement p→q is false when
p is true and q is false, and true otherwise.
• p implies q
pq = “If today is Friday, then today is my birthday” • If p, q
• p only if q
• In the conditional statement p→q, • p is sufficient for q
• p is called the hypothesis (or antecedent or premise) • q if p
• q is called the conclusion (or consequence)
• q whenever p
• q is necessary for p
16
 Logical operators: Conditional
• p → q = ¬p q p q pq

the the
T T T
antecedent consequence
T F F
I will do
F T T only for
Let, p = “Maria learns discrete mathematics” and
myself
q = “Maria will find a good job.” F F T
Express the statement p→q as a statement in
English.
If I am elected,
then I will lower
taxes.
Logical operators: Bi-Conditional
Definition
Let p and q be propositions. The biconditional statement p↔q is the
proposition “p if and only if q.” The biconditional statement p↔q is true
when p and q have the same truth values, and is false otherwise.
Biconditional statements are also called bi-implications.

• “p is necessary and sufficient for q”

• “if p then q, and conversely”
• “p iff q.”

18
Logical operators: Bi-Conditional
• True when both has same truth values and otherwise false.
• Alternatively, it means “(if p then q) and (if q then p)” p q pq
(p→q)∧ (q→p). T T T
• Note that a bi-conditional has the opposite truth values T F F
of the exclusive or
F T F
F F T
• Let p = “You take this class” and q = “You get a grade”
• pq = “You take this class if and only if you get a grade”
• Alternatively, it means “If you take this class, then you get a
grade and if you get a grade then you take (took) this class”
Truth Tables of Compound Propositions
Example
Construct the truth table of the compound proposition
(p∨¬q)→(p∧q).

20
Boolean operators summary
and or xor conditional Bi-conditional
p q pq pq pq pq pq
T T T T F T T
T F F T T F F
F T F T T T F
F F F F F T T

Learn what they mean, don’t just memorize the table!

21
 Precedence of operators

• Just as in algebra, operators have precedence

4+3*2 = ?
 4+3*2 = 4+(3*2)

 4+3*2 = (4+3)*2

22
 Precedence of operators
• p  q  ¬r → s ↔ t = ?
Operators Precedence

¬ 1
=(p  (q  (¬r)) → s) ↔ (t)  2
 3
• First three are the most
important → 4

• Not is always performed ↔ 5

before any other operation
Logic and Bit Operations

24
Applications of Propositional Logic

• Translating English Sentences

• System Specifications
• Boolean Searches
• Logic Puzzles
• Logic Circuits

25
Translating English Sentences
Example
p = “It is below freezing”
q = “It is snowing”
It is below freezing and it is snowing pq
It is below freezing but not snowing p¬q

If it is below freezing, it is also snowing p→q

It is either below freezing or it is snowing, but it is not
snowing if it is below freezing (pq)(p→¬q)

That it is below freezing is necessary and sufficient for it to p↔q

be snowing
26
Translating English Sentences
Problem: 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.”

Solve:
Let, a = “You can access the Internet from campus,”
c = “You are a computer science major,” and
d = “You are a freshman,”

Then the statement can be represented as a → (c ∨ ¬f).

27
Translating English Sentences
Problem: 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.”

Solve:
Let, a = “You can access the Internet from campus,”
c = “You are a computer science major,” and
f = “You are a freshman,”

Then the statement can be represented as a → (c ∨ ¬f).

28
Translating English Sentences
How can this English sentence be translated into a logical expression?
“You can not 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,” respectively. Then the sentence can
be translated to (r ∧ ¬s) → ¬q.

29
Propositional Equivalences

Back to the Future

 Back to the Future
Propositional Calculus or Propositional Logic.
The area of logic that deals with propositions is called the propositional
calculus or propositional logic.

Compound Propositions
New propositions formed from existing propositions using logical
operators are called compound propositions.

31
 Some Common Terms
Tautology
A compound proposition that is always true, no matter what the truth values of the
propositional variables that occur in it, is called a tautology.

Contradiction
A compound proposition that is always false is called a contradiction.

Contingency
A compound proposition that is neither a tautology nor a contradiction is called a
contingency.
32
 Example
Tautology
p  ¬p

Contradiction
p  ¬p

Contingency
p  ¬p

33
 Tautology
Demonstrate that
[¬p (p q )]q
is a tautology in two ways:
1. Using a truth table – show that [¬p (p q )]q is always true
2. Using a proof (will get to this later).

34
 Tautology by truth table

p q ¬p p q ¬p (p q ) [¬p (p q )]q

T T

T F

F T

F F

L3 35
 Tautology by truth table

p q ¬p p q ¬p (p q ) [¬p (p q )]q

T T F

T F F

F T T

F F T

L3 36
 Tautology by truth table

p q ¬p p q ¬p (p q ) [¬p (p q )]q

T T F T

T F F T

F T T T

F F T F

L3 37
 Tautology by truth table

p q ¬p p q ¬p (p q ) [¬p (p q )]q

T T F T F

T F F T F

F T T T T

F F T F F

L3 38
 Tautology by truth table

p q ¬p p q ¬p (p q ) [¬p (p q )]q

T T F T F T

T F F T F T

F T T T T T

F F T F F T

L3 39
 Propositional Equivalences
Definition

• Compound propositions that have the same truth values in all possible cases are
called logically equivalent.

40
Propositional Equivalences : How to Prove?

• Two methods:
– Using truth tables
• Not good for long formula
• In this course, only allowed if specifically stated!
– Using the logical equivalences
• The preferred method
• p q  ¬q¬p
• (p  r)  (q  r)  (p  q)  r
Logical Equivalence Using Truth Table

The easiest way to check for logical equivalence is to

see if the truth tables of both variants have
identical last columns. (p q  ¬q¬p)

p q p q p q ¬q ¬p ¬q¬p

L3 42
Logical Equivalence Using Truth Table

The easiest way to check for logical equivalence is to

see if the truth tables of both variants have
identical last columns: (p q  ¬q¬p)

p q p q p q ¬q ¬p ¬q¬p
T T T
T F F
F T T
F F T

L3 43
Logical Equivalence Using Truth Table

The easiest way to check for logical equivalence is to

see if the truth tables of both variants have
identical last columns: (p q  ¬q¬p)

p q p q p q ¬q ¬p ¬q¬p
T T T T T
T F F T F
F T T F T
F F T F F

L3 44
Logical Equivalence Using Truth Table

The easiest way to check for logical equivalence is to

see if the truth tables of both variants have
identical last columns: (p q  ¬q¬p)

p q p q p q ¬q ¬p ¬q¬p
T T T T T F
T F F T F T
F T T F T F
F F T F F T

L3 45
Logical Equivalence Using Truth Table

The easiest way to check for logical equivalence is to

see if the truth tables of both variants have
identical last columns: (p q  ¬q¬p)

p q p q p q ¬q ¬p ¬q¬p
T T T T T F F
T F F T F T F
F T T F T F T
F F T F F T T

L3 46
Logical Equivalence Using Truth Table

The easiest way to check for logical equivalence is to

see if the truth tables of both variants have
identical last columns: (p q  ¬q¬p)

p q p q p q ¬q ¬p ¬q¬p
T T T T T F F T
T F F T F T F F
F T T F T F T T
F F T F F T T T

L3 47
Propositional Equivalences : How to Prove?

• Two methods:
– Using truth tables
• Not good for long formula
• In this course, only allowed if specifically stated!
– Using the logical equivalences
• The preferred method
• p q  ¬q¬p
• (p  r)  (q  r)  (p  q)  r
 Truth Table Solution
• (p  r)  (q  r)  (p  q)  r
p q r p→r q →r pq (p→r)(q →r) (pq) →r

T T T T T T T T
T T F F F T F F
T F T T T F T T
T F F F T F T T
F T T T T F T T
F T F T F F T T
F F T T T F T T
F F F T T F T T
 Logical Equivalences
pTp (p  q)  r  p  (q  r)
Identity Laws Associative laws
pFp (p  q)  r  p  (q  r)

pTT p  (q  r)  (p  q)  (p  r)
Domination Law Distributive laws
pFF p  (q  r)  (p  q)  (p  r)

ppp Idempotent  (p  q)   p   q
De Morgan’s laws
ppp Laws  (p  q)   p   q

Double p  (p  q)  p
( p)  p negation law
Absorption laws
p  (p  q)  p

pqqp Commutative ppT

Negation lows
pqqp Laws ppF

Definition of Definition of
pq  pq Implication p  q  (p  q)  (q  p) Bi-conditional
Logical Equivalences

51
Proof using Logical Equivalence
(p  r)  (q  r)
 ( p  r)  ( q  r) Definition of implication
prqr Associative
pqrr Commutative
 ( p   q)  (r  r) Associative
  (p  q)  r De Morgan, Idempotent
 (p  q)  r Definition of implication
Logical Equivalences
Example : Example
• Show that (p  q)  (p  q) is a Tautology. (Proof)

(p  q)  (p  q)
 (p  q)  (p  q) Implication

 ( p   q)  (p  q) De Morgan

 ( p  p)  ( q  q) Commutative, Associative

TT Negation

T Identity
 Tautology by
Tautology byproof
proof
[¬p (p q )]q
 [(¬p p)(¬p q)]q Distributive

L3 54
 Tautology by
Tautology byproof
proof
[¬p (p q )]q
 [(¬p p)(¬p q)]q Distributive
 [ F  (¬p q)]q ULE

L3 55
 Tautology by
Tautology byproof
proof
[¬p (p q )]q
 [(¬p p)(¬p q)]q Distributive
 [ F  (¬p q)]q ULE
 [¬p q ]q Identity

L3 56
 Tautology by
Tautology byproof
proof
[¬p (p q )]q
 [(¬p p)(¬p q)]q Distributive
 [ F  (¬p q)]q ULE
 [¬p q ]q Identity
 ¬ [¬p q ]  q ULE

L3 57
 Tautology by
Tautology byproof
proof
[¬p (p q )]q
 [(¬p p)(¬p q)]q Distributive
 [ F  (¬p q)]q ULE
 [¬p q ]q Identity
 ¬ [¬p q ]  q ULE
 [¬(¬p) ¬q ]  q DeMorgan

L3 58
 Tautology by
Tautology byproof
proof
[¬p (p q )]q
 [(¬p p)(¬p q)]q Distributive
 [ F  (¬p q)]q ULE
 [¬p q ]q Identity
 ¬ [¬p q ]  q ULE
 [¬(¬p) ¬q ]  q DeMorgan
 [p  ¬q ]  q Double Negation

L3 59
 Tautology by
Tautology byproof
proof
[¬p (p q )]q
 [(¬p p)(¬p q)]q Distributive
 [ F  (¬p q)]q ULE
 [¬p q ]q Identity
 ¬ [¬p q ]  q ULE
 [¬(¬p) ¬q ]  q DeMorgan
 [p  ¬q ]  q Double Negation
 p  [¬q q ] Associative

L3 60
 Tautology by
Tautology byproof
proof
[¬p (p q )]q
 [(¬p p)(¬p q)]q Distributive
 [ F  (¬p q)]q ULE
 [¬p q ]q Identity
 ¬ [¬p q ]  q ULE
 [¬(¬p) ¬q ]  q DeMorgan
 [p  ¬q ]  q Double Negation
 p  [¬q q ] Associative
 p  [q ¬q ] Commutative

L3 61
 Tautology by
Tautology byproof
proof
[¬p (p q )]q
 [(¬p p)(¬p q)]q Distributive
 [ F  (¬p q)]q ULE
 [¬p q ]q Identity
 ¬ [¬p q ]  q ULE
 [¬(¬p) ¬q ]  q DeMorgan
 [p  ¬q ]  q Double Negation
 p  [¬q q ] Associative
 p  [q ¬q ] Commutative
pT ULE

L3 62
 Tautology by
Tautology byproof
proof
[¬p (p q )]q
 [(¬p p)(¬p q)]q Distributive
 [ F  (¬p q)]q ULE
 [¬p q ]q Identity
 ¬ [¬p q ]  q ULE
 [¬(¬p) ¬q ]  q DeMorgan
 [p  ¬q ]  q Double Negation
 p  [¬q q ] Associative
 p  [q ¬q ] Commutative
pT ULE
T Domination

L3 63
 What can’t we say?
• Quantification: every student has a father.
• Relations: If X is married to Y, then Y is
married to X.
• Probability: There is an 80% chance of rain.
• Combine Evidence: This car is better than
that one because…
• Uncertainty: Maybe John is playing golf.
Predicates (Propositional Function)
and
Quantifiers
Predicates (Propositional Function)

• So far we can represent the statement – “10 > 100” or “10 <= 100”
• But we can’t represent - “x > 3,” “x = y + 3,” “x + y = z,”
• Can represent – “Jorna knows C programming.”
• Can’t represent – “X knows C programming.”
• Can’t represent – “Every student know C programming.”
• Can’t represent – “At least one student know C programming.”

66
Predicates : “x is greater than 3”
“x is greater than 3” has two parts
• “x is greater than 3” – the variable x, is the subject of the statement.
• “x is greater than 3” – the predicate, refers to a property that the
subject of the statement can have.

• We can denote the statement “x is greater than 3” by P(x),

• Where P denotes the predicate “is greater than 3” and
• x is the variable.
67
Predicates : “x is greater than 3”
• We can denote the statement “x is greater than 3” by P(x),
• Where P denotes the predicate “is greater than 3” and
• x is the variable.
• The statement P(x) is also said to be the value of the propositional function P at x.

• Once a value has been assigned to the variable x, the statement P(x) becomes a
proposition and has a truth value.

Q: Let P(x) denote the statement “x > 3.” What are the truth values of P(4) and P(2)?

68
 Predicates : Some Example

Example 1
Let Q(x, y) denote the statement “x = y + 3.” What are the truth values of the
propositions Q(1, 2)and Q(3, 0)?

Example 3

Let R(x, y, z) denote the statement “x + y = z.” What are the truth values of the
propositions R(1,2,3) and R(0,0,1)?

69
 Quantifiers
What is it?
Quantification is a way to create a proposition from a propositional
function (predicate).
Quantification expresses the extent to which a predicate is true over a
range of elements.

• English words all, some, many, none, and few are used in quantifications.

70
Quantifiers : Types

• THE UNIVERSAL QUANTIFIER

• THE EXISTENTIAL QUANTIFIER

71
 The Universal Quantifier

Definition

72
The Universal Quantifier : True/False?

Statement When True? When False?

∀x P(x) P(x) is true for every x There is an x for which P(x) is false.

P(x) = “Student x knows C programming.” Domain : This Class!

When true? If every student knows programming

When false? If a least one student does not know

73
 The Existential Quantifier

Definition

74
The Existential Quantifier : True/False?

Statement When True? When False?

∃x P(x) There is an x for which P(x) is true. P(x) is false for every x.

P(x) = “Student x knows C programming.” Domain : This Class!

When true? If at least one student knows programming

When false? If a every student does not know

75
Summarize

76
 Quantifiers : Example
Let Q(x) be the statement “x < 2.” What is the truth value of the quantification ∀x
Q(x), where the domain consists of all real numbers?

Solution : Q(x) is not true for every real number x, because, for instance, Q(3) is false.
That is, x = 3 is a counter example for the statement ∀x Q(x). Thus ∀x Q(x) is false.

Let P(x) denote the statement “x > 3”. What is the truth value of the quantification ∃x P (x),
where the domain consists of all real numbers?

Solution : Because “ x > 3” is sometimes true—for instance, when x = 4, the

existential quantification of P(x), which is ∃x P(x), is true.

77
Negating Quantified Expressions
P(x) = “Student x in your class has taken a course in calculus.”

• ∀x P(x) = “Every student in your class has taken a course in calculus.”

• ∃x P(x) = “At least one student in this class has taken a course in calculus.”

• ∀x P(x)
• ∃x P(x)

• ∀x P(x)
• ∃x P(x)
78
Negating Quantified Expressions

79
Applications Area

• Translating English Sentences

• System Specifications
• Boolean Searches
• Logic Puzzles
• Logic Circuits

80
Translating English Sentences
Express the statement “Every student in this class has studied calculus” using predicates
and quantifiers.

• Rewrite: “For every student in this class, that student has studied calculus.”
• Use variable x : “For every student x in this class, x has studied calculus.”
• C(x), which is the statement “x has studied calculus.”
• ∀x C(x) [OK, if the domain for x consists of the students in the class]

81
Translating English Sentences
Express the statement “Every student in this class has studied calculus” using predicates
and quantifiers.

• “For every person x, if person x is a student in this class then x has studied calculus.”
• If S(x) represents the statement that person x is in this class.
• ∀x (S(x) → C(x))

82
 Multivariable Predicates
M(X, Y) : X has emailed Y

• ∀X ∀Y M(X, Y)

• ∀X ∃Y M(X, Y)

• ∃X ∀Y M(X, Y)

• ∃X ∃Y M(X, Y)

83
Multi Variable Quantifier Negation
M(X, Y) : X has emailed Y

• ∀X ∀Y M(X, Y) X ∃Y M(X, Y)

• ∀X ∃Y M(X, Y) X Y M(X, Y)

• ∃X ∀Y M(X, Y) X Y M(X, Y)

• ∃X ∃Y M(X, Y) X Y M(X, Y)

84
Multi Variable Quantifier Negation
De-Morgans Law
¬(∀ 𝑥 ∀ 𝑦 𝑃 ( 𝑥 , 𝑦 ) ⋀ Q ( x , y )) ≡∃ 𝑥 ∃ 𝑦 ¬𝑝(𝑥 , 𝑦)⋁ ¬𝑄(𝑥, 𝑦)

85
Rules of Inference

Example from
Book!!!
86
Rules of Inference for Quantified
Statements

Example from
Book!!!
87
 Fallacy
Looks OK but Not OK!!!

88
Proof Techniques
 Some Terminology
Theorem
A theorem is a statement that can be shown to be true. In mathematical
writing, the term theorem is usually reserved for a statement that is
considered at least somewhat important.

Propositions
Less important theorems sometimes are called propositions.

90
 Some Terminology
lemma
A less important theorem that is helpful in the proof of other results is
called a lemma.

Proof
A proof is a valid argument that establishes the truth of a theorem.

91
 Proof Techniques
General Techniques
• Direct Proof
• Proof by Contraposition (Indirect Proof)
• Proof by Contradiction

The square of an even number is even.

92
The square of an even number is even.

Direct Proof
Proof: N even N2 is even
Assume N is even. Then,
N = 2K
N2 = (2K)2
N2 = 4K2
N2 = 2.2K2 (this is an even number)

Hence, the square of an even number is even. (Proofed)

93
 Proof Techniques
Proof by Contraposition
Sometime we can not provide direct proof.

If N2 is even then N is even.

94
 The square of an even number is even
(Indirect Proof )
PROVE: The square of an even number is
even. (Ex. 1.16.b)
1. Suppose k 2 is not even.

L14 95
 The square of an even number is even
(Indirect Proof )
PROVE: The square of an even number is
even. (Ex. 1.16.b)
1. Suppose k 2 is not even.
2. So k 2 is odd.

L14 96
 The square of an even number is even
(Indirect Proof )
PROVE: The square of an even number is
even. (Ex. 1.16.b)
1. Suppose k 2 is not even.
2. So k 2 is odd.
3. n k 2 = 2n + 1

L14 97
 The square of an even number is even
(Indirect Proof )
PROVE: The square of an even number is
even. (Ex. 1.16.b)
1. Suppose k 2 is not even.
2. So k 2 is odd.
3. n k 2 = 2n + 1
4. n k 2 - 1 = 2n

L14 98
 The square of an even number is even
(Indirect Proof )
PROVE: The square of an even number is
even. (Ex. 1.16.b)
1. Suppose k 2 is not even.
2. So k 2 is odd.
3. n k 2 = 2n + 1
4. n k 2 - 1 = 2n
5. n (k - 1)(k + 1) = 2n

L14 99
 The square of an even number is even
(Indirect Proof )
PROVE: The square of an even number is even. (Ex.
1.16.b)
1. Suppose k 2 is not even.
2. So k 2 is odd.
3. n k 2 = 2n + 1
4. n k 2 - 1 = 2n
5. n (k - 1)(k + 1) = 2n
6. (k - 1)(k + 1) | 2 = n

L14 100
 The square of an even number is even
(Indirect Proof )
PROVE: The square of an even number is even. (Ex.
1.16.b)
1. Suppose k 2 is not even.
2. So k 2 is odd.
3. n k 2 = 2n + 1
4. n k 2 - 1 = 2n
5. n (k - 1)(k + 1) = 2n
6. (k - 1)(k + 1) | 2 = n
7. (k - 1) | 2  (k + 1) | 2 since 2 is prime

L14 101
 The square of an even number is even
(Indirect Proof )
PROVE: The square of an even number is even. (Ex.
1.16.b)
1. Suppose k 2 is not even.
2. So k 2 is odd.
3. n k 2 = 2n + 1
4. n k 2 - 1 = 2n
5. n (k - 1)(k + 1) = 2n
6. (k - 1)(k + 1) | 2 = n
7. (k - 1) | 2  (k + 1) | 2 since 2 is prime
8. a k - 1 = 2a  b k+1 = 2b
L14 102
 The square of an even number is even
(Indirect Proof )
PROVE: The square of an even number is even. (Ex.
1.16.b)
1. Suppose k 2 is not even.
2. So k 2 is odd.
3. n k 2 = 2n + 1
4. n k 2 - 1 = 2n
5. n (k - 1)(k + 1) = 2n
6. (k - 1)(k + 1) | 2 = n
7. (k - 1) | 2  (k + 1) | 2 since 2 is prime
8. a k - 1 = 2a  b k+1 = 2b
9. a k = 2a + 1  b k = 2b – 1
L14 103
 The square of an even number is even
(Indirect Proof )
PROVE: The square of an even number is even. (Ex.
1.16.b)
1. Suppose k 2 is not even.
2. So k 2 is odd.
3. n k 2 = 2n + 1
4. n k 2 - 1 = 2n
5. n (k - 1)(k + 1) = 2n
6. (k - 1)(k + 1) | 2 = n
7. (k - 1) | 2  (k + 1) | 2 since 2 is prime
8. a k - 1 = 2a  b k+1 = 2b
9. a k = 2a + 1  b k = 2b – 1
L14
10. In both cases k is odd 104
 The square of an even number is even
(Indirect Proof )
PROVE: The square of an even number is even. (Ex. 1.16.b)
1. Suppose k 2 is not even.
2. So k 2 is odd.
3. n k 2 = 2n + 1
4. n k 2 - 1 = 2n
5. n (k - 1)(k + 1) = 2n
6. (k - 1)(k + 1) | 2 = n
7. (k - 1) | 2  (k + 1) | 2 since 2 is prime
8. a k - 1 = 2a  b k+1 = 2b
9. a k = 2a + 1  b k = 2b – 1
10. In both cases k is odd
11. So k is not even

L14 105
 Direct Proof : Example
PROVE: kZ k 1(mod 3)  k 31(mod 9)

L14 106
 Direct Proof : Example
PROVE: kZ k 1(mod 3)  k 31(mod 9)
1. k 1(mod 3)

L14 107
 Direct Proof : Example
PROVE: kZ k 1(mod 3)  k 31(mod 9)
1. k 1(mod 3)
2. n k-1 = 3n

L14 108
 Direct Proof : Example
PROVE: kZ k 1(mod 3)  k 31(mod 9)
1. k 1(mod 3)
2. n k-1 = 3n
3. n k = 3n + 1

L14 109
 Direct Proof : Example
PROVE: kZ k 1(mod 3)  k 31(mod 9)
1. k 1(mod 3)
2. n k-1 = 3n
3. n k = 3n + 1
4. n k 3 = (3n + 1)3

L14 110
 Direct Proof : Example
PROVE: kZ k 1(mod 3)  k 31(mod 9)
1. k 1(mod 3)
2. n k-1 = 3n
3. n k = 3n + 1
4. n k 3 = (3n + 1)3
5. n k 3 = 27n 3 + 27n 2 + 9n + 1

L14 111
 Direct Proof : Example
PROVE: kZ k 1(mod 3)  k 31(mod 9)
1. k 1(mod 3)
2. n k-1 = 3n
3. n k = 3n + 1
4. n k 3 = (3n + 1)3
5. n k 3 = 27n 3 + 27n 2 + 9n + 1
6. n k 3-1 = 27n 3 + 27n 2 + 9n

L14 112
 Direct Proof : Example
PROVE: kZ k 1(mod 3)  k 31(mod 9)
1. k 1(mod 3)
2. n k-1 = 3n
3. n k = 3n + 1
4. n k 3 = (3n + 1)3
5. n k 3 = 27n 3 + 27n 2 + 9n + 1
6. n k 3-1 = 27n 3 + 27n 2 + 9n
7. n k 3-1 = (3n 3 + 3n 2 + n)·9

L14 113
 Direct Proof : Example
PROVE: kZ k 1(mod 3)  k 31(mod 9)
1. k 1(mod 3)
2. n k-1 = 3n
3. n k = 3n + 1
4. n k 3 = (3n + 1)3
5. n k 3 = 27n 3 + 27n 2 + 9n + 1
6. n k 3-1 = 27n 3 + 27n 2 + 9n
7. n k 3-1 = (3n 3 + 3n 2 + n)·9
8. m k 3-1 = m·9

L14 114
 Direct Proof : Example
PROVE: kZ k 1(mod 3)  k 31(mod 9)
1. k 1(mod 3)
2. n k-1 = 3n
3. n k = 3n + 1
4. n k 3 = (3n + 1)3
5. n k 3 = 27n 3 + 27n 2 + 9n + 1
6. n k 3-1 = 27n 3 + 27n 2 + 9n
7. n k 3-1 = (3n 3 + 3n 2 + n)·9
8. m k 3-1 = m·9
9. k 31(mod 9)

L14 115
 Contradiction Proof : Example
Proof that (
Proof: Assume is rational.
Then . Where and are relatively prime numbers (a and b have no common factors)
and .
So,

But since is even. a must be even as well, since the square of a even number is also
even. Then we have

The same argument can be applied to to find . However, this contradicts the original
assumption that a and b are relatively prime, and the above is impossible. Therefore,
we must conclude that is irrational.
L14 116