DISCRETE MATHS.

Running head: DISCRETE MATHS
Discrete Maths
Name of the Student:
Name of the University:

1
DISCRETE MATHEMATICS
Table of Contents
Q1............................................................................................................2
Q2...............................................................................................................................................2
Q3...............................................................................................................................................2
Q4...............................................................................................................................................3
Q5...............................................................................................................................................3

2
DISCRETE MATHEMATICS
Q1
To Prove, for all sets A, B and C: A × ( B ∩C ) =( A × B) ∩( A × C)
A × ( B ∩C )= { ( x , y ) such that x ∈ A∧ y ∈ ( B ∩C ) }
∴ x ε A∧ yε B∧ yε C .
∴ xεA ∧ yεB∧xεA ∧ yεC
¿ ( x , y ) ε ( A × B)∧ ( x , y ) ε (B ×C)
∴ ( x , y ) ε ( A × B)∩( B ×C )
The reverse direction can be done similarly.
Q2.
f : Z × Z → Z where f ( ( x , y ) ) =3 x +5 y for all ( x , y ) ∈ Z × Z
a)
No, the function is not one-one as f (0,0) = 0 and f (-5,3)=0.
b)
A function is onto if there exists a pre image foe every element in Z.
If z ∈ Z , thenthe equation 3 x +5 y=z is a Diophantine equation which has a solution only iff
g.c.d of (3,5) divides z. But g.c.d of (3,5) is 1 and hence will always be a multiple of any z
from Z. Hence there is always a solution to the equation and the function is onto.
Q3.
S is the set of all finite ordered n tuples of nonnegative integers where the last coordinate is
not 0.
To find a bijection from S to Z+.
A bijection from S to Z+ can be given by taking each n tuple and mapping it to the product of
ordered primes raised to the power of the elements in the n tuple.
Say, if s1 is an element of S and s1= (a1,a2, a3,...) then the map from S to Z will take s1 to
2a1
.3a2
. 5a3
... . .
Which is one one and onto.