Mathematical Foundation of Computer Science

DHARM 4 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE l If X ⊆ Y and Y ⊆ Z then certainly, X ⊆ Z (transitive). l A set with no ele ...

DHARM DISCRETE THEORY, RELATIONS AND FUNCTIONS 5 i.e. X ∪ Y = {x/x ∈ X OR x ∈ Y} For example, l {a,, b, c} ∪ {1, 2} = {a, b, c, ...

DHARM 6 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Difference Given two sets X and Y, then difference of X and Y denoted by X – ...

DHARM DISCRETE THEORY, RELATIONS AND FUNCTIONS 7 (S2) Rule of Sums Let Xk {for k = 1 to n}, is a finite family of finite pair wi ...

DHARM 8 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE For example, l For the sets X = {x 1 , x 2 } and Y = {y 1 , y 2 } then X × Y ...

DHARM DISCRETE THEORY, RELATIONS AND FUNCTIONS 9 y 1 y 2 x 1 11 x 2 01 x 3 10 (a)(b) (Tabular representation of relation R) (Gra ...

DHARM 10 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Similarly the range set (range) of relation R denoted by R(R), contains all ...

DHARM DISCRETE THEORY, RELATIONS AND FUNCTIONS 11 xyz x 111 y 11— z 1—1 Fig. 1.4 Compatibility relation. Example 1.3. Let N = {1 ...

DHARM 12 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE 1.4.3 Pictorial Representation of Relations................................ ...

DHARM DISCRETE THEORY, RELATIONS AND FUNCTIONS 13 1.4.5 Ordering Relation (Partial Ordered Relation) A binary relation R is said ...

DHARM 14 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE arg(f) = x∈im∪.g()f fy−^1 (); s (symbol ∪. indicates that the sets involved ...

DHARM DISCRETE THEORY, RELATIONS AND FUNCTIONS 15 We find that at x = 0 ⇒ f(0) = 0 % 5 = 0; at x = 1 ⇒ f(1) = 1 % 5 = 1; at x = ...

DHARM 16 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Thus, | f : X → Y | = 27, when f is arbitrary. For surjective mapping img ...

DHARM DISCRETE THEORY, RELATIONS AND FUNCTIONS 17 = (x + 2) – 2; = x Therefore, f ◊ f–1 = {(x, x)/x ∈ R} is an identity or funct ...

DHARM 18 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE recurrence relation only applies for n larger than the base cases. To study ...

DHARM DISCRETE THEORY, RELATIONS AND FUNCTIONS 19 Induction Hypothesis For n greater then 0, assume that ii k k k i k ()/ ( )( ) ...

DHARM 20 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE ik ik i k *()*2122^1 1 =− + + = ∑ true for all k ≥ 1 such that k < n. In ...

DHARM DISCRETE THEORY, RELATIONS AND FUNCTIONS 21 1.2 Define the finite set and infinite set; countable set and uncountable set. ...

DHARM 22 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE 1.17 Which of the following graphs represents injective, surjective, and bi ...

DHARM DISCRETE THEORY, RELATIONS AND FUNCTIONS 23 1.26 Prove that the sum of cubes of the first n natural numbers is equal to Rn ...