MODULE 1 - DISCRETE STRUCTURES AND PROPOSITIONAL LOGIC
LESSON 1: INTRODUCTION TO DISCRETE STRUCTURES AND PROPOSITIONAL
1.0 Definition of Discrete Mathematics
The study of the measurement, properties, and relationships of
quantities and sets, using numbers and symbols.
Science of structure, order, and relation that has evolved from
counting, measuring, and describing the shapes of objects. It deals with
logical reasoning and quantitative calculation.
the branch of mathematics dealing with objects that can assume only
distinct, separated values.
Discrete mathematics is the mathematical language of computer
science, and as such, its importance has increased dramatically in
recent decades.
study of mathematical structures that are fundamentally discrete rather
than continuous.
1.1 Propositional Logic
Logic is the study of reasoning; it is specifically concerned with
whether reasoning is correct. Logic focuses on the relationship among
statements as opposed to the content of any particular statement.
Propositional logic is logic at the sentential level. It is a part of logic
which deals with statements that are either true or false(but not false),
hence, the smallest unit we deal with propositional logic is a
sentence(proposition).
PROPOSITIONS
A proposition is a declarative statement which is either true or false, but
not both. Clearly, not all sentences are propositions since not all
sentences are declarative.
If a proposition is true, then we say it has a truth value of "true"; if a
proposition is false, its truth value is "false".
Page 1
MODULE 1 - DISCRETE STRUCTURES AND PROPOSITIONAL LOGIC
For example, "Grass is green", and "2 + 5 = 5" are propositions. The
first proposition has the truth value of "true" and the second "false".
But "Close the door", and "Is it hot outside? "are not propositions. Also "x is
greater than 2", where x is a variable representing a number, is not a
proposition, because unless a specific value is given to x we cannot say
whether it is true or false, nor do we know what x represents.
Similarly "x = x" is not a proposition because we don't know what "x"
represents hence what "=" means. For example, while we understand
what "3 = 3" means, what does "Air is equal to air" or "Water is equal to
water" mean? Does it mean a mass of air is equal to another mass or the
concept of air is equal to the concept of air? We don't quite know what
"x = x" mean. Thus we cannot say whether it is true or not. Hence it is not a
proposition.
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( )
MODULE 1 - DISCRETE STRUCTURES AND PROPOSITIONALLOGIC
LESSON 2: TRUTH TABLE
A proposition in general contains a number of variables. For example
(P Q) contains variables P and Q each of which represents an arbitrary
proposition. Thus a proposition takes different values depending on the
values of the constituent variables. This relationship of the value of a
proposition and those of its constituent variables can be represented by a
table. It tabulates the value of a proposition for all possible values of its
variables and it is called a truth table.
a. The connective NOT simply negates the truth value of a proposition. If
a proposition is true, the resulting value is false, if it’s true, then the
resulting value is false.
The truth table of NOT is given below:
P P
T F
F T
b. Definition: Let p and q be propositions
The conjunction of p and q, denoted by p q is the proposition p
and q
The disjunction of p and q, denoted by p q is the proposition p or q
Propositions such as p q and p q that result from combining
propositions are called compound propositions.
Example:
If p: The teacher is good
q: She is beautiful.
Then the conjunction of p and q is
p q : The teacher is good and she is beautiful.
and the disjunction of p or q is
p3 q : The teacher is good or she is beautiful.
Page
MODULE 1 - DISCRETE STRUCTURES AND PROPOSITIONAL LOGIC
The truth value of the compound proposition p q is defined by
the truth table below:
P Q p q
T T T
T F F
F T F
F F F
Notice that in the truth table, all four possible combinations of truth
assignments for p and q are given. The table shows that the conjunction of
p q is true provided that p and q are both true; otherwise, p q is
false.
Example: p : square of 2 is 4; q: a dozen is 24.
In the given propositions, p is true and q is false, therefore p q is
false.
The truth value of the compound proposition p q is defined by the truth
table below:
P Q p q
T T T
T F T
F T T
F F F
The table above shows that the disjunction of p q is false if both
propositions are false; otherwise, p q is true if one or all of the
propositions are true.
Example: p : square of 2 is 4; q: a dozen is 24.
In the given propositions, p is true and q is false, therefore p q is
true.
MODULE 1 - DISCRETE STRUCTURES AND PROPOSITIONALLOGIC
c. Definition: If p and q are propositions, the compound proposition if p
then q is called a conditional proposition and is denoted by p q.
The proposition p is called the hypothesis (antecedent) and the
proposition q is called the conclusion(consequent).
The truth value of the conditional proposition p q is defined by the truth
table below:
P Q P q
T T T
T F F
F T T
F F T
Example: Let p : square of 2 is 4; q: a dozen is 24.
Then p is true and q is false, therefore, p q is false and q p is
true.
d. Definition: If p and q are propositions, the compound proposition
p if and only if q
is called a biconditional proposition and is denoted by pq
The truth value of the proposition is defined by the truth table:
P Q p q
T T T
T F F
F T F
F F T
Example: Let p : square of 2 is 4; q: a dozen is 24.
Then p is true and q is false, therefore, p q is false.
The truth value of a proposition depends exclusively upon the truth values
of its variables, that is, the truth value of a proposition is known once the
Page 5
truth values of its variables are known.
MODULE 1 - DISCRETE STRUCTURES AND PROPOSITIONAL LOGIC
A simple concise way to show this relationship is through a TRUTH TABLE.
Example: How are we going to construct the truth table of (p q)
Solution: Since we have 2 variables which is p,q, four rows are necessary or
four combinations of T and F, because for n variables, 2n rows are
required. So we have:
P Q q p q (p q)
T T F F T
T F T T F
F T F F T
F F T F T
IF-THEN VARIATIONS(IMPLICATION)
If-then statements appear in various forms in practice. The following
list presents some of the variations. These are all logically equivalent, that is
as far as true or false of statement is concerned there is no difference
between them. Thus if one is true then all the others are also true, and if one
is false all the others are false.
For instance, instead of saying "If she smiles then she is happy", we
can say "If she smiles, she is happy", "She is happy whenever she smiles", "She
smiles only if she is happy" etc. without changing their truth values.
"Only if" can be translated as "then". For example, "She smiles only if she is
happy" is equivalent to "If she smiles, then she is happy".
Note that "She smiles only if she is happy" means "If she is not happy, she
does not smile", which is the contrapositive of "If she smiles, she is happy".
You can also look at it this way: "She smiles only if she is happy" means
"She smiles only when she is happy". So any time you see her smile you know
she is happy. Hence "If she smiles, then she is happy". Thus they are logically
equivalent.
MODULE 1 - DISCRETE STRUCTURES AND PROPOSITIONALLOGIC
Also "If she smiles, she is happy" is equivalent to "It is necessary for her to
smile that she is happy". For "If she smiles, she is happy" means "If she smiles,
she is always happy". That is, she never fails to be happy when she smiles.
"Being happy" is inevitable consequence/necessity of "smile". Thus if "being
happy" is missing, then "smile" cannot be there either. "Being happy" is
necessary "for her to smile" or equivalently "It is necessary for her to smile
that she is happy".
Converse and Contrapositive
For the proposition P Q, the proposition Q P is called its converse, and
the proposition Q P is called its contrapositive.
For example for the proposition "If it rains, then I get wet",
Converse : If I get wet, then it rains.
Contrapositive : If I don't get wet, then it does not rain.
The converse of a proposition is not necessarily logically equivalent to it,
that is they may or may not take the same truth value at the same time.
On the other hand, the contrapositive of a proposition is always logically
equivalent to the proposition. That is, they take the same truth value
regardless of the values of their constituent variables. Therefore, "If it rains,
then I get wet." and "If I don't get wet, then it does not rain." are logically
equivalent. If one is true then the other is also true, and vice versa.
PRECEDENCE RULES
In forming sentences, we usually put grouping symbols(parenthesis,
brackets or braces) to where we want to be. Without the presence of
grouping symbols, we will assume that the grouping will follow the
precedence rules for the logical connectives.
Not (highest priority)
If p , then q. p implies q. p only
If p, q. if q. q if p. q is
necessary for p.
p is sufficient for q.
q whenever p.
Page 7 And
MODULE 1 - DISCRETE STRUCTURES AND PROPOSITIONAL LOGIC
Page 6 of 12
Or
If-then
If and only if (lowest priority)
EXAMPLE: The following examples demonstrate the process of
converting English statements in symbolic form:
Assume that we have the following propositions:
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
I will not go to Manila p
If I have money then I will go to Manila and I will attend qp r
a seminar
Neither I will go to Manila nor I will attend a seminar (p r)
Either the topic is interesting or the speaker is intelligent (s n ) m
then I will learn a lot
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
n r The speaker is not intelligent or I will attend a seminar
p (q r) I will go to manila if and only if I have money and I will
attend a seminar
n sm If the speaker is intelligent and the topic is interesting
then I will learn a lot
r p q I will attend a seminar or I will go to Manila and I have
money