The Foundations: Logic and

Proofs
Chapter 1, Part I: Propositional
Logic

Mr. Shoaib Raza

Discrete Mathematics
Discrete mathematics is the part of mathematics devoted to the
study of discrete objects (Kenneth H. Rosen, 7th edition).
● How to think (and argument) mathematically.

● Learn mathematical facts and their applications.

● Discrete mathematics is the mathematical study of

properties, and relationships among discrete
objects.
● Discrete mathematics is the study of mathematical
structures that are fundamentally discrete rather
than continuous.
 Discrete Vs Continuous
● Continuous Data: A set of data is said to be continuous if the values
belonging to the set can take on any value within a finite or infinite
interval.
● Continuous data is information that can be measured on a
continuum or scale. , e.g., [ 0, 70].
● Continuous data can have almost any numeric value and can be
meaningfully subdivided into finer and finer increments, depending
upon the precision of the measurement system.

● Discrete Data: A set of data is said to be discrete if the values

belonging to the set are distinct and separate. It is counted
e.g., {1,2,3,4,5,6}
3
4
Why DM?

• Digital computers are based on discrete “atoms”

(bits).
• Therefore, both a computer’s
⚪ structure (circuits) and
⚪ operations (execution of algorithms)
can be described by discrete mathematics.
Applications
 Course Description:
● This class teaches students
⚪ how to think logically and mathematically.
⚪ It stresses mathematical reasoning and different ways to solve problems.
It enhance your ability to formulate and solve applied problems, to analyze
and interpret algorithms and functions and to use them effectively.

● Five important themes are interwoven in this class:

⚪ mathematical reasoning,
⚪ combinatorial analysis,
⚪ discrete structures,
⚪ algorithmic thinking,
⚪ applications and modeling
7
Course Outline

● Logic and Proofs

● Sets and Functions
● Relations
● Counting and Recurrence Relations
● Graphs
● Trees
● Number Theory
● Discrete Probability and Finite State Automata

8
TEXT Book:
● Discrete Mathematics & its Applications,
7th edition. By Kenneth H. Rosen.

References Book:
● Invitation to Discrete Maths, 2nd edition.
By Matousek and Nesetril.
● Discrete Mathematics. By Lovasz, Pelikan
and Vesztergombi.
9
Logic

● Logic is fundamental because it allows us to understand

meaning of statements, deduce information about
mathematical structures and uncover further structures.

● The rules of logic specify the meaning of mathematical

statements.

● These rules are used to distinguish between valid and

invalid arguments.

10
 Applications: Logic
Hardware and software specifications

Formal: Input_wire_A
value in {0, 1}

Example 1: Adder
One-bit Full Adder
with
Carry-In and

Carry-Out
4-bit full adder

Example 2: System Specification:

●The router can send packets to the edge system only if it supports the new address space.
●For the router to support the new address space it’s necessary that the latest software release
be installed.
●The router can send packets to the edge system if the latest software release is installed.
●The router does not support the new address space.
11
How to write these specifications in a rigorous / formal way? Use
Applications: Number Theory
RSA and Public-key Cryptography

Alice and Bob have never met but they would like to
exchange a message. Eve would like to eavesdrop.
E.g. between you and the Bank of America.
They could come up with a good
encryption algorithm and exchange the
encryption key – but how to do it without
Eve getting it? (If Eve gets it, all security
is lost.)

CS folks found the solution:

public key encryption. Quite
remarkable
that is feasible.

12
 Applications: Coloring a Map

How to color this map so that no two

adjacent regions have the same
color?
13
 Applications: Graph representation

Coloring the nodes of the graph:

What’s the minimum number of colors such that any two nodes
connected by an edge have different colors?
14
 Applications: Scheduling of Final Exams

● How can the final exams at FAST be

scheduled so that no student has two exams
at the same time?

Graph:
A vertex correspond to a course.
An edge between two vertices denotes that there is at least one
common
student in the courses they represent.
Each time slot for a final exam is represented by a different color.

A coloring of the graph corresponds to a valid schedule of the exams.

15
Applications: Scheduling of Final Exams

1 1
Time Courses
Period
2 7 2 I 1,6
7
II 2
III 3,5
IV 4,7
6 3 6 3

5 4 5 4

What are the constraints between courses?

16 Find a valid coloring
 Applications: Index Registers

● The execution of loops can be speeded up by storing

frequently used variables temporarily in registers in the central
processing unit, instead in the regular memory. For a given
loop, how many index registers are needed?

● Each vertex corresponds to a variable in the loop.

● An edge between two vertices denotes the fact that the corresponding
variables must be stored in registers at the same time during the
execution of the loop.
● Chromatic number of the graph gives the number of index registers
needed.

17
Logic
● Logic is fundamental because it allows us to
understand meaning of statements, deduce
information about mathematical structures and
uncover further structures.

● The rules of logic specify the meaning of

mathematical statements.

● These rules are used to distinguish between

valid and invalid arguments.
18
Propositional Logic
Introduction
● A proposition is a declarative sentence (a
sentence that declares a fact) that is either
true or false, but not both.
● Are the following sentences propositions?
⚪ Islamabad is the capital of Pakistan. (Yes)
⚪ Read this carefully. (No)
⚪ 1+2=3 (Yes)
⚪ x+1=2 (No)
⚪ What time is it? (No)

19
20
Examples: Propositions

21
22
Activity 1

Write down at least 5 examples of propositions and

Non-propositions.
24
Logical operators are used to form new propositions also called compound
propositions from two or more existing propositions.

The logical operators are also called connectives.

Propositional Logic – the area of logic that deals with propositions

25
1. Negation:
DEFINITION 1:
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.”
⚪ Find the negation of the proposition “At least 10 mm of rain fell
today in Karachi.” and express this in simple English.
Solution: The negation is “It is not the case that at least 10 mm of
rain fell today in Karachi.”
26
In simple English, “Less than 10 mm of rain fell today in
Karachi.”
Negation:
● Note: Always assume fixed times, fixed places, and particular people
unless otherwise noted.
● Truth table: The Truth Table for the
Negation of a Proposition.
p ¬p
T F
F T

27
2. Conjunction:
DEFINITION 2
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.

28
3. Disjunction:
DEFINITION 3
Let p and q be propositions. The disjunction of p and q, denoted by p ν
q, is the proposition “p or q”. The disjunction 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 3 uses inclusive or.
29
30
4. Exclusive OR:
DEFINITION 4
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.

The Truth Table for The Truth Table for The Truth Table for the
the Conjunction of the Disjunction of Exclusive Or (XOR) of
Two Propositions. Two Propositions. Two Propositions.
p q pΛq p q pνq p q p q
T T T T T T T T F
T F F T F T T F T
F T F F T T F T T
F F F F F F F F F
31
32
33
5. Implication / Conditional Statements:

DEFINITION 5
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. In the conditional
statement p → q, p is called the hypothesis (or antecedent or premise)
and q is called the conclusion (or consequence).
● A conditional statement is also called an implication.
● Example: “If I am elected, then I will lower taxes.” p→q
implication:
elected, lower taxes. T T |T
not elected, lower taxes. F T |T
not elected, not lower taxes. F F |T
elected, not lower taxes. T F |F

34
Example: Conditional Statements
● Example:
⚪ Let p be the statement “Maria learns discrete mathematics.” and
q the statement “Maria will find a good job.” Express the
statement p → q as a statement in English.
Solution: Any of the following -
“If Maria learns discrete mathematics, then she will find a
good job.
“Maria will find a good job when she learns discrete
mathematics.”
“For Maria to get a good job, it is sufficient for her to learn
discrete mathematics.”
“Maria will find a good job unless she does not learn
discrete mathematics.”
35
Examples: Implication

36
Examples: Implication

Some other cases of

implications:

37
38
● Other conditional statements:
⚪ Converse of p → q : q → p
⚪ Contrapositive of p → q : ¬ q → ¬ p
⚪ Inverse of p → q : ¬ p → ¬ q

39
Converse, Contrapositive, and Inverse
● From p →q we can form new conditional
statements .
⚪ q →p is the converse of p →q
⚪ ¬q → ¬ p is the contrapositive of p →q
⚪ ¬p→¬q is the inverse of p →q

Example: Find the converse, inverse, and contrapositive of

“It is raining is a sufficient condition for my not going to town.”
Solution:
converse: If I do not go to town, then it is raining.
inverse: If it is not raining, then I will go to town.
contrapositive: If I go to town, then it is not raining.
Contrapositive:

● Contrapositive of p → q is ¬q → ¬p
● Any proposition and its contrapositive are
logically equivalent (have the same truth
table values) – Check with the truth table.
● E.g. The contrapositive of “If you get 100%
in this course, you will get an A+” is “If you
do not get an A+ in this course, you did not
get 100%”.
41
Converse:

