Discrete Mathematics (MTH202) VU
Discrete Mathematics
MTH202
Virtual University of Pakistan
Knowledge beyond the boundaries
1
© Copyright Virtual University of Pakistan
,Discrete Mathematics (MTH202) VU
Table of Contents
LECTURE NO.1 LOGIC .............................................................................................................................. 3
LECTURE NO.2 TRUTH TABLES............................................................................................................. 9
LECTURE NO.3 LAWS OF LOGIC.......................................................................................................... 17
LECTURE NO.4 BICONDITIONAL......................................................................................................... 24
LECTURE NO.5 ARGUMENT.................................................................................................................. 29
LECTURE NO.6 APPLICATIONS OF LOGIC ........................................................................................ 34
LECTURE NO.7 SET THEORY ................................................................................................................ 41
LECTURE NO.8 VENN DIAGRAM ......................................................................................................... 46
LECTURE NO.9 SET IDENTITIES .......................................................................................................... 58
LECTURE NO.10 APPLICATIONS OF VENN DIAGRAM..................................................................... 65
LECTURE NO.11 RELATIONS .................................................................................................................. 73
LECTURE NO.12 TYPES OF RELATIONS............................................................................................... 80
LECTURE NO.13 MATRIX REPRESENTATION OF RELATIONS ...................................................... 90
LECTURE NO.14 INVERSE OF RELATIONS.......................................................................................... 97
LECTURE NO.15 FUNCTIONS ................................................................................................................ 102
LECTURE NO.16 TYPES OF FUNCTIONS ............................................................................................ 112
LECTURE NO.17 INVERSE FUNCTION ................................................................................................ 123
LECTURE NO.18 COMPOSITION OF FUNCTIONS ............................................................................. 134
LECTURE NO.19 SEQUENCE.................................................................................................................. 144
LECTURE NO.20 SERIES ......................................................................................................................... 151
LECTURE NO.21 RECURSION I ............................................................................................................. 159
LECTURE NO.22 RECURSION II ............................................................................................................ 165
LECTURE NO.23 MATHEMATICAL INDUCTION .............................................................................. 170
LECTURE NO.24 MATHEMATICAL INDUCTION FOR DIVISIBILITY........................................... 179
LECTURE NO.25 METHODS OF PROOF............................................................................................... 186
LECTURE NO.26 PROOF BY CONTRADICTION................................................................................. 193
LECTURE NO.27 ALGORITHM .............................................................................................................. 201
LECTURE NO.28 DIVISION ALGORITHM ........................................................................................... 205
LECTURE NO.29 COMBINATORICS ..................................................................................................... 210
LECTURE NO.30 PERMUTATIONS ....................................................................................................... 218
LECTURE NO.31 COMBINATIONS........................................................................................................ 226
LECTURE NO.32 K-COMBINATIONS ................................................................................................... 232
LECTURE NO.33 TREE DIAGRAM ........................................................................................................ 238
LECTURE NO.34 INCLUSION-EXCLUSION PRINCIPLE ................................................................... 245
LECTURE NO.35 PROBABILITY............................................................................................................ 250
LECTURE NO.36 LAWS OF PROBABILITY ......................................................................................... 256
LECTURE NO. 37 CONDITIONAL PROBABILITY.............................................................................. 265
LECTURE NO. 38 RANDOM VARIABLE .............................................................................................. 272
LECTURE NO. 39 INTRODUCTION TO GRAPHS ............................................................................... 280
LECTURE NO. 40 PATHS AND CIRCUITS ........................................................................................... 289
LECTURE NO. 41 MATRIX REPRESENTATION OF GRAPHS.......................................................... 296
LECTURE NO. 42 ISOMORPHISM OF GRAPHS ................................................................................... 303
LECTURE NO. 43 PLANAR GRAPHS .................................................................................................... 312
LECTURE NO. 44 TREES ......................................................................................................................... 319
LECTURE NO. 45 SPANNING TREES.................................................................................................... 327
2
© Copyright Virtual University of Pakistan
,1- Logic VU
Lecture No.1 Logic
Course Objective:
1.Express statements with the precision of formal logic
2.Analyze arguments to test their validity
3.Apply the basic properties and operations related to sets
4.Apply to sets the basic properties and operations related to relations and functions
5.Define terms recursively
6.Prove a formula using mathematical induction
7.Prove statements using direct and indirect methods
8.Compute probability of simple and conditional events
9.Identify and use the formulas of combinatorics in different problems
10.Illustrate the basic definitions of graph theory and properties of graphs
11.Relate each major topic in Discrete Mathematics to an application area in computing
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
MAIN TOPICS:
1. Logic
2. Sets & Operations on sets
3. Relations & Their Properties
4. Functions
5. Sequences & Series
6. Recurrence Relations
7. Mathematical Induction
8. Loop Invariants
9. Loop Invariants
10. Combinatorics
11. Probability
12. Graphs and Trees
Continuous
Discrete
© Copyright Virtual University of Pakistan
, 1-Logic VU
Set of Integers:
• • • • • •
3 -2 -1 0 1 2
Set of Real Numbers:
• • • • • • •
-3 -2 -1 0 1 2 3
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 distinguish 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
EXAMPLES:
a. 2+2 = 4,
b. 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:
Propositions Not Propositions
1) Grass is green. 1) Close the door.
2) 4 + 2 = 6 2) x is greater than 2.
3) 4 + 2 = 7 3) He is very rich
4) There are four fingers in a hand.
Rule:
If the sentence is preceded by other sentences that make the pronoun or variable reference
clear, then the sentence is a statement.
Example
Example:
x=1 Bill Gates is an American
x>2 He is very rich
“x > 2” is a statement with truth-value “He is very rich” is a statement with truth-
FALSE. value TRUE.
4
© Copyright Virtual University of Pakistan
Discrete Mathematics
MTH202
Virtual University of Pakistan
Knowledge beyond the boundaries
1
© Copyright Virtual University of Pakistan
,Discrete Mathematics (MTH202) VU
Table of Contents
LECTURE NO.1 LOGIC .............................................................................................................................. 3
LECTURE NO.2 TRUTH TABLES............................................................................................................. 9
LECTURE NO.3 LAWS OF LOGIC.......................................................................................................... 17
LECTURE NO.4 BICONDITIONAL......................................................................................................... 24
LECTURE NO.5 ARGUMENT.................................................................................................................. 29
LECTURE NO.6 APPLICATIONS OF LOGIC ........................................................................................ 34
LECTURE NO.7 SET THEORY ................................................................................................................ 41
LECTURE NO.8 VENN DIAGRAM ......................................................................................................... 46
LECTURE NO.9 SET IDENTITIES .......................................................................................................... 58
LECTURE NO.10 APPLICATIONS OF VENN DIAGRAM..................................................................... 65
LECTURE NO.11 RELATIONS .................................................................................................................. 73
LECTURE NO.12 TYPES OF RELATIONS............................................................................................... 80
LECTURE NO.13 MATRIX REPRESENTATION OF RELATIONS ...................................................... 90
LECTURE NO.14 INVERSE OF RELATIONS.......................................................................................... 97
LECTURE NO.15 FUNCTIONS ................................................................................................................ 102
LECTURE NO.16 TYPES OF FUNCTIONS ............................................................................................ 112
LECTURE NO.17 INVERSE FUNCTION ................................................................................................ 123
LECTURE NO.18 COMPOSITION OF FUNCTIONS ............................................................................. 134
LECTURE NO.19 SEQUENCE.................................................................................................................. 144
LECTURE NO.20 SERIES ......................................................................................................................... 151
LECTURE NO.21 RECURSION I ............................................................................................................. 159
LECTURE NO.22 RECURSION II ............................................................................................................ 165
LECTURE NO.23 MATHEMATICAL INDUCTION .............................................................................. 170
LECTURE NO.24 MATHEMATICAL INDUCTION FOR DIVISIBILITY........................................... 179
LECTURE NO.25 METHODS OF PROOF............................................................................................... 186
LECTURE NO.26 PROOF BY CONTRADICTION................................................................................. 193
LECTURE NO.27 ALGORITHM .............................................................................................................. 201
LECTURE NO.28 DIVISION ALGORITHM ........................................................................................... 205
LECTURE NO.29 COMBINATORICS ..................................................................................................... 210
LECTURE NO.30 PERMUTATIONS ....................................................................................................... 218
LECTURE NO.31 COMBINATIONS........................................................................................................ 226
LECTURE NO.32 K-COMBINATIONS ................................................................................................... 232
LECTURE NO.33 TREE DIAGRAM ........................................................................................................ 238
LECTURE NO.34 INCLUSION-EXCLUSION PRINCIPLE ................................................................... 245
LECTURE NO.35 PROBABILITY............................................................................................................ 250
LECTURE NO.36 LAWS OF PROBABILITY ......................................................................................... 256
LECTURE NO. 37 CONDITIONAL PROBABILITY.............................................................................. 265
LECTURE NO. 38 RANDOM VARIABLE .............................................................................................. 272
LECTURE NO. 39 INTRODUCTION TO GRAPHS ............................................................................... 280
LECTURE NO. 40 PATHS AND CIRCUITS ........................................................................................... 289
LECTURE NO. 41 MATRIX REPRESENTATION OF GRAPHS.......................................................... 296
LECTURE NO. 42 ISOMORPHISM OF GRAPHS ................................................................................... 303
LECTURE NO. 43 PLANAR GRAPHS .................................................................................................... 312
LECTURE NO. 44 TREES ......................................................................................................................... 319
LECTURE NO. 45 SPANNING TREES.................................................................................................... 327
2
© Copyright Virtual University of Pakistan
,1- Logic VU
Lecture No.1 Logic
Course Objective:
1.Express statements with the precision of formal logic
2.Analyze arguments to test their validity
3.Apply the basic properties and operations related to sets
4.Apply to sets the basic properties and operations related to relations and functions
5.Define terms recursively
6.Prove a formula using mathematical induction
7.Prove statements using direct and indirect methods
8.Compute probability of simple and conditional events
9.Identify and use the formulas of combinatorics in different problems
10.Illustrate the basic definitions of graph theory and properties of graphs
11.Relate each major topic in Discrete Mathematics to an application area in computing
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
MAIN TOPICS:
1. Logic
2. Sets & Operations on sets
3. Relations & Their Properties
4. Functions
5. Sequences & Series
6. Recurrence Relations
7. Mathematical Induction
8. Loop Invariants
9. Loop Invariants
10. Combinatorics
11. Probability
12. Graphs and Trees
Continuous
Discrete
© Copyright Virtual University of Pakistan
, 1-Logic VU
Set of Integers:
• • • • • •
3 -2 -1 0 1 2
Set of Real Numbers:
• • • • • • •
-3 -2 -1 0 1 2 3
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 distinguish 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
EXAMPLES:
a. 2+2 = 4,
b. 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:
Propositions Not Propositions
1) Grass is green. 1) Close the door.
2) 4 + 2 = 6 2) x is greater than 2.
3) 4 + 2 = 7 3) He is very rich
4) There are four fingers in a hand.
Rule:
If the sentence is preceded by other sentences that make the pronoun or variable reference
clear, then the sentence is a statement.
Example
Example:
x=1 Bill Gates is an American
x>2 He is very rich
“x > 2” is a statement with truth-value “He is very rich” is a statement with truth-
FALSE. value TRUE.
4
© Copyright Virtual University of Pakistan
