Mathematics in the Modern World

Week 3

GEED 10053

Prof. C. Equiza
TOPIC OUTLINE

v Propositions and Logical Connectives

v Sets, Operation and Venn Diagrams

Learning Outcomes
At the end of the lesson, the students are able to
1. identify which are propositions and which are not;
2. construct compound propositions using logical connectives;
3. construct truth tables for propositions;
4. test validity of arguments
 What is
Propositions?
Mathematics is a language. As in any other types of language, we use sentences to
communicate thoughts and ideas. Mathematics is not an exception. We use
propositions to communicate mathematical ideas precisely.
Example 1. Consider the following sentences.

1. Douglas MacArthur arrived in the Philippines in 1512.

2. Are you insane?
3. √2 is an irrational number.
4. Find all x such that xe−x = 2.
5. Is that your Laptop?
6. Basketball players are handsome.
7. There is life in other planets.
8. Welcome to the Philippines!
Immediately, we find that sentences (2), (4), (5), and (8) are not declarative sentences, so they
are not propositions.
Sentence (1) is a proposition because Douglas MacArthur either arrived in the Philippines in
1521 or not. In fact, this proposition is false because historical records shows that Douglas
MacArthur arrived in the Philippines some time in 1900s.

Sentence (3) is clearly a true proposition. Although statement (6) is a declarative sentence, it
cannot be considered a proposition because the meaning of the word “handsome” is subjective in
nature. Unless we could agree on an objective definition of “handsome”, then statement (6) cannot
be considered a proposition.
Finally, statement (7) is a proposition. Whether there is life or not in other planets, it doesn’t really
matter. The fact that this sentence is either true or false, and cannot be both true and false, makes
it a proposition. For this example, we still don’t have enough evidence to claim that proposition (7)
is true yet, and we don’t have a proof that it is false either. Hence, only time will tell when can we
assign a truth value for (7), but certainly, it has a truth value.

Symbolically, we denote propositions in this lesson using lower case letters, such as p, q, r, s, etc.
In the English language, we can simply state the negation of a proposition p by saying “It is not the case
that p.” However, there are many ways to express negations of statements grammatically by replacing
“is/are” by “is not/are not”, etc.

Example 2. Given the statements.

p : Everyone in Visayas speaks Cebuano.
q : Today is Wednesday

The corresponding negations are:

¬ p : Not everyone in Visayas speaks Cebuano.
¬ q : Today is not Wednesday.
 What is
Compound
Propositions?
A simple proposition is a proposition with only one subject and only one predicate. For
example, the proposition “Every cat that barks has a PhD.” is a simple proposition. The
subject of this proposition is “every cat that barks” and the predicate is “has a PhD.” In logic,
we can combine simple propositions to form compound propositions using logical
connectives. Some of the most common connectives are “or”, “and”, “but”, “unless”, etc.
Definition 3
Let p and q be given propositions. The CONJUNCTION of p and q is the proposition “ p and q”,
denoted by p ∧ q, which is true only when both p and q are true.

In other words, if one of p or q is false, then p ∧ q is false. We summarize this idea

using the following table.

p q p ∧q Such a table is called a TRUTH table for p ∧q.

1 1 1 The truth table above illustrates the different
combinations of truth values for p and q and
1 0 0
the corresponding truth value for the
0 1 0 conjunction.
0 0 0
 Example 3. Given the propositions.
p : 3 is odd. (T)
q : Elephants are mammals. (T)
r : Philippines is a first world country. (F)

We know that p and q are true and r is false. Therefore,

p ∧ q : 3 is odd and elephants are mammals. is True

While,
p ∧ r : 3 is odd and Philippines is a first world country. is False
For a more complicated example, the proposition

(¬ p) ∧ (¬ r) : Neither 3 is odd nor Philippines is a first world country.

is still False, since ¬ p is False.
Definition 4
Let p and q be given propositions. The DISJUNCTION of p and q is the proposition “ p or q”,
denoted by p ∨ q, which is false only when both p and q are false.

