Discrete Mathematics 1

Chapter 1: The Foundations: Logic and Proofs

Department of Mathematics
The FPT university

TrungDT (FUHN) MAD111 Chapter 1 1 / 29

0. Course Introduciton

TrungDT (FUHN) MAD111 Chapter 1 2 / 29

0. Course Introduciton

Course name: Discrete Mathematics 1 (MAD111)

TrungDT (FUHN) MAD111 Chapter 1 2 / 29

0. Course Introduciton

Course name: Discrete Mathematics 1 (MAD111)

Textbook: Discrete Mathematics and its applications, 6th edition,

K. Rosen

TrungDT (FUHN) MAD111 Chapter 1 2 / 29

0. Course Introduciton

Course name: Discrete Mathematics 1 (MAD111)

Textbook: Discrete Mathematics and its applications, 6th edition,

K. Rosen

Topics covered:

TrungDT (FUHN) MAD111 Chapter 1 2 / 29

0. Course Introduciton

Course name: Discrete Mathematics 1 (MAD111)

Textbook: Discrete Mathematics and its applications, 6th edition,

K. Rosen

Topics covered:

Chapter 1: Logic and Proofs

TrungDT (FUHN) MAD111 Chapter 1 2 / 29

0. Course Introduciton

Course name: Discrete Mathematics 1 (MAD111)

Textbook: Discrete Mathematics and its applications, 6th edition,

K. Rosen

Topics covered:

Chapter 1: Logic and Proofs

Chapter 2: Sets, Functions, Sequences, and Sums

TrungDT (FUHN) MAD111 Chapter 1 2 / 29

0. Course Introduciton

Course name: Discrete Mathematics 1 (MAD111)

Textbook: Discrete Mathematics and its applications, 6th edition,

K. Rosen

Topics covered:

Chapter 1: Logic and Proofs

Chapter 2: Sets, Functions, Sequences, and Sums
Chapter 3: Algorithms and the Integers

TrungDT (FUHN) MAD111 Chapter 1 2 / 29

0. Course Introduciton

Course name: Discrete Mathematics 1 (MAD111)

Textbook: Discrete Mathematics and its applications, 6th edition,

K. Rosen

Topics covered:

Chapter 1: Logic and Proofs

Chapter 2: Sets, Functions, Sequences, and Sums
Chapter 3: Algorithms and the Integers
Chapter 4: Induction and Recursion

TrungDT (FUHN) MAD111 Chapter 1 2 / 29

0. Course Introduciton

Course name: Discrete Mathematics 1 (MAD111)

Textbook: Discrete Mathematics and its applications, 6th edition,

K. Rosen

Topics covered:

Chapter 1: Logic and Proofs

Chapter 2: Sets, Functions, Sequences, and Sums
Chapter 3: Algorithms and the Integers
Chapter 4: Induction and Recursion
Chapter 5: Counting

TrungDT (FUHN) MAD111 Chapter 1 2 / 29

0. Course Introduciton

Course name: Discrete Mathematics 1 (MAD111)

Textbook: Discrete Mathematics and its applications, 6th edition,

K. Rosen

Topics covered:

Chapter 1: Logic and Proofs

Chapter 2: Sets, Functions, Sequences, and Sums
Chapter 3: Algorithms and the Integers
Chapter 4: Induction and Recursion
Chapter 5: Counting
Chapter 6: Discrete Probability

TrungDT (FUHN) MAD111 Chapter 1 2 / 29

0. Course Introduciton

Course name: Discrete Mathematics 1 (MAD111)

Textbook: Discrete Mathematics and its applications, 6th edition,

K. Rosen

Topics covered:

Chapter 1: Logic and Proofs

Chapter 2: Sets, Functions, Sequences, and Sums
Chapter 3: Algorithms and the Integers
Chapter 4: Induction and Recursion
Chapter 5: Counting
Chapter 6: Discrete Probability
Chapter 7: Advanced Counting Techniques

TrungDT (FUHN) MAD111 Chapter 1 2 / 29

Chapter 1: Introduction

TrungDT (FUHN) MAD111 Chapter 1 3 / 29

Chapter 1: Introduction

Topics covered:

TrungDT (FUHN) MAD111 Chapter 1 3 / 29

Chapter 1: Introduction

Topics covered:

1.1 Propositional Logic

TrungDT (FUHN) MAD111 Chapter 1 3 / 29

Chapter 1: Introduction

Topics covered:

1.1 Propositional Logic

1.2 Propositional Equivalences

TrungDT (FUHN) MAD111 Chapter 1 3 / 29

Chapter 1: Introduction

Topics covered:

1.1 Propositional Logic

1.2 Propositional Equivalences
1.3 Predicates and Quantifiers

TrungDT (FUHN) MAD111 Chapter 1 3 / 29

Chapter 1: Introduction

Topics covered:

1.1 Propositional Logic

1.2 Propositional Equivalences
1.3 Predicates and Quantifiers
1.4 Nested Quantifiers

TrungDT (FUHN) MAD111 Chapter 1 3 / 29

Chapter 1: Introduction

Topics covered:

1.1 Propositional Logic

1.2 Propositional Equivalences
1.3 Predicates and Quantifiers
1.4 Nested Quantifiers
1.5 Rules of Inference

TrungDT (FUHN) MAD111 Chapter 1 3 / 29

Chapter 1: Introduction

Topics covered:

1.1 Propositional Logic

1.2 Propositional Equivalences
1.3 Predicates and Quantifiers
1.4 Nested Quantifiers
1.5 Rules of Inference
1.6 Introduction to Proofs

TrungDT (FUHN) MAD111 Chapter 1 3 / 29

Chapter 1: Introduction

Topics covered:

1.1 Propositional Logic

1.2 Propositional Equivalences
1.3 Predicates and Quantifiers
1.4 Nested Quantifiers
1.5 Rules of Inference
1.6 Introduction to Proofs
1.7 Proof Methods and Strategy

TrungDT (FUHN) MAD111 Chapter 1 3 / 29

1.1 Propositional Logic

A proposition is a declarative sentence that is either true or false.

TrungDT (FUHN) MAD111 Chapter 1 4 / 29

1.1 Propositional Logic

A proposition is a declarative sentence that is either true or false.

Example.

TrungDT (FUHN) MAD111 Chapter 1 4 / 29

1.1 Propositional Logic

A proposition is a declarative sentence that is either true or false.

Example. Which of the following sentences are propositions?

TrungDT (FUHN) MAD111 Chapter 1 4 / 29

1.1 Propositional Logic

A proposition is a declarative sentence that is either true or false.

Example. Which of the following sentences are propositions?

Great!

TrungDT (FUHN) MAD111 Chapter 1 4 / 29

1.1 Propositional Logic

A proposition is a declarative sentence that is either true or false.

Example. Which of the following sentences are propositions?

Great!
Tokyo is the capital of Japan

TrungDT (FUHN) MAD111 Chapter 1 4 / 29

1.1 Propositional Logic

A proposition is a declarative sentence that is either true or false.

Example. Which of the following sentences are propositions?

Great!
Tokyo is the capital of Japan
What time is it?

TrungDT (FUHN) MAD111 Chapter 1 4 / 29

1.1 Propositional Logic

A proposition is a declarative sentence that is either true or false.

Example. Which of the following sentences are propositions?

Great!
Tokyo is the capital of Japan
What time is it?
It is now 3pm

TrungDT (FUHN) MAD111 Chapter 1 4 / 29

1.1 Propositional Logic

A proposition is a declarative sentence that is either true or false.

Example. Which of the following sentences are propositions?

Great!
Tokyo is the capital of Japan
What time is it?
It is now 3pm
1+7=9

TrungDT (FUHN) MAD111 Chapter 1 4 / 29

1.1 Propositional Logic

A proposition is a declarative sentence that is either true or false.

Example. Which of the following sentences are propositions?

Great!
Tokyo is the capital of Japan
What time is it?
It is now 3pm
1+7=9
x+1=3

TrungDT (FUHN) MAD111 Chapter 1 4 / 29

Compound Propositions

TrungDT (FUHN) MAD111 Chapter 1 5 / 29

Compound Propositions

Let p, q be propositions.

TrungDT (FUHN) MAD111 Chapter 1 5 / 29

Compound Propositions

Let p, q be propositions.

Negation.

TrungDT (FUHN) MAD111 Chapter 1 5 / 29

Compound Propositions

Let p, q be propositions.

Negation.
¬p

TrungDT (FUHN) MAD111 Chapter 1 5 / 29

Compound Propositions

Let p, q be propositions.

Negation.
¬p = not p = proposition that is true if p is false, and is false if p is
true.

TrungDT (FUHN) MAD111 Chapter 1 5 / 29

Compound Propositions

Let p, q be propositions.

Negation.
¬p = not p = proposition that is true if p is false, and is false if p is
true.
Conjunction.

