The statement $ p \rightarrow q $ is logically equivalent to

The contrapositive of the conditional statement $ p \rightarrow q $ is

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?

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

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

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

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

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

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

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

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.

The statement $ p \rightarrow q $ is logically equivalent to

The contrapositive of the conditional statement $ p \rightarrow q $ is

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?

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

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

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

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

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

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

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

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.

For any three sets A, B and C, which of the following statements is wrong?

Let A and B be two non-empty sets. Then the set of all ordered pairs (a, b), where $ a \in A $ and $ b \in B $ is called

If $ (a,a) \in R $ or equivalently $ a R a $, $ \forall a \in A $, then a relation R on a set A is called

Let A and B be finite sets with $ |A| = n $ and $ |B| = m $. How many functions are possible from A to B with A as the domain?

For the functions f and g defined by $ f(x) = x^3 $ and $ g(x) = x^2 + 1 \; \forall x \in R $, the value of $ (g \circ f)(x) $ is

A group G is said to be Abelian (or commutative) if for every

If $ f : G \rightarrow G' $ is a homomorphism, then which of the following it true?

For which of the following does there exist a tree satisfying the specified constraints?

For which of the following does there exist a graph $ G(V, E) $ satisfying the specified conditions?

The number of simple digraphs with $ |V| = 3 $ is

Let $ f(x) = ax^2 + b $ and $ g(x) = cx^2 + d $, where a, b, c and d are constants. Determine for which constants a, b, c and d the following equation holds: $ f \circ g = g \circ f $

Show that the relation $ (x, y) R (a, b) $ such that $ x^2 + y^2 = a^2 + b^2 $ is an equivalence relation on the plane and describe the equivalence classes.

Let $ (G, \cdot) $ be a group, where $ \cdot $ is usual multiplication operation on G. Then show that for any $ x, y \in G $ following equations hold:
(i) $ (x^{-1})^{-1} = x $
(ii) $ (xy)^{-1} = y^{-1}x^{-1} $

Construct the truth table for $ [(p \vee q) \wedge (p \rightarrow r) \wedge (q \rightarrow r)] \rightarrow r $. Also show that above statement is a tautology by developing a series of logical equivalences.

If $ A = \{1, 2, 4\} $, $ B = \{2, 5, 7\} $ and $ C = \{1, 3, 7\} $, find $ (A \times B) \cup (A \times C) $.

List the ordered pairs in the relation R from $ A = \{1, 2, 3, 4\} $ to $ B = \{2, 3, 4, 5\} $, where $ (a, b) \in R $ if and only if-
(i) $ a = b $
(ii) $ a + b = 5 $

Show that the set of integers with the composition $ \circ $ and * defined by $ a \circ b = a + b + 1 $ and $ a * b = ab + a + b $ is a ring.

State and prove Lagrange's theorem.

Define a relation R on the set Z of all integers as follows: $ m R n \Leftrightarrow m+n $ is even for all $ m, n \in Z $. Is R a partial order relation? Prove or give a counter example.

Show that the group
(i) $ \{1, 2, 3, 4\}, X_5 $
(ii) $ \{1, 2, 3, 4, 5, 6\}, X_7 $
is cyclic.

Let $ A = \{0, 1, 2, 3\} $, $ R = \{(x, y) : x+y=3\} $, $ S = \{(x, y) : 3|(x+y)\} $, $ T = \{(x, y) : \max(x,y)=3\} $. Compute (i) $ R \circ T $, (ii) $ T \circ R $ and (iii) $ S \circ S $.

In a group of 70 cars tested by a garage in Delhi, 15 had faulty tyres, 20 had faulty breaks and 18 exceeded the allowable emission limits. Also, 5 cars had faulty tyres and brakes, 6 failed on tyres and emission, 10 failed on brakes and emissions, and 4 cars were unsatisfactory in all three respects. How many cars had no faults in these three checks? Draw an appropriate Venn diagram.

Define the vertex connectivity and edge connectivity of a graph. Prove that for a graph G with n vertices and e edges, vertex connectivity $ \le $ edge connectivity $ \le 2e/n $.

Define the adjacency matrix of a graph. Find the rank of the regular graph with n vertices and with degree $ p (< n) $ of every vertex.

For any three sets A, B and C, which of the following statements is wrong?

Let A and B be two non-empty sets. Then the set of all ordered pairs (a, b), where $ a \in A $ and $b \in B$ is called

If $(a,a) \in R$ or equivalently $a R a$, $\forall a \in A$, then a relation R on a set A is called

Let A and B be finite sets with $|A| = n$ and $|B| = m$. How many functions are possible from A to B with A as the domain?