In other words, if one of p or q is true (or both), then p ∨ q is true. The truth table for p ∨ q
is given below.
Example 4. Consider the statements p, q and r in
the preceding example. The statement
p q p ∨q
1 1 1 p ∨ q : Either 3 is odd (T) or elephants are
1 0 1 mammals (T). (is true)
Also,
0 1 1
0 0 0 p ∨ r : Either 3 is odd (T) or Philippines is
a first world country (F): (is true)
Example 5. The proposition “Either 3 is odd or there is life in other planets.” is
technically true since the component “3 is odd.” is a true proposition. Whether the
proposition “There is life in other planets.” is true or false, the disjunction is always
true
Example 6. Construct a truth table for the compound statement p ∨ (q ∧ (¬ r)).
p q r ¬ r q ∧ (¬ r ) p ∨ (q ∧ (¬r ))
Solution: 1 1 1 0 0 1
Since each of p,q and r
1 1 0 1 1 1
may assume the distinct truth values
then there are a total of 2 x 2 x2= 8 1 0 1 0 0 1
combinations, hence the truth table 1 0 0 1 0 1
must contain eight rows as shown
0 1 1 0 0 0
0 1 0 1 1 1
0 0 1 0 0 0
0 0 0 1 0 0
The following is the truth table for p −→ q.

p q p −→ q In the proposition p ⎯→ q, the proposition p is

also called as the premise, hypothesis or
1 1 1 antecedent and q is called as the conclusion or
1 0 0 consequent.

0 1 1 From the truth table, we can see that a

conditional statement is trivially true when the
0 0 1 premise is false.
Example 7. Suppose that your mother exclaims “If you don’t wash the
dishes, then you don’t get money for a buffet.” In this conditional
statement, the premise is “You don’t wash the dishes.” and the
conclusion is “you don’t get money for a buffet.” This statement can only
false only when you don’t wash the dishes but you still get money for
the buffet.

Note that there are many ways to say p −→ q aside from “If p, then q.”
Alternatively, we can say “q if p” or “p implies q”, “p is sufficient for q” or “q is
necessary for p.”
Example 8. Given the statements p : “ı is irrational.” and
q : “3 is less than 2.”, then

p −→ q : If ı is irrational, then 3 is less than 2.

the converse of this conditional is
q −→ p : If 3 is less than 2, then ı is irrational.
the inverse is

(¬ p) −→ (¬ q) : If ı is not irrational, then 3 is not less than 2.

and the contrapositive is

(¬ q) −→ (¬ p) : If 3 is not less than 2, then ı is not irrational.
If we assume that p is true and q is false (just like how they really are in
mathematics), one verifies that both p −→ q and (¬ q) −→ (¬ p) are false,
while both q −→ p and (¬ p) −→ (¬ q) are true.

We like to emphasize that we write the negation of “ı is irrational” as “ı is

not irrational” to emphasize the fact that we actually don’t assume that
the opposite of being irrational is being rational, unless otherwise stated.
p q p↔q
1 1 1
1 0 0
0 1 0
0 0 1
Example 9. The compound statement p ∨ (¬ p) is a
tautology and the compound statement p ∧ (¬ p) A compound proposition is called
a tautology if it is always true, no
is a contradiction. This can be observed by looking
matter what the truth values
at the truth table below. of the propositions
p ¬ p p ∨ (¬ p) p ∧ (¬ p) A compound proposition is
called a contradiction if it is
1 0 1 0 always false, no matter what the
0 1 1 0 truth values of the propositions

a proposition that is neither a

tautology nor a contradiction
is called a contingency.
 Example 10. By constructing truth tables, show that (p =⇒ p ∨ q) and (p ∧ q =⇒ p).
p q p ∨ q p ∧ q p −→ (p ∨ q) (p ∧ q) −→ p
1 1 1 1 1 1
1 0 1 0 1 1
0 1 1 0 1 1
0 0 0 0 1 1

In logic, the implication p =⇒ (p ∨ q) is called as the law of addition and the implication (p ∧ q) =⇒ p is
the law of simplification.
Assessments 2:
1. Write each statement in words. Let p: The plane is on time. Let q: The sky is clear.
a) p ∧ (¬ q)
b) q → (p ∨ ¬p)
c) p↔q
d) p → q
2. Construct a truth table for each proposition.
a) p → ¬q
b) [(p ∧ ¬ q) → r
c) (p ∧ q) ∨ r ] ↔ [(p ∧ r ) ∨ (q ∧ r )]
d) [(p ∧ r ) → (q ∧ ¬r )] → [(p ∧ q) ∨ r )]

3. Using the truth table prove that the following propositions are logically
equivalent: p ∨ (q ∧ r) ⇐⇒ (p ∨ q) ∧ (p ∨ r)
4. Prove the De Morgan’s Laws by constructing truth tables.
What is
Sets?
A set in mathematics is a collection of well defined and distinct objects, considered as an object in
its own right. Sets are one of the most fundamental concepts in mathematics.

A collection is well-defined if for any given object we can objectively decide whether it is or
is not in the collection. Any object which belongs to a given set is said to be an element of
or a member of the given set.