TrungDT (FUHN) MAD111 Chapter 1 5 / 29

Compound Propositions

Let p, q be propositions.

Negation.
¬p = not p = proposition that is true if p is false, and is false if p is
true.
Conjunction.
p∧q

TrungDT (FUHN) MAD111 Chapter 1 5 / 29

Compound Propositions

Let p, q be propositions.

Negation.
¬p = not p = proposition that is true if p is false, and is false if p is
true.
Conjunction.
p ∧ q = ”p and q”

TrungDT (FUHN) MAD111 Chapter 1 5 / 29

Compound Propositions

Let p, q be propositions.

Negation.
¬p = not p = proposition that is true if p is false, and is false if p is
true.
Conjunction.
p ∧ q = ”p and q” = proposition that is true when both p and q are
true, and is false otherwise.

TrungDT (FUHN) MAD111 Chapter 1 5 / 29

Compound Propositions

Let p, q be propositions.

Negation.
¬p = not p = proposition that is true if p is false, and is false if p is
true.
Conjunction.
p ∧ q = ”p and q” = proposition that is true when both p and q are
true, and is false otherwise.
Disjunction.

TrungDT (FUHN) MAD111 Chapter 1 5 / 29

Compound Propositions

Let p, q be propositions.

Negation.
¬p = not p = proposition that is true if p is false, and is false if p is
true.
Conjunction.
p ∧ q = ”p and q” = proposition that is true when both p and q are
true, and is false otherwise.
Disjunction.
p ∨ q = ”p or q” = proposition that is false when both p and q are
false, and is true otherwise.

TrungDT (FUHN) MAD111 Chapter 1 5 / 29

Compound Propositions

Let p, q be propositions.

Negation.
¬p = not p = proposition that is true if p is false, and is false if p is
true.
Conjunction.
p ∧ q = ”p and q” = proposition that is true when both p and q are
true, and is false otherwise.
Disjunction.
p ∨ q = ”p or q” = proposition that is false when both p and q are
false, and is true otherwise.
Exclusive or.

TrungDT (FUHN) MAD111 Chapter 1 5 / 29

Compound Propositions

Let p, q be propositions.

Negation.
¬p = not p = proposition that is true if p is false, and is false if p is
true.
Conjunction.
p ∧ q = ”p and q” = proposition that is true when both p and q are
true, and is false otherwise.
Disjunction.
p ∨ q = ”p or q” = proposition that is false when both p and q are
false, and is true otherwise.
Exclusive or.
p⊕q

TrungDT (FUHN) MAD111 Chapter 1 5 / 29

Compound Propositions

Let p, q be propositions.

Negation.
¬p = not p = proposition that is true if p is false, and is false if p is
true.
Conjunction.
p ∧ q = ”p and q” = proposition that is true when both p and q are
true, and is false otherwise.
Disjunction.
p ∨ q = ”p or q” = proposition that is false when both p and q are
false, and is true otherwise.
Exclusive or.
p ⊕ q = ”only p or only q”

TrungDT (FUHN) MAD111 Chapter 1 5 / 29

Compound Propositions

Let p, q be propositions.

Negation.
¬p = not p = proposition that is true if p is false, and is false if p is
true.
Conjunction.
p ∧ q = ”p and q” = proposition that is true when both p and q are
true, and is false otherwise.
Disjunction.
p ∨ q = ”p or q” = proposition that is false when both p and q are
false, and is true otherwise.
Exclusive or.
p ⊕ q = ”only p or only q” = proposition that is true when exactly
one of p and q is true and is false otherwise.

TrungDT (FUHN) MAD111 Chapter 1 5 / 29

TrungDT (FUHN) MAD111 Chapter 1 6 / 29
Let p, q be propositions.

TrungDT (FUHN) MAD111 Chapter 1 6 / 29

Let p, q be propositions.

Conditional statement.
p→q

TrungDT (FUHN) MAD111 Chapter 1 6 / 29

Let p, q be propositions.

Conditional statement.
p → q = proposition that is false when p is true and q is false, and is
true otherwise.

TrungDT (FUHN) MAD111 Chapter 1 6 / 29

Let p, q be propositions.

Conditional statement.
p → q = proposition that is false when p is true and q is false, and is
true otherwise.
(*) Note: There are several ways to express the conditional statement
p→q

TrungDT (FUHN) MAD111 Chapter 1 6 / 29

Let p, q be propositions.

Conditional statement.
p → q = proposition that is false when p is true and q is false, and is
true otherwise.
(*) Note: There are several ways to express the conditional statement
p→q
If p then q

TrungDT (FUHN) MAD111 Chapter 1 6 / 29

Let p, q be propositions.

Conditional statement.
p → q = proposition that is false when p is true and q is false, and is
true otherwise.
(*) Note: There are several ways to express the conditional statement
p→q
If p then q
q if p

TrungDT (FUHN) MAD111 Chapter 1 6 / 29

Let p, q be propositions.

Conditional statement.
p → q = proposition that is false when p is true and q is false, and is
true otherwise.
(*) Note: There are several ways to express the conditional statement
p→q
If p then q
q if p
p is sufficient for q

TrungDT (FUHN) MAD111 Chapter 1 6 / 29

Let p, q be propositions.

Conditional statement.
p → q = proposition that is false when p is true and q is false, and is
true otherwise.
(*) Note: There are several ways to express the conditional statement
p→q
If p then q
q if p
p is sufficient for q
q is a necessary condition for p

TrungDT (FUHN) MAD111 Chapter 1 6 / 29

Let p, q be propositions.

Conditional statement.
p → q = proposition that is false when p is true and q is false, and is
true otherwise.
(*) Note: There are several ways to express the conditional statement
p→q
If p then q
q if p
p is sufficient for q
q is a necessary condition for p
p only if q

TrungDT (FUHN) MAD111 Chapter 1 6 / 29

Let p, q be propositions.

Conditional statement.
p → q = proposition that is false when p is true and q is false, and is
true otherwise.
(*) Note: There are several ways to express the conditional statement
p→q
If p then q
q if p
p is sufficient for q
q is a necessary condition for p
p only if q
Biconditional statement.

TrungDT (FUHN) MAD111 Chapter 1 6 / 29

Let p, q be propositions.

Conditional statement.
p → q = proposition that is false when p is true and q is false, and is
true otherwise.
(*) Note: There are several ways to express the conditional statement
p→q
If p then q
q if p
p is sufficient for q
q is a necessary condition for p
p only if q
Biconditional statement.
p↔q

TrungDT (FUHN) MAD111 Chapter 1 6 / 29

Let p, q be propositions.

Conditional statement.
p → q = proposition that is false when p is true and q is false, and is
true otherwise.
(*) Note: There are several ways to express the conditional statement
p→q
If p then q
q if p
p is sufficient for q
q is a necessary condition for p
p only if q
Biconditional statement.
p ↔ q = proposition that is true when p and q have the same truth
values, and is false otherwise.

TrungDT (FUHN) MAD111 Chapter 1 6 / 29

Let p, q be propositions.

Conditional statement.
p → q = proposition that is false when p is true and q is false, and is
true otherwise.
(*) Note: There are several ways to express the conditional statement
p→q
If p then q
q if p
p is sufficient for q
q is a necessary condition for p
p only if q
Biconditional statement.
p ↔ q = proposition that is true when p and q have the same truth
values, and is false otherwise.

TrungDT (FUHN) MAD111 Chapter 1 6 / 29

Translating Sentences into Logical Expressions

TrungDT (FUHN) MAD111 Chapter 1 7 / 29

Translating Sentences into Logical Expressions
Example 1. I watch soccer only if Arsenal play or I have no homework.

TrungDT (FUHN) MAD111 Chapter 1 7 / 29

Translating Sentences into Logical Expressions
Example 1. I watch soccer only if Arsenal play or I have no homework.

p=”I watch soccer”

TrungDT (FUHN) MAD111 Chapter 1 7 / 29

Translating Sentences into Logical Expressions
Example 1. I watch soccer only if Arsenal play or I have no homework.

p=”I watch soccer”

q=”Arsenal play”

TrungDT (FUHN) MAD111 Chapter 1 7 / 29

Translating Sentences into Logical Expressions
Example 1. I watch soccer only if Arsenal play or I have no homework.

p=”I watch soccer”

q=”Arsenal play”

r=”I have homework”

TrungDT (FUHN) MAD111 Chapter 1 7 / 29

Translating Sentences into Logical Expressions
Example 1. I watch soccer only if Arsenal play or I have no homework.

p=”I watch soccer”

q=”Arsenal play”

r=”I have homework”

Example 2. (a) You can not pass this class if you miss more than 20% of
lectures.

TrungDT (FUHN) MAD111 Chapter 1 7 / 29

Translating Sentences into Logical Expressions
Example 1. I watch soccer only if Arsenal play or I have no homework.

