Discrete Mathematical Structures - Sets and Subsets

Sets and Subsets :

Sets and Subsets
Download Notes for :  

The Notes include :

Set: A set is a collection of well-defined objects (elements/members). The elements of the set are said to belong to (or be contained in) the set.
A set may be itself be an element of some other set.
A set can be a set of sets of sets and so on.
Sets will be denoted be capital letters A, B, C, ...
Elements will be denoted by lower case letters a, b, c, ....  x, y, z.

There are five ways to describe a set.
1. Describe a set by describing the properties of the members of the set.
2. Describe a set by listing its elements.
3. Describe a set by its characteristic functions
4. Describe a set by a recursive formula.
5. Describe a set by an operation (such as union, intersection, complement etc.,) on some other

Venn diagrams: Venn diagrams are used to visualise various properties of the set operations.
The Universal Set is represented by a large rectangular area.

Distributive and DeMorgan’s Laws can be established from Venn diagrams.

Distributive laws
AÈ(BÇC) = (AÈB) Ç (AÈC) 

 1.         Let A = {1, 2, 3, 4, 5}. Which of the following sets are equal to A?
a.             {4, 1, 2, 3, 5}
b.            {2, 3, 4}
c.             {1, 2, 3, 4, 5, 6}
d.            {x | x is an integer and x2 £ 25}
e.             {x | x is a positive integer and x £ 5}
f.             {x | x is a positive rational number and x £ 5}

A sequence is a list of objects arranged in a definite order; a first element, second element, third element, and so on. It is classified as finite sequence and infinite sequence. The elements may all be different, or some may be repeated.
1.      The sequence 1, 0, 0, 1, 0, 1, 0, 0, 1, 1 is a finite sequence with repeated items.
2.      The sequence 1, 3, 5, 7, 9, 11, 13, 15 is a finite sequence with different items.
3.      The sequence 3, 8, 13, 18, … is an infinite sequence.


Characteristic Functions
If A is a subset of a universal set U, the characteristic function fA of A is defined for each x Î U as:
            fA(x)    = 1, if x Î A
                        = 0, if x Ï A.



Given a set A, we can construct the set A* consisting of all finite sequences of elements of A. Often, the set A is not a set of numbers, but some set of symbols and Set A is called an alphabet, and the finite sequences in A* are called words or strings from A. The empty sequence or empty string contains no symbols and denoted as Ù.

Regular Expressions
A regular expression (over A) is a string constructed from the elements of A and the symbols (, ), Ú, *, Ù, according to the following definition.
RE1. The symbol Ù is a regular expression.
RE2. If x Î A, the symbol x is a regular expression.
RE3. If a and b are regular expressions, then the expression ab is regular.
RE4. If a and b are regular expressions, then the expression (aÚb) is regular.
RE5. If a is a regular expression, then the expression (a)* is regular.

1.      0*(0Ú1)*


A matrix is a rectangular array of numbers arranged in m horizontal rows and n vertical columns.
            a11          a12          …             a1n
            a21          a22          …             a2n
A =      .           .           .           .
            .           .           .           .
am1         am2         …             amn

A = [ aij ].


Boolean matrix
A Boolean matrix is an m x n matrix whose entries are either zero or one.

Boolean matrix operations
Let A and B be m x n Boolean matrices.



  1. can u please provide this notes for download .........

  2. I have updated the above download links...
    download those materials...

  3. u have updated the Q&A only cane u please update the notes


Post a Comment

Popular Posts