Scribd
Upload
687 views91 pages

Set Theory and Logic in Discrete Math

The document provides an overview of discrete structures and logic theory (KCS-303) taught by Virendra Pal Singh at Ajay Kumar Garg Engineering College. It covers the following topics in the first unit: 1) Set theory concepts like combinations of sets, multisets and ordered pairs as well as proofs of general set identities. 2) Relations including definitions, operations, properties, composite and equality of relations as well as recursive relation definitions. 3) Functions covering definitions, classifications, operations, recursively defined functions and growth of functions. 4) Natural numbers introducing induction, variants of induction, induction with non-zero bases and proof methods like proof by counter-example and contradiction. The objectives are to

Uploaded by

Nitesh pandey
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
687 views91 pages

Set Theory and Logic in Discrete Math

The document provides an overview of discrete structures and logic theory (KCS-303) taught by Virendra Pal Singh at Ajay Kumar Garg Engineering College. It covers the following topics in the first unit: 1) Set theory concepts like combinations of sets, multisets and ordered pairs as well as proofs of general set identities. 2) Relations including definitions, operations, properties, composite and equality of relations as well as recursive relation definitions. 3) Functions covering definitions, classifications, operations, recursively defined functions and growth of functions. 4) Natural numbers introducing induction, variants of induction, induction with non-zero bases and proof methods like proof by counter-example and contradiction. The objectives are to

Uploaded by

Nitesh pandey
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
  • Unit-1: Set Theory
  • Practice Questions for Set Theory
  • Unit-2: Relations
  • Unit-3: Functions

DISCRETE STRUCTURES

& THEORY OF LOGIC


(KCS-303)
By- Virendra Pal Singh
(Ajay Kumar Garg Engg. College)
Unit-1
Contents:
Set Theory: Introduction, Combination of sets, Multisets,
Ordered pairs. Proofs of some general identities on sets.
Relations: Definition, Operations on relations, Properties of
relations, Composite Relations, Equality of relations, Recursive
definition of relation, Order 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.
Learning Objective of the Unit
The objectives of the contents of this unit is to
make student aware about the :
Describe the concept of set theory.
Understand the concept behind relations.
Learn about the use and applications of function.
Study about natural number concept and mathematical
induction.
Introduction
Discrete: consisting of distinct or unconnected elements.
Discrete Structure is a collection of topics that examine and use finite or
countable infinite objects or structures.

Discrete vs. Continuous


 Discrete deals with only real numbers, which are multiple of some basic
units.
 If basic unit is one, then the discrete variable can assume only integral
values.
 Discrete variable can not become infinitely small and concept as
instantaneous rate of change is not present.
 It is different from branches as calculus which deals with continuous
functions.
Sets Theory
Operations on Sets
Algebra of Sets
Sets under the operations of union, intersection, and complement satisfy various laws
(identities) which are listed in Table-
Multisets
Practice Questions from Set Theory
Relations:
Relations show a link between elements of two sets and may hold reflexive,
irreflexive, symmetric, antisymmetric, or transitive properties.
Function
What is a Recursively Defined Function?
For any recursively defined function, it has two parts. The first part is the definition of the
smallest argument and the second part is the definition of the nth term. The smallest
argument is usually denoted by f(0) or f(1) and the nth argument is denoted by f(n).  
Now, let us understand the recursively defined function with the help of an example.
Let the sequence be 5, 7, 9, 11
The explicit formula for the given sequence is f(n)= 2n+5
The recursive formula for the given sequence is given by
f(0)= 5
f(n) = f(n-1)+2
Now, we can check the sequence terms using the recursive formula as follows:
f(0)= 5
f(1) = f(0)+2
f(1)= 5+2 = 7
f(2) = f(1)+2 
f(2)= 7+2 =9
f(3)= f(2)+2
f(3)= 9+2 = 11
In this way, we can find the next term in the sequence with the help of the recursive function
formula.

DISCRETE STRUCTURES & THEORY OF LOGIC (KCS-303) By- Virendra Pal Singh (Ajay Kumar Garg Engg. College)
Unit-1 Contents: Set Theory: Introduction, Combination of sets, Multisets, Ordered pairs. Proofs of some general identities
Learning Objective of the Unit The objectives of the contents of this unit is to make student aware about the : Describe th
Introduction Discrete: consisting of distinct or unconnected elements. Discrete Structure is a collection of topics that e
Sets Theory

You might also like