SAMAR COLLEGES INC.

Samar College Technological Institute

MODULE IN

DISCRETE MATHEMATICS
Chapter 1 — Propositions and Connectives

Prepared by
JOHANNA C. FLORA
SAMAR COLLEGES INC. — Samar College Technological Institute Discrete Mathematics

Chapter 1: Propositions and Connectives

Logic and mathematical reasoning has numerous applications in computer science. Rules in
logic are used in the design of computer circuits, the development of computer programs, the
verification of the correctness of programs, and many other ways.

Propositions
Let us begin with the basic building blocks of logic — propositions. A proposition is a
declarative sentence that is either true or false, but not both.

Examples
All the following declarative sentences are propositions.
1. 3 is an odd integer.
2. Quezon City was once the capital of the Philippines.
3. 12 ÷ 4 = 3.
4. √3 is an integer.
Propositions 1, 2, and 3 are true, whereas 4 is false.
Some sentences that are not propositions are given below.
1. Who are you talking to?
2. Read this sentence carefully.
3. x + 4 = 7
4. u + v = w
Sentences 1 and 2 are not propositions because they are not declarative sentences. Sentences
3 and 4 are not propositions because they are neither true nor false.
An acceptable proposition is given the decision value true (or 1), while an unacceptable
statement is assigned a decision value false (or 0). An array of decision value (truth value) is
called a logical matrix (or truth table).
The area of logic that deals with propositions is called propositional logic. The bases for
propositional logic are the three laws of Aristotelian logic. These are:
1. Law of Identity. “A thing is itself.”
2. Law of Excluded Middle. “A statement is either true or false but not both.”
3. Law of Non-Contradiction. “No statement is both true and false.”

Logical Operators
Many mathematical statements are constructed by combining one or more propositions. These
new propositions are formed from existing propositions using logical operators. The logical

Prepared by Johanna C. Flora Page 2

SAMAR COLLEGES INC. — Samar College Technological Institute Discrete Mathematics

operators that are used to form new propositions from two or more existing propositions are
called connectives.

Negation
Definition. Let p be a proposition. The statement “It is not the case that p” is another
proposition, called the negation of p, denoted by ¬p. The proposition ¬p is read “not p”.

Example
The negation of the proposition
“5 is positive.”
is
“It is not the case that 5 is positive.”
or
“5 is not positive.”
The truth value of a true proposition is T or 1. The truth value of a false proposition is F or 0.
A truth table or truth matrix displays the relationships between the truth values of propositions.
Table 1. The Truth Matrix of the Negation of a Proposition
p ¬p
1 0
0 1

Conjunction
Definition. Let p and q be propositions. The proposition “p and q” denoted by p ∧ q, is the
proposition that is true when both p and q are true and is false otherwise. The proposition p ∧ q
is called the conjunction of p and q.

Examples
1. Consider the following statements:
p: 2 is an even integer.
q: 3 is an odd integer.
The conjunction of these propositions, p ∧ q, is the proposition
“2 is an even integer and 3 is an odd integer.”
2. Let
p: 3 divides 9.
q: 3 divides 15.
p ∧ q, is the proposition,

Prepared by Johanna C. Flora Page 3

SAMAR COLLEGES INC. — Samar College Technological Institute Discrete Mathematics

“3 divides 9 and 3 divides 15.”

or
“3 divides both 9 and 15.”
Let
p: √4 is a rational number
q: √2 is not a rational number
p ∧ q, is the proposition
“√4 is a rational number and √2 is not a rational number.”
or
“√4 is a rational number but √2 is not a rational number.”
Table 2. The Truth Matrix for the Conjunction of Two Propositions
p q p∧q
1 1 1
1 0 0
0 1 0
0 0 0

Disjunction
Definition. Let p and q be propositions. The proposition “p or q”, denoted by p ∨ q, is the
proposition that is false when both p and q are false and true otherwise. The proposition p ∨ q is
called the disjunction of p and q.

Example
Let
p: Students who have taken algebra can take Discrete Mathematics.
q: Students who have taken computer science can take Discrete Mathematics.
The disjunction of the propositions p and q is, p ∨ q,
“Students who have taken algebra or computer science, but not both, can take discrete
mathematics.”
Table 3. The Truth Matrix for the Disjunction of Two Propositions
p q p∨q
1 1 1
1 0 1
0 1 1
0 0 0

Prepared by Johanna C. Flora Page 4

SAMAR COLLEGES INC. — Samar College Technological Institute Discrete Mathematics

Implication
Definition. Let p and q be propositions. The implication p → q is the proposition that is false
when p is true and q is false, and true otherwise. In this implication p is called the premise or
the hypothesis, and q is called the consequence or conclusion.
The implication p → q can be expressed in the following:
• “if p then q”
• “p implies q”
• “p is sufficient for q”
• “a necessary condition for p is q”
• “q is necessary for p”
• “q follows from p”