● Converse of p → q is q → p
● Both are not logically equivalent.
● Ex 1: “If you get 100% in this course, you
will get an A+” and “If you get an A+ in this
course, you scored 100%” are not
equivalent.
● Ex 2: If you won the lottery, you are rich.

42
Inverse:

● Inverse of p → q is ¬p → ¬q
● Both are not logically equivalent.
● Ex1 : “If you get 100% in this course, you
will get an A+” and “If you didn’t 100%,
then won’t have an A+ in this course.” are
not equivalent.
● Ex2: You can not ride the roller coaster if
you are under 4 feet. What is its inverse
statement?
43
Example of converse (1/2)

● Find the converse of the following

statement:
● R: ‘Raining tomorrow is a sufficient
condition for my not going to town.’
● Step 1: Assign propositional variables to
● component propositions
● P: It will rain tomorrow
● Q: I will not go to town
44
Example of converse (2/2)
● Step 2: Symbolize the assertion R: P → Q
● Step 3: Symbolize the converse Q → P
● Step 4: Convert the symbols back into words
‘If I don’t go to town then it will rain tomorrow’ or
‘Raining tomorrow is a necessary condition for my not
going to town.’ or
‘My not going to town is a sufficient condition for it
raining tomorrow.’

45
6. Bi-implications:
DEFINITION 6
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 ↔ q has the same truth value as (p → q) Λ (q → p)

● “if and only if” can be expressed by “iff”
● Example:
⚪ Let p be the statement “You can take the flight” and let q be the
statement “You buy a ticket.” Then p ↔ q is the statement
“You can take the flight if and only if you buy a ticket.”
Implication:
If you buy a ticket you can take the flight.
If you don’t buy a ticket you cannot take the flight.
46
Bi-implications:
If p denotes “I am at home.” and q denotes “It is raining.” then
p ↔q denotes “I am at home if and only if it is raining.”

The Truth Table for

the Biconditional p
↔ q.
p q p↔ q
T T T
T F F
F T F
F F T
47
Expressing the Biconditional

● Some alternative ways “p if and only if q”

is expressed in English:
⚪ p is necessary and sufficient for q
⚪ if p then q , and conversely
⚪ p iff q
49
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 50
Example Truth Table

● Construct a truth table for

p q r ¬r p∨q p∨q→
¬r
T T T F T F
T T F T T T
T F T F T F
T F F T T T
F T T F T F
F T F T T T
F F T F F T
F F F T F T
Problem:
● How many rows are there in a truth table with
n propositional variables?

Solution: 2n We will see how to do this in

Chapter 6.

● Note that this means that with n propositional

variables, we can construct 2n distinct (i.e.,
not equivalent) propositions.
 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
53
 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:
(r Λ ¬ s) → ¬q.
You cannot ride the coaster if You are under 4 feet tall and you are not
older than 16 Years old.
54
Translating English Sentences
● Steps to convert an English sentence to a
statement in propositional logic
⚪ Identify atomic propositions and represent using
propositional variables.
⚪ Determine appropriate logical connectives
● “If I go to Harry’s or to the country, I will not go
shopping.”
⚪ p: I go to Harry’s
⚪ q: I go to the country. If p or q then not r.
⚪ r: I will go shopping.
Translating English Sentences
● 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).

56
System Specifications
● System and Software engineers take requirements in
English and express them in a precise specification
language based on logic.
Example: Express in propositional logic:
“The automated reply cannot be sent when the file system
is full”
Solution: One possible solution: Let p denote “The
automated reply can be sent” and q denote “The file
system is full.”
q→ ¬ p
1.1 Propositional Logic
Logic and Bit Operations
● Computers represent information using bits.
● A bit is a symbol with two possible values, 0 and 1.
● By convention, 1 represents T (true) and 0 represents F (false).
● A variable is called a Boolean variable if its value is either true or
false.
● Bit operation – replace true by 1 and false by 0 in logical
operations.

Table for the Bit Operators OR, AND, and XOR.

x y xνy xΛy x y
0 0 0 0 0
0 1 1 0 1
1 0 1 0 1
1 1 1 1 0 58
1.1 Propositional Logic
DEFINITION 7
A bit string is a sequence of zero or more bits. The length of this string
is the number of bits in the string.

● Example: Find the bitwise OR, bitwise AND, and bitwise XOR of the
bit string 01 1011 0110 and 11 0001 1101.
Solution:
01 1011 0110
11 0001 1101
-------------------
11 1011 1111 bitwise OR
01 0001 0100 bitwise AND
10 1010 1011 bitwise XOR

59
Propositional Equivalences
DEFINITION 1
A compound proposition that is always true, no matter
what the truth values of the propositions that occurs in
it, is called a tautology.
A compound proposition that is always false is called a
contradiction.
A compound proposition that is neither a tautology or a
contradiction is called a contingency.
Examples of a Tautology and a Contradiction.
p ¬p p ν ¬p p Λ ¬p

T F T F
F T T F 60
61
62
Propositional Equivalences
DEFINITION 2
The compound propositions p and q are called logically equivalent if p ↔
q is a tautology. The notation p ≡ q denotes that p and q are logically
equivalent.

● Compound propositions that have the same truth values in all

possible cases are called logically equivalent.
● Example: Show that ¬p ν q and p → q are logically equivalent.

Truth Tables for ¬p ν q and p → q .

p q ¬p ¬p ν q p→q
T T F T T
T F F F F
F T T T T
63
F F T T T
Propositional Equivalences
● In general, 2n rows are required if a compound proposition involves n
propositional variables in order to get the combination of all truth
values.

64
Propositional Equivalences

65
Applications: Boolean Searches
● Logical connectives are used extensively in
searches of large collections of information.
⚪ Example: indexes of Web pages.

● AND - used to match records that contain both of

two search terms.
● OR - used to match one or both of two search terms.
● NOT - used to exclude a particular search term.

● Read about: Web Page Searching

Applications: Logic Puzzles
● Puzzles (important job interview question) that
can be solved using logical reasoning

● [Sm78] Smullyan: An island that has two kinds of

inhabitants.
⚪ knights, who always tell the truth.
⚪ knaves, who always lie.
● You encounter two people A and B.
● What are A and B if:
⚪ A says “B is a knight” and
⚪ B says “The two of us are opposite types?”
Example 1:
● p: A is a knight ¬p: A is a knave
● q: B is a knight ¬q: B is a knave

● Consider the possibility that A is a knight;

⚪ So, p is true. And he is telling truth.
⚪ So, q is true. So, A and B are the same type.

● However, if B is a knight, then B ’s statement that A

and B are of opposite types, the statement (p ∧¬q) ∨
(¬p ∧ q), would have to be true, which it is not,
because A and B are both knights. Consequently, we
can conclude that A is not a knight, that is, that p is
false.
Example 1: Solution (cont..)

● Consider the possibility that A is a knave,

⚪ everything a knave says is false; q is true, is a
lie.
⚪ So, q is false. B is also a knave.
⚪ B ’s statement that A and B are opposite types
is a lie, which is consistent with both A and B
being knaves.
● We can conclude that both A and B
are knaves.
 Example
2:
● A father tells his two children, a boy and a girl, to
play in their backyard without getting dirty.
● However, while playing, both children get mud on
their foreheads. When the children stop playing,
the father says “At least one of you has a muddy
forehead,” and then asks the children to answer
“Yes” or “No” to the question: “Do you know
whether you have a muddy forehead?”
● The father asks this question twice. What will the
children answer each time this question is asked,
assuming that a child can see whether his or her
sibling has a muddy forehead, but cannot see his
or her own forehead?
● Assume that both children are honest and that the
children answer each question simultaneously.
Example
2:

71
Example 3:

72
Propositional Satisfiability
● A compound proposition is satisfiable if there is an
assignment of truth values to its variables that makes it
true.
● When no such assignments exists, that is, when the
compound proposition is false for all assignments of truth
values to its variables, the compound proposition is
unsatisfiable.

● A truth table can be used to determine whether a

compound proposition is satisfiable, or equivalently,
whether its negation is a tautology.
74
 Propositional Equivalences
Constructing New Logical Equivalences
● Example: Show that ¬(p → q ) and p Λ ¬q are logically equivalent.
Solution:
¬(p → q ) ≡ ¬(¬p ν q) by example discussed in slide 66
≡ ¬(¬p) Λ ¬q by the second De Morgan law
≡ p Λ ¬q by the double negation law
● Example: Show that (p Λ q) → (p ν q) is a tautology.
Solution: To show that this statement is a tautology, we will use logical
equivalences to demonstrate that it is logically equivalent to T.
(p Λ q) → (p ν q) ≡ ¬(p Λ q) ν (p ν q) by example already discussed
≡ (¬ p ν ¬q) ν (p ν q) by the first De Morgan law
≡ (¬ p ν p) ν (¬ q ν q) by the associative and
communicative law for disjunction
≡TνT
≡T 75
● Note: The above examples can also be done using truth tables.
76
77
78
79
80
81
82
83
Exercise

