D ISCRETE S TRUCTURE

L ECTURE NO . 1 M. IJAZ KHAN LECTURER ICIT G OMAL

U NIVERSITY
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
3. Discrete Mathematics by Ross and Wright
What is Discrete Mathematics?

It is the branch of mathematics which deals with the study of discrete objects i.e. objects which are
not continuous.

It includes the study of

1. Logics (logical connectives e.g. OR, AND etc. truth tables, compound preposition etc.)
2. Set theory (union, intersection of sets)
3. Functions
4. Relations
5. Algorithmic thinking
6. Boolean algebra
7. Number theory
8. Linear programming etc.

Importance of Discrete Mathematics:

Discrete Mathematics has become increasingly important in the recent years for the number of
reasons.

1. Discrete Mathematics is essential to college level Mathematics and beyond:

Discrete Mathematics together with calculus and algebra is one of the core subjects of
mathematics at the undergraduate level, so the students having some knowledge of Discrete
Mathematics before entering to the college have significant advantage while taking
undergraduate level math courses.
2. Discrete Mathematics is mathematics of computer:
The mathematics of modern computer science is built almost entirely on Discrete
Mathematics. This means that in order to learn the fundamental algorithms used by computer
programmers, students will need a solid background in Discrete Mathematics.
3. Discrete Mathematics is just like “real world” Mathematics:
Discrete Mathematics often deals with daily life problems. So students show interest in
Discrete Mathematics while traditional math (algebra, geometry trigonometry etc.) has
abstract nature which turns off the students.
4. Discrete Mathematics is often shown on the most middle and high school math contests due
to its importance.
5. Discrete Mathematics teaches the mathematical reasoning and proof techniques.

Importance of Mathematics in Computer:

Discrete math is also called the mathematics of computer. The mathematics of modern computer
science is built almost entirely on Discrete Mathematics.
In discrete math we study Logics, algorithms, number theory, graph theory (tree structure etc.) which
is the core topics of computer so to become master in computer science we must have the solid
knowledge of Discrete Mathematics. Some of the reasons to study logic are the following:
i. At the hardware level the design of ’logic’ circuits to implement instructions is greatly
simplified by the use of symbolic logic.
ii. At the software level the knowledge of symbolic logic is helpful in the design of programs.

1
 D ISCRETE S TRUCTURE
L ECTURE NO . 1 M. IJAZ KHAN LECTURER ICIT G OMAL
U NIVERSITY
Similarly
 The student of Discrete Math has greater power of problem solving.
 Discrete Mathematics teaches the mathematical reasoning and proof techniques.
 Discrete Mathematics increases the programming skill.
Thus in order to learn the fundamental algorithms used by computer programmers, students will
need a solid background in Discrete Mathematics. In many universities, a undergraduate level
course in Discrete Mathematics is a required part of pursuing a computer science degree.

Goals of a Discrete Mathematics Course

A discrete mathematics course has more than one purpose. Students should learn a particular set of
mathematical facts and how to apply them; more importantly, such a course should teach students
how to think logically and mathematically.
1. Mathematical Reasoning: Students must understand mathematical reasoning in order to
read, comprehend, and construct mathematical arguments. Mathematical logic serves as the
foundation for the methods of proof.
2. Combinatorial Analysis: discrete mathematics teaches us the basic techniques of counting.
The stress is on performing combinatorial analysis to solve counting problems and analyze
algorithms, not on applying formulae.
3. Discrete Structures: A course in discrete mathematics should teach students how to work
with discrete structures, how to deal with the discrete objects and relationships between these
objects. These discrete structures include sets, permutations, relations, graphs, trees, and
finite-state machines.
4. Algorithmic Thinking: Certain classes of problems are solved by the specification of an
algorithm. Specification, verification and the analysis of the computer Algorithms are all
covered in discrete mathematics.
5. Applications and Modeling: Discrete mathematics has applications to almost every
conceivable area of study. There are many applications to computer science and data
networking in this text.
Logic:
Logic is the study of the principles and methods that distinguishes between a valid and an invalid
argument.

Or

Logic is the study of valid reasoning.

Or

Anything which is based on true or false only is called logic

2
 D ISCRETE S TRUCTURE
L ECTURE NO . 1 M. IJAZ KHAN LECTURER ICIT G OMAL
U NIVERSITY

Propositions:
A proposition is a meaningful statement that is either true or false but not both.
For example, the following are propositions:
1. “Paris is in France” (true),
2. “London is in Denmark” (false),
3. “2 < 4” (true),
4. “4 = 7 (false)”.
However, the following are not propositions:
1. “What is your name?” (This is a question),
2. “Do your homework” (this is a command),
3. “This sentence is false” (neither true nor false),
4. “x is an even number” (it depends on what x represents),
5. “Socrates” (it is not even a sentence).
We use lowercase letters, such as p, q, r,…., to represent propositions e.g.
p: 1 + 1 = 3
To define p to be the proposition 1+1 = 3. The truth value of a proposition is true, denoted by T if it is
a true statement and false, denoted by F if it is a false statement. Statements that are not propositions
include questions and commands.
The truth or falsehood of a proposition is called its truth value.
Example 1.1
Which of the following are propositions? Give the truth value of the propositions.
a. 2 + 3 = 7.
b. Zardari was the president of the United States.
c. What time is it?
d. Be quiet!
Solution
a. A proposition with truth value (F).
b. A proposition with truth value (F).
c. Not a proposition since no truth value can be assigned to this statement.
d. Not a proposition
Example 1.2
Which of the following are propositions? Give the truth value of the propositions.
a. The difference of two primes.
b. 2 + 2 = 4.
c. Washington D.C. is the capital of New York.
d. How are you?
Solution
a. Not a proposition.
b. A proposition with truth value (T).
c. A proposition with truth value (F).
d. Not a proposition

