Q1.

Define Conditional and Bi-conditional Statement with example

Conditional Statement

A conditional statement is of the form p → q, which is read as

👉 “If p, then q”

 p = hypothesis (antecedent)

 q = conclusion (consequent)

Truth: It is false only when p is true and q is false, otherwise true.

Example:
p: It is raining
q: The ground is wet

Statement: If it is raining, then the ground is wet.

Bi-conditional Statement

A bi-conditional statement is of the form p ↔ q, read as

👉 “p if and only if q”

It is true when both p and q have the same truth value.

Example:
p: You pass the exam
q: You score more than 40 marks

Statement: You pass the exam if and only if you score more than 40 marks.

Q2. Truth table for

p∨
pq p→q q→p Final Result
q

TTT T T T

TFT F T F

FTT T F F

FFF T T F

✅ Conclusion: Statement is true only when p and q are both true.

Q3. Truth table for

( p ∨q)→ {( p ∨ q)→(r ∨ q)}

p∨ r∨ (p∨q)→(r∨q
pqr Final
q q )

T TTT T T T

T TFT T T T

T F TT T T T

T FFT F F F

F TTT T T T

F TFT T T T

F F TF T T T

F FFF F T T

Q4. Show that

Truth table shows final column is always TRUE, hence:

✅ It is a Tautology (always true).

Q5. Translation into English

Let
P: It is hot
Q: It is raining

(ii) p ∧ q → It is hot and it is raining

(i) ~p → It is not hot

(iii) p ∨ q → It is hot or it is raining

(iv) q ∨ ~p → It is raining or it is not hot

Q6. CNF of
 ∼( p ∨ q)↔( p ∧ q)

Step 1:

∼( p ∨ q)=∼ p ∧∼q

Step 2:

Step 3: Convert ↔ into implication and simplify

Final CNF:

Q7. PDNF & PCNF

(i) p ∨ q

PDNF:

PCNF:

( p ∨q )

(ii) p → q

p → q=∼ p ∨ q

PDNF:

PCNF:

( ∼ p ∨q )

(iii) ~p ∨ ~q

PDNF:

PCNF:

( ∼ p ∨∼ q )
Q8. Show De-Morgan’s Laws

(i)

∼( p ∨ q)≡(∼ p ∧∼ q)

(ii)

∼( p ∧ q)≡(∼ p ∨∼ q)

✅ Both proved using truth tables.

Q9. Validity of Argument

Let
p: It rains today
q: We have a barbeque today
r: We have a barbeque tomorrow

Given:

1. p → ~q

2. ~q → r

Conclusion: p → r

This follows Hypothetical Syllogism

✅ Argument is VALID

Q10. Universal and Existential Quantifiers

Universal Quantifier (∀)

Means “for all”

Example:

∀ x (x> 0)

→ All numbers are positive

Existential Quantifier (∃)

Means “there exists”

Example:

∃ x (x=0)

→ There exists a number equal to zero

Q11. Validity of Argument

Given:

1. If today is David’s birthday → Today is January 24

2. Today is January 24

Conclusion: Today is David’s birthday

This is the fallacy of Affirming the Consequent

❌ Argument is INVALID

Q1. Domain and Range

(i) Find the Domain

x
(a) f (x)= 2
x +1

The denominator is x 2+ 1.

Since
2 2
x ≥ 0 ⇒ x +1>0 for all real x

So the denominator is never zero.

✅ Domain

(−∞ , ∞ )

(b) f (x)=
√ x+ 2
x−2

Conditions:

1. Square root must be defined:

x +2≥ 0 ⇒ x ≥−2

2. Denominator must not be zero:

x−2 ≠ 0 ⇒ x ≠ 2
✅ Domain

¿ ∪(2, ∞)

(ii) Find the Range

x
(a) f (x)= 2
1+ x

Let
x
y= 2
1+ x

Rearranging:
2 2
y (1+ x )=x ⇒ y x −x + y=0

This is a quadratic in x .
For real solutions, discriminant ≥ 0:
−1 1
¿ ≤ y≤
2 2

✅ Range

[ −1 1
,
2 2 ]
(b) f (x)=√ 9−x 2

For square root:

2
9−x ≥ 0 ⇒−3 ≤ x ≤3