84
The Foundations: Logic and
Proofs
Chapter 1, Part II: Predicate Logic
Summary

● Predicate Logic (First-Order Logic (FOL),

Predicate Calculus)
⚪ The Language of Quantifiers
⚪ Logical Equivalences
⚪ Nested Quantifiers
⚪ Translation from Predicate Logic to English
⚪ Translation from English to Predicate Logic
Predicates and Quantifiers
Section 1.4
Section Summary
● Predicates
● Variables
● Quantifiers
⚪ Universal Quantifier
⚪ Existential Quantifier
● Negating Quantifiers
⚪ De Morgan’s Laws for Quantifiers
● Translating English to Logic
● Logic Programming (optional)
Propositional Logic Not Enough

● If we have:
“All men are mortal.”
“Socrates is a man.”
● Does it follow that “Socrates is mortal?”
● Can’t be represented in propositional
logic. Need a language that talks about
objects, their properties, and their
relations.
● Later we’ll see how to draw inferences.
Introducing Predicate Logic
● Predicate logic uses the following new
features:
⚪ Variables: x, y, z
⚪ Predicates: P(x), M(x)
⚪ Quantifiers (to be covered in a few slides):
● Propositional functions are a generalization of
propositions.
⚪ They contain variables and a predicate, e.g., P(x)
⚪ Variables can be replaced by elements from their
domain.
Propositional Functions
● Propositional functions become propositions (and have
truth values) when their variables are each replaced by
a value from the domain (or bound by a quantifier, as
we will see later).
● The statement P(x) is said to be the value of the
propositional function P at x.
● For example, let P(x) denote “x > 0” and the domain
be the integers. Then:
P(-3) is false.
P(0) is false.
P(3) is true.
● Often the domain is denoted by U. So in this example
U is the integers.
Examples of Propositional Functions
● Let “x + y = z” be denoted by R(x, y, z) and U (for all three
variables) be the integers. Find these truth values:
R(2,-1,5)
Solution: F
R(3,4,7)
Solution: T
R(x, 3, z)
Solution: Not a Proposition
● Now let “x - y = z” be denoted by Q(x, y, z), with U as the
integers. Find these truth values:
Q(2,-1,3)
Solution: T
Q(3,4,7)
Solution: F
Q(x, 3, z)
Solution: Not a Proposition
Compound Expressions
● Connectives from propositional logic carry over to predicate
logic.
● If P(x) denotes “x > 0,” find these truth values:
P(3) ∨ P(-1) Solution: T
P(3) ∧ P(-1) Solution: F
P(3) → P(-1) Solution: F
P(3) → P(1) Solution: T
● Expressions with variables are not propositions and therefore
do not have truth values. For example,
P(3) ∧ P(y)
P(x) → P(y)
● When used with quantifiers (to be introduced next), these
expressions (propositional functions) become propositions.
Quantifiers
Charles Peirce (1839-1914)

● We need quantifiers to express the meaning of English

words including all and some:
⚪ “All men are Mortal.”
⚪ “Some cats do not have fur.”
● The two most important quantifiers are:
⚪ Universal Quantifier, “For all,” symbol: ∀
⚪ Existential Quantifier, “There exists,” symbol: ∃
● We write as in ∀x P(x) and ∃x P(x).
● ∀x P(x) asserts P(x) is true for every x in the domain.
● ∃x P(x) asserts P(x) is true for some x in the domain.
● The quantifiers are said to bind the variable x in these
expressions.
Quantifiers
⚪ Universal Quantifier, “For all,” symbol: ∀
⚪ Existential Quantifier, “There exists,” symbol:
∃

95
Universal Quantifier
⚪ ∀x P(x) is read as “ For all x, P(x)” or “For every
x, P(x)”
Examples:
1) If P(x) denotes “x > 0” and U is the integers, then ∀x
P(x) is false.
2) If P(x) denotes “x > 0” and U is the positive integers,
then ∀x P(x) is true.
3) If P(x) denotes “x is even” and U is the integers, then
∀ x P(x) is false.
Existential Quantifier

● ∃x P(x) is read as “For some x, P(x)”, or

as “There is an x such that P(x),” or “For
at least one x, P(x).”
Examples:
1. If P(x) denotes “x > 0” and U is the integers, then ∃x
P(x) is true. It is also true if U is the positive integers.
2. If P(x) denotes “x < 0” and U is the positive integers,
then ∃x P(x) is false.
3. If P(x) denotes “x is even” and U is the integers, then
∃x P(x) is true.
Uniqueness Quantifier (optional)
● ∃!x P(x) means that P(x) is true for one and only one x in the
universe of discourse.
● This is commonly expressed in English in the following
equivalent ways:
⚪ “There is a unique x such that P(x).”
⚪ “There is one and only one x such that P(x)”
● Examples:
1. If P(x) denotes “x + 1 = 0” and U is the integers, then ∃!x P(x) is true.
2. But if P(x) denotes “x > 0,” then ∃!x P(x) is false.
● The uniqueness quantifier is not really needed as the
restriction that there is a unique x such that P(x) can be
expressed as:
∃x (P(x) ∧∀y (P(y) → y =x))
Thinking about Quantifiers
● When the domain of discourse is finite, we can think of
quantification as looping through the elements of the domain.
● To evaluate ∀x P(x) loop through all x in the domain.
⚪ If at every step P(x) is true, then ∀x P(x) is true.
⚪ If at a step P(x) is false, then ∀x P(x) is false and the loop
terminates.
● To evaluate ∃x P(x) loop through all x in the domain.
⚪ If at some step, P(x) is true, then ∃x P(x) is true and the loop
terminates.
⚪ If the loop ends without finding an x for which P(x) is true, then ∃x
P(x) is false.
● Even if the domains are infinite, we can still think of the
quantifiers this fashion, but the loops will not terminate in
some cases.
Properties of Quantifiers
● The truth value of ∃x P(x) and ∀ x P(x)
depend on both the propositional function P(x) and
on the domain U.
● Examples:
1. If U is the positive integers and P(x) is the
statement “x < 2”, then ∃x P(x) is true, but
∀ x P(x) is false.
2. If U is the negative integers and P(x) is the
statement “x < 2”, then both ∃x P(x) and ∀
x P(x) are true.
3. If U consists of 3, 4, and 5, and P(x) is the
statement “x > 2”, then both ∃x P(x) and
∀ x P(x) are true. But if P(x) is the statement “x <
2”, then both ∃x P(x) and ∀ x P(x) are
false.
Precedence of Quantifiers

● The quantifiers ∀ and ∃ have higher

precedence than all the logical operators.
● For example, ∀x P(x) ∨ Q(x) means (∀x
P(x))∨ Q(x)
● ∀x (P(x) ∨ Q(x)) means something different.
● Unfortunately, often people write ∀x P(x) ∨
Q(x) when they mean ∀ x (P(x) ∨ Q(x)).
Translating from English to Logic
Example 1: Translate the following sentence
into predicate logic: “Every student in this
class has taken a course in Java.”
Solution:
First decide on the domain U.
Solution 1: If U is all students in this class, define a
propositional function J(x) denoting “x has taken a
course in Java” and translate as ∀x J(x).
Solution 2: But if U is all people, also define a
propositional function S(x) denoting “x is a student
in this class” and translate as ∀x (S(x)→ J(x)).
∀x (S(x) ∧ J(x)) is not correct. What does it mean?
For example,
we may be interested in a wider group of people than only those in this class.
If we change the domain to consist of all people, we will need to express our
statement as
“For every person x, if person x is a student in this class then x has studied
Java.”
If S(x) represents the statement that person x is in this class, we see that our
statement can be expressed as ∀x(S(x) → J(x)).
[Caution! Our statement cannot be expressed as ∀x(S(x) ∧ J(x)) because
this statement says that all people are students in this class and have studied
Java!]

103
Translating from English to Logic
Example 2: Translate the following sentence
into predicate logic: “Some student in this
class has taken a course in Java.”
Solution:
First decide on the domain U.
Solution 1: If U is all students in this class, translate
as
∃x J(x)
Solution 1: But if U is all people, then translate as
∃x (S(x) ∧ J(x))
∃x (S(x)→ J(x)) is not correct. What does it mean?
if we are interested in people other than those in this class, we look at the
statement a little differently. Our statement can be expressed as
“There is a person x having the properties that x is a student in this class and
x has studied Java.”
In this case, the domain for the variable x consists of all people. We introduce
S(x) to represent
“x is a student in this class.” Our solution becomes ∃x(S(x) ∧ J(x)) because
the statement is that there is a person x who is a student in this class and
who has studied Java.
[Caution! Our statement cannot be expressed as ∃x(S(x) → J(x)), which is
true when there is someone not in the class because, in that case, for such a
person x, S(x) → J(x) becomes either F→T or F→F, both of which are true.]

105
Returning to the Socrates Example
● Introduce the propositional functions Man(x)
denoting “x is a man” and Mortal(x) denoting
“x is mortal.” Specify the domain as all
people.
● The two premises are:

