Discrete Mathematics for SPPU 2 - Dr. H. R. Bhapkar PDF

Preview

Summary

Engineering Mathematics 3...

Description

SUBJECT CODE

: 210241 Strictly as per Revised Syllabus of

Savitribai Phule Pune University Choice Based Credit System (CBCS) S.E. (Computer) Semester - I

Discrete Mathematics (For IN SEM Exam - 30 Marks) Dr. H. R. Bhapkar M.Sc. SET, Ph.D. (Mathematics) MIT Art, Design and Technology University’s MIT School of Engineering, Lonikalbhor, Pune Email : [email protected] Mobile : 9011227141

Dr. Rajesh Nandkumar Phursule Ph.D. (Computer Science and Engineering) Associate Professor, Pimpri Chinchwad College of Engineering Nigdi, Pune.

®

®

TECHNICAL PUBLICATIONS

SINCE 1993

An Up-Thrust for Knowledge

(i)

Discrete Mathematics (For IN SEM Exam - 30 Marks) Subject Code : 210241

S.E. (Computer) Semester - I

First Edition : August 2020

ã Copyright with Dr. H. R. Bhapkar All publishing rights (printed and ebook version) reserved with Technical Publications. No part of this book should be reproduced in any form, Electronic, Mechanical, Photocopy or any information storage and retrieval system without prior permission in writing, from Technical Publications, Pune.

Published by : ®

®

TECHNICAL PUBLICATIONS

SINCE 1993

An Up-Thrust for Knowledge

Amit Residency, Office No.1, 412, Shaniwar Peth, Pune - 411030, M.S. INDIA, Ph.: +91-020-24495496/97 Email : [email protected] Website : www.technicalpublications.org

Printer : Yogiraj Printers & Binders Sr.No. 10/1A, Ghule Industrial Estate, Nanded Village Road, Tal. - Haveli, Dist. - Pune - 411041.

ISBN 978-93-332-0276-3

SPPU 19

9 789333 202763 9 789333202763 [1]

(ii)

Preface The importance of Discrete Mathematics is well known in various engineering fields. Overwhelming response to our books on various subjects inspired us to write this book. The book is structured to cover the key aspects of the subject Discrete Mathematics. The book uses plain, lucid language to explain fundamentals of this subject. The book provides logical method of explaining various complicated concepts and stepwise methods to explain the important topics. Each chapter is well supported with necessary illustrations, practical examples and solved problems. All the chapters in the book are arranged in a proper sequence that permits each topic to build upon earlier studies. All care has been taken to make students comfortable in understanding the basic concepts of the subject. The book not only covers the entire scope of the subject but explains the philosophy of the subject. This makes the understanding of this subject more clear and makes it more interesting. The book will be very useful not only to the students but also to the subject teachers. The students have to omit nothing and possibly have to cover nothing more. We wish to express our profound thanks to all those who helped in making this book a reality. Much needed moral support and encouragement is provided on numerous occasions by our whole family. We wish to thank the Publisher and the entire team of Technical Publications who have taken immense pain to get this book in time with quality printing. Any suggestion for the improvement of the book will be acknowledged and well appreciated.

Authors Dr. H. R. Bhapkar Dr. Rajesh N. Phursule

Dedicated to the Readers of the Book

(iii)

Syllabus Discrete Mathematics - (210241) Credit Scheme 03

Unit I

Examination Scheme and Marks Mid_Semester (TH) : 30 Marks

Set Theory and Logic

Introduction and significance of Discrete Mathematics, Sets – Naïve Set Theory (Cantorian Set Theory), Axiomatic Set Theory, Set Operations, Cardinality of set, Principle of incl usion and exclusion, Types of Sets - Bounded and Unbounded Sets, Diagonalization Argument, Countable and Uncountable Sets, Finite and Infinite Sets, Countably Infinite and Uncountably Infinite Sets, Power set, Propositional Logic logic, Propositional Equivalences, Application of Propositional Logic - Translating English Sentences, Proof by Mathematical Induction and Strong Mathematical Induction. (Chapters - 1, 2, 3)

Unit II

Relations and Functions

Relations and their Properties, n-ary relations and their applications, Representing relations, Closures of relations, Equivalence relations, Partial orderings, Partitions, Hasse diagram, Lattices, Chains and Anti-Chains, Transitive closure and Warshall‘s algorithm. Functions - Surjective, Injective and Bijective functions, Identity function, Partial function, Invertible function, Constant function, Inverse functions and Compositions of functions, The Pigeonhole Principle. (Chapters - 4, 5)

(iv)

Table of Contents Unit - I Chapter - 1

Theory of Sets

(1 - 1) to (1 - 48)

1.1 Introduction ......................................................................................................1 - 2 1.2 Sets ...................................................................................................................1 - 2 1.3 Methods of Describing Sets ..............................................................................1 - 2 1.3.1 Roster Method (Listing Method) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 - 2 1.3.2 Statement Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 - 2 1.3.3 Set Builder Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 - 3

1.4 Some Special Sets .............................................................................................1 - 3 1.5 Subsets..............................................................................................................1 - 3 1.5.1 Proper Subset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 - 3 1.5.2 Improper Subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 - 4 1.5.3 Equal sets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 - 4

1.6 Types of Sets .....................................................................................................1 - 4 1.7 Venn Diagrams..................................................................................................1 - 6 1.8 Operations on Sets............................................................................................1 - 6 1.8.1 Union of Two Sets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 - 6 1.8.2 Intersection of Two Sets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 - 7 1.8.3 Disjoint Sets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 - 8 1.8.4 Complement of a Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 - 8 1.8.5 Difference of Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 - 8 1.8.6 Symmetric Difference of Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 - 10

