MODULE 2: LOGIC

The Foundation: Logic, Sets, and Function

Prepare by:

Mary Grace M. Nebab

College Instructor

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 = 5.
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