For the functions f and g defined by $f(x) = x^3$ and $ g(x) = x^2 + 1 ; \forall x \in R $, the value of$ (g \circ f)(x) $ is

A group G is said to be Abelian (or commutative) if for every

If $f : G \rightarrow G'$ is a homomorphism, then which of the following it true?

For which of the following does there exist a tree satisfying the specified constraints?

For which of the following does there exist a graph $G(V, E)$ satisfying the specified conditions?

The number of simple digraphs with $|V| = 3$ is

Let $f(x) = ax^2 + b$ and $g(x) = cx^2 + d$, where a, b, c and d are constants. Determine for which constants a, b, c and d the following equation holds: $f \circ g = g \circ f$

Show that the relation $(x, y) R (a, b)$ such that $x^2 + y^2 = a^2 + b^2$ is an equivalence relation on the plane and describe the equivalence classes.

Let $(G, \cdot)$ be a group, where $\cdot$ is usual multiplication operation on G. Then show that for any $x, y \in G$ following equations hold:
(i) $ (x^{-1})^{-1} = x $
(ii) $(xy)^{-1} = y^{-1}x^{-1}$

Construct the truth table for $ [(p \vee q) \wedge (p \rightarrow r) \wedge (q \rightarrow r)] \rightarrow r $. Also show that above statement is a tautology by developing a series of logical equivalences.

If $A = \{1, 2, 4\}$, $B = \{2, 5, 7\}$ and $C = \{1, 3, 7\}$, find $ (A \times B) \cup (A \times C) $.

List the ordered pairs in the relation R from $A = \{1, 2, 3, 4\}$ to $ B = {2, 3, 4, 5} $, where$ (a, b) \in R $ if and only if-
(i) $ a = b $
(ii) $a + b = 5$

Show that the set of integers with the composition $\circ$ and * defined by $ a \circ b = a + b + 1 $and$ a * b = ab + a + b $ is a ring.

State and prove Lagrange's theorem.

Define a relation R on the set Z of all integers as follows: $m R n \Leftrightarrow m+n$ is even for all $m, n \in Z$. Is R a partial order relation? Prove or give a counter example.

Show that the group
(i) $ {1, 2, 3, 4}, X_5 $
(ii) $ {1, 2, 3, 4, 5, 6}, X_7 $
is cyclic.

Let $A = \{0, 1, 2, 3\}$, $R = \{(x, y) : x+y=3\}$, $ S = {(x, y) : 3|(x+y)} $,$ T = {(x, y) : \max(x,y)=3} $. Compute (i)$ R \circ T $, (ii)$ T \circ R $and (iii)$ S \circ S $.

In a group of 70 cars tested by a garage in Delhi, 15 had faulty tyres, 20 had faulty breaks and 18 exceeded the allowable emission limits. Also, 5 cars had faulty tyres and brakes, 6 failed on tyres and emission, 10 failed on brakes and emissions, and 4 cars were unsatisfactory in all three respects. How many cars had no faults in these three checks? Draw an appropriate Venn diagram.

Define the vertex connectivity and edge connectivity of a graph. Prove that for a graph G with n vertices and e edges, vertex connectivity $\le$ edge connectivity $\le 2e/n$.

Define the adjacency matrix of a graph. Find the rank of the regular graph with n vertices and with degree p (&lt; n) of every vertex.

• Multigraphs
• Planar graphs
• Cosets
• Ring polynomials

The set of all real numbers under the usual multiplication operation is not a group since

If $ R = \{(1, 2), (2, 3), (3, 3)\} $ be a relation defined on $ A = \{1, 2, 3\} $, then $ R \circ R $ is

Pick out the correct statement(s):

Let f and g be the functions defined by $ f(x) = 2x+3 $ and $ g(x) = 3x+2 $. Then the composition of f and g is

Among 200 people, 150 either swim or jog or both. If 85 swim and 60 swim and jog, then how many people jog?

If a graph is a tree, then

The relation R on the set of all integers, where $ (x, y) \in R $ if and only if $ xy \ge 1 $ is

How many functions are there from a set with three elements to a set with two elements?

Which one of the following is correct for any simple connected undirected graph with more than 2 vertices?

In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity, by

Define set. Let X be the universal set and $ S \subset X $, $ T \subset X $. Then prove that:
(a) $ (S \cup T)^c = S^c \cap T^c $
(b) $ (S \cap T)^c = S^c \cup T^c $

Define relations and function. What is equivalence relation?

Let A be the set of all people in India. If $ x, y \in A $, then let us say that $ (x,y) \in R $ if x and y have the same surname (i.e., last name). Then prove that R is an equivalence relation.