3
 D ISCRETE S TRUCTURE
L ECTURE NO . 1 M. IJAZ KHAN LECTURER ICIT G OMAL
U NIVERSITY
Logical Connectives: The following table shows the logical connectives, their meanings, symbols
and names.

CONNECTIV MEANING SYMBOL CALLED

E
Negation not ~ Tilde

Conjunction and  Hat

Disjunction or  Vel

Conditional if…then…  Arrow

Biconditional if and only if  Double arrow

Conjunction:
Let p and q be prepositions then...
“The conjunction of p and q, denoted by p ^ q, is the proposition called “p and q”. This proposition is
defined to be true only when both p and q are true and it is false otherwise”.
Example 1.3
Let
p:5<9
q : 9 < 7.
Construct the propositions p ^ q
Solution
The conjunction of the propositions p and q is the proposition
p ^ q : 5 < 9 and 9 < 7.
Example 1.4
Consider the following propositions
p : It is Friday
q : It is raining.
Construct the propositions p ^ q
Solution
The conjunction of the propositions p and q is the proposition
p ^ q : It is Friday and it is raining.
Disjunction:
Let p and q be prepositions then...
The disjunction of p and q, denoted by p ⋁q, is the proposition called “p or q”. The ’or’ is used in an
inclusive way. This proposition is false only when both p and q are false, otherwise it is true.

Example 1.5

4
 D ISCRETE S TRUCTURE
L ECTURE NO . 1 M. IJAZ KHAN LECTURER ICIT G OMAL
U NIVERSITY
Let
p:5<9
q : 9 < 7.
Construct the propositions p ⋁ q.
Solution
The disjunction of the propositions p and q is the proposition
p ⋁ q : 5 < 9 or 9 < 7
Example 1.6
Consider the following propositions
p: It is Friday
q: It is raining.
Construct the propositions p ⋁ q.
Solution.
The disjunction of the propositions p and q is the proposition
p ⋁q : It is Friday or It is raining

Truth table:

A truth table displays the relationships between the truth values of propositions. The truth tables of
p^q and pV q are shown below.

p Q p^q
T T T
T F F
F T F
F F F

p Q p Vq
T T T
T F T
F T T
F F F

Exclusive OR:

Let p and q be two propositions. The exclusive or of p and q, denoted p + q, is the proposition that is
true when exactly one of p and q is true and is false otherwise. The truth table of the exclusive 'or' is
displayed below

p q
p +q
T T F
T F T
F T T
F F F

Example 1.5
a. Construct a truth table for (p + q) + r.
b. Construct a truth table for p + p.

5
 D ISCRETE S TRUCTURE
L ECTURE NO . 1 M. IJAZ KHAN LECTURER ICIT G OMAL
U NIVERSITY

Solution
a.
p q
r p+q (p + q) + r
T T T F T
T T F F F
T F T T F
T F F T T
F T T T F
F T F T T
F F T F T
F F F F F

b.
p p+p
T F
F F

Negation:

The final operation on a proposition p that we discuss is the negation of p. The negation of p, denoted
~ p, is the proposition not p. The truth table of ~ p is displayed below
p
~p
T F
F T

Example 1.6
Consider the following propositions:
p: Today is Thursday.
q: 2 + 1 = 3.
r: There is no pollution in New Jersey. Construct the
truth table of [~ (p A q)] V r. Solution.

p q
r p ^q ~ (p ^ q) [~ (p ^ q)] V r
T T T T F T
T T F T F F
F T T F T T
F T F F T T

Example 1.7

Find the negation of the proposition p : —5 < x < 0.

Solution.
The negation of p is the proposition ~ p : x > 0 or x < — 5

6
 D ISCRETE S TRUCTURE
L ECTURE NO . 1 M. IJAZ KHAN LECTURER ICIT G OMAL
U NIVERSITY

Tautology:
A compound proposition is called a tautology if it is always true, no matter what the truth values are.
E.g.
p
~p pV ~ p
T F T
F T T

This proposition is a tautology.

Equivalent:
Two propositions are equivalent if they have exactly the same truth values under all circumstances.
We can write as p = q.

Example 1.9
a. Show that ~ (p V q) =~ p ^ ~ q.
b. Show that ~ (p ^ q) =~ p ^ ~ q.
c. Show that ~ (~ p) = p.
a. and b. are known as DeMorgan's laws.

