Discrete Mathematics and Graph Theory

The function $ f:R \rightarrow R $ defined by $ f(x)=x^3+5 $

Consider the following relation R on a set $ A=\{1,2,3,4\} $: R = {(1,1), (1, 3), (3, 2), (2, 2), (3, 3), (3, 1), (2, 3), (1, 4), (4, 4)} Then

Out of the following which of these integers is not prime?

The Greatest common divisor of 0 and 11

Suppose G is a group with a binary operation * defined by $ a*b=a+b+1 $, for $ a, b \in G $ then

The field which contains at least _____ element/elements

The set of integers with respect to addition is

The total number of edges in a complete graph of n vertices is

In any undirected graph, the sum of degrees of all vertices

$ (p \rightarrow q) \wedge (r \rightarrow q) $ is equivalent to

Given $ A=\{1,2,3\} $, $ B=\{7,8\} $ and $ R=\{(1,7), (2, 7), (1, 8), (3, 8)\} $, find $ R^{-1} $ (inverse of R) and $ R' $ complement of R.

Consider $ A=B=C=R $ set of real numbers and let $ f:A \rightarrow B $, $ g: B \rightarrow C $ defined by $ f(x)=x+9 $ and $ g(y)=y^2+3 $ find the following composition functions: $ (f \circ g)(a) $, $ (g \circ f)(a) $, $ (g \circ f)(x) $, $ (f \circ g)(-3) $.

What is the negation of each of the following propositions? (i) Today is Tuesday (ii) A cow is an animal (iii) No one wants to buy my house

Determine the truth value of each of the following statements (i) $ 4+3=7 $ and $ 6+2=8 $ (ii) $ 2+3=4 $ and $ 3+1=2 $

Show that the set of rational numbers Q forms an abelian group.

Define a ring, give an example of a commutative ring without zero divisors and a non-commutative ring with identity.

Describe the Fundamental Theorem of Arithmetic. Factorize the number '324' and represent it as a product of primes.

Use the Euclidean algorithm to find the greatest common divisor of each pair of integers, (i) 60, 90 (ii) 414, 662

Describe a graph model that can be used to represent all forms of electronic communication between two people in a single graph. What kind of graph is needed?

Explain the complete graph and prove that $ k_5 $ (complete graph) is a nonplanar graph.

Explain the congruence relation. Let $ n $ be a positive integer then: (i) If $ a \equiv b \pmod{n} $, then $ b \equiv a \pmod{n} $ (ii) If $ a \equiv b \pmod{n} $ and $ b \equiv c \pmod{n} $, then $ a \equiv c \pmod{n} $.

Show that $ p \Leftrightarrow q \equiv (p \Rightarrow q) \wedge (q \Rightarrow p) $

Write short notes of the following: (i) Eulerian Graph (ii) Graph Coloring

Write short notes of the following: (i) Chromatic number (ii) Perfect Graph

What is the field? Show that $ (Q, +, \times) $ is a field.

If in a ring R with $ (xy)^2=x^2y^2 $ for all $ x, y \in R $, then R is commutative.

The function $ f:R \rightarrow R $ defined by $ f(x)=x^3+5 $

Consider the following relation R on a set $ A=\{1,2,3,4\} $: R = {(1,1), (1, 3), (3, 2), (2, 2), (3, 3), (3, 1), (2, 3), (1, 4), (4, 4)} Then

Out of the following which of these integers is not prime?

The Greatest common divisor of 0 and 11

Suppose G is a group with a binary operation * defined by $ a*b=a+b+1 $, for $ a, b \in G $ then

The field which contains at least _____ element/elements

The set of integers with respect to addition is

The total number of edges in a complete graph of n vertices is

In any undirected graph, the sum of degrees of all vertices

$ (p \rightarrow q) \wedge (r \rightarrow q) $ is equivalent to

Given $ A=\{1,2,3\} $, $ B=\{7,8\} $ and $ R=\{(1,7), (2, 7), (1, 8), (3, 8)\} $, find $ R^{-1} $ (inverse of R) and $ R' $ complement of R.

Consider $ A=B=C=R $ set of real numbers and let $ f:A \rightarrow B $, $ g: B \rightarrow C $ defined by $ f(x)=x+9 $ and $ g(y)=y^2+3 $ find the following composition functions: $ (f \circ g)(a) $, $ (g \circ f)(a) $, $ (g \circ f)(x) $, $ (f \circ g)(-3) $.

What is the negation of each of the following propositions? (i) Today is Tuesday (ii) A cow is an animal (iii) No one wants to buy my house

