# discrete mathematical structures [as per p. grimaldi: discrete and combinatorial mathematics, , 5th...

Post on 06-Feb-2018

243 views

Embed Size (px)

TRANSCRIPT

DISCRETE MATHEMATICAL STRUCTURES15CS36

DISCRETE MATHEMATICAL STRUCTURES[As per Choice Based Credit System (CBCS) scheme]

SEMESTER - IIISubject Code 15CS36 IA Marks 20Number of Lecture

04 Exam Marks 80Hours/WeekTotal Number of

50 Exam Hours 03Lecture HoursCourse objectives:. This course will enable students to Prepare for a background in abstraction, notation, andcritical thinking for the mathematics most directly related to computer science.

Understand and apply logic, relations, functions, basic set theory, countability and countingarguments, proof techniques,

Understand and apply mathematical induction, combinatorics, discrete probability, recursion,sequence and recurrence, elementary number theory

Understand and apply graph theory and mathematical proof techniques.Module -1

Set Theory: Sets and Subsets, Set Operations and the Laws of SetTheory, Counting and Venn Diagrams, A First Word on Probability,Countable and Uncountable Sets.Fundamentals of Logic: Basic Connectives and Truth Tables, LogicEquivalence The Laws of Logic, Logical Implication Rules ofInference.Module -2Fundamentals of Logic contd.: The Use of Quantifiers, Quantifiers,Definitions and the Proofs of Theorems, Properties of the Integers:Mathematical Induction, The Well Ordering Principle Mathematical Induction, Recursive DefinitionsModule 3Relations and Functions: Cartesian Products and Relations,Functions Plain and One-to-One, Onto Functions StirlingNumbers of the Second Kind, Special Functions, The Pigeon-holePrinciple, Function Composition and Inverse Functions.Module-4Relations contd.: Properties of Relations, Computer Recognition Zero-One Matrices and Directed Graphs, Part ial Orders HasseDiagrams, Equivalence Relations and Partitions.Module-5Groups: Definitions, properties, Homomrphisms, Isomorphisms,Cyclic Groups, Cosets, and Lagranges Theorem. Coding Theoryand Rings: Elements of CodingTheory, The Hamming Metric, TheParity Check, and Generator Matrices. Group Codes: Decodingwith Coset Leaders, Hamming Matrices. Rings and ModularArithmetic: The Ring Structure Definition and Examples, RingProperties and Substructures, The Integer modulo n.

TeachingHours

10 Hours

10 Hours

10 Hours

10 Hours

10 Hours

RBTLevels

L2, L3

L3, L4

L3,L4,L5

L3,L4,L5

L3,L4,L5

DEPT. OF CSE, ACE Page 1

DISCRETE MATHEMATICAL STRUCTURES15CS36

Course outcomes:After studying this course, students will be able to:1. Verify the correctness of an argument using propositional and predicate logic and truth tables.2. Demonstrate the ability to solve problems using counting techniques and combinatorics in the

context of discrete probability.3. Solve problems involving recurrence relations and generating functions.4. Perform operations on discrete structures such as sets, functions, relations, and sequences.5. Construct proofs using direct proof, proof by contraposition, proof by contradiction, proof by

cases, and mathematical induction.Graduate Attributes (as per NBA)1. Engineering Knowledge2. Problem Analysis3. Conduct Investigations of Complex Problems4. Design/Development of SolutionsQuestion paper pattern:The question paper will have ten questions.There will be 2 questions from each module.Each question will have questions covering all the topics under a module.The students will have to answer 5 full questions, selecting one full question from each module.Text Books:1.Ralph P. Grimaldi: Discrete and Combinatorial Mathematics, , 5th Edition, Pearson Education. 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, 6th Edition, McGraw Hill,

2007.2. JayantGanguly: A TreatCSE on Discrete Mathematical Structures, Sanguine-Pearson, 2010.3. D.S. Malik and M.K. Sen: Discrete Mathematical Structures: Theory and Applications,

Thomson, 2004.4. Thomas Koshy: Discrete Mathematics with Applications, Elsevier, 2005, Reprint 2008.

DEPT. OF CSE, ACE Page 2

DISCRETE MATHEMATICAL STRUCTURES15CS36

Module s

Module -1

Module -2

Module -3

Module -4

Module -5

INDEX SHEET

Contents Page No.Set Theory: Sets and Subsets, Set Operations and the Laws of SetTheory, Counting and Venn Diagrams, A First Word on Probability,

Countable and Uncountable Sets.04-26

Fundamentals of Logic: Basic Connectives and Truth Tables, Logic

