Table of Contents

Toggle**Important RGPV Question **

**AL-401 (Introduction to Discrete Structure &Linear Algebra)**

**IV Sem, AI**

**UNIT 1- Set Theory, Relation, Function, Theorem Proving Techniques**

**Q.1)** If A= {2,4,6,9} and B = {4, 6, 18, 27, 54}, a β A, be B, find the set of ordered pairs such that ‘a’ is factor of ‘b’ and a < b.

**RGPV June 2023**

**Q.2)** Let R be the relation on the set R of all real numbers defined by a R b if and only if (a – b|β€ 1. Then prove that R is reflexive, symmetric, but not transitive.

**RGPV June 2023**

**Q.3) **Let A={1,2,3,4,5,6} and a R b if and only if a is multiple of b.

Find:

i) Domain

ii) Range,

iii) Matrix of a relation,

iv) Digraph of the relation R

**RGPV June 2023**

**Q.4) **What common relations on Z are the transitive closures of the following relations?

i) a S b if and only if a + 1 = b.

ii) a R b if and only if a – b = 2.

**RGPV June 2023**

**Q.5) **Write short note on partially ordered sets and explain with suitable example.

**RGPV June 2023**

**Q.6) **Let A = {1,2,3,4,6,8,9,12,18,24) be ordered by divisibility. Draw Hasse diagram.

**RGPV June 2023**

**Q.7)** With the help of Venn-diagram, prove that (AUB) = A’ B’ and (Aβ©B)’ = A’B’

**RGPV Nov 2023**

**Q.8) **Consider the set Z of integers m > 1. We say that x is congruent to y modulo m written as x = y(modm)

If xy is divisible by m. Show that this defines an equivalence relation on Z.

**RGPV Nov 2023**

**Q.9) **Let Dm denotes the positive divisors of m ordered by divisibility. Draw the Hasse diagrams of the following:

i) D15

ii) D24

**RGPV Nov 2023**

**Q.10) **Prove that:

i) A-(BOC) = (A-B)U(A-C)

ii) Ax(BOC)=(AxB)(AxC)

**RGPV Nov 2023**

**Q.11) **List the 16 different relations on the set {0, 1}. How many of the 16 different relations on {0, 1} contain the pair 0, 1}. Which of the 16 relations on {0, 1} are reflexive, symmetric and transitive.

**RGPV June 2022**

**Q.12) **Draw the Hasse diagram for divisibility on the set {1, 2, 3, 4, 5, 6} .

**RGPV June 2022**

**UNIT 2- Algebraic structure: Definition, Properties, types**

### Β

**Q.1)**Β Consider the set Q of rational numbers and let * be the operation on Q defined by:

a*b=a+b-ab

i) Is (Q, *) a semi-group. Is it commutative.

ii) Find the identity element for

iii) Do any elements in Q have inverse? What is it?

**RGPV Nov 2023**

**Q.2)**Β **Β **Define Ring with example. Also explain Commutative ring and ring homomorphism.

**RGPV Nov 2023**

**Q.3) **Solve the following recurrence relations

**RGPV Nov 2023**

**Q.4) **Show that the set S = {(1, 3, 5, 7), X} forms a group.

**RGPV June 2022**

**Q.5) **Prove that

using recurrence relation.

**RGPV June 2022**

**Q.6) **Define the terms: Abelian Group, Cyclic Group and Normal Sub group.

**RGPV June 2022**

**UNIT 3- Propositional logic: Proposition, First order Logic**

**Q.1)**Β Prove that p β§ q β p β¨ q is a tautology.

**RGPV June 2023**

**Q.2)**Β Show that (p β¨ q) β§ (~p) β§(~q) is a contradiction.

**RGPV June 2023**

**Q.3) **Prove that in any graph G, even number of vertices is of

odd degree.

**RGPV June 2023**

**Q.4) **Let G be a planar graph with 10 vertices, 3 components and 9 edges. Find the number of regions in G.

**RGPV June 2023**

**Q.5) **Find chromatic number of the following graph- **RGPV June 2023**

**Q.6) **Show that-

is a tautology by laws of algebra of propositions.

**RGPV Nov 2023**

**Q.7) **Β Obtain the conjunctive normal form of

**RGPV Nov 2023**

**Q.8)** Check for Euler and Hamiltonian graphs: **RGPV Nov 2023**

**Q.9) **What is coloring problem? Hence define coloring of graph.

**RGPV Nov 2023, June 2022**

**Q.10) **Demonstrate that pβ¨(qβ§r) and (pβ¨q)β§(pβ¨r) are

logically equivalent. (Using Truth table)

**Q.11) **Show that

are logically equivalent by developing series of logical equivalence.

**RGPV June 2022**

**Q.12) **Discuss various graph terminologies.

**RGPV June 2022**

**UNIT 4- : Matrices: Determinant and Trace, Cholesky Decomposition**

**Q.1)**Β Solve the equations

6x +15y + 55z = 76,

15x + 55y + 225z = 295,

55x + 225y + 979z = 1259

Using Cholesky decomposition method.

**RGPV June 2023**

**Q.2)**Β Find singular value decomposition for- **RGPV June 2023**

**Q.3) **Solve the simultaneous equations:

25x+15y-Sz=35, 15x+18y+0. z=33,-5x+0. y=11z=6 Using Cholesky Decomposition.

**RGPV Nov 2023**

**Q.4) )** Find the singular value decomposition of the matrix: **RGPV Nov 2023**

**Q.5) **Solve the system by Cholesky decomposition.

x+2y+3z = 5, 2x + 8y +22z=6, 3x + 22y +82z= -10.

**RGPV June 2022**

**Q.6) **Find the singular value decomposition of the matrix- **RGPV June 2022**

**UNIT 5- Test of Hypothesis : Concept and Formulation**

Β Β **Q.1)**Β To test the hypothesis that eating fish makes one smarter, a random sample of 12 persons take a fish oil supplement for one year and then are given an IQ test. Here are the results:

116 111 101 120 99 94 106 115 107 101 110 92

Test using the following hypothesis, report the test statistic with the P-value, then summarize your conclusion.

H0: ΞΌ = 100

Ha: ΞΌ > 100

**RGPV June 2023**

**Q.2)**Β An agricultural research organization wants to study the effect of four types of fertilizers on the yield of crop. It divided the entire field into 24 plots of land and used fertilizer at random in 6 plots of land. Part of calculations are given below:

i) Fill in the blanks in the ANOVA table.

ii) Test at a = 0.5, whether the fertilizers differ significantly.

**RGPV Nov 2023**

**Q.3) **A coin was tossed 400 times and the head turned up 216 times. Test the hypothesis that the coin is unbiased.

**RGPV Nov 2023**

**Q.4) **Three samples, each of size 5, were drawn from three uncorrelated normal populations with equal variances. Test the hypothesis that the population means are equal at 5% Level.

**RGPV June 2022**

**EXTRA QUESTIONS**

Β **Q.1)**Β What are the critical values for a one-independent sample non directional (two-tailed) z test at a .05 level of significance?

**RGPV June 2023**

**Q.2)**Β Write short Note on

a) Hasse diagram

b) Lattice

c) Weighted Graph

**RGPV June 2023**

**Q.3) **What is null hypothesis? What is its significance in statistical variance?

**RGPV Nov 2023**

**— Best of Luck for Exam —**