Discrete Structure

Find the number between 1 to 500 that are not divisible by any of the integers 2 or 3 or 7.

Prove that 5^2n-1 is divisible by 24, where is any positive integer.

What is mapping ? Explain types of mapping.

Define relation with example. Explain various types of representation of relation.

Prove that G = \{0, 1, 2, 3, 4, 5, 6} is an abelian group of order 7 with respect to addition modulo 7.

What is a Ring? Define elementary properties of ring with example.

Construct truth table of the following and prove:
(p→p∧r) → (~r → p) is a tautology

(p∧q) ∧(~p) ∧(~q) is a contradiction.

Define and explain any four of the following with suitable example.

1. Bipartite graph
2. Hamiltonian path and circuit
3. Chromatic number and graph coloring of graph
4. Adjacency matrix of graph
5. Binary search tree

Prove that F={a + b √2 | a, b rational} is a field.

Prove or disprove that intersection of two normal subgroups of a group G is again a normal subgroup of G. Define subgroup, normal subgroup, Quotient group, with an example for each.

Explain the following

1. Euler Graph
2. Isomorphic Graphs
3. Minimal spanning tree
4. Height of the tree

Define planner Graph. Prove that for any connected planner graph, v-e+r=2 where v,e,r is the number of vertices, edges, and region of the graph respectively.

Solve the following recurrence relation :

a_r – 7a_r-1 + 10a_r-2 = 3^r Given that a₀=0, a₁=1.

Solve the following recurrence relation using generating function
G(K)-7G(K-1)+10G(K-2)=8K+6

Discuss in brief any two of the following:

1. Partial ordering relation
2. Poset
3. Disjunctive normal form
4. Pigeonhole principle

Define the lattice. Let (L,≤,∨,∧) be a lattice and a,b,c,d∈L such that a≤b and c≤d. Show that a∨c≤b∨d and a∧c≤b∧d.