Discrete Mathematics

The area of mathematics known as discrete mathematics is concerned with mathematical objects that can only take into account distinct, isolated values.

Introduction to Set Theory 

A collection of unique things belonging to the same type or class of objects is referred to as a set. The elements or members of a set are its objectives. Numbers, alphabets, names, and other symbols can all be objects.

Several sets are examples:     A set of vowels.              A set of books.

The fundamentals of a set are denoted by the small letters a, b, x, y, etc. while a set is generally denoted by the capital letters A, B, C, etc.

If A is a set, and a is one of the elements of A, then we denote it as a ∈ A. Here the symbol ∈ means -"Element of."

Set Formation

The set can be formed in two ways:

i) Tabular form:

In this kind of representation, we list all of the items of the set within braces and separate them with commas. Example: A set of even numbers can be expressed as A={2,4,6,8}.

ii) Builder form

In this kind of representation, we enumerate the attributes that all of the set's items satisfy.

P = {x : x ∈ N, x is a multiple of 5}

R = {x : x>1 and x<50 and x is even}

Standard Notations:

x ∈ A	x belongs to A or x is an element of set A.
x ∉ A	x does not belong to set A.
∅	Empty Set.
U	Universal Set.
N	The set of all natural numbers.
I	The set of all integers.
I0	The set of all non- zero integers.
I+	The set of all + ve integers.
C, C0	The set of all complex, non-zero complex numbers respectively.
Q, Q0, Q+	The sets of rational, non- zero rational, +ve rational numbers respectively.
R, R0, R+	The set of real, non-zero real, +ve real number respectively.

Types of Sets

Finite Set

A set of specific number of different elements is called as finite set.

P = {x : x ∈ N, 3 < x < 10 }

B = {1, 3, 5, 7}

Infinite Set

Infinite Sets are non-finite sets.

Example:

       A = {Set of all integers}

       B = {x: x ∈ N, x is multiple of 5}

Subset

A set is said to be a subset of another if every element in it is also an element of the other set, B. It can be denoted as A ⊆ B. Here B is called Superset of A.

Example: If A= {11, 22} and B= {44, 22, 11} the A is the subset of B or A ⊆ B.

Properties of Subsets:

1. Every set is a subset of itself.
2. The Null Set i.e.∅ is a subset of every set.
3. If A is a subset of B and B is a subset of C, then A will be the subset of C. If A⊂B and B⊂ C ⟹ A ⊂ C
4. A finite set having n elements has 2ⁿ  subsets.

    (i) Proper Subset:

         If set A is subset of set B and A ≠ B then set A is a proper subset of set B. If set A is a proper subset of set B then B is not subset of A which means that there should be at least one element which is not in set A. 

    Example: 

           A = {2,4,6}

           B = {2,4,6,8}      then set A is a proper subset of set B.

 

    (ii) Improper subset:

                If set A is subset of set B and A = B then set A is an improper subset of set B.

           Example: 

                 A = {2,4,6}

                 B = {2,4,6}      then set A is improper subset of set B.

            In short, every set is improper subset of itself.

 Universal Set:

    A set that contains elements from every related set, without any element repetition, is known as a universal set (often symbolized by U). 

    Operations on Sets

    

            Basic operations on sets are as follows:

               1) Union of Sets:  Union of two sets is a set which contains all the elements from both the sets.  A ∪ B = {x : x ∈ A or x ∈ B} 

                              A = {1,2,3}            B = {5,6,7}  

                    Then A ∪ B = { 1,2,3,5,6,7}

                2) Intersection of Sets: Intersection of two sets is a set containing common elements from both the sets.  A ∩ B = { x : x ∈ A and x ∈ B}

                        A = { 1,2,3,4}      B = { 10, 2, 3, 34} then   A ∩ B = { 2, 3}

                  3) Difference of sets: A set of elements which belongs to set A and not to set B is the difference of sets A and B. It is denoted as A - B.     A - B = {x : x ∈ A and x ∉ B}

                       A= {1,2,3,4,5}      B={5, 6,7,8}

                       A - B = { 1,2,3,4}

                4) Symmetric difference of sets:  A set of elements containing all the elements that are in set A or in set B but not in both. It is denoted as A ⨁ B =(A ∪ B) - (A ∩ B) 

Algebra of Sets:

1)                      Idempotent Laws:

(i)                 A  ∪   A = A

(ii)               A  ∩  A = A

1)                       Associative Laws:

(i)                 (A ∪ B) ∪ C =A ∪  (B ∪  C)

(ii)         (A ∩ B) ∩ C = A ∩ (B ∩ C)

Commutative Laws:

(i)  A ∪ B = B ∪ A

(ii)  A ∩ B = B ∩ A

Distributive Laws:

(i) A ∪(B ∩  C) = (A ∪ B) ∩ (A ∪ C)

(ii) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

De Morgan's Laws:

(i) (A ∪ B) ^c= A^c∩ B^c

            (ii) (A ∩ B)^c= A^c ∪  B^c

             Identity Laws:

            (i)   A ∪ ∅ = A

            (ii)  A ∩ U = A

            (iii) A ∪ U = U

            (iv) A ∩ ∅ = ∅

            Complement Laws:

            (i)  A ∪ A^c = U

            (ii) A ∪ A^c = ∅

            (iii) U^c = ∅

            (iv)  ∅^c = U

            Involution Law:

            (i)  (A^c )^c = A