Maximum value when x=0 :

f (0)=3

Minimum value:

f (± 3)=0

✅ Range

[ 0 , 3]

Q2. Composition of Functions

Given:
2
f (x)=x +5 x−7 , g( x )=7 x +8

(i) f ∘ g

f (g(x ))=f (7 x +8)¿ ¿¿ 49 x 2 +112 x+ 64+35 x +40−7f ∘ g=49 x 2 +147 x +97

(ii) g ∘ f
2 2
g(f ( x ))=g ( x +5 x−7)¿ 7(x +5 x−7)+8g ∘ f =7 x 2 +35 x−41

(iii) f ∘ f
2
f (f (x))=f (x +5 x−7)¿ ¿ f ∘ f =¿

Q3. Closures of Relation

Given:

A={1 , 2, 3 , 4 } R={(1, 2), (2 ,3),(3 , 4)}

(i) Reflexive Closure

Add all ( a , a )for a ∈ A :

{ (1 ,1),(2 ,2),(3 , 3),(4 , 4 ),(1, 2), (2 ,3),(3 , 4) }

(ii) Symmetric Closure

Add reverse of each pair:

{ (1 ,2),(2 ,1),(2 ,3),(3 , 2),(3 , 4),(4 ,3) }

(iii) Transitive Closure

Since:

¿¿¿{ (1 ,2),(2 ,3),(3 , 4 ),(1 , 3),(2 , 4),(1 , 4) }

Q4. Equivalence Relation

Definition

A relation is an equivalence relation if it is:

1. Reflexive

2. Symmetric

3. Transitive

Given:

A={1 , 2, 3 } R={(1, 1),(1, 2), (2 ,1) ,(2 ,2),(3 , 3)}

✔ Reflexive: All ( a , a )present

✔ Symmetric: ( 1 , 2 )and ( 2 , 1 )present
✔ Transitive: Closure satisfied

R is an equivalence relation

Q5. Poset (Divisibility)

X ={1 , 3 ,5 , 7 , 15 , 21, 35,105 }

(i) LUB of 3 and 7

lcm (3 , 7)=21 LUB=21

(ii) GLB of 15 and 35

gcd (15 , 35)=5GLB=5

(iii) Greatest and Least Element

Least element divides all → 1

Greatest element divisible by all → 105

Least = 1, Greatest = 105

Q6. Hasse Diagram

A={2 , 3 ,6 ,12 , 24 , 36 }

Divisibility order.

Minimal elements: 2, 3
Maximal elements: 24, 36

Q7. Transitive Closure (Warshall Algorithm)

A={1 , 2, 3 , 4 } R={(1, 2), (2 ,3),(3 , 4),(2 , 1)}

New pairs obtained:

¿ R+¿={(1 ,2),(2 ,3),(3 , 4),(2 ,1),(1 ,3),(2 ,4 ),(1, 4)}¿

Q8. Lattice

The lattice ( D12 ,∣ )is distributive.

But lattices formed by:

A={1 , 2, 3 , 5 ,30 }and B={1 ,2 , 3 ,5 , 30 }

under divisibility are not distributive, since meet and join do not satisfy distributive laws.

Hence, lattices A and B are not distributive Q9. Write short notes with example

(i) Distributive Lattice

A lattice ( L ,∨ , ∧) is called a distributive lattice if it satisfies the distributive laws:

a ∧(b ∨ c)=(a ∧ b)∨(a ∧ c)a ∨(b ∧ c)=(a ∨ b)∧(a ∨ c)

for all a , b , c ∈ L.

In a distributive lattice, meet distributes over join and join distributes over meet.

Example

The power set P(S)of a set Swith operations:

 Join = Union (∪)

 Meet = Intersection (∩)

forms a distributive lattice.

Hence, ( P( S), ∪ ,∩ )is a distributive lattice.

(ii) Bounded Lattice

A lattice ( L ,∨ , ∧) is called a bounded lattice if it has:

 A least element (0) such that 0 ≤ afor all a ∈ L

 A greatest element (1) such that a ≤ 1for all a ∈ L

Example

In the lattice ( P( S), ∪ ,∩ ):

 Least element = Ø (empty set)

 Greatest element = S

Hence, it is a bounded lattice.

(iii) Finite and Infinite Lattice

