RAJ KUMAR GOEL INSTITUTE OF TECHNOLOGY,

GHAZIABAD

Department of CSE (AI&ML)

UNIT TEST
(DSTL BCS303)

UNIT-1
1. If 𝐴 = {1,2}, 𝐵 = {2,3,4}, 𝐶 = {4,5}, then find: 𝐴 × (𝐵 ∩ 𝐶).
2. Find the power set of each of these sets, where a and b are distinct elements (𝑖) {𝑎, {𝑏}}
, (𝑖𝑖) {1, ∅, {∅}}.
3. If R is a relation on the set A={ 1,2,3,4} defined by x R y if x exactly divides y . Prove
that (A,R) is a poset.
4. Show that the relation R={ (a,a),(a,b),(b,a),(b,b)(c,c)} on A={a,b,c} is an equivalence
relation and find A/R also find partitions of A.
5. Draw the Hasse diagram representing the positive divisors of 45.

UNIT-2
1. Let A = B = {x/ -1≤ 𝑥 ≤ 1} for each of the following functions state whether it is
injective, surjective or bijective

3. Let f:R→ 𝑅, 𝑔: 𝑅 → 𝑅, where R is the set of real numbers be given by f(x) = 𝑥2 − 2 and
2. Let f(x)=x+2, g(x) = x-2, h(x) =3x find i) fog ii) fogoh.

4. Prove that (𝑖) (𝑎 + 𝑏)' = 𝑎'. 𝑏' (𝑖𝑖) (𝑎. 𝑏)' = 𝑎' + 𝑏'.
g(x) = x+4 find fog and gof. State whether these functions are bijective or not.

5. Minimize the following Boolean function Using K-Map : 𝐹(𝑎, 𝑏, 𝑐, 𝑑) = ∑

𝑚(0,1,2,5.7,8,9,10,13,15)

UNIT-3

1. Define the terms with example supporting to each: (a) Proposition (b) Compound
proposition (c) Disjunction and Conjunction (d) Conditional and Bi conditional
2. Construct the truth table of (pq) → (pq).

(( 𝑝 ˅ 𝑞) ˄ (𝑝 → 𝑟) ˄(𝑞 → 𝑟)) → 𝑟.
3. Show that the following statement is tautology :

4. Prove that (p  q)  (p  q) is logically equivalent to P  Q.

5. Let p and q be the propositions :
p : It is below freezing.
q : It is snowing.
Write these propositions using p and q and logical connectives (including negations).
a) It is below freezing and snowing.
b) It is below freezing but not snowing.
c) It is not below freezing and it is not snowing.
 UNIT-4

1. Define Group and write its properties.

2. Let Z be the group of integers with binary operation * defined by a*b
= a + b – 2, for all a, b  Z. Find the identity element of the group (Z,*).
3. Show that every cyclic group is abelian.
4. Let 𝐺 be the set of all non-zero real number and let 𝑎 ∗ 𝑏 = 𝑎𝑏/2. Show that
(𝐺,∗) be an abelian group.
5. If G be an abelian group with identity e, then prove that all elements 𝑥 of G
satisfying the equation 𝑥2 = 𝑒 from a sub-group 𝐻 of 𝐺.

UNIT-5

1. State and Prove Pigeonhole Principle.

2. Prove that (2𝑛)! = 2n 𝑛! {1, 3, 5, (2𝑛 − 1)}.
3. What do you mean by Hamiltonian graph?
4. Define the Euler circuit with example.
5. What is the Bipartite graphs.
 1) Use Mathematical Induction to prove the following generalization of one of Demorgan’s
laws

𝑛
( 𝑗=1 𝐴𝑗)′ =𝑗= ��
⋂
1
⋃
′
where A1,A2,A3,………An are subsets of universal set U.
𝑛 ��

2) Prove that if a/bc and (a,b)=1 then a/c.

3) State and Prove Division algorithm theorem using well ordering principle.
4) Describe set of rooted trees recursively?

Use Mathematical Induction to show that 1+2+22 + 23 + ⋯ … … … + 2𝑛 = 2𝑛+1 − 1

5) Show that if a,b,c are integers such that a/b and a/c then a/mb+nc where m, n are integers.
6)
7) Write the Procedure for Euclidean algorithm to find gcd of two numbers.
8) Describe full binary tree recursively.
9) Prove that there are infinitely many primes.
10) Define modular arithmetic? Prove that the integers a,b are congruent modulo m iff there is an
integer k such that a=b+km, where m is a positive integer.

VERY SHORT ANSWER QUESTIONS

1) State fundamental theorem of arithmetic hence find the prime factorization of 810.
2) Write prime numbers less than 150.
3) Write the properties of gcd.
4) State and prove Euclid’s lemma.
5) Define Fibonacci numbers recursively.
6) Explain about Mathematical Induction.
7) Explain pair wise relatively primes with an example.
8) Define Mersenne prime numbers.
9) Write the properties of divisibility.
10) Define well ordering principle.
UNIT-3

MATHEMATICAL LOGIC

SHORT ANSWER QUESTIONS(5 MARKS)

1) Find PCNF without Constructing truth table (P→(Q𝖠R)) → (~ P→ (~ Q𝖠 ~R))

2) Use truth table to prove the following argument

p→~
qr→
p

∴ ~𝑟
q

3) Find PDNF by constructing its PCNF of (Q v P)⋀ (QVR)𝖠 (∼ (PV R) V ∼Q))

4) Find whether the following argument is valid or not
“ No Engineering student is bad in studies “
“Anil is not bad in studies”

Therefore “ Anil is an engineering student”

5) Without constructing truth table find PDNF of
{(P →(Q 𝖠 R)) 𝖠 (~ Q𝖠∼ 𝑅 )}
6) Prove that the following argument is valid:
“all dogs are carnivorous. “
“some animals are dogs.”

Therefore” some animals are carnivorous”.

~𝑞
7) Is the following Conclusion valid derive from contradiction method.

p⋁ t
p→q

∴𝑡

8)Construct PCNF of (P⇔ 𝑄) → R.

9)Obtain CNF of ((𝑃 → 𝑄)⋀ ∼ 𝑄) → ~𝑃

10)Obtain DNF of (𝑄 → 𝑃)⋀(~𝑃⋀𝑄)

11) Find PDNF by constructing the PCNF of (Q v P)⋀ (QVR)𝖠 (∼ (PV R) V ∼Q)).
12) Prove that for any three propositions P,Q,R the compound proposition (𝑃 → (𝑄 →
𝑅)) → ((𝑃 → 𝑄) → (𝑃 → 𝑅)) is a tautology by 𝑖) with truth table ii) with
laws of logic.

𝑃 → 𝑄, 𝑃 → 𝑅, 𝑄 → ~𝑅, 𝑃
13) Show that the following set of premises are inconsistent
 14) 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.

VERY SHORT ANSWER QUESTIONS

1) Construct the truth table of (PVQ) → P.
2) Write the rule of disjunctive amplification of predicates.
3) Construct the truth table of (P𝖠Q)→P.
4) Write the rule of Modus tollens of predicates.
5) Write the rule of Modus Pones of predicates.

Express the compound propositions p→(q⋁ r), p 𝖠 (∼ q) in words.

6) If p: A circle is a conic, q: 5 is a real number, r: Exponential series is convergent.

7) Show that the following argument is consistent

pVq

∼p

∴𝐶

8) Write a short notes on DNF and CNF.

9) Express the statement in words: “Every student in class has studied Calculus.” Using

10) Show using truth table that the statements ( p → q) and (∼ p V q ) are logically
quantifiers.

equivalent.

UNIT -4 GROUPS

SHORT ANSWER QUESTIONS(5 MARKS)