Determine the truth value of each of the following statements (i) $ 4+3=7 $ and $ 6+2=8 $ (ii) $ 2+3=4 $ and $ 3+1=2 $

Show that the set of rational numbers Q forms an abelian group.

Define a ring, give an example of a commutative ring without zero divisors and a non-commutative ring with identity.

Describe the Fundamental Theorem of Arithmetic. Factorize the number '324' and represent it as a product of primes.

Use the Euclidean algorithm to find the greatest common divisor of each pair of integers, (i) 60, 90 (ii) 414, 662

Describe a graph model that can be used to represent all forms of electronic communication between two people in a single graph. What kind of graph is needed?

Explain the complete graph and prove that $ k_5 $ (complete graph) is a nonplanar graph.

Explain the congruence relation. Let $ n $ be a positive integer then: (i) If $ a \equiv b \pmod{n} $, then $ b \equiv a \pmod{n} $ (ii) If $ a \equiv b \pmod{n} $ and $ b \equiv c \pmod{n} $, then $ a \equiv c \pmod{n} $.

Show that $ p \Leftrightarrow q \equiv (p \Rightarrow q) \wedge (q \Rightarrow p) $

Write short notes of the following: (i) Eulerian Graph (ii) Graph Coloring

Write short notes of the following: (i) Chromatic number (ii) Perfect Graph

What is the field? Show that $ (Q, +, \times) $ is a field.

If in a ring R with $ (xy)^2=x^2y^2 $ for all $ x, y \in R $, then R is commutative.

Let A be the set odd positive integers less than 10. Then cardinality of A, |A| is

If m is the number of objects (pigeons) and n is the number of boxes (pigeonholes), then the function is both one-to-one and onto if

If $ A \times B = B \times A $, (Where A and B are general matrices) then

A partial ordered relation is transitive, reflexive and

If B is a Boolean Algebra, then which of the following is true

$ P \rightarrow q $ is logically equivalent to

If $ f(x) = \cos x $ and $ g(x) = x^3 $ then $ (f \circ g)(x) $ is

The number of distinguishable permutations of the letters in the word BANANA are

Which of the following pair is not congruent modulo 7?

Let $ N=\{1,2,3,........\} $ be ordered by divisibility, which of the following subset is totally ordered

Let $ A = B = \{x | -1 \le x \le 1\} $ for each of the following functions state where it is injective, surjective or bijective: i) $ g(x) = \sin \pi x $ ii) $ b(x) = \frac{2x}{3} $

Let $ f(x) = x+2 $, $ g(x) = x-2 $, $ h(x) = 3x $ find (i) $ f \circ g $ (ii) $ f \circ g \circ h $

Find the power set of each of these sets: i) $ \{a,b\} $ ii) $ \{\phi, \{\phi\}\} $

Use Cantor's diagonal argument to prove that set F of all functions $ f: (0,1) \rightarrow R $ has larger Cardinality than |R|.

Determine if the sets are countable or uncountable: a.) the set A of all function $ g: Z_{+} \rightarrow Z_{+} $ b.) The set B of all functions $ f: Z_{+} \rightarrow \{0,1\} $

Prove the following by using the principle of mathematical induction for all $ n \in N $: $ 1^3 + 2^3 + 3^3 + \dots + n^3 = \left(\frac{n(n+1)}{2}\right)^2 $

State and prove Division algorithm theorem well-ordering principle.

Check the validity of the following argument all integers are rational numbers. Some integers are powers of 5. Therefore, some rational numbers are powers of 5.

A grocery store employee is stocking apples. Each apple is a different color. There are 10 apples left in the box and the employee pulls out 2 of them at random. What is the probability that the employee pulls out one pink apple and yellow apple?

Let $ \Psi: G \rightarrow H $ be a homomorphism of groups. Show that if $ a \in G $ has order n, then $ \Psi(a) \in H $ has order dividing n.

Consider the given graph. (a) Does a Hamiltonian path exist? If so describe it. If not say why not.

(b) Does an Eulerian path exist? If so describe it. If not say why not.

Let A be the set odd positive integers less than 10. Then cardinality of A, |A| is

If m is the number of objects (pigeons) and n is the number of boxes (pigeonholes), then the function is both one-to-one and onto if

If $ A \times B = B \times A $, (Where A and B are general matrices) then

A partial ordered relation is transitive, reflexive and

If B is a Boolean Algebra, then which of the following is true

$ P \rightarrow q $ is logically equivalent to

If $ f(x) = \cos x $ and $ g(x) = x^3 $ then $ (f \circ g)(x) $ is

The number of distinguishable permutations of the letters in the word BANANA are