1.9 Algebra of Set Operations...............................................................................1 - 11 1.10 Principle of Duality........................................................................................1 - 12 1.11 Cardinality of Sets ........................................................................................ 1 - 23 1.12 The Principle of Inclusion and Exclusion for Sets..........................................1 - 24

(v)

1.13 Multiset.........................................................................................................1 - 45 1.13.1 Multiplicity of an Element . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 - 46 1.13.2 Equality of Multisets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 - 46 1.13.3 Union and Intersection of Multisets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 - 46 1.13.4 Difference of Multisets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 - 47 1.13.5 Sum of Multisets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 - 47

Chapter - 2

Propositional Calculus

(2 - 1) to (2 - 38)

2.1 Introduction ......................................................................................................2 - 2 2.2 Statements or Propositions ..............................................................................2 - 2 2.3 Laws of Formal Logic.........................................................................................2 - 3 2.3.1 Law of Contradiction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 - 3 2.3.2 Law of Excluded Middle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 - 3

2.4 Connectives and Compound Statements .........................................................2 - 3 2.4.1 Compound Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 - 3 2.4.2 Truth Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 - 4 2.4.3 Negation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 - 4 2.4.4 Conjunction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 - 4 2.4.5 Disjunction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 - 5 2.4.6 Conditional Statement (If ..... then ....) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 - 6 2.4.7 Biconditional (If and only if). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 - 7 2.4.8 Special Propositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 - 8

2.5 Propositional or Statement Formula ..............................................................2 - 12 2.6 Tautology ........................................................................................................2 - 12 2.7 Contradiction ..................................................................................................2 - 12 2.8 Contingency ....................................................................................................2 - 12 2.9 Precedence Rule .............................................................................................2 - 16 2.10 Logical Equivalence.......................................................................................2 - 16 2.11 Logical Identities ...........................................................................................2 - 18 2.12 The Duality Principle.....................................................................................2 - 20 2.13 Logical Implication ........................................................................................2 - 20 (vi)

2.14 Important Connectives .................................................................................2 - 20 2.15 Normal Forms ...............................................................................................2 - 21 2.15.1 Disjunctive Normal Form (dnf) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 - 22 2.15.2 Conjunctive Normal Form (cnf) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 - 22 2.15.3 Principal Normal Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 - 22

2.16 Methods of Proof..........................................................................................2 - 27 2.16.1 Law of Detachment (or Modus Ponens) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 - 28 2.16.2 Modus Tollen (Law of Contrapositive) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 - 29 2.16.3 Disjunctive Syllogism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 - 29 2.16.4 Hypothetical Syllogism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 - 29

2.17 Quantifiers ....................................................................................................2 - 32 2.17.1 Universal Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 - 33 2.17.2 Existential Quantifier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 - 33 2.17.3 Negation of Quantified Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 - 33

Chapter - 3

Mathematical Induction

(3 - 1) to (3 - 18)

3.1 Introduction ..................................................................................................... 3 - 2 3.2 First Principle of Mathematical Induction Statement.......................................3 - 2 3.3 Second Principle of Mathematical Induction Statement (Strong Mathematical Induction) ......................................................................3 - 2

Unit - II Chapter - 4

Relations

(4 - 1) to (4 - 64)

4.1 Introduction ......................................................................................................4 - 2 4.2 Cartesian Product ............................................................................................4 - 2 4.3 Relation ............................................................................................................4 - 3 4.4 Matrix Representation of a Relation ................................................................4 - 4 4.4.1 Relation Matrix Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 5 4.4.2 Properties of Relation Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 6

4.5 Diagraphs .........................................................................................................4 - 6 4.6 Special Types of Relations ................................................................................4 - 9 4.6.1 Inverse Relation (OR Converse Relation) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 9 (vii)

4.6.2 Complement of a Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 10 4.6.3 Composite Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 11

4.7 Types of Relations on Set................................................................................4 - 12 4.7.1 Identity Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 12 4.7.2 Reflexive Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 13 4.7.3 Symmetric Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 14 4.7.4 Compatible Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 14 4.7.4.1 Asymmetric Relation . . . . . . . . . . . . . . . . . . . . . . . . 4 - 15

4.7.5 Antisymmetric Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 15 4.7.6 Transitive Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 15 4.7.7 Equivalence Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 16 4.7.8 Properties of Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 16 4.7.9 Equivalence Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 17

4.8 Partitions of a Set............................................................................................4 - 36 4.8.1 Relation Induced by a Partition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 37 4.8.2 Refinement of Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 39 4.8.3 Product and Sum of Partitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 40 4.8.4 Quotient Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 40

4.9 Closure of a Relation.......................................................................................4 - 40 4.9.1 Reflexive Closure. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 40 4.9.2 Symmetric Closure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 41 4.9.3 Transitive Closure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 42 4.9.4 Warshall's Algorithm to Find Transitive Closure . . . . . . . . . . . . . . . . . . . . . . . . 4 - 42

4.10 Partially Ordered Set.....................................................................................4 - 52 4.10.1 Hasse Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 53 4.10.2 Chains and Antichains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 54 4.10.3 Elements of Poset. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 54 4.10.4 Types of Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 56 4.10.5 Properties of a Lattice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 58 4.10.6 Types of Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 58

4.11 Principle of Duality........................................................................................4 - 59

(viii)

Chapter - 5

Functions

(5 - 1) to (5 - 28)

5.1 Introduction ......................................................................................................5 - 2 5.2 Function ............................................................................................................5 - 2 5.2.1 Important Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 - 2 5.2.2 Partial Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 - 3 5.2.3 Equality of Two Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 - 4 5.2.4 Identity Function. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 - 4 5.2.5 Constant Function. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 - 4 5.2.6 Composite Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 - 4

5.3 Special Types of Functions................................................................................5 - 6 5.4 Infini...