Republic of the Philippines

Cagayan State University

SANCHEZ MIRA CAMPUS
Sanche Mira, Cagayan

COLLEGE of INFORMATION and COMPUTING SCIENCES

MODULE I: DISCRETE STRUCTURES AND PROPOSITIONAL LOGIC

LESSON 1: o Introduction to Discrete Structures
LESSON 2: o Propositional Logic
LESSON 3: o Truth Table
LESSON 4: o Tautologies and Logical Equivalence

OBJECTIVES: At the end of the lesson the students will be able to:

 Explain the definition of discrete mathematics;

 Distinguish if a given sentence is a proposition or not;
 Convert English statements in symbolic form and
vice versa;
 Show whether two propositions are logically
equivalent using a truth table;
 Prove the validity of an argument using any of the
proof techniques.

LESSON 1

Discrete Structures

– Theoretical basis of computer science

– A mathematical foundation that makes you think logically
– A prerequisite course to understand the fundamentals of programming

Examples of discrete structures:

sets, permutations, relations, graphs, trees, and finite state machines, etc.

Why Study Discrete Structures?

 It discusses languages used in mathematical reasoning, basic concepts, and

their properties and relationships among them.
 It is also concerned with techniques to solve certain types of problems such
as how to count or enumerate quantities.
 It helps you form a logical basis to decompose a given problem into
statements that make sense.

1
 Republic of the Philippines
Cagayan State University
SANCHEZ MIRA CAMPUS
Sanche Mira, Cagayan

COLLEGE of INFORMATION and COMPUTING SCIENCES

Discrete Mathematics

Discrete math is mathematics that deals with the study of discrete objects and the
concepts associated with them, their properties, and relationships among them.

Discrete objects are those which are separated/distinct from each other

Examples of discrete objects:

integers, rational numbers, steps taken by a computer program, houses,
people, etc.

LESSON 2

Propositional Logic

Logic is the study of reasoning; it is specifically concerned with whether

reasoning is correct. Logic focuses on the relationship among statements.

Proposition is a declarative statement which is either true or false.

Examples:
Manila is the capital of Philippines
5 is a prime number
8 is an odd number
20 is greater than 12

Propositional logic
- is logic that deals with statements that are either true or false.

FINDING THE TRUTH VALUE

If a proposition is true, it has a truth value of "true"; if a proposition is false, its truth value is
"false".

Exercises:
Which of the following do you think are propositions?

a. Philippines is in Asia
b. Grass is Green

2
 Republic of the Philippines
Cagayan State University
SANCHEZ MIRA CAMPUS
Sanche Mira, Cagayan

COLLEGE of INFORMATION and COMPUTING SCIENCES

c. How old are you?
d. Paris is the capital of France
e. Go to the beach
f. All cows are brown
g. Merry Christmas!
h. There is life on Mars
i. x + 2 = 2x
j. +2=5

Elements of Propositional Logic

Simple sentences which are true or false are basic propositions. Larger and more
complex sentences are constructed from basic propositions by combining them with
connectives. Thus, propositions and connectives are the basic elements of propositional
logic.

Five Basic Connectives:

1. NOT( )
2. AND( )
3. OR( )
4. IF-THEN(IMPLY) (→ )
5. IF AND ONLY IF( ↔)

Common Logical Connectives

**Note: P and Q are statements/propositions

1) Negation

The negation of a statement is also a statement with a truth value that is exactly
opposite that of the original statement.

Symbol: ~ or ¬ is read as NOT

Example: ~P or ¬P is translated as “not P” or “it is not true that P“

Rule for Negation:

The truth value of a negated statement is the exact opposite of the truth value of the
original statement.

2) Conjunction

A conjunction is a type of compound statement that is comprised of two propositions

(also known as simple statements) joined by the AND operator.

3
 Republic of the Philippines
Cagayan State University
SANCHEZ MIRA CAMPUS
Sanche Mira, Cagayan

COLLEGE of INFORMATION and COMPUTING SCIENCES

Symbol: ∧ is read as AND

Example: P∧Q is translated as “P and Q“

Rule for Conjunction:

The RESULT is TRUE if the statements are all true. Otherwise, the statement is FALSE.

3) Disjunction or Inclusive OR

A disjunction is a kind of compound statement that is composed of two simple