p=”I watch soccer”

q=”Arsenal play”

r=”I have homework”

Example 2. (a) You can not pass this class if you miss more than 20% of
lectures.

p=”You pass this class”

TrungDT (FUHN) MAD111 Chapter 1 7 / 29

Translating Sentences into Logical Expressions
Example 1. I watch soccer only if Arsenal play or I have no homework.

p=”I watch soccer”

q=”Arsenal play”

r=”I have homework”

Example 2. (a) You can not pass this class if you miss more than 20% of
lectures.

p=”You pass this class”

q=”You miss more than 20% of lectures”

TrungDT (FUHN) MAD111 Chapter 1 7 / 29

Translating Sentences into Logical Expressions
Example 1. I watch soccer only if Arsenal play or I have no homework.

p=”I watch soccer”

q=”Arsenal play”

r=”I have homework”

Example 2. (a) You can not pass this class if you miss more than 20% of
lectures.

p=”You pass this class”

q=”You miss more than 20% of lectures”

(b) You can not pass this class if you miss more than 20% of lectures
unless you provide reasonable excuses.

TrungDT (FUHN) MAD111 Chapter 1 7 / 29

Translating Sentences into Logical Expressions
Example 1. I watch soccer only if Arsenal play or I have no homework.

p=”I watch soccer”

q=”Arsenal play”

r=”I have homework”

Example 2. (a) You can not pass this class if you miss more than 20% of
lectures.

p=”You pass this class”

q=”You miss more than 20% of lectures”

(b) You can not pass this class if you miss more than 20% of lectures
unless you provide reasonable excuses.

r=”You provide reasonable excuses”

TrungDT (FUHN) MAD111 Chapter 1 7 / 29
Logic and Bit Operations

TrungDT (FUHN) MAD111 Chapter 1 8 / 29

Logic and Bit Operations

Computers represent information using bits. A bit is a symbol of two

possible values, 0 and 1. A bit can represent a truth value, that is, 1
represents T (true) and 0 represents F (false). Information is often
represented using bit strings, and operations on bit strings can be used to
manipulate this information.

TrungDT (FUHN) MAD111 Chapter 1 8 / 29

Logic and Bit Operations

Computers represent information using bits. A bit is a symbol of two

possible values, 0 and 1. A bit can represent a truth value, that is, 1
represents T (true) and 0 represents F (false). Information is often
represented using bit strings, and operations on bit strings can be used to
manipulate this information.

Example.

TrungDT (FUHN) MAD111 Chapter 1 8 / 29

Logic and Bit Operations

Computers represent information using bits. A bit is a symbol of two

possible values, 0 and 1. A bit can represent a truth value, that is, 1
represents T (true) and 0 represents F (false). Information is often
represented using bit strings, and operations on bit strings can be used to
manipulate this information.

Example. 1001100 ∧ 0011001 = 0001000.

TrungDT (FUHN) MAD111 Chapter 1 8 / 29

Logic and Bit Operations

Computers represent information using bits. A bit is a symbol of two

possible values, 0 and 1. A bit can represent a truth value, that is, 1
represents T (true) and 0 represents F (false). Information is often
represented using bit strings, and operations on bit strings can be used to
manipulate this information.

Example. 1001100 ∧ 0011001 = 0001000.

Note.

TrungDT (FUHN) MAD111 Chapter 1 8 / 29

Logic and Bit Operations

Computers represent information using bits. A bit is a symbol of two

possible values, 0 and 1. A bit can represent a truth value, that is, 1
represents T (true) and 0 represents F (false). Information is often
represented using bit strings, and operations on bit strings can be used to
manipulate this information.

Example. 1001100 ∧ 0011001 = 0001000.

Note. Other notation for ∧, ∨, ⊕ are AND, OR, XOR.

TrungDT (FUHN) MAD111 Chapter 1 8 / 29

1.2 Propositional Equivalences

TrungDT (FUHN) MAD111 Chapter 1 9 / 29

1.2 Propositional Equivalences

TrungDT (FUHN) MAD111 Chapter 1 9 / 29

1.2 Propositional Equivalences

A compound proposition is called a tautology if it is always true

regardless of the truth values of the propositions that occur in it.

TrungDT (FUHN) MAD111 Chapter 1 9 / 29

1.2 Propositional Equivalences

A compound proposition is called a tautology if it is always true

regardless of the truth values of the propositions that occur in it. A
compound proposition is called a contradiction if it is always false.

TrungDT (FUHN) MAD111 Chapter 1 9 / 29

1.2 Propositional Equivalences

A compound proposition is called a tautology if it is always true

regardless of the truth values of the propositions that occur in it. A
compound proposition is called a contradiction if it is always false. A
compound proposition that is neither tautology nor contradiction is
called a contingency.

TrungDT (FUHN) MAD111 Chapter 1 9 / 29

1.2 Propositional Equivalences

A compound proposition is called a tautology if it is always true

regardless of the truth values of the propositions that occur in it. A
compound proposition is called a contradiction if it is always false. A
compound proposition that is neither tautology nor contradiction is
called a contingency.
Two propositions p and q are logically equivalent if the biconditional
statement p ↔ q is a tautology.

TrungDT (FUHN) MAD111 Chapter 1 9 / 29

1.2 Propositional Equivalences

A compound proposition is called a tautology if it is always true

regardless of the truth values of the propositions that occur in it. A
compound proposition is called a contradiction if it is always false. A
compound proposition that is neither tautology nor contradiction is
called a contingency.
Two propositions p and q are logically equivalent if the biconditional
statement p ↔ q is a tautology. In this case we use notation p ≡ q.

TrungDT (FUHN) MAD111 Chapter 1 9 / 29

1.2 Propositional Equivalences

A compound proposition is called a tautology if it is always true

regardless of the truth values of the propositions that occur in it. A
compound proposition is called a contradiction if it is always false. A
compound proposition that is neither tautology nor contradiction is
called a contingency.
Two propositions p and q are logically equivalent if the biconditional
statement p ↔ q is a tautology. In this case we use notation p ≡ q.

Two methods for proving logical equivalences:

TrungDT (FUHN) MAD111 Chapter 1 9 / 29

1.2 Propositional Equivalences

A compound proposition is called a tautology if it is always true

regardless of the truth values of the propositions that occur in it. A
compound proposition is called a contradiction if it is always false. A
compound proposition that is neither tautology nor contradiction is
called a contingency.
Two propositions p and q are logically equivalent if the biconditional
statement p ↔ q is a tautology. In this case we use notation p ≡ q.

Two methods for proving logical equivalences:

Use truth table

TrungDT (FUHN) MAD111 Chapter 1 9 / 29

1.2 Propositional Equivalences

A compound proposition is called a tautology if it is always true

regardless of the truth values of the propositions that occur in it. A
compound proposition is called a contradiction if it is always false. A
compound proposition that is neither tautology nor contradiction is
called a contingency.
Two propositions p and q are logically equivalent if the biconditional
statement p ↔ q is a tautology. In this case we use notation p ≡ q.

Two methods for proving logical equivalences:

Use truth table

Use other logical equivalences.

TrungDT (FUHN) MAD111 Chapter 1 9 / 29

1.2 Propositional Equivalences

A compound proposition is called a tautology if it is always true

regardless of the truth values of the propositions that occur in it. A
compound proposition is called a contradiction if it is always false. A
compound proposition that is neither tautology nor contradiction is
called a contingency.
Two propositions p and q are logically equivalent if the biconditional
statement p ↔ q is a tautology. In this case we use notation p ≡ q.

Two methods for proving logical equivalences:

Use truth table

Use other logical equivalences.

TrungDT (FUHN) MAD111 Chapter 1 9 / 29

TrungDT (FUHN) MAD111 Chapter 1 10 / 29
Some
logical
equivalences

TrungDT (FUHN) MAD111 Chapter 1 10 / 29

 Double negation law ¬(¬p) ≡ p
Identity laws p∧T ≡p
p∨F ≡p
Domination laws p∨T ≡T
p∧F ≡F
Negation laws p ∨ ¬p ≡ T
p ∧ ¬p ≡ F
Some Idempotent laws p∨p ≡p
logical p∧p ≡p
equivalences Commutative laws p∨q ≡q∨p
p∧q ≡q∧p
Associative laws (p ∨ q) ∨ r ≡ p ∨ (q ∨ r )
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r )
Distributive laws p ∨ (q ∧ r ) ≡ (p ∨ q) ∧ (p ∨ r )
p ∧ (q ∨ r ) ≡ (p ∧ q) ∨ (p ∧ r )
De Morgan’s laws ¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q

TrungDT (FUHN) MAD111 Chapter 1 10 / 29

TrungDT (FUHN) MAD111 Chapter 1 11 / 29
Note:

p → q ≡ ¬p ∨ q.