Equivalence The Laws of Logic, Logical Implication Rules of

Inference.

Fundamentals of Logic contd.: The Use of Quantifiers, Quantifiers,Definitions and the Proofs of Theorems, Properties of the Integers:

27-40Mathematical Induction, The Well Ordering Principle Mathematical

Induction, Recursive Definitions

Relations and Functions: Cartesian Products and Relations, Functions Plain and One-to-One, Onto Functions Stirling Numbers of the

41-68Second Kind, Special Functions, The Pigeon-hole Principle, Function

Composition and Inverse Functions.

Relations contd.: Properties of Relations, Computer Recognition

Zero-One Matrices and Directed Graphs, Partial Orders Hasse 69-76Diagrams, Equivalence Relations and Partitions.

Groups: Definitions, properties, Homomrphisms, Isomorphisms,Cyclic Groups, Cosets, and Lagranges Theorem. Coding Theory and

Rings: Elements of CodingTheory, The Hamming Metric, The Parity

Check, and Generator Matrices. Group Codes: Decoding with Coset 77-114Leaders, Hamming Matrices. Rings and Modular Arithmetic: The

Ring Structure Definition and Examples, Ring Properties and

Substructures, The Integer modulo n

DEPT. OF CSE, ACE Page 3

DISCRETE MATHEMATICAL STRUCTURES15CS36

Module 1: Set Theory:

Sets and Subsets,

Set Operations and the Laws of Set Theory,

Counting and Venn Diagrams,

A First Word on Probability,

Countable and

Uncountable Sets

Fundamentals of Logic:

Basic Connectives and Truth Tables,

Logic Equivalence The Laws of Logic,

Logical Implication Rules of Inference.

DEPT. OF CSE, ACE Page 4

DISCRETE MATHEMATICAL STRUCTURES15CS36

Set Theory:

Sets and Subsets:A set is a collection

of objects, called elements of

the set. A

set can be

by listing

itsbetween

braces: A = {1, 2, 3, 4, 5}. The symbol e is (or

belongs to) a set.elements

For instance3 e A. Its negation is represented by /e,

e.g. 7 /e A. If the set Is

finite, its

number of elements is represented |A|, e.g. if A = {1, 2, 3, 4, 5} then

| A| = 5

1. N = {0, 1, 2, 3, } = the set of natural numbers.2. Z = { , -3, -2, -1, 0, 1, 2, 3, } = the set of integers.3. Q = the set of rational numbers.4. R = the set of real numbers.5. C = the set of complex numbers.If S is one of those sets

then we also use the following notations :

1. S +

= set of positive

elements

in S, forinstance

Z +

= {1, 2, 3, } =

the set of positiveintegers.

2. S-= set

of negative elements in S, for instance

Z-= {-1, -2, -3, } = the

set of negativeintegers.

3. S = set

ofelements

in S

excluding zero, for instance R = the set of non zero real

num bers.

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

itselements,for instance

A = {x e Z

| 1 x 5}=

set of integers

x such that 1 x

5i.e.: A = {1, 2, 3,

4, 5}. In

general: A = {x e U | p(x)}, where

U is the

universe

ofdiscourse in which

the predicate P (x)

must

be interpreted, or A = {x | P (x)} if the universe of discourse

for P (x) is understood In set the term universalis often used in

implicitly . theory setplace of universe of discourse for a given predicate.Principle

of Extension: Two sets are equalif and

only if they have the same

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

A = B

Subset: We say that

A is a subset

of set B,

or A is contained

in B,and we represent

it A B,if all elements

of A are in B, e.g.,

if A = {a, b, c}and

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

Proper subset: A is a

proper

subset

of B,

represented A B, if A B

A = B,i.e., there is some element in B

which isnot in A.

DEPT. OF CSE, ACE

Page 5

DISCRETE MATHEMATICAL STRUCTURES15CS36

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

element of another

set

(which

is not the same as being a subset!). For i n stance

if A =

{1, a, {3, t}, { 1, 2, 3}}and B=

{ 3, t}, t hen

obvious ly B

is an elem ent of A,

i.e., B

e A.

Power

Set: The

collection

of all

subsets of a set

A is called

the power set of A,

andis represented

P(A). For instance, if A = {1, 2, 3}, then

P(A) = {,{1},

{2}, {3}, {1, 2}, {1, 3}, {2, 3}, A} .

MultCSEts: Two

ordinary

sets are

identical if they have the

same elements, so for

instance, {a, a, b}and

{a, b} are

the same

set because they have

exactly the same

elements, and