Finite Lattice

A lattice having a finite number of elements is called a finite lattice.

Example:

L={1 ,2 , 3 ,6 }

under divisibility forms a finite lattice.

Infinite Lattice

A lattice having infinitely many elements is called an infinite lattice.

Example:
The set of integers Z under usual ≤ relation forms an infinite lattice.

Q10. Write short notes

(i) Partial Order Relation

A relation R on a set A is called a partial order relation if it satisfies:

 1. Reflexive: (a ,a)∈ R

2. Antisymmetric: If ( a , b )and ( b , a )belong to R , then a=b

3. Transitive: If ( a , b )and ( b , c )belong to R , then (a ,c )∈ R

A set with a partial order relation is called a poset.

Example:
Divisibility relation on natural numbers.

(ii) Lattice

A lattice is a partially ordered set in which every pair of elements has:

 A least upper bound (join)

 A greatest lower bound (meet)

Lattice is denoted as ( L ,∨ , ∧) .

Example:
( P( S), ∪ ,∩ )is a lattice.

UNIT – III

Q1

(i) Three digit numbers using {0,2,3,4,5,6}

(a) Repetition allowed

 Hundreds place: 5 choices (0 not allowed)

 Tens place: 6 choices

 Units place: 6 choices

5 ×6 × 6=180

(b) Repetition not allowed

 Hundreds place: 5 choices

 Tens place: 5 choices

 Units place: 4 choices

5 ×5 × 4=100
(ii) Numbers between 100 and 1000 with distinct digits

 Hundreds place: 9 choices (1–9)

 Tens place: 9 choices

 Units place: 8 choices

9 × 9× 8=648

Q2. Formation of Words

(a) MATHEMATICS

Total letters = 11
Repeated letters: M(2), A(2), T(2)
11!
=4,989,600
2! 2 ! 2 !

(b) BANANA

Letters = 6
A(3), N(2)
6!
=60
3! 2!

(c) MISSISSIPPI

Letters = 11
M(1), I(4), S(4), P(2)
11!
=34,650
4! 4!2!

Q3. Committee Formation

Total persons = 6
Boys = 7, Girls = 5

(a) At least 1 girl

Total committees:
12
❑ C6

All boys:
7 12 7
❑ C 6¿❑ C 6−❑ C 6

(b) At most 4 girls

Girls = 0,1,2,3,4
Add all combinations.

(c) All girls

5
❑ C 6=0

(d) No girl
7
❑ C6

