Logic and Set Theory

PROBLEM SOLVING AND PROCESSES

Prepared by Cherish Ivy P. Fabricante, LPT

 Logic
Gottfried Wilhelm Leibniz tries to advance the study of logic from a merely philosophical
subject to a formal mathematical subject. Leibniz never completely achieved this goal;
however, several mathematicians, such as Augustus De Morgan and George Boole,
contributed to the advancement of symbolic logic as a mathematical discipline.

STATEMENT
A statement is a declarative sentence that is either true or false, but not both true and false.

Example:
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________

Exercise: Determine whether each sentence is a statement.

1. How are you feeling today? _________________________

2. Pangasinan is a province in the Philippines. _________________________
3. Ivy is a good singer. _________________________
4. 𝑥 + 8 = 23 _________________________

SIMPLE STATEMENT
A simple statement is a statement that conveys a single idea.

Example:
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________

COMPOUND STATEMENT
A compound statement is a statement that conveys two or more ideas. Connecting simple
statements with words and phrases such as and, or, if . . . then, and if and only if creates a
compound statement.

Example:
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________

LOGIC AND SET THEORY PREPARED BY CHERISH IVY P. FABRICANTE PAGE 1

 Logic Connectives and Symbols

Statement Connective Symbolic Form Type of Statement

not 𝑝 not ∼𝑝 negation
𝑝 and 𝑞 and 𝑝∧𝑞 conjunction
𝑝 or 𝑞 or 𝑝∨𝑞 disjunction
If 𝑝, then 𝑞 If … then 𝑝→𝑞 conditional
𝑝 if and only if 𝑞 if and only if 𝑝↔𝑞 biconditional

NEGATION OF STATEMENT
The negation of a statement is the opposite of the given mathematical statement.

Example:
1. 3 is a prime number. ______________________________________
2. Today is Thursday ______________________________________

WRITING COMPOUND STATEMENTS IN SYMBOLIC FORM

Examples: Consider the following simple statements.

𝑝: Today is Friday
𝑞: It is raining
𝑟: I am going to a movie
𝑠: I am not going to the basketball game.

Write the following compound statements in symbolic form.

a. Today is Friday and it is raining. ____________

b. It is not raining and I am going to a movie. ____________
c. I am going to the basketball game or I am going to a movie. ____________
d. If it is raining, then I am not going to the basketball game. ____________

TRANSLATE SYMBOLIC STATEMENTS

Examples: Consider the following simple statements.

𝑝: The game will be played in Manila.

𝑞: The game will be shown on ABS-CBN.
𝑟: The game will not be shown on GMA.
𝑠: The Ginebra are favored to win.

LOGIC AND SET THEORY PREPARED BY CHERISH IVY P. FABRICANTE PAGE 2

 Write each of the following symbolic statements in words

a. 𝑞 ∧ 𝑝 _________________________________________________________________
b. 𝑠 ↔∽ 𝑝 ________________________________________________________________

THE CONDITIONAL AND RELATED STATEMENTS

Every conditional statement has three related statements. They are called the converse, the
inverse, and the contrapositive.

- The converse of 𝑝 → 𝑞 is 𝑞 → 𝑝.
- The inverse of 𝑝 → 𝑞 is ~𝑝 → ~𝑞.
- The contrapositive of 𝑝 → 𝑞 is ~𝑞 → ~𝑝.

Examples: Write the converse, inverse, and contrapositive of

If I get the job, then I will rent the apartment.

Converse: _____________________________________________________________________
Inverse: ______________________________________________________________________
Contrapositive: ________________________________________________________________

LOGIC AND SET THEORY PREPARED BY CHERISH IVY P. FABRICANTE PAGE 3

 Sets
To better understand the universe, ancient astronomers classified certain groups of stars as
constellations. Today we still find it extremely helpful to classify items into groups that
enable us to find order and meaning in our complicated world.

SET
A set is a collection of things, in any order. Sets are usually identified with capital letters to
keep them distinct from variables in algebra, which are usually small letters.
For example, let 𝐴 be the set of the primary colors. Thus,

𝐴 = {𝑏𝑙𝑢𝑒, 𝑦𝑒𝑙𝑙𝑜𝑤, 𝑟𝑒𝑑}

Examples:
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________

ELEMENTS
The things contained in a set are called elements (also known as members). Consider the
set 𝐴 above, blue is an element of set 𝐴. You can write this statement using the symbol ∈,
which means “is an element of”:
𝑏𝑙𝑢𝑒 ∈ 𝐴
Note that green is not an element of 𝐴. Thus, we can write this statement using the
symbol ∉, which means “is not an element of”:

𝑔𝑟𝑒𝑒𝑛 ∉ 𝐴

Examples:
______________________________________________________________________________
______________________________________________________________________________

BASIC NUMBER SETS

Natural Numbers or
ℕ = {1, 2, 3, 4, 5, … }
Counting Numbers

Whole Numbers 𝑊 = {0, 1, 2, 3, 4, 5, … }

