Discrete Mathematics Test 1

The characteristic equation of  \({a_n} = 8{a_n}_{ - 1} - 16{a_n}_{ - 2}\) is

\({r^2} - 8r + 16 = 0\)

\(\left( {r - 4} \right)\left( {r - 4} \right) = 0\)

\({a_n} = {\alpha _1}{\left( {{r_1}} \right)^n} + {\alpha _2}n{\left( {{r_1}} \right)^n}\)

\({a_n} = {\alpha _1}{\left( 4 \right)^n} + {\alpha _2}n{\left( 4 \right)^n}\)

[(p → r) ∧ (q → r)] → [(p ∨ q) → r]

≡ [(p̅ + r).(q̅ +r)] →[  \(\overline{p+q}\) + r]     .....p → r =p̅ + r        

≡ [(p̅.q̅ + p̅r + rq̅ + r] →[  p̅.q̅ + r] 

≡  [(p̅.q̅ + r(p̅ + q̅ + 1)] →[ p̅.q̅ + r] 

≡ [(p̅.q̅ + r] →[ p̅.q̅  + r] 

≡ True               (T → T = T or F → F = T)

The following propositional statement is tautology

Important Point:

For each combination of truth value of p,q,r given expression produce always true value therefore it is tautology. Hence option b is correct.

Concept:

One - one function: A function is one-one if the images of distinct elements of x under f are distinct. For every x₁ and x₂, f(x₁) = f(x₂) implies x₁ = x₂.

Onto function: if there are two sets X and Y. If for every element of B, there is atleast one or more than one element matching with A, then the function is said to be onto function.

Explanation:

Let x₁, x₂ belongs to Z and f(x₁) = f(x₂). Then with f(x₁) and f(x₂) there are two cases either both are even or both are odd.

To prove one-one

CASE 1: if both are even, then f(x₁) = f(x₂)

i.e. -4x₁ = -4x₂, x₁ = x₂

CASE 2: If both are odd, then 4x₁ – 1 = 4x₂ – 1

i.e. x₁ = x₂

So, f is one one function

To prove onto

Let n belongs to N

CASE 1: if n is even, then –n/4 belongs to Z and (-n/4) < 0

f(-n/4) = -4(-n/4) = n

CASE 2: if n is odd, then n+1/4 belongs to Z and (n+1)/4 >0

F((n+1)/4) = 4 (n+1)/4 – 1 = n

So, f is onto.

• It is closed
• Multiplicative modulo is associative
• 1 is the identity element
• Inverse exists of every element

∴ it is a group

∴ it is a also a monoid

3 ⊗ 8 x = 1 

∴ x = 3

3 is a inverse of 3  

But identity element of G is 1 not 3

Notes:

Question is asking which is false (not true) 

fog(x) = f(g(x)) = \(\frac{{3\frac{{x\; + \;2}}{{4x - 3}}{\rm{\;}} + {\rm{\;}}2}}{{4\frac{{x + \;2}}{{4x\; - 3}}{\rm{\;}}-{\rm{\;}}1}}\) = \(\frac{{11x}}{{11}}\) = x

Concept:

By using handshaking theorem of graph theory, the sum of degree of all the vertices in a tree is equal to twice the number of edges in a graph.

Formula:

\(\mathop \sum \limits_{i = 1}^{i = n} {d_i} = 2 \times e\)

where d_i is the degree of vertex i and e is the total number of edges in a graph

Calculation:

For a tree,

number of edges = e = n – 1

\(\mathop \sum \limits_{i = 1}^{i = n} {d_i} = 2 \times \left( {n - 1} \right) = 2 \times \left( {17 - 1} \right) = 32\)

sum of the degrees of all the vertices in T is 32.

Let p and q be two prepositional statement

If p then q ≡ p → q

Contrapositive of p → q is ~q → ~p

Let p: you’re GATE score is 80 in CS.

q: you’ll get a single digit rank.

If you’re GATE score is 80 in CS, then you’ll get a single digit rank ≡ p → q

Contrapositive of above statement

If you do not get a single digit rank then you’re GATE score is not 80 in CS ≡ ~q → ~p

Important Points:

If: p → q

then:

Contrapositive: ~q → ~p

Converse: q → p

Inverse: ~p → ~q

Data:

D_min = 4, F = 12

In a planar graph,

D_min × F ≤ 2E

4 × F ≤ 2E

4 × 12 ≤ 2E

E ≥ 24 (1)

E_min = 24

∴ x = 24

Euler’s Formula:

V – E + F = 2

E = V + F – 2

Substitute the value of E in equation 1

V + F – 2 ≥ 24

V + 12 – 2 ≥ 24

V ≥ 14

V_min = 14

∴ y = 14

Data:

degree = d

vertices = n

Formula:

By handshaking Lemma:

\(\mathop \sum \limits_{{\text{i}} = 1}^{{\text{i}} = {\text{n}}} {{\text{d}}_{\text{i}}} = 2 \times {\text{e}}\)

Calculation:

For a regular graph,

n × d = 2 × e

|A| = n

Total number relation: \({2^n}^2 = {2^{16}} = 64K\)

Total number reflexive relation R1 on set of n elements: \({2^{{n^2} - n}} = {2^{12}} = 4K\)

Total number irreflexive relation R2 on set of n elements: \({2^{{n^2} - n}} = {2^{12}} = 4K\)

Since intersection between R1 and R2 = 0

Option 1: CORRECT

A graph is bipartite if and only if it is two colorable.

Option 2: CORRECT

A cycle graph with even vertices is bipartite.

Option 3: CORRECT

A graph is bipartite if and only if it does not contain odd cycle.

Option 4: CORRECT

A tree is a bipartite graph.

n(A) = 3

n(B) = 25

From A to B

Total number of function possible = n(B)^n(A) = 25³

Total number of one-to-one function possible = 25P3  = 25 × 24 × 23

the probability of g being one-to-one =  \(\frac{25 \times 24 \times 23}{25^3} = 0.8832\)

In a Cayley table,

Last row: _ _ _ _

Since e is the identity element

s * e = s

Last row: _ _ s _

p * s = e

If s is the inverse of p then p is also the inverse of s

∴ s * p = e

Last row: e _ s _

Since each column and row is unique

∴ q * p = s

Also, q * s ≠ e ∴ q * s = p

∴ q * q = e

Which leads to s * q = p and s * s = q

Last row: e p s q

Cayley Table:

Data:

Vertices = v = 7

length of cycle = c = 4

Formula:

\({\rm{number\;of\;cycles}} = {{\rm{\;}}^{\rm{v}}}{{\rm{C}}_{\rm{c}}}{\rm{\;}} \times (c -1)!/2\)

Calculation:

\({\rm{number\;of\;cycles}} = {{\rm{\;}}^7}{{\rm{C}}_4}\times(4-1)!/2 =105\)

Formula:

X → Y ≡ ~X ∨ Y ≡ X’ + Y

AND ≡ ∧ ≡ .

OR ≡ ∨ ≡ +

Calculation:

Option 1: TRUE

A → B ≡ ~A ∨ B

Option 2: TRUE

~(A ∧ ~B) ≡ ~A ∨ B ≡ A → B

Option 3: TRUE

~A ∨ (~A ∧ B) ∨ (~A ∧ ~B) ∨ B

≡ A’ + (A’.B) + (A’.B’ ) + B

≡ A’(1 + B + B’) + B ≡ A’ + B

≡ ~A ∨ B ≡ A → B

Option 4: TRUE

~B → ~A ≡ ~(~B) ∨ ~A

≡ B ∨ ~A ≡ A → B

a_n - 2a_n-1 - 4a_n-2 = 0

a_n = 2a_n-1 + 4a_n-2 (given)

a₀ = 2, a₁ = 5

a₂ = 2(5) + 4(2) = 18, a₃ = 2(18) + 4(5) = 56

a₄ = 2(56) + 4(18) = 184

∴ sequence: 2, 5, 18, 56, 184

G(x) = 2 + 5x + 18x² + 56x³ + 184x⁴ …

2xG(x) = 4x + 10x² + 36x³ + 112x⁴ …

4x²G(x) = 8 x² + 20x³ + 72x⁴ …

G(x)(1 – 2x – 4x²) = 2 + x

\(G\left( x \right) = \frac{{2\; + \;x}}{{\left( {1 - 2x - 4{x^2}} \right)}}\)

Every permutation of n numbers differs by at least 1 swap of adjacent pairs, hence each node will be connected, hence graph will have one connected component.

Also degree of each node will be 99.

Hence 99 + 10*1 = 109.

Option 1:  False 

Because there can be some pair which is present in a relation R whose symmetric pair is not present in its superset.

Option 2:  True

Because Ɐi (i ≤ i).

Option 3:  False 

Because the smallest relation which is irreflexive contains 0 element. A null set is the smallest relation which is irreflexive

Option 4:  True

Because R1ꓴR2 will contain each element (i, i) which is present in R1 and R2.

Therefore, both option 1 and option 3 are false.