Sets
and Subsets :
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 x2 £ 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.
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.
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.
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.
etc...