Which of the following pair is not congruent modulo 7?

Let $ N=\{1,2,3,........\} $ be ordered by divisibility, which of the following subset is totally ordered

Let $ A = B = \{x | -1 \le x \le 1\} $ for each of the following functions state where it is injective, surjective or bijective: i) $ g(x) = \sin \pi x $ ii) $ b(x) = \frac{2x}{3} $

Let $ f(x) = x+2 $, $ g(x) = x-2 $, $ h(x) = 3x $ find (i) $ f \circ g $ (ii) $ f \circ g \circ h $

Find the power set of each of these sets: i) $ \{a,b\} $ ii) $ \{\phi, \{\phi\}\} $

Use Cantor's diagonal argument to prove that set F of all functions $ f: (0,1) \rightarrow R $ has larger Cardinality than |R|.

Determine if the sets are countable or uncountable: a.) the set A of all function $ g: Z_{+} \rightarrow Z_{+} $ b.) The set B of all functions $ f: Z_{+} \rightarrow \{0,1\} $

Prove the following by using the principle of mathematical induction for all $ n \in N $: $ 1^3 + 2^3 + 3^3 + \dots + n^3 = \left(\frac{n(n+1)}{2}\right)^2 $

State and prove Division algorithm theorem well-ordering principle.

Check the validity of the following argument all integers are rational numbers. Some integers are powers of 5. Therefore, some rational numbers are powers of 5.

A grocery store employee is stocking apples. Each apple is a different color. There are 10 apples left in the box and the employee pulls out 2 of them at random. What is the probability that the employee pulls out one pink apple and yellow apple?

Let $ \Psi: G \rightarrow H $ be a homomorphism of groups. Show that if $ a \in G $ has order n, then $ \Psi(a) \in H $ has order dividing n.

Consider the given graph. (a) Does a Hamiltonian path exist? If so describe it. If not say why not.

(b) Does an Eulerian path exist? If so describe it. If not say why not.

The statement $ (\sim P \leftrightarrow Q) \wedge \sim Q $ is true, when

Which of the following statements regarding sets is false?

What is the induction hypothesis assumption for the inequality $ m! > 2^m $ where $ m \ge 4 $?

A simple graph can have

An undirected graph has 8 vertices labelled 1, 2, ..., 8 and 31 edges. Vertices 1, 3, 5, 7 have degree 8 and vertices 2, 4, 6, 8 have degree 7. What is the degree of vertex 8?

A graph which has the same number of edges as its complement must have number of vertices congruent to ___ or ___ modulo 4 (for integral values of number of edges).

A graph which consists of disjoint union of trees is called

Which of the following two sets are equal?

If $ C_n $ is the nth cyclic graph, where $ n > 3 $ and n is odd, determine the value of $ X(C_n) $

The number of edges in a regular graph of degree 46 and 8 vertices is

Let $ D = \{-48, -14, -8, 0, 1, 3, 16, 23, 26, 32, 36\} $. Determine which of the following statements are true and which are false. Provide counterexamples for those statements that are false.
(i) $ \forall x \in D $, if x is odd, then $ x > 0 $
(ii) $ \forall x \in D $, if x is less than 0, then x is even
(iii) $ \forall x \in D $, if x is even, then $ x \le 0 $

Indicate which of the following statements are true and which are false. Justify your answers as best you can:
(i) $ \forall x \in Z^+ $, $ \exists y \in Z^+ $ such that $ x = y + 1 $
(ii) $ \forall x \in Z $, $ \exists y \in Z $ such that $ x = y + 1 $
(iii) $ \exists x \in R $ such that $ \forall y \in R $, $ x = y + 1 $
(iv) $ \forall x \in R^+ $, $ \exists y \in R^+ $ such that $ xy = 1 $
(v) $ \forall x \in R $, $ \exists y \in R $ such that $ xy = 1 $
(vi) $ \forall x \in Z^+ $ and $ \forall y \in Z^+ $ $ \exists z \in Z^+ $ such that $ z = x - y $
(vii) $ \forall x \in Z $ and $ \forall y \in Z $, $ \exists z \in Z $ such that $ z = x - y $
(viii) $ \exists u \in R^+ $ such that $ \forall v \in R^+ $, $ uv < v $

Prove the following:
(i) There is a real number x such that $ x > 1 $ and $ 2^x > x^{10} $.
(ii) There is an integer n such that $ 2n^2 - 5n + 2 $ is prime.

Disprove that for all real numbers a and b, if $ a < b $, then $ a^2 < b^2 $.