Define group, Abelian group and groupoid. Also define composition of functions. Let $ f: R \rightarrow \{x \in R: x \ge 0\} $ be given by $ f(x) = x^4 + x^2 + 6 $ and $ g: \{x \in R: x \ge 0\} \rightarrow R $ be given by $ g(x) = \sqrt{x} - 4 $. Then find $ (g \circ f)(x) $ and $ (f \circ g)(x) $.

Suppose H and K are normal subgroups of G with $ H \cap K = \{1\} $. Show that $ xy = yx $ for all $ x \in H $ and $ y \in K $. Let $ I \in R $ be an ideal.

The radical $ \sqrt{I} = \{r \in R | rn \in I, n \in N\} $. Show that $ \sqrt{I} $ is an ideal.

Define commutative ring. Consider the set X, its power set $ P(X) = \{A | A \subset X\} $ is the set of all subsets of X. Show that the power set is a commutative ring under the following two operations $ A + B = (A - B) \cup (B - A) $ where $ \cup $ is set union and $ - $ is set difference, and $ AB = A \cap B $.

Prove that (a) the maximum number of nodes N on level i of a binary tree is $ 2^i $, $ i \ge 0 $ and (b) the maximum number of nodes in a binary tree of height h is $ 2^h - 1 $, $ h \ge 1 $.

Define Walks, Paths and Circuits related to a graph. Write down all possible (a) paths from $ v_1 $ to $ v_8 $, (b) circuits of G and (c) trails of length three in G from $ v_3 $ to $ v_5 $ of the graph shown in the figure below.

Show that if a and b are the only two odd degree vertices of a graph G, then a and b are connected in G. Prove that a connected graph G remains connected after removing an edge e from G if and only if e lie in some circuit in G.

The set of all real numbers under the usual multiplication operation is not a group since

If $ R = \{(1, 2), (2, 3), (3, 3)\} $ be a relation defined on $ A = \{1, 2, 3\} $, then $ R \circ R $ is

Pick out the correct statement(s):

Let f and g be the functions defined by $ f(x) = 2x+3 $ and $ g(x) = 3x+2 $. Then the composition of f and g is

Among 200 people, 150 either swim or jog or both. If 85 swim and 60 swim and jog, then how many people jog?

If a graph is a tree, then

The relation R on the set of all integers, where $ (x, y) \in R $ if and only if $ xy \ge 1 $ is

How many functions are there from a set with three elements to a set with two elements?

Which one of the following is correct for any simple connected undirected graph with more than 2 vertices?

In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity, by

Define set. Let X be the universal set and $ S \subset X $, $ T \subset X $. Then prove that:
(a) $ (S \cup T)^c = S^c \cap T^c $
(b) $ (S \cap T)^c = S^c \cup T^c $

Define relations and function. What is equivalence relation?

Let A be the set of all people in India. If $ x, y \in A $, then let us say that $ (x,y) \in R $ if x and y have the same surname (i.e., last name). Then prove that R is an equivalence relation.

Define group, Abelian group and groupoid. Also define composition of functions. Let $ f: R \rightarrow \{x \in R: x \ge 0\} $ be given by $ f(x) = x^4 + x^2 + 6 $ and $ g: \{x \in R: x \ge 0\} \rightarrow R $ be given by $ g(x) = \sqrt{x} - 4 $. Then find $ (g \circ f)(x) $ and $ (f \circ g)(x) $.

Suppose H and K are normal subgroups of G with $ H \cap K = \{1\} $. Show that $ xy = yx $ for all $ x \in H $ and $ y \in K $. Let $ I \in R $ be an ideal.

The radical $ \sqrt{I} = \{r \in R | rn \in I, n \in N\} $. Show that $ \sqrt{I} $ is an ideal.

Define commutative ring. Consider the set X, its power set $ P(X) = \{A | A \subset X\} $ is the set of all subsets of X. Show that the power set is a commutative ring under the following two operations $ A + B = (A - B) \cup (B - A) $ where $ \cup $ is set union and $ - $ is set difference, and $ AB = A \cap B $.

Prove that (a) the maximum number of nodes N on level i of a binary tree is $ 2^i $, $ i \ge 0 $ and (b) the maximum number of nodes in a binary tree of height h is $ 2^h - 1 $, $ h \ge 1 $.

Define Walks, Paths and Circuits related to a graph. Write down all possible (a) paths from $ v_1 $ to $ v_8 $, (b) circuits of G and (c) trails of length three in G from $ v_3 $ to $ v_5 $ of the graph shown in the figure below.

Show that if a and b are the only two odd degree vertices of a graph G, then a and b are connected in G. Prove that a connected graph G remains connected after removing an edge e from G if and only if e lie in some circuit in G.

Answer the following:

Answer the following:

Answer the following:

Answer the following:

Answer the following:

Answer the following:

Answer the following:

Answer the following:

Answer the following: