Discrete Structures Course Syllabus
Discrete Structures Course Syllabus
February 9, 2022
Syllabus Information
Required Materials
I i-Clicker 2. ($$$) Each class we will take attendance at the beginning, the end,
and perhaps have a brief graded question during the lecture.
I Non-Graphing Calculator. ($$) Such as the TI30XIIS. No Smartphones.
I Supplementary Materials: Notebook, writing utensiles, or anything you need to
facilitate learning.
Course Format
I Office Hours: I will be at the SMART Lab (LIB-232) from 11am-3pm on Tuesdays
to help students with my MGF1106 course, but these also serve as drop-in office
hours.
I Please look for/ask for me as I may be helping other students or working in
a cubicle.
Grade Distribution
Rest assured, all exam content will make use of the concepts we intend to cover even
if you have not encountered the particular problems.
I The “A” students will be able to identify which concepts are needed to solve any
problems encountered and apply those concepts to do so.
I Other students may be able to get by on some easier problems, but not be able
to tackle on more difficult ones.
Approach each homework and practice problem with the goal of producing solutions,
not simply finding answers.
Work toward each solution with pen and paper, knowing at each step how you arrived
there and which concept(s) you used, before being content with your solution.
John Theado, PhD Intro to Discrete Structures February 9, 2022 8 / 157
Syllabus Information
Grading Scale
Grading Scale
97.00 ≤ A+ < 100.00 74.00 ≤ C < 77.00
94.00 ≤ A < 97.00 70.00 ≤ C- < 74.00
90.00 ≤ A- < 94.00 67.00 ≤ D+ < 70.00
87.00 ≤ B+ < 90.00 64.00 ≤ D < 67.00
84.00 ≤ B < 87.00 60.00 ≤ D- < 64.00
80.00 ≤ B- < 83.00 0.00 ≤ F < 60.00
77.00 ≤ C+ < 80.00
Warning: Final grades will not be rounded, e.g. a 69.99 is considered a D+.
Your final grade will be computed based on a reasonable amount of missed work:
To recover intangible benefits of missed work, such as observing class and the
opportunity to practice, read the textbook, my notes, and look for problems in the text.
As such, requests for extensions on these will not be considered. Email requests for
extensions will go unanswered.
If you are falling behind due to extreme circumstances where the automatic
remedies are insufficient, plan to meet with me to discuss the need and a plan.
One of my roles in this course is to set it up, which is mostly complete, and maintain
and make necessary adjustments during the semester.
Although I wish for your success in this and all of your other courses and endeavors, I
am not here to directly affect your grade. Your grade is your responsibility.
My other major role is to help you learn the material, by giving lectures, hosting Friday
sessions, and being available Tuesday to visi with, in order to indirectly help you
achieve a good grade.
If your goal is to maximize your grade while minimizing your learning and effort, then
the grade distribution/scale and requirements are clear. Don’t expect my assistance.
If your goal is to learn as much as possible in order to earn your best grade, then feel
free to seek my help in this regard.
Regardless, do so within the bounds of academic integrity, by behaving, acting, and
communicating with honest intent.
Other expectations:
Introduction
Introduction
Introduction
Introduction
Introduction
If the bell rings or the flag drops, then the race is over.
∴ If the race is not over, then the bell hasn’t rung and
the flag hasn’t dropped.
Introduction
If the bell rings or the flag drops, then the race is over.
∴ If the race is not over, then the bell hasn’t rung and
the flag hasn’t dropped.
If x = −2 or x = 2 then x 2 = 4
∴ If x 2 6= 4 then x 6= −2 and x 6= 2.
If p or q then r .
∴ If not r then not p and not q.
If p or q then r .
∴ If not r then not p and not q.
It is a valid form since any substitution for the component statements p, q, and
r which make all the premise(s) true guarantees the truth of the conclusion.
If p or q then r .
∴ If not r then not p and not q.
It is a valid form since any substitution for the component statements p, q, and
r which make all the premise(s) true guarantees the truth of the conclusion.
Not every argument is valid, such as when you can have true premises but a
false conclusion.
If p or q then r .
∴ If not r then not p and not q.
It is a valid form since any substitution for the component statements p, q, and
r which make all the premise(s) true guarantees the truth of the conclusion.
Not every argument is valid, such as when you can have true premises but a
false conclusion.
Additionally, not every valid argument is used soundly, i.e. when not all
premises are true.
If p or q then r .
∴ If not r then not p and not q.
It is a valid form since any substitution for the component statements p, q, and
r which make all the premise(s) true guarantees the truth of the conclusion.
Not every argument is valid, such as when you can have true premises but a
false conclusion.
Additionally, not every valid argument is used soundly, i.e. when not all
premises are true.
We will discuss arguments more in depth later on, but for now, let us focus on
the statements used to build arguments.
Statements
Statements
Statements
Statements
Statements
Statements
Statements
a) Today is Tuesday.
a) Today is Tuesday. 3
a) Today is Tuesday. 3
b) Mathematics is the best subject.
a) Today is Tuesday. 3
b) Mathematics is the best subject. 7
a) Today is Tuesday. 3
b) Mathematics is the best subject. 7
c) Philadelphia is the capital of the United States.
a) Today is Tuesday. 3
b) Mathematics is the best subject. 7
c) Philadelphia is the capital of the United States. 3
a) Today is Tuesday. 3
b) Mathematics is the best subject. 7
c) Philadelphia is the capital of the United States. 3
d) x 2 + 2 = 11.
a) Today is Tuesday. 3
b) Mathematics is the best subject. 7
c) Philadelphia is the capital of the United States. 3
d) x 2 + 2 = 11. 7 (It can become a statement for specified value(s) of x.)
a) Today is Tuesday. 3
b) Mathematics is the best subject. 7
c) Philadelphia is the capital of the United States. 3
d) x 2 + 2 = 11. 7 (It can become a statement for specified value(s) of x.)
e) He has a cat.
a) Today is Tuesday. 3
b) Mathematics is the best subject. 7
c) Philadelphia is the capital of the United States. 3
d) x 2 + 2 = 11. 7 (It can become a statement for specified value(s) of x.)
e) He has a cat. 7 (It can become a statement after we specific who “he” is.)
a) Today is Tuesday. 3
b) Mathematics is the best subject. 7
c) Philadelphia is the capital of the United States. 3
d) x 2 + 2 = 11. 7 (It can become a statement for specified value(s) of x.)
e) He has a cat. 7 (It can become a statement after we specific who “he” is.)
f) This sentence is false.
a) Today is Tuesday. 3
b) Mathematics is the best subject. 7
c) Philadelphia is the capital of the United States. 3
d) x 2 + 2 = 11. 7 (It can become a statement for specified value(s) of x.)
e) He has a cat. 7 (It can become a statement after we specific who “he” is.)
f) This sentence is false. 7 (If it’s true, it’s false; if it’s false, it’s true.)
a) Today is Tuesday. 3
b) Mathematics is the best subject. 7
c) Philadelphia is the capital of the United States. 3
d) x 2 + 2 = 11. 7 (It can become a statement for specified value(s) of x.)
e) He has a cat. 7 (It can become a statement after we specific who “he” is.)
f) This sentence is false. 7 (If it’s true, it’s false; if it’s false, it’s true.)
g) This sentence is true.
a) Today is Tuesday. 3
b) Mathematics is the best subject. 7
c) Philadelphia is the capital of the United States. 3
d) x 2 + 2 = 11. 7 (It can become a statement for specified value(s) of x.)
e) He has a cat. 7 (It can become a statement after we specific who “he” is.)
f) This sentence is false. 7 (If it’s true, it’s false; if it’s false, it’s true.)
g) This sentence is true. 7 (It’s reasonable to consider it to be both true and
false.)
a) Today is Tuesday. 3
b) Mathematics is the best subject. 7
c) Philadelphia is the capital of the United States. 3
d) x 2 + 2 = 11. 7 (It can become a statement for specified value(s) of x.)
e) He has a cat. 7 (It can become a statement after we specific who “he” is.)
f) This sentence is false. 7 (If it’s true, it’s false; if it’s false, it’s true.)
g) This sentence is true. 7 (It’s reasonable to consider it to be both true and
false.)
h) There are 100 Senators.
a) Today is Tuesday. 3
b) Mathematics is the best subject. 7
c) Philadelphia is the capital of the United States. 3
d) x 2 + 2 = 11. 7 (It can become a statement for specified value(s) of x.)
e) He has a cat. 7 (It can become a statement after we specific who “he” is.)
f) This sentence is false. 7 (If it’s true, it’s false; if it’s false, it’s true.)
g) This sentence is true. 7 (It’s reasonable to consider it to be both true and
false.)
h) There are 100 Senators. 3 (We should probably be more specific here
though.)
Compound Statements
Compound Statements
p :It is raining.
q :I will bring an umbrella.
Compound Statements
p :It is raining.
q :I will bring an umbrella.
Compound Statements
p :It is raining.
q :I will bring an umbrella.
I The negation of p is “not p” or “It is not the case that p” which we denote
as ∼p (or occasionally ¬p). It always has the opposite truth value of p: If
p is true then ∼p is false; if p is false then ∼p is true.
I The negation of p is “not p” or “It is not the case that p” which we denote
as ∼p (or occasionally ¬p). It always has the opposite truth value of p: If
p is true then ∼p is false; if p is false then ∼p is true.
I The conjunction of p and q is “p and q”. It is true only when both p and
q are true. If either p or q is false, or both are false, then p ∧ q is false.
I The negation of p is “not p” or “It is not the case that p” which we denote
as ∼p (or occasionally ¬p). It always has the opposite truth value of p: If
p is true then ∼p is false; if p is false then ∼p is true.
I The conjunction of p and q is “p and q”. It is true only when both p and
q are true. If either p or q is false, or both are false, then p ∧ q is false.
I The disjunction of p and q is “p or q”. It is true when when either p is
true or q is true. If both p and q are false, then p ∨ q is false.
I The negation of p is “not p” or “It is not the case that p” which we denote
as ∼p (or occasionally ¬p). It always has the opposite truth value of p: If
p is true then ∼p is false; if p is false then ∼p is true.
I The conjunction of p and q is “p and q”. It is true only when both p and
q are true. If either p or q is false, or both are false, then p ∧ q is false.
I The disjunction of p and q is “p or q”. It is true when when either p is
true or q is true. If both p and q are false, then p ∨ q is false.
I The negation of p is “not p” or “It is not the case that p” which we denote
as ∼p (or occasionally ¬p). It always has the opposite truth value of p: If
p is true then ∼p is false; if p is false then ∼p is true.
I The conjunction of p and q is “p and q”. It is true only when both p and
q are true. If either p or q is false, or both are false, then p ∧ q is false.
I The disjunction of p and q is “p or q”. It is true when when either p is
true or q is true. If both p and q are false, then p ∨ q is false.
I The negation of p is “not p” or “It is not the case that p” which we denote
as ∼p (or occasionally ¬p). It always has the opposite truth value of p: If
p is true then ∼p is false; if p is false then ∼p is true.
I The conjunction of p and q is “p and q”. It is true only when both p and
q are true. If either p or q is false, or both are false, then p ∧ q is false.
I The disjunction of p and q is “p or q”. It is true when when either p is
true or q is true. If both p and q are false, then p ∨ q is false.
p :It is raining.
q :I will bring an umbrella.
p :It is raining.
q :I will bring an umbrella.
p :It is raining.
q :I will bring an umbrella.
p :It is raining.
q :I will bring an umbrella.
p :It is raining.
q :I will bring an umbrella.
p :It is raining.
q :I will bring an umbrella.
p :It is raining.
q :I will bring an umbrella.
p :It is raining.
q :I will bring an umbrella.
p :It is raining.
q :I will bring an umbrella.
p :It is raining.
q :I will bring an umbrella.
p :It is raining.
q :I will bring an umbrella.
x ≤a means x <a or x =a
a≤x ≤b means a≤x and x ≤ b.
x ≤a means x <a or x =a
a≤x ≤b means a≤x and x ≤ b.
Example: For an x ∈ R, let p, q, and r symbolize the statements −1 < x,
x < 5, and x = 5 respectively. Symbolize the following statements in terms of
p, q, and r :
x ≤a means x <a or x =a
a≤x ≤b means a≤x and x ≤ b.
Example: For an x ∈ R, let p, q, and r symbolize the statements −1 < x,
x < 5, and x = 5 respectively. Symbolize the following statements in terms of
p, q, and r :
1. x ≤ 5
x ≤a means x <a or x =a
a≤x ≤b means a≤x and x ≤ b.
Example: For an x ∈ R, let p, q, and r symbolize the statements −1 < x,
x < 5, and x = 5 respectively. Symbolize the following statements in terms of
p, q, and r :
x ≤a means x <a or x =a
a≤x ≤b means a≤x and x ≤ b.
Example: For an x ∈ R, let p, q, and r symbolize the statements −1 < x,
x < 5, and x = 5 respectively. Symbolize the following statements in terms of
p, q, and r :
x ≤a means x <a or x =a
a≤x ≤b means a≤x and x ≤ b.
Example: For an x ∈ R, let p, q, and r symbolize the statements −1 < x,
x < 5, and x = 5 respectively. Symbolize the following statements in terms of
p, q, and r :
x ≤a means x <a or x =a
a≤x ≤b means a≤x and x ≤ b.
Example: For an x ∈ R, let p, q, and r symbolize the statements −1 < x,
x < 5, and x = 5 respectively. Symbolize the following statements in terms of
p, q, and r :
x ≤a means x <a or x =a
a≤x ≤b means a≤x and x ≤ b.
Example: For an x ∈ R, let p, q, and r symbolize the statements −1 < x,
x < 5, and x = 5 respectively. Symbolize the following statements in terms of
p, q, and r :
x ≤a means x <a or x =a
a≤x ≤b means a≤x and x ≤ b.
Example: For an x ∈ R, let p, q, and r symbolize the statements −1 < x,
x < 5, and x = 5 respectively. Symbolize the following statements in terms of
p, q, and r :
x ≤a means x <a or x =a
a≤x ≤b means a≤x and x ≤ b.
Example: For an x ∈ R, let p, q, and r symbolize the statements −1 < x,
x < 5, and x = 5 respectively. Symbolize the following statements in terms of
p, q, and r :
p ∼p
T F
F T
p ∼p
T F
F T
Note that since ∼p has n = 1 components involved, the truth table will have
2n = 21 = 2 rows for each possible combination of truth values.
Example: Given statement variables p and q, let us construct a truth table for
their conjunction (p ∧ q) and disjunction (p ∨ q).
Example: Given statement variables p and q, let us construct a truth table for
their conjunction (p ∧ q) and disjunction (p ∨ q).
p q
Example: Given statement variables p and q, let us construct a truth table for
their conjunction (p ∧ q) and disjunction (p ∨ q).
p q
T
F
T
F
Alternate true (T) and (F) false for the last component statement variable.
This will be our convention.
Example: Given statement variables p and q, let us construct a truth table for
their conjunction (p ∧ q) and disjunction (p ∨ q).
p q
T T
T F
F T
F F
Alternate two trues and two falses for the previous column.
This will account for all possible truth values for components.
Example: Given statement variables p and q, let us construct a truth table for
their conjunction (p ∧ q) and disjunction (p ∨ q).
p q p∧q
T T
T F
F T
F F
Example: Given statement variables p and q, let us construct a truth table for
their conjunction (p ∧ q) and disjunction (p ∨ q).
p q p∧q
T T T
T F F
F T F
F F F
Fill in the truth values for each row corresponding to the component values.
Example: Given statement variables p and q, let us construct a truth table for
their conjunction (p ∧ q) and disjunction (p ∨ q).
p q p∧q p∨q
T T T
T F F
F T F
F F F
Example: Given statement variables p and q, let us construct a truth table for
their conjunction (p ∧ q) and disjunction (p ∨ q).
p q p∧q p∨q
T T T T
T F F T
F T F T
F F F F
Example: Given statement variables p and q, let us construct a truth table for
their conjunction (p ∧ q) and disjunction (p ∨ q).
p q p∧q p∨q
T T T T
T F F T
F T F T
F F F F
p q r
p q r
T
F
T
F
T
F
T
F
Alternate T and F for the r column.
p q r
T T
T F
F T
F F
T T
T F
F T
F F
Alternate TT and FF for the q column to the left.
p q r
T T T
T T F
T F T
T F F
F T T
F T F
F F T
F F F
Alternate TTTT and FFFF for the p column to the left.
p q r p∧q
T T T T
T T F T
T F T F
T F F F
F T T F
F T F F
F F T F
F F F F
Make a helper column for the component p ∧ q and fill.
p q r p∧q ∼r
T T T T F
T T F T T
T F T F F
T F F F T
F T T F F
F T F F T
F F T F F
F F F F T
Make a helper column for the component ∼r and fill.
p q r p∧q ∼r (p ∧ q ) ∨ ∼r
T T T T F T
T T F T T T
T F T F F F
T F F F T T
F T T F F F
F T F F T T
F F T F F F
F F F F T T
Complete the table from the helper columns.
p q r p∧q ∼r (p ∧ q ) ∨ ∼r
T T T T F T
T T F T T T
T F T F F F
T F F F T T
F T T F F F
F T F F T T
F F T F F F
F F F F T T
Note: Strictly speaking, helper columns are not necessary. We use them,
however, to work toward the final statement in a way that each new column is
formed simply as a conjunction, disjunction, or negation involving previous
columns.
John Theado, PhD Intro to Discrete Structures February 9, 2022 26 / 157
Chapter 2: The Logic of Compound Statements Section 1: Logical Forms and Logical Equivalence
Logical Equivalence
Consider statement forms A and B possibly using some of the same statement
variables.
Logical Equivalence
Consider statement forms A and B possibly using some of the same statement
variables.
That is, for example, A could represent ∼p ∨ q and B some other statement
form.
Logical Equivalence
Consider statement forms A and B possibly using some of the same statement
variables.
That is, for example, A could represent ∼p ∨ q and B some other statement
form.
A and B are considered logically equivalent, denoted A ≡ B, if any
substitution of statement variables with statements (or truth values) results in
the same truth value.
Logical Equivalence
Consider statement forms A and B possibly using some of the same statement
variables.
That is, for example, A could represent ∼p ∨ q and B some other statement
form.
A and B are considered logically equivalent, denoted A ≡ B, if any
substitution of statement variables with statements (or truth values) results in
the same truth value.
In other words, two statement forms are equivalent if they have identical
columns in a truth table.
Logical Equivalence
Consider statement forms A and B possibly using some of the same statement
variables.
That is, for example, A could represent ∼p ∨ q and B some other statement
form.
A and B are considered logically equivalent, denoted A ≡ B, if any
substitution of statement variables with statements (or truth values) results in
the same truth value.
In other words, two statement forms are equivalent if they have identical
columns in a truth table.
In the same way, two statement forms, presented in two different truth tables,
are equivalent if they have identical columns so long as they are consistently
labeled such as by our convention!
Logical Equivalence
Consider statement forms A and B possibly using some of the same statement
variables.
That is, for example, A could represent ∼p ∨ q and B some other statement
form.
A and B are considered logically equivalent, denoted A ≡ B, if any
substitution of statement variables with statements (or truth values) results in
the same truth value.
In other words, two statement forms are equivalent if they have identical
columns in a truth table.
In the same way, two statement forms, presented in two different truth tables,
are equivalent if they have identical columns so long as they are consistently
labeled such as by our convention!
This is why, for this course and text, we use one and only one convention for
labeling truth tables.
John Theado, PhD Intro to Discrete Structures February 9, 2022 28 / 157
Chapter 2: The Logic of Compound Statements Section 1: Logical Forms and Logical Equivalence
p ∼p ∼(∼p)
T F T
F T F
p ∼p ∼(∼p)
T F T
F T F
Question: Does ∼ distribute with ∧ and ∨ in the same way that multiplication
distributes over addition?
Question: Does ∼ distribute with ∧ and ∨ in the same way that multiplication
distributes over addition?
Solution: Not exactly. Let’s look at a truth table for both ∼(p ∧ q ) and
∼p ∧ ∼q:
p q
T T
T F
F T
F F
Question: Does ∼ distribute with ∧ and ∨ in the same way that multiplication
distributes over addition?
Solution: Not exactly. Let’s look at a truth table for both ∼(p ∧ q ) and
∼p ∧ ∼q:
p q p∧q
T T
T F
F T
F F
Question: Does ∼ distribute with ∧ and ∨ in the same way that multiplication
distributes over addition?
Solution: Not exactly. Let’s look at a truth table for both ∼(p ∧ q ) and
∼p ∧ ∼q:
p q p∧q
T T T
T F F
F T F
F F F
Question: Does ∼ distribute with ∧ and ∨ in the same way that multiplication
distributes over addition?
Solution: Not exactly. Let’s look at a truth table for both ∼(p ∧ q ) and
∼p ∧ ∼q:
p q p∧q ∼(p ∧ q )
T T T
T F F
F T F
F F F
Question: Does ∼ distribute with ∧ and ∨ in the same way that multiplication
distributes over addition?
Solution: Not exactly. Let’s look at a truth table for both ∼(p ∧ q ) and
∼p ∧ ∼q:
p q p∧q ∼(p ∧ q )
T T T F
T F F T
F T F T
F F F T
Question: Does ∼ distribute with ∧ and ∨ in the same way that multiplication
distributes over addition?
Solution: Not exactly. Let’s look at a truth table for both ∼(p ∧ q ) and
∼p ∧ ∼q:
p q p∧q ∼(p ∧ q ) ∼p
T T T F
T F F T
F T F T
F F F T
Question: Does ∼ distribute with ∧ and ∨ in the same way that multiplication
distributes over addition?
Solution: Not exactly. Let’s look at a truth table for both ∼(p ∧ q ) and
∼p ∧ ∼q:
p q p∧q ∼(p ∧ q ) ∼p
T T T F F
T F F T F
F T F T T
F F F T T
Question: Does ∼ distribute with ∧ and ∨ in the same way that multiplication
distributes over addition?
Solution: Not exactly. Let’s look at a truth table for both ∼(p ∧ q ) and
∼p ∧ ∼q:
p q p∧q ∼(p ∧ q ) ∼p ∼q
T T T F F
T F F T F
F T F T T
F F F T T
Question: Does ∼ distribute with ∧ and ∨ in the same way that multiplication
distributes over addition?
Solution: Not exactly. Let’s look at a truth table for both ∼(p ∧ q ) and
∼p ∧ ∼q:
p q p∧q ∼(p ∧ q ) ∼p ∼q
T T T F F F
T F F T F T
F T F T T F
F F F T T T
Question: Does ∼ distribute with ∧ and ∨ in the same way that multiplication
distributes over addition?
Solution: Not exactly. Let’s look at a truth table for both ∼(p ∧ q ) and
∼p ∧ ∼q:
p q p∧q ∼(p ∧ q ) ∼p ∼q ∼p ∧ ∼q
T T T F F F
T F F T F T
F T F T T F
F F F T T T
Question: Does ∼ distribute with ∧ and ∨ in the same way that multiplication
distributes over addition?
Solution: Not exactly. Let’s look at a truth table for both ∼(p ∧ q ) and
∼p ∧ ∼q:
p q p∧q ∼(p ∧ q ) ∼p ∼q ∼p ∧ ∼q
T T T F F F F
T F F T F T F
F T F T T F F
F F F T T T T
Question: Does ∼ distribute with ∧ and ∨ in the same way that multiplication
distributes over addition?
Solution: Not exactly. Let’s look at a truth table for both ∼(p ∧ q ) and
∼p ∧ ∼q:
p q p∧q ∼(p ∧ q ) ∼p ∼q ∼p ∧ ∼q
T T T F F F F
T F F T F T F
F T F T T F F
F F F T T T T
Since the columns for ∼(p ∧ q ) and ∼p ∧ ∼q do not match, the statements
are not equivalent, and hence the analogous distributive property does not
always hold.
Question: Does ∼ distribute with ∧ and ∨ in the same way that multiplication
distributes over addition?
Solution: Not exactly. Let’s look at a truth table for both ∼(p ∧ q ) and
∼p ∧ ∼q:
p q p∧q ∼(p ∧ q ) ∼p ∼q ∼p ∧ ∼q ∼p ∨ ∼q
T T T F F F F F
T F F T F T F T
F T F T T F F T
F F F T T T T T
Since the columns for ∼(p ∧ q ) and ∼p ∧ ∼q do not match, the statements
are not equivalent, and hence the analogous distributive property does not
always hold.
However, if we add a column for ∼p ∨ ∼q we see that it is equivalent to
∼(p ∧ q ).
De Morgan’s Laws
De Morgan’s laws:
i. ∼(p ∧ q ) ≡ ∼p ∨ ∼q
ii. ∼(p ∨ q ) ≡ ∼p ∧ ∼q
De Morgan’s Laws
De Morgan’s laws:
i. ∼(p ∧ q ) ≡ ∼p ∨ ∼q
ii. ∼(p ∨ q ) ≡ ∼p ∧ ∼q
The first law may be read as the negation of the conjunction is equivalent to
the disjunction of the negations.
De Morgan’s Laws
De Morgan’s laws:
i. ∼(p ∧ q ) ≡ ∼p ∨ ∼q
ii. ∼(p ∨ q ) ≡ ∼p ∧ ∼q
The first law may be read as the negation of the conjunction is equivalent to
the disjunction of the negations.
The second law may be read as the negation of the disjunction is equivalent to
the conjunction of the negations.
De Morgan’s Laws
De Morgan’s laws:
i. ∼(p ∧ q ) ≡ ∼p ∨ ∼q
ii. ∼(p ∨ q ) ≡ ∼p ∧ ∼q
The first law may be read as the negation of the conjunction is equivalent to
the disjunction of the negations.
The second law may be read as the negation of the disjunction is equivalent to
the conjunction of the negations.
Example: Recall the earlier neither-nor example: Neither p nor q may be
symbolized as either ∼p ∧ ∼q or ∼(p ∨ q ).
p
T
F
p ∼p
T
F
p ∼p
T F
F T
p ∼p p ∨ ∼p
T F
F T
p ∼p p ∨ ∼p
T F T
F T T
p ∼p p ∨ ∼p p ∧ ∼p
T F T
F T T
p ∼p p ∨ ∼p p ∧ ∼p
T F T F
F T T F
p ∼p p ∨ ∼p p ∧ ∼p
T F T F
F T T F
No matter what truth value we give p, the statement p ∨ ∼p is true and hence
a tautology while the statement p ∧ ∼p is false and hence a contradiction.
John Theado, PhD Intro to Discrete Structures February 9, 2022 34 / 157
Chapter 2: The Logic of Compound Statements Section 1: Logical Forms and Logical Equivalence
∼(∼p ∧ q ) ∧ (p ∨ q )
Conditional Statements
Let p and q be statements. A sentence of the form “If p then q”, denoted
symbolically as p → q is called a conditional statement where
Conditional Statements
Let p and q be statements. A sentence of the form “If p then q”, denoted
symbolically as p → q is called a conditional statement where
Conditional Statements
Let p and q be statements. A sentence of the form “If p then q”, denoted
symbolically as p → q is called a conditional statement where
Conditional Statements
Let p and q be statements. A sentence of the form “If p then q”, denoted
symbolically as p → q is called a conditional statement where
Conditional Statements
Let p and q be statements. A sentence of the form “If p then q”, denoted
symbolically as p → q is called a conditional statement where
Conditional Statements
Let p and q be statements. A sentence of the form “If p then q”, denoted
symbolically as p → q is called a conditional statement where
Example: Suppose you are on call with a tech support agent about a
computer issue. The agent states:
p q p→q Explanation
T T
T F
F T
F F
Example: Suppose you are on call with a tech support agent about a
computer issue. The agent states:
p q p→q Explanation
T T T If you reboot, and this solves the issue, the
agent spoke true.
T F
F T
F F
Example: Suppose you are on call with a tech support agent about a
computer issue. The agent states:
p q p→q Explanation
T T T If you reboot, and this solves the issue, the
agent spoke true.
T F F If you reboot, but this does not solve the issue,
the agent spoke falsely.
F T
F F
Example: Suppose you are on call with a tech support agent about a
computer issue. The agent states:
p q p→q Explanation
T T T If you reboot, and this solves the issue, the
agent spoke true.
T F F If you reboot, but this does not solve the issue,
the agent spoke falsely.
F T T But if you refuse to reboot, we cannot say that
F F T agent spoke falsely no matter what happens.
Example: Suppose you are on call with a tech support agent about a
computer issue. The agent states:
p q p→q Explanation
T T T If you reboot, and this solves the issue, the
agent spoke true.
T F F If you reboot, but this does not solve the issue,
the agent spoke falsely.
F T T But if you refuse to reboot, we cannot say that
F F T agent spoke falsely no matter what happens.
A conditional statement that is true because the hypothesis is false is called
vacuously true or true by default.
John Theado, PhD Intro to Discrete Structures February 9, 2022 39 / 157
Chapter 2: The Logic of Compound Statements Section 2: Conditional Statements
Regardless, we want this statement to always be true, and the consequent considered
true conditionally based on the truth of the hypothesis.
Regardless, we want this statement to always be true, and the consequent considered
true conditionally based on the truth of the hypothesis.
Example 2: Consider the statement
If 0 = 1 then 1 = 2.
Regardless, we want this statement to always be true, and the consequent considered
true conditionally based on the truth of the hypothesis.
Example 2: Consider the statement
If 0 = 1 then 1 = 2.
As strange as it may seem, this statement is vacuously true by virtue of always having
a false hypothesis. Contrary to Example 1 though, it does not have much use outside
of being an example.
p q ∼q p ∨ ∼q ∼p
T T F T F
T F T T F
F T F F T
F F T T T
p q ∼q p ∨ ∼q ∼p p ∨ ∼q → ∼p
T T F T F
T F T T F
F T F F T
F F T T T
p q ∼q p ∨ ∼q ∼p p ∨ ∼q → ∼p
T T F T F F
T F T T F
F T F F T
F F T T T
p q ∼q p ∨ ∼q ∼p p ∨ ∼q → ∼p
T T F T F F
T F T T F F
F T F F T
F F T T T
p q ∼q p ∨ ∼q ∼p p ∨ ∼q → ∼p
T T F T F F
T F T T F F
F T F F T T
F F T T T
p q ∼q p ∨ ∼q ∼p p ∨ ∼q → ∼p
T T F T F F
T F T T F F
F T F F T T
F F T T T T
p q ∼q p ∨ ∼q ∼p p ∨ ∼q → ∼p
T T F T F F
T F T T F F
F T F F T T
F F T T T T
Remark: While ∨ and ∧ are commutative, → is not. We must be careful when
determining the truth table for conditionals.
p q r
p q r
T
F
T
F
T
F
T
F
p q r
T T
T F
F T
F F
T T
T F
F T
F F
p q r
T T T
T T F
T F T
T F F
F T T
F T F
F F T
F F F
p q r p∨q
T T T T
T T F T
T F T T
T F F T
F T T T
F T F T
F F T F
F F F F
p q r p∨q p∨q → r
T T T T
T T F T
T F T T
T F F T
F T T T
F T F T
F F T F
F F F F
p q r p∨q p∨q → r
T T T T
T T F T
T F T T
T F F T
F T T T
F T F T
F F T F
F F F F
p q r p∨q p∨q → r
T T T T
T T F T
T F T T
T F F T
F T T T
F T F T
F F T F T
F F F F T
p q r p∨q p∨q → r
T T T T T
T T F T F
T F T T T
T F F T F
F T T T T
F T F T F
F F T F T
F F F F T
I Case 2a: If p ∨ q is false, both p and q must be false, making the hypothesis in
each conditional above false.
I Case 2a: If p ∨ q is false, both p and q must be false, making the hypothesis in
each conditional above false. Then each conditional above will be vacuously
true.
I Case 2a: If p ∨ q is false, both p and q must be false, making the hypothesis in
each conditional above false. Then each conditional above will be vacuously
true. Hence the conjunction in the RHS true and both sides have the same truth
value again.
I Case 2a: If p ∨ q is false, both p and q must be false, making the hypothesis in
each conditional above false. Then each conditional above will be vacuously
true. Hence the conjunction in the RHS true and both sides have the same truth
value again.
I Case 2b: Otherwise at least one of p or q is true making the hypothesis in the
LHS true.
I Case 2a: If p ∨ q is false, both p and q must be false, making the hypothesis in
each conditional above false. Then each conditional above will be vacuously
true. Hence the conjunction in the RHS true and both sides have the same truth
value again.
I Case 2b: Otherwise at least one of p or q is true making the hypothesis in the
LHS true. This makes the entire LHS false.
I Case 2a: If p ∨ q is false, both p and q must be false, making the hypothesis in
each conditional above false. Then each conditional above will be vacuously
true. Hence the conjunction in the RHS true and both sides have the same truth
value again.
I Case 2b: Otherwise at least one of p or q is true making the hypothesis in the
LHS true. This makes the entire LHS false. Whether or not p, q, or both are true,
at least one of the conditionals will be false, making the conjunction false.
I Case 2a: If p ∨ q is false, both p and q must be false, making the hypothesis in
each conditional above false. Then each conditional above will be vacuously
true. Hence the conjunction in the RHS true and both sides have the same truth
value again.
I Case 2b: Otherwise at least one of p or q is true making the hypothesis in the
LHS true. This makes the entire LHS false. Whether or not p, q, or both are true,
at least one of the conditionals will be false, making the conjunction false. Then
both the LHS and RHS will have the same truth value of false.
I Case 2a: If p ∨ q is false, both p and q must be false, making the hypothesis in
each conditional above false. Then each conditional above will be vacuously
true. Hence the conjunction in the RHS true and both sides have the same truth
value again.
I Case 2b: Otherwise at least one of p or q is true making the hypothesis in the
LHS true. This makes the entire LHS false. Whether or not p, q, or both are true,
at least one of the conditionals will be false, making the conjunction false. Then
both the LHS and RHS will have the same truth value of false.
Since we have demonstrated the equivalence in all possible cases, the proof is
complete.
John Theado, PhD Intro to Discrete Structures February 9, 2022 43 / 157
Chapter 2: The Logic of Compound Statements Section 2: Conditional Statements
Consider the algorthmic difference between the previous proof and proving via
a truth table. If you were to approach this as a programming project, which
code would look nicer?
Consider the algorthmic difference between the previous proof and proving via
a truth table. If you were to approach this as a programming project, which
code would look nicer?
∼(p → q )
The contrapositive of “If p, then q” is “If not q, then not p. Symbolically, the
contrapositive of p → q is ∼q → ∼p.
The contrapositive of “If p, then q” is “If not q, then not p. Symbolically, the
contrapositive of p → q is ∼q → ∼p.
Observe that any conditional statement is equivalent to its contrapositive:
∼q → ∼p
The contrapositive of “If p, then q” is “If not q, then not p. Symbolically, the
contrapositive of p → q is ∼q → ∼p.
Observe that any conditional statement is equivalent to its contrapositive:
∼q → ∼p ≡ q ∨ ∼p Equivalent disjunction.
The contrapositive of “If p, then q” is “If not q, then not p. Symbolically, the
contrapositive of p → q is ∼q → ∼p.
Observe that any conditional statement is equivalent to its contrapositive:
∼q → ∼p ≡ q ∨ ∼p Equivalent disjunction.
≡ ∼p ∨ q Commutativity of ∨.
The contrapositive of “If p, then q” is “If not q, then not p. Symbolically, the
contrapositive of p → q is ∼q → ∼p.
Observe that any conditional statement is equivalent to its contrapositive:
∼q → ∼p ≡ q ∨ ∼p Equivalent disjunction.
≡ ∼p ∨ q Commutativity of ∨.
≡p→q Equivalent conditional.
The contrapositive of “If p, then q” is “If not q, then not p. Symbolically, the
contrapositive of p → q is ∼q → ∼p.
Observe that any conditional statement is equivalent to its contrapositive:
∼q → ∼p ≡ q ∨ ∼p Equivalent disjunction.
≡ ∼p ∨ q Commutativity of ∨.
≡p→q Equivalent conditional.
To summarize,
Statement
Name Example In Words
Form
The contrapositive of “If p, then q” is “If not q, then not p. Symbolically, the
contrapositive of p → q is ∼q → ∼p.
Observe that any conditional statement is equivalent to its contrapositive:
∼q → ∼p ≡ q ∨ ∼p Equivalent disjunction.
≡ ∼p ∨ q Commutativity of ∨.
≡p→q Equivalent conditional.
To summarize,
Statement
Name Example In Words
Form
p→q Conditional If it rains, I will bring an umbrella.
The contrapositive of “If p, then q” is “If not q, then not p. Symbolically, the
contrapositive of p → q is ∼q → ∼p.
Observe that any conditional statement is equivalent to its contrapositive:
∼q → ∼p ≡ q ∨ ∼p Equivalent disjunction.
≡ ∼p ∨ q Commutativity of ∨.
≡p→q Equivalent conditional.
To summarize,
Statement
Name Example In Words
Form
p→q Conditional If it rains, I will bring an umbrella.
∼p ∨ q Equivalent Disjunction It won’t rain, or I will bring an umbrella.
The contrapositive of “If p, then q” is “If not q, then not p. Symbolically, the
contrapositive of p → q is ∼q → ∼p.
Observe that any conditional statement is equivalent to its contrapositive:
∼q → ∼p ≡ q ∨ ∼p Equivalent disjunction.
≡ ∼p ∨ q Commutativity of ∨.
≡p→q Equivalent conditional.
To summarize,
Statement
Name Example In Words
Form
p→q Conditional If it rains, I will bring an umbrella.
∼p ∨ q Equivalent Disjunction It won’t rain, or I will bring an umbrella.
Equivalent If I do not bring an umbrella, it did not
∼q → ∼p
Contrapositive rain.
The contrapositive of “If p, then q” is “If not q, then not p. Symbolically, the
contrapositive of p → q is ∼q → ∼p.
Observe that any conditional statement is equivalent to its contrapositive:
∼q → ∼p ≡ q ∨ ∼p Equivalent disjunction.
≡ ∼p ∨ q Commutativity of ∨.
≡p→q Equivalent conditional.
To summarize,
Statement
Name Example In Words
Form
p→q Conditional If it rains, I will bring an umbrella.
∼p ∨ q Equivalent Disjunction It won’t rain, or I will bring an umbrella.
Equivalent If I do not bring an umbrella, it did not
∼q → ∼p
Contrapositive rain.
Negation of the It will rain, but I won’t bring an
p ∧ ∼q
Conditional umbrella.
The Biconditional
The Biconditional
The Biconditional
The Biconditional
The Biconditional
I p if and only if q,
The Biconditional
I p if and only if q,
I p is necessary and sufficient for q.
The Biconditional
I p if and only if q,
I p is necessary and sufficient for q.
The Biconditional
I p if and only if q,
I p is necessary and sufficient for q.
Order of Operations
Order of Operations
Order of Operations
Arguments
Arguments
Arguments
Arguments
Arguments
Valid argument forms may be thought of as machines which verify the truth of
their conclusion when used to make sound arguments. Some things to keep in
mind:
Valid argument forms may be thought of as machines which verify the truth of
their conclusion when used to make sound arguments. Some things to keep in
mind:
Valid argument forms may be thought of as machines which verify the truth of
their conclusion when used to make sound arguments. Some things to keep in
mind:
Valid argument forms may be thought of as machines which verify the truth of
their conclusion when used to make sound arguments. Some things to keep in
mind:
Valid argument forms may be thought of as machines which verify the truth of
their conclusion when used to make sound arguments. Some things to keep in
mind:
We will begin by looking at the most basic argument form, modus ponens.
Consider following modus ponens argument form and its truth table:
p q p→q p q
If p, then q T T T T T
p T F F T F
∴ q F T T F T
F F T F F
Consider following modus ponens argument form and its truth table:
p q p→q p q
If p, then q T T T T T
p T F F T F
∴ q F T T F T
F F T F F
Consider following modus ponens argument form and its truth table:
p q p→q p q
If p, then q T T T T T
p T F F T F
∴ q F T T F T
F F T F F
Consider following modus ponens argument form and its truth table:
p q p→q p q
If p, then q T T T T T
p T F F T F
∴ q F T T F T
F F T F F
The truth of the premises do not guarantee a true conclusion, so this argument
is invalid.
The truth of the premises do not guarantee a true conclusion, so this argument
is invalid.
This argument form is a fallacy known as the converse error or
affirming the consequent.
John Theado, PhD Intro to Discrete Structures February 9, 2022 57 / 157
Chapter 2: The Logic of Compound Statements Section 3: Valid and Invalid Arguments
You may determine the validity or invalidity of an argument via truth table as
follows:
You may determine the validity or invalidity of an argument via truth table as
follows:
You may determine the validity or invalidity of an argument via truth table as
follows:
You may determine the validity or invalidity of an argument via truth table as
follows:
You may determine the validity or invalidity of an argument via truth table as
follows:
You may determine the validity or invalidity of an argument via truth table as
follows:
p → q ∨ ∼r
q → p∧r
∴p→r
p → q ∨ ∼r
q → p∧r
∴p→r
p → q ∨ ∼r
q → p∧r
∴p→r
p → q ∨ ∼r
q → p∧r
∴p→r
We only look where the premises are true . If each conclusion were true , the
argument would be valid, but we find a false conclusion in a critical row, invalidating
the argument.
p → q ∨ ∼r
q → p∧r
∴p→r
p → q ∨ ∼r
q → p∧r
∴p→r
Solution 2: Alternatively, since we are looking for situations where the premises are
true, but the conclusion is false, we will assume a false conclusion and see if there are
any cases where all the premises are all true, and conclude the argument is invalid,
and otherwise conclude it is valid.
p → q ∨ ∼r
q → p∧r
∴p→r
Solution 2: Alternatively, since we are looking for situations where the premises are
true, but the conclusion is false, we will assume a false conclusion and see if there are
any cases where all the premises are all true, and conclude the argument is invalid,
and otherwise conclude it is valid.
Observe that the conclusion p → r is false when p is true and r is false.
p → q ∨ ∼r
q → p∧r
∴p→r
Solution 2: Alternatively, since we are looking for situations where the premises are
true, but the conclusion is false, we will assume a false conclusion and see if there are
any cases where all the premises are all true, and conclude the argument is invalid,
and otherwise conclude it is valid.
Observe that the conclusion p → r is false when p is true and r is false.
The second premise can only be true when q is false.
p → q ∨ ∼r
q → p∧r
∴p→r
Solution 2: Alternatively, since we are looking for situations where the premises are
true, but the conclusion is false, we will assume a false conclusion and see if there are
any cases where all the premises are all true, and conclude the argument is invalid,
and otherwise conclude it is valid.
Observe that the conclusion p → r is false when p is true and r is false.
The second premise can only be true when q is false.
The first premise is true regardless of the value of q.
p → q ∨ ∼r
q → p∧r
∴p→r
Solution 2: Alternatively, since we are looking for situations where the premises are
true, but the conclusion is false, we will assume a false conclusion and see if there are
any cases where all the premises are all true, and conclude the argument is invalid,
and otherwise conclude it is valid.
Observe that the conclusion p → r is false when p is true and r is false.
The second premise can only be true when q is false.
The first premise is true regardless of the value of q.
This argument form is therefore invalid since p being true while q and r are false gives
true premises with a false conclusion. Compare this with the truth table solution.
An argument form consisting of two premises, called the major premise and
minor premise is called a syllogism.
An argument form consisting of two premises, called the major premise and
minor premise is called a syllogism.
The most famous syllogism, modus ponens, which we already introduced,
has the following form:
If p, then q
p
∴ q
An argument form consisting of two premises, called the major premise and
minor premise is called a syllogism.
The most famous syllogism, modus ponens, which we already introduced,
has the following form:
If p, then q
p
∴ q
It is valid as we have already seen with a truth table, but we can reason its
validity assuming the truth of the premises:
An argument form consisting of two premises, called the major premise and
minor premise is called a syllogism.
The most famous syllogism, modus ponens, which we already introduced,
has the following form:
If p, then q
p
∴ q
It is valid as we have already seen with a truth table, but we can reason its
validity assuming the truth of the premises:
An argument form consisting of two premises, called the major premise and
minor premise is called a syllogism.
The most famous syllogism, modus ponens, which we already introduced,
has the following form:
If p, then q
p
∴ q
It is valid as we have already seen with a truth table, but we can reason its
validity assuming the truth of the premises:
An argument form consisting of two premises, called the major premise and
minor premise is called a syllogism.
The most famous syllogism, modus ponens, which we already introduced,
has the following form:
If p, then q
p
∴ q
It is valid as we have already seen with a truth table, but we can reason its
validity assuming the truth of the premises:
p q p→q ∼q ∼p
If p, then q T T T F F
∼q T F F T F
∴ ∼p F T T F T
F F T T T
p q p→q ∼q ∼p
If p, then q T T T F F
∼q T F F T F
∴ ∼p F T T F T
F F T T T
p q p→q ∼q ∼p
If p, then q T T T F F
∼q T F F T F
∴ ∼p F T T F T
F F T T T
The truth table demonstrates the validity, but if we replace the conditional with
the equivalent contrapositive, then the argument form is equivalent to modus
ponens.
p q p→q ∼q ∼p
If p, then q T T T F F
∼q T F F T F
∴ ∼p F T T F T
F F T T T
The truth table demonstrates the validity, but if we replace the conditional with
the equivalent contrapositive, then the argument form is equivalent to modus
ponens.
Example: The following is an example of modus tollens:
If Zeus is human, then Zeus is mortal.
Zeus is not mortal.
∴ Zeus is not human.
Logical Fallacies
Logical Fallacies
Logical Fallacies
Logical Fallacies
We have already discussed the converse error a.k.a. affirming the consequent,
as a fallacy. It is often confused with the valid modus ponens form.
We have already discussed the converse error a.k.a. affirming the consequent,
as a fallacy. It is often confused with the valid modus ponens form.
We also have the inverse fallacy, a.k.a. denying the antecedent. It has the
invalid form
If p, then q.
∼p
∴ ∼q
We have already discussed the converse error a.k.a. affirming the consequent,
as a fallacy. It is often confused with the valid modus ponens form.
We also have the inverse fallacy, a.k.a. denying the antecedent. It has the
invalid form
If p, then q.
∼p
∴ ∼q
If p is false, the premises become true, but we cannot deduce the conclusion
either way.
We have already discussed the converse error a.k.a. affirming the consequent,
as a fallacy. It is often confused with the valid modus ponens form.
We also have the inverse fallacy, a.k.a. denying the antecedent. It has the
invalid form
If p, then q.
∼p
∴ ∼q
If p is false, the premises become true, but we cannot deduce the conclusion
either way.
This form may be confused with the valid modus tollens.
Rules of Inference
A rule of inference is an argument form, like modus ponens or modus tollens, that is
valid. We will give some common examples.
Rules of Inference
A rule of inference is an argument form, like modus ponens or modus tollens, that is
valid. We will give some common examples.
The following valid argument forms are called generalization:
p q
∴ p∨q ∴ p∨q
Rules of Inference
A rule of inference is an argument form, like modus ponens or modus tollens, that is
valid. We will give some common examples.
The following valid argument forms are called generalization:
p q
∴ p∨q ∴ p∨q
p : Anton is a junior.
q : Anton is a senior.
Rules of Inference
A rule of inference is an argument form, like modus ponens or modus tollens, that is
valid. We will give some common examples.
The following valid argument forms are called generalization:
p q
∴ p∨q ∴ p∨q
p : Anton is a junior.
q : Anton is a senior.
Then p ∨ q, the statement that Anton is a junior or senior, also means that Anton is an
upperclassman.
Rules of Inference
A rule of inference is an argument form, like modus ponens or modus tollens, that is
valid. We will give some common examples.
The following valid argument forms are called generalization:
p q
∴ p∨q ∴ p∨q
p : Anton is a junior.
q : Anton is a senior.
Then p ∨ q, the statement that Anton is a junior or senior, also means that Anton is an
upperclassman.
We then infer from the fact that if Anton is a junior (p), that more generally, he is an
upperclassman (p ∨ q ).
p∧q p∧q
∴p ∴q
p∧q p∧q
∴p ∴q
p∧q p∧q
∴p ∴q
If we discover that Ana knows both numerical analysis and graph algorithms
(p ∧ q ), that in particular, she knows graph algorithms (q).
p∨q p∨q
∼q ∼p
∴p ∴q
p∨q p∨q
∼q ∼p
∴p ∴q
p∨q p∨q
∼q ∼p
∴p ∴q
p∨q p∨q
∼q ∼p
∴p ∴q
p→q
q→r
∴p→r
p→q
q→r
∴p→r
p→q
q→r
∴p→r
p∨q
p→r
q→r
∴r
p∨q
p→r
q→r
∴r
Example: Outline a proof that the product of two consecutive integers is always even.
p∨q
p→r
q→r
∴r
Example: Outline a proof that the product of two consecutive integers is always even.
Solution: The product of two consecutive integers is n(n + 1), where n is any integer.
p∨q
p→r
q→r
∴r
Example: Outline a proof that the product of two consecutive integers is always even.
Solution: The product of two consecutive integers is n(n + 1), where n is any integer.
The statement forms p, q, and r will be as follows:
p: n is odd. q: n is even. r: n(n + 1) is even.
p∨q
p→r
q→r
∴r
Example: Outline a proof that the product of two consecutive integers is always even.
Solution: The product of two consecutive integers is n(n + 1), where n is any integer.
The statement forms p, q, and r will be as follows:
p: n is odd. q: n is even. r: n(n + 1) is even.
Since this is a valid argument form, the proof will be successful if we
p∨q
p→r
q→r
∴r
Example: Outline a proof that the product of two consecutive integers is always even.
Solution: The product of two consecutive integers is n(n + 1), where n is any integer.
The statement forms p, q, and r will be as follows:
p: n is odd. q: n is even. r: n(n + 1) is even.
Since this is a valid argument form, the proof will be successful if we
p∨q
p→r
q→r
∴r
Example: Outline a proof that the product of two consecutive integers is always even.
Solution: The product of two consecutive integers is n(n + 1), where n is any integer.
The statement forms p, q, and r will be as follows:
p: n is odd. q: n is even. r: n(n + 1) is even.
Since this is a valid argument form, the proof will be successful if we
p∨q
p→r
q→r
∴r
Example: Outline a proof that the product of two consecutive integers is always even.
Solution: The product of two consecutive integers is n(n + 1), where n is any integer.
The statement forms p, q, and r will be as follows:
p: n is odd. q: n is even. r: n(n + 1) is even.
Since this is a valid argument form, the proof will be successful if we
Example: Suppose that you lost your glasses. Furthermore, you know the following
statements (premises) are true:
Example: Suppose that you lost your glasses. Furthermore, you know the following
statements (premises) are true:
I (RK → GK ) If I was reading my notes in the kitchen (RK ), then my glasses are
on the kitchen table (GK ).
Example: Suppose that you lost your glasses. Furthermore, you know the following
statements (premises) are true:
I (RK → GK ) If I was reading my notes in the kitchen (RK ), then my glasses are
on the kitchen table (GK ).
I (GK → SB) If my glasses are on the kitchen table (GK ), then I saw them at
breakfast (SB).
Example: Suppose that you lost your glasses. Furthermore, you know the following
statements (premises) are true:
I (RK → GK ) If I was reading my notes in the kitchen (RK ), then my glasses are
on the kitchen table (GK ).
I (GK → SB) If my glasses are on the kitchen table (GK ), then I saw them at
breakfast (SB).
I (∼SB) I did not see my glasses at breakfast.
Example: Suppose that you lost your glasses. Furthermore, you know the following
statements (premises) are true:
I (RK → GK ) If I was reading my notes in the kitchen (RK ), then my glasses are
on the kitchen table (GK ).
I (GK → SB) If my glasses are on the kitchen table (GK ), then I saw them at
breakfast (SB).
I (∼SB) I did not see my glasses at breakfast.
I (RL ∨ RK ) I was reading my notes in the living room (RL) or I was reading my
notes in the kitchen (RK ).
Example: Suppose that you lost your glasses. Furthermore, you know the following
statements (premises) are true:
I (RK → GK ) If I was reading my notes in the kitchen (RK ), then my glasses are
on the kitchen table (GK ).
I (GK → SB) If my glasses are on the kitchen table (GK ), then I saw them at
breakfast (SB).
I (∼SB) I did not see my glasses at breakfast.
I (RL ∨ RK ) I was reading my notes in the living room (RL) or I was reading my
notes in the kitchen (RK ).
I (RL → GC) If I was reading my notes in the living room (RL), then my glasses
are on the coffee table (GC ).
Example: Suppose that you lost your glasses. Furthermore, you know the following
statements (premises) are true:
I (RK → GK ) If I was reading my notes in the kitchen (RK ), then my glasses are
on the kitchen table (GK ).
I (GK → SB) If my glasses are on the kitchen table (GK ), then I saw them at
breakfast (SB).
I (∼SB) I did not see my glasses at breakfast.
I (RL ∨ RK ) I was reading my notes in the living room (RL) or I was reading my
notes in the kitchen (RK ).
I (RL → GC) If I was reading my notes in the living room (RL), then my glasses
are on the coffee table (GC ).
Let’s deduce that the glasses are on the coffee table (GC).
Arguments:
Simple Statements
RK : Reading in kitchen
GK : Glassess on kitchen table
SB: Saw at breakfast
RL: Reading in living room
GC: Glasses on coffee table
Starting Premises
1. RK → GK
2. GK → SB
3. ∼SB
4. RL ∨ RK
5. RL → GC
Arguments:
Simple Statements
1. RK → GK Premise 1
RK : Reading in kitchen
GK → SB Premise 2
GK : Glassess on kitchen table
∴ RK → SB Transitivity
SB: Saw at breakfast
RL: Reading in living room
GC: Glasses on coffee table
Starting Premises
1. RK → GK
2. GK → SB
3. ∼SB
4. RL ∨ RK
5. RL → GC
Arguments:
Simple Statements
1. RK → GK Premise 1
RK : Reading in kitchen
GK → SB Premise 2
GK : Glassess on kitchen table
∴ RK → SB Transitivity
SB: Saw at breakfast
RL: Reading in living room
2. RK → SB Conclusion 1
GC: Glasses on coffee table
∼SB Premise 3
∴ ∼RK Modus Tollens
Starting Premises
1. RK → GK
2. GK → SB
3. ∼SB
4. RL ∨ RK
5. RL → GC
Arguments:
Simple Statements
1. RK → GK Premise 1
RK : Reading in kitchen
GK → SB Premise 2
GK : Glassess on kitchen table
∴ RK → SB Transitivity
SB: Saw at breakfast
RL: Reading in living room
2. RK → SB Conclusion 1
GC: Glasses on coffee table
∼SB Premise 3
∴ ∼RK Modus Tollens
Starting Premises
1. RK → GK
3. RL ∨ RK Premise 4
2. GK → SB
3. ∼SB
∼RK Conclusion 2
4. RL ∨ RK ∴ RL Elimination
5. RL → GC
Arguments:
Simple Statements
1. RK → GK Premise 1
RK : Reading in kitchen
GK → SB Premise 2
GK : Glassess on kitchen table
∴ RK → SB Transitivity
SB: Saw at breakfast
RL: Reading in living room
2. RK → SB Conclusion 1
GC: Glasses on coffee table
∼SB Premise 3
∴ ∼RK Modus Tollens
Starting Premises
1. RK → GK
3. RL ∨ RK Premise 4
2. GK → SB
3. ∼SB
∼RK Conclusion 2
4. RL ∨ RK ∴ RL Elimination
5. RL → GC
4. RL → GC Premise 5
RL Conclusion 3
∴ GC Modus Ponens
p→q
q→r
r →p
∴p↔q↔r
p→q
q→r
r →p
∴p↔q↔r
Contradiction Rule
∼p → c, where c is a contradiction
∴p
Contradiction Rule
∼p → c, where c is a contradiction
∴p
Contradiction Rule
∼p → c, where c is a contradiction
∴p
Example: The logician Raymond Smullyan describes an island containing two types
of people: knights who always tell the truth and knaves who always lie.
You visit the island and are approached by two natives A and B who each approach
you as follows
A says :B is a knight.
B says :A and I are of opposite type.
Example: The logician Raymond Smullyan describes an island containing two types
of people: knights who always tell the truth and knaves who always lie.
You visit the island and are approached by two natives A and B who each approach
you as follows
A says :B is a knight.
B says :A and I are of opposite type.
Predicates
Consider the sentence
x 2 + 2 = 11.
Predicates
Consider the sentence
x 2 + 2 = 11.
In the domain of real numbers, this sentence is true when x = 3 or x = −3, and false
otherwise.
Predicates
Consider the sentence
x 2 + 2 = 11.
In the domain of real numbers, this sentence is true when x = 3 or x = −3, and false
otherwise.
If we symbolize this open sentence as P (x ), it may be thought of as a function from
the set R of real numbers to a set of statements, each with a truth value:
Predicates
Consider the sentence
x 2 + 2 = 11.
In the domain of real numbers, this sentence is true when x = 3 or x = −3, and false
otherwise.
If we symbolize this open sentence as P (x ), it may be thought of as a function from
the set R of real numbers to a set of statements, each with a truth value:
Predicates
Consider the sentence
x 2 + 2 = 11.
In the domain of real numbers, this sentence is true when x = 3 or x = −3, and false
otherwise.
If we symbolize this open sentence as P (x ), it may be thought of as a function from
the set R of real numbers to a set of statements, each with a truth value:
Predicates
Consider the sentence
x 2 + 2 = 11.
In the domain of real numbers, this sentence is true when x = 3 or x = −3, and false
otherwise.
If we symbolize this open sentence as P (x ), it may be thought of as a function from
the set R of real numbers to a set of statements, each with a truth value:
Predicates
Consider the sentence
x 2 + 2 = 11.
In the domain of real numbers, this sentence is true when x = 3 or x = −3, and false
otherwise.
If we symbolize this open sentence as P (x ), it may be thought of as a function from
the set R of real numbers to a set of statements, each with a truth value:
We can form predicates using more than one, but finitely many variables. Consider
these examples, and their truth sets:
We can form predicates using more than one, but finitely many variables. Consider
these examples, and their truth sets:
We can form predicates using more than one, but finitely many variables. Consider
these examples, and their truth sets:
We can form predicates using more than one, but finitely many variables. Consider
these examples, and their truth sets:
We can form predicates using more than one, but finitely many variables. Consider
these examples, and their truth sets:
The predicate E (n) is true for all integers n ∈ Z, but vacuously true in the case of odd
integers!
Quantified Statements
A quantified statement is formed from predicates by adding quantifiers like “some”
or “all” to make existential and universal statements.
Quantified Statements
A quantified statement is formed from predicates by adding quantifiers like “some”
or “all” to make existential and universal statements.
A universal statement using a predicate Q (x ) with a domain D is a statement of the
form (or using equivalent wording), ∀x ∈ D : Q (x ), and read as “for all x in D, Q (x )”.
Quantified Statements
A quantified statement is formed from predicates by adding quantifiers like “some”
or “all” to make existential and universal statements.
A universal statement using a predicate Q (x ) with a domain D is a statement of the
form (or using equivalent wording), ∀x ∈ D : Q (x ), and read as “for all x in D, Q (x )”.
Quantified Statements
A quantified statement is formed from predicates by adding quantifiers like “some”
or “all” to make existential and universal statements.
A universal statement using a predicate Q (x ) with a domain D is a statement of the
form (or using equivalent wording), ∀x ∈ D : Q (x ), and read as “for all x in D, Q (x )”.
Quantified Statements
A quantified statement is formed from predicates by adding quantifiers like “some”
or “all” to make existential and universal statements.
A universal statement using a predicate Q (x ) with a domain D is a statement of the
form (or using equivalent wording), ∀x ∈ D : Q (x ), and read as “for all x in D, Q (x )”.
Quantified Statements
A quantified statement is formed from predicates by adding quantifiers like “some”
or “all” to make existential and universal statements.
A universal statement using a predicate Q (x ) with a domain D is a statement of the
form (or using equivalent wording), ∀x ∈ D : Q (x ), and read as “for all x in D, Q (x )”.
Quantified Statements
A quantified statement is formed from predicates by adding quantifiers like “some”
or “all” to make existential and universal statements.
A universal statement using a predicate Q (x ) with a domain D is a statement of the
form (or using equivalent wording), ∀x ∈ D : Q (x ), and read as “for all x in D, Q (x )”.
Quantified Statements
A quantified statement is formed from predicates by adding quantifiers like “some”
or “all” to make existential and universal statements.
A universal statement using a predicate Q (x ) with a domain D is a statement of the
form (or using equivalent wording), ∀x ∈ D : Q (x ), and read as “for all x in D, Q (x )”.
Remark: We may often omit the domain specification for the variable if it is
understood, e.g. ∀x , Q (x ) instead of ∀x ∈ D , Q (x ).
John Theado, PhD Intro to Discrete Structures February 9, 2022 83 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Observe that the truth set for a. is the set D itself, i.e. a universal statement is
true if the truth set is equal to the domain.
Observe that the truth set for a. is the set D itself, i.e. a universal statement is
true if the truth set is equal to the domain.
The truth set for b. is the set (−∞, 0] ∪ [1, ∞) which is certainly not all of R.
Observe that the truth set for a. is the set D itself, i.e. a universal statement is
true if the truth set is equal to the domain.
The truth set for b. is the set (−∞, 0] ∪ [1, ∞) which is certainly not all of R.
In both cases, the predicate x 2 ≥ x is true existentially on the given domains
since the truth set is not empty, i.e. there exists an x such that x 2 ≥ x whether
D = {1, 2, 3, 4, 5} or D = R.
The truth set for a. is the set {1} which is nonempty and so existence is true
as claimed.
The truth set for a. is the set {1} which is nonempty and so existence is true
as claimed.
The truth set for b. is the empty set, so the existential statement is false.
The truth set for a. is the set {1} which is nonempty and so existence is true
as claimed.
The truth set for b. is the empty set, so the existential statement is false.
Neither a. nor b. are universally true, of course, on their respective domains.
Formal Informal
2
∀x ∈ R, x ≥ 0 All real numbers have nonnegative squares.
The square of every real number is nonnegative.
Any real number has a nonnegative square.
2
∀x ∈ R, x 6= −1 All real numbers have squares that do not equal −1.
No real number has a square equal to −1.
(Words such as none are or no . . . are mean all are not.)
+ 2
∃m ∈ Z : m = m At least one positive ingeger is equal to its square.
Some positive integer(s) equal their own square.
(Although in English, we may pluralize an existential
statement, in math, we allow the possibility only one exists.)
More examples:
Formal Informal
∀ triangles t All triangles have three sides.
t has three sides.
∀ dogs d, No dogs have wings; or
d does not have wings. All dogs do not have wings.
∃ a program p Some programs are structured.
such that p is structured.
More examples:
Formal Informal
∀ triangles t All triangles have three sides.
t has three sides.
∀ dogs d, No dogs have wings; or
d does not have wings. All dogs do not have wings.
∃ a program p Some programs are structured.
such that p is structured.
It is also possible to place the quantification last, such as
More examples:
Formal Informal
∀ triangles t All triangles have three sides.
t has three sides.
∀ dogs d, No dogs have wings; or
d does not have wings. All dogs do not have wings.
∃ a program p Some programs are structured.
such that p is structured.
It is also possible to place the quantification last, such as
More examples:
Formal Informal
∀ triangles t All triangles have three sides.
t has three sides.
∀ dogs d, No dogs have wings; or
d does not have wings. All dogs do not have wings.
∃ a program p Some programs are structured.
such that p is structured.
It is also possible to place the quantification last, such as
I Q (n): n is a factor of 8.
I R (n): n is a factor of 4.
I S (n): n < 5 and n 6= 3.
where n ∈ Z+ .
I Q (n): n is a factor of 8.
I R (n): n is a factor of 4.
I S (n): n < 5 and n 6= 3.
where n ∈ Z+ .
Solution: The truth set of Q (n) is {1, 2, 4, 8} while R (n) and S (n) both have the
same truth set {1, 2, 4}.
I Q (n): n is a factor of 8.
I R (n): n is a factor of 4.
I S (n): n < 5 and n 6= 3.
where n ∈ Z+ .
Solution: The truth set of Q (n) is {1, 2, 4, 8} while R (n) and S (n) both have the
same truth set {1, 2, 4}.
Then R (n) =⇒ Q (n), and S (n) =⇒ Q (n) while R (n) ⇐⇒ S (n).
Although both statements make reference to the variable x, the variable serves
a different function in each case.
Although both statements make reference to the variable x, the variable serves
a different function in each case.
In each case, the variable is bound by the quantifier that introduces it.
Although both statements make reference to the variable x, the variable serves
a different function in each case.
In each case, the variable is bound by the quantifier that introduces it.
The scope of each variable begins when the quantifier introduces it, and ends
with the end of the statement.
Although both statements make reference to the variable x, the variable serves
a different function in each case.
In each case, the variable is bound by the quantifier that introduces it.
The scope of each variable begins when the quantifier introduces it, and ends
with the end of the statement.
Compare this to local variables in computer programs that are bound by the
function defining it, with a scope restricted to that function.
Although both statements make reference to the variable x, the variable serves
a different function in each case.
In each case, the variable is bound by the quantifier that introduces it.
The scope of each variable begins when the quantifier introduces it, and ends
with the end of the statement.
Compare this to local variables in computer programs that are bound by the
function defining it, with a scope restricted to that function. It is similarly
convenient in mathematics to use and reuse symbols like x.
Example: Consider the statement that there exists an integer n that is both
prime and even.
Example: Consider the statement that there exists an integer n that is both
prime and even.
If P (n) is the predicate that n is prime, and E (n) the predicate that n is even,
we may equivalently write the given statement as
Example: Consider the statement that there exists an integer n that is both
prime and even.
If P (n) is the predicate that n is prime, and E (n) the predicate that n is even,
we may equivalently write the given statement as
Example: Consider the statement that there exists an integer n that is both
prime and even.
If P (n) is the predicate that n is prime, and E (n) the predicate that n is even,
we may equivalently write the given statement as
Example: Consider the statement that there exists an integer n that is both
prime and even.
If P (n) is the predicate that n is prime, and E (n) the predicate that n is even,
we may equivalently write the given statement as
Recall however that any statement, quantified or otherwise, is true if and only if
its negation is false, meaning they must always have opposite truth values.
Recall however that any statement, quantified or otherwise, is true if and only if
its negation is false, meaning they must always have opposite truth values.
What if some, but not all mathematicians wear glasses? Then the two
statements above are both false! So they cannot be negations of each other.
Recall however that any statement, quantified or otherwise, is true if and only if
its negation is false, meaning they must always have opposite truth values.
What if some, but not all mathematicians wear glasses? Then the two
statements above are both false! So they cannot be negations of each other.
Instead, the proper negation of the first statement is
and
∃x ∈ D such that P (x ) negates to ∀x ∈ D , ∼P (x )
where the domain is a set of balls that may or may not be in the bowl.
where the domain is a set of balls that may or may not be in the bowl.
If the bowl is non-empty, then these statements certainly have opposite truth values,
depending on whether one of the balls is blue.
where the domain is a set of balls that may or may not be in the bowl.
If the bowl is non-empty, then these statements certainly have opposite truth values,
depending on whether one of the balls is blue.
Even if the bowl is empty, we want these statements to negate each other, meaning
the second statement is false, and the first one is true.
where the domain is a set of balls that may or may not be in the bowl.
If the bowl is non-empty, then these statements certainly have opposite truth values,
depending on whether one of the balls is blue.
Even if the bowl is empty, we want these statements to negate each other, meaning
the second statement is false, and the first one is true.
That is, the statement “All balls in the bowl are blue” is considered vacuously true or
true by default even if the bowl is empty.
Multiple Quantifiers
Consider the statement
John Theado, PhD Intro to Discrete Structures February 9, 2022 100 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Multiple Quantifiers
Consider the statement
John Theado, PhD Intro to Discrete Structures February 9, 2022 100 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Multiple Quantifiers
Consider the statement
John Theado, PhD Intro to Discrete Structures February 9, 2022 100 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Multiple Quantifiers
Consider the statement
John Theado, PhD Intro to Discrete Structures February 9, 2022 100 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Multiple Quantifiers
Consider the statement
As it turns out, both meanings can be interpreted, but clearly both meanings are not
equivalent. We need to be careful.
John Theado, PhD Intro to Discrete Structures February 9, 2022 100 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Multiple Quantifiers
Consider the statement
As it turns out, both meanings can be interpreted, but clearly both meanings are not
equivalent. We need to be careful.
Let P (x , y ) be the predicate “person x supervises detail y . Then
John Theado, PhD Intro to Discrete Structures February 9, 2022 100 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Multiple Quantifiers
Consider the statement
As it turns out, both meanings can be interpreted, but clearly both meanings are not
equivalent. We need to be careful.
Let P (x , y ) be the predicate “person x supervises detail y . Then
I ∃x such that ∀y , P (x , y ) symbolizes the meaning that one person supervises all
the details.
John Theado, PhD Intro to Discrete Structures February 9, 2022 100 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Multiple Quantifiers
Consider the statement
As it turns out, both meanings can be interpreted, but clearly both meanings are not
equivalent. We need to be careful.
Let P (x , y ) be the predicate “person x supervises detail y . Then
I ∃x such that ∀y , P (x , y ) symbolizes the meaning that one person supervises all
the details.
I ∀y , ∃x such that P (x , y ) symbolizes the meaning that for each detail, there is a
person supervising that detail.
John Theado, PhD Intro to Discrete Structures February 9, 2022 100 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
John Theado, PhD Intro to Discrete Structures February 9, 2022 101 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
The first statement symbolizes that every nonzero real number has a
reciprocal, but the second one symbolizes that some real number has a
product of 1 with every real number.
John Theado, PhD Intro to Discrete Structures February 9, 2022 101 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
The first statement symbolizes that every nonzero real number has a
reciprocal, but the second one symbolizes that some real number has a
product of 1 with every real number.
Recall the definition of the scope of a variable. In the first statement, the scope
of a in the universal statement extends to the existential one while the scope of
the existential statement begins in the middle of the universal one.
John Theado, PhD Intro to Discrete Structures February 9, 2022 101 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
The first statement symbolizes that every nonzero real number has a
reciprocal, but the second one symbolizes that some real number has a
product of 1 with every real number.
Recall the definition of the scope of a variable. In the first statement, the scope
of a in the universal statement extends to the existential one while the scope of
the existential statement begins in the middle of the universal one.
This is why we say, in this case, that the variable b depends on the variable a.
John Theado, PhD Intro to Discrete Structures February 9, 2022 101 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
John Theado, PhD Intro to Discrete Structures February 9, 2022 102 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Negating statements with multiple quantifiers is just an extra step. The statement
∀x , ∃y : P (x , y ) is simply a universal statement using an existental one as a predicate.
John Theado, PhD Intro to Discrete Structures February 9, 2022 102 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Negating statements with multiple quantifiers is just an extra step. The statement
∀x , ∃y : P (x , y ) is simply a universal statement using an existental one as a predicate.
We will find the negation of by simply adding an extra step to negate the inner
quantified statements(s)
John Theado, PhD Intro to Discrete Structures February 9, 2022 102 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Negating statements with multiple quantifiers is just an extra step. The statement
∀x , ∃y : P (x , y ) is simply a universal statement using an existental one as a predicate.
We will find the negation of by simply adding an extra step to negate the inner
quantified statements(s)
John Theado, PhD Intro to Discrete Structures February 9, 2022 102 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Negating statements with multiple quantifiers is just an extra step. The statement
∀x , ∃y : P (x , y ) is simply a universal statement using an existental one as a predicate.
We will find the negation of by simply adding an extra step to negate the inner
quantified statements(s)
John Theado, PhD Intro to Discrete Structures February 9, 2022 102 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Negating statements with multiple quantifiers is just an extra step. The statement
∀x , ∃y : P (x , y ) is simply a universal statement using an existental one as a predicate.
We will find the negation of by simply adding an extra step to negate the inner
quantified statements(s)
John Theado, PhD Intro to Discrete Structures February 9, 2022 102 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Negating statements with multiple quantifiers is just an extra step. The statement
∀x , ∃y : P (x , y ) is simply a universal statement using an existental one as a predicate.
We will find the negation of by simply adding an extra step to negate the inner
quantified statements(s)
negates to
There exists x, such that for all y , not P (x , y )
John Theado, PhD Intro to Discrete Structures February 9, 2022 102 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Negating statements with multiple quantifiers is just an extra step. The statement
∀x , ∃y : P (x , y ) is simply a universal statement using an existental one as a predicate.
We will find the negation of by simply adding an extra step to negate the inner
quantified statements(s)
negates to
There exists x, such that for all y , not P (x , y )
So if it is not the case that every detail x has a supervisor y , then some detail x must
not have any y supervising!
John Theado, PhD Intro to Discrete Structures February 9, 2022 102 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
John Theado, PhD Intro to Discrete Structures February 9, 2022 103 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
John Theado, PhD Intro to Discrete Structures February 9, 2022 104 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
There exists a real number L such that for every real ε > 0, there exists a real
number δ > 0 such that for all real numbers t, if 0 < |x − t | < δ then
|f (t ) − L| < ε .
John Theado, PhD Intro to Discrete Structures February 9, 2022 104 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
There exists a real number L such that for every real ε > 0, there exists a real
number δ > 0 such that for all real numbers t, if 0 < |x − t | < δ then
|f (t ) − L| < ε .
which negates to
John Theado, PhD Intro to Discrete Structures February 9, 2022 104 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
There exists a real number L such that for every real ε > 0, there exists a real
number δ > 0 such that for all real numbers t, if 0 < |x − t | < δ then
|f (t ) − L| < ε .
which negates to
We may read this as For every real number L, there exists an ε > 0 such that
for every real number δ > 0, there exists a real number t such that
0 < |x − t | < δ but |f (t ) − L| ≥ ε .
John Theado, PhD Intro to Discrete Structures February 9, 2022 104 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Mathematical Induction
Recall the Modus Ponens rule of inference.
p→q
p
∴ q
John Theado, PhD Intro to Discrete Structures February 9, 2022 105 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Mathematical Induction
Recall the Modus Ponens rule of inference. We also have a Universal Modus Ponens.
p→q ∀x , P (x ) → Q (x )
p P (a)
∴ q ∴ Q (a).
John Theado, PhD Intro to Discrete Structures February 9, 2022 105 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Mathematical Induction
Recall the Modus Ponens rule of inference. We also have a Universal Modus Ponens.
p→q ∀x , P (x ) → Q (x )
p P (a)
∴ q ∴ Q (a).
We reason the validity as follows, using the rule of universal instantiation: if something
is true for everything in a set, it is true for any particular thing in that set:
John Theado, PhD Intro to Discrete Structures February 9, 2022 105 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Mathematical Induction
Recall the Modus Ponens rule of inference. We also have a Universal Modus Ponens.
p→q ∀x , P (x ) → Q (x )
p P (a)
∴ q ∴ Q (a).
We reason the validity as follows, using the rule of universal instantiation: if something
is true for everything in a set, it is true for any particular thing in that set:
I If the first premise is true, then in particular, P (a) → Q (a) is true for a given a.
John Theado, PhD Intro to Discrete Structures February 9, 2022 105 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Mathematical Induction
Recall the Modus Ponens rule of inference. We also have a Universal Modus Ponens.
p→q ∀x , P (x ) → Q (x )
p P (a)
∴ q ∴ Q (a).
We reason the validity as follows, using the rule of universal instantiation: if something
is true for everything in a set, it is true for any particular thing in that set:
I If the first premise is true, then in particular, P (a) → Q (a) is true for a given a.
I Since P (a) is true, we can infer by Modus Ponens that Q (a) is true.
John Theado, PhD Intro to Discrete Structures February 9, 2022 105 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Mathematical Induction
Recall the Modus Ponens rule of inference. We also have a Universal Modus Ponens.
p→q ∀x , P (x ) → Q (x )
p P (a)
∴ q ∴ Q (a).
We reason the validity as follows, using the rule of universal instantiation: if something
is true for everything in a set, it is true for any particular thing in that set:
I If the first premise is true, then in particular, P (a) → Q (a) is true for a given a.
I Since P (a) is true, we can infer by Modus Ponens that Q (a) is true.
John Theado, PhD Intro to Discrete Structures February 9, 2022 105 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
John Theado, PhD Intro to Discrete Structures February 9, 2022 106 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Consider the predicate P (n) whose domain is the set Z+ of positive integers
and suppose we would like to prove that ∀n ∈ Z+ , P (n).
John Theado, PhD Intro to Discrete Structures February 9, 2022 107 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Consider the predicate P (n) whose domain is the set Z+ of positive integers
and suppose we would like to prove that ∀n ∈ Z+ , P (n).
The following argument form is known as the (weak) principle of
mathematical induction:
P (1)
∀k ∈ Z+ , P (k ) → P (k + 1)
∴ ∀n ∈ Z+ , P (n)
where
John Theado, PhD Intro to Discrete Structures February 9, 2022 107 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Consider the predicate P (n) whose domain is the set Z+ of positive integers
and suppose we would like to prove that ∀n ∈ Z+ , P (n).
The following argument form is known as the (weak) principle of
mathematical induction:
P (1)
∀k ∈ Z+ , P (k ) → P (k + 1)
∴ ∀n ∈ Z+ , P (n)
where
John Theado, PhD Intro to Discrete Structures February 9, 2022 107 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Consider the predicate P (n) whose domain is the set Z+ of positive integers
and suppose we would like to prove that ∀n ∈ Z+ , P (n).
The following argument form is known as the (weak) principle of
mathematical induction:
P (1)
∀k ∈ Z+ , P (k ) → P (k + 1)
∴ ∀n ∈ Z+ , P (n)
where
John Theado, PhD Intro to Discrete Structures February 9, 2022 107 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Consider the predicate P (n) whose domain is the set Z+ of positive integers
and suppose we would like to prove that ∀n ∈ Z+ , P (n).
The following argument form is known as the (weak) principle of
mathematical induction:
P (1)
∀k ∈ Z+ , P (k ) → P (k + 1)
∴ ∀n ∈ Z+ , P (n)
where
John Theado, PhD Intro to Discrete Structures February 9, 2022 107 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Consider the predicate P (n) whose domain is the set Z+ of positive integers
and suppose we would like to prove that ∀n ∈ Z+ , P (n).
The following argument form is known as the (weak) principle of
mathematical induction:
P (1)
∀k ∈ Z+ , P (k ) → P (k + 1)
∴ ∀n ∈ Z+ , P (n)
where
That is, if one can demonstrate P (1) is true, and then demonstrate that P (k )
implies P (k + 1) for every integer k ≥ 1, then P (n) must be true for all integers
n ≥ 1.
John Theado, PhD Intro to Discrete Structures February 9, 2022 107 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
John Theado, PhD Intro to Discrete Structures February 9, 2022 108 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
John Theado, PhD Intro to Discrete Structures February 9, 2022 108 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
John Theado, PhD Intro to Discrete Structures February 9, 2022 108 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
John Theado, PhD Intro to Discrete Structures February 9, 2022 108 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
John Theado, PhD Intro to Discrete Structures February 9, 2022 108 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Exercise: Prove that the sum of the first n positive odd integers is n2 by
John Theado, PhD Intro to Discrete Structures February 9, 2022 108 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Exercise: Prove that the sum of the first n positive odd integers is n2 by
I Showing that the sum of the first positive odd integer (1) equals 12 .
John Theado, PhD Intro to Discrete Structures February 9, 2022 108 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Exercise: Prove that the sum of the first n positive odd integers is n2 by
I Showing that the sum of the first positive odd integer (1) equals 12 .
I Assume as the induction hypothesis that the sum of the first k squares is k 2 , i.e.
1 + 3 + 5 + ... + (2k − 1) = k 2 .
John Theado, PhD Intro to Discrete Structures February 9, 2022 108 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Exercise: Prove that the sum of the first n positive odd integers is n2 by
I Showing that the sum of the first positive odd integer (1) equals 12 .
I Assume as the induction hypothesis that the sum of the first k squares is k 2 , i.e.
1 + 3 + 5 + ... + (2k − 1) = k 2 .
I Show that from this, we get that the sum of the first k + 1 positive integers is
(k + 1)2 , by adding 2(k + 1) − 1 (the (k + 1)th odd number) to both sides, and
factor the right hand side of the equation.
John Theado, PhD Intro to Discrete Structures February 9, 2022 108 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
Exercise: Prove that the sum of the first n positive odd integers is n2 by
I Showing that the sum of the first positive odd integer (1) equals 12 .
I Assume as the induction hypothesis that the sum of the first k squares is k 2 , i.e.
1 + 3 + 5 + ... + (2k − 1) = k 2 .
I Show that from this, we get that the sum of the first k + 1 positive integers is
(k + 1)2 , by adding 2(k + 1) − 1 (the (k + 1)th odd number) to both sides, and
factor the right hand side of the equation.
I Conclude that the statement is true for any n.
John Theado, PhD Intro to Discrete Structures February 9, 2022 108 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
n
n=1: ∑ (2t − 1) = n2
t =1
1 = 1
John Theado, PhD Intro to Discrete Structures February 9, 2022 109 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
n
n=2: ∑ (2t − 1) = n2
t =1
1 + 3 = 4
John Theado, PhD Intro to Discrete Structures February 9, 2022 109 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
n
n=3: ∑ (2t − 1) = n2
t =1
1 + 3 + 5 = 9
John Theado, PhD Intro to Discrete Structures February 9, 2022 109 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
n
n=4: ∑ (2t − 1) = n2
t =1
1 + 3 + 5 + 7 = 16
John Theado, PhD Intro to Discrete Structures February 9, 2022 109 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
n
n=5: ∑ (2t − 1) = n2
t =1
1 + 3 + 5 + 7 + 9 = 25
John Theado, PhD Intro to Discrete Structures February 9, 2022 109 / 157
Chapter 3: The Logic of Quantified Statements Section 1-4: Predicates and Quantified Statements
n
n=6: ∑ (2t − 1) = n2
t =1
1 + 3 + 5 + 7 + 9 + 11 = 36
John Theado, PhD Intro to Discrete Structures February 9, 2022 109 / 157
Chapter 6: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 110 / 157
Chapter 6: Set Theory Section 0: Set Language
John Theado, PhD Intro to Discrete Structures February 9, 2022 111 / 157
Chapter 6: Set Theory Section 0: Set Language
Set Definitions
A set is a well-defined collection of distinct objects called members or elements.
John Theado, PhD Intro to Discrete Structures February 9, 2022 112 / 157
Chapter 6: Set Theory Section 0: Set Language
Set Definitions
A set is a well-defined collection of distinct objects called members or elements.
To be well-defined, membership must not be ambiguous, meaning that an object
either belongs to the set or, exclusively, it does not.
John Theado, PhD Intro to Discrete Structures February 9, 2022 112 / 157
Chapter 6: Set Theory Section 0: Set Language
Set Definitions
A set is a well-defined collection of distinct objects called members or elements.
To be well-defined, membership must not be ambiguous, meaning that an object
either belongs to the set or, exclusively, it does not.
Some common examples of sets of numbers we see in mathematics are:
John Theado, PhD Intro to Discrete Structures February 9, 2022 112 / 157
Chapter 6: Set Theory Section 0: Set Language
Set Definitions
A set is a well-defined collection of distinct objects called members or elements.
To be well-defined, membership must not be ambiguous, meaning that an object
either belongs to the set or, exclusively, it does not.
Some common examples of sets of numbers we see in mathematics are:
John Theado, PhD Intro to Discrete Structures February 9, 2022 112 / 157
Chapter 6: Set Theory Section 0: Set Language
Set Definitions
A set is a well-defined collection of distinct objects called members or elements.
To be well-defined, membership must not be ambiguous, meaning that an object
either belongs to the set or, exclusively, it does not.
Some common examples of sets of numbers we see in mathematics are:
John Theado, PhD Intro to Discrete Structures February 9, 2022 112 / 157
Chapter 6: Set Theory Section 0: Set Language
Set Definitions
A set is a well-defined collection of distinct objects called members or elements.
To be well-defined, membership must not be ambiguous, meaning that an object
either belongs to the set or, exclusively, it does not.
Some common examples of sets of numbers we see in mathematics are:
7
Example: Consider the numbers numbers 5, 22
, π , and the imaginary unit i.
John Theado, PhD Intro to Discrete Structures February 9, 2022 113 / 157
Chapter 6: Set Theory Section 0: Set Language
7
Example: Consider the numbers numbers 5, 22
, π , and the imaginary unit i.
I We can truthfully write 5 ∈ C, 7
∈ C, π ∈ C, and i ∈ C since the set of
22
complex numbers contains all real numbers as well as the imaginary unit.
John Theado, PhD Intro to Discrete Structures February 9, 2022 113 / 157
Chapter 6: Set Theory Section 0: Set Language
7
Example: Consider the numbers numbers 5, 22
, π , and the imaginary unit i.
I We can truthfully write 5 ∈ C, 7
∈ C, π ∈ C, and i ∈ C since the set of
22
complex numbers contains all real numbers as well as the imaginary unit.
I We can also write 5 ∈ R, 7
∈ R and π ∈ R since these are real
22
numbers, but we must write i 6∈ R since it is not a real number.
John Theado, PhD Intro to Discrete Structures February 9, 2022 113 / 157
Chapter 6: Set Theory Section 0: Set Language
7
Example: Consider the numbers numbers 5, 22
, π , and the imaginary unit i.
I We can truthfully write 5 ∈ C, 7
∈ C, π ∈ C, and i ∈ C since the set of
22
complex numbers contains all real numbers as well as the imaginary unit.
I We can also write 5 ∈ R, 7
∈ R and π ∈ R since these are real
22
numbers, but we must write i 6∈ R since it is not a real number.
I Since 5 and 7 7
22
are rational, we can write 5, 22 ∈ Q but π, i 6∈ Q however.
John Theado, PhD Intro to Discrete Structures February 9, 2022 113 / 157
Chapter 6: Set Theory Section 0: Set Language
7
Example: Consider the numbers numbers 5, 22
, π , and the imaginary unit i.
I We can truthfully write 5 ∈ C, 7
∈ C, π ∈ C, and i ∈ C since the set of
22
complex numbers contains all real numbers as well as the imaginary unit.
I We can also write 5 ∈ R, 7
∈ R and π ∈ R since these are real
22
numbers, but we must write i 6∈ R since it is not a real number.
I Since 5 and 22 7 7
are rational, we can write 5, 22 ∈ Q but π, i 6∈ Q however.
I 5 is the only integer in the bunch so 5 ∈ Z but 227
, π, i 6∈ Z.
John Theado, PhD Intro to Discrete Structures February 9, 2022 113 / 157
Chapter 6: Set Theory Section 0: Set Language
7
Example: Consider the numbers numbers 5, 22
, π , and the imaginary unit i.
I We can truthfully write 5 ∈ C, 7
∈ C, π ∈ C, and i ∈ C since the set of
22
complex numbers contains all real numbers as well as the imaginary unit.
I We can also write 5 ∈ R, 7
∈ R and π ∈ R since these are real
22
numbers, but we must write i 6∈ R since it is not a real number.
I Since 5 and 22 7 7
are rational, we can write 5, 22 ∈ Q but π, i 6∈ Q however.
I 5 is the only integer in the bunch so 5 ∈ Z but 227
, π, i 6∈ Z.
John Theado, PhD Intro to Discrete Structures February 9, 2022 113 / 157
Chapter 6: Set Theory Section 0: Set Language
7
Example: Consider the numbers numbers 5, 22
, π , and the imaginary unit i.
I We can truthfully write 5 ∈ C, 7
∈ C, π ∈ C, and i ∈ C since the set of
22
complex numbers contains all real numbers as well as the imaginary unit.
I We can also write 5 ∈ R, 7
∈ R and π ∈ R since these are real
22
numbers, but we must write i 6∈ R since it is not a real number.
I Since 5 and 22 7 7
are rational, we can write 5, 22 ∈ Q but π, i 6∈ Q however.
I 5 is the only integer in the bunch so 5 ∈ Z but 227
, π, i 6∈ Z.
Z ⊆ Q ⊆ R ⊆ C.
John Theado, PhD Intro to Discrete Structures February 9, 2022 113 / 157
Chapter 6: Set Theory Section 0: Set Language
7
Example: Consider the numbers numbers 5, 22
, π , and the imaginary unit i.
I We can truthfully write 5 ∈ C, 7
∈ C, π ∈ C, and i ∈ C since the set of
22
complex numbers contains all real numbers as well as the imaginary unit.
I We can also write 5 ∈ R, 7
∈ R and π ∈ R since these are real
22
numbers, but we must write i 6∈ R since it is not a real number.
I Since 5 and 22 7 7
are rational, we can write 5, 22 ∈ Q but π, i 6∈ Q however.
I 5 is the only integer in the bunch so 5 ∈ Z but 227
, π, i 6∈ Z.
Z ⊆ Q ⊆ R ⊆ C.
John Theado, PhD Intro to Discrete Structures February 9, 2022 113 / 157
Chapter 6: Set Theory Section 0: Set Language
We can introduce sets with a description, e.g. let S be the set of students in this class.
John Theado, PhD Intro to Discrete Structures February 9, 2022 114 / 157
Chapter 6: Set Theory Section 0: Set Language
We can introduce sets with a description, e.g. let S be the set of students in this class.
We can use set-roster or more simply roster notation to list the elements of a set: let
A = {x , y , z } for example.
John Theado, PhD Intro to Discrete Structures February 9, 2022 114 / 157
Chapter 6: Set Theory Section 0: Set Language
We can introduce sets with a description, e.g. let S be the set of students in this class.
We can use set-roster or more simply roster notation to list the elements of a set: let
A = {x , y , z } for example.
We may use ellipsis to avoid having to list every element, such as the set
E = {2, 4, 6, 8, . . .} to mean the set of positive even integers or
A = {1, 2, 3, . . . , 99, 100} to mean the first one hundred positive integers.
John Theado, PhD Intro to Discrete Structures February 9, 2022 114 / 157
Chapter 6: Set Theory Section 0: Set Language
We can introduce sets with a description, e.g. let S be the set of students in this class.
We can use set-roster or more simply roster notation to list the elements of a set: let
A = {x , y , z } for example.
We may use ellipsis to avoid having to list every element, such as the set
E = {2, 4, 6, 8, . . .} to mean the set of positive even integers or
A = {1, 2, 3, . . . , 99, 100} to mean the first one hundred positive integers.
However, this can be ambiguous unless there is a clear pattern, so we may use
set-builder notation instead, such as with
John Theado, PhD Intro to Discrete Structures February 9, 2022 114 / 157
Chapter 6: Set Theory Section 0: Set Language
We can introduce sets with a description, e.g. let S be the set of students in this class.
We can use set-roster or more simply roster notation to list the elements of a set: let
A = {x , y , z } for example.
We may use ellipsis to avoid having to list every element, such as the set
E = {2, 4, 6, 8, . . .} to mean the set of positive even integers or
A = {1, 2, 3, . . . , 99, 100} to mean the first one hundred positive integers.
However, this can be ambiguous unless there is a clear pattern, so we may use
set-builder notation instead, such as with
John Theado, PhD Intro to Discrete Structures February 9, 2022 114 / 157
Chapter 6: Set Theory Section 0: Set Language
We can introduce sets with a description, e.g. let S be the set of students in this class.
We can use set-roster or more simply roster notation to list the elements of a set: let
A = {x , y , z } for example.
We may use ellipsis to avoid having to list every element, such as the set
E = {2, 4, 6, 8, . . .} to mean the set of positive even integers or
A = {1, 2, 3, . . . , 99, 100} to mean the first one hundred positive integers.
However, this can be ambiguous unless there is a clear pattern, so we may use
set-builder notation instead, such as with
Examples:
John Theado, PhD Intro to Discrete Structures February 9, 2022 115 / 157
Chapter 6: Set Theory Section 0: Set Language
Examples:
John Theado, PhD Intro to Discrete Structures February 9, 2022 115 / 157
Chapter 6: Set Theory Section 0: Set Language
Examples:
John Theado, PhD Intro to Discrete Structures February 9, 2022 115 / 157
Chapter 6: Set Theory Section 0: Set Language
Examples:
[0, 1) = {x ∈ R : 0 ≤ x < 1}
John Theado, PhD Intro to Discrete Structures February 9, 2022 115 / 157
Chapter 6: Set Theory Section 0: Set Language
A = B ⇐⇒ A ⊆ B and B ⊆ A.
John Theado, PhD Intro to Discrete Structures February 9, 2022 116 / 157
Chapter 6: Set Theory Section 0: Set Language
A = B ⇐⇒ A ⊆ B and B ⊆ A.
John Theado, PhD Intro to Discrete Structures February 9, 2022 116 / 157
Chapter 6: Set Theory Section 0: Set Language
A = B ⇐⇒ A ⊆ B and B ⊆ A.
John Theado, PhD Intro to Discrete Structures February 9, 2022 116 / 157
Chapter 6: Set Theory Section 0: Set Language
Cartesian Product
Given elements a and b, the symbol (a, b) denotes the ordered pair
consisting of a and b together with the specification that a is the first element
and b is the second element.
John Theado, PhD Intro to Discrete Structures February 9, 2022 117 / 157
Chapter 6: Set Theory Section 0: Set Language
Cartesian Product
Given elements a and b, the symbol (a, b) denotes the ordered pair
consisting of a and b together with the specification that a is the first element
and b is the second element.
Two ordered pairs (a, b) and (c , d ) are equal if and only if a = c and b = d, i.e.
(a, b) = (c , d ) ⇐⇒ a = c and b = d
John Theado, PhD Intro to Discrete Structures February 9, 2022 117 / 157
Chapter 6: Set Theory Section 0: Set Language
Cartesian Product
Given elements a and b, the symbol (a, b) denotes the ordered pair
consisting of a and b together with the specification that a is the first element
and b is the second element.
Two ordered pairs (a, b) and (c , d ) are equal if and only if a = c and b = d, i.e.
(a, b) = (c , d ) ⇐⇒ a = c and b = d
Let A and B be sets. The Cartesian product of A and B is an entirely new set
A × B consisting of all ordered pairs (a, b) such that a ∈ A and b ∈ B, i.e.
A × B = {(a, b) : a ∈ A and b ∈ B }
John Theado, PhD Intro to Discrete Structures February 9, 2022 117 / 157
Chapter 6: Set Theory Section 0: Set Language
Cartesian Product
Given elements a and b, the symbol (a, b) denotes the ordered pair
consisting of a and b together with the specification that a is the first element
and b is the second element.
Two ordered pairs (a, b) and (c , d ) are equal if and only if a = c and b = d, i.e.
(a, b) = (c , d ) ⇐⇒ a = c and b = d
Let A and B be sets. The Cartesian product of A and B is an entirely new set
A × B consisting of all ordered pairs (a, b) such that a ∈ A and b ∈ B, i.e.
A × B = {(a, b) : a ∈ A and b ∈ B }
Remark: The set A × B is entirely different from both A and B and formally,
neither A or B are subsets of A × B or belong to the same universal set.
John Theado, PhD Intro to Discrete Structures February 9, 2022 117 / 157
Chapter 6: Set Theory Section 0: Set Language
John Theado, PhD Intro to Discrete Structures February 9, 2022 118 / 157
Chapter 6: Set Theory Section 0: Set Language
John Theado, PhD Intro to Discrete Structures February 9, 2022 118 / 157
Chapter 6: Set Theory Section 0: Set Language
This is the set of all points in the xy-plane that lie on the unit circle.
John Theado, PhD Intro to Discrete Structures February 9, 2022 118 / 157
Chapter 6: Set Theory Section 0: Set Language
This is the set of all points in the xy-plane that lie on the unit circle.
A real-valued function f (x ) of a real variable may be defined as as subset of
R × R where
f = {(x , y ) ∈ R × R : y = f (x )} .
John Theado, PhD Intro to Discrete Structures February 9, 2022 118 / 157
Chapter 6: Set Theory Section 0: Set Language
This is the set of all points in the xy-plane that lie on the unit circle.
A real-valued function f (x ) of a real variable may be defined as as subset of
R × R where
f = {(x , y ) ∈ R × R : y = f (x )} .
John Theado, PhD Intro to Discrete Structures February 9, 2022 118 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 119 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Venn Diagrams
Venn diagrams, named for British mathematician John Venn, are used to present
relations among sets.
John Theado, PhD Intro to Discrete Structures February 9, 2022 120 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Venn Diagrams
Venn diagrams, named for British mathematician John Venn, are used to present
relations among sets.
If A ⊆ B, we could have
A B A=B
John Theado, PhD Intro to Discrete Structures February 9, 2022 120 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Venn Diagrams
Venn diagrams, named for British mathematician John Venn, are used to present
relations among sets.
If A ⊆ B, we could have
A B A=B
If A 6⊆ B we could have
A
A B A B
B
John Theado, PhD Intro to Discrete Structures February 9, 2022 120 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Z Q R
John Theado, PhD Intro to Discrete Structures February 9, 2022 121 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Set Operations
John Theado, PhD Intro to Discrete Structures February 9, 2022 122 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Set Operations
John Theado, PhD Intro to Discrete Structures February 9, 2022 122 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Set Operations
John Theado, PhD Intro to Discrete Structures February 9, 2022 122 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Set Operations
John Theado, PhD Intro to Discrete Structures February 9, 2022 122 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Often, we would like to consider sets that are contained within (i.e. subsets of)
some larger set, such as the set of real numbers R, the set of integers Z, or
any other set of interest.
John Theado, PhD Intro to Discrete Structures February 9, 2022 123 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Often, we would like to consider sets that are contained within (i.e. subsets of)
some larger set, such as the set of real numbers R, the set of integers Z, or
any other set of interest.
We call such a set of interest the universal set or universe, and often
introduce the set as U or U.
John Theado, PhD Intro to Discrete Structures February 9, 2022 123 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Often, we would like to consider sets that are contained within (i.e. subsets of)
some larger set, such as the set of real numbers R, the set of integers Z, or
any other set of interest.
We call such a set of interest the universal set or universe, and often
introduce the set as U or U.
If A is contained in some universe U , we call the set U − A, denoted as Ac , the
complement of A in U , and it contains all those members of U not in A.
John Theado, PhD Intro to Discrete Structures February 9, 2022 123 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A B
John Theado, PhD Intro to Discrete Structures February 9, 2022 124 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A B
A∪B
John Theado, PhD Intro to Discrete Structures February 9, 2022 124 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A B
A∩B
John Theado, PhD Intro to Discrete Structures February 9, 2022 124 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A B
A−B
John Theado, PhD Intro to Discrete Structures February 9, 2022 124 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A B
B−A
John Theado, PhD Intro to Discrete Structures February 9, 2022 124 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A B
Ac
John Theado, PhD Intro to Discrete Structures February 9, 2022 124 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A B
Bc
John Theado, PhD Intro to Discrete Structures February 9, 2022 124 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 125 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A ∪ B = {a, c , d , e, f , g }
John Theado, PhD Intro to Discrete Structures February 9, 2022 125 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A ∪ B = {a, c , d , e, f , g } A ∩ B = {e , g }
John Theado, PhD Intro to Discrete Structures February 9, 2022 125 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A ∪ B = {a, c , d , e, f , g } A ∩ B = {e , g }
A − B = {a, c }
John Theado, PhD Intro to Discrete Structures February 9, 2022 125 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A ∪ B = {a, c , d , e, f , g } A ∩ B = {e , g }
A − B = {a, c } B − A = {d , f }
John Theado, PhD Intro to Discrete Structures February 9, 2022 125 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A ∪ B = {a, c , d , e, f , g } A ∩ B = {e , g }
A − B = {a, c } B − A = {d , f }
c
A = {b, d , f }
John Theado, PhD Intro to Discrete Structures February 9, 2022 125 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A ∪ B = {a, c , d , e, f , g } A ∩ B = {e , g }
A − B = {a, c } B − A = {d , f }
c
A = {b, d , f } B c = {a , b , c }
John Theado, PhD Intro to Discrete Structures February 9, 2022 125 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A ∪ B = {a, c , d , e, f , g } A ∩ B = {e , g }
A − B = {a, c } B − A = {d , f }
c
A = {b, d , f } B c = {a , b , c }
U
A B
a e d
c g f
John Theado, PhD Intro to Discrete Structures February 9, 2022 125 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A ∪ B = {a, c , d , e, f , g } A ∩ B = {e , g }
A − B = {a, c } B − A = {d , f }
c
A = {b, d , f } B c = {a , b , c }
U
A B
a e d
c g f
A∪B
John Theado, PhD Intro to Discrete Structures February 9, 2022 125 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A ∪ B = {a, c , d , e, f , g } A ∩ B = {e , g }
A − B = {a, c } B − A = {d , f }
c
A = {b, d , f } B c = {a , b , c }
U
A B
a e d
c g f
A∩B
John Theado, PhD Intro to Discrete Structures February 9, 2022 125 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A ∪ B = {a, c , d , e, f , g } A ∩ B = {e , g }
A − B = {a, c } B − A = {d , f }
c
A = {b, d , f } B c = {a , b , c }
U
A B
a e d
c g f
A−B
John Theado, PhD Intro to Discrete Structures February 9, 2022 125 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A ∪ B = {a, c , d , e, f , g } A ∩ B = {e , g }
A − B = {a, c } B − A = {d , f }
c
A = {b, d , f } B c = {a , b , c }
U
A B
a e d
c g f
B−A
John Theado, PhD Intro to Discrete Structures February 9, 2022 125 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A ∪ B = {a, c , d , e, f , g } A ∩ B = {e , g }
A − B = {a, c } B − A = {d , f }
c
A = {b, d , f } B c = {a , b , c }
U
A B
a e d
c g f
Ac
John Theado, PhD Intro to Discrete Structures February 9, 2022 125 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A ∪ B = {a, c , d , e, f , g } A ∩ B = {e , g }
A − B = {a, c } B − A = {d , f }
c
A = {b, d , f } B c = {a , b , c }
U
A B
a e d
c g f
Bc
John Theado, PhD Intro to Discrete Structures February 9, 2022 125 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Interval Notation
Let R be the universal set. Then intervals are subsets of R where for a < b
we have
John Theado, PhD Intro to Discrete Structures February 9, 2022 126 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Interval Notation
Let R be the universal set. Then intervals are subsets of R where for a < b
we have
John Theado, PhD Intro to Discrete Structures February 9, 2022 126 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Interval Notation
Let R be the universal set. Then intervals are subsets of R where for a < b
we have
John Theado, PhD Intro to Discrete Structures February 9, 2022 126 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Interval Notation
Let R be the universal set. Then intervals are subsets of R where for a < b
we have
John Theado, PhD Intro to Discrete Structures February 9, 2022 126 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Interval Notation
Let R be the universal set. Then intervals are subsets of R where for a < b
we have
John Theado, PhD Intro to Discrete Structures February 9, 2022 126 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Interval Notation
Let R be the universal set. Then intervals are subsets of R where for a < b
we have
John Theado, PhD Intro to Discrete Structures February 9, 2022 126 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Interval Notation
Let R be the universal set. Then intervals are subsets of R where for a < b
we have
(a, ∞) = {x ∈ R : x > a}
John Theado, PhD Intro to Discrete Structures February 9, 2022 126 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Interval Notation
Let R be the universal set. Then intervals are subsets of R where for a < b
we have
John Theado, PhD Intro to Discrete Structures February 9, 2022 126 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Interval Notation
Let R be the universal set. Then intervals are subsets of R where for a < b
we have
John Theado, PhD Intro to Discrete Structures February 9, 2022 126 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Interval Notation
Let R be the universal set. Then intervals are subsets of R where for a < b
we have
John Theado, PhD Intro to Discrete Structures February 9, 2022 126 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Find A ∪ B, A ∩ B, B − A, and Ac .
John Theado, PhD Intro to Discrete Structures February 9, 2022 127 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Find A ∪ B, A ∩ B, B − A, and Ac .
Solution:
John Theado, PhD Intro to Discrete Structures February 9, 2022 127 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Find A ∪ B, A ∩ B, B − A, and Ac .
John Theado, PhD Intro to Discrete Structures February 9, 2022 127 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Find A ∪ B, A ∩ B, B − A, and Ac .
John Theado, PhD Intro to Discrete Structures February 9, 2022 127 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Find A ∪ B, A ∩ B, B − A, and Ac .
John Theado, PhD Intro to Discrete Structures February 9, 2022 127 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Find A ∪ B, A ∩ B, B − A, and Ac .
John Theado, PhD Intro to Discrete Structures February 9, 2022 127 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Find A ∪ B, A ∩ B, B − A, and Ac .
John Theado, PhD Intro to Discrete Structures February 9, 2022 127 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Find A ∪ B, A ∩ B, B − A, and Ac .
John Theado, PhD Intro to Discrete Structures February 9, 2022 127 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Find A ∪ B, A ∩ B, B − A, and Ac .
John Theado, PhD Intro to Discrete Structures February 9, 2022 127 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Find A ∪ B, A ∩ B, B − A, and Ac .
John Theado, PhD Intro to Discrete Structures February 9, 2022 127 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Find A ∪ B, A ∩ B, B − A, and Ac .
John Theado, PhD Intro to Discrete Structures February 9, 2022 127 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Find A ∪ B, A ∩ B, B − A, and Ac .
John Theado, PhD Intro to Discrete Structures February 9, 2022 127 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Find A ∪ B, A ∩ B, B − A, and Ac .
John Theado, PhD Intro to Discrete Structures February 9, 2022 127 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Find A ∪ B, A ∩ B, B − A, and Ac .
John Theado, PhD Intro to Discrete Structures February 9, 2022 127 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
The empty set or null set, denoted as 0/ , is a set that contains no elements.
John Theado, PhD Intro to Discrete Structures February 9, 2022 128 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
The empty set or null set, denoted as 0/ , is a set that contains no elements.
A set could be empty because it is defined with a property that does not apply
to any element, or as the intersection of sets with no common elements.
John Theado, PhD Intro to Discrete Structures February 9, 2022 128 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
The empty set or null set, denoted as 0/ , is a set that contains no elements.
A set could be empty because it is defined with a property that does not apply
to any element, or as the intersection of sets with no common elements.
Examples: The following sets are equal to the empty set
John Theado, PhD Intro to Discrete Structures February 9, 2022 128 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
The empty set or null set, denoted as 0/ , is a set that contains no elements.
A set could be empty because it is defined with a property that does not apply
to any element, or as the intersection of sets with no common elements.
Examples: The following sets are equal to the empty set
John Theado, PhD Intro to Discrete Structures February 9, 2022 128 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
The empty set or null set, denoted as 0/ , is a set that contains no elements.
A set could be empty because it is defined with a property that does not apply
to any element, or as the intersection of sets with no common elements.
Examples: The following sets are equal to the empty set
John Theado, PhD Intro to Discrete Structures February 9, 2022 128 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
The empty set or null set, denoted as 0/ , is a set that contains no elements.
A set could be empty because it is defined with a property that does not apply
to any element, or as the intersection of sets with no common elements.
Examples: The following sets are equal to the empty set
John Theado, PhD Intro to Discrete Structures February 9, 2022 128 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
The empty set or null set, denoted as 0/ , is a set that contains no elements.
A set could be empty because it is defined with a property that does not apply
to any element, or as the intersection of sets with no common elements.
Examples: The following sets are equal to the empty set
John Theado, PhD Intro to Discrete Structures February 9, 2022 128 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
∀x , if x ∈ A then x ∈ B .
John Theado, PhD Intro to Discrete Structures February 9, 2022 129 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
∀x , if x ∈ A then x ∈ B .
John Theado, PhD Intro to Discrete Structures February 9, 2022 129 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
∀x , if x ∈ A then x ∈ B .
John Theado, PhD Intro to Discrete Structures February 9, 2022 129 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
∀x , if x ∈ A then x ∈ B .
John Theado, PhD Intro to Discrete Structures February 9, 2022 129 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
∀x , if x ∈ A then x ∈ B .
John Theado, PhD Intro to Discrete Structures February 9, 2022 129 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A = {m ∈ Z : m = 6r + 12 for some r ∈ Z}
B = {n ∈ Z : n = 3s for some s ∈ Z}
John Theado, PhD Intro to Discrete Structures February 9, 2022 130 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A = {m ∈ Z : m = 6r + 12 for some r ∈ Z}
B = {n ∈ Z : n = 3s for some s ∈ Z}
Proof:
I First, suppose x ∈ A.
John Theado, PhD Intro to Discrete Structures February 9, 2022 130 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A = {m ∈ Z : m = 6r + 12 for some r ∈ Z}
B = {n ∈ Z : n = 3s for some s ∈ Z}
Proof:
I First, suppose x ∈ A.
I Since x ∈ A, we have that x = 6r + 12 for some r ∈ Z, by definition of A.
John Theado, PhD Intro to Discrete Structures February 9, 2022 130 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A = {m ∈ Z : m = 6r + 12 for some r ∈ Z}
B = {n ∈ Z : n = 3s for some s ∈ Z}
Proof:
I First, suppose x ∈ A.
I Since x ∈ A, we have that x = 6r + 12 for some r ∈ Z, by definition of A.
I In furtherance of our goal, we can factor 6r + 12 as 3(2r + 4).
John Theado, PhD Intro to Discrete Structures February 9, 2022 130 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A = {m ∈ Z : m = 6r + 12 for some r ∈ Z}
B = {n ∈ Z : n = 3s for some s ∈ Z}
Proof:
I First, suppose x ∈ A.
I Since x ∈ A, we have that x = 6r + 12 for some r ∈ Z, by definition of A.
I In furtherance of our goal, we can factor 6r + 12 as 3(2r + 4).
I To demonstrate this is in the form for something in B, let s = 2r + 4.
John Theado, PhD Intro to Discrete Structures February 9, 2022 130 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A = {m ∈ Z : m = 6r + 12 for some r ∈ Z}
B = {n ∈ Z : n = 3s for some s ∈ Z}
Proof:
I First, suppose x ∈ A.
I Since x ∈ A, we have that x = 6r + 12 for some r ∈ Z, by definition of A.
I In furtherance of our goal, we can factor 6r + 12 as 3(2r + 4).
I To demonstrate this is in the form for something in B, let s = 2r + 4.
I Then s ∈ Z since r ∈ Z.
John Theado, PhD Intro to Discrete Structures February 9, 2022 130 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A = {m ∈ Z : m = 6r + 12 for some r ∈ Z}
B = {n ∈ Z : n = 3s for some s ∈ Z}
Proof:
I First, suppose x ∈ A.
I Since x ∈ A, we have that x = 6r + 12 for some r ∈ Z, by definition of A.
I In furtherance of our goal, we can factor 6r + 12 as 3(2r + 4).
I To demonstrate this is in the form for something in B, let s = 2r + 4.
I Then s ∈ Z since r ∈ Z.
I Thus, 3s = 3(2r + 4) = 6r + 12 = x.
John Theado, PhD Intro to Discrete Structures February 9, 2022 130 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A = {m ∈ Z : m = 6r + 12 for some r ∈ Z}
B = {n ∈ Z : n = 3s for some s ∈ Z}
Proof:
I First, suppose x ∈ A.
I Since x ∈ A, we have that x = 6r + 12 for some r ∈ Z, by definition of A.
I In furtherance of our goal, we can factor 6r + 12 as 3(2r + 4).
I To demonstrate this is in the form for something in B, let s = 2r + 4.
I Then s ∈ Z since r ∈ Z.
I Thus, 3s = 3(2r + 4) = 6r + 12 = x.
I By definition of B, 3s = x is in B as desired.
John Theado, PhD Intro to Discrete Structures February 9, 2022 130 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A = {m ∈ Z : m = 6r + 12 for some r ∈ Z}
B = {n ∈ Z : n = 3s for some s ∈ Z}
Proof:
I First, suppose x ∈ A.
I Since x ∈ A, we have that x = 6r + 12 for some r ∈ Z, by definition of A.
I In furtherance of our goal, we can factor 6r + 12 as 3(2r + 4).
I To demonstrate this is in the form for something in B, let s = 2r + 4.
I Then s ∈ Z since r ∈ Z.
I Thus, 3s = 3(2r + 4) = 6r + 12 = x.
I By definition of B, 3s = x is in B as desired.
I Therefore, A ⊆ B.
John Theado, PhD Intro to Discrete Structures February 9, 2022 130 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A = {m ∈ Z : m = 6r + 12 for some r ∈ Z}
B = {n ∈ Z : n = 3s for some s ∈ Z}
John Theado, PhD Intro to Discrete Structures February 9, 2022 131 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A = {m ∈ Z : m = 6r + 12 for some r ∈ Z}
B = {n ∈ Z : n = 3s for some s ∈ Z}
John Theado, PhD Intro to Discrete Structures February 9, 2022 131 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A = {m ∈ Z : m = 6r + 12 for some r ∈ Z}
B = {n ∈ Z : n = 3s for some s ∈ Z}
6r + 12 = 3
=⇒ 6r = −9
−9 −3
=⇒ r= = .
6 2
John Theado, PhD Intro to Discrete Structures February 9, 2022 131 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A = B ⇐⇒ A ⊆ B and B ⊆ A.
John Theado, PhD Intro to Discrete Structures February 9, 2022 132 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A = B ⇐⇒ A ⊆ B and B ⊆ A.
Proving that two sets A and B are equal then requires proving that A is a
subset of B and B is a subset of A.
John Theado, PhD Intro to Discrete Structures February 9, 2022 132 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A = B ⇐⇒ A ⊆ B and B ⊆ A.
Proving that two sets A and B are equal then requires proving that A is a
subset of B and B is a subset of A.
Question: Consider the sets
Is A = B?
John Theado, PhD Intro to Discrete Structures February 9, 2022 132 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A = B ⇐⇒ A ⊆ B and B ⊆ A.
Proving that two sets A and B are equal then requires proving that A is a
subset of B and B is a subset of A.
Question: Consider the sets
Is A = B?
Answer: Yes.
Exercise: Show this is true by showing A ⊆ B and B ⊆ A where each direction
is done as in the previous example.
John Theado, PhD Intro to Discrete Structures February 9, 2022 132 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A B
John Theado, PhD Intro to Discrete Structures February 9, 2022 133 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
U (a) A ∪ B = B ∪ A and
A B
John Theado, PhD Intro to Discrete Structures February 9, 2022 133 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
U (a) A ∪ B = B ∪ A and A ∩ B = B ∩ A
A B
John Theado, PhD Intro to Discrete Structures February 9, 2022 133 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
U (a) A ∪ B = B ∪ A and A ∩ B = B ∩ A
(b) (A ∪ B ) ∪ C = A ∪ (B ∪ C ) and
A B
John Theado, PhD Intro to Discrete Structures February 9, 2022 133 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
U (a) A ∪ B = B ∪ A and A ∩ B = B ∩ A
(b) (A ∪ B ) ∪ C = A ∪ (B ∪ C ) and
(A ∩ B ) ∩ C = A ∩ (B ∩ C )
A B
John Theado, PhD Intro to Discrete Structures February 9, 2022 133 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
U (a) A ∪ B = B ∪ A and A ∩ B = B ∩ A
(b) (A ∪ B ) ∪ C = A ∪ (B ∪ C ) and
(A ∩ B ) ∩ C = A ∩ (B ∩ C )
A B
(c) A ∪ (B ∩ C ) = (A ∪ B ) ∩ (A ∪ C ) and
John Theado, PhD Intro to Discrete Structures February 9, 2022 133 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
U (a) A ∪ B = B ∪ A and A ∩ B = B ∩ A
(b) (A ∪ B ) ∪ C = A ∪ (B ∪ C ) and
(A ∩ B ) ∩ C = A ∩ (B ∩ C )
A B
(c) A ∪ (B ∩ C ) = (A ∪ B ) ∩ (A ∪ C ) and
A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C )
John Theado, PhD Intro to Discrete Structures February 9, 2022 133 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
U (a) A ∪ B = B ∪ A and A ∩ B = B ∩ A
(b) (A ∪ B ) ∪ C = A ∪ (B ∪ C ) and
(A ∩ B ) ∩ C = A ∩ (B ∩ C )
A B
(c) A ∪ (B ∩ C ) = (A ∪ B ) ∩ (A ∪ C ) and
A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C )
(d) A ∪ U = U
John Theado, PhD Intro to Discrete Structures February 9, 2022 133 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
U (a) A ∪ B = B ∪ A and A ∩ B = B ∩ A
(b) (A ∪ B ) ∪ C = A ∪ (B ∪ C ) and
(A ∩ B ) ∩ C = A ∩ (B ∩ C )
A B
(c) A ∪ (B ∩ C ) = (A ∪ B ) ∩ (A ∪ C ) and
A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C )
(d) A ∪ U = U (e) A ∩ 0/ = 0/
John Theado, PhD Intro to Discrete Structures February 9, 2022 133 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
U (a) A ∪ B = B ∪ A and A ∩ B = B ∩ A
(b) (A ∪ B ) ∪ C = A ∪ (B ∪ C ) and
(A ∩ B ) ∩ C = A ∩ (B ∩ C )
A B
(c) A ∪ (B ∩ C ) = (A ∪ B ) ∩ (A ∪ C ) and
A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C )
(d) A ∪ U = U (e) A ∩ 0/ = 0/
(f) A ∪ 0/ = A
John Theado, PhD Intro to Discrete Structures February 9, 2022 133 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
U (a) A ∪ B = B ∪ A and A ∩ B = B ∩ A
(b) (A ∪ B ) ∪ C = A ∪ (B ∪ C ) and
(A ∩ B ) ∩ C = A ∩ (B ∩ C )
A B
(c) A ∪ (B ∩ C ) = (A ∪ B ) ∩ (A ∪ C ) and
A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C )
(d) A ∪ U = U (e) A ∩ 0/ = 0/
(f) A ∪ 0/ = A (g) A ∩ U = A
John Theado, PhD Intro to Discrete Structures February 9, 2022 133 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
U (a) A ∪ B = B ∪ A and A ∩ B = B ∩ A
(b) (A ∪ B ) ∪ C = A ∪ (B ∪ C ) and
(A ∩ B ) ∩ C = A ∩ (B ∩ C )
A B
(c) A ∪ (B ∩ C ) = (A ∪ B ) ∩ (A ∪ C ) and
A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C )
(d) A ∪ U = U (e) A ∩ 0/ = 0/
(f) A ∪ 0/ = A (g) A ∩ U = A
(h) A ∪ A = A
C
John Theado, PhD Intro to Discrete Structures February 9, 2022 133 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
U (a) A ∪ B = B ∪ A and A ∩ B = B ∩ A
(b) (A ∪ B ) ∪ C = A ∪ (B ∪ C ) and
(A ∩ B ) ∩ C = A ∩ (B ∩ C )
A B
(c) A ∪ (B ∩ C ) = (A ∪ B ) ∩ (A ∪ C ) and
A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C )
(d) A ∪ U = U (e) A ∩ 0/ = 0/
(f) A ∪ 0/ = A (g) A ∩ U = A
(h) A ∪ A = A (i) A ∩ A = A
C
John Theado, PhD Intro to Discrete Structures February 9, 2022 133 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
U (a) A ∪ B = B ∪ A and A ∩ B = B ∩ A
(b) (A ∪ B ) ∪ C = A ∪ (B ∪ C ) and
(A ∩ B ) ∩ C = A ∩ (B ∩ C )
A B
(c) A ∪ (B ∩ C ) = (A ∪ B ) ∩ (A ∪ C ) and
A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C )
John Theado, PhD Intro to Discrete Structures February 9, 2022 133 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
U (a) A ∪ B = B ∪ A and A ∩ B = B ∩ A
(b) (A ∪ B ) ∪ C = A ∪ (B ∪ C ) and
(A ∩ B ) ∩ C = A ∩ (B ∩ C )
A B
(c) A ∪ (B ∩ C ) = (A ∪ B ) ∩ (A ∪ C ) and
A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C )
John Theado, PhD Intro to Discrete Structures February 9, 2022 133 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
U (a) A ∪ B = B ∪ A and A ∩ B = B ∩ A
(b) (A ∪ B ) ∪ C = A ∪ (B ∪ C ) and
(A ∩ B ) ∩ C = A ∩ (B ∩ C )
A B
(c) A ∪ (B ∩ C ) = (A ∪ B ) ∩ (A ∪ C ) and
A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C )
(l) A ∪ (A ∩ B ) = A
John Theado, PhD Intro to Discrete Structures February 9, 2022 133 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
U (a) A ∪ B = B ∪ A and A ∩ B = B ∩ A
(b) (A ∪ B ) ∪ C = A ∪ (B ∪ C ) and
(A ∩ B ) ∩ C = A ∩ (B ∩ C )
A B
(c) A ∪ (B ∩ C ) = (A ∪ B ) ∩ (A ∪ C ) and
A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C )
(l) A ∪ (A ∩ B ) = A (m) A ∩ (A ∪ B ) = A
John Theado, PhD Intro to Discrete Structures February 9, 2022 133 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
U (a) A ∪ B = B ∪ A and A ∩ B = B ∩ A
(b) (A ∪ B ) ∪ C = A ∪ (B ∪ C ) and
(A ∩ B ) ∩ C = A ∩ (B ∩ C )
A B
(c) A ∪ (B ∩ C ) = (A ∪ B ) ∩ (A ∪ C ) and
A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C )
(l) A ∪ (A ∩ B ) = A (m) A ∩ (A ∪ B ) = A
(n) U c = 0/
John Theado, PhD Intro to Discrete Structures February 9, 2022 133 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
U (a) A ∪ B = B ∪ A and A ∩ B = B ∩ A
(b) (A ∪ B ) ∪ C = A ∪ (B ∪ C ) and
(A ∩ B ) ∩ C = A ∩ (B ∩ C )
A B
(c) A ∪ (B ∩ C ) = (A ∪ B ) ∩ (A ∪ C ) and
A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C )
(l) A ∪ (A ∩ B ) = A (m) A ∩ (A ∪ B ) = A
(n) U c = 0/ (o) 0/ c = U
John Theado, PhD Intro to Discrete Structures February 9, 2022 133 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
U (a) A ∪ B = B ∪ A and A ∩ B = B ∩ A
(b) (A ∪ B ) ∪ C = A ∪ (B ∪ C ) and
(A ∩ B ) ∩ C = A ∩ (B ∩ C )
A B
(c) A ∪ (B ∩ C ) = (A ∪ B ) ∩ (A ∪ C ) and
A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C )
(l) A ∪ (A ∩ B ) = A (m) A ∩ (A ∪ B ) = A
(n) U c = 0/ (o) 0/ c = U
(p) (Ac )c = A
John Theado, PhD Intro to Discrete Structures February 9, 2022 133 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
U (a) A ∪ B = B ∪ A and A ∩ B = B ∩ A
(b) (A ∪ B ) ∪ C = A ∪ (B ∪ C ) and
(A ∩ B ) ∩ C = A ∩ (B ∩ C )
A B
(c) A ∪ (B ∩ C ) = (A ∪ B ) ∩ (A ∪ C ) and
A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C )
(l) A ∪ (A ∩ B ) = A (m) A ∩ (A ∪ B ) = A
(n) U c = 0/ (o) 0/ c = U
(p) (Ac )c = A (q) A − B = A ∩ B c
John Theado, PhD Intro to Discrete Structures February 9, 2022 133 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 134 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
1. x ∈ A ∪ B ⇐⇒ x ∈ A or x ∈ B
John Theado, PhD Intro to Discrete Structures February 9, 2022 134 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
1. x ∈ A ∪ B ⇐⇒ x ∈ A or x ∈ B
2. x ∈ A ∩ B ⇐⇒ x ∈ A and x ∈ B
John Theado, PhD Intro to Discrete Structures February 9, 2022 134 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
1. x ∈ A ∪ B ⇐⇒ x ∈ A or x ∈ B
2. x ∈ A ∩ B ⇐⇒ x ∈ A and x ∈ B
3. x ∈ A − B ⇐⇒ x ∈ A but x 6∈ B
John Theado, PhD Intro to Discrete Structures February 9, 2022 134 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
1. x ∈ A ∪ B ⇐⇒ x ∈ A or x ∈ B
2. x ∈ A ∩ B ⇐⇒ x ∈ A and x ∈ B
3. x ∈ A − B ⇐⇒ x ∈ A but x 6∈ B
4. x ∈ Ac ⇐⇒ x 6∈ A
John Theado, PhD Intro to Discrete Structures February 9, 2022 134 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
1. x ∈ A ∪ B ⇐⇒ x ∈ A or x ∈ B
2. x ∈ A ∩ B ⇐⇒ x ∈ A and x ∈ B
3. x ∈ A − B ⇐⇒ x ∈ A but x 6∈ B
4. x ∈ Ac ⇐⇒ x 6∈ A
5. (x , y ) ∈ A × B ⇐⇒ x ∈ A and y ∈ B
John Theado, PhD Intro to Discrete Structures February 9, 2022 134 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
1. x ∈ A ∪ B ⇐⇒ x ∈ A or x ∈ B
2. x ∈ A ∩ B ⇐⇒ x ∈ A and x ∈ B
3. x ∈ A − B ⇐⇒ x ∈ A but x 6∈ B
4. x ∈ Ac ⇐⇒ x 6∈ A
5. (x , y ) ∈ A × B ⇐⇒ x ∈ A and y ∈ B
John Theado, PhD Intro to Discrete Structures February 9, 2022 134 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
1. x ∈ A ∪ B ⇐⇒ x ∈ A or x ∈ B
2. x ∈ A ∩ B ⇐⇒ x ∈ A and x ∈ B
3. x ∈ A − B ⇐⇒ x ∈ A but x 6∈ B
4. x ∈ Ac ⇐⇒ x 6∈ A
5. (x , y ) ∈ A × B ⇐⇒ x ∈ A and y ∈ B
I Let x ∈ A ∩ B.
John Theado, PhD Intro to Discrete Structures February 9, 2022 134 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
1. x ∈ A ∪ B ⇐⇒ x ∈ A or x ∈ B
2. x ∈ A ∩ B ⇐⇒ x ∈ A and x ∈ B
3. x ∈ A − B ⇐⇒ x ∈ A but x 6∈ B
4. x ∈ Ac ⇐⇒ x 6∈ A
5. (x , y ) ∈ A × B ⇐⇒ x ∈ A and y ∈ B
I Let x ∈ A ∩ B.
I Then x ∈ A and x ∈ B.
John Theado, PhD Intro to Discrete Structures February 9, 2022 134 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
1. x ∈ A ∪ B ⇐⇒ x ∈ A or x ∈ B
2. x ∈ A ∩ B ⇐⇒ x ∈ A and x ∈ B
3. x ∈ A − B ⇐⇒ x ∈ A but x 6∈ B
4. x ∈ Ac ⇐⇒ x 6∈ A
5. (x , y ) ∈ A × B ⇐⇒ x ∈ A and y ∈ B
I Let x ∈ A ∩ B.
I Then x ∈ A and x ∈ B.
I If this is true, then x ∈ A or x ∈ B is also true.
John Theado, PhD Intro to Discrete Structures February 9, 2022 134 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
1. x ∈ A ∪ B ⇐⇒ x ∈ A or x ∈ B
2. x ∈ A ∩ B ⇐⇒ x ∈ A and x ∈ B
3. x ∈ A − B ⇐⇒ x ∈ A but x 6∈ B
4. x ∈ Ac ⇐⇒ x 6∈ A
5. (x , y ) ∈ A × B ⇐⇒ x ∈ A and y ∈ B
I Let x ∈ A ∩ B.
I Then x ∈ A and x ∈ B.
I If this is true, then x ∈ A or x ∈ B is also true.
I Thus x ∈ A ∪ B.
John Theado, PhD Intro to Discrete Structures February 9, 2022 134 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
1. x ∈ A ∪ B ⇐⇒ x ∈ A or x ∈ B
2. x ∈ A ∩ B ⇐⇒ x ∈ A and x ∈ B
3. x ∈ A − B ⇐⇒ x ∈ A but x 6∈ B
4. x ∈ Ac ⇐⇒ x 6∈ A
5. (x , y ) ∈ A × B ⇐⇒ x ∈ A and y ∈ B
I Let x ∈ A ∩ B.
I Then x ∈ A and x ∈ B.
I If this is true, then x ∈ A or x ∈ B is also true.
I Thus x ∈ A ∪ B.
I Therefore, A ∩ B ⊆ A ∪ B.
John Theado, PhD Intro to Discrete Structures February 9, 2022 134 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
i. A ∩ B ⊆ A and A ∩ B ⊆ B,
ii. A ⊆ A ∪ B and B ⊆ A ∪ B, and
iii. if A ⊆ B and B ⊆ C, then A ⊆ C.
John Theado, PhD Intro to Discrete Structures February 9, 2022 135 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
i. A ∩ B ⊆ A and A ∩ B ⊆ B,
ii. A ⊆ A ∪ B and B ⊆ A ∪ B, and
iii. if A ⊆ B and B ⊆ C, then A ⊆ C.
Proof (partial): In each case, let x be an element in the LHS and we will use
the rules of inference from Chapter 2:
John Theado, PhD Intro to Discrete Structures February 9, 2022 135 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
i. A ∩ B ⊆ A and A ∩ B ⊆ B,
ii. A ⊆ A ∪ B and B ⊆ A ∪ B, and
iii. if A ⊆ B and B ⊆ C, then A ⊆ C.
Proof (partial): In each case, let x be an element in the LHS and we will use
the rules of inference from Chapter 2:
i. Specialization.
John Theado, PhD Intro to Discrete Structures February 9, 2022 135 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
i. A ∩ B ⊆ A and A ∩ B ⊆ B,
ii. A ⊆ A ∪ B and B ⊆ A ∪ B, and
iii. if A ⊆ B and B ⊆ C, then A ⊆ C.
Proof (partial): In each case, let x be an element in the LHS and we will use
the rules of inference from Chapter 2:
i. Specialization.
ii. Generalization.
John Theado, PhD Intro to Discrete Structures February 9, 2022 135 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
i. A ∩ B ⊆ A and A ∩ B ⊆ B,
ii. A ⊆ A ∪ B and B ⊆ A ∪ B, and
iii. if A ⊆ B and B ⊆ C, then A ⊆ C.
Proof (partial): In each case, let x be an element in the LHS and we will use
the rules of inference from Chapter 2:
i. Specialization.
ii. Generalization.
iii. Transitivity.
John Theado, PhD Intro to Discrete Structures February 9, 2022 135 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Proof that A ∩ B ⊆ A:
John Theado, PhD Intro to Discrete Structures February 9, 2022 136 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Proof that A ∩ B ⊆ A:
I Let x ∈ A ∩ B.
John Theado, PhD Intro to Discrete Structures February 9, 2022 136 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Proof that A ∩ B ⊆ A:
I Let x ∈ A ∩ B.
I Then x ∈ A and x ∈ B.
John Theado, PhD Intro to Discrete Structures February 9, 2022 136 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Proof that A ∩ B ⊆ A:
I Let x ∈ A ∩ B.
I Then x ∈ A and x ∈ B.
I In particular, (by specialization), x ∈ A.
John Theado, PhD Intro to Discrete Structures February 9, 2022 136 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Proof that A ∩ B ⊆ A:
I Let x ∈ A ∩ B.
I Then x ∈ A and x ∈ B.
I In particular, (by specialization), x ∈ A.
I Thefore, A ∩ B ⊆ A.
John Theado, PhD Intro to Discrete Structures February 9, 2022 136 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Proof that A ∩ B ⊆ A:
I Let x ∈ A ∩ B.
I Then x ∈ A and x ∈ B.
I In particular, (by specialization), x ∈ A.
I Thefore, A ∩ B ⊆ A.
Exercise: Similarly argue the truth of the remain parts of the previous theorem.
John Theado, PhD Intro to Discrete Structures February 9, 2022 136 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
De Morgan’s Laws
Theorem: If A and B are any two sets in some universe U , then
(a) (A ∪ B )c = Ac ∩ B c
(b) (A ∩ B )c = Ac ∪ B c
Proof: De Morgan’s Laws for sets are true for the same reason as in logic:
John Theado, PhD Intro to Discrete Structures February 9, 2022 137 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
De Morgan’s Laws
Theorem: If A and B are any two sets in some universe U , then
(a) (A ∪ B )c = Ac ∩ B c
(b) (A ∩ B )c = Ac ∪ B c
Proof: De Morgan’s Laws for sets are true for the same reason as in logic:
x ∈ (A ∪ B )c
John Theado, PhD Intro to Discrete Structures February 9, 2022 137 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
De Morgan’s Laws
Theorem: If A and B are any two sets in some universe U , then
(a) (A ∪ B )c = Ac ∩ B c
(b) (A ∩ B )c = Ac ∪ B c
Proof: De Morgan’s Laws for sets are true for the same reason as in logic:
x ∈ (A ∪ B )c
⇐⇒ x 6∈ A ∪ B Procedure for complement
John Theado, PhD Intro to Discrete Structures February 9, 2022 137 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
De Morgan’s Laws
Theorem: If A and B are any two sets in some universe U , then
(a) (A ∪ B )c = Ac ∩ B c
(b) (A ∩ B )c = Ac ∪ B c
Proof: De Morgan’s Laws for sets are true for the same reason as in logic:
x ∈ (A ∪ B )c
⇐⇒ x 6∈ A ∪ B Procedure for complement
⇐⇒ ∼(x ∈ A ∪ B ) Definition of 6∈
John Theado, PhD Intro to Discrete Structures February 9, 2022 137 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
De Morgan’s Laws
Theorem: If A and B are any two sets in some universe U , then
(a) (A ∪ B )c = Ac ∩ B c
(b) (A ∩ B )c = Ac ∪ B c
Proof: De Morgan’s Laws for sets are true for the same reason as in logic:
x ∈ (A ∪ B )c
⇐⇒ x 6∈ A ∪ B Procedure for complement
⇐⇒ ∼(x ∈ A ∪ B ) Definition of 6∈
⇐⇒ ∼(x ∈ A ∨ x ∈ B ) Procedure for union
John Theado, PhD Intro to Discrete Structures February 9, 2022 137 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
De Morgan’s Laws
Theorem: If A and B are any two sets in some universe U , then
(a) (A ∪ B )c = Ac ∩ B c
(b) (A ∩ B )c = Ac ∪ B c
Proof: De Morgan’s Laws for sets are true for the same reason as in logic:
x ∈ (A ∪ B )c
⇐⇒ x 6∈ A ∪ B Procedure for complement
⇐⇒ ∼(x ∈ A ∪ B ) Definition of 6∈
⇐⇒ ∼(x ∈ A ∨ x ∈ B ) Procedure for union
⇐⇒ ∼(x ∈ A) ∧ ∼(x ∈ B ) Logical De Morgan’s Law
John Theado, PhD Intro to Discrete Structures February 9, 2022 137 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
De Morgan’s Laws
Theorem: If A and B are any two sets in some universe U , then
(a) (A ∪ B )c = Ac ∩ B c
(b) (A ∩ B )c = Ac ∪ B c
Proof: De Morgan’s Laws for sets are true for the same reason as in logic:
x ∈ (A ∪ B )c
⇐⇒ x 6∈ A ∪ B Procedure for complement
⇐⇒ ∼(x ∈ A ∪ B ) Definition of 6∈
⇐⇒ ∼(x ∈ A ∨ x ∈ B ) Procedure for union
⇐⇒ ∼(x ∈ A) ∧ ∼(x ∈ B ) Logical De Morgan’s Law
⇐⇒ x 6∈ A ∧ x 6∈ B Definition of 6∈
John Theado, PhD Intro to Discrete Structures February 9, 2022 137 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
De Morgan’s Laws
Theorem: If A and B are any two sets in some universe U , then
(a) (A ∪ B )c = Ac ∩ B c
(b) (A ∩ B )c = Ac ∪ B c
Proof: De Morgan’s Laws for sets are true for the same reason as in logic:
x ∈ (A ∪ B )c
⇐⇒ x 6∈ A ∪ B Procedure for complement
⇐⇒ ∼(x ∈ A ∪ B ) Definition of 6∈
⇐⇒ ∼(x ∈ A ∨ x ∈ B ) Procedure for union
⇐⇒ ∼(x ∈ A) ∧ ∼(x ∈ B ) Logical De Morgan’s Law
⇐⇒ x 6∈ A ∧ x 6∈ B Definition of 6∈
c c
⇐⇒ x ∈ A ∧ x ∈ B Procedure for complement
John Theado, PhD Intro to Discrete Structures February 9, 2022 137 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
De Morgan’s Laws
Theorem: If A and B are any two sets in some universe U , then
(a) (A ∪ B )c = Ac ∩ B c
(b) (A ∩ B )c = Ac ∪ B c
Proof: De Morgan’s Laws for sets are true for the same reason as in logic:
x ∈ (A ∪ B )c
⇐⇒ x 6∈ A ∪ B Procedure for complement
⇐⇒ ∼(x ∈ A ∪ B ) Definition of 6∈
⇐⇒ ∼(x ∈ A ∨ x ∈ B ) Procedure for union
⇐⇒ ∼(x ∈ A) ∧ ∼(x ∈ B ) Logical De Morgan’s Law
⇐⇒ x 6∈ A ∧ x 6∈ B Definition of 6∈
c c
⇐⇒ x ∈ A ∧ x ∈ B Procedure for complement
c c
⇐⇒ x ∈ A ∩ B Procedure for intersection
John Theado, PhD Intro to Discrete Structures February 9, 2022 137 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Boolean Algebras
John Theado, PhD Intro to Discrete Structures February 9, 2022 138 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Boolean Algebras
John Theado, PhD Intro to Discrete Structures February 9, 2022 138 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 139 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 139 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 139 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 139 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 139 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 139 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 139 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 139 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 139 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 140 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 140 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 140 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 140 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 140 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 140 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 140 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 140 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 140 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Exercise: Prove these laws from the definition. They are analagous to the
same laws for logical forms and sets.
John Theado, PhD Intro to Discrete Structures February 9, 2022 140 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 141 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 141 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 141 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 141 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 141 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 141 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 141 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 141 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 142 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A ⊆ B ⇐⇒ ∀x , if x ∈ A then x ∈ B .
John Theado, PhD Intro to Discrete Structures February 9, 2022 142 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A ⊆ B ⇐⇒ ∀x , if x ∈ A then x ∈ B .
If A = 0/ , then the universal conditional above is vacuously true since the empty
set has no elements.
John Theado, PhD Intro to Discrete Structures February 9, 2022 142 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A ⊆ B ⇐⇒ ∀x , if x ∈ A then x ∈ B .
If A = 0/ , then the universal conditional above is vacuously true since the empty
set has no elements.
Fact: The empty set is unique.
John Theado, PhD Intro to Discrete Structures February 9, 2022 142 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A ⊆ B ⇐⇒ ∀x , if x ∈ A then x ∈ B .
If A = 0/ , then the universal conditional above is vacuously true since the empty
set has no elements.
Fact: The empty set is unique.
Proof: If E1 and E2 are both empty sets, then the above fact gives that both
E1 ⊆ E2 and E2 ⊆ E1 .
John Theado, PhD Intro to Discrete Structures February 9, 2022 142 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
A ⊆ B ⇐⇒ ∀x , if x ∈ A then x ∈ B .
If A = 0/ , then the universal conditional above is vacuously true since the empty
set has no elements.
Fact: The empty set is unique.
Proof: If E1 and E2 are both empty sets, then the above fact gives that both
E1 ⊆ E2 and E2 ⊆ E1 .
That is, E1 = E2 .
John Theado, PhD Intro to Discrete Structures February 9, 2022 142 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 143 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 143 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 143 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 143 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 143 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 143 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 143 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 143 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 143 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 143 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 143 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 143 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 144 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 144 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 144 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 144 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 144 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
same as A1 ∩ A2 ∩ . . . ∩ An .
John Theado, PhD Intro to Discrete Structures February 9, 2022 144 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 145 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
1. A1 ∪ A2 ∪ A3
John Theado, PhD Intro to Discrete Structures February 9, 2022 145 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 145 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 145 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
2. A1 ∩ A2 ∩ A3
John Theado, PhD Intro to Discrete Structures February 9, 2022 145 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 145 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 145 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 145 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 145 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 145 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 145 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 145 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 145 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 146 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 146 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 146 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
LHS ⊆ RHS :
John Theado, PhD Intro to Discrete Structures February 9, 2022 146 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
LHS ⊆ RHS :
I Let x ∈ A ∪
T∞
i =1 Bi .
John Theado, PhD Intro to Discrete Structures February 9, 2022 146 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
LHS ⊆ RHS :
I Let x ∈ A ∪ ∞
T
i =1 Bi .
I Then x ∈ A or x ∈ ∞
T
i =1 Bi .
John Theado, PhD Intro to Discrete Structures February 9, 2022 146 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
LHS ⊆ RHS :
I Let x ∈ A ∪ ∞
T
i =1 Bi .
I Then x ∈ A or x ∈ ∞
T
i =1 Bi .
I If x ∈ A then ∀i , x ∈ A ∪ Bi
John Theado, PhD Intro to Discrete Structures February 9, 2022 146 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
LHS ⊆ RHS :
I Let x ∈ A ∪ ∞
T
i =1 Bi .
I Then x ∈ A or x ∈ ∞
T
i =1 Bi .
I If x ∈ A then ∀i , x ∈ A ∪ Bi
I If x ∈ ∞
T
i =1 Bi , then
∀i , x ∈ A ∪ Bi .
John Theado, PhD Intro to Discrete Structures February 9, 2022 146 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
LHS ⊆ RHS :
I Let x ∈ A ∪ ∞
T
i =1 Bi .
I Then x ∈ A or x ∈ ∞
T
i =1 Bi .
I If x ∈ A then ∀i , x ∈ A ∪ Bi
I If x ∈ ∞
T
i =1 Bi , then
∀i , x ∈ A ∪ Bi .
I Thus, x ∈ RHS.
John Theado, PhD Intro to Discrete Structures February 9, 2022 146 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
LHS ⊆ RHS :
I Let x ∈ A ∪ ∞
T
i =1 Bi .
I Then x ∈ A or x ∈ ∞
T
i =1 Bi .
I If x ∈ A then ∀i , x ∈ A ∪ Bi
I If x ∈ ∞
T
i =1 Bi , then
∀i , x ∈ A ∪ Bi .
I Thus, x ∈ RHS.
I Therefore, LHS ⊆ RHS
John Theado, PhD Intro to Discrete Structures February 9, 2022 146 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
I Let x ∈ A ∪ i =1 Bi .
T∞
I Then x ∈ A or x ∈ ∞
T
i =1 Bi .
I If x ∈ A then ∀i , x ∈ A ∪ Bi
I If x ∈ ∞
T
i =1 Bi , then
∀i , x ∈ A ∪ Bi .
I Thus, x ∈ RHS.
I Therefore, LHS ⊆ RHS
John Theado, PhD Intro to Discrete Structures February 9, 2022 146 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
I Let x ∈ A ∪ i =1 Bi . I Let x ∈
T∞ T∞
i =1 (A ∪ Bi ).
I Then x ∈ A or x ∈ ∞
T
i =1 Bi .
I If x ∈ A then ∀i , x ∈ A ∪ Bi
I If x ∈ ∞
T
i =1 Bi , then
∀i , x ∈ A ∪ Bi .
I Thus, x ∈ RHS.
I Therefore, LHS ⊆ RHS
John Theado, PhD Intro to Discrete Structures February 9, 2022 146 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
I Let x ∈ A ∪ i =1 Bi . I Let x ∈ ∞
T∞
i =1 (A ∪ Bi ).
T
I Then x ∈ A or x ∈ ∞
T
I Then ∀i , x ∈ A ∪ Bi .
i =1 Bi .
I If x ∈ A then ∀i , x ∈ A ∪ Bi
I If x ∈ ∞
T
i =1 Bi , then
∀i , x ∈ A ∪ Bi .
I Thus, x ∈ RHS.
I Therefore, LHS ⊆ RHS
John Theado, PhD Intro to Discrete Structures February 9, 2022 146 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
I Let x ∈ A ∪ i =1 Bi . I Let x ∈ ∞
T∞
i =1 (A ∪ Bi ).
T
I Then x ∈ A or x ∈ ∞
T
I Then ∀i , x ∈ A ∪ Bi .
i =1 Bi .
I If x ∈ A then ∀i , x ∈ A ∪ Bi I Then either x ∈ A or x 6∈ A.
I If x ∈ ∞
T
i =1 Bi , then
∀i , x ∈ A ∪ Bi .
I Thus, x ∈ RHS.
I Therefore, LHS ⊆ RHS
John Theado, PhD Intro to Discrete Structures February 9, 2022 146 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
I Let x ∈ A ∪ i =1 Bi . I Let x ∈ ∞
T∞
i =1 (A ∪ Bi ).
T
I Then x ∈ A or x ∈ ∞
T
I Then ∀i , x ∈ A ∪ Bi .
i =1 Bi .
I If x ∈ A then ∀i , x ∈ A ∪ Bi I Then either x ∈ A or x 6∈ A.
I If x ∈ ∞ I If x ∈ A then x ∈ LHS
T
i =1 Bi , then
∀i , x ∈ A ∪ Bi .
I Thus, x ∈ RHS.
I Therefore, LHS ⊆ RHS
John Theado, PhD Intro to Discrete Structures February 9, 2022 146 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
I Let x ∈ A ∪ i =1 Bi . I Let x ∈ ∞
T∞
i =1 (A ∪ Bi ).
T
I Then x ∈ A or x ∈ ∞
T
I Then ∀i , x ∈ A ∪ Bi .
i =1 Bi .
I If x ∈ A then ∀i , x ∈ A ∪ Bi I Then either x ∈ A or x 6∈ A.
I If x ∈ ∞ I If x ∈ A then x ∈ LHS
T
i =1 Bi , then
∀i , x ∈ A ∪ Bi . I If x 6∈ A, then ∀i , x ∈ A ∪ Bi means
∀i , x ∈ Bi , so that x ∈ ∞
T
I Thus, x ∈ RHS. i =1 Bi
I Therefore, LHS ⊆ RHS
John Theado, PhD Intro to Discrete Structures February 9, 2022 146 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
I Let x ∈ A ∪ i =1 Bi . I Let x ∈ ∞
T∞
i =1 (A ∪ Bi ).
T
I Then x ∈ A or x ∈ ∞
T
I Then ∀i , x ∈ A ∪ Bi .
i =1 Bi .
I If x ∈ A then ∀i , x ∈ A ∪ Bi I Then either x ∈ A or x 6∈ A.
I If x ∈ ∞ I If x ∈ A then x ∈ LHS
T
i =1 Bi , then
∀i , x ∈ A ∪ Bi . I If x 6∈ A, then ∀i , x ∈ A ∪ Bi means
∀i , x ∈ Bi , so that x ∈ ∞
T
I Thus, x ∈ RHS. i =1 Bi
I Therefore, LHS ⊆ RHS I Thus, x ∈ LHS.
John Theado, PhD Intro to Discrete Structures February 9, 2022 146 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
I Let x ∈ A ∪ i =1 Bi . I Let x ∈ ∞
T∞
i =1 (A ∪ Bi ).
T
I Then x ∈ A or x ∈ ∞
T
I Then ∀i , x ∈ A ∪ Bi .
i =1 Bi .
I If x ∈ A then ∀i , x ∈ A ∪ Bi I Then either x ∈ A or x 6∈ A.
I If x ∈ ∞ I If x ∈ A then x ∈ LHS
T
i =1 Bi , then
∀i , x ∈ A ∪ Bi . I If x 6∈ A, then ∀i , x ∈ A ∪ Bi means
∀i , x ∈ Bi , so that x ∈ ∞
T
I Thus, x ∈ RHS. i =1 Bi
I Therefore, LHS ⊆ RHS I Thus, x ∈ LHS.
I Therefore, RHS ⊆ LHS
John Theado, PhD Intro to Discrete Structures February 9, 2022 146 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
I Let x ∈ A ∪ i =1 Bi . I Let x ∈ ∞
T∞
i =1 (A ∪ Bi ).
T
I Then x ∈ A or x ∈ ∞
T
I Then ∀i , x ∈ A ∪ Bi .
i =1 Bi .
I If x ∈ A then ∀i , x ∈ A ∪ Bi I Then either x ∈ A or x 6∈ A.
I If x ∈ ∞ I If x ∈ A then x ∈ LHS
T
i =1 Bi , then
∀i , x ∈ A ∪ Bi . I If x 6∈ A, then ∀i , x ∈ A ∪ Bi means
∀i , x ∈ Bi , so that x ∈ ∞
T
I Thus, x ∈ RHS. i =1 Bi
I Therefore, LHS ⊆ RHS I Thus, x ∈ LHS.
I Therefore, RHS ⊆ LHS
Partitions of Sets
Often, we would like to take a set, say A and partition it into a number of other
sets where each member of A belongs to exactly one set in the partition.
John Theado, PhD Intro to Discrete Structures February 9, 2022 147 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Partitions of Sets
Often, we would like to take a set, say A and partition it into a number of other
sets where each member of A belongs to exactly one set in the partition.
For this, we want distinct sets in this partition to nonoverlapping, i.e. disjoint.
John Theado, PhD Intro to Discrete Structures February 9, 2022 147 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Partitions of Sets
Often, we would like to take a set, say A and partition it into a number of other
sets where each member of A belongs to exactly one set in the partition.
For this, we want distinct sets in this partition to nonoverlapping, i.e. disjoint.
Some natural (and possibly imperfect) examples:
John Theado, PhD Intro to Discrete Structures February 9, 2022 147 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Partitions of Sets
Often, we would like to take a set, say A and partition it into a number of other
sets where each member of A belongs to exactly one set in the partition.
For this, we want distinct sets in this partition to nonoverlapping, i.e. disjoint.
Some natural (and possibly imperfect) examples:
John Theado, PhD Intro to Discrete Structures February 9, 2022 147 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Partitions of Sets
Often, we would like to take a set, say A and partition it into a number of other
sets where each member of A belongs to exactly one set in the partition.
For this, we want distinct sets in this partition to nonoverlapping, i.e. disjoint.
Some natural (and possibly imperfect) examples:
John Theado, PhD Intro to Discrete Structures February 9, 2022 147 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Partitions of Sets
Often, we would like to take a set, say A and partition it into a number of other
sets where each member of A belongs to exactly one set in the partition.
For this, we want distinct sets in this partition to nonoverlapping, i.e. disjoint.
Some natural (and possibly imperfect) examples:
John Theado, PhD Intro to Discrete Structures February 9, 2022 147 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Partitions of Sets
Often, we would like to take a set, say A and partition it into a number of other
sets where each member of A belongs to exactly one set in the partition.
For this, we want distinct sets in this partition to nonoverlapping, i.e. disjoint.
Some natural (and possibly imperfect) examples:
John Theado, PhD Intro to Discrete Structures February 9, 2022 147 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Partitions of Sets
Often, we would like to take a set, say A and partition it into a number of other
sets where each member of A belongs to exactly one set in the partition.
For this, we want distinct sets in this partition to nonoverlapping, i.e. disjoint.
Some natural (and possibly imperfect) examples:
John Theado, PhD Intro to Discrete Structures February 9, 2022 147 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Two sets A and B are called disjoint if they have no common elements, i.e their
intersection is empty. Symbolically,
John Theado, PhD Intro to Discrete Structures February 9, 2022 148 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Two sets A and B are called disjoint if they have no common elements, i.e their
intersection is empty. Symbolically,
Example: For A = {1, 3, 5} and B = {2, 4, 6} we have that A and B are disjoint.
John Theado, PhD Intro to Discrete Structures February 9, 2022 148 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Two sets A and B are called disjoint if they have no common elements, i.e their
intersection is empty. Symbolically,
Example: For A = {1, 3, 5} and B = {2, 4, 6} we have that A and B are disjoint.
Sets A1 , A2 , A3 , . . . are called mutually disjoint (or pairwise disjoint or
nonoverlapping) if no two sets Ai and Aj with distinct subscripts have any elements
in common, i.e. are disjoint. That is, for any pair of integers i and j,
Ai ∩ Aj = 0/ whenever i 6= j .
John Theado, PhD Intro to Discrete Structures February 9, 2022 148 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 149 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Example 1: Let A = {1, 2, 3, 4, 5, 6}, A1 = {1, 2}, A2 = {3, 4}, A3 = {5, 6}. Is
{A1 , A2 , A3 } a partition of A?
John Theado, PhD Intro to Discrete Structures February 9, 2022 149 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Example 1: Let A = {1, 2, 3, 4, 5, 6}, A1 = {1, 2}, A2 = {3, 4}, A3 = {5, 6}. Is
{A1 , A2 , A3 } a partition of A?
Solution: Yes, each member of A is on one of the sets in the partition, i,e. the union of
the collection is A, and each of the sets is pairwise disjoint.
John Theado, PhD Intro to Discrete Structures February 9, 2022 149 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Example 1: Let A = {1, 2, 3, 4, 5, 6}, A1 = {1, 2}, A2 = {3, 4}, A3 = {5, 6}. Is
{A1 , A2 , A3 } a partition of A?
Solution: Yes, each member of A is on one of the sets in the partition, i,e. the union of
the collection is A, and each of the sets is pairwise disjoint.
Example 2: Does {T0 , T1 , T2 } form a partion of Z where
John Theado, PhD Intro to Discrete Structures February 9, 2022 149 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Example 1: Let A = {1, 2, 3, 4, 5, 6}, A1 = {1, 2}, A2 = {3, 4}, A3 = {5, 6}. Is
{A1 , A2 , A3 } a partition of A?
Solution: Yes, each member of A is on one of the sets in the partition, i,e. the union of
the collection is A, and each of the sets is pairwise disjoint.
Example 2: Does {T0 , T1 , T2 } form a partion of Z where
John Theado, PhD Intro to Discrete Structures February 9, 2022 149 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Power Sets
Let A be a set. The power set of A, denoted by P(A), is the set containing all subsets
of A.
John Theado, PhD Intro to Discrete Structures February 9, 2022 150 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Power Sets
Let A be a set. The power set of A, denoted by P(A), is the set containing all subsets
of A.
Recall that the cardinality of a finite set A, denoted as |A|, is the number of elements
contained in the set.
John Theado, PhD Intro to Discrete Structures February 9, 2022 150 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Power Sets
Let A be a set. The power set of A, denoted by P(A), is the set containing all subsets
of A.
Recall that the cardinality of a finite set A, denoted as |A|, is the number of elements
contained in the set. Observe that
Set A |A| Power Set |P(A)|
John Theado, PhD Intro to Discrete Structures February 9, 2022 150 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Power Sets
Let A be a set. The power set of A, denoted by P(A), is the set containing all subsets
of A.
Recall that the cardinality of a finite set A, denoted as |A|, is the number of elements
contained in the set. Observe that
Set A |A| Power Set |P(A)|
0/
John Theado, PhD Intro to Discrete Structures February 9, 2022 150 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Power Sets
Let A be a set. The power set of A, denoted by P(A), is the set containing all subsets
of A.
Recall that the cardinality of a finite set A, denoted as |A|, is the number of elements
contained in the set. Observe that
Set A |A| Power Set |P(A)|
0/ 0
John Theado, PhD Intro to Discrete Structures February 9, 2022 150 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Power Sets
Let A be a set. The power set of A, denoted by P(A), is the set containing all subsets
of A.
Recall that the cardinality of a finite set A, denoted as |A|, is the number of elements
contained in the set. Observe that
Set A |A| Power
n o Set |P(A)|
0/ 0 0/
John Theado, PhD Intro to Discrete Structures February 9, 2022 150 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Power Sets
Let A be a set. The power set of A, denoted by P(A), is the set containing all subsets
of A.
Recall that the cardinality of a finite set A, denoted as |A|, is the number of elements
contained in the set. Observe that
Set A |A| Power
n o Set |P(A)|
0/ 0 0/ 1
John Theado, PhD Intro to Discrete Structures February 9, 2022 150 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Power Sets
Let A be a set. The power set of A, denoted by P(A), is the set containing all subsets
of A.
Recall that the cardinality of a finite set A, denoted as |A|, is the number of elements
contained in the set. Observe that
Set A |A| Power
n o Set |P(A)|
0/ 0 0/ 1
{a}
John Theado, PhD Intro to Discrete Structures February 9, 2022 150 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Power Sets
Let A be a set. The power set of A, denoted by P(A), is the set containing all subsets
of A.
Recall that the cardinality of a finite set A, denoted as |A|, is the number of elements
contained in the set. Observe that
Set A |A| Power
n o Set |P(A)|
0/ 0 0/ 1
{a} 1
John Theado, PhD Intro to Discrete Structures February 9, 2022 150 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Power Sets
Let A be a set. The power set of A, denoted by P(A), is the set containing all subsets
of A.
Recall that the cardinality of a finite set A, denoted as |A|, is the number of elements
contained in the set. Observe that
Set A |A| Power
n o Set |P(A)|
0/ 0 0/ 1
n o
{a} 1 / {a}
0,
John Theado, PhD Intro to Discrete Structures February 9, 2022 150 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Power Sets
Let A be a set. The power set of A, denoted by P(A), is the set containing all subsets
of A.
Recall that the cardinality of a finite set A, denoted as |A|, is the number of elements
contained in the set. Observe that
Set A |A| Power
n o Set |P(A)|
0/ 0 0/ 1
n o
{a} 1 / {a}
0, 2
John Theado, PhD Intro to Discrete Structures February 9, 2022 150 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Power Sets
Let A be a set. The power set of A, denoted by P(A), is the set containing all subsets
of A.
Recall that the cardinality of a finite set A, denoted as |A|, is the number of elements
contained in the set. Observe that
Set A |A| Power
n o Set |P(A)|
0/ 0 0/ 1
n o
{a} 1 / {a}
0, 2
{a, b}
John Theado, PhD Intro to Discrete Structures February 9, 2022 150 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Power Sets
Let A be a set. The power set of A, denoted by P(A), is the set containing all subsets
of A.
Recall that the cardinality of a finite set A, denoted as |A|, is the number of elements
contained in the set. Observe that
Set A |A| Power
n o Set |P(A)|
0/ 0 0/ 1
n o
{a} 1 / {a}
0, 2
{a, b} 2
John Theado, PhD Intro to Discrete Structures February 9, 2022 150 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Power Sets
Let A be a set. The power set of A, denoted by P(A), is the set containing all subsets
of A.
Recall that the cardinality of a finite set A, denoted as |A|, is the number of elements
contained in the set. Observe that
Set A |A| Power
n o Set |P(A)|
0/ 0 0/ 1
n o
{a} 1 / {a}
0, 2
n o
{a, b} 2 / {a}, {b}, {a, b}
0,
John Theado, PhD Intro to Discrete Structures February 9, 2022 150 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Power Sets
Let A be a set. The power set of A, denoted by P(A), is the set containing all subsets
of A.
Recall that the cardinality of a finite set A, denoted as |A|, is the number of elements
contained in the set. Observe that
Set A |A| Power
n o Set |P(A)|
0/ 0 0/ 1
n o
{a} 1 / {a}
0, 2
n o
{a, b} 2 / {a}, {b}, {a, b}
0, 4
John Theado, PhD Intro to Discrete Structures February 9, 2022 150 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Power Sets
Let A be a set. The power set of A, denoted by P(A), is the set containing all subsets
of A.
Recall that the cardinality of a finite set A, denoted as |A|, is the number of elements
contained in the set. Observe that
Set A |A| Power
n o Set |P(A)|
0/ 0 0/ 1
n o
{a} 1 / {a}
0, 2
n o
{a, b} 2 / {a}, {b}, {a, b}
0, 4
{a, b, c }
John Theado, PhD Intro to Discrete Structures February 9, 2022 150 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Power Sets
Let A be a set. The power set of A, denoted by P(A), is the set containing all subsets
of A.
Recall that the cardinality of a finite set A, denoted as |A|, is the number of elements
contained in the set. Observe that
Set A |A| Power
n o Set |P(A)|
0/ 0 0/ 1
n o
{a} 1 / {a}
0, 2
n o
{a, b} 2 / {a}, {b}, {a, b}
0, 4
{a, b, c } 3
John Theado, PhD Intro to Discrete Structures February 9, 2022 150 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Power Sets
Let A be a set. The power set of A, denoted by P(A), is the set containing all subsets
of A.
Recall that the cardinality of a finite set A, denoted as |A|, is the number of elements
contained in the set. Observe that
Set A |A| Power
n o Set |P(A)|
0/ 0 0/ 1
n o
{a} 1 / {a}
0, 2
n o
{a, b} 2 / {a}, {b}, {a, b}
0, 4
n
/ {a}, {b}, {c },
0,
{a, b, c } 3 {a, b}, {o
a, c }, {b, c },
{a, b, c }
John Theado, PhD Intro to Discrete Structures February 9, 2022 150 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Power Sets
Let A be a set. The power set of A, denoted by P(A), is the set containing all subsets
of A.
Recall that the cardinality of a finite set A, denoted as |A|, is the number of elements
contained in the set. Observe that
Set A |A| Power
n o Set |P(A)|
0/ 0 0/ 1
n o
{a} 1 / {a}
0, 2
n o
{a, b} 2 / {a}, {b}, {a, b}
0, 4
n
/ {a}, {b}, {c },
0,
{a, b, c } 3 {a, b}, {o
a, c }, {b, c }, 8
{a, b, c }
John Theado, PhD Intro to Discrete Structures February 9, 2022 150 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Power Sets
Let A be a set. The power set of A, denoted by P(A), is the set containing all subsets
of A.
Recall that the cardinality of a finite set A, denoted as |A|, is the number of elements
contained in the set. Observe that
Set A |A| Power
n o Set |P(A)|
0/ 0 0/ 1
n o
{a} 1 / {a}
0, 2
n o
{a, b} 2 / {a}, {b}, {a, b}
0, 4
n
/ {a}, {b}, {c },
0,
{a, b, c } 3 {a, b}, {o
a, c }, {b, c }, 8
{a, b, c }
The cardinality of the power set of any finite set A is 2|A| . For this reason, we often see
2A as a notation for the power set.
John Theado, PhD Intro to Discrete Structures February 9, 2022 150 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Is the following set property true for all possible sets A, B, and C?
(A − B ) ∪ (B − C ) = A − C
John Theado, PhD Intro to Discrete Structures February 9, 2022 151 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Is the following set property true for all possible sets A, B, and C?
(A − B ) ∪ (B − C ) = A − C
(x − y ) + (y − z ) = x − z
John Theado, PhD Intro to Discrete Structures February 9, 2022 151 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Is the following set property true for all possible sets A, B, and C?
(A − B ) ∪ (B − C ) = A − C
(x − y ) + (y − z ) = x − z
C C
John Theado, PhD Intro to Discrete Structures February 9, 2022 151 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Is the following set property true for all possible sets A, B, and C?
(A − B ) ∪ (B − C ) = A − C
(x − y ) + (y − z ) = x − z
C C
John Theado, PhD Intro to Discrete Structures February 9, 2022 151 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Is the following set property true for all possible sets A, B, and C?
(A − B ) ∪ (B − C ) = A − C
(x − y ) + (y − z ) = x − z
C C
John Theado, PhD Intro to Discrete Structures February 9, 2022 151 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Is the following set property true for all possible sets A, B, and C?
(A − B ) ∪ (B − C ) = A − C
(x − y ) + (y − z ) = x − z
C C
John Theado, PhD Intro to Discrete Structures February 9, 2022 151 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Instead, compare
(A − B ) ∪ (B − C ) = A − C
to the false logical equivalence
(a ∧ ∼b) ∨ (b ∧ ∼c ) ≡ a ∧ ∼c
which is demonstrated to be false, for example, when b is true but a and c are
false.
John Theado, PhD Intro to Discrete Structures February 9, 2022 152 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Instead, compare
(A − B ) ∪ (B − C ) = A − C
to the false logical equivalence
(a ∧ ∼b) ∨ (b ∧ ∼c ) ≡ a ∧ ∼c
which is demonstrated to be false, for example, when b is true but a and c are
false.
We can, looking at both of these, and the Venn diagram, to construct a
counterexample in the case that B contains an element in neither A nor C.
John Theado, PhD Intro to Discrete Structures February 9, 2022 152 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Instead, compare
(A − B ) ∪ (B − C ) = A − C
to the false logical equivalence
(a ∧ ∼b) ∨ (b ∧ ∼c ) ≡ a ∧ ∼c
which is demonstrated to be false, for example, when b is true but a and c are
false.
We can, looking at both of these, and the Venn diagram, to construct a
counterexample in the case that B contains an element in neither A nor C.
A simple one is given by B = {1}, A = 0/ , and C = 0/ .
John Theado, PhD Intro to Discrete Structures February 9, 2022 152 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 153 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 153 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
(A ∪ B ) − C
John Theado, PhD Intro to Discrete Structures February 9, 2022 153 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 153 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 153 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 153 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 153 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 153 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Russell’s Paradox
Recall that the Power Set P(A) of a set A is a set containing other sets: those subsets
of A. This set is well-defined.
John Theado, PhD Intro to Discrete Structures February 9, 2022 154 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Russell’s Paradox
Recall that the Power Set P(A) of a set A is a set containing other sets: those subsets
of A. This set is well-defined.
Question: What about other sets containing sets? Is there, for instance, a set of all
sets? Somehow a super-universal set containing everything?
John Theado, PhD Intro to Discrete Structures February 9, 2022 154 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Russell’s Paradox
Recall that the Power Set P(A) of a set A is a set containing other sets: those subsets
of A. This set is well-defined.
Question: What about other sets containing sets? Is there, for instance, a set of all
sets? Somehow a super-universal set containing everything?
Solution: Consider that such a set existed. It would contain, as a subset, a set S
consisting of all sets that do not contain themselves, i.e.
John Theado, PhD Intro to Discrete Structures February 9, 2022 154 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Russell’s Paradox
Recall that the Power Set P(A) of a set A is a set containing other sets: those subsets
of A. This set is well-defined.
Question: What about other sets containing sets? Is there, for instance, a set of all
sets? Somehow a super-universal set containing everything?
Solution: Consider that such a set existed. It would contain, as a subset, a set S
consisting of all sets that do not contain themselves, i.e.
Now we ask, does S contain itself, i.e. is S ∈ S? Well, there are two possibilities, it
does or it doesn’t. Let’s consider these.
John Theado, PhD Intro to Discrete Structures February 9, 2022 154 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Russell’s Paradox
Recall that the Power Set P(A) of a set A is a set containing other sets: those subsets
of A. This set is well-defined.
Question: What about other sets containing sets? Is there, for instance, a set of all
sets? Somehow a super-universal set containing everything?
Solution: Consider that such a set existed. It would contain, as a subset, a set S
consisting of all sets that do not contain themselves, i.e.
Now we ask, does S contain itself, i.e. is S ∈ S? Well, there are two possibilities, it
does or it doesn’t. Let’s consider these.
John Theado, PhD Intro to Discrete Structures February 9, 2022 154 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Russell’s Paradox
Recall that the Power Set P(A) of a set A is a set containing other sets: those subsets
of A. This set is well-defined.
Question: What about other sets containing sets? Is there, for instance, a set of all
sets? Somehow a super-universal set containing everything?
Solution: Consider that such a set existed. It would contain, as a subset, a set S
consisting of all sets that do not contain themselves, i.e.
Now we ask, does S contain itself, i.e. is S ∈ S? Well, there are two possibilities, it
does or it doesn’t. Let’s consider these.
John Theado, PhD Intro to Discrete Structures February 9, 2022 154 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
Russell’s Paradox
Recall that the Power Set P(A) of a set A is a set containing other sets: those subsets
of A. This set is well-defined.
Question: What about other sets containing sets? Is there, for instance, a set of all
sets? Somehow a super-universal set containing everything?
Solution: Consider that such a set existed. It would contain, as a subset, a set S
consisting of all sets that do not contain themselves, i.e.
Now we ask, does S contain itself, i.e. is S ∈ S? Well, there are two possibilities, it
does or it doesn’t. Let’s consider these.
Either way, we reach a contradiction, so S cannot exist, and neither can a set which
contains everything.
John Theado, PhD Intro to Discrete Structures February 9, 2022 154 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 155 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 155 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 155 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 155 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 155 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 156 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 156 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 156 / 157
Chapter 6: Set Theory Section 1-4: Set Theory
John Theado, PhD Intro to Discrete Structures February 9, 2022 156 / 157
References
References
John Theado, PhD Intro to Discrete Structures February 9, 2022 157 / 157