Department of Mathematics

Faculty of Engineering & Technology

VBS Purvanchal University, Jaunpur

Subject: Discrete Structure and Theory of Logic (KCS-303)

Syllabus

DETAILED SYLLABUS 3-0-0

Unit Topic Proposed
Lecture
I Relations: Definition, Operations on relations, Properties of 08
relations, Composite Relations, Equality of relations, Recursive
definition of relation, Order of relations.
Functions: Definition, Classification of functions, Operations on
functions, Recursively defined functions. Growth of Functions.
Natural Numbers: Introduction, Mathematical Induction,
Variants of Induction, Induction with Nonzero Base cases. Proof
Methods, Proof by counter – example, Proof by contradiction.

II Algebraic Structures: Definition, Groups, Subgroups and order, 08

Cyclic Groups, Cosets, Lagrange's theorem, Normal Subgroups,
Permutation and Symmetric groups, Group Homomorphisms,
Definition and elementary properties of Rings and Fields.

III Lattices: Definition, Properties of lattices – Bounded, 08

Complemented, Modular and Complete lattice. Boolean Algebra:
Introduction, Axioms and Theorems of Boolean algebra,
Algebraic manipulation of Boolean expressions. Simplification of
Boolean Functions, Karnaugh maps, Logic gates, Digital circuits
and Boolean algebra.

IV Propositional Logic: Proposition, well formed formula, Truth 08

tables, Tautology, Satisfiability, Contradiction, Algebra of
proposition, Theory of Inference.
Predicate Logic: First order predicate, well formed formula of
predicate, quantifiers, Inference theory of predicate logic.

V Recurrence Relation & Generating function: Recursive 08

definition of functions, Recursive algorithms, Method of solving
recurrences.
Combinatorics: Introduction, Counting Techniques, Pigeonhole
Principle
Number Theory: Introduction, Basic Properties, Divisibility
Theory, Congruences, Applications of Congruences.
Text books:
1. Koshy, Discrete Structures, Elsevier Pub. 2008 Kenneth H. Rosen, Discrete Mathematics and
Its Applications, 6/e, McGraw-Hill, 2006.
2. B. Kolman, R.C. Busby, and S.C. Ross, Discrete Mathematical Structures, 5/e, Prentice Hall,
2004.
3. E.R. Scheinerman, Mathematics: A Discrete Introduction, Brooks/Cole, 2000
4. R.P. Grimaldi, Discrete and Combinatorial Mathematics, 5/e, Addison Wesley, 2004
5. Liptschutz, Seymour, “Discrete Mathematics”, McGraw Hill.
6. Trembley, J.P & R. Manohar, “Discrete Mathematical Structure with Application to
ComputerScience”, McGraw Hill
7. Narsingh, “Graph Theory With application to Engineering and [Link].”, PHI.
8. Krishnamurthy, V., “Combinatorics Theory & Application”, East-West Press Pvt. Ltd., New
Delhi

Question Bank

UNIT - I

1. Let 𝐴 = {𝑎, 𝑏, 𝑐} and the relation R be defined on A as follows:

𝑅 = { (𝑎, 𝑎), (𝑏, 𝑐), (𝑎, 𝑏) }. Then, write minimum number of ordered pairs to be
added in R to make R reflexive and transitive. Ans: 3.
2. Let D be the domain of real valued function f defined by 𝑓(𝑥) = √25 − 𝑥 then,
write D. Ans : 𝐷 = [−5,5] ,
3. Show that a set A with 3 elements has 2 symmetric relations on A. Hint: 2 ( )⁄