Show that $ p \vee (q \wedge r) $ and $ (p \vee q) \wedge (p \vee r) $ are logically equivalent. This is the distributive law of disjunction over conjunction.

Find the greatest common divisor of 414 and 662 using the Euclidean algorithm.

If a and b are positive integers, then prove that there exists integers s and t such that $ gcd(a,b) = sa + tb $.

Use mathematical induction to prove this formula for the sum of a finite number of terms of a geometric progression with initial term a and common ratio r:
$ \sum_{j=0}^{n} ar^j = a + ar + ar^2 + \cdots + ar^n = \frac{ar^{n+1}-a}{r-1} $ when $ r \ne 1 $, where n is a non-negative integer.

Write short notes on the following:
(i) Forward proof
(ii) Disjunctive and conjunctive normal form
(iii) Fundamental theorem of arithmetic

An odd number of people stand in a yard at mutually distinct distances. At the same time each person throws a pie at their nearest neighbour, hitting this person. Use mathematical induction to show that there is at least one survivor, that is, at least one person who is not hit by a pie.

Prove Bernoulli's inequality that if $ h > -1 $, then $ 1 + nh \le (1 + h)^n $ for all non-negative integers n.

What is pigeonhole principle? Using it, prove the following:
During a month with 30 days, a baseball team plays at least one game a day, but no more than 45 games. Show that there must be a period of some number of consecutive days during which the team must play exactly 14 games.

What is pigeonhole principle? Using it, prove the following:
The sequence 8, 11, 9, 1, 4, 6, 12, 10, 5, 7 contains 10 terms. Note that $ 10 = 3^2 + 1 $. There are four strictly increasing subsequences of length four, namely, 1, 4, 6, 12; 1, 4, 6, 7; 1, 4, 6, 10; and 1, 4, 5, 7. There is also a strictly decreasing subsequence of length four, namely, 11, 9, 6, 5.

In a Round-Robin tournament, the Tigers beat the Blue Jays, the Tigers beat the Cardinals, the Tigers beat the Orioles, the Blue Jays beat the Cardinals, the Blue Jays beat the Orioles and the Cardinals beat the Orioles. Model this outcome with a directed graph.

Let $ G=(V,E) $ be a simple graph. Let R be the relation on V consisting of pairs of vertices (u, v) such that there is a path from u to v or such that $ u = v $. Show that R is an equivalence relation.

Determine whether the following given pair of directed graphs, shown in Fig. 1 and Fig. 2, are isomorphic or not. Exhibit an isomorphism or provide a rigorous argument that none exists.

Use pseudocode to describe an algorithm for determining the value of a game tree when both players follow a minmax strategy.

Suppose that $ T_1 $ and $ T_2 $ are spanning trees of a simple graph G. Moreover, suppose that $ e_1 $ is an edge in $ T_1 $ that is not in $ T_2 $. Show that there is an edge $ e_2 $ in $ T_2 $ that is not in $ T_1 $ such that $ T_1 $ remains a spanning tree if $ e_1 $ is removed from it and $ e_2 $ is added to it, and $ T_2 $ remains a spanning tree if $ e_2 $ is removed from it and $ e_1 $ is added to it.

Show that a degree-constrained spanning tree of a simple graph in which each vertex has degree not exceeding 2 consists of a single Hamiltonian path in the graph.

The statement $ (\sim P \leftrightarrow Q) \wedge \sim Q $ is true, when

Which of the following statements regarding sets is false?

What is the induction hypothesis assumption for the inequality $ m! > 2^m $ where $ m \ge 4 $?

A simple graph can have

An undirected graph has 8 vertices labelled 1, 2, ..., 8 and 31 edges. Vertices 1, 3, 5, 7 have degree 8 and vertices 2, 4, 6, 8 have degree 7. What is the degree of vertex 8?

A graph which has the same number of edges as its complement must have number of vertices congruent to ___ or ___ modulo 4 (for integral values of number of edges).

A graph which consists of disjoint union of trees is called

Which of the following two sets are equal?

If $ C_n $ is the nth cyclic graph, where $ n > 3 $ and n is odd, determine the value of $ X(C_n) $

The number of edges in a regular graph of degree 46 and 8 vertices is

Let $ D = \{-48, -14, -8, 0, 1, 3, 16, 23, 26, 32, 36\} $. Determine which of the following statements are true and which are false. Provide counterexamples for those statements that are false.
(i) $ \forall x \in D $, if x is odd, then $ x > 0 $
(ii) $ \forall x \in D $, if x is less than 0, then x is even
(iii) $ \forall x \in D $, if x is even, then $ x \le 0 $