TrungDT (FUHN) MAD111 Chapter 1 11 / 29

Note:

p → q ≡ ¬p ∨ q.
p ↔ q ≡ (p → q) ∧ (q → p)

TrungDT (FUHN) MAD111 Chapter 1 11 / 29

Note:

p → q ≡ ¬p ∨ q.
p ↔ q ≡ (p → q) ∧ (q → p)
p ⊕ q ≡ ¬(p ↔ q)

TrungDT (FUHN) MAD111 Chapter 1 11 / 29

Note:

p → q ≡ ¬p ∨ q.
p ↔ q ≡ (p → q) ∧ (q → p)
p ⊕ q ≡ ¬(p ↔ q)

Example 1. Prove that ¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬q

TrungDT (FUHN) MAD111 Chapter 1 11 / 29

Note:

p → q ≡ ¬p ∨ q.
p ↔ q ≡ (p → q) ∧ (q → p)
p ⊕ q ≡ ¬(p ↔ q)

Example 1. Prove that ¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬q

Example 2. Show that (p ∧ q) → (p ∨ q) is a tautology.

TrungDT (FUHN) MAD111 Chapter 1 11 / 29

1.3 Predicates and Quantifiers

TrungDT (FUHN) MAD111 Chapter 1 12 / 29

1.3 Predicates and Quantifiers

Predicate.

TrungDT (FUHN) MAD111 Chapter 1 12 / 29

1.3 Predicates and Quantifiers

Predicate.

The statement ”x > 3” is not a proposition.

TrungDT (FUHN) MAD111 Chapter 1 12 / 29

1.3 Predicates and Quantifiers

Predicate.

The statement ”x > 3” is not a proposition. It will become a proposition

when a value is assigned to x.

TrungDT (FUHN) MAD111 Chapter 1 12 / 29

1.3 Predicates and Quantifiers

Predicate.

The statement ”x > 3” is not a proposition. It will become a proposition

when a value is assigned to x.

The statement ”x > 3” is called a propositional function, denoted by

P(x).

TrungDT (FUHN) MAD111 Chapter 1 12 / 29

1.3 Predicates and Quantifiers

Predicate.

The statement ”x > 3” is not a proposition. It will become a proposition

when a value is assigned to x.

The statement ”x > 3” is called a propositional function, denoted by

P(x). Then:

TrungDT (FUHN) MAD111 Chapter 1 12 / 29

1.3 Predicates and Quantifiers

Predicate.

The statement ”x > 3” is not a proposition. It will become a proposition

when a value is assigned to x.

The statement ”x > 3” is called a propositional function, denoted by

P(x). Then:

P(0)=F

TrungDT (FUHN) MAD111 Chapter 1 12 / 29

1.3 Predicates and Quantifiers

Predicate.

The statement ”x > 3” is not a proposition. It will become a proposition

when a value is assigned to x.

The statement ”x > 3” is called a propositional function, denoted by

P(x). Then:

P(0)=F, P(5)=T

TrungDT (FUHN) MAD111 Chapter 1 12 / 29

1.3 Predicates and Quantifiers

Predicate.

The statement ”x > 3” is not a proposition. It will become a proposition

when a value is assigned to x.

The statement ”x > 3” is called a propositional function, denoted by

P(x). Then:

P(0)=F, P(5)=T

x is called a variable, ”> 3” is the predicate

TrungDT (FUHN) MAD111 Chapter 1 12 / 29

1.3 Predicates and Quantifiers

Predicate.

The statement ”x > 3” is not a proposition. It will become a proposition

when a value is assigned to x.

The statement ”x > 3” is called a propositional function, denoted by

P(x). Then:

P(0)=F, P(5)=T

x is called a variable, ”> 3” is the predicate

A propositional function can be multi-variable.

TrungDT (FUHN) MAD111 Chapter 1 12 / 29

1.3 Predicates and Quantifiers

Predicate.

The statement ”x > 3” is not a proposition. It will become a proposition

when a value is assigned to x.

The statement ”x > 3” is called a propositional function, denoted by

P(x). Then:

P(0)=F, P(5)=T

x is called a variable, ”> 3” is the predicate

A propositional function can be multi-variable.

Example. R(x, y , z) = ”x + y < z” is a propositional function with

variables x, y , z and R is the predicate.

TrungDT (FUHN) MAD111 Chapter 1 12 / 29

1.3 Predicates and Quantifiers

Predicate.

The statement ”x > 3” is not a proposition. It will become a proposition

when a value is assigned to x.

The statement ”x > 3” is called a propositional function, denoted by

P(x). Then:

P(0)=F, P(5)=T

x is called a variable, ”> 3” is the predicate

A propositional function can be multi-variable.

Example. R(x, y , z) = ”x + y < z” is a propositional function with

variables x, y , z and R is the predicate.

TrungDT (FUHN) MAD111 Chapter 1 12 / 29

TrungDT (FUHN) MAD111 Chapter 1 13 / 29
Quantifiers

TrungDT (FUHN) MAD111 Chapter 1 13 / 29

Quantifiers ∀, ∃.

TrungDT (FUHN) MAD111 Chapter 1 13 / 29

Quantifiers ∀, ∃.

Let P(x) be a propositional function where x gets values in a particular

domain.

TrungDT (FUHN) MAD111 Chapter 1 13 / 29

Quantifiers ∀, ∃.

Let P(x) be a propositional function where x gets values in a particular

domain.

The universal quantification ∀xP(x)

TrungDT (FUHN) MAD111 Chapter 1 13 / 29

Quantifiers ∀, ∃.

Let P(x) be a propositional function where x gets values in a particular

domain.

The universal quantification ∀xP(x)= For all values of x in the domain,

P(x) is true

TrungDT (FUHN) MAD111 Chapter 1 13 / 29

Quantifiers ∀, ∃.

Let P(x) be a propositional function where x gets values in a particular

domain.

The universal quantification ∀xP(x)= For all values of x in the domain,

P(x) is true

The existential quantification ∃xP(x)

TrungDT (FUHN) MAD111 Chapter 1 13 / 29

Quantifiers ∀, ∃.

Let P(x) be a propositional function where x gets values in a particular

domain.

The universal quantification ∀xP(x)= For all values of x in the domain,

P(x) is true

The existential quantification ∃xP(x)= There is at least a value of x in

the domain such that P(x) is true.

TrungDT (FUHN) MAD111 Chapter 1 13 / 29

Quantifiers ∀, ∃.

Let P(x) be a propositional function where x gets values in a particular

domain.

The universal quantification ∀xP(x)= For all values of x in the domain,

P(x) is true

The existential quantification ∃xP(x)= There is at least a value of x in

the domain such that P(x) is true.

Example. Let x represent a real number. Determine the truth value of

the following propositions
(a) ∀x((x > 0) → (x 2 ≥ x))

TrungDT (FUHN) MAD111 Chapter 1 13 / 29

Quantifiers ∀, ∃.

Let P(x) be a propositional function where x gets values in a particular

domain.

The universal quantification ∀xP(x)= For all values of x in the domain,

P(x) is true

The existential quantification ∃xP(x)= There is at least a value of x in

the domain such that P(x) is true.

Example. Let x represent a real number. Determine the truth value of

the following propositions
(a) ∀x((x > 0) → (x 2 ≥ x))
(b) ∀x((x > 0) ∧ (x 2 ≥ x))

TrungDT (FUHN) MAD111 Chapter 1 13 / 29

Quantifiers ∀, ∃.

Let P(x) be a propositional function where x gets values in a particular

domain.

The universal quantification ∀xP(x)= For all values of x in the domain,

P(x) is true

The existential quantification ∃xP(x)= There is at least a value of x in

the domain such that P(x) is true.

Example. Let x represent a real number. Determine the truth value of

the following propositions
(a) ∀x((x > 0) → (x 2 ≥ x))
(b) ∀x((x > 0) ∧ (x 2 ≥ x))
(c) ∀x((x > 0) ∨ (x 2 ≥ x))

TrungDT (FUHN) MAD111 Chapter 1 13 / 29

Quantifiers ∀, ∃.

Let P(x) be a propositional function where x gets values in a particular

domain.

The universal quantification ∀xP(x)= For all values of x in the domain,

P(x) is true

The existential quantification ∃xP(x)= There is at least a value of x in

the domain such that P(x) is true.

Example. Let x represent a real number. Determine the truth value of

the following propositions
(a) ∀x((x > 0) → (x 2 ≥ x)) (d) ∃x((x > 0) → (x 2 ≥ x))
(b) ∀x((x > 0) ∧ (x 2 ≥ x))
(c) ∀x((x > 0) ∨ (x 2 ≥ x))

TrungDT (FUHN) MAD111 Chapter 1 13 / 29

Quantifiers ∀, ∃.

Let P(x) be a propositional function where x gets values in a particular

domain.

