Module 1.
Foundations: Logic and Proofs
Learning Objectives:
1. Explain what makes up a correct mathematical argument and introduce tools to construct
these arguments.
2. Develop an arsenal of different proof methods that will enable us to prove many different
types of results.
3. Introduce several strategies for constructing proofs.
4. Introduce the notion of a conjecture and explain the process of developing mathematics
by studying conjectures.
I. The Fundamentals of Logic
a. Propositional Logic
The rules of logic give precise meaning to mathematical statements. These rules are
used to distinguish between valid and invalid mathematical arguments.
Besides the importance of logic in understanding mathematical reasoning, logic are
also used in the design of computer circuits, the construction of computer programs,
the verification of the correctness of programs, and in many other ways.
The area of logic that deals with propositions is called the propositional calculus
or propositional logic. It was first developed systematically by the Greek
philosopher Aristotle more than 2300 years ago.
Definition: Proposition is a declarative sentence (that is, a sentence that declares a fact)
that is either true or false, but not both.
Letters of the alphabet is used to denote propositional variables (or statement
variables), that is, variables that represent propositions, just as letters are used to
denote numerical variables. The conventional letters used for propositional variables
are p, q, r, s, . . . .
P: today is raining
S: bring your umbrella
The truth value of a proposition is true, denoted by T, if it is a true proposition, and
the truth value of a proposition is false, denoted by F, if it is a false proposition.
P ~P
T F
F T
EXAMPLE 1 All the following declarative sentences are propositions.
1. Manila is the capital of the Republic of the Philippines. (True)
2. CMU is the only public university in Metro Manila (False)
3. 1 + 1 = 2.(true)
4. 2 + 2 = 3. (False)
Notice: Propositions 1 and 3 are true, whereas 2 and 4 are false.
EXAMPLE 2 Consider the following sentences.
1. What time is it? Not a Proposition
2. Read this carefully.
3. x + 1 = 2.
4. x + y = z.
Exercises: Identify whether the statement is a proposition or not.
1. “Drilling for oil caused dinosaurs to become extinct.” Proposition
2. “Look out!” Not a proposition
3. “How far is it to the next town?” Not a proposition
4. “x + 2 = 2x” Not a proposition
5. “x + 2 = 2x when x = −2” proposition
6. All cows are brown. Proposition
7. The Earth is further from the sun than Venus. proposition
8. There is life on Mars. proposition
9. 2 × 2 = 5. Proposition
10. Covid 19 pandemic is near to its end. Proposition
Definition: Propositions that are composites that are composed of sub propositions and various
connectives are called compound proposition. A proposition is said to be primitive if it cannot
be broken down into simpler propositions, that is, if it is not composite.
Example 3. Consider the following sentences.
1. The sun is shining today and it is colder than yesterday.
2. Sita is intelligent and she studies every night.
3. I will bring my umbrella if it rains today.
Definition: Let p be a proposition. The negation of p, denoted by￢p (also denoted by p), is the
statement “It is not the case that p.” The proposition ￢p is read “not p.” The truth value of the
negation of p, ￢p, is the opposite of the truth value of p. ~p
EXAMPLE 3. Find the negation of the proposition “Michael’s PC runs Linux” and express
this in simple English.
Solution: The negation is
“It is not the case that Michael’s PC runs Linux.”
This negation can be more simply expressed as
“Michael’s PC does not run Linux.”
EXAMPLE 4 Find the negation of the proposition “Vandana’s smartphone has at least 32GB of
memory” and express this in simple English.
Solution: The negation is
“It is not the case that Vandana’s smartphone has at least 32GB of memory.”
This negation can also be expressed as
“Vandana’s smartphone does not have at least 32GB of memory”
or even more simply as
“Vandana’s smartphone has less than 32GB of memory.”
b. Compound Statements
Exercises 2. Write is the negation of each of these propositions.
1. Mei has an MP3 player.
2. There is no pollution in Japan.
3. 2 + 1 = 3.
4. The summer in Maine is hot and sunny.
5. Jennifer and Teja are friends.
6. There are 13 items in a baker’s dozen.
7. Abby sent more than 100 text messages every day.
8. 121 is a perfect square.
9. Steve has more than 100 GB free disk space on his laptop.
10. Zach blocks e-mails and texts from Jennifer.