Examples
1. If all men are mortal then Mario is mortal. (Logical implication)
2. If this polygon is a quadrilateral then it has four sides. (Definitional implication)
3. If today is Monday then tomorrow is Tuesday. (Sequential implication)
4. If sugar is placed in water, it will dissolve. (Causal implication)
5. If x = 0 → y = 10, x ≠ 0 → y ≠ 10. (Material implication)
Table 5. The Truth Matrix for Implication
p q p→q
1 1 1
1 0 0
0 1 1
0 0 1

Converse, Contra-positive, and Inverse

There are some related implications that can be formed from p → q.
• The proposition q → p is called the converse of p → q.
• The proposition ¬q → ¬p is called the contra-positive of p → q.
• The proposition ¬p → ¬q is called the inverse of p → q.

Example
What are the contra-positive, the converse and the inverse of the implication
“The price of crude oil goes up whenever the US goes to war”

Prepared by Johanna C. Flora Page 5

SAMAR COLLEGES INC. — Samar College Technological Institute Discrete Mathematics

This proposition can be expressed in the if-then form

“If the US goes to war, then the price of crude oil goes up.”
Consequently, the contra-positive of this implication is
“If the price of crude oil does not go up, then the US does not go to war.”
The converse is
“If the US goes to war, then the price of crude oil goes up.”
The inverse is
“If the price of crude oil does not go up, then the US does not go to war.”

Bi-Conditional
Definition. Let p and q be propositions. The bi-conditional p ↔ q is the proposition that is true
when p and q have the same truth values, and is false otherwise.
p iff q
q iff p, or
p implies q and q implies p

Examples
1. The curve is a circle if and only if the curve is equidistant to a point.
2. The polygon is a triangle if and only if it has three sides.
3. 68,295 is divisible by 15 if and only if 68,295 is divisible by 3 and 5.
Table 6. The Truth Matrix for Bi-Conditional
(p → q)
∧ (q →
p q p→q q→p
p) = p ↔
q
1 1 1 1 1
1 0 0 1 0
0 1 1 0 0
0 0 1 1 1

Exclusive Or
Definition. Let p and q be propositions. The exclusive or of p and q denoted by p ⊕ q is the
proposition that is true when exactly one of p and q is true and is false otherwise.

Example
Either you can have a glass of milk or a glass of orange juice for breakfast.
Table 7. The Truth Matrix for Exclusive Or

Prepared by Johanna C. Flora Page 6

SAMAR COLLEGES INC. — Samar College Technological Institute Discrete Mathematics

p q p⊕q
1 1 0
1 0 1
0 1 1
0 0 0

Major Connective
When two or more connectives are present in a statement, one of them is the dominant or major
connective. The major connective is shown by using parentheses.

Examples
1. In the statement “x = 1 or x = 2, and y = 3”, the major connective is conjunction.
2. (s ∧ t) → r, implication
3. [(p → q) ∧ (q → r)] ∨ q, disjunction
4. (x = 0) ∨ (x > 0 ∧ y ≠ 1), disjunction
5. [(x = 1) ∨ (x > 1) → (y = 4)] ∧ (y < z), conjunction

Expression Trees
An expression tree is a visual representation for the way that a compound proposition is built
from propositions and logical connectives. A proposition is represented by a single node.

Examples
1. Representation for p ∧ q
p ∧ q
/ \
p q

2. Expression tree of p ∧ (q ∧ r)
p ∧ (q ∧ r)
/ \
p q ∧ r
/ \
q r

3. The expression tree of (¬p) → (p ∨ q)

(¬p) → (p ∨ q)

Prepared by Johanna C. Flora Page 7

SAMAR COLLEGES INC. — Samar College Technological Institute Discrete Mathematics

/ \
¬p (p ∨ q)
| / \
p p q

Prepared by Johanna C. Flora Page 8

SAMAR COLLEGES INC. — Samar College Technological Institute Discrete Mathematics

Exercises

Exercise 1.1
A. Which of these sentences are propositions? What are the truth values of those that are
propositions?
1. Today is Friday.
2. On January 6, 2008, the temperature of Baguio City dropped to 10° C.
3. √4 is an even integer.
4. Why should you take discrete mathematics before automata?
5. There is an integer x such that x² = 4.
6. Answer this question.
7. 2 + 6 = 8
8. 5 − 7 > 4
9. Do not disturb.
10. x + 7 ≥ 9
B. Which of these sentences are propositions? What are the truth values of those that are
propositions?
1. x + y = 12
2. Hold on to your wit.
3. 5 + 4 < 10
4. 6 − 1 ≤ 8
5. f(x) − g(x) = 2x + 3
6. Dengue fever are prevalent in the slum communities.
7. Ceres is the ninth planet in our solar system.
8. 3ⁿ ≥ 8100.
9. Why are you here?
10. Give me the cards.

