ITM 201: DISCRETE MATHEMATICS

Module 1
The Foundation: Logic, Sets, and Function

Prepare by:

Mary Grace M. Nebab

Lesson 1: Logic

Introduction

When writing mathematical ideas, we take care in differentiating TRUE from FALSE statements. For
example, we that for all real numbers a, b and c, if a = b and b = c, then a = c. The reason why such a statement
is true is that it is a property of the set of real numbers.
There is a difference, however, between determining the truth or falsity of a statement based on its
meaning from determining its truth or falsity based on its structure. Sentences consist of nouns, verbs, and
connectives such as and, or, not are important for its structure to be consistent and logical.
The rules in logic give precise meaning to mathematical statements. These rules are used to distinguish
between valid and invalid mathematical arguments.

Definition
Proposition is a declarative sentence that is either true or false, but not both.

Example 1
1. Washington, D.C., is the capital of the United States of America.
2. Toronto is the capital of Canada.
3. 1 + 1 = 2.
4. 2 + 2 = 3.
Propositions 1 and 2 are true, whereas 3 and 4 are false.
Example 2
1. What time is it?
2. Read this carefully.
3. 𝑥 + 1 = 2.
4. 𝑥 + 𝑦 = 𝑧.
Sentences 1 and 2 are not propositions because they are not declarative statements. Sentences 3 and 4
are not propositions since they are neither true nor false.
We use letters to denote propositional variables or statement variables, that is, variables that represent
propositions, just as letters are used to denote numerical variables. Conventional letters for propositional
variables are p, q, r and s.
The area of logic that deals with propositions is called propositional calculus or propositional logic. It
was first developed systematically by the Greek Philosopher Aristotle more than 2300 years ago.
 The truth value of a proposition is TRUE (denoted by T) if it is a true proposition, and FALSE (denoted
by F) if it is a false proposition.
Many mathematical statements are constructed by combining one or more propositions. New
propositions, called compound propositions, are formed from existing propositions using logical operators.

Logical Operators
Definition
Let p be a proposition. The negation of p, denoted by ¬p, is the statement “It is not the case that p.”
The proposition ¬p is read as “not p”. The truth value of the negation of p is the opposite of the truth value of p.

Example
The negation of the statement “Today is Saturday.” is “It is not the case that today is Saturday.”
and can be expressed simply as “Today is not Saturday.”
The following is a truth table for the negation of the proposition p. This table has a row for each of the
two possible truth values of the proposition p. Each row shows the truth value of ¬p corresponding to the truth
value of p in this row.

The negation of a proposition can also be considered as the result of the operation negation operation
on a proposition.
Logical operators that are used to form new propositions from two or more existing propositions is called
connectives.

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

Example
The conjunction of the propositions p and q where p is the proposition “Today is Saturday.” and q is
the proposition “It is raining today.” is “Today is Saturday and it is raining today.”
This proposition is TRUE on rainy Saturdays, and is FALSE on any day that is not Saturday and on
Saturday when it does not rain.
Definition
Let p and q be propositions. The disjunction of p and q, denoted by p ∨ q, is the proposition “p or q”.
The conjunction p ∨ q is FALSE when both p and q are false and TRUE otherwise.

Example
The disjunction of the propositions p and q where p and q are the same propositions as the
previous example is “Today is Saturday or it is raining today.”
This proposition is TRUE on any day that is either a Saturday or a rainy day (including rainy
Saturdays) and FALSE on days that are not Saturday when it also does not rain.

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 FALSE otherwise.

Conditional Statements
Definition
Let p and q be propositions. The conditional statement, denoted by p → q, is the proposition “If p,
then q.” The conditional statement p → q is FALSE when p is true and q is false, and TRUE otherwise.
In the conditional statement p → q, p is called hypothesis (antecedent or premise) and q is called
conclusion (or consequence).

Other Terminologies
 The statement p → q is called a conditional statement because p → q asserts q is true on the condition
that p holds. A conditional statement is also called implication.
Note that the truth value of the conditional statement p → q is TRUE when p is false (whatever the truth
value of q) and when both p and q are true. Since conditional statements play such an important role in
mathematical reasoning, a variety of terminology is used to express p → q:

Example
The statement “If today is Monday, then 2 + 3 = 5.” is TRUE because the conclusion is true. That is,
the truth value of the hypothesis does not matter.
While the statement “If today is Monday, then 2 + 3 = 6.” is true every day except Monday, even
though 2 + 3 = 6 is false.
We can form some new conditional statements from the given conditional statement p → q. In
particular, there are three related conditional statements that occur so often that they have their special names.
1. The proposition q → p is called the converse of p → q.
2. The contrapositive of p → q is the propositions ¬q → ¬p.
3. The proposition ¬p → ¬q is called the inverse of p → q.

Remember:
1. Note that the contrapositive of ¬q → ¬p is FALSE only when ¬q is true and ¬p is false, that is, p is true
and q is false.
2. Now, when p is true and q is false, the conditional statement is FALSE but the converse and inverse
are both TRUE.

When two conditional statements have the same truth value we call them equivalent. Hence, a
conditional statement and its contrapositive are equivalent.
Example:
What are the contrapositive, converse and inverse of the conditional statement “Games are suspended
whenever it is raining.”?
The original statement can be written as “If it is raining, then games are suspended.” Thus,
1. Contrapositive
“If the games are not suspended, then it is not raining.”
2. Converse
“If the games are suspended, then it is raining.”
 3. Inverse
“If it is not raining, then games are not suspended.”

Biconditional Statements
Definition
Let p and q be propositions. The biconditional statement p ↔ q is the proportion “p if and only if q”.
The biconditional statement is TRUE when p and q have the same truth values, and FALSE
otherwise.
Biconditional statements are also called bi-implication.

Example
Construct the truth table of the compound proposition (p ∨ ¬q) → q.
Solutions
Since there are only two propositional variables involve, thus there are 22 = 4 in this truth table,
corresponding to the combinations of truth values, TT, TF, FT, and FF.

p q ¬q p ∨ ¬q (p ∨ ¬q) → q.
T T F T T
T F T T F
F T F F T
F F T T F

fin