Discrete Mathematical Structures - Sets and Subsets

Sets and Subsets :

Download Notes for :  
Download1
Download2

The Notes include :

Definitions:

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

    sets.

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) 

Exercises:

 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 x² £ 25}

e.             {x | x is a positive integer and x £ 5}

f.             {x | x is a positive rational number and x £ 5}

etc...

Sequences

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.

Examples:

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.

etc...

Characteristic Functions

If A is a subset of a universal set U, the characteristic function f_A of A is defined for each x Î U as:

            f_A(x)    = 1, if x Î A

                        = 0, if x Ï A.

etc...

Strings

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 Ù.

Example:

etc...
 

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.

Examples:

1.      0*(0Ú1)*

etc...

Matrices

A matrix is a rectangular array of numbers arranged in m horizontal rows and n vertical columns.

            a₁₁          a_{12          …}             a_1n

            a₂₁          a_{22          …}             a_2n

A =      .           .           .           .

            .           .           .           .

a_m1         a_{m2         …}             a_mn

A = [ a_ij ].

etc...

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.

etc...