Exercise 1.2
A. Write the negations of each of these propositions.
1. Today is Monday.
2. The air in Metro Manila is polluted.
3. Summer in Davao City is hot and sunny.
4. 2 + 1 > 5

Prepared by Johanna C. Flora Page 9

SAMAR COLLEGES INC. — Samar College Technological Institute Discrete Mathematics

5. It is hot.
B. Write the negations of each of these propositions.
1. x + y = 4
2. Sierra Madre mountains are denuded.
3. a × b > 6
4. It’s raining in August.
5. It is cold in December.

Exercise 1.3
A. Let p and q be propositions
p: 4 is a rational number.
q: √3 is an irrational number.
Express each of these propositions as an English sentence:
1. ¬p
2. p ∨ q
3. p ∧ q
4. p → q
5. p ↔ q
B. Let p and q be propositions.
p: Cristina is a computer science major.
q: Leonardo is an Information Technology major.
Express each of these propositions as an English sentence:
1. ¬q
2. ¬p ∧ q
3. ¬p → ¬q
4. p ↔ q
5. ¬q ∨ (¬p ∧ q)

Exercise 1.4
A. Let p and q be propositions
p: 4 is an even integer
q: 5 is an odd integer
Write each of the following sentences in terms of p, q and logical connectives:
1. 4 is an even integer and 5 is an odd integer.

Prepared by Johanna C. Flora Page 10

SAMAR COLLEGES INC. — Samar College Technological Institute Discrete Mathematics

2. 4 is not an even integer or 5 is an odd integer.

3. If 4 is an even integer then 5 is an odd integer.
4. 4 is an even integer whenever 5 is an odd integer.
5. 4 is not an even integer if and only if 5 is not an odd integer.
B. Let p and q be propositions
p: You make a correct program
q: You get an A.
Write each of the following sentences in terms of p, q and logical connectives.
1. You do not make a correct program.
2. You make a correct program, but you do not get an A.
3. Making a correct program is sufficient for getting an A.
4. You get an A but you do not make a correct program.
5. Whenever you get an A, you are making a correct program.

Exercise 1.5
A. Write in the form “if p then q”, then write the converse, inverse and contra-positive of each of
the following implications.
1. It is necessary to do your homework to get a passing grade.
2. A low pressure area imply a coming storm.
3. A sufficient condition for the warranty to be good is that you bought the iPod less than a
year ago.
4. You can access the school WIFI only if you are enrolled.
5. Mark gets a high grade whenever he studies his lesson.
B. Write in the form “if p then q”, then write the converse, inverse and contra-positive of each of
the following implications.
1. For you to get a 10, it is necessary that you learn how to solve mathematics problem.
2. You get promoted only if you work hard.
3. A positive integer is a prime only if it has no divisor other than 1 and itself.
4. If it rains today, I will stay home and read my lessons.
5. If you read your lessons everyday, you will pass all your courses.

Exercise 1.6
A. Construct a truth table (truth matrix) for each of these compound propositions.
1. p ∧ ¬q
2. p → ¬p

Prepared by Johanna C. Flora Page 11

SAMAR COLLEGES INC. — Samar College Technological Institute Discrete Mathematics

3. (p ∨ q) → (p ∧ q)
4. (p ∨ q) → r
5. (p ∨ q) ∧ ¬r
B. Construct a truth table (truth matrix) for each of these compound propositions.
1. p ⊕ ¬q
2. (p → q) ⊕ (¬p → q)
3. p ⊕ (q → r)
4. (p ↔ q) ∨ (¬p → r)
5. (¬p ↔ ¬q) ↔ (q ↔ p)

Exercise 1.7
A. Let proposition p be T and proposition q be F. Find the truth value of the following.
1. p ∧ ¬q
2. ¬p ∨ q
3. p → q
4. ¬q ↔ p
5. ¬p ⊕ q
B. Let proposition p be T and proposition q be F. Find the truth value of the following.
1. p ∧ (¬p ∨ q)
2. ¬p ∨ (p → q)
3. (p ∨ ¬q) → q
4. ¬(p → q) ↔ p
5. ¬(¬p ∧ ¬q) ⊕ (q → ¬p)

Exercise 1.8
A. Draw the expression trees of each of the following:
1. (p ∨ q) ∧ r
2. (p ∧ q) → r
3. p ∧ ¬(¬(p → q))
4. ((p → q) ↔ r) ∨ p
5. (¬q ∨ r) → (q → r)

Prepared by Johanna C. Flora Page 12