MTH202 Official Handouts

Table of Contents

LOGIC ...................................................................................................................... 3

LAWS OF LOGIC ................................................................................................... 14

ARGUMENT .......................................................................................................... 25 APPLICATIONS OF LOGIC .................................................................................. 30 SET THEORY ......................................................................................................... 37 VENN DIAGRAM .................................................................................................. 42 SET IDENTITIES ................................................................................................... 54 LECTURE NO.10 APPLICATIONS OF VENN DIAGRAM ................................................................ 61 LECTURE NO.11 RELATIONS ........................................................................................................... 70 LECTURE NO.12 TYPES OF RELATIONS ........................................................................................ 77 LECTURE NO.13 MATRIX REPRESENTATION OF RELATIONS ................................................... 88 LECTURE NO.14 INVERSE OF RELATIONS .................................................................................... 95 LECTURE NO.15 FUNCTIONS ........................................................................................................ 101 LECTURE NO.16 TYPES OF FUNCTIONS ...................................................................................... 111 LECTURE NO.17 INVERSE FUNCTION.......................................................................................... 123 LECTURE NO.18 COMPOSITION OF FUNCTIONS ........................................................................ 134 LECTURE NO.19 SEQUENCE .......................................................................................................... 144 LECTURE NO.20 SERIES ................................................................................................................. 150 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 .............................................................................................. 209 LECTURE NO.30 PERMUTATIONS ................................................................................................ 217 LECTURE NO.31 COMBINATIONS ................................................................................................. 225 LECTURE NO.32 K-COMBINATIONS ............................................................................................. 231 LECTURE NO.33 TREE DIAGRAM ................................................................................................. 237 LECTURE NO.34 INCLUSION-EXCLUSION PRINCIPLE .............................................................. 245 LECTURE NO.35 PROBABILITY ..................................................................................................... 250 LECTURE NO.36 LAWS OF PROBABILITY ................................................................................... 257 LECTURE NO. 37 CONDITIONAL PROBABILITY ........................................................................ 267 LECTURE NO. 38 RANDOM VARIABLE ........................................................................................ 274 LECTURE NO. 39 INTRODUCTION TO GRAPHS .......................................................................... 283 LECTURE NO. 40 PATHS AND CIRCUITS ..................................................................................... 292 LECTURE NO. 41 MATRIX REPRESENTATION OF GRAPHS ...................................................... 298 LECTURE NO. 42 ISOMORPHISM OF GRAPHS ............................................................................. 305 LECTURE NO. 43 PLANAR GRAPHS ............................................................................................. 314 LECTURE NO. 44 TREES ................................................................................................................. 321 LECTURE NO. 45 SPANNING TREES ............................................................................................. 329 1Logic

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 function
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
3. 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. Combinatorics
10. Probability
11. Graphs and Trees

Continuous

Discrete

1-Logic

Set of Integers:

-2 -1

Set of Real Numbers:

-3 -2 -1

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
3. 4 + 2 = 7
4. There are four fingers in a hand.

are 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.

UNDERSTANDING STATEMENTS:

1. 1. x + 2 is positive. Not a statement

Q2. 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

Not Propositions

Close the door. x is greater than 2. He is very rich are not propositions.

Example

Bill Gates is an American He is very rich He is very rich is a statement with truth-value TRUE.