4. Is 𝑔 = {(1, 1), (2, 3, (3, 5), (4, 7)} a function? If g is described by g(x) = αx +𝛽𝑦,
then what value should be assigned to α and β? Ans : 𝛼 = 2, 𝛽 = −1.
5. If R ={ (a, a³): a is a prime number less than 5 } be a relation. Find the range of R.
Ans : {8,27}.
6. Let R be the equivalence relation in the set A = {0,1,2,3,4,5} given by
R = {(a,b): 2 divides (a - b)}. Write the equivalence class [0].
Ans: equivalence class of [0] = [2,4].

7. If 𝑅 = {(𝑥, 𝑦): 𝑥 + 2𝑦 = 8} is a relation on N, then write the range of R.

8. Ans: Range={3, 2, 1}.
9. If 𝐴 = {1,2}, 𝐵 = {2,3,4}, 𝐶 = {4,5}, then find: 𝐴 × (𝐵 ∩ 𝐶).
10. If 𝑃 = {1,3}, 𝑄 = {2,3,5} find the number of relations from P to Q. Ans: 64.

11. If the ordered Pairs (𝑥 − 1, 𝑦 + 3) and (2, 𝑥 + 4) are equal, find 𝑥 and 𝑦.
Ans :𝑥 = 3, 𝑦 = 4.

[Link] a and b are any two elements of group G then prove : (𝑎∗ 𝑏) =𝑏 *𝑎 .
13. If f : A  B is one-one onto mapping, then prove that 𝑓 : B  A will be
one-one onto mapping.
14. Let R be a relation on the set of natural numbers N, as R = {(x, y) : x, y  N, 3x +
y = 19}. Find the domain and range of R. Verify whether R is reflexive.
15. Show that the relation R on the set Z of integers given by R = {(a, b) : 3 divides a
– b}, is an equivalence relation.
16. Let 𝐴 = { 𝑎 , 𝑎 , 𝑎 }, 𝐵 = { 𝑏 , 𝑏 , 𝑏 , 𝑏 } . Find the matrix relation.
17. Define injective, surjective and bijective function.
[Link] the power set of each of these sets, where a and b are distinct elements
(𝑖) 𝑎, {𝑏} , (𝑖𝑖) 1, ∅, {∅} .
19. Prove that 𝐴 × (𝐵 ∩ 𝐶) = (𝐴 × 𝐵) ∩ (𝐴 × 𝐶).
20.. The following relation on A = {1, 2, 3, 4}. Determine whether the following: (a)
R = {(1, 3),(3,1), (1, 1), (1, 2), (3, 3), (4, 4)}. (b) 𝑅 = 𝐴 × 𝐴 is an equivalence
relation or not.
21.. Let R be a binary relation defined as R = { (a,b) ∈ 𝑅 ∶ (𝑎, 𝑏) ≤ 3} determine
whether R is reflexive, symmetric, anti symmetric and transitive and how many
distinct binary relation are there on finite set.
22. Let A = { 1,2,3,4,5,6 } and let R be the relation defined by x divides y written as
x/y :
(a) Write R as a set of ordered pairs.
 (b) Draw its directed graph.
(c) Find 𝑅 .
23. If f : A  B, g : B  C are invertible functions, then show that gof : A  C is
invertible and (𝑔𝑜𝑓) =𝑓 𝑜𝑔 .
24. State whether the function f: N→ N given by f(x) = 5x is injective, surjective or
both.
25. Given a non empty set X, consider P(X) which is the set of all subsets of X.
Define the relation R in P(X) as follows: For subsets A, B in P(X), A R B if and
only if A⊂B. Is R an equivalence relation on P(X)?
26. Write short notes on : a. Equivalence relation b. Composition of relation.
27. Show that the relation R in the set {1, 2, 3} given by R= {(1, 1), (2, 2), (3, 3), (1,
2), (2, 3)} is reflexive but neither symmetric nor transitive.
28. Let X = {1, 2, 3,....., 7} and R = {(x, y)|(x – y) is divisible by 3}. Is R equivalence
relation. Draw the digraph of R.
29. Determine whether each of these functions is a bijective from R to R:
(a) 𝑓(𝑥) = 𝑥 + 1 (b) 𝑓(𝑥) = 𝑥 (c) 𝑓(𝑥) = (𝑥 + 1)⁄(𝑥 + 2).
30. Let R ={ (1,2), (2,3), (3,1) } and A = { 1,2,3 } , find the reflexive , symmetric
and transitive closure of R ,using (i) Composition of relation R. (ii) Composition
of matrix relation R. (iii) Graphical representation of R.
31. Show that the function f and g both of which are from N × N to N given by
𝑓(𝑥, 𝑦) = 𝑥 + 𝑦 and 𝑔(𝑥, 𝑦) = 𝑥𝑦 are onto but not one-one.
32. The composition of any function with the identity function is the function itself
i.e. (𝑓 𝑜 𝐼 )(𝑥) = (𝐼 𝑜 𝑓)(𝑥) = 𝑓(𝑥).
33. Show that √3 is not a rational number.
34. By the first principle of mathematical induction, prove that: 3 + (−1) 2 ≡
(𝑚𝑜𝑑 5).
35. Prove that 𝑛 + 2𝑛 is divisible by 3 using principle of mathematical induction,
where n is natural number.

UNIT -II

1. Define : (a) Groupoid (b) Semigroup (c) Monoid.

2. Define Group and write its properties.
3. 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,*).
4. Define order of finite and infinite Group.
5. Define Homomorphism of Group.
6. Show that every cyclic group is abelian.
7. Define a binary operation? Give an example of a binary operation which is not
associative.
8. Let S= {𝑒, 𝑎, 𝑏, 𝑐} be a group with binary operation ∗ ,then complete the following
group table.(Explanation table says that a ∗ b = c).
* e a b c
e e a b c
a a c
b b
c c
9. Let S be a set of all real numbers except -1. Define ∗ on S by the rule 𝑎 ∗ b = a +
b + ab ∀ 𝑎, 𝑏 ∈ 𝑆. Show that (S,*) is a group.
10. Prove that the intersection of any subgroup of a group (G,∗) .
[Link] G be a group. If 𝑎, 𝑏 ∈ 𝐺 such that 𝑎 = 𝑒,the identity element of 𝐺 and 𝑎𝑏 =
𝑏𝑎 ,prove that 𝑎 = 𝑒.
[Link] that the binary operation * defined on (𝑅,∗) where 𝑥 ∗ 𝑦 = 𝑚𝑎𝑥 (𝑥, 𝑦) is
associative.
13. If the permutation of the elements of {1, 2, 3, 4, 5} are given by 𝑎 =
(1 2 3)(4 5), 𝑏 = (1) (2) (3) (4 5), 𝑐 = (1 5 2 4) (3). Find the value of 𝑥, if
𝑎𝑥 = b. And also prove that the set 𝑍 = (0, 1, 2, 3) is a commutative ring with
respect to the binary modulo operation + and ∗ .
[Link] that every group of order 3 is cyclic.
[Link] all distinct left cosets of {(0), (3)} in the group (𝑍 , + ) and find their
union.
16.. Let 𝐺 be the set of all non-zero real number and let 𝑎 ∗ 𝑏 = 𝑎𝑏/2. Show
that (𝐺,∗) be an abelian group.
[Link] that the set of integers forms an abelian group under addition.
[Link] that the cube root of unity is an abelian group under multiplication.
19.. Let 𝐺 = {1, −1, 𝑖, −𝑖} with the binary operation multiplication be an algebraic
structure, where 𝑖 = √−1. Determine whether 𝐺 is an abelian or not.

