Discrete Structures and Theory of Logic
Lecture-1
September 7, 2022
Syllabus
Syllabus
Unit-1
Set Theory: Introduction, Combination of sets, Multisets, Ordered
pairs. Proofs of some general identities on sets. Relations: Defi-
nition, Operations on relations, Properties of relations, Composite
Relations, Equality of relations, Recursive definition of relation, Or-
der of relations.
Functions: Definition, Classification of functions, Operations on
functions, Recursively defined functions. Growth of Functions.
Natural Numbers: Introduction, Mathematical Induction, Variants
of Induction, Induction with Nonzero Base cases. Proof Methods,
Proof by counter – example, Proof by contradiction.
1
Syllabus cont.
Unit-2
Algebraic Structures: Definition, Groups, Subgroups and order,
Cyclic Groups, Cosets, Lagrange’s theorem, Normal Subgroups, Per-
mutation and Symmetric groups, Group Homomorphisms, Definition
and elementary properties of Rings and Fields.
2
Syllabus cont.
Unit-3
Lattices: Definition, Properties of lattices –Bounded, Comple-
mented, Modular and Complete lattice. Boolean Algebra: Introduc-
tion, Axioms and Theorems of Boolean algebra, Algebraic manipu-
lation of Boolean expressions. Simplification of Boolean Functions,
Karnaugh maps, Logic gates, Digital circuits and Boolean algebra.
Unit-4
Propositional Logic: Proposition, well formed formula, Truth ta-
bles, Tautology, Satisfiability, Contradiction, Algebra of proposition,
Theory of Inference.
Predicate Logic: First order predicate, well formed formula of pred-
icate, quantifiers, Inference theory of predicate logic.
3
Syllabus cont.
Unit-5
Trees: Definition, Binary tree, Binary tree traversal, Binary search
tree.
Graphs: Definition and terminology, Representation of graphs, Multi-
graphs, Bipartite graphs, Planar graphs, Isomorphism and Homeo-
morphism of graphs, Euler and Hamiltonian paths, Graph coloring,
Recurrence Relation Generating function: Recursive definition of
functions, Recursive algorithms, Method of solving recurrences.
Combinatorics: Introduction, Counting Techniques, Pigeonhole
Principle
4
Reference books
Reference books
1. Kenneth H. Rosen, Discrete Mathematics and Its
Applications, 6/e, McGraw-Hill, 2006.
2. B. Kolman, R.C. Busby, and S.C. Ross, Discrete
Mathematical Structures, 5/e, Prentice Hall, 2004.
3. Trembley, J.P R. Manohar, “Discrete Mathematical Structure
with Application to Computer Science”, McGraw Hill.
4. Sarkar, Swapan Kumar, Discrete Mathematics, S. Chand.
5
Course Outcome
Course Outcome
CO1 Describe and Identify concepts of set theory, relation, function
and Apply proof of induction method to proof the statements
CO2 Describe and Recognize group, ring and field and Solve the
problem related with Group theory
CO3 Describe Lattice and Boolean algebra and Identify different
types of lattice.
CO4 Formulate logic statements in terms of predicates, quantifiers,
and logical connectives and Derive an expression equivalent to
another expression.
CO5 Explain Trees, Graphs and Identify types of Graph and Solve
problems related with Combinatory, Recurrence relations and
Generating functions.
6
Set
Set
• A well-defined collection of distinct objects can be considered
to be a set.
• A set is typically expressed by curly braces, {} enclosing its
elements.
• If A is a set and a is an element of it, then we write a ∈ A.
The fact that a is not an element of A is written as a ∈ / A.
• For instance, if A is the set {1, 2, 4, 9}, then 1 ∈ A; 4 ∈ A; 2
∈ A and 9 ∈ A. But 7 ∈ / A; 10 ∈/ A, the English word ‘four’ is
not in A, etc.
7
Representation of sets
Representation of sets
We can represent sets in two ways.
1. Tabular form or roster form: Listing the elements of a set
inside a pair of braces { } is called the roster form.
2. Set builder form: In the set builder form, all the elements of
the set, must possess a single property to become the member of
that set.
8
Examples
Examples
1. Let X = {apple, tomato, orange}. Here, orange ∈ X, but
potato ∈
/ X.
2. X = {a1 , a2 , ............., a100 }. Then, a100 ∈ X.
3. Observe that the sets {1, 2, 3} and {3, 1, 2} are equal.
4. Let X = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Then X is the set of first
10 natural numbers. Or equivalently, X is the set of integers
between 0 and 11.
5. X = {x : x is a prime number}.
6. X = {x : 0 < x ≤ 10 and x is an even integer }
Clearly examples 1, 2, 3, and 4 are in roster form, but 5 and 6 are
in set builder form.
9
Cardinality of a set
Cardinality of a set
The number of elements in a set is said to be cardinality of a set.
It is denoted by || symbol. That is, if A is a set then cardinality of
set A is denoted by |A|.
Example: X = {x : 0 < x ≤ 10 and x is an even integer }
The cardinality of this set, |X | = 5.
10
Types of set
Types of set
Finite and Infinite sets
A set is said to be finite if the number of elements in the set is
finite otherwise it is said to be infinite.
For example, a set of days in a week, set of months in a year, and
a set of integer lie between 1 and 100 are finite sets. But set of
integers, set of real numbers, and set of stars in sky are infinite
sets.
Null or Empty set
A set which does not contain any element, is said to be null set. It
is denoted by ϕ.
Example: set A = {a : a is an integer lie between 4 and 5}
11
Types of set(Cont.)
Singleton set
A set is said to be singleton set if it contains only one element.
Universal set
A universal set is the set of all elements under consideration,
denoted by capital U or sometimes capital E.
Example: If we consider the elements are integers, then universal
set will be the set of integer numbers. Similarly, if the elements are
days of a week, then the set of all days in a week will be the
universal set.
12
Types of set(Cont.)
Subset
Consider two sets A and B. Set B is said to be subset of A if all
the elements of B belong into A. It is denoted by ⊆ symbol. That
is, B ⊆ A.
Example: Consider three sets A, B and C such that A= { 2, 3, 5,
8}, B= { 3, 5}, C={ 2, 9, 5, 8}. Clearly B is a subset of A but B
is not a subset of C. Similarly, neither A is a subset of C nor C is a
subset of A.
Note: (1) Every set A is a subset of itself i.e. A ⊆ A.
(2) The null set ϕ is a subset of any set.
(3) If A ⊆ B and B ⊆ C then A ⊆ C.
13
Types of set(Cont.)
Superset
Consider two sets A and B. Set A is said to be superset of B if all
the elements of B belong into A. It is denoted by ⊇ symbol. That
is, A ⊇ B.
Example: Consider three sets A, B and C such that A= { 2, 3, 5,
8}, B= { 3, 5}, C={ 2, 9, 5, 8}. Clearly A is a superset of B but
C is not a superset of B. Similarly, neither A is a superset of C nor
C is a superset of A.
14
Types of set(Cont.)
Proper and Improper subsets
A set B is said to proper subset of set A if B is a subset of A and
not equal to A that is B ⊆ A and A ̸= B. It is denoted by ⊃.
Therefore, we can represent proper subset as B ⊂ A.
A set B is said to improper subset of set A if B is a subset of A
and equal to A that is B ⊆ A and A = B.
Example: Consider four sets A, B, C and D such that A= { 2, 3,
5, 8}, B= { 3, 5}, C={ 2, 3, 5}, D={ 2, 3, 5, 8}. Clearly, B and
C are the proper subsets of A and D is an improper subset of A.
15
Types of set(Cont.)
Equal set
Two sets are said to be equal if both contains same elements.
That is, if A ⊆ B and B ⊆ A then A = B.
Power set
The power set of a set A is the set of all the subsets of set A. It is
denoted by P(A) or 2A .
Example: (1) Consider set A = { a, b, c}. Then the power set of
A is, P(A) = {ϕ ,{a},{b},{c},{a,b},{b,c},{a,c},{a,b,c}}.
(2) The power set of null or empty set will be {ϕ}.
Note: If set A has n elements then number of elements in the
power set of A will be 2n .
16