The universal quantification ∀xP(x)= For all values of x in the domain,

P(x) is true

The existential quantification ∃xP(x)= There is at least a value of x in

the domain such that P(x) is true.

Example. Let x represent a real number. Determine the truth value of

the following propositions
(a) ∀x((x > 0) → (x 2 ≥ x)) (d) ∃x((x > 0) → (x 2 ≥ x))
(b) ∀x((x > 0) ∧ (x 2 ≥ x)) (e) ∃x((x > 0) ∧ (x 2 ≥ x))
(c) ∀x((x > 0) ∨ (x 2 ≥ x))

TrungDT (FUHN) MAD111 Chapter 1 13 / 29

Quantifiers ∀, ∃.

Let P(x) be a propositional function where x gets values in a particular

domain.

The universal quantification ∀xP(x)= For all values of x in the domain,

P(x) is true

The existential quantification ∃xP(x)= There is at least a value of x in

the domain such that P(x) is true.

Example. Let x represent a real number. Determine the truth value of

the following propositions
(a) ∀x((x > 0) → (x 2 ≥ x)) (d) ∃x((x > 0) → (x 2 ≥ x))
(b) ∀x((x > 0) ∧ (x 2 ≥ x)) (e) ∃x((x > 0) ∧ (x 2 ≥ x))
(c) ∀x((x > 0) ∨ (x 2 ≥ x)) (f) ∃x((x > 0) ∨ (x 2 ≥ x))

TrungDT (FUHN) MAD111 Chapter 1 13 / 29

Quantifiers ∀, ∃.

Let P(x) be a propositional function where x gets values in a particular

domain.

The universal quantification ∀xP(x)= For all values of x in the domain,

P(x) is true

The existential quantification ∃xP(x)= There is at least a value of x in

the domain such that P(x) is true.

Example. Let x represent a real number. Determine the truth value of

the following propositions
(a) ∀x((x > 0) → (x 2 ≥ x)) (d) ∃x((x > 0) → (x 2 ≥ x))
(b) ∀x((x > 0) ∧ (x 2 ≥ x)) (e) ∃x((x > 0) ∧ (x 2 ≥ x))
(c) ∀x((x > 0) ∨ (x 2 ≥ x)) (f) ∃x((x > 0) ∨ (x 2 ≥ x))

TrungDT (FUHN) MAD111 Chapter 1 13 / 29

TrungDT (FUHN) MAD111 Chapter 1 14 / 29
Negating Quantified Expressions

TrungDT (FUHN) MAD111 Chapter 1 14 / 29

Negating Quantified Expressions
¬∀xP(x) = ∃x¬P(x)

TrungDT (FUHN) MAD111 Chapter 1 14 / 29

Negating Quantified Expressions
¬∀xP(x) = ∃x¬P(x) ¬∃xP(x) = ∀x¬P(x)

TrungDT (FUHN) MAD111 Chapter 1 14 / 29

Negating Quantified Expressions
¬∀xP(x) = ∃x¬P(x) ¬∃xP(x) = ∀x¬P(x)

TrungDT (FUHN) MAD111 Chapter 1 14 / 29

Negating Quantified Expressions
¬∀xP(x) = ∃x¬P(x) ¬∃xP(x) = ∀x¬P(x)

Example. Rewrite the expression

¬∀x(P(x) → Q(x))

so that the negation precedes the predicates.

TrungDT (FUHN) MAD111 Chapter 1 14 / 29

Translating Sentences into Logical Expressions

TrungDT (FUHN) MAD111 Chapter 1 15 / 29

Translating Sentences into Logical Expressions

Example 1. ”Every students of class SE0000 passed Calculus”

TrungDT (FUHN) MAD111 Chapter 1 15 / 29

Translating Sentences into Logical Expressions

Example 1. ”Every students of class SE0000 passed Calculus”

(a) If domain consists of all students of SE0000

TrungDT (FUHN) MAD111 Chapter 1 15 / 29

Translating Sentences into Logical Expressions

Example 1. ”Every students of class SE0000 passed Calculus”

(a) If domain consists of all students of SE0000

Put P(x)=”x passed Calculus”

TrungDT (FUHN) MAD111 Chapter 1 15 / 29

Translating Sentences into Logical Expressions

Example 1. ”Every students of class SE0000 passed Calculus”

(a) If domain consists of all students of SE0000

Put P(x)=”x passed Calculus”

(b) If domain consists of all students of the university

TrungDT (FUHN) MAD111 Chapter 1 15 / 29

Translating Sentences into Logical Expressions

Example 1. ”Every students of class SE0000 passed Calculus”

(a) If domain consists of all students of SE0000

Put P(x)=”x passed Calculus”

(b) If domain consists of all students of the university

We need Q(x)=”x is in SE0000”

TrungDT (FUHN) MAD111 Chapter 1 15 / 29

Translating Sentences into Logical Expressions

Example 1. ”Every students of class SE0000 passed Calculus”

(a) If domain consists of all students of SE0000

Put P(x)=”x passed Calculus”

(b) If domain consists of all students of the university

We need Q(x)=”x is in SE0000”

Example 2. ”Each student of SE0000 has visited Canada or Mexico”

TrungDT (FUHN) MAD111 Chapter 1 15 / 29

Translating Sentences into Logical Expressions

Example 1. ”Every students of class SE0000 passed Calculus”

(a) If domain consists of all students of SE0000

Put P(x)=”x passed Calculus”

(b) If domain consists of all students of the university

We need Q(x)=”x is in SE0000”

Example 2. ”Each student of SE0000 has visited Canada or Mexico”

Example 3. ”Some student of SE0000 has visited Canada or Mexico”

TrungDT (FUHN) MAD111 Chapter 1 15 / 29

1.4 Nested Quantifiers

TrungDT (FUHN) MAD111 Chapter 1 16 / 29

1.4 Nested Quantifiers

∀x∀yP(x, y )

TrungDT (FUHN) MAD111 Chapter 1 16 / 29

1.4 Nested Quantifiers

∀x∀yP(x, y ) = For all x and for all y , P(x, y ) is true

TrungDT (FUHN) MAD111 Chapter 1 16 / 29

1.4 Nested Quantifiers

∀x∀yP(x, y ) = For all x and for all y , P(x, y ) is true

∀x∃yP(x, y )

TrungDT (FUHN) MAD111 Chapter 1 16 / 29

1.4 Nested Quantifiers

∀x∀yP(x, y ) = For all x and for all y , P(x, y ) is true

∀x∃yP(x, y ) = For all x there is y such that P(x, y ) is true

TrungDT (FUHN) MAD111 Chapter 1 16 / 29

1.4 Nested Quantifiers

∀x∀yP(x, y ) = For all x and for all y , P(x, y ) is true

∀x∃yP(x, y ) = For all x there is y such that P(x, y ) is true

∃x∀yP(x, y )

TrungDT (FUHN) MAD111 Chapter 1 16 / 29

1.4 Nested Quantifiers

∀x∀yP(x, y ) = For all x and for all y , P(x, y ) is true

∀x∃yP(x, y ) = For all x there is y such that P(x, y ) is true

∃x∀yP(x, y ) = There exists x such that for all y , P(x, y ) is true

TrungDT (FUHN) MAD111 Chapter 1 16 / 29

1.4 Nested Quantifiers

∀x∀yP(x, y ) = For all x and for all y , P(x, y ) is true

∀x∃yP(x, y ) = For all x there is y such that P(x, y ) is true

∃x∀yP(x, y ) = There exists x such that for all y , P(x, y ) is true

∃x∃yP(x, y )

TrungDT (FUHN) MAD111 Chapter 1 16 / 29

1.4 Nested Quantifiers

∀x∀yP(x, y ) = For all x and for all y , P(x, y ) is true

∀x∃yP(x, y ) = For all x there is y such that P(x, y ) is true

∃x∀yP(x, y ) = There exists x such that for all y , P(x, y ) is true

∃x∃yP(x, y ) = There exist x and y such that P(x, y ) is true

TrungDT (FUHN) MAD111 Chapter 1 16 / 29

1.4 Nested Quantifiers

∀x∀yP(x, y ) = For all x and for all y , P(x, y ) is true

∀x∃yP(x, y ) = For all x there is y such that P(x, y ) is true

∃x∀yP(x, y ) = There exists x such that for all y , P(x, y ) is true

∃x∃yP(x, y ) = There exist x and y such that P(x, y ) is true

Note. The order of the quantifiers is important!

TrungDT (FUHN) MAD111 Chapter 1 16 / 29

1.4 Nested Quantifiers

∀x∀yP(x, y ) = For all x and for all y , P(x, y ) is true

∀x∃yP(x, y ) = For all x there is y such that P(x, y ) is true

∃x∀yP(x, y ) = There exists x such that for all y , P(x, y ) is true

∃x∃yP(x, y ) = There exist x and y such that P(x, y ) is true