Example 11.

1. The collection of all letters in the English Alphabet is a set.

2. The collection of all handsome guys is not a set, because one cannot objectively identify
if a given guy is handsome or not, because the word “handsome” is subjective in nature.
Upper case letters are usually used to name sets. A set A can be commonly
described in three ways, by
a) listing (roster) method,
b) set-builder notation or
c) descriptive method.
The listing method describes the set by listing all the elements between braces
and separated by commas (note: in enumerating the elements of a certain set,
each element is listed only once and the arrangement of elements in the list is
immaterial).
The set-builder notation uses a variable (a symbol, usually a letter, that can
represent different elements of a set), braces, and a vertical bar | that is read
as "such that". This is usually used when the elements are too many to list
down. The descriptive method uses a short verbal statement to describe the
set.
 Example 12. Using the roster method, the set of months in a year that ends with
letter ‘y’ can be represented by {January, February, May, July}.

Example 13. The set {2, 3, 4, 5, 6, 7, 8, 9} in set-builder notation is

{x | x is an integer greater than 1 but less than 10}.

If a is an element of a set A, we write a ∈ A. Otherwise, we write a ∉ A. There are

sets with no elements. Such a set is said to be empty and we use the symbol Ø or { } to
denote the empty set. A set with only one element is called a unit set or a singleton.

Example 14. The set of integers between 1 and 2 is empty, while the set of even
prime numbers is a singleton.
For future discussion, we will use the following notations:

• N for the set of natural or counting numbers (positive integers): {1, 2, 3,…}
• Z for the set of integers: {…−4, −3, −2, −1, 0, 1, 2, 3…}
• Q for the set of rational numbers: { a/b| a, b ∈ Z, b ≠ 0}
• R for the set of real numbers

A set A is said to be finite if it is possible to list down all the elements of A in a list.
Otherwise, A is said to be infinite. If A is finite, the cardinality of A is the number of
elements of A, which is denoted by n(A).

Example 15. The set of all letters in the English Alphabet is finite and its
cardinality is 26, because there are 26 distinct letters in the English alphabet. On
the other hand, the set of all even integers in infinite.
Definition 10
Let A and B be sets. We say that A is a subset of B and write A⊆B if every element
of A is an element of B. We say that A and B are equal and write A = B if A ⊆ B and
B ⊆ A.
Remarks.
1. For any set A, A⊆A and Ø ⊆A.
2. If A and B are finite sets and A=B, then n(A) = n(B).

Example 16. Let A be the set of all mathematicians 20 feet high and B be the set of all
PUP students. Then A = Ø. By Remark (1) above, A ⊆ B. Therefore, we can conclude that
every mathematician 20 feet high is a PUP student.

Two finite sets A and B are said to be equivalent if and only if n(A) = n(B). Note that equal
sets are necessarily equivalent but equivalent sets need not be equal.
Example 17. Let A = {x | x is a prime number less than 20} and B = {1, 2, 3, 4, 5, 6,7, 8} are equivalent
since n(A) = 8 = n(B), however, A ≠ B.

Definition 11
Let A and B be sets. The union of A and B is defined as
A ∪ B = {x | x ∈ A or x ∈ B}.
The intersection of A and B is
A ∩ B = {x | x ∈ A and x ∈ B}
Then relative complement of B in A is the set
A \ B := {x ∈ A | x ∈= B}.
We could represent A ∪ B, A ∩ B, and A \ B in terms of Venn Diagrams as shown below.
Example 18. Let A = {0,1,3,5,7} and B = {1,2,4,7,9}.
Then A ∪ B = {0,1,2,3,4,5,7,9},
A ∩ B = {1,7} and
A \ B = {0,3, 5}.

In most of the interesting instances in mathematics, we normally talk about a

particular set of objects at a given time. The set of all objects of interest is called as
the universal set, generically denoted as U. If A⊂U, the complement of A is defined
as the set
A ʹ = U \ A = { x ∈ U ∈ x ∈= A }
Using the De Morgan’s Law of logic, one can readily verify that

(A∪B) ʹ =A ʹ∩B ʹ and (A∩B) ʹ =A ʹ∪B ʹ

We can use our knowledge of sets to solve some word problems using Venn Diagram
Example 19. At a certain high school, each student is a member of the English Club, the Science Club, or
the Mathematics Club. Of the 79 students asked, 33 are members of the English Club, 37 are members of
the Math Club, and 37 are members of the of the Science club. Furthermore, 7 are members of both the
English and the Math Clubs, 12 are members of both the English and the Science Clubs, and 9 are
members of the Science and Math Clubs. No high school student is a member of all the three clubs. How
many joined only the Math Club?

