Discrete Mathematics Test 2

\(\begin{array}{l}g\left( {h\left( x \right)} \right) = 1 - \frac{x}{{x - 1}} = \frac{{x - 1 - x}}{{x - 1}} = \frac{{ - 1}}{{x - 1}}\\h\left( {g\left( x \right)} \right) = \frac{{1 - x}}{{1 - x - 1}} = \frac{{1 - x}}{{ - x}} = \frac{{x - 1}}{x}\\\therefore \frac{{g\left( {h\left( x \right)} \right)}}{{h\left( {g\left( x \right)} \right)}} = \frac{{ - 1}}{{x - 1}} \times \frac{x}{{x - 1}} = \frac{{ - x}}{{{{\left( {x - 1} \right)}^2}}}\end{array}\) 

Also, \(\frac{{h\left( x \right)}}{{g\left( x \right)}} = \frac{{ - x}}{{{{\left( {x - 1} \right)}^2}}}\)

In an Anti-symmetric relation: symmetric pair, that is, (a, b) and (b, a) where a ≠ b should not be present,

S = {a, b, c, d}

S × S = {(a, a), (a, b), (a, c), (a, d),

(b, a), (b, b), (b, c), (b, d),

(c, a), (c, b), (c, c), (c, d),

(d, a), (d, b), (d, c), (d, d)}

R = {(a, a), (b, b), (c, c), (d, d), (a, b), (a, c), (a, d), (b, c), (b, d), (c, d)}

Since we cannot add any other relation

Maximum cardinality = |R| = 10

Tips and Tricks:

maximum cardinality = \(n + \frac{{{n^2} - n}}{2}\)

|S| = 4

maximum cardinality = \(4 + \frac{{{4^2} - 4}}{2} = 4 + \frac{{16\; - 4}}{2} = 10\)

Concepts:

In mathematics, the power set (or powerset) of any set S is the set of all subsets of S, including the empty set and S itself.

Explanation:

X = {a, {b}, {c}}

Power set of A = 2X = {Φ, {a}, {{b}}, {{c}}, {a, {b}}, {a, {c}}, {{b}, {c}}, {b, {c}, {c}}}

Elements: Φ, {a}, {{b}}, {{c}}, {a, {b}}, {a, {c}}, {{b}, {c}}, {b, {c}, {c}}

Option 1: INCORRECT

{a, {b}} is element of power set of A. Therefore, {{a, {b}}} ⊆ 2X.

{a, {b}} ⊄ 2As

Option 2: CORRECT

Φ is an element of the power set of A. Therefore, Φ ϵ 2X.

Option 3: CORRECT

{a, {c}} is element of power set of A. Therefore {a, {c}} ϵ 2X.

Option 4: CORRECT

Power set of A consists of all subsets of A and from the definition of a subset, ϕ is a subset of any set.

Therefore, Φ ⊆ 2X

Concept:

A relation R on a set A is said to be reflexive if xRx exists for all x belongs to set A.

The relation R on set A is called irreflexive if x is not related to x i.e. the ordered pair (x,x) does not belongs to the relation.

Explanation:

Consider A = {1,2,3, …….. n}

Then number of non-diagonal element in A × A = n² – n

So, Number of reflexive relations possible are = 2^n(n-1)

Number of irreflexive relations that are possible on A are also = 2^n(n-1)

Total number of relations possible on A = \({2^{{n^2}}}\)

Number of relations on A which are reflexive or irreflexive =

\({2^{n\left( {n - 1} \right)}} + {2^{n\left( {n - 1} \right)}} = 2 \times {2^{n\left( {n - 1} \right)}} = \;{2^{n\left( {n - 1} \right) + 1}}\)

Let Z = {1, 2, 3}

Z × Z = {(1,1), (1,2), (1,3), (2, 1), (2, 2), (2,3), (3, 1), (3, 2), (3, 3)}

R = {(1, 2), (1, 3), (2, 3)}

• In Relation R, (1, 1), (2, 2) and (3, 3) is not present therefore it is not reflexive.
• In Relation R, (1, 2) is present but (2, 1) is not present therefore it is not symmetric.
• In Relation R, (1, 1) OR (2, 2) OR (3, 3) is not present therefore it is irreflexive.
• Any symmetric pair like (1, 2) and (2, 1) is not present therefore it is Anti-symmetric

Injective means for every pre-image there should be a distinct image. Here f has distinct value for each input.

Surjective or onto means range should be equal to co-domain, that is all elements in co-domain should be covered, which is not the case for given function.

n(X) = 3

n(Y) = 8

Function from Y to X

Total number of function possible = n(X)^n(Y) = 3⁸ = 6561

Total number of onto function possible is

\({3^8}{ - ^3}{C_1}{\left( {3 - 1} \right)^8}{ + ^3}{C_2}{\left( {3 - 2} \right)^8} - {\;^3}{C_3}{\left( {3 - 3} \right)^8}\;\)

3⁸ – 3 × 2⁸ + 3 = 5796

the probability of g being one-to-one = \(\frac{{5796}}{{6561}} = 0.8834\;\)

Given: A = {a, b, c, d}

R = {(a, a) , (b, a), (b, b), (b, c), (b, d), (c, a), (c, b), (c, c), (c, d)}

Consider all the options one by one:

1. R is an equivalence relation

An equivalence relation is the one which is reflexive, symmetric and transitive. Given relation is not reflexive as (d,d) is not present. Also it is not symmetric as (a,b) is present but (b,a) is not there. So, it is not equivalence relation.

2. R is an irreflexive or anti symmetric relation

This relation is not irreflexive. As (a,a) (b,b) (c,c ) are present in this. Also, it is not anti-symmetric. Because (b,c) and (c,b) both are present.

3. R is symmetric or asymmetric relation

Given relation is not symmetric as (a,b) is present but (b,a) is not there. Also it is not asymmetric because (b,c) and (c,b) both are present.

4. R is transitive.

Formula:

Number of function possible for set of m element to a set of n element: n^m

Calculation:

Number of elements in set {a, b, c, d}¹⁶: 4¹⁶

Number of elements in set {1, 2}: 2

Number of elements in set P is set of all functions from a set of 4¹⁶ to 2 is \({2^{{4^{16}}}}\).

Number of elements from set P to {1, 2} = n = \({2^{{2^{{4^{16}}}}}}\)

\({\log _2}{\log _2}{\log _2}{2^{{2^{{4^{16}}}}}} = {\log _2}{\log _2}{2^{{4^{16}}}} = \;{\log _2}{4^{16}} = 16{\log _2}4 = 32\)