Note. The order of the quantifiers is important!

Example. Determine the truth values of the following propositions on the

set of real numbers.

TrungDT (FUHN) MAD111 Chapter 1 16 / 29

1.4 Nested Quantifiers

∀x∀yP(x, y ) = For all x and for all y , P(x, y ) is true

∀x∃yP(x, y ) = For all x there is y such that P(x, y ) is true

∃x∀yP(x, y ) = There exists x such that for all y , P(x, y ) is true

∃x∃yP(x, y ) = There exist x and y such that P(x, y ) is true

Note. The order of the quantifiers is important!

Example. Determine the truth values of the following propositions on the

set of real numbers.
∀x∀y (x + y = 1)

TrungDT (FUHN) MAD111 Chapter 1 16 / 29

1.4 Nested Quantifiers

∀x∀yP(x, y ) = For all x and for all y , P(x, y ) is true

∀x∃yP(x, y ) = For all x there is y such that P(x, y ) is true

∃x∀yP(x, y ) = There exists x such that for all y , P(x, y ) is true

∃x∃yP(x, y ) = There exist x and y such that P(x, y ) is true

Note. The order of the quantifiers is important!

Example. Determine the truth values of the following propositions on the

set of real numbers.
∀x∀y (x + y = 1)
∀x∃y (x + y = 1)

TrungDT (FUHN) MAD111 Chapter 1 16 / 29

1.4 Nested Quantifiers

∀x∀yP(x, y ) = For all x and for all y , P(x, y ) is true

∀x∃yP(x, y ) = For all x there is y such that P(x, y ) is true

∃x∀yP(x, y ) = There exists x such that for all y , P(x, y ) is true

∃x∃yP(x, y ) = There exist x and y such that P(x, y ) is true

Note. The order of the quantifiers is important!

Example. Determine the truth values of the following propositions on the

set of real numbers.
∀x∀y (x + y = 1) ∃x∀y (x + y = 1)
∀x∃y (x + y = 1)

TrungDT (FUHN) MAD111 Chapter 1 16 / 29

1.4 Nested Quantifiers

∀x∀yP(x, y ) = For all x and for all y , P(x, y ) is true

∀x∃yP(x, y ) = For all x there is y such that P(x, y ) is true

∃x∀yP(x, y ) = There exists x such that for all y , P(x, y ) is true

∃x∃yP(x, y ) = There exist x and y such that P(x, y ) is true

Note. The order of the quantifiers is important!

Example. Determine the truth values of the following propositions on the

set of real numbers.
∀x∀y (x + y = 1) ∃x∀y (x + y = 1)
∀x∃y (x + y = 1) ∃x∃y (x + y = 1)

TrungDT (FUHN) MAD111 Chapter 1 16 / 29

1.4 Nested Quantifiers

∀x∀yP(x, y ) = For all x and for all y , P(x, y ) is true

∀x∃yP(x, y ) = For all x there is y such that P(x, y ) is true

∃x∀yP(x, y ) = There exists x such that for all y , P(x, y ) is true

∃x∃yP(x, y ) = There exist x and y such that P(x, y ) is true

Note. The order of the quantifiers is important!

Example. Determine the truth values of the following propositions on the

set of real numbers.
∀x∀y (x + y = 1) ∃x∀y (x + y = 1)
∀x∃y (x + y = 1) ∃x∃y (x + y = 1)

TrungDT (FUHN) MAD111 Chapter 1 16 / 29

Translate Logical Expressions into Sentences

TrungDT (FUHN) MAD111 Chapter 1 17 / 29

Translate Logical Expressions into Sentences

Example 1. ∀x∀y [(x > 0) ∧ (y > 0) → (xy > 0)]

TrungDT (FUHN) MAD111 Chapter 1 17 / 29

Translate Logical Expressions into Sentences

Example 1. ∀x∀y [(x > 0) ∧ (y > 0) → (xy > 0)]

where x, y are real numbers.

TrungDT (FUHN) MAD111 Chapter 1 17 / 29

Translate Logical Expressions into Sentences

Example 1. ∀x∀y [(x > 0) ∧ (y > 0) → (xy > 0)]

where x, y are real numbers.

Example 2. Let x, y represent students in a university, and

TrungDT (FUHN) MAD111 Chapter 1 17 / 29

Translate Logical Expressions into Sentences

Example 1. ∀x∀y [(x > 0) ∧ (y > 0) → (xy > 0)]

where x, y are real numbers.

Example 2. Let x, y represent students in a university, and

C (x) = ” x has a laptop”

TrungDT (FUHN) MAD111 Chapter 1 17 / 29

Translate Logical Expressions into Sentences

Example 1. ∀x∀y [(x > 0) ∧ (y > 0) → (xy > 0)]

where x, y are real numbers.

Example 2. Let x, y represent students in a university, and

C (x) = ” x has a laptop” F (x, y ) = ” x and y are friends”

TrungDT (FUHN) MAD111 Chapter 1 17 / 29

Translate Logical Expressions into Sentences

Example 1. ∀x∀y [(x > 0) ∧ (y > 0) → (xy > 0)]

where x, y are real numbers.

Example 2. Let x, y represent students in a university, and

C (x) = ” x has a laptop” F (x, y ) = ” x and y are friends”

Translate the logical expression ∀x[C (x) ∨ ∃y (C (y ) ∧ F (x, y ))]

TrungDT (FUHN) MAD111 Chapter 1 17 / 29

Translate Logical Expressions into Sentences

Example 1. ∀x∀y [(x > 0) ∧ (y > 0) → (xy > 0)]

where x, y are real numbers.

Example 2. Let x, y represent students in a university, and

C (x) = ” x has a laptop” F (x, y ) = ” x and y are friends”

Translate the logical expression ∀x[C (x) ∨ ∃y (C (y ) ∧ F (x, y ))]

Example 3. Let x, y represent students in a university, and

TrungDT (FUHN) MAD111 Chapter 1 17 / 29

Translate Logical Expressions into Sentences

Example 1. ∀x∀y [(x > 0) ∧ (y > 0) → (xy > 0)]

where x, y are real numbers.

Example 2. Let x, y represent students in a university, and

C (x) = ” x has a laptop” F (x, y ) = ” x and y are friends”

Translate the logical expression ∀x[C (x) ∨ ∃y (C (y ) ∧ F (x, y ))]

Example 3. Let x, y represent students in a university, and

F (x, y ) = ” x and y are friends”

TrungDT (FUHN) MAD111 Chapter 1 17 / 29

Translate Logical Expressions into Sentences

Example 1. ∀x∀y [(x > 0) ∧ (y > 0) → (xy > 0)]

where x, y are real numbers.

Example 2. Let x, y represent students in a university, and

C (x) = ” x has a laptop” F (x, y ) = ” x and y are friends”

Translate the logical expression ∀x[C (x) ∨ ∃y (C (y ) ∧ F (x, y ))]

Example 3. Let x, y represent students in a university, and

F (x, y ) = ” x and y are friends”

Translate the logical expression

∃x∀y ∀z[(F (x, y ) ∧ F (x, z) ∧ (y 6= z)) → ¬F (y , z)]

TrungDT (FUHN) MAD111 Chapter 1 17 / 29

Translate Sentences into Logical Expression using Nested
Quantifiers

TrungDT (FUHN) MAD111 Chapter 1 18 / 29

Translate Sentences into Logical Expression using Nested
Quantifiers

Example 1. ”Each student has sent emails to each other, but not to
him/herself.”

TrungDT (FUHN) MAD111 Chapter 1 18 / 29

Translate Sentences into Logical Expression using Nested
Quantifiers

Example 1. ”Each student has sent emails to each other, but not to
him/herself.”

Use:

TrungDT (FUHN) MAD111 Chapter 1 18 / 29

Translate Sentences into Logical Expression using Nested
Quantifiers

Example 1. ”Each student has sent emails to each other, but not to
him/herself.”

Use: E (x, y )=”x has sent emails to y ”

TrungDT (FUHN) MAD111 Chapter 1 18 / 29

Translate Sentences into Logical Expression using Nested
Quantifiers

Example 1. ”Each student has sent emails to each other, but not to
him/herself.”

Use: E (x, y )=”x has sent emails to y ”

Example 2. ”Each student either has a car or has a room-mate in the

same class who has a car”

TrungDT (FUHN) MAD111 Chapter 1 18 / 29

Translate Sentences into Logical Expression using Nested
Quantifiers

Example 1. ”Each student has sent emails to each other, but not to
him/herself.”

Use: E (x, y )=”x has sent emails to y ”

Example 2. ”Each student either has a car or has a room-mate in the

same class who has a car”

Use:

TrungDT (FUHN) MAD111 Chapter 1 18 / 29

Translate Sentences into Logical Expression using Nested
Quantifiers

