Discrete Mathematical Structure and Graph Theory - B.Tech 4th Semester Exam., 2019

The statement \( p \rightarrow q \) is logically equivalent to

1. \( p \vee q \)
2. \( p \vee \sim q \)
3. \( \sim p \vee q \)
4. \( p \rightarrow q \)

The contrapositive of the conditional statement \( p \rightarrow q \) is

1. \( q \rightarrow p \)
2. \( \sim p \rightarrow \sim q \)
3. \( p \leftrightarrow q \)
4. \( \sim q \rightarrow \sim p \)

If A and B are two nonempty sets having n elements in common, then \( A \times B \) and \( B \times A \) will have how many elements in common?

1. \( 2^n \)
2. \( n^2 \)
3. \( n^4 \)
4. \( 2n \)

If a set A have n elements, then how many relations will be there on set A?

1. \( n^2 \)
2. \( 2^{n^2} \)
3. \( 2^n \)
4. \( 2n \)

If \( P(\phi) \) represents the power set of \( \phi \), then \( n(P(P(P(\phi)))) \) equal to

1. 1
2. 2
3. 3
4. 4

The number of edges in a bipartite graph with n vertices is at most

1. \( \frac{n^2}{2} \)
2. \( \frac{n^2}{4} \)
3. \( n^2 \)
4. \( 2n \)

If \( (S, *) \) is a monoid, where \( S = \{1, 2, 3, 6\} \) is defined by \( a * b = \text{lcm}(a, b) \), and where \( a, b \in S \), then the identity element is

1. 1
2. 2
3. 3
4. 6

The total number of subgroups of a group G of prime order is

1. 1
2. 2
3. 3
4. 4

For the poset \( \{3, 5, 9, 15, 24, 45\} \); divisor of the glb of \( \{3, 5\} \) is

1. 3
2. 5
3. 15
4. 45

The number of pendant vertices of a full-binary tree is

1. \( \frac{n+1}{2} \)
2. \( \frac{n-1}{2} \)
3. \( \frac{2n+1}{2} \)
4. \( \frac{2n-1}{2} \)

Using truth table, show that-
(i) \( ((p \rightarrow (q \rightarrow r))) \rightarrow ((p \rightarrow q) \rightarrow (p \rightarrow r)) \) is a tautology.
(ii) \( \sim(q \rightarrow r) \wedge r \wedge (p \rightarrow q) \) is a contradiction.

Obtain the principal disjunctive normal form (PDNF) and principal conjunctive normal form (PCNF) of the statement \( (p \rightarrow (q \wedge r)) \wedge (\sim p \rightarrow (\sim q \wedge \sim r)) \).

For any sets A and B, prove that
(i) \( (A \cup B)' = A' \cap B' \);
(ii) \( (A \cap B)' = A' \cup B' \).

If two sets A and B have n elements in common, then show that the sets \( A \times B \) and \( B \times A \) will have \( 2^n \) elements in common.

If R is the relation on the set of positive integers, such that \( (a, b) \in R \) if and only if \( a^2 + b \) is even, prove that R is an equivalence relation.

Define partition of a set. If the relation R on the set of integers Z is defined by \( a R b \) iff \( a \cong b \pmod 4 \), find the partition induced by R.

If R and S be relations on \( A = \{1, 2, 3\} \) represented by the matrices \( M_R = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix} \) and \( M_S = \begin{bmatrix} 0 & 1 & 1 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \).
Find the matrices that represent (i) \( R \cup S \), (ii) \( R \cap S \), (iii) \( R \circ S \), (iv) \( R - S \), (v) \( R' \), (vi) \( R \circ R \) and (vii) \( R \oplus S \).

Draw the Hasse diagram representing the partial ordering \( \{(A,B) : A \subseteq B\} \) on the power set \( P(S) \) where \( S = \{a,b,c\} \). Find the maximal, minimal, greatest and least elements of the poset.

Define characteristic function of a set. If A and B are any two subsets of universal set U, then show that:
\( f_{A \cup B}(x) = f_A(x) + f_B(x) - f_{A \cap B}(x) \), for all \( x \in U \)

If functions \( f, g, h: Z \rightarrow Z \) are defined as \( f(x) = x-1 \), \( g(x) = 3x \) and \( h(x) = \begin{cases} 0, & \text{if x is even} \\ 1, & \text{if x is odd} \end{cases} \)
Verify that \( f \circ (g \circ h) = (f \circ g) \circ h \).

Show that every group of order 3 is cyclic.

Prove that the necessary and sufficient condition for a non-empty set H of a group (G, *) to be a subgroup is \( a, b \in H \Rightarrow a * b^{-1} \in H \).

Show that the order of a subgroup of a finite group is a divisor of the order of the group.

Prove that the set S of all real numbers of the form \( a + b\sqrt{2} \) where a, b are integers is an integral domain with respect to usual addition and multiplication.

Define adjacency matrix and incidence matrix of graph G. Draw the graph represented by the adjacency matrix
\( \begin{bmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix} \)

Show that a tree with n vertices has \( (n-1) \) edges.