1) Construct composition table for the roots of equation x4= 1 and Show that it is a group with
respect to operation multiplication.
2) Prove that every finite group of order ‘n’ is isomorphic to permutation group of degree ‘n’.
3) If ‘G’ is a group then prove that (a-1)-1=a.
4) Prove that G ={0,1,2,3,4} is an abelian group of order 5 with respect to addition modulo 5.
5) Show that Q1 (rational numbers other than1) is an infinite abelian group with respect to *
defined by a*b=a+b-ab, where a,b are rational numbers.
6) Prove that the identity element of a group “G’ is same as identity element of its subgroup H.
7) Prove that in a group its identity element, inverse element are unique.
8) State and prove Lagrange’s theorem on cosets.
9) Prove that G ={0,1,2,3,4,5,6} is an abelian group of order 7 with respect to addition modulo
7.
 10) Define subgroup, normal subgroup, Quotient group, left and right cosets with an example for
each.
11) Prove that set of non-singular matrices of order 2 x 2 is a group but not an abelian group
under multiplication.

VERY SHORT ANSWER QUESTIONS(2 MARKS)

1) Show that binary operation * defined on (R,*) where x*y=xy is not associative.
2) Define a) Normal subgroup of a group b) Quotient group.

If aob=a+b+ab ∀ a,b∈Z ,show that (Z,0) is a semi group.

3) Define cyclic group with an example.

Find the order of each element in the group {1, −1, 𝑖, −𝑖}.
4)

If a, b ∈ group G, then prove that (𝑎𝑏)−1 =b-1 a-1

5)
6)
7) Show that the cube roots of unity forms a group with respect to multiplication.
8) Define a) Left coset of subgroup H in G. b) Right coset of subgroup H in G.

9) Define a) Index of a coset. b) If H={1,-1} is a subgroup of the group G={1,-1,I,-i},then find the
index of H in G.

10) Define permutation group and degree of a permutation group.

UNIT 5

GRAPH THEORY

SHORT ANSWER QUESTIONS(5 MARKS)

1) Define graph coloring and chromatic number of a graph and find the chromatic

𝑖)𝐾3,3
number of
ii) cycle with even number of vertices.
2) Define the following terms. Give one suitable example for each

i) Euler circuit ii) Hamiltonian graph.

3) State and prove Euler’s theorem on plane graphs.
4) Define isomorphism of graphs. What are the steps followed in discovering the
isomorphism.
5) Define dual and Isomorphism of graphs with example.
6) State and prove fundamental theorem of graph theory.
 7) Explain Eulerian and Hamiltonian graphs with examples, also draw the graphs of the
following

i)Eulerian but not Hamiltonian

ii)Hamiltonian but not Eulerian

8)Two graphs with the following adjacency list are given, Find whether G and H are
isomorphic or not
Graph G Graph H -
vertices Adjacent Vertices Adjacent
vertices vertices

P q,s a b,c,d

Q p,r,s b b,d

R q,t c a,d

S p,q,t d a,b,c

T s e D

9)Write incident matrix and adjacency matrix to the graph whose adjacency list is
given by
vertices Adjacent
vertices

a b,e

b a,c,d,

c b,d

d e,b,c,

e a,d

9) Two graphs with the following adjacency list are given, show that they are isomorphic to each
other
Graph G Graph H
vertices Adjacent Vertices Adjacent
vertices vertices

A b,c k L

B a L k,m,n

C a,d,e m l

D c n l,o
 E c O n

10) If ‘𝐺’ be a graph with |𝑉|=n vertices and |𝐸| edges then prove that∑𝑛𝑖= deg (𝑣𝑖)= 2E
11) Write the conditions to construct dual of the graph and construct dual1 of the following graph
whose adjacency list is given :
Vertices Adjacent
vertices

A b,c

B a,c,e

C a,d,e,b

D C

E b,c

VERY SHORT ANSWER QUESTIONS (2 MARKS)

1) Define complete bipartite graph with example.

2) Define the following terms with suitable example i) Complete graph ii) Regular graph.
3) Define isomorphism of two graphs.
4) Define the following terms with suitable example i) Subgraph ii) Spanning graph.
5) Define the following sub graphs of a graph a) Closed Walk and Open walk b) Trail
6) Define dual of a planar graph and explain it through an example.
7) Define Chromatic number of a graph. Explain it through an example.
8) Draw K5 complete graph.
9) Let G be a 4-regular connected planar graph having 16 edges. Find the number of regions of
G.
10) State fundamental theorem of graph theory.