Class notes
Discrete Mathematics
- Course
- Institution
- Book
Discrete Mathematics
[Show more]
Connected book
Book Title:
Author(s):
- Edition:
- ISBN:
- Edition:
More summaries for
-
discrete maths
-
Arguments with quantified statement
-
Mat 232
Seller
Follow
Sasikalyan
Content preview
UNIT-2Set Theory
Set:A set is collection of well defined objects.
In the above definition the words set and collection for all practical purposes are Synonymous. We have really
used the word set to define itself.
Each of the objects in the set is called a member of an element of the set. The objects themselves can be almost
anything. Books, cities, numbers, animals, flowers, etc. Elements of a set are usually denoted by lower-case
letters. While sets are denoted by capital letters of English larguage.
The symbol ∈ indicates the membership in a set.
If ―a is an element of the set A‖, then we write a ∈ A.
The symbol ∈ is read ―is a member of ‖ or ―is an element of ‖.
The symbol is used to indicate that an object is not in the given set.
The symbol is read ―is not a member of ‖ or ―is not an element of ‖.
If x is not an element of the set A then we write x A.
Subset:
A set A is a subset of the set B if and only if every element of A is also an element of B. We also say that A is
contained in B, and use the notation A B.
Proper Subset:
A set A is called proper subset of the set B. If (i) A is subset of B and (ii) B is not a subset A i.e., A is said to be
a proper subset of B if every element of A belongs to the set B, but there is atleast one element of B, which is
not in A. If A is a proper subset of B, then we denote it by A B.
Super set: If A is subset of B, then B is called a superset of A.
Null set: The set with no elements is called an empty set or null set. A Null set is designated by the symbol .
The null set is a subset of every set, i.e., If A is any set then A.
Universal set:
In many discussions all the sets are considered to be subsets of one particular set. This set is called the
universal set for that discussion. The Universal set is often designated by the script letter . Universal set in
not unique and it may change from one discussion to another.
Power set:
The set of all subsets of a set A is called the power set of A.
The power set of A is denoted by P (A). If A has n elements in it, then P (A) has 2n elements:
Disjoint sets:
Two sets are said to be disjoint if they have no element in common.
Union of two sets:
The union of two sets A and B is the set whose elements are all of the elements in A or in B or in both. The
union of sets A and B denoted by A B is read as ―A union B‖.
Intersection of two sets:
The intersection of two sets A and B is the set whose elements are all of the elements common to both A and B.
The intersection of the sets of ―A‖ and ―B‖ is denoted by A B and is read as ―A intersection B‖
Difference of sets:
If A and B are subsets of the universal set U, then the relative complement of B in Ais the set of all elements in
A which are not in A. It is denoted by A – B thus: A – B = {x | x ∈ A and x B}
www.Jntufastupdates.com 1
44
,Complement of a set:
If U is a universal set containing the set A, then U – A is called the complement of A. It is denoted by A1 . Thus
A1 = {x: x A}
Inclusion-Exclusion Principle:
The inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining
the number of elements in the unionof two finite sets; symbolically expressed as
|A ∪ B| = |A| + |B| − |A ∩ B|.
Fig.Venn diagram showing the
union of sets A and B
where A and B are two finite sets and |S| indicates the cardinality of a set S (which may be considered as the
number of elements of the set, if the set is finite). The formula expresses the fact that the sum of the sizes of
the two sets may be too large since some elements may be counted twice. The double-counted elements are
those in the intersection of the two sets and the count is corrected by subtracting the size of the intersection.
The principle is more clearly seen in the case of three sets, which for the sets A, B and C is given by
|A ∪ B∪ BC| = |A| + |B|+ |C| − |A ∩ B|− |C ∩ B| − |A ∩ C|+|A ∩B∩C|.
Fig.Inclusion–exclusion illustrated by a
Venn diagram for three sets
This formula can be verified by counting how many times each region in the Venn diagram figure is included
in the right-hand side of the formula. In this case, when removing the contributions of over-counted elements,
the number of elements in the mutual intersection of the three sets has been subtracted too often, so must be
added back in to get the correct total.
In general, Let A1, · · · , Ap be finite subsets of a set U. Then,
Example: How many natural numbers n ≤ 1000 are not divisible by any of 2, 3?
Ans: Let A2 = {n ∈ N | n ≤ 1000, 2|n} and A3 = {n ∈ N | n ≤ 1000, 3|n}.
Then, |A2 ∪ A3| = |A2| + |A3| − |A2 ∩ A3| = 500 + 333 − 166 = 667.
So, the required answer is 1000 − 667 = 333.
Example: How many integers between 1 and 10000 are divisible by none of 2, 3, 5, 7?
Ans: For i ∈ {2, 3, 5, 7}, let Ai = {n ∈ N | n ≤ 10000, i|n}.
Therefore, the required answer is 10000 − |A2 ∪ A3 ∪ A5 ∪ A7| = 2285.
www.Jntufastupdates.com 2
45
,Relations
Definition: Any set of ordered pairs defines a binary relation.
We shall call a binary relation simply a relation. Binary relations represent
relationships between elements of two sets. If R is a relation, a particular ordered pair, say (x,
y) ∈ R can be written as xRy and can be read as ―x is in relation R to y‖.
Example: Give an example of a relation.
′ ′
Solution: The relation ―greater than‖ for real numbers is denoted by > . If x and y are any
two real numbers such that x > y, then we say that (x, y) ∈>. Thus the relation > is { } >= (x,
y) : x and y are real numbers and x > y
Example: Define a relation between two sets A = {5, 6, 7} and B = {x, y}.
Solution: If A = {5, 6, 7} and B = {x, y}, then the subset R = {(5, x), (5, y), (6, x), (6, y)} is a
relation from A to B.
Definition: Let S be any relation. The domain of the relation S is defined as the set of all first
elements of the ordered pairs that belong to S and is denoted by D(S).
D(S) = { x : (x, y) ∈ S, for some y }
The range of the relation S is defined as the set of all second elements of the ordered pairs that
belong to S and is denoted by R(S).
R(S) = { y : (x, y) ∈ S, for some x}
Example: A = {2, 3, 4} and B = {3, 4, 5, 6, 7}. Define a relation from A to B by (a, b) ∈ R if a
divides b.
Solution: We obtain R = {(2, 4), (2, 6), (3, 3), (3, 6), (4, 4)}.
Domain of R = {2, 3, 4} and range of R = {3, 4, 6}.
Properties of Binary Relations in a Set
A relation R on a set X is said to be
Reflexive relation if xRx or (x, x) ∈ R, ∀x ∈ X
Symmetric relation if xRy then yRx, ∀x, y ∈ X
Transitive relation if xRy and yRz then xRz, ∀x, y, z ∈ X
Irreflexive relation if x ̸Rx or (x, x) R, ∀x ∈ X
Antisymmetric relation if for every x and y in X, whenever xRy and yRx, then x = y.
Examples: (i). If R1 = {(1, 1), (1, 2), (2, 2), (2, 3), (3, 3)} be a relation on A = {1, 2, 3}, then R1 is
a reflexive relation, since for every x ∈ A, (x, x) ∈ R1.
(ii). If R2 = {(1, 1), (1, 2), (2, 3), (3, 3)} be a relation on A = {1, 2, 3}, then R2 is not a reflexive
relation, since for every 2 ∈ A, (2, 2) R2.
(iii). If R3 = {(1, 1), (1, 2), (1, 3), (2, 2), (2, 1), (3, 1)} be a relation on A = {1, 2, 3}, then R3 is a
symmetric relation.
www.Jntufastupdates.com 3
46
, (iv). If R4 = {(1, 2), (2, 2), (2, 3)} on A = {1, 2, 3} is an antisymmetric.
Example: Given S = {1, 2, ..., 10} and a relation R on S, where R = {(x, y)| x + y = 10}.
What are the properties of the relation R?
Solution: Given that
S = {1, 2, ..., 10}
= {(x, y)| x + y = 10}
= {(1, 9), (9, 1), (2, 8), (8, 2), (3, 7), (7, 3), (4, 6), (6, 4), (5, 5)}.
(i). For any x ∈ S and (x, x) R. Here, 1 ∈ S but (1, 1) R.
⇒ the relation R is not reflexive. It is also not irreflexive, since (5, 5) ∈ R.
(ii). (1, 9) ∈ R ⇒ (9, 1) ∈ R
(2, 8) ∈ R ⇒ (8, 2) ∈ R…..
⇒ the relation is symmetric, but it is not antisymmetric. (iii). (1, 9) ∈ R and (9, 1) ∈ R
⇒ (1, 1) R
⇒ The relation R is not transitive. Hence, R is symmetric.
Relation Matrix and the Graph of a Relation
Relation Matrix: A relation R from a finite set X to a finite set Y can be repre-sented by a matrix
is called the relation matrix of R.
Let X = {x1, x2, ..., xm} and Y = {y1, y2, ..., yn} be finite sets containing m and n elements,
respectively, and R be the relation from A to B. Then R can be represented by an m × n matrix
MR = [rij ], which is defined as follows:
1, if (x i , y j ) R
r =
ij 0, if (x i , y j ) R
Example. Let A = {1, 2, 3, 4} and B = {b1, b2, b3}. Consider the relation R = {(1, b2), (1, b3), (3,
b2), (4, b1), (4, b3)}. Determine the matrix of the relation.
Solution: A = {1, 2, 3, 4}, B = {b1, b2, b3}.
Relation R = {(1, b2), (1, b3), (3, b2), (4, b1), (4, b3)}.
Matrix of the relation R is written as
0 1 1
0 0 0
That is MR =
0 1 0
1 0 1
www.Jntufastupdates.com 4
47
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller Sasikalyan. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $6.49. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
67474 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now