● The conclusion is:

● Later we will show how to prove that the

conclusion follows from the premises.
Equivalences in Predicate Logic
● Statements involving predicates and
quantifiers are logically equivalent if and only
if they have the same truth value
⚪ for every predicate substituted into these
statements and
⚪ for every domain of discourse used for the variables
in the expressions.
● The notation S ≡T indicates that S and T are
logically equivalent.
● Example: ∀x ¬¬S(x) ≡ ∀x S(x)
Thinking about Quantifiers as
Conjunctions and Disjunctions
● If the domain is finite, a universally quantified proposition is
equivalent to a conjunction of propositions without quantifiers
and an existentially quantified proposition is equivalent to a
disjunction of propositions without quantifiers.
● If U consists of the integers 1,2, and 3:

● Even if the domains are infinite, you can still think of the
quantifiers in this fashion, but the equivalent expressions
without quantifiers will be infinitely long.
Negating Quantified Expressions
● Consider ∀x J(x)
“Every student in your class has taken a course in
Java.”
Here J(x) is “x has taken a course in Java” and
the domain is students in your class.
● Negating the original statement gives “It is not
the case that every student in your class has
taken a course in Java.” This implies that
“There is a student in your class who has not
taken a course in Java.”
Symbolically ¬∀x J(x) and ∃x ¬J(x) are
equivalent
Negating Quantified Expressions
(continued)
● Now Consider ∃ x J(x)
“There is a student in this class who has taken a
course in Java.”
Where J(x) is “x has taken a course in Java.”
● Negating the original statement gives “It is not
the case that there is a student in this class
who has taken Java.” This implies that “Every
student in this class has not taken a course in
Java”
Symbolically ¬∃ x J(x) and ∀ x ¬J(x) are
equivalent
De Morgan’s Laws for Quantifiers
● The rules for negating quantifiers are:

● The reasoning in the table shows that:

● These are important. You will use these.

Translation from English to Logic
Examples:
1. “Some student in this class has visited
Mexico.”
Solution: Let M(x) denote “x has visited Mexico”
and S(x) denote “x is a student in this class,” and
U be all people.
∃x (S(x) ∧ M(x))
2. “Every student in this class has visited
Canada or Mexico.”
Solution: Add C(x) denoting “x has visited Canada.”
∀x (S(x)→ (M(x)∨C(x)))
Some Fun with Translating from English
into Logical Expressions
● U = {Nitwits, Blubbers, Oddments}
F(x): x is a Nitwit
S(x): x is a Blubber
T(x): x is a Oddment
Translate “Everything is a Nitwit”

Solution: ∀x F(x)
Translation (cont)

● U = {Nitwits, Blubbers, Oddments}

F(x): x is a Nitwit
S(x): x is a Blubber
T(x): x is a Oddment
“Nothing is a Blubber.”

Solution: ¬∃x S(x) What is this equivalent

to?
Solution: ∀x ¬ S(x)
Translation (cont)

● U = {Nitwits, Blubbers, Oddments}

F(x): x is a Nitwit
S(x): x is a Blubber
T(x): x is a Oddment
“All Nitwits are Blubbers.”

Solution: ∀x (F(x)→ S(x))

Translation (cont)

● U = {Nitwits, Blubbers, Oddments}

F(x): x is a Nitwit
S(x): x is a Blubber
T(x): x is a Oddment
“Some Nitwits are Oddments.”

Solution: ∃x (F(x) ∧ T(x))

Translation (cont)

● U = {Nitwits, Blubbers, Oddments}

F(x): x is a Nitwit
S(x): x is a Blubber
T(x): x is a Oddment
“No Blubber is a Oddment.”

Solution: ¬∃x (S(x) ∧ T(x)) What is this

equivalent to?
Solution: ∀x (¬S(x) ∨ ¬T(x))
Translation (cont)

● U = {Nitwits, Blubbers, Oddments}

F(x): x is a Nitwit
S(x): x is a Blubber
T(x): x is a Oddment
“If any Nitwit is a Blubber then it is also a
Oddment.”

Solution: ∀x ((F(x) ∧ S(x))→ T(x))

 System Specification Example

● Predicate logic is used for specifying properties that systems must

satisfy.
● For example, translate into predicate logic:
⚪ “Every mail message larger than one megabyte will be
compressed.”
⚪ “If a user is active, at least one network link will be available.”
● Decide on predicates and domains (left implicit here) for the
variables:
⚪ Let L(m, y) be “Mail message m is larger than y megabytes.”
⚪ Let C(m) denote “Mail message m will be compressed.”
⚪ Let A(u) represent “User u is active.”
⚪ Let S(n, x) represent “Network link n is state x.

● Now we have:
Lewis Carroll Example
Charles Lutwidge
Dodgson
(AKA Lewis Caroll)
(1832-1898)
● The first two are called premises and the third is called the
conclusion.
1. “All lions are fierce.”
2. “Some lions do not drink coffee.”
3. “Some fierce creatures do not drink coffee.”
● Here is one way to translate these statements to predicate
logic. Let P(x), Q(x), and R(x) be the propositional functions “x
is a lion,” “x is fierce,” and “x drinks coffee,” respectively.
1. ∀x (P(x)→ Q(x))
2. ∃x (P(x) ∧ ¬R(x))
3. ∃x (Q(x) ∧ ¬R(x))
● Later we will see how to prove that the conclusion follows
from the premises.
Nested Quantifiers
Section 1.5
Section Summary

● Nested Quantifiers
● Order of Quantifiers
● Translating from Nested Quantifiers into
English
● Translating Mathematical Statements into
Statements involving Nested Quantifiers.
● Translated English Sentences into Logical
Expressions.
● Negating Nested Quantifiers.
Nested Quantifiers
● Nested quantifiers are often necessary to express
the meaning of sentences in English as well as
important concepts in computer science and
mathematics.
Example: “Every real number has an inverse” is
∀x ∃y(x + y = 0)
where the domains of x and y are the real numbers.
● We can also think of nested propositional
functions:
∀x ∃y(x + y = 0) can be viewed as ∀x Q(x) where Q(x) is
∃y P(x, y) where P(x, y) is (x + y = 0)
Thinking of Nested Quantification
● Nested Loops
⚪ To see if ∀x∀yP (x,y) is true, loop through the values of x :
● At each step, loop through the values for y.
● If for some pair of x andy, P(x,y) is false, then ∀x ∀yP(x,y) is false and both
the outer and inner loop terminate.
∀x ∀y P(x,y) is true if the outer loop ends after stepping through each x.
⚪ To see if ∀x ∃yP(x,y) is true, loop through the values of x:
● At each step, loop through the values for y.
● The inner loop ends when a pair x and y is found such that P(x, y) is true.
● If no y is found such that P(x, y) is true the outer loop terminates as ∀x ∃yP(x,y)
has been shown to be false.
∀x ∃y P(x,y) is true if the outer loop ends after stepping through each x.
● If the domains of the variables are infinite, then this process
can not actually be carried out.
Order of Quantifiers

Examples:
1. Let P(x,y) be the statement “x + y = y + x.”
Assume that U is the real numbers. Then
∀x ∀yP(x,y) and∀y ∀xP(x,y) have the
same truth value.
2. Let Q(x,y) be the statement “x + y = 0.”
Assume that U is the real numbers. Then
∀x ∃yP(x,y) is true, but ∃y ∀xP(x,y) is
false.
Questions on Order of Quantifiers
Example 1: Let U be the real numbers,
Define P(x,y) : x ∙ y = 0
What is the truth value of the following:
1. ∀x∀yP(x,y)
Answer: False
2. ∀x∃yP(x,y)
Answer: True
3. ∃x∀y P(x,y)
Answer: True
4. ∃x ∃ y P(x,y)
Answer: True
Questions on Order of Quantifiers
Example 2: Let U be the real numbers,
Define P(x,y) : x / y = 1
What is the truth value of the following:
1. ∀x∀yP(x,y)
Answer: False
2. ∀x∃yP(x,y)
Answer: True
3. ∃x∀y P(x,y)
Answer: False
4. ∃x ∃ y P(x,y)
Answer: True
Quantifications of Two Variables
Statement When True? When False
P(x,y) is true for every There is a pair x, y for
pair x,y. which P(x,y) is false.

For every x there is a y There is an x such that

for which P(x,y) is true. P(x,y) is false for every y.

There is an x for which For every x there is a y

P(x,y) is true for every y. for which P(x,y) is false.

There is a pair x, y for P(x,y) is false for every