statements formed by joining the statements with the OR operator.

Symbol: ∨ is read as OR
Example: P∨Q is translated as “P or Q“

Rule for Disjunction:

The RESULT is TRUE if there’s one TRUE among the statements, which means, the result will
only become FALSE if all statements are false.

4) Implication or Conditional

An implication (also known as a conditional statement) is a type of compound

statement that is formed by joining two simple statements with the logical implication
connective or operator.

Symbol: → is read as IMPLIES

Example: P→Q stands for the statement “P implies Q“

 where P is known as the hypothesis

 where Q is known as the conclusion

There are many ways how to read the conditional P→Q. Below are some of the few
common ones.

 P→Q is read as “P implies Q“.

 P→Q is read as “If P then Q“.
 P→Q is read as “P only if Q“.
 P→Q is read as “If P is sufficient for Q“.
 P→Q is read as “Q is necessary for P“.
 P→Q is read as “Q follows from P“.
 P→Q is read as “Q if P“.

4
 Republic of the Philippines
Cagayan State University
SANCHEZ MIRA CAMPUS
Sanche Mira, Cagayan

COLLEGE of INFORMATION and COMPUTING SCIENCES

Rule for Implication:

The truth value of the compound statement is true when both are true and if P is false.
Otherwise, the result will become FALSE.

5) Double Implication or Biconditional

A double implication (also known as a biconditional statement) is a type of compound

statement that is formed by joining two simple statements with the biconditional
operator. A biconditional statement is really a combination of a conditional statement
and its converse.

Symbol: ↔ is read as IF AND ONLY IF

Example: P↔Q stands for the statement “P if and only if Q“

Rule for Biconditional:

The truth value of the biconditional statement is TRUE when both simple statements are
both true or both false. Otherwise, the result is FALSE.

LESSON 3

TRUTH TABLE

Definition of a Truth Table

In math logic, a truth table is a chart of rows and columns showing the truth value
(either “T” for True or “F” for False) of every possible combination of the given
statements (usually represented by uppercase letters P, Q, and R) as operated by
logical connectives.

Two Components of a Truth Table

I. Statement
A statement is a sentence or mathematical expression that is either definitely true or
definitely false but not both. It is usually denoted by an uppercase letter or variable. The
common ones are P, Q, R and S.

II. Logical Connective

A logical connective is a word usually written as a symbol that carries a particular

instruction of logic on how to operate a statement or compound statement. Logical

5
 Republic of the Philippines
Cagayan State University
SANCHEZ MIRA CAMPUS
Sanche Mira, Cagayan

COLLEGE of INFORMATION and COMPUTING SCIENCES

connectives can also be used to join or combine two or more statements to form a new
statement.

OPEN SENTENCE

An open sentence is a sentence that is either true or false depending on the value of
the variable(s). This kind of sentence is NOT a proposition because it must be definitely
true or definitely false.

Examples:
- The number k is even.
Notice, the sentence is true if k=4k=4 or false if k=7k=7. Since the truth value of
the sentence can be true or false depending on the value of the variable k, then
it is an open sentence, and thus not a proposition.

6
 Republic of the Philippines
Cagayan State University
SANCHEZ MIRA CAMPUS
Sanche Mira, Cagayan

COLLEGE of INFORMATION and COMPUTING SCIENCES

The following examples demonstrate the process of converting English statements in
symbolic form:

Assume that we have the following statements:

p: I will go to Manila s: the topic is interesting

q: I have money m: I will learn a lot
r: I will attend a seminar n: the speaker is intelligent

English Statement Symbolic Form

1. I will not go to Manila p
2. If I have money then I will go to Manila and I will qp r
attend a seminar
3. Neither I will go to Manila nor I will attend a seminar (p r)
4. Either the topic is interesting or the speaker is (s n)m
intelligent then I will learn a lot
5. I will go to Manila if and only if I have money p q

The examples below translate symbolic propositions into words

Symbolic Form English Statement

1. n r The speaker is not intelligent or I will attend a seminar
2. p (q r) I will go to manila if and only if I have money and I will
attend a seminar
3. n sm If the speaker is intelligent and the topic is interesting then
I will learn a lot
4. r p q I will attend a seminar or I will go to Manila and I have
money