Solution
a.
p q
~p ~q pVq ~ (p V q) ~p^~q
T T F F T F F
T F F T T F F
F T T F T F F
F F T T F T T

b.
p
q ~p ~q p^q ~ (p ^ q) ~ pV ~ q
T T F F T F F
T F F T F T T
F T T F F T T
F F T T F T T
c.
p
~p ~ (~ p)
T F T
F T F
Contradiction:
A compound proposition that has the value F for all possible values of the propositions in it is called a
contradiction.

Example 1.12

Show that the proposition p^ ~ p is a contradiction.

7
 D ISCRETE S TRUCTURE
L ECTURE NO . 1 M. IJAZ KHAN LECTURER ICIT G OMAL
U NIVERSITY

Solution
p
~p p^ ~ p
T F F
F T F
V
In propositional functions, the order of operations is that ~ is performed first. The operations and ^
are executed in any order.

Conditional and Biconditional Propositions

Implication:

Let p and q be propositions. The implication p → q is the proposition that is false only when p is true and q is false;
otherwise it is true. p is called the hypothesis and q is called the conclusion. The connective → is called the conditional
connective.
Example 2.1
Construct the truth table of the implication p → q.
Solution
The truth table is
p q p
→q
T T T
T F F
F T T
F F T

Example 2.2

Show that p → q =~ p V q. Solution.

p p
q ~p →q ~pVq
T T F T T
T F F F F
F T T T T
F F T T T

It follows from the previous example that the proposition p → q is always true if the
hypothesis p is false, regardless of the truth value of q. We say that p → q is true by default or
vacuously true. In terms of words the proposition p → q also reads:
(a) if p then q.
(b) p implies q.
(c) p is a sufficient condition for q.
(d) q is a necessary condition for p.
(e) p only if q.
The converse of p → q is the proposition q →p. The opposite or inverse of p → q is the proposition ~ p→~q. The
contrapositive of p → q is the proposition ~ q →~ p.

Example 2.3

Use the if-then form to rewrite the statement "I am on time for work if I catch the 8:05 bus."

8
 D ISCRETE S TRUCTURE
L ECTURE NO . 1 M. IJAZ KHAN LECTURER ICIT G OMAL
U NIVERSITY
Solution.
If I catch the 8:05 bus then I am on time for work

In propositional functions that involve the connectives ~, ^, V, and → the order of operations is that ~ is performed first and
→ is performed last.

Example 2.4
a. Show that ~ (p → q) = p ^ ~ q.
b. Find the negation of the statement "If my car in the repair shops, then I
cannot go to class."
Solution
a. We use De Morgan's laws as follows.

~ (p →q) = ~ (~ p V q) = ~ (~ p) ^ ~ q = p^ ~ q.
b. "My car in the repair shop and I can get to class."
The converse of p → q is the proposition q → p. The opposite or inverse of p →q is the proposition ~ p →~ q. The
contrapositive of p → q is the proposition ~ q →~ p.

Example 2.5
Find the converse, opposite, and the contrapositive of the implication: " If today is Thursday, then I have a test today."

Solution.
The converse: If I have a test today then today is Thursday.
The opposite: If today is not Thursday then I don't have a test today.
The contrapositive: If I don't have a test today then today in not Thursday
Example 2.6
Show that p → q =~ q →~ p.
Solution.
We use De Morgan's laws as follows.

p→q = ~pVq
= ~ (pA ~ q)
= ~ (~ q A p)
= qV ~ p
= qV ~ p
= ~ q →~ p

Example 2.7
Using truth tables show the following:
a. p →q = q → p
b. p → q =~ p →~ q

Solution.
a. It suffices to show that ~ p V q =~ q V p.
p q
~p ~q ~pVq ~qVp
T T F F T T
T F F T F T
F T T F T F
F F T T T T

b. We will show that ~ p V q = pV ~ q.

9
 D ISCRETE S TRUCTURE
L ECTURE NO . 1 M. IJAZ KHAN LECTURER ICIT G OMAL
U NIVERSITY
p q
~p ~q ~pVq pV ~ q
T T F F T T
T F F T F T
F T T F T F
F F T T T T

Example 2.8
Show that ~ q →~ p = p → q Solution.
We use De Morgan's laws as follows.

~ q →~ p = qV ~ p
= ~ (~ q A p)
= ~ (pA ~ q)
= ~ pV ~~ q
= ~ p V q= p → q
Biconditional:
The biconditional proposition of p and q, denoted by p↔ q, is the propositional function that is true when both p and q have
the same truth values and false if p and q have opposite truth values. Also reads, "p if and only if q" or "p is a necessary and
sufficient condition for q."

Example 2.9

Construct the truth table for p ↔ q. Solution.

p q
p ↔ q
T T T
T F F
F T F
F F T

Example 2.10
Show that the biconditional proposition of p and q is logically equivalent to the conjunction of the conditional propositions p
→q and q → p.
Solution

p q p →q q →p p ↔ q (p→q)^ (q → p)
T T T T T T
T F F T F F
F T T F F F
F F T T T T

The order of operations for the five logical connectives is as follows:

1. ~
2. ^,V in any order.
3. →, in any order.

10