which P(x,y) is true. pair x,y
Translating Nested Quantifiers into
English
Example 1: Translate the statement
∀x (C(x )∨ ∃y (C(y ) ∧ F(x, y)))
where C(x) is “x has a computer,” and F(x,y) is “x
and y are friends,” and the domain for both x and y
consists of all students in your school.
Solution: Every student in your school has a
computer or has a friend who has a computer.
Translating Mathematical Statements into
Predicate Logic
Example : Translate “The sum of two positive integers
is always positive” into a logical expression.
Solution:
1. Rewrite the statement to make the implied quantifiers and
domains explicit:
“For every two integers, if these integers are both positive, then the sum
of these integers is positive.”
2. Introduce the variables x and y, and specify the domain, to
obtain:
“For all positive integers x and y, x + y is positive.”
3. The result is:
∀x ∀ y ((x > 0)∧ (y > 0)→ (x + y > 0))
where the domain of both variables consists of all integers
Translating English into Logical
Expressions Example
Example: Use quantifiers to express the
statement “There is a woman who has
taken a flight on every airline in the world.”
Solution:
1. Let P(w,f) be “w has taken f ” and Q(f,a) be “f
is a flight on a .”
2. The domain of w is all women, the domain of f
is all flights, and the domain of a is all airlines.
3. Then the statement can be expressed as:
∃w ∃f ∀a (P(w,f ) ∧ Q(f,a))
Questions on Translation from
English
Choose the obvious predicates and express in predicate logic.
Example 1: “Brothers are siblings.”
Solution: ∀x ∀y (B(x,y) → S(x,y))
Example 2: “Siblinghood is symmetric.”
Solution: ∀x ∀y (S(x,y) → S(y,x))
Example 3: “Everybody loves somebody.”
Solution: ∀x ∃y L(x,y)
Example 4: “There is someone who is loved by everyone.”
Solution: ∃y ∀x L(x,y)
Example 5: “There is someone who loves someone.”
Solution: ∃x ∃y L(x,y)
Example 6: “Everyone loves himself”
Solution: ∀x L(x,x)
Negating Nested Quantifiers
Example 1: Recall the logical expression developed three slides back:
∃w ∀a ∃f (P(w,f ) ∧ Q(f,a))
Part 1: Use quantifiers to express the statement that “There does not exist a woman
who has taken a flight on every airline in the world.”
Solution: ¬∃w ∀a ∃f (P(w,f ) ∧ Q(f,a))
Part 2: Now use De Morgan’s Laws to move the negation as far inwards as possible.
Solution:
1. ¬∃w ∀a ∃f (P(w,f ) ∧ Q(f,a))
2. ∀w ¬ ∀a ∃f (P(w,f ) ∧ Q(f,a)) by De Morgan’s for ∃
3. ∀w ∃ a ¬ ∃f (P(w,f ) ∧ Q(f,a)) by De Morgan’s for ∀
4. ∀w ∃ a ∀f ¬ (P(w,f ) ∧ Q(f,a)) by De Morgan’s for ∃
5. ∀w ∃ a ∀f (¬ P(w,f ) ∨ ¬ Q(f,a)) by De Morgan’s for ∧.
Part 3: Can you translate the result back into English?
Solution:
“For every woman there is an airline such that for all flights, this woman has not
taken that flight or that flight is not on this airline”
Some Questions about Quantifiers
(optional)
● Can you switch the order of quantifiers?
⚪ Is this a valid equivalence?
Solution: Yes! The left and the right side will always have the same truth
value. The order in which x and y are picked does not matter.
⚪ Is this a valid equivalence?
Solution: No! The left and the right side may have different truth values
for some propositional functions for P. Try “x + y = 0” for P(x,y) with U being
the integers. The order in which the values of x and y are picked does
matter.
● Can you distribute quantifiers over logical connectives?
⚪ Is this a valid equivalence?
Solution: Yes! The left and the right side will always have the same truth
value no matter what propositional functions are denoted by P(x) and Q(x).
⚪ Is this a valid equivalence?
Solution: No! The left and the right side may have different truth values.
Pick “x is a fish” for P(x) and “x has scales” for Q(x) with the domain of
discourse being all animals. Then the left side is false, because there are
some fish that do not have scales. But the right side is true since not all
animals are fish.
The Foundations: Logic and
Proofs
Chapter 1, Part III: Proofs
Summary

● Valid Arguments and Rules of Inference

● Proof Methods
● Proof Strategies
Rules of Inference
Section 1.6
Section Summary

● Valid Arguments
● Inference Rules for Propositional Logic
● Using Rules of Inference to Build
Arguments
● Rules of Inference for Quantified
Statements
● Building Arguments for Quantified
Statements
Revisiting the Socrates Example

● We have the two premises:

⚪ “All men are mortal.”
⚪ “Socrates is a man.”
● And the conclusion:
⚪ “Socrates is mortal.”
● How do we get the conclusion from the
premises?
The Argument

● We can express the premises (above the

line) and the conclusion (below the line) in
predicate logic as an argument:

● We will see shortly that this is a valid

argument.
Valid Arguments

● We will show how to construct valid

arguments in two stages; first for
propositional logic and then for predicate
logic. The rules of inference are the
essential building block in the
construction of valid arguments.
1. Propositional Logic
Inference Rules
2. Predicate Logic
Inference rules for propositional logic plus additional
inference rules to handle variables and quantifiers.
Valid Arguments (Propositional
Logic)
● “If you have a current password, then you
can log onto the network.”
● “You have a current password.”
● Therefore, “You can log onto the network.”

● Sequence of propositions (argument) is

valid; the conclusion must be true when
both premise are true.
Argument Form

● p: “You have a current password”

● q: “You can log onto the network.”
● the argument has the form

p→q
p
∴q
the statement ((p → q) ∧ p) → q is a tautology
Argument Form
● p: ““You have access to the network”
● q: “You can change your grade”
● the argument has the form

“If you have access to the network, then you can change
your grade.”
“You have access to the network.”
∴ “You can change your grade.”

● The argument is valid, but if premise is false, we cannot

conclude that the conclusion is true.
Arguments in Propositional Logic
● A argument in propositional logic is a sequence of
propositions. All but the final proposition are called premises.
The last statement is the conclusion.
● The argument is valid if the premises imply the conclusion.
An argument form is an argument that is valid no matter
what propositions are substituted into its propositional
variables.
● If the premises are p1 ,p2, …,pn and the conclusion is q then
(p1 ∧ p2 ∧ … ∧ pn ) → q is a tautology.
● Inference rules are all argument simple argument forms that
will be used to construct more complex argument forms.
Rules of Inference for Propositional
Logic: Modus Ponendo Ponens
● Latin for “the way that affirms by affirming”

● Implication elimination
● Abbreviated to MP or modus ponens
p q p→q
● whenever p → q is true T T T

● and p is true, T F F
F T T
● q must also be true. F F T
Modus Ponens

Corresponding Tautology:
(p ∧ (p →q)) → q

Example:
Let p be “It is snowing.”
Let q be “I will study discrete math.”

“If it is snowing, then I will study discrete math.”

“It is snowing.”

“Therefore , I will study discrete math.”

Modus Ponens
● State which rule of inference is the basis of the
following argument:
● “If it snows today, then we will go skiing”. “It is
snowing today”, “therefore we will go skiing”.
● Let p be the proposition “It is snowing today” and
q the proposition “We will go skiing” Then this
argument is of the form
p q
p
∴q
● This is an argument that uses the Modus Ponens
rule.
Modus Tollendo Tollens

● Latin for "the way that denies by denying"

● Denying the consequent

● Abbreviated to modus tollens

● in every instance in which p q p→q

T T T
● p → q is true and q is false,
T F F
● p must also be false. F T T
F F T
Modus Tollens

Corresponding Tautology:
(¬p∧(p →q))→¬q

Example:
Let p be “it is snowing.”
Let q be “I will study discrete math.”

“If it is snowing, then I will study discrete math.”

“I will not study discrete math.”

“Therefore , it is not snowing.”

Hypothetical Syllogism

Corresponding Tautology:
((p →q) ∧ (q→r))→(p→ r)

Example:
Let p be “it snows.”
Let q be “I will study discrete math.”
Let r be “I will get an A.”

“If it snows, then I will study discrete math.”

“If I study discrete math, I will get an A.”

“Therefore , If it snows, I will get an A.”

Hypothetical Syllogism
● State which rule of inference is used in the
argument:
● If it rains today, then we will not have a barbecue
today. If we do not have a barbecue today, then
we will have a barbecue tomorrow. Therefore, if
it rains today, then we will have a barbecue
tomorrow.
p→q
q→r
∴p→r
● Hence, this argument is a hypothetical syllogism.
Disjunctive Syllogism

Corresponding Tautology:
(¬p∧(p ∨q))→q

Example:
Let p be “I will study discrete math.”
Let q be “I will study English literature.”

“I will study discrete math or I will study English literature.”

“I will not study discrete math.”

“Therefore , I will study English literature.”

Addition

Corresponding Tautology:
p →(p ∨q)

Example:
Let p be “I will study discrete math.”
Let q be “I will visit Las Vegas.”

“I will study discrete math.”

“Therefore, I will study discrete math or I will visit