Example 1. ”Each student has sent emails to each other, but not to
him/herself.”

Use: E (x, y )=”x has sent emails to y ”

Example 2. ”Each student either has a car or has a room-mate in the

same class who has a car”

Use: C (x) = ”x has a car”

R(x, y )=”x and y are room-mates ”

TrungDT (FUHN) MAD111 Chapter 1 18 / 29

Translate Sentences into Logical Expression using Nested
Quantifiers

Example 1. ”Each student has sent emails to each other, but not to
him/herself.”

Use: E (x, y )=”x has sent emails to y ”

Example 2. ”Each student either has a car or has a room-mate in the

same class who has a car”

Use: C (x) = ”x has a car”

R(x, y )=”x and y are room-mates ”

Example 3. (a) There is exactly one student in the class that was born in
Hanoi.

TrungDT (FUHN) MAD111 Chapter 1 18 / 29

Translate Sentences into Logical Expression using Nested
Quantifiers

Example 1. ”Each student has sent emails to each other, but not to
him/herself.”

Use: E (x, y )=”x has sent emails to y ”

Example 2. ”Each student either has a car or has a room-mate in the

same class who has a car”

Use: C (x) = ”x has a car”

R(x, y )=”x and y are room-mates ”

Example 3. (a) There is exactly one student in the class that was born in
Hanoi.

(b) There are exactly two students in the class that was born in Hanoi.

TrungDT (FUHN) MAD111 Chapter 1 18 / 29

Negating Nested Quantifiers

TrungDT (FUHN) MAD111 Chapter 1 19 / 29

Negating Nested Quantifiers

TrungDT (FUHN) MAD111 Chapter 1 19 / 29

Negating Nested Quantifiers

¬(∀x∀yP(x, y )) = ∃x∃y ¬P(x, y )

TrungDT (FUHN) MAD111 Chapter 1 19 / 29

Negating Nested Quantifiers

¬(∀x∀yP(x, y )) = ∃x∃y ¬P(x, y ) ¬(∀x∃yP(x, y )) = ∃x∀y ¬P(x, y )

TrungDT (FUHN) MAD111 Chapter 1 19 / 29

Negating Nested Quantifiers

¬(∀x∀yP(x, y )) = ∃x∃y ¬P(x, y ) ¬(∀x∃yP(x, y )) = ∃x∀y ¬P(x, y )

¬(∃x∀yP(x, y )) = ∀x∃y ¬P(x, y )

TrungDT (FUHN) MAD111 Chapter 1 19 / 29

Negating Nested Quantifiers

¬(∀x∀yP(x, y )) = ∃x∃y ¬P(x, y ) ¬(∀x∃yP(x, y )) = ∃x∀y ¬P(x, y )

¬(∃x∀yP(x, y )) = ∀x∃y ¬P(x, y ) ¬(∃x∃yP(x, y )) = ∀x∀y ¬P(x, y )

TrungDT (FUHN) MAD111 Chapter 1 19 / 29

Negating Nested Quantifiers

¬(∀x∀yP(x, y )) = ∃x∃y ¬P(x, y ) ¬(∀x∃yP(x, y )) = ∃x∀y ¬P(x, y )

¬(∃x∀yP(x, y )) = ∀x∃y ¬P(x, y ) ¬(∃x∃yP(x, y )) = ∀x∀y ¬P(x, y )

Example.

TrungDT (FUHN) MAD111 Chapter 1 19 / 29

Negating Nested Quantifiers

¬(∀x∀yP(x, y )) = ∃x∃y ¬P(x, y ) ¬(∀x∃yP(x, y )) = ∃x∀y ¬P(x, y )

¬(∃x∀yP(x, y )) = ∀x∃y ¬P(x, y ) ¬(∃x∃yP(x, y )) = ∀x∀y ¬P(x, y )

Example. Translate the following statements into logical expressions, then

find the negation statement.

TrungDT (FUHN) MAD111 Chapter 1 19 / 29

Negating Nested Quantifiers

¬(∀x∀yP(x, y )) = ∃x∃y ¬P(x, y ) ¬(∀x∃yP(x, y )) = ∃x∀y ¬P(x, y )

¬(∃x∀yP(x, y )) = ∀x∃y ¬P(x, y ) ¬(∃x∃yP(x, y )) = ∀x∀y ¬P(x, y )

Example. Translate the following statements into logical expressions, then

find the negation statement.

(a) ” For all real numbers x there is a real number y such that x = y 3 ”

TrungDT (FUHN) MAD111 Chapter 1 19 / 29

Negating Nested Quantifiers

¬(∀x∀yP(x, y )) = ∃x∃y ¬P(x, y ) ¬(∀x∃yP(x, y )) = ∃x∀y ¬P(x, y )

¬(∃x∀yP(x, y )) = ∀x∃y ¬P(x, y ) ¬(∃x∃yP(x, y )) = ∀x∀y ¬P(x, y )

Example. Translate the following statements into logical expressions, then

find the negation statement.

(a) ” For all real numbers x there is a real number y such that x = y 3 ”
(b) ” For all  > 0, for all real numbers x there exists a rational number p
such that |p − x| < ”

TrungDT (FUHN) MAD111 Chapter 1 19 / 29

1.5 Rules of Inference

TrungDT (FUHN) MAD111 Chapter 1 20 / 29

1.5 Rules of Inference

An argument is a sequence of statements that end with a conclusion.

TrungDT (FUHN) MAD111 Chapter 1 20 / 29

1.5 Rules of Inference

An argument is a sequence of statements that end with a conclusion.

An argument is valid if the conclusion follows from the truth of the
preceding statements (premises or hypotheses).

TrungDT (FUHN) MAD111 Chapter 1 20 / 29

1.5 Rules of Inference

An argument is a sequence of statements that end with a conclusion.

An argument is valid if the conclusion follows from the truth of the
preceding statements (premises or hypotheses).
In propositional logic, an argument is valid if it is based on a
tautology.

TrungDT (FUHN) MAD111 Chapter 1 20 / 29

1.5 Rules of Inference

An argument is a sequence of statements that end with a conclusion.

An argument is valid if the conclusion follows from the truth of the
preceding statements (premises or hypotheses).
In propositional logic, an argument is valid if it is based on a
tautology.
Arguments that are not based on tautology are called fallacies.

TrungDT (FUHN) MAD111 Chapter 1 20 / 29

TrungDT (FUHN) MAD111 Chapter 1 21 / 29
Name Rule of Inference Tautology
Addition p p → (p ∨ q)
∴p∨q
Simplification p∧q (p ∧ q) → p
∴p
Modus ponens p p ∧ (p → q) → q
p→q
∴q
Modus tollens ¬q (¬q) ∧ (p → q) → ¬p
p→q
∴ ¬p
Hypothetical syllogism p→q (p → q) ∧ (q → r ) → (p → r )
q→r
∴p→r
Disjunctive syllogism ¬p (p ∨ q) ∧ (¬p) → q
p∨q
∴q

TrungDT (FUHN) MAD111 Chapter 1 21 / 29

TrungDT (FUHN) MAD111 Chapter 1 22 / 29
Example 1.

TrungDT (FUHN) MAD111 Chapter 1 22 / 29

Example 1. Given the hypotheses:

TrungDT (FUHN) MAD111 Chapter 1 22 / 29

Example 1. Given the hypotheses:

”It is not sunny and is cold”

TrungDT (FUHN) MAD111 Chapter 1 22 / 29

Example 1. Given the hypotheses:

”It is not sunny and is cold”

”We go swimming only if it is sunny”

TrungDT (FUHN) MAD111 Chapter 1 22 / 29

Example 1. Given the hypotheses:

”It is not sunny and is cold”

”We go swimming only if it is sunny”
”If we do not go swimming then we will play soccer”

TrungDT (FUHN) MAD111 Chapter 1 22 / 29

Example 1. Given the hypotheses:

”It is not sunny and is cold”

”We go swimming only if it is sunny”
”If we do not go swimming then we will play soccer”
”If we play soccer then we will go home by sunset”

TrungDT (FUHN) MAD111 Chapter 1 22 / 29

Example 1. Given the hypotheses:

”It is not sunny and is cold”

”We go swimming only if it is sunny”
”If we do not go swimming then we will play soccer”
”If we play soccer then we will go home by sunset”

Show that these hypotheses lead to the conclusion: ”We will go home by
sunset”.

TrungDT (FUHN) MAD111 Chapter 1 22 / 29

TrungDT (FUHN) MAD111 Chapter 1 23 / 29
Example 2.

TrungDT (FUHN) MAD111 Chapter 1 23 / 29

Example 2. Given the hypotheses:

TrungDT (FUHN) MAD111 Chapter 1 23 / 29

Example 2. Given the hypotheses:

”If you send me an email, I will finish writing the program”

TrungDT (FUHN) MAD111 Chapter 1 23 / 29