[Link] 𝑍 be the set of integers, show that the operation * on 𝑍 defined by 𝑎 ∗ 𝑏 =

𝑎 + 𝑏 for all 𝑎, 𝑏 ∈ 𝑍 satisfies the closure property, associative law and the
commutative law. Find the identity element. What is the inverse of an integer?
[Link] that [((p  q)  r) (~ p)]  (q  r) is tautology or contradiction.
[Link] that the matrices
1 0 −1 0 1 0 −1 0
, , ,
0 1 0 1 0 −1 0 −1
form a multiplicative abelian group.
[Link] 𝑄 be the set of positive rational numbers which can be expressed in the
form 2 3 , where 𝑎 and 𝑏 are integers, Prove that the algebraic structure (𝑄,
. ) is a group where is multiplication operator.
[Link] the order of every element in the multiplicative group
𝐺 = {𝑎, 𝑎 , 𝑎 , 𝑎 , 𝑎 , 𝑎 = 𝑒}
[Link] G be an abelian group with identity e, then prove that all elements 𝑥 of G
satisfying the equation 𝑥 = 𝑒 from a sub-group 𝐻 of 𝐺.

UNIT – III

1. Define Partially Ordered sets.

2. Draw the Hasse diagram of 𝐷 .
3. Prove that a lattice with 5 elements is not a boolean algebra.
4. Define minimal and maximal element in Posets.
5. Draw the Hasse diagram of [P (a, b, c), ] (Note : ‘’ stands for subset). Find
greatest element, least element, minimal element and maximal element.
6. Distinguish between Bounded lattice and Complemented lattice.
7. Prove that in a distributive lattice ,if an element has complement then this
complement is unique.
8. Prove that (𝑖) (𝑎 + 𝑏) = 𝑎 . 𝑏 (𝑖𝑖) (𝑎. 𝑏) = 𝑎 + 𝑏 .
9. Obtain the equivalent expression for [(𝑥. 𝑦)(𝑧’ + 𝑥𝑦’)].
10. In a lattice if a  b  c, then show that
(a) a  b = b  c.
(b) (a  b)  (b  c) = (a  b)  (a  c) = b.
11. (a) Prove that every finite subset of a lattice has an LUB and a GLB.
(a) (b) Give an example of a lattice which is a modular but not a distributive.
[Link] the poset of divisors of 36 into a totally ordered set in two ways.
[Link] modular lattice, distribute lattice and bounded lattice with example and
diagram.
[Link] the Sum-Of-Products and Product-Of-sum expansion of the Boolean
function F(x, y, z) = (x + y) z.
Ans: 𝑆𝑂𝑃 = 𝑥𝑦𝑧’ + 𝑧’𝑥’𝑦 + 𝑥𝑦’𝑧’ , 𝑃𝑂𝑆 = (𝑥’ + 𝑦’ + 𝑧). (𝑥’ + 𝑦 + 𝑧). (𝑥 + 𝑦’ + 𝑧).
[Link] the following Boolean function :
𝐹(𝑎, 𝑏, 𝑐, 𝑑) = ∑ 𝑚(0,1,2,5.7,8,9,10,13,15). Ans : BD+C’D+B’D’
[Link] the following Boolean function :
𝐹(𝑎, 𝑏, 𝑐, 𝑑) = ∑ 𝑚(0,2,8,10,14) + ∑ 𝑑(5,15) .
And design logic circuit usind NAND gate. Ans: ACD’+B’D’

UNIT -IV

1. Define the terms with example supporting to each: (a) Proposition (b) Compound
proposition (c) Disjunction and Conjunction (d) Conditional and Bi conditional
(e) Tautology,Contradiction and Contingency.
2. How can this sentence be translated into a logical expression ? “you can access
the internet from campus only if you are a computer science major or are not a
freshman. Ans : p→ (q   r).
3. Construct the truth table of (pq) → (pq).
4. Prove that (p  q)  (p  q) is logically equivalent to P  Q.
5. Prove that : ¬(𝑝˅𝑞) ≡ (¬𝑝˄¬𝑞). (De Morgan’s Law)
6. Prove that : 𝑝˅(𝑞˄𝑟) ≡ (𝑝˅𝑞)˄(𝑝˅𝑟). (Distributive Law)
7. Negate the statements (i) All integers are greater than 8. (ii) For all real numbers
𝑥,if 𝑥 > 3 then 𝑥 > 9.
Ans :(i) ~ ∀ 𝑥 𝑝 (𝑥) ≡ ∃ 𝑥 ~ 𝑝(𝑥) . (𝑖𝑖) ∃ 𝑥 (𝑝 (𝑥 ˄ ~ 𝑞 (𝑥)).
8. 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.
d) It is either snowing or below freezing (or both).
e) If it is below freezing, it is also snowing.
f ) Either it is below freezing or it is snowing, but it is not snowing if it is below
freezing
9. How many rows appear in a truth table for each of these compound
propositions?
a) p →∼ p
b) (p∨ ∼ r) ∧ (q∨ ∼ s)
c) q ∨ p∨ ∼ s∨ ∼ r∨ ∼ t ∨ u
d) (p ∧ r ∧ t) ↔ (q ∧ t)
[Link] that if n is a positive integer, then n is even if and only if 7n + 4 is even .
[Link] that the premises “If you send me an e-mail message, then I will finish
writing the program,” If you do not send me an e-mail message, then I will go to
sleep early,” and “If I go to sleep early, then I will wake up feeling refreshed”
lead to the conclusion “If I do not finish writing the program, then I will wake up
feeling refreshed.” Ans with Hint: Use, Contrapositive, Hypothetical syllogism.
[Link] that the following statement is tautology :
(( 𝑝 ˅ 𝑞) ˄ (𝑝 → 𝑟) ˄(𝑞 → 𝑟)) → 𝑟.