Las Vegas.”
Addition Rule
● State which rule of inference is the basis of
the following argument:
● “It is below freezing now. Therefore, it is either
below freezing or raining now.”
● Let p be the proposition “It is below freezing
now” and q the proposition “It is raining now.”
Then this argument is of the form
p
∴p∨q
● This is an argument that uses the addition
rule.
Simplification

Corresponding Tautology:
(p∧q) →p

Example:
Let p be “I will study discrete math.”
Let q be “I will study English literature.”

“I will study discrete math and English literature”

“Therefore, I will study discrete math.”

Simplification Rule
● State which rule of inference is the basis of
the following argument:
● “It is below freezing and raining now.
Therefore, it is below freezing now.”
● Let p be the proposition “It is below freezing
now,” and let q be the proposition “It is raining
now.” This argument is of the form
p∧q
∴p
● This argument uses the simplification rule.
Conjunction

Corresponding Tautology:
((p) ∧ (q)) →(p ∧ q)

Example:
Let p be “I will study discrete math.”
Let q be “I will study English literature.”

“I will study discrete math.”

“I will study English literature.”

“Therefore, I will study discrete math and I will study

English literature.”
Resolution
Resolution plays an important role
in AI and is used in Prolog.

Corresponding Tautology:
((¬p ∨ r ) ∧ (p ∨ q)) →(q ∨ r)

Example:
Let p be “I will study discrete math.”
Let r be “I will study English literature.”
Let q be “I will study databases.”

“I will not study discrete math or I will study English literature.”

“I will study discrete math or I will study databases.”

“Therefore, I will study databases or I will English literature.”

Using the Rules of Inference to Build
Valid Arguments
● A valid argument is a sequence of statements. Each
statement is either a premise or follows from previous
statements by rules of inference. The last statement is called
conclusion.
● A valid argument takes the following form:
S1
S2
.
.
.
Sn

C
Fallacies
● Arguments are based on tautologies.
● Fallacies are based on contingencies.
● The proposition ((p → q) ∧q) → p is not a
tautology, because it is false when p is false and q
is true.
● This type of incorrect reasoning is called the
fallacy of affirming the conclusion.
● Example:
● If you do every problem in this book, then you will
learn discrete mathematics. You learned discrete
mathematics. Therefore, you did every problem in
this book.
Fallacy of denying the hypothesis.

● The proposition ((p → q)∧￢p)→￢q is not a tautology,

because it is false when p is false and q is true.
● Is it correct to assume that you did not learn discrete
mathematics if you did not do every problem in the book,
assuming that if you do every problem in this book, then you
will learn discrete mathematics?
● It is possible that you learned discrete mathematics even if
you did not do every problem in this book. This incorrect
argument is of the form p → q and ￢p imply ￢q, which is an
example of the fallacy of denying the hypothesis.

164
165
166
167
168
169
170
171
172
EXAMPLE #2

173
174
175
176
Valid Arguments

Example 3: From the single proposition

Show that q is a conclusion.

Solution:
Valid Arguments (Predicate Logic)

178
Universal Instantiation

● Universal instantiation is the rule of inference

used to conclude that P(c) is true, where c is a
particular member of the domain, given the
premise ∀x P(x).
● •Universal instantiation is used when we
conclude from the statement “All women are
wise” that “Lisa is wise,” where Lisa is a
member of the domain of all women.

179
Universal Generalization

● Universal generalization is the rule of inference that states that ∀xP

(x) is true, given the premise that P(c)is true for all
elements c in the domain.
● •Universal generalization is used when we show that ∀x
P(x) is true by taking an arbitrary element c from the
domain and showing that P(c) is true.
● •Universal generalization is used implicitly in many
proofs in mathematics and is seldom mentioned
explicitly. However, the error of adding unwarranted
assumptions about the arbitrary element c when
universal generalization is used is all too common in
incorrect reasoning.
180
Existential Instantiation

● Existential instantiation is the rule that allows us

to conclude that there is an element c in the
domain for which P(c) is true if we know that ∃x
P(x) is true.
● We cannot select an arbitrary value of c here,
but rather it must be a c for which P(c) is true.
● Usually we have no knowledge of what c is, only
that it exists. Because it exists, we may give it a
name (c) and continue our argument.

181
Existential Generalization

● Existential generalization is the rule of

inference that is used to conclude that ∃x
P(x) is true when a particular element c
with P(c) true is known.
● That is, if we know one element c in the
domain for which P(c) is true, then we
know that ∃x P(x) is true.
182
Basic Structures: Sets and
Functions
Chapter 2
 Sets
Section 2.1
Section Summary
● Definition of sets
● Describing Sets
⚪ Roster Method
⚪ Set-Builder Notation
● Some Important Sets in Mathematics
● Empty Set and Universal Set
● Subsets and Set Equality
● Cardinality of Sets
● Tuples
● Cartesian Product
Introduction
● Sets are one of the basic building blocks for the types of
objects considered in discrete mathematics.
⚪ Important for counting.
⚪ Programming languages have set operations.
● Set theory is an important branch of mathematics.
⚪ Many different systems of axioms have been used to develop set
theory.
⚪ Here we are not concerned with a formal set of axioms for set
theory. Instead, we will use what is called naïve set theory.
Sets

● A set is an unordered collection of objects.

⚪ the students in this class
⚪ the chairs in this room
● The objects in a set are called the
elements, or members of the set. A set is
said to contain its elements.
● The notation a ∈ A denotes that a is an
element of the set A.
● If a is not a member of A, write a ∉ A
Describing a Set: Roster Method
● S = {a,b,c,d}
● Order not important
S = {a,b,c,d} = {b,c,a,d}
● Each distinct object is either a member or not; listing
more than once does not change the set.
S = {a,b,c,d} = {a,b,c,b,c,d}
● Elipses (…) may be used to describe a set without listing all of
the members when the pattern is clear.
S = {a,b,c,d, ……,z }
Roster Method

● Set of all vowels in the English alphabet:

V = {a,e,i,o,u}
● Set of all odd positive integers less than 10:
O = {1,3,5,7,9}
● Set of all positive integers less than 100:
S = {1,2,3,……..,99}
● Set of all integers less than 0:
S = {…., -3,-2,-1}
Some Important Sets

N = natural numbers = {0,1,2,3….}

Z = integers = {…,-3,-2,-1,0,1,2,3,…}
Z⁺ = positive integers = {1,2,3,…..}
R = set of real numbers
R+ = set of positive real numbers
C = set of complex numbers.
Q = set of rational numbers
Set-Builder Notation
● Specify the property or properties that all members
must satisfy:
S = {x | x is a positive integer less than 100}
O = {x | x is an odd positive integer less than 10}
O = {x ∈ Z⁺ | x is odd and x < 10}
● A predicate may be used:
S = {x | P(x)}
● Example: S = {x | Prime(x)}
● Positive rational numbers:
Q+ = {x ∈ R | x = p/q, for some positive integers
p,q}
Universal Set and Empty Set

● The universal set U is the set containing

everything currently under consideration.
⚪ Sometimes implicit Venn Diagram
⚪ Sometimes explicitly stated.
⚪ Contents depend on the context. U
aei
● The empty set is the set with no V ou
elements. Symbolized ∅, but
{} also used.
John Venn (1834-1923)
Cambridge, UK
Some things to remember

● Sets can be elements of sets.

{{1,2,3},a, {b,c}}
{N,Z,Q,R}
● The empty set is different from a set
containing the empty set.
∅ ≠{∅}
Set Equality

Definition: Two sets are equal if and only

if they have the same elements.
⚪ Therefore if A and B are sets, then A and B are
equal if and only if .
⚪ We write A = B if A and B are equal sets.
{1,3,5} = {3, 5, 1}
{1,5,5,5,3,3,1} = {1,3,5}
Subsets

Definition: The set A is a subset of B, if

and only if every element of A is also an
element of B.
⚪ The notation A ⊆ B is used to indicate that A is a
subset of the set B.
⚪ A ⊆ B holds if and only if
is true.
1. Because a ∈ ∅ is always false, ∅ ⊆ S ,for every set
S.
2. Because a ∈ S → a ∈ S, S ⊆ S, for every set S.
Showing a Set is or is not a Subset of
Another Set
● Showing that A is a Subset of B: To show that A
⊆ B, show that if x belongs to A, then x also belongs to
B.
● Showing that A is not a Subset of B: To show
that A is not a subset of B, A ⊈ B, find an element
x ∈ A with x ∉ B. (Such an x is a counterexample to
the claim that x ∈ A implies x ∈ B.)
Examples:
1. The set of all computer science majors at your school is a
subset of all students at your school.
2. The set of integers with squares less than 100 is not a subset
of the set of nonnegative integers.
Another look at Equality of Sets

● Recall that two sets A and B are equal,

denoted by A = B, iff

● Using logical equivalences we have that A

= B iff

● This is equivalent to
A⊆B and B⊆A
Proper Subsets

