# cse-iii-discrete mathematical structures [10cs34]-notes

Post on 14-Apr-2018

215 views

Embed Size (px)

TRANSCRIPT

7/29/2019 Cse-III-discrete Mathematical Structures [10cs34]-Notes

1/115

DMS 10CS34

CITSTUDENTS.IN Page 1

DISCRETE MATHEMATICAL STRUCTURES(Common to CSE & ISE)

Subject Code: 10CS34 I.A. Marks : 25 Hours/Week : 04 Exam Hours: 03 Total Hours : 52 Exam Marks: 100

PART A

UNIT 1 6 Hours

Set Theory: Sets and Subsets, Set Operations and the Laws of Set Theory, Counting andVenn Diagrams, A First Word on Probability, Countable and Uncountable Sets

UNIT 2 7 Hours

Fundamentals of Logic: Basic Connectives and Truth Tables, Logic Equivalence TheLaws of Logic, Logical Implication Rules of Inference

UNIT 3 6 Hours

Fundamentals of Logic contd.: The Use of Quantifiers, Quantifiers, Definitions and theProofs of Theorems

UNIT 4 7 Hours

Properties of the Integers: Mathematical Induction, The Well Ordering Principle Mathematical Induction, Recursive Definitions

PART B

UNIT 5 7 Hours

Relations and Functions: Cartesian Products and Relations, Functions Plain and One-to-One, Onto Functions Stirling Numbers of the Second Kind, Special Functions, ThePigeon-hole Principle, Function Composition and Inverse Functions

UNIT 6 7 Hours

Relations contd.: Properties of Relations, Computer Recognition Zero-One Matrices andDirected Graphs, Partial Orders Hasse Diagrams, Equivalence Relations and Partitions

UNIT 7 6 Hours

Groups: Definitions, Examples, and Elementary Properties, Homomorphisms,

Isomorphisms, and Cyclic Groups, Cosets, and Lagrange s Theorem.Coding Theory and Rings: Elements of Coding Theory, The Hamming Metric, The ParityCheck, and Generator Matrices

7/29/2019 Cse-III-discrete Mathematical Structures [10cs34]-Notes

2/115

DMS 10CS34

CITSTUDENTS.IN Page 2

UNIT 8 6 Hours

Group Codes: Decoding with Coset Leaders, Hamming Matrices Rings and Modular Arithmetic: The Ring Structure Definition and Examples, Ring Properties andSubstructures, The Integers Modulo n

Text Book:

1. Ralph P. Grimaldi: Discrete and Combinatorial Mathematics,5 Edition, PearsonEducation, 2004. (Chapter 3.1, 3.2, 3.3, 3.4, Appendix 3, Chapter 2, Chapter 4.1, 4.2,Chapter 5.1 to 5.6, Chapter 7.1 to 7.4, Chapter 16.1, 16.2, 16.3, 16.5 to 16.9, and Chapter 14.1, 14.2, 14.3).Reference Books:

1. Kenneth H. Rosen: Discrete Mathematics and its Applications, 7 Edition, McGraw Hill,2010.2. Jayant Ganguly: A Treatise on Discrete Mathematical Structures, Sanguine-Pearson,

2010.3. D.S. Malik and M.K. Sen: Discrete Mathematical Structures: Theory and Applications,Cengage Learning, 2004.4. Thomas Koshy: Discrete Mathematics with Applications, Elsevier, 2005, Reprint 2008.

7/29/2019 Cse-III-discrete Mathematical Structures [10cs34]-Notes

3/115

DMS 10CS34

CITSTUDENTS.IN Page 3

INDEX SHEET

PART A Page no.

UNIT 1 Set Theory: 5 - 15

UNIT

2 Fundamentals of Logic: 16 - 29UNIT 3 Fundamentals of Logic contd.: 30 - 38

UNIT 4 Properties of the Integers: 39 - 48

PART B Page no.

UNIT 5 Relations and Functions: 49 - 60

UNIT 6 Relations contd.: 61 - 74

UNIT 7 Groups:

Coding Theory and Rings:

75 - 90

91 - 103

UNIT 8 Group Codes: 104 - 115

7/29/2019 Cse-III-discrete Mathematical Structures [10cs34]-Notes

4/115

DMS 10CS34

CITSTUDENTS.IN Page 4

PART A

UNIT 1 Set Theory: 6 Hours

Sets and Subsets,

Set Operations and the Laws of Set Theory,

Counting and Venn Diagrams,

A First Word on Probability,

Countable and

Uncountable Sets

7/29/2019 Cse-III-discrete Mathematical Structures [10cs34]-Notes

5/115

DMS 10CS34

CITSTUDENTS.IN Page 5

DISRETE MATHEMATICAL STRUCTURES

UNIT I 6 Hours Set Theory

Sets: A set is a collection of objects, called elements of the set. A set can be presented by list ing its elemen t s between braces: A = { 1, 2, 3, 4, 5} . The symbol e is

used to express that an element is (or belongs to) a set. For instance 3 e A. Itsnegation is r e pr esent ed by /e, e.g. 7 /e A. If the set Is finite, its number of elemen t sis represented |A|, e.g. if A = { 1, 2, 3, 4, 5} then |A| =5

Some imp ort an t sets are the following:

1. N = { 0, 1, 2, 3, } = the set of natural numb ers.2. Z = { , 3, 2, 1, 0, 1, 2, 3, } = the set of in teg er s. 3. Q = the set of rational numb ers.4. R = the set of real numb ers.5. C = the set of complex numb ers.

If S is one of those sets then we also use the following notations :

1. S + = set of positive elements in S , for ins t anceZ + = { 1, 2, 3, } = the set of positive in t egers.

2. S = set of negative elements in S , for ins t anceZ = {1, 2, 3, } = the set of negative in teg er s.

3. S = set of elements in S excluding zero, for instance R = the set of non zero realnumb er s.

Set-builder notation: An alternative way to define a set, called set- builder notation, is by stating a property (predicate) P (x) verified by exactly its elements, for instanceA = {x e Z | 1 x 5} = set of integers x such that 1 x 5 i.e.: A = { 1, 2, 3,4, 5} . In general: A = {x e U | p(x) } , where U is the universe of discourse in whichthe predicate P (x) must be interpreted, or A = {x | P (x)} if the universe of discoursefor P (x) is implicitly understood. In set theory the t er m universal set is of t en used in

place of universe of discourse for a given predicate.

7/29/2019 Cse-III-discrete Mathematical Structures [10cs34]-Notes

6/115

DMS 10CS34

CITSTUDENTS.IN Page 6

Principle of Extension: Two set s are equal if and only if they have the same

elements, i.e.: A = B x (x e A x e B) .

Subset: We say that A is a subset of set B, or A is contained in B, and we r e p resen t

it A

B

, if all elements of A are in B, e.g., if A = {a, b, c

} andB = {a, b, c, d, e} then A B .

Proper subset: A is a proper subset of B, represen t ed A B , if A B but A = B, i.e., there is some elemen t in B which is not in A .

Empty Set: A set with no elements is called empty set (or null set,

or void set ), and is represented by or {} .

Note that nothing prevents a set from possibly being an elemen t of another set (whichis not the same as being a subset!). For i n s t ance

if A = { 1, a, { 3, t } , { 1, 2, 3}} and B= { 3, t} , then obviously B is an element of A,i.e., B e A .

Power Set: The collect ion of all subsets of a set A is called the power set of A,and is represented P(A). For instance, if A = { 1, 2, 3} , then

P(A) = { , { 1} , { 2} , { 3} , { 1, 2} , { 1, 3} , { 2, 3} , A} .

Multisets: Two ordinary set s are identical if they have the same elements, so for inst ance, {a, a, b} and {a, b} are the same set because they have exa ct ly the sameelements, name ly a and b. However, in some applications it mig ht be useful toallow repeated elements in a set. In that case we use multisets, which aremathematical entities similar to sets, but with possibly repeated elements. So, asmultisets, {a, a, b} and {a, b} would be considered different, since in the first one theelemen t a occurs twice and in the second one it occurs only once.

Set Op erati ons:

1. Intersection : The common elements of two sets:

A B = {x | (x e A) (x e B) } . If A B =, the sets are said to be disjoint.

2. Union : The set of elements that belong to either of two sets:

A B = {x | (x e A) (x e B) } .

7/29/2019 Cse-III-discrete Mathematical Structures [10cs34]-Notes

7/115

7/29/2019 Cse-III-discrete Mathematical Structures [10cs34]-Notes

8/115

7/29/2019 Cse-III-discrete Mathematical Structures [10cs34]-Notes

9/115

7/29/2019 Cse-III-discrete Mathematical Structures [10cs34]-Notes

10/115

DMS 10CS34

CITSTUDENTS.IN Page 10

Generalized Union and Intersection: Given a collec- tion of sets A 1 , A 2 , . . . ,A N , their union is defined as the set of elements that belong to at least one of the sets(here n represents an integer in the range from 1 to N ):

7/29/2019 Cse-III-discrete Mathematical Structures [10cs34]-Notes

11/115

7/29/2019 Cse-III-discrete Mathematical Structures [10cs34]-Notes

12/115

DMS 10CS34

CITSTUDENTS.IN Page 12

{ (a 1 , a2, . . . , a m ) | (a1 e A 1) (a2 e A 2) (a m e A m )} . If all the sets in a Cartesian product are the same, then we can use an exponen t : A2 =A A, A 3 = A A A, et c. In general:(m tim es)m = A A A .

A First Word on Probability: Introduction: Assume that we perform an exp er imen t such as tossing a coin or rolling a die. The set of possible outcomes is called the sample space of the experiment.An event is a subset of the sample space. For instance, if we toss a coin three t imes,the sample space is

S { H H H, H H T , H T H, H T T , T H H, T H T , T T H, T T T } .The even t at least two heads in a ro wwould be the subset

E { H H H, H H T , T H H } .

If all possible outcomes of an experimen t have the same likelihood of occurrence, then

the probability of an event A S is given by Laplace s rule:

For instance, the probability of get ting at least two heads in a row inthe above experimen t is 3/ 8.

Properties of probabi li t y: Let P be a probability func- tion on a sample space S .The n:

7/29/2019 Cse-III-discrete Mathematical Structures [10cs34]-Notes

13/115

DMS 10CS34

CITSTUDENTS.IN Page 13