Q4. 5th and 11th term of ( 2 x+ 7 ¿15

General term:
15
T r+ 1=❑ C r ¿

5th term → r =4
11th term → r =10

Q5. General and Middle Term

( 5 x − 3 ¿8
General term:
8
T r+ 1=❑ C r ¿

Middle term:
Since n=8 , middle term =T (8/ 2)+1=T 5
Q6. Multinomial Expansion

( 2 x+ y+ z ¿10
General term:
10 !
¿
p! q!r!

where p+q +r=10

Coefficient of x 2 y 5 z 3
10 ! 2
2
2! 5 ! 3 !

Coefficient of x 3 y 7 z 4

Not possible since powers sum ≠ 10.

Q7. Explain

(i) Semigroup

A non-empty set with an associative binary operation.

Example:
¿

(ii) Monoid

A semigroup with identity element.

Example:
¿with identity 0.

Q8. Group under Multiplication

Set:

G={1 ,−1 ,i ,−i }

✔ Closure
✔ Associativity
✔ Identity = 1
✔ Inverse exists

Hence G is a group

Q9. Isomorphism

Define:

f : Z → n Z f (x)=nx

This mapping is:

 One–one

 Onto

 Operation preserving

Z≅ nZ

Q10. Explain

(i) Homomorphism

A mapping preserving operation:

f (a∗b)=f (a)∘ f (b)

(ii) Isomorphism

A bijective homomorphism is called an isomorphism.

Q1. Solve the recurrence relation

a n=a n−1 + 4 , n ≥ 2, a 1=5

Solution

This is a first-order linear recurrence relation.

Write terms:
a1 ¿5
a2 ¿ a1 +4=9
a3 ¿ a2 +4=13
a 4 ¿ a3 +4=17
This is an arithmetic sequence with:

 First term = 5

 Common difference = 4

General formula

a n=a1 +(n−1)da n=5+(n−1)4 a n=4 n+1

Q2. Solve the recurrence relation

a n=a n−1 +n , n> 1, a 1=2

Solution

Expand step by step:

a2 ¿ a 1+2=4
a3 ¿ a2+ 3=7
a 4 ¿ a3 +4=11

Write summation form:

n
a n=a1 + ∑ k
k =2

Sum of first nnatural numbers:

n
n(n+1)
∑ k=¿ 2
¿
k =1

So,
n
n(n+1) n(n+1) n(n+1)
∑ k=¿ 2
−1 ¿a n=2+
2
−1a n=
2
+1
k =2

Q3. Write notes

(a) Binomial Generating Function (BGF)

The binomial generating function of a sequence { an }is:

∞
G(x )=∑ a n x n
n=0

It is used to:
  Solve recurrence relations

 Study combinatorial sequences

Example:
For a n=1:

2 3 1
G(x )=1+ x+ x + x +⋯=
1−x

(b) Exponential Generating Function (EGF)

The exponential generating function is:

∞
xn
G(x )=∑ a n
n=0 n!

Used when:

 Order matters

 Counting permutations

Example:
For a n=1:
x
G( x )=e

Q4. Solve
a n=4 an−1−4 a n−2 , a1=1, a2=3

Solution

Assume solution a n=r n

Characteristic equation:

r −4 r + 4=0( r −2 ¿ =0
2 2

Repeated root: r =2

General solution
n
a n=(C 1 +C 2 n)2

Apply initial conditions:

For n=1:
 2(C 1+ C2 )=1

For n=2:

4 (C 1+ 2C 2)=3

Solve:
−1
C 1=1 ,C 2=
2

Final Answer

( n2 )2
a n= 1−
n

Q5. Solve

(i)
a n−9 a n−1+27 an−2−27 a n−3=0

Characteristic equation:

r −9 r + 27 r−27=0( r −3 ¿ =0
3 2 3

General solution
2 n
a n=(C 1 +C 2 n+C 3 n )3

(ii)
a n+ 6 an−1 +12 an−2 +8 a n−3 =0

Characteristic equation:

( r +2 ¿3 =0
General solution
2
a n=(C 1 +C 2 n+C 3 n )¿

Q6. Solve
a n−7 a n−1 +10 a n−2=0 , a0 =0 , a 1=3

Characteristic equation:
 r −7 r+ 10=0 (r −5)(r−2)=0
2

General solution
n n
a n=C 1 5 +C 2 2

Using conditions:

C 1+C 2=05 C1 +2 C 2=3C 1=1 , C 2=−1

Final Answer
n n
a n=5 −2

Q7. Solve
2
a n+ 5 an−1+ 6 an−2=3 n −2 n+1

Homogeneous part

(r +2)(r +3)=0a (nh )=C1 ¿

Particular solution

Assume:
(p) 2
a n =A n +Bn+C

Substitute and compare coefficients:

3 −2 1
A= , B= , C=
12 12 12

Final solution
a n=C 1 ¿

Q8. Solve
a n−5 an−1 +6 a n−2=1

Characteristic equation:

(r −2)(r−3)=0 a (nh )=C1 2n+ C2 3n

Particular solution (constant):

(p) 1
a n =A A=
2
Final Answer

n n 1
a n=C 1 2 +C 2 3 +
2

Q9. Generating Functions

Sequence Binomial GF Exponential GF

n 1 2x
2 e
1−2 x

n 1 5x
5 e
1−5 x

n 1 3x
3 e
1−3 x

2 x
Constant 2 2e
1−x

Q10. Solve
a n=15 an−1 +34 an−2 ,a 1=1 , a 2=3

Characteristic equation:

r −15 r −34=0r =17 , −2

2

General solution
n
a n=C 1 17 +C 2 ¿

Using initial conditions:

1 18
C 1= , C 2=
19 19

Final Answer
1 n 18
a n= 17 + ¿ Q1. Write notes on the following
19 19

(i) Planar Graph

A planar graph is a graph that can be drawn on a plane in such a way that no two edges
intersect or cross each other, except at their end vertices.

Key Points
  Edges meet only at vertices

 The drawing without crossings is called a planar embedding

 A planar graph divides the plane into regions called faces

Examples

 Triangle K 3

 Square

 Graph K 4 is planar

Non-planar graphs

 K 5(complete graph with 5 vertices)

 K 3 ,3 (complete bipartite graph)

(ii) Complete Graph

A complete graph is a simple graph in which every pair of distinct vertices is connected by
exactly one edge.

It is denoted by K n, where n is the number of vertices.

Properties

 Number of edges:

n(n−1)
2

 Every vertex has degree n−1

Example

 K 3: triangle

 K 4 : 4 vertices, 6 edges

(iii) Regular Graph

A regular graph is a graph in which every vertex has the same degree.

If each vertex has degree r , the graph is called an r-regular graph.

Examples
  Cycle graph C nis 2-regular

 Complete graph K nis ( n −1 ) -regular

Q2. Explain the following with examples

(i) Adjacency Matrix of a Graph

The adjacency matrix of a graph with n vertices is an n × nmatrix A=[aij ], where:

a ij= {
1 if vertex v i is adjacent to v j
0 otherwise

Example

Graph with vertices v 1 , v 2 , v 3

Edges: v 1 v 2 , v 2 v 3

[ ]
0 1 0
A= 1 0 1
0 1 0

(ii) Incidence Matrix of a Graph

An incidence matrix represents the relationship between vertices and edges.

If a graph has n vertices and m edges, the incidence matrix is an n × mmatrix.

a ij= {
1 if vertex v i is incident to edge e j
0 otherwise

Example

Vertices: v 1 , v 2 , v 3
Edges: e 1=v 1 v 2 , e 2=v 2 v 3

e1 e 2
0 ¿ v 2 ¿ 1 ¿1 ¿ v 3 ¿ 0 ¿ 1 ¿
v1 ¿

Q3. What is Chromatic Number? Find chromatic number of K 5and K 6

Chromatic Number

The chromatic number of a graph, denoted by χ (G), is the minimum number of colors
required to color the vertices of the graph such that no two adjacent vertices have the
same color.
Chromatic number of complete graph

For a complete graph K n:

χ (K n)=n

Answers

 χ (K 5)=5

 χ (K 6)=6

Reason: Every vertex is adjacent to every other vertex.

Q4. Chromatic number of a bipartite graph K m , n

A bipartite graph can be divided into two disjoint sets of vertices such that no edge joins
vertices within the same set.

Chromatic Number

χ (K m ,n )=2 for all m , n ≥1

Reason: One color for set m , one color for set n .

Q5. Algorithms to find Minimum Spanning Tree (MST)

(i) Kruskal’s Algorithm

Steps

1. Arrange all edges in increasing order of weight

2. Select the smallest edge

3. Add it if it does not form a cycle

4. Repeat until n−1edges are selected

Features

 Greedy algorithm

 Works well for sparse graphs

Example

Edges chosen in increasing order without forming cycles.

(ii) Prim’s Algorithm

Steps

1. Start from any vertex

2. Select the smallest edge connected to the tree

3. Add the vertex and edge

4. Repeat until all vertices are included

Features

 Greedy algorithm

 Suitable for dense graphs

Q6. Explain the following with example

(i) Depth First Search (DFS)

DFS explores a graph by going as deep as possible before backtracking.

Algorithm

1. Start from a vertex

2. Visit an unvisited adjacent vertex

3. Continue until no unvisited vertices

4. Backtrack

Example Traversal

A→B→D→E→C

(ii) Breadth First Search (BFS)

BFS explores vertices level by level.

Algorithm

1. Start from a vertex

2. Visit all adjacent vertices

3. Then visit their adjacent vertices

4. Uses a queue
Example Traversal

A→B→C→D→E

Q7. Write short notes on

(i) Euler Graph

A graph is an Euler graph if it contains a closed trail that includes every edge exactly once.

Condition

 All vertices have even degree

(ii) Hamiltonian Graph

A graph is Hamiltonian if it contains a Hamiltonian cycle, which visits each vertex exactly
once and returns to the starting vertex.

Example

 Complete graphs

 Cycle graphs

(iii) Multigraph

A multigraph is a graph that allows:

 Multiple edges between same vertices

 Self-loops

Example

Two cities connected by multiple roads.