Integers 𝐼 = {… , −4, −3, −2, −1, 0, 1, 2, 3, 4, … }

Rational Numbers ℚ = the set of all terminating and repeating decimals

Irrational Numbers ℑ = the set of all nonterminating, nonrepeating decimals

LOGIC AND SET THEORY PREPARED BY CHERISH IVY P. FABRICANTE PAGE 4

 Real Numbers ℝ = the set of all rational or irrational numbers

CARDINALITY OF SETS
The cardinality of a set is just a fancy word for the number of elements in that set.
For example, set 𝐴 = {𝑏𝑙𝑢𝑒, 𝑦𝑒𝑙𝑙𝑜𝑤, 𝑟𝑒𝑑} has 3 elements, so the cardinality of 𝐴 is 3.

Examples:
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________

SUBSETS
When all the elements of one set are completely contained in a second set, the first set is a
subset of the second. For example, consider these sets:
Example: Consider the following sets:

𝐻 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

𝐽 = {2, 4, 6, 8, 10}

Since every element of 𝐽 is also an element of 𝐻, then 𝐽 is a subset of 𝐻. Thus, we can write
this statement as

𝐽⊂𝐻

Examples:
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________

Number of Subsets of a Set

A set with 𝑛 elements has 2𝑛 subsets.

Examples:
______________________________________________________________________________
______________________________________________________________________________

LOGIC AND SET THEORY PREPARED BY CHERISH IVY P. FABRICANTE PAGE 5

 EMPTY SET
The empty set – also called the null set – is a set that has no elements:

𝑃 ={}

The symbol ∅ is used to represent the empty set. So 𝑃 = ∅.

UNIVERSAL SET
It is the set of all elements that are being considered. The letter U is used to denote the
universal set.

PERFORMING OPERATIONS ON SETS

Set theory also has important operations: union, intersection, and complement.

For discussion purposes, we consider the following four sets of number:

𝐷 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

𝐸 = {0, 2, 4, 6, 8}

𝐹 = {1, 3, 5, 7}

𝑈 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}

Union: Combined Elements

The union of set 𝐴 and 𝐵, denoted by 𝐴 ∪ 𝐵, is the set that contains all the elements that
belong to 𝐴 or to 𝐵 or to both.

𝐴 ∪ 𝐵 = { 𝑥 | 𝑥 ∈ 𝐴 𝑜𝑟 𝑥 ∈ 𝐵}

Example:

𝐸 ∪ 𝐹 = {0, 2, 4, 6, 8, } ∪ {1, 3, 5, 7}

= {0, 1, 2, 3, 4, 5, 6, 7, 8}

Exercise:

1. ________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
2. ________________________________________________________________________
________________________________________________________________________
________________________________________________________________________

LOGIC AND SET THEORY PREPARED BY CHERISH IVY P. FABRICANTE PAGE 6

 Intersection: Elements in Common
The intersection of set 𝐴 and 𝐵, denoted by 𝐴 ∩ 𝐵, is the set of elements common to both
𝐴 and 𝐵.

𝐴 ∩ 𝐵 = { 𝑥 | 𝑥 ∈ 𝐴 𝑎𝑛𝑑 𝑥 ∈ 𝐵}

Example:

𝐷 ∩ 𝐸 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} ∩ {0, 2, 4, 6, 8}

= {2, 4, 6, 8}

Exercise:

1. ________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
2. ________________________________________________________________________
________________________________________________________________________
________________________________________________________________________

Complement: Feeling left out

The complement of a set 𝐴, denoted by 𝐴′, is the set of all elements of the universal set 𝑈
that are not elements of 𝐴.
Example: Find the complement of 𝐷
𝐷 ′ = {11, 12, 13, 14, 15}

Exercise:

1. ________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
2. ________________________________________________________________________
________________________________________________________________________
________________________________________________________________________

LOGIC AND SET THEORY PREPARED BY CHERISH IVY P. FABRICANTE PAGE 7

 VENN DIAGRAM
A Venn diagram is an illustration that uses circles to show the relationships among things
or finite groups of things.

The Venn diagram in figure above shows the four regions formed by two intersecting sets
in a universal set 𝑈. It shows the four possible relationships that can exist between an
element of a universal set 𝑈 and two sets 𝐴 and 𝐵.
An element of 𝑈:
may be an element of both 𝐴 and 𝐵 Region i
may be an element of 𝐴, but not 𝐵 Region ii
may be an element of 𝐵, but not 𝐴 Region iii
may not be an element of either 𝐴 or 𝐵 Region iv

Examples:

1. In a school, there are 30 teachers who teach Mathematics or Physics. Of these, 18 teach
Mathematics and 6 teach both Physics and Mathematics. How many teach Physics only?

LOGIC AND SET THEORY PREPARED BY CHERISH IVY P. FABRICANTE PAGE 8

 Additional Notes:

______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________
______________________________________________________________________________

LOGIC AND SET THEORY PREPARED BY CHERISH IVY P. FABRICANTE PAGE 9