LECTURE NOTES ON DISCRETE MATHEMATICS - MREC …

1 MALLA REDDY ENGINEERING COLLEGE (Autonomous) Maisammaguda, Dhulapally (Post Via. Hakimpet), Secunderabad 500100, Telangana State, INDIA. LECTURE NOTES ON DISCRETE MATHEMATICS DEPARTMENT OF INFORMATION TECHNOLOGY Prerequisites: NIL Course Objectives: This course provides the concepts of mathematical logic demonstrate predicate logic and Binary Relations among different variables, discuss different type of functions and concepts of Algebraic system and its properties. It also evaluates techniques of Combinatorics based on counting methods and analyzes the concepts of Generating functions to solve Recurrence equations.

2 MODULE I: Mathematical Logic Basic Logics - Statements and notations, Connectives, Well-formed formulas, Truth Tables, tautology. Implications and Quantifiers - Equivalence implication, Normal forms, Quantifiers, Universal quantifiers. MODULE II: Predicate Logic and Relations Predicate Logic - Free & Bound variables, Rules of inference, Consistency, proof of contradiction, Proof of automatic Theorem. Relations - Properties of Binary Relations, equivalence, transitive closure, compatibility and partial ordering relations, Lattices, Hasse diagram.

3 MODULE III: Functions and Algebraic Structures [10 Periods] A: Functions - Inverse Function, Composition of functions, recursive Functions Lattice and its Properties. B: Algebraic structures - Algebraic systems Examples and general properties, Semigroups and monoids, groups, sub-groups, homomorphism, Isomorphism, Lattice as POSET, Boolean algebra. MODULE IV: Counting Techniques and Theorems [09 Periods] Counting Techniques - Basis of counting, Combinations and Permutations with repetitions, Constrained repetitions Counting Theorems - Binomial Coefficients, Binomial and Multinomial theorems, principles of Inclusion Exclusion.

4 Pigeon hole principle and its applications. MODULE V: Generating functions and Recurrence Relation [09 Periods] Generating Functions - Generating Functions, Function of Sequences, Calculating Coefficient of generating function. Recurrence Relations - Recurrence relations, Solving recurrence relation by substitution and Generating functions. Method of Characteristics roots, solution of Non-homogeneous Recurrence Relations. TEXTBOOKS 1. J P Tremblay & R Manohar, DISCRETE MATHEMATICS with applications to Computer Science , Tata mcgraw hill . 2. Mott, A.

5 Kandel, DISCRETE MATHEMATICS for Computer Scientists & Mathematicians , PHI. REFERENCES 1. Kenneth H. Rosen, " DISCRETE MATHEMATICS and its Applications , TMH, Fifth Edition. 2. Thomas Koshy, " DISCRETE MATHEMATICS with Applications", Elsevier. 3. Grass Man & Trembley, "Logic and DISCRETE MATHEMATICS , Pearson Education. 4. C L Liu, D P Nohapatra, Elements of DISCRETE MATHEMATICS - A Computer Oriented Approach , Tata mcgraw hill , Third Edition. E-RESOURCES 1. ~bagchi/courses/ DISCRETE - 2. ~curmat/matdiscretas/ 3. qS12 ZbN7pUSSlWCxSgPOZJEokyWJlxQLYsrFyeITA70W 9C8Pg 4.

6 Course Outcomes: At the end of the course, a student will be able to 1. Apply the concepts of connectives and normal forms in real time applications. 2. Summarize predicate logic, relations and their operations. 3. Describe functions, algebraic systems, groups and Boolean algebra. 4. Illustrate practical applications of basic counting principles, permutations, combinations, and the pigeonhole methodology. 5. Analyze techniques of generating functions and recurrence relations. MODULE-I Mathematical Logic Statements and notations: A proposition or statement is a declarative sentence that is either true or false (but not both).

7 For instance, the following are propositions: Paris is in France< (true) London is in Denmark< (false) 2 < 4 < (true) 4 = 7< (false) However the following are not propositions: what is your name?< (this is a question) do your homework< (this is a command) this sentence is false< (neither true nor false) x is an even number< (it depends on what x represents) Socrates< (it is not even asentence) The truth or falsehood of a proposition is called its truth value. Connectives: Connectives are used for making compound propositions. Generally used five connectives are OR (V) AND (K) Negation/ NOT ( ) Implication / if-then ( ) If and only if ( ).

8 Well formed formulas (wff): The strings that produce a proposition when their symbols are interpreted must follow the rules given below, and they are called wffs(well-formed formulas) of the first order predicate logic. DM 1 A predicate name followed by a list of variables such as P(x, y), where P is predicate name, and x and y are variables, is called an atomic formula. A well formed formula of predicate calculus is obtained by using the following rules. 1. An atomic formula is a wff. 2. If A is a wff, then A is also a wff. 3. If A and B are wffs, then (A V B), (A B), (A B) and (A B) are wffs.

9 4. If A is a wff and x is any variable, then (x)A and ($x)A are wffs. 5. Only those formulas obtained by using (1) to (4) are wffs. Wffs are constructed using the following rules: 1. True and False are wffs. 2. Each propositional constant ( specific proposition), and each propositional variable ( a variable representing propositions) are wffs. 3. Each atomic formula ( a specific predicate with variables) is a wff. 4. If A, B, and C are wffs, then so are A, (A B), (A B), (A B), and (A B). 5. If x is a variable (representing objects of the universe of discourse), and A is a wff, then so are x A and x A.

10 For example, "The capital of Virginia is Richmond." is a specific proposition. Hence it is a wff by Rule 2. Let B be a predicate name representing "being blue" and let x be a variable. Then B(x) is an atomic formula meaning "x is blue". Thus it is a wff by Rule 3. above. By applying Rule 5. to B(x), xB(x) is a wff and so is xB(x). Then by applying Rule 4. to them x B(x) x B(x) is seen to be a wff. Similarly if R is a predicate name representing "being round". Then R(x) is an atomic formula. Hence it is a wff. By applying Rule 4 to B(x) and R(x), a wff B(x) R(x) is obtained.