DISCRETE STRUCTURE

1.Recommended Books:

1.Discrete Mathematics with Applications (second edition)

by Susanna S. Epp
2.Discrete Mathematics and Its Applications (fourth
edition) by Kenneth H. Rosen
1.Discrete Mathematics by Ross and Wright
Discrete Continuous
• • • • • • •
-3 -2 -1 0 1 2

Set of Integers
• • • • • •
3 -2 -1 0 1 2

Set of Real Numbers

• • • • • • •
-3 -2 -1 0 1 2
What is Discrete Mathematics?

Discrete Mathematics concerns processes that

consist of a sequence of individual steps.

LOGIC
Logic is the study of the principles and methods
that distinguishes between a
valid and an invalid argument.
SIMPLE STATEMENT
A statement is a declarative sentence that is either true
or false but not both.
A statement is also referred to as a proposition
Example: 2+2 = 4, It is Sunday today
If a proposition is true, we say that it has a truth value of
"true”.
If a proposition is false, its truth value is "false".
The truth values “true” and “false” are, respectively,
denoted by the letters T and F.
EXAMPLES
1. Grass is green.
2. 4+2=6
2. 4+2=7
3. There are four fingers in a hand.
are propositions
Not Propositions
Close the door.
x is greater than 2.
He is very rich
are not propositions.
 Rule
If the sentence is preceded by other sentences that
make the pronoun or variable reference clear, then the
sentence is a statement

Example
x=1
x>2
x > 2 is a statement with truth-value
FALSE.
Example
Bill Gates is an American
He is very rich
He is very rich is a statement with truth-value TRUE.
UNDERSTANDING STATEMENTS
1. x + 2 is positive. Not a statement
2. May I come in? Not a statement

3. Logic is interesting. A statement

4. It is hot today. A statement

5. -1 > 0 A statement

6. x + y = 12 Not a statement
 COMPOUND STATEMENT
Simple statements could be
used to build a compound
statement.

EXAMPLES LOGICAL CONNECTIVES

1. “3 + 2 = 5” and “Lahore is a city in Pakistan”
2. “The grass is green” or “ It is hot today”
3. “Discrete Mathematics is not difficult to me”
AND, OR, NOT are called LOGICAL CONNECTIVES.

SYMBOLIC REPRESENTATION
Statements are symbolically represented by letters
such as p, q, r,...
1. “3 + 2 = 5” and “Lahore is a city in Pakistan”
2. “The grass is green” or “ It is hot today”
3. “Discrete Mathematics is not difficult to me”
AND, OR, NOT are called LOGICAL CONNECTIVES.

EXAMPLES:
p = “Islamabad is the capital of Pakistan”
q = “17 is divisible by 3”
EXAMPLES
p = “Islamabad is the capital of Pakistan”
q = “17 is divisible by 3”
p  q = “Islamabad is the capital of Pakistan and 17 is
divisible by 3”
p  q = “Islamabad is the capital of Pakistan or 17 is
divisible by 3”
~p = “It is not the case that Islamabad is the capital
of Pakistan” or simply
“Islamabad is not the capital of Pakistan”
TRANSLATING FROM ENGLISH TO SYMBOLS
:
Let p = “It is hot”, and q = “It is sunny”

SENTENCE SYMBOLIC FORM

1. It is not hot. ~p
2. It is hot and sunny. p q
3. It is hot or sunny. pq
4. It is not hot but sunny. ~ p q
5. It is neither hot nor sunny. ~p~q
EXAMPLE

Let h = “Zia is healthy”

w = “Zia is wealthy”
s = “Zia is wise”
Translate the compound statements to symbolic form:
1. Zia is healthy and wealthy but not wise. (h  w) 
(~s)

2. Zia is not wealthy but he is healthy and wise. ~w  (h

 s)

3. Zia is neither healthy, wealthy nor wise. ~h  ~w

 ~s
TRANSLATING FROM SYMBOLS TO ENGLISH
Let m = “Ali is good in Mathematics”
c = “Ali is a Computer Science student”
Translate the following statement forms into plain English:

1. ~ c Ali is not a Computer Science student

2. c  m Ali is a Computer Science student or good in Maths.

3. m  ~c Ali is good in Maths but not a Computer Science student

A convenient method for analyzing a compound statement is to
make a truth table for it.
A truth table specifies the truth value of a compound proposition for
all possible truth values of its constituent propositions.
NEGATION (~)

If p is a statement variable, then negation of p, “not p”, is

denoted as “~p”
It has opposite truth value from p i.e.,
TRUTH TABLE FOR
~p
p ~p

T F

F T
 CONJUNCTION ()
If p and q are statements, then the conjunction of p and q is “p
and q”, denoted as
“p  q”.
It is true when, and only when, both p and q are true. If either
p or q is false, or
if both are false, pq is false.
TRUTH TABLE FOR
p q pq

pq T T T

T F F

F T F

F F F
DISJUNCTION ()
or INCLUSIVE OR
If p & q are statements, then the disjunction of p and q is “p
or q”, denoted as
“p  q”.It is true when at least one of p or q is true and is
false only when both
p and q are false.
TRUTH TABLE FOR
pq p q pq

T T T

T F T

F T T

F F F
Remark:
Note that for Conjunction of two statements we find the T
in both the statements, but in disjunction we find F in both the
statements. In other words we will fill T first in the column of
conjunction and F in the column of disjunction.
SUMMARY
1. What is a statement?
2. How a compound statement is formed.
3. Logical connectives (negation, conjunction, disjunction).
4. How to construct a truth table for a statement form.
 Truth Tables
Truth Tables for:
1. ~pq
2. ~ p  (q  ~ r)
3.(pq)  ~ (pq)
Truth table for the statement form ~ p  q
p q ~p ~pq

T T F F

T F F F

F T T T

F F T F
Truth table for ~ p  (q  ~ r)
Truth table for (pq)  ~ (pq)
Double Negative Property ~(~p)  p
Example
“It is not true that I am not happy”
Solution:
Let p = “I am happy”
then ~ p = “I am not happy”
and ~(~ p) = “It is not true that I am not happy”
Since ~ (~p)  p
Hence the given statement is equivalent to:
“I am happy”

~ (pq) and ~p  ~q are not logically equivalent

Different truth values in row 2 and row 3
DE MORGAN’S LAWS

:
1) The negation of an and statement is logically equivalent to
the or
statement in which each component is negated.
Symbolically ~(p  q)  ~p  ~q.
2) The negation of an or statement is logically equivalent to the
and
statement in which each component is negated.
Symbolically: ~(p  q)  ~p  ~q.

~(p  q)  ~p  ~q
Same truth values
Application:
Give negations for each of the following statements:
a. The fan is slow or it is very hot.
b. Akram is unfit and Saleem is injured.
Solution
a. The fan is not slow and it is not very hot.
b. Akram is not unfit or Saleem is not injured.
INEQUALITIES AND DEMORGAN’S LAWS
Use DeMorgan’s Laws to write the negation of
-1 < x  4
for some particular real no. x
-1 < x  4 means x > –1 and x  4
By DeMorgan’s Law, the negation is:
x > –1 or x  4
Which is equivalent to: x  –1 or x > 4
EXERCISE:
1. (p  q)  r  p (q  r)
2. Are the statements (pq)r and p  (q  r) logically equivalent?