Solution Let E, S, and M denote the sets of members of English, Science, and Mathematics Club,
respectively. As given in the problem, the universal set U has cardinality n(U ) = 79, n(E) = 33, n(M)=37,and
n(S)=37.

Furthermore, n(E∩M)=7,n(E∩S)=12,and n(S∩M)=9. The last condition imply that E ∩ S ∩ M = Ø. This

situation can be represented by the following Venn diagram.
Since n(E ∩ S ∩ M) = 0, then the number of students who only joined the
Mathematics Club is n(M) − n(E ∩ M) − n(S ∩ M) = 37 − (7 + 9) = 21.
 EXAMPLE 19.
A survey of faculty and graduate students at the
University of Florida's film school revealed the
following information:
Given: SOLUTION
51 admire Moe Step 1:
49 admire Larry We will organize the information in the
60 admire Curly following Venn diagram, where "M," "L,"
34 admire Moe and Larry and "C" represent the sets of those who
32 admire Larry and Curly admire Moe, Larry and Curly, respectively:
36 admire Moe and Curly
24 admire all three of the Stooges
1 admires none of the Three Stooges

Answer the ff. questions

a) How many people were surveyed?
b) How many admire Curly, but not Larry nor Moe?
c) How many admire Larry or Curly?
d) How many admire exactly one of the Stooges?
e) How many admire exactly two of the Stooges?
 Step 2: Step 3: Step 4:
"24 admire all three of the "1 admires none of the Three "36 admire Moe and Curly:"
Stooges:" Stooges:"

Step 5: Step 6: Step 7:

"32 admire Larry and Curly: "34 admire Moe and Larry:" "60 admire Curly:"
 Step 9:
Step 8:
"49 admire Larry"
"51 admire Moe"

Now that we have one a) How many people were surveyed?

number in each of the We add all eight numbers.
diagram's eight regions, we
use the numbers to answer 5 + 10 + 7 + 12 + 24 + 8 + 16 + 1 = 83 ans.
the given questions.
b) How many admire Curly, but not Larry nor c) How many admire Larry or Curly?
Moe? Unless we specify otherwise, we always use the word
These are the ones who are simultaneously "or" in the inclusive sense, so that this means "admire
inside of circle C yet outside of the other two Larry, or admire Curly, or admire both." Those who
circles. The diagram shows that the answer is satisfy this compound condition are underlined in the
"16." diagram below.

10 + 7 + 24 + 8 + 12 + 16 = 77 ans.
d) How many admire exactly one of the e) How many admire exactly two of the Stooges?
Stooges? Again, there are three possibilities: admires Moe
There are three possibilities: admires Moe but and Larry but not Curly, admires Moe and Curly
not Curly and not Larry, admires Larry but not but not Larry, or admires Larry and Curly but not
Curly and not More, or admires Curly but not Moe. Those who satisfy this compound condition
Moe and not Larry. Those who satisfy this are in the regions underlined below:
compound condition are underlined in the
diagram below.
Given: M=51
24+12+10=46
51- 46= 5

Given: L=49
24+10+8=42
49 – 42= 7

Given: C=60 12 + 10 + 8 = 30 ans.

24+12+8=44
5 + 7 + 16 = 28 ans. 60 – 44= 16
 Assessments 2.1
1. Let U = {1 ,2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 26, 27, 30}

A = {2, 4, 6, 8, 10, 12, 14} 2. A survey of 90 customers was taken at Barnes & Noble regarding
B= {3, 6, 9, 12, 15, 18, 21} the types of books purchased. The survey found that 44 purchased
C= { 1, 3, 9, 15, 21, 24, 27, 30}
mysteries, 33 purchased science fiction, 29 purchased romance
Determine the following: novels, 13 purchased mysteries and science fiction, 5 purchased
a) A∩B science fiction and romance novels, 11 purchased mysteries and
romance novels, and 2 purchased all three types of books (mysteries,
b) A\ B
science fiction, romance novels). How many of the customers
c) A ∪ (B ∩ C ) surveyed purchased
d) (A ∪ B)‹ ∩ C
Determine the following:
e) (A ∩ C ) ∪ (B ∩ C )
a) mysteries only?
f) A ∩ (C ∩ U )‹
g) n[ (A ∪ B) ∩ (B ∪ C )] b) mysteries and science fiction, but not romance novels?
c) mysteries or science fiction?
d) romance novels or mysteries, but not science fiction?
e) exactly two types (mysteries, science fiction, romance novels)?