UNIT – V
1. Define Recurence relation with example.
2. Find the first four terms of each of the following recurrence relation:
(a) 𝑎 = 2𝑎 + 𝑘, ∀ 𝑖𝑛𝑡𝑒𝑔𝑒𝑟𝑠 𝑘 ≥ 2, 𝑎 = 1. Ans: 𝑎 = 1, 𝑎 = 4, 𝑎 = 4, 𝑎 = 26.
(b) 𝑎 = 𝑘(𝑎 ) , ∀ 𝑖𝑛𝑡𝑒𝑔𝑒𝑟𝑠 𝑘 ≥ 2, 𝑎 = 1. Ans: 𝑎 = 1, 𝑎 = 1, 𝑎 = 2, 𝑎 = 12.
3. Find the recurrence relation from 𝑦 = 𝐴 2 + 𝐵(−3) .
Ans: y −y − 6y = 0.
4. What is the generating function of {1,1,1,1,1,……}. Ans : 1⁄1 − 𝑥 .

5. Solve the recurrence relation using generating function:

𝑎 − 7𝑎 + 10𝑎 = 0 with 𝑎 = 3, 𝑎 = 3. Ans : 𝑎 = 4. 2 − 5 .

6. Solve the recurrence relation using Iteration method :

𝑎 =𝑎 + 2 , 𝑛 ≥ 2, 𝑎 = 3. Ans : 𝑎 = 3 + (𝑛 − 1). 2

7. Solve the recurrence relation:

(a) 𝑎 − 5𝑎 + 6𝑎 = 2, 𝑎 = 1, 𝑎 = −1. Ans:𝑎 = −2. 3 + 2. 2 + 1.

(b) 𝑦 −𝑦 − 2𝑦 = 𝑛 . Ans :𝑦 = 𝐶 (−1) + 𝐶 . 2 − 1 − 𝑛⁄2 − (1⁄2) 𝑛 .

(c) 𝑎 − 2𝑎 = 4, 𝑓𝑜𝑟 𝑛 ≥ 1 𝑎𝑛𝑑 𝑎 = 3. Ans : 𝑎 = √13. 2 − 4.
8. State and Prove Pigeonhole Principle.
9. Prove that (2𝑛)! = 2 𝑛! {1,3,5, … … . . (2𝑛 − 1)}.
10. A coin tossed 6 times .In how many ways can we obtain 4 heads and 2 tails?
Ans: 15
[Link] the gcd of 595 and 252 and express it in the form 252𝑚 + 595𝑛.
Ans: 𝑔𝑐𝑑(595,252) = 7.
[Link] the integers 𝑥 and 𝑦 such that 71𝑥 − 50𝑦 = 1. Ans: 𝑥 = 31, 𝑦 = 44.
[Link] 𝑎 ≡ 𝑏(𝑚𝑜𝑑 𝑚) and 𝑐 is any integer,then prove that:
(a) (𝑎 + 𝑐) ≡ (𝑏 + 𝑐)(𝑚𝑜𝑑 𝑚)
 (b) (𝑎 − 𝑐) ≡ (𝑏 − 𝑐)(𝑚𝑜𝑑 𝑚)
[Link] first 9 digits of this book are 81-219-2232. What is the check digit for this
book? Ans: Check digit 𝑥 = 1.
[Link] the remainder when the following sum is divisiblw by 4, 1 + 2 + 3 +
⋯ … … … . . +100 . Ans : zero
16. Use the theory of congruence to prove that for 𝑛 ≥ 1,17 ‫(׀‬2 + 3. 5 ).
.