Example 2. Given the hypotheses:

”If you send me an email, I will finish writing the program”

”If you do not send email then I will go to bed early”

TrungDT (FUHN) MAD111 Chapter 1 23 / 29

Example 2. Given the hypotheses:

”If you send me an email, I will finish writing the program”

”If you do not send email then I will go to bed early”
”If I go to bed early then I will go jogging tomorrow morning”

TrungDT (FUHN) MAD111 Chapter 1 23 / 29

Example 2. Given the hypotheses:

”If you send me an email, I will finish writing the program”

”If you do not send email then I will go to bed early”
”If I go to bed early then I will go jogging tomorrow morning”

Show that these hypotheses lead to the conclusion: ”If I do not finish
writing the program then I will go jogging tomorrow morning”.

TrungDT (FUHN) MAD111 Chapter 1 23 / 29

TrungDT (FUHN) MAD111 Chapter 1 24 / 29
Some fallacies

TrungDT (FUHN) MAD111 Chapter 1 24 / 29

Some fallacies
Fallacy of affirming the conclusion: [(p → q) ∧ q] → p

TrungDT (FUHN) MAD111 Chapter 1 24 / 29

Some fallacies
Fallacy of affirming the conclusion: [(p → q) ∧ q] → p
Fallacy of denying the hypothesis: [(p → q) ∧ ¬p] → ¬q

TrungDT (FUHN) MAD111 Chapter 1 24 / 29

Some fallacies
Fallacy of affirming the conclusion: [(p → q) ∧ q] → p
Fallacy of denying the hypothesis: [(p → q) ∧ ¬p] → ¬q

TrungDT (FUHN) MAD111 Chapter 1 24 / 29

Rules of Inference for Quantified Statements

TrungDT (FUHN) MAD111 Chapter 1 25 / 29

Rules of Inference for Quantified Statements

Name Rule of Inference

Universal instantiation ∀xP(x)
∴ P(c), c is arbitrary
Universal generalization P(c), c is arbitrary
∴ ∀xP(x)
Existential instantiation ∃xP(x)
∴ P(c), for some c
Existential generalization P(c), for some c
∴ ∃xP(x)

TrungDT (FUHN) MAD111 Chapter 1 25 / 29

Rules of Inference for Quantified Statements

Name Rule of Inference

Universal instantiation ∀xP(x)
∴ P(c), c is arbitrary
Universal generalization P(c), c is arbitrary
∴ ∀xP(x)
Existential instantiation ∃xP(x)
∴ P(c), for some c
Existential generalization P(c), for some c
∴ ∃xP(x)

TrungDT (FUHN) MAD111 Chapter 1 25 / 29

TrungDT (FUHN) MAD111 Chapter 1 26 / 29
Example 1. Given the hypotheses:

TrungDT (FUHN) MAD111 Chapter 1 26 / 29

Example 1. Given the hypotheses:

”Each student of SE0000 must take Discrete Math”,

TrungDT (FUHN) MAD111 Chapter 1 26 / 29

Example 1. Given the hypotheses:

”Each student of SE0000 must take Discrete Math”,

”Jenifer is a student of SE0000”.

TrungDT (FUHN) MAD111 Chapter 1 26 / 29

Example 1. Given the hypotheses:

”Each student of SE0000 must take Discrete Math”,

”Jenifer is a student of SE0000”.

Show that these hypotheses lead to the conclusion ”Jenifer must take
Discrete Math”.

TrungDT (FUHN) MAD111 Chapter 1 26 / 29

Example 1. Given the hypotheses:

”Each student of SE0000 must take Discrete Math”,

”Jenifer is a student of SE0000”.

Show that these hypotheses lead to the conclusion ”Jenifer must take
Discrete Math”.

Example 2. Given the hypotheses:

TrungDT (FUHN) MAD111 Chapter 1 26 / 29

Example 1. Given the hypotheses:

”Each student of SE0000 must take Discrete Math”,

”Jenifer is a student of SE0000”.

Show that these hypotheses lead to the conclusion ”Jenifer must take
Discrete Math”.

Example 2. Given the hypotheses:

”Some student of SE0000 has not read this book”,

TrungDT (FUHN) MAD111 Chapter 1 26 / 29

Example 1. Given the hypotheses:

”Each student of SE0000 must take Discrete Math”,

”Jenifer is a student of SE0000”.

Show that these hypotheses lead to the conclusion ”Jenifer must take
Discrete Math”.

Example 2. Given the hypotheses:

”Some student of SE0000 has not read this book”,

”Every student of SE0000 passed the exam”.

TrungDT (FUHN) MAD111 Chapter 1 26 / 29

Example 1. Given the hypotheses:

”Each student of SE0000 must take Discrete Math”,

”Jenifer is a student of SE0000”.

Show that these hypotheses lead to the conclusion ”Jenifer must take
Discrete Math”.

Example 2. Given the hypotheses:

”Some student of SE0000 has not read this book”,

”Every student of SE0000 passed the exam”.

Show that these hypotheses lead to the conclusion ”Some student of

SE0000 who passed the exam has not read this book”.

TrungDT (FUHN) MAD111 Chapter 1 26 / 29

1.6 Introduction to Proofs

TrungDT (FUHN) MAD111 Chapter 1 27 / 29

1.6 Introduction to Proofs

Direct method

TrungDT (FUHN) MAD111 Chapter 1 27 / 29

1.6 Introduction to Proofs

Direct method
Problem: Prove that the statement p → q is correct.

TrungDT (FUHN) MAD111 Chapter 1 27 / 29

1.6 Introduction to Proofs

Direct method
Problem: Prove that the statement p → q is correct.
Proof: Assume that p is true. We will show that q is true.

TrungDT (FUHN) MAD111 Chapter 1 27 / 29

1.6 Introduction to Proofs

Direct method
Problem: Prove that the statement p → q is correct.
Proof: Assume that p is true. We will show that q is true.

Example. Prove that if n is an odd number then n2 is also an odd number.

TrungDT (FUHN) MAD111 Chapter 1 27 / 29

1.6 Introduction to Proofs

Direct method
Problem: Prove that the statement p → q is correct.
Proof: Assume that p is true. We will show that q is true.

Example. Prove that if n is an odd number then n2 is also an odd number.

Indirect method - Proof by contraposition

TrungDT (FUHN) MAD111 Chapter 1 27 / 29

1.6 Introduction to Proofs

Direct method
Problem: Prove that the statement p → q is correct.
Proof: Assume that p is true. We will show that q is true.

Example. Prove that if n is an odd number then n2 is also an odd number.

Indirect method - Proof by contraposition
Problem: Prove that the statement p → q is correct.

TrungDT (FUHN) MAD111 Chapter 1 27 / 29

1.6 Introduction to Proofs

Direct method
Problem: Prove that the statement p → q is correct.
Proof: Assume that p is true. We will show that q is true.

Example. Prove that if n is an odd number then n2 is also an odd number.

Indirect method - Proof by contraposition
Problem: Prove that the statement p → q is correct.
Proof: Assume that q is false. We will show that p is also false.

TrungDT (FUHN) MAD111 Chapter 1 27 / 29

1.6 Introduction to Proofs

Direct method
Problem: Prove that the statement p → q is correct.
Proof: Assume that p is true. We will show that q is true.

Example. Prove that if n is an odd number then n2 is also an odd number.

Indirect method - Proof by contraposition
Problem: Prove that the statement p → q is correct.
Proof: Assume that q is false. We will show that p is also false.

Example. Show that if x is an irrational number then 1/x is also

irrational.

TrungDT (FUHN) MAD111 Chapter 1 27 / 29

TrungDT (FUHN) MAD111 Chapter 1 28 / 29
Proof by contradiction

TrungDT (FUHN) MAD111 Chapter 1 28 / 29

Proof by contradiction
Problem: Prove that the statement p is correct.

TrungDT (FUHN) MAD111 Chapter 1 28 / 29

Proof by contradiction
Problem: Prove that the statement p is correct.
Proof: Suppose that p is not correct. We will find a contradiction.

TrungDT (FUHN) MAD111 Chapter 1 28 / 29

Proof by contradiction
Problem: Prove that the statement p is correct.
Proof: Suppose that p is not correct. We will find a contradiction.

√
Example. Show that 2 is irrational.

TrungDT (FUHN) MAD111 Chapter 1 28 / 29

Proof by contradiction
Problem: Prove that the statement p is correct.
Proof: Suppose that p is not correct. We will find a contradiction.

√
Example. Show that 2 is irrational.

TrungDT (FUHN) MAD111 Chapter 1 28 / 29

1.7 Proof Methods and Strategies

TrungDT (FUHN) MAD111 Chapter 1 29 / 29

1.7 Proof Methods and Strategies

Read textbook!

TrungDT (FUHN) MAD111 Chapter 1 29 / 29