Indicate which of the following statements are true and which are false. Justify your answers as best you can:
(i) $ \forall x \in Z^+ $, $ \exists y \in Z^+ $ such that $ x = y + 1 $
(ii) $ \forall x \in Z $, $ \exists y \in Z $ such that $ x = y + 1 $
(iii) $ \exists x \in R $ such that $ \forall y \in R $, $ x = y + 1 $
(iv) $ \forall x \in R^+ $, $ \exists y \in R^+ $ such that $ xy = 1 $
(v) $ \forall x \in R $, $ \exists y \in R $ such that $ xy = 1 $
(vi) $ \forall x \in Z^+ $ and $ \forall y \in Z^+ $ $ \exists z \in Z^+ $ such that $ z = x - y $
(vii) $ \forall x \in Z $ and $ \forall y \in Z $, $ \exists z \in Z $ such that $ z = x - y $
(viii) $ \exists u \in R^+ $ such that $ \forall v \in R^+ $, $ uv < v $

Prove the following:
(i) There is a real number x such that $ x > 1 $ and $ 2^x > x^{10} $.
(ii) There is an integer n such that $ 2n^2 - 5n + 2 $ is prime.

Disprove that for all real numbers a and b, if $ a < b $, then $ a^2 < b^2 $.

Show that $ p \vee (q \wedge r) $ and $ (p \vee q) \wedge (p \vee r) $ are logically equivalent. This is the distributive law of disjunction over conjunction.

Find the greatest common divisor of 414 and 662 using the Euclidean algorithm.

If a and b are positive integers, then prove that there exists integers s and t such that $ gcd(a,b) = sa + tb $.

Use mathematical induction to prove this formula for the sum of a finite number of terms of a geometric progression with initial term a and common ratio r:
$ \sum_{j=0}^{n} ar^j = a + ar + ar^2 + \cdots + ar^n = \frac{ar^{n+1}-a}{r-1} $ when $ r \ne 1 $, where n is a non-negative integer.

Write short notes on the following:
(i) Forward proof
(ii) Disjunctive and conjunctive normal form
(iii) Fundamental theorem of arithmetic

An odd number of people stand in a yard at mutually distinct distances. At the same time each person throws a pie at their nearest neighbour, hitting this person. Use mathematical induction to show that there is at least one survivor, that is, at least one person who is not hit by a pie.

Prove Bernoulli's inequality that if $ h > -1 $, then $ 1 + nh \le (1 + h)^n $ for all non-negative integers n.

What is pigeonhole principle? Using it, prove the following:
During a month with 30 days, a baseball team plays at least one game a day, but no more than 45 games. Show that there must be a period of some number of consecutive days during which the team must play exactly 14 games.

What is pigeonhole principle? Using it, prove the following:
The sequence 8, 11, 9, 1, 4, 6, 12, 10, 5, 7 contains 10 terms. Note that $ 10 = 3^2 + 1 $. There are four strictly increasing subsequences of length four, namely, 1, 4, 6, 12; 1, 4, 6, 7; 1, 4, 6, 10; and 1, 4, 5, 7. There is also a strictly decreasing subsequence of length four, namely, 11, 9, 6, 5.

In a Round-Robin tournament, the Tigers beat the Blue Jays, the Tigers beat the Cardinals, the Tigers beat the Orioles, the Blue Jays beat the Cardinals, the Blue Jays beat the Orioles and the Cardinals beat the Orioles. Model this outcome with a directed graph.

Let $ G=(V,E) $ be a simple graph. Let R be the relation on V consisting of pairs of vertices (u, v) such that there is a path from u to v or such that $ u = v $. Show that R is an equivalence relation.

Determine whether the following given pair of directed graphs, shown in Fig. 1 and Fig. 2, are isomorphic or not. Exhibit an isomorphism or provide a rigorous argument that none exists.

Use pseudocode to describe an algorithm for determining the value of a game tree when both players follow a minmax strategy.

Suppose that $ T_1 $ and $ T_2 $ are spanning trees of a simple graph G. Moreover, suppose that $ e_1 $ is an edge in $ T_1 $ that is not in $ T_2 $. Show that there is an edge $ e_2 $ in $ T_2 $ that is not in $ T_1 $ such that $ T_1 $ remains a spanning tree if $ e_1 $ is removed from it and $ e_2 $ is added to it, and $ T_2 $ remains a spanning tree if $ e_2 $ is removed from it and $ e_1 $ is added to it.

Show that a degree-constrained spanning tree of a simple graph in which each vertex has degree not exceeding 2 consists of a single Hamiltonian path in the graph.

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