Definition: If A ⊆ B, but A ≠B, then we

say A is a proper subset of B, denoted by
A ⊂ B. If A ⊂ B, then

is true. U
B
A

Venn Diagram
Set Cardinality
Definition: If there are exactly n distinct elements in S
where n is a nonnegative integer, we say that S is
finite. Otherwise it is infinite.
Definition: The cardinality of a finite set A, denoted by
|A|, is the number of (distinct) elements of A.
Examples:
1. |ø| = 0
2. Let S be the letters of the English alphabet. Then |S|
= 26
3. |{1,2,3}| = 3
4. |{ø}| = 1
5. The set of integers is infinite.
Power Sets

Definition: The set of all subsets of a set

A, denoted P(A), is called the power set of
A.
Example: If A = {a,b} then
P(A) = {ø, {a},{b},{a,b}}

● If a set has n elements, then the

cardinality of the power set is 2ⁿ. (In
Chapters 5 and 6, we will discuss different
ways to show this.)
Tuples

● The ordered n-tuple (a1,a2,…..,an) is the

ordered collection that has a1 as its first
element and a2 as its second element
and so on until an as its last element.
● Two n-tuples are equal if and only if their
corresponding elements are equal.
● 2-tuples are called ordered pairs.
● The ordered pairs (a,b) and (c,d) are equal
if and only if a = c and b = d.
 René Descartes
Cartesian Product (1596-1650)

Definition: The Cartesian Product of two sets A and

B, denoted by A × B is the set of ordered pairs (a,b)
where a ∈ A and b ∈ B .

Example:
A = {a,b} B = {1,2,3}
A × B = {(a,1),(a,2),(a,3), (b,1),(b,2),(b,3)}

● Definition: A subset R of the Cartesian product A × B

is called a relation from the set A to the set B.
(Relations will be covered in depth in Chapter 9. )
Cartesian Product
Definition: The cartesian products of the sets
A1,A2,……,An, denoted by A1 × A2 × …… × An , is the
set of ordered n-tuples (a1,a2,……,an) where
ai belongs to Ai for i = 1, … n.

Example: What is A × B × C where A = {0,1}, B =

{1,2} and C = {0,1,2}
Solution: A × B × C = {(0,1,0), (0,1,1),
(0,1,2),(0,2,0), (0,2,1), (0,2,2),(1,1,0), (1,1,1),
(1,1,2), (1,2,0), (1,2,1), (1,1,2)}
Truth Sets of Quantifiers

● Given a predicate P and a domain D, we

define the truth set of P to be the set of
elements in D for which P(x) is true. The
truth set of P(x) is denoted by

● Example: The truth set of P(x) where the

domain is the integers and P(x) is “|x| = 1”
is the set {-1,1}
Set Operations
Section 2.2
Section Summary

● Set Operations
⚪ Union
⚪ Intersection
⚪ Complementation
⚪ Difference
● More on Set Cardinality
● Set Identities
● Proving Identities
● Membership Tables
Boolean Algebra

● Propositional calculus and set theory are

both instances of an algebraic system
called a Boolean Algebra. This is
discussed in Chapter 12.
● The operators in set theory are analogous
to the corresponding operator in
propositional calculus.
● As always there must be a universal set
U. All sets are assumed to be subsets of
U.
Union
● Definition: Let A and B be sets. The union of
the sets A and B, denoted by A ∪ B, is the
set:

● Example: What is {1,2,3} ∪ {3, 4, 5}?

Venn Diagram for A ∪ B
Solution: {1,2,3,4,5}
U
A B
Intersection
● Definition: The intersection of sets A and B,
denoted by A ∩ B, is

● Note if the intersection is empty, then A and

B are said to be disjoint.
● Example: What is? {1,2,3} ∩ {3,4,5} ?
Solution: {3} Venn Diagram for A ∩B
● Example:What is?
U
{1,2,3} ∩ {4,5,6} ? A B
Solution: ∅
Complement

Definition: If A is a set, then the complement of the A

(with respect to U), denoted by Ā is the set U - A
Ā = {x ∈ U | x ∉ A}
(The complement of A is sometimes denoted by Ac .)
Example: If U is the positive integers less than 100, what
is the complement of {x | x > 70}
Solution: {x | x ≤ 70} Venn Diagram for Complement
U

A
Ā
Difference
● Definition: Let A and B be sets. The difference
of A and B, denoted by A – B, is the set
containing the elements of A that are not in B.
The difference of A and B is also called the
complement of B with respect to A.
A – B = {x | x ∈ A ∧ x ∉ B} = A ∩ B
Venn Diagram for A − B
U
A
B
The Cardinality of the Union of Two
Sets
• Inclusion-Exclusion
U
|A ∪ B| = |A| + | B| - |A ∩ B| A B

Venn Diagram for A, B, A ∩ B, A ∪ B

• Example: Let A be the math majors in your class and B be the CS majors.
To count the number of students who are either math majors or CS majors,
add the number of math majors and the number of CS majors, and subtract
the number of joint CS/math majors.
• We will return to this principle in Chapter 6 and Chapter 8 where we will
derive a formula for the cardinality of the union of n sets, where n is a
positive integer.
Review Questions
Example: U = {0,1,2,3,4,5,6,7,8,9,10} A = {1,2,3,4,5}, B ={4,5,6,7,8}
1. A∪B
Solution: {1,2,3,4,5,6,7,8}
2. A∩B
Solution: {4,5}
3. Ā
Solution: {0,6,7,8,9,10}
4.
Solution: {0,1,2,3,9,10}
5. A – B
Solution: {1,2,3}
6. B – A
Solution: {6,7,8}
Symmetric Difference (optional)

Definition: The symmetric difference of A

and B, denoted by is the set

Example:
U = {0,1,2,3,4,5,6,7,8,9,10}
U
A = {1,2,3,4,5} B ={4,5,6,7,8}
A B
What is:
⚪ Solution: {1,2,3,6,7,8}
Venn Diagram
Set Identities

● Identity laws

● Domination laws

● Idempotent laws

● Complementation law

Continued on next slide

Set Identities

● Commutative laws

● Associative laws

● Distributive laws

Continued on next slide

Set Identities

● De Morgan’s laws

● Absorption laws

● Complement laws
Proving Set Identities

● Different ways to prove set identities:

1. Prove that each set (side of the identity) is a
subset of the other.
2. Use set builder notation and propositional
logic.
3. Membership Tables: Verify that elements in the
same combination of sets always either belong
or do not belong to the same side of the
identity. Use 1 to indicate it is in the set and a
0 to indicate that it is not.
Proof of Second De Morgan Law

Example: Prove that

Solution: We prove this identity by
showing that:

1) and

2)

Continued on next slide

Proof of Second De Morgan Law

These steps show that:

Continued on next slide

Proof of Second De Morgan Law

These steps show that:

Set-Builder Notation: Second De Morgan
Law
Membership Table
Example: Construct a membership table to show that the distributive law
holds.

Solution:

A B C
1 1 1 1 1 1 1 1
1 1 0 0 1 1 1 1
1 0 1 0 1 1 1 1
1 0 0 0 1 1 1 1
0 1 1 1 1 1 1 1
0 1 0 0 0 1 0 0
0 0 1 0 0 0 1 0
0 0 0 0 0 0 0 0
Functions
Section 2.3
Section Summary
⚫ Definition of a Function.
⚫ Domain, Codomain
⚫ Image, Pre image
⚫ Injection, Surjection, Bijection
⚫ Inverse Function
⚫ Function Composition
⚫ Graphing Functions
⚫ Floor, Ceiling, Factorial
Functions
Definition: Let A and B be nonempty sets. A function f
from A to B, denoted f: A → B is an assignment of each
element of A to exactly one element of B. We write f(a) =
b if b is the unique element of B assigned by the function
f to the element a of A. Students Grades
⚫ Functions are sometimes A
Carlota Rodriguez
called mappings or B
transformations. Sandeep Patel C

Jalen Williams D
F
Kathy Scott
Functions
⚫ A function f: A → B can also be defined as a subset of
A×B (a relation). This subset is restricted to be a relation
where no two elements of the relation have the same first
element.
⚫ Specifically, a function f from A to B contains one, and
only one ordered pair (a, b) for every element a∈ A.

and
Functions
Given a function f: A → B:
⚫ We say f maps A to B or
f is a mapping from A to B.
⚫ A is called the domain of f.
⚫ B is called the codomain of f.
⚫ If f(a) = b,
⚫ then b is called the image of a under f.
⚫ a is called the preimage of b.
⚫ The range of f is the set of all images of points in A under f. We
denote it by f(A).
⚫ Two functions are equal when they have the same domain, the same
codomain and map each element of the domain to the same element of
the codomain.
Equal Functions
⚫ Two functions are equal when they
⚫ have the same domain,
⚫ have the same codomain,
⚫ map each element of their common domain to the same
element in their common codomain.
⚫ If we change either the domain or the codomain of a
function, then we obtain a different function.
⚫ If we change the mapping of elements, then we also obtain
a different function.
Representing Functions
⚫ Functions may be specified in different ways:
⚫ An explicit statement of the assignment.
Students and grades example.
⚫ A formula.
f(x) = x + 1
⚫ A computer program.
⚫ A Java program that when given an integer n, produces the nth
Fibonacci Number (covered in the next section and also inChapter
5).
Activity Time
What are the domain,
codomain, and range of the
following function
Solution
⚫ Let G be the function that assigns a grade to a student in
our discrete mathematics class.
⚫ Note that G(Adams) = A, for instance.
⚫ The domain of G is the set {Adams, Chou, Goodfriend,
Rodriguez, Stevens},
⚫ The codomain is the set {A,B,C,D,F}.
⚫ The range of G is the set {A,B,C, F},
 Questions
f(a) = ? z A B
a
The image of d is ? z x
b
The domain of f is ? A y
c
The codomain of f is ? B
d z
The preimage of y is ? b
f(A) = ?
The preimage(s) of z is (are) ? {a,c,d}
Question on Functions and Sets
⚫ If and S is a subset of A, then

A B
a
f {a,b,c,} is ? {y,z}
x

b
f {c,d} is ? {z} y
c

d z
Injections
Definition: A function f is said to be one-to-one , or
injective, if and only if f(a) = f(b) implies that a = b for all
a and b in the domain of f. A function is said to be an
injection if it is one-to-one.
A B
a x

v
b
y
c
z
d

w
Surjections
Definition: A function f from A to B is called onto or
surjective, if and only if for every element there is
an element with . A function f is
called a surjection if it is onto.

A B
a x

b
y
c
z
d
Bijections
Definition: A function f is a one-to-one correspondence,
or a bijection, if it is both one-to-one and onto (surjective
and injective).

A B
a x

b
y
c

d z

w
real-valued
⚫ A function is called real-valued if its codomain is the set
of real numbers.

⚫ Let f1 and f2 be functions from A to R.

⚫ Then f1 + f2 and f1f2 are also functions from A to R
defined for all x ∈ A by
⚫ (f1 + f2)(x) = f1(x) + f2(x),
⚫ (f1f2)(x) = f1(x)f2(x).
Showing that f is one-to-one or onto
Showing that f is one-to-one or onto
Example 1: Let f be the function from {a,b,c,d} to {1,2,3}
defined by f(a) = 3, f(b) = 2, f(c) = 1, and f(d) = 3. Is f an
onto function?
Solution: Yes, f is onto since all three elements of the
codomain are images of elements in the domain. If the
codomain were changed to {1,2,3,4}, f would not be onto.
Example 2:
Determine whether the function f (x) = x2 from the set
of integers to the set of integers is one-to-one.
Increasing/ decreasing functions
⚫ A function f whose domain and codomain are subsets of
the set of real numbers is called increasing if f (x) ≤ f (y),
and strictly increasing if f(x) < f(y), whenever x < y and x
and y are in the domain of f.
⚫ Similarly, f is called decreasing if f (x) ≥ f (y), and strictly
decreasing if f(x) > f(y), whenever x < y and x and y are in
the domain of f.
Increasing/ decreasing functions
⚫ A function f is
⚫ increasing if ∀x∀y(x < y → f (x) ≤ f (y)),
⚫ strictly increasing if ∀x∀y(x < y → f (x) < f (y)),
⚫ decreasing if ∀x∀y(x < y → f (x) ≥ f (y)),
⚫ strictly decreasing if ∀x∀y(x < y → f (x) > f (y)),

where the universe of discourse is the domain of f.

Relationship with one-to-one
⚫ a function that is either strictly increasing or strictly
decreasing must be one-to-one.

⚫ a function that is increasing, but not strictly increasing, or

decreasing, but not strictly decreasing, is not one-to-one.
The identity function
⚫ Let A be a set. The identity function on A is the function ιA
: A → A, where
ιA(x) = x
⚫ for all x ∈ A.

⚫ The function ιA is one-to-one and onto, so it is a bijection.

Inverse Functions
Definition: Let f be a bijection from A to B. Then the
inverse of f, denoted , is the function from B to A
defined as
No inverse exists unless f is a bijection. Why?
Inverse Functions
A f
B A B
a V V
a

b b
W W
c c

d X X
d

Y Y
Questions
Example 1: Let f be the function from {a,b,c} to {1,2,3}
such that f(a) = 2, f(b) = 3, and f(c) = 1. Is f invertible and
if so what is its inverse?

Solution: The function f is invertible because it is a

one-to-one correspondence. The inverse function f-1
reverses the correspondence given by f, so f-1 (1) = c,
f-1 (2) = a, and f-1 (3) = b.
Questions
Example 2: Let f: Z Z be such that f(x) = x + 1. Is f
invertible, and if so, what is its inverse?

Solution: The function f is invertible because it is a

one-to-one correspondence. The inverse function f-1
reverses the correspondence so f-1 (y) = y – 1.
Questions
Example 3: Let f: R → R be such that . Is f
invertible, and if so, what is its inverse?

Solution: The function f is not invertible because it is

not one-to-one .
Composition
⚫ Definition: Let f: B → C, g: A → B. The composition of f
with g, denoted is the function from A to C defined
by
Composition
g f
A B C A C
V a
a h h
b i b
W i
c
c
X j
d
d j
Y
Composition
Example 1: If and ,
then

and
Composition Questions
Example 2: Let g be the function from the set {a,b,c} to itself
such that g(a) = b, g(b) = c, and g(c) = a. Let f be the function
from the set {a,b,c} to the set {1,2,3} such that f(a) = 3, f(b)
= 2, and f(c) = 1.
What is the composition of f and g, and what is the
composition of g and f.
Solution: The composition f∘g is defined by
f∘g (a)= f(g(a)) = f(b) = 2.
f∘g (b)= f(g(b)) = f(c) = 1.
f∘g (c)= f(g(c)) = f(a) = 3.
Note that g∘f is not defined, because the range of f is not a subset
of the domain of g.
Composition Questions
Example 2: Let f and g be functions from the set of
integers to the set of integers defined by f(x) = 2x + 3 and
g(x) = 3x + 2.
What is the composition of f and g, and also the
composition of g and f ?
Solution:
f∘g (x)= f(g(x)) = f(3x + 2) = 2(3x + 2) + 3 = 6x + 7
g∘f (x)= g(f(x)) = g(2x + 3) = 3(2x + 3) + 2 = 6x + 11
Graphs of Functions
⚫ Let f be a function from the set A to the set B. The graph
of the function f is the set of ordered pairs {(a,b) | a ∈A
and f(a) = b}.

Graph of f(n) = 2n + 1 Graph of f(x) = x2

from Z to Z from Z to Z
Some Important Functions
⚫ The floor function, denoted

is the largest integer less than or equal to x.

⚫ The ceiling function, denoted

is the smallest integer greater than or equal to x

Example:
Floor and Ceiling Functions

Graph of (a) Floor and (b) Ceiling Functions

Floor and Ceiling Functions
Proving Properties of Functions
Example: Prove that x is a real number, then
⌊2x⌋= ⌊x⌋ + ⌊x + 1/2⌋
Solution: Let x = n + ε, where n is an integer and 0 ≤ ε< 1.
Case 1: ε < ½
⚫ 2x = 2n + 2ε and ⌊2x⌋ = 2n, since 0 ≤ 2ε< 1.
⚫ ⌊x + 1/2⌋ = n, since x + ½ = n + (1/2 + ε ) and 0 ≤ ½ +ε < 1.
⚫ Hence, ⌊2x⌋ = 2n and ⌊x⌋ + ⌊x + 1/2⌋ = n + n = 2n.
Case 2: ε≥½
⚫ 2x = 2n + 2ε = (2n + 1) +(2ε − 1) and ⌊2x⌋ =2n + 1,
since 0 ≤ 2 ε - 1< 1.
⚫ ⌊x + 1/2⌋ = ⌊ n + (1/2 + ε)⌋ = ⌊ n + 1 + (ε – 1/2)⌋ = n + 1 since 0≤
ε – 1/2< 1.
⚫ Hence, ⌊2x⌋ = 2n + 1 and ⌊x⌋ + ⌊x + 1/2⌋ = n + (n + 1) = 2n + 1.
Factorial Function
Definition: f: N → Z+ , denoted by f(n) = n! is the
product of the first n positive integers when n is a
nonnegative integer.

f(n) = 1 ∙ 2 ∙∙∙ (n – 1) ∙ n, f(0) = 0! = 1

Stirling’s Formula:
Examples:
f(1) = 1! = 1

f(2) = 2! = 1 ∙ 2 = 2

f(6) = 6! = 1 ∙ 2 ∙ 3∙ 4∙ 5 ∙ 6 = 720

f(20) = 2,432,902,008,176,640,000.