THEORY EXAMINATION (SEM–VIII) 2016-17 DISCRETE MATHEMATICS

SECTION – A

Attempt all parts (Short Answer Type)

A relation is a connection between elements of two sets, while a function is a special type of relation in which each element of the domain is mapped to exactly one element of the codomain.

An equivalence relation is a relation that satisfies three properties: reflexive, symmetric, and transitive.

The statement “Jack and Jill went up the hill” can be written symbolically using logical operators to represent both actions happening together.

Negation is a logical operation that reverses the truth value of a statement. If a statement is true, its negation becomes false, and vice versa.

Permutation of a set refers to arranging its elements in different possible orders. Taking two elements at a time from the set {1,2,3,4} involves selecting and arranging them.

When 10 people at a party are paired into groups of two, the number of ways can be calculated using combination and pairing formulas.

An abelian group is a group in which the operation is commutative, meaning the order of elements does not affect the result.

A cyclic group is a group that can be generated by repeatedly applying a group operation to a single element.

A Hamiltonian path is a path in a graph that visits every vertex exactly once.

The chromatic number of a graph is the minimum number of colors needed to color its vertices so that no two adjacent vertices share the same color.

Questions (Section A)

What is the difference between relation and function?

Define equivalence relation.

What is negation in logic?

Define cyclic group.

What is Hamiltonian path?

SECTION – B

Attempt any five (Long Answer Type)

An equivalence relation divides a set into equivalence classes where all elements are related to each other based on a given condition.

Logical implication shows the relationship between statements using logical operators such as AND, OR, and NOT.

Recurrence relations define sequences based on previous terms. They are solved using characteristic equations or iterative methods.

A field is an algebraic structure with two operations, addition and multiplication, that satisfy properties like closure, associativity, and distributivity.

In graph theory, the number of vertices with odd degree in a graph is always even. This is an important property used in network analysis.

A Hamiltonian circuit is a cycle that visits every vertex exactly once and returns to the starting point.

Subgroups are smaller groups within a larger group that satisfy group properties under the same operation.

Generating functions represent sequences using algebraic expressions and help solve combinatorial problems.

Questions (Section B)

What is an equivalence relation?

Explain recurrence relations.

What is a field in algebra?

Prove number of odd degree vertices is even.

What is Hamiltonian circuit?

SECTION – C

Attempt any two (Detailed Explanation)

Set identities such as distributive laws can be proven using Venn diagrams to show relationships between sets visually.

A partial order relation is a relation that is reflexive, antisymmetric, and transitive. It helps describe ordering among elements.

An algebraic system can form a group if it satisfies closure, associativity, identity, and inverse properties.

The intersection of two subgroups is always a subgroup because it contains common elements that satisfy group properties.

The Handshaking Lemma states that the sum of degrees of all vertices in a graph is equal to twice the number of edges.

The maximum number of edges in a simple graph with n vertices is given by the formula n(n−1)/2.

Questions (Section C)

What is partial order relation?

State and prove Handshaking Lemma.

What is maximum number of edges in a simple graph?