MCS-013: Discrete Mathematics
(2 Credits)
Objectives
Discrete mathematics, sometimes called finite mathematics, is the study of mathematical structure that are fundamentally discrete, in the sense of not supporting notion of continuity. A study of discrete sets has become more and more necessary because of many application of Computer Science and various areas of engineering. Regarding computer science concept from discrete mathematics are useful to study or express objects or problems in computer algorithm and programming languages. For instance, to improve the efficiency of a computer programs, we need to study its logical structure, which involves a finite number of steps each requiring a certain amount of time. Using the theory of combinatory and graph theory, major areas of discrete mathematics, we can do this. Therefore, a study of these areas would complement and improve the understanding of courses based on algorithm and problem solving.
This course is designed to give basic concepts of propositions, predicates, Boolean algebra, logic circuit, sets, relations, functions, combinatorics, partitions and distributions.
Syllabus
Block 1:
Elementary Logic
Unit 1:Prepositional
Calculus
·
Propositions
·
Logical Connectives
o
Disjunction
o
Conjunction
o
Negation
o
Conditional Connectives
o
Precedence Rule
·
Logical Equivalence
·
Logical Quantifiers
Unit 2:Methods of Proof
·
What is a
Proof?
·
Different Methods of Proof
o
Direct Proof
o
Indirect Proofs
o
Counter examples
·
Principle of Induction
Unit 3:Boolean
Algebra and Circuits
·
Boolean Algebras
·
Logic Circuits
·
Boolean Functions
Block 2:
Basic Combinatorics
Unit 1:Sets,
Relations and Functions
·
Introducing Sets
·
Operations on Sets
o
Basic Operations
o
Properties Common to Logic and Sets
·
Relations
o
Cartesian Product
o
Relations and their types
o
Properties of Relations
·
Functions
o
Types of Functions
o
Operations on Functions
Unit 2:Combinatorics – An Introduction
·
Multiplication and Addition
Principles
·
Permutations
o
Permutations of Objects not Necessarily Distinct
o
Circular Permutations
·
Combinations
·
Binomial Coefficients
·
Combinatorial Probability
Unit 3:Some
More Counting Principles
·
Pigeonhole Principle
·
Inclusion-Exclusion
Principle
·
Applications of Inclusion
– Exclusion
o
Application to Surjective
Functions
o
Application to Probability
o
Application to Derangements
Unit 4:Partitions
and Distributions
·
Integer Partitions
·
Distributions
o
Distinguishable Objects into Distinguishable Containers
o
Distinguishable Objects into Indistinguishable Containers
o
Indistinguishable Objects into Distinguishable Containers
o
Indistinguishable Objects into Indistinguishable Containers