DM - IMPORTANT QUESTIONS [PART – B]
UNIT 1
1 Show that (( P Q¿ (P (Q R ) )¿( P Q)(P R) is a tautology by using equivalences.
2 Find the PDNF and PCNF of the formula P∨(¬P→(Q∨(¬Q→R)))
3 Prove that √ 2is irrational by giving a proof by contradiction.
4 Showthat the premises” A student in the class has not read the book ”and ”Everyone
in this class passed the semester exam” imply the conclusion ”Some one who passed
the semester exam” has not read the book”.
5 When do we say a formula is tautology or contradiction? Without constructing truth
Table, verify whether QP¬Q¬P¬Q
6 Is a contradiction or tautology. Justify your answer.
Prove that(PQ)(QR) (PR)
7 show that (pq)(rs),(qt)(su),(tu) and (pr)p
8 Prove that (x)(p(x)q(x))(x)p(x)(x)Q(X)
9 Show that (x)(P(x)→ Q( x)¿( x )(Q(x) → R (x))≡( x)(P ( x)→ R(x ))
10 Showthat “one student in class knows how to write program in java” and “ everyone
who knows how to write program in java can get a high paying job “ imply the
conclusion “ someone in this class can get the high paying job”.
11 Without constructing the truth table obtain the product of sums canonical form of
the formula:( PR) (QP). Hence find the sum of product canonical form.
12 Show that (PQ) (QR) (PR) is a tautology.
UNIT 2
1 Solve the recurrence relation
an=2(an−1−an−2),wheren≥2anda0=1,a1=2
2 prove that 8 n−3n is a multiple of 5 using mathematical induction
3 Find an explicit formula for the Fibonacci sequence.
4 Determine the number of positive integers n,
1 ≤n ≤2000 that are not divisible by 2,3, or 5 but are divisible by 7.
5 Solve D(k) – 7D(k-2)+6D(k-3) = 0 where D(0) = 8, D(1)=6, and D(2) =22
6 Solve the recurrence relation a n−7 a n−1 +10 a n−2 = 0 for n ≥ 2 given that a0 = 10, a1 = 41
using generating functions
7 Find the number of integers between 1 to 250 that are not divisible by any of integers 2, 3,
5 and 7.
+
8 3
Use mathematical induction to show that n -n is divisible by 3 ,for n∈Z
9 Prove that 1/ √ 1+1 / √ 2+… ..+1/√ n ≥ √ n for n ≥ 2using principle of mathematical
induction
UNIT 1
1 Show that (( P Q¿ (P (Q R ) )¿( P Q)(P R) is a tautology by using equivalences.
2 Find the PDNF and PCNF of the formula P∨(¬P→(Q∨(¬Q→R)))
3 Prove that √ 2is irrational by giving a proof by contradiction.
4 Showthat the premises” A student in the class has not read the book ”and ”Everyone
in this class passed the semester exam” imply the conclusion ”Some one who passed
the semester exam” has not read the book”.
5 When do we say a formula is tautology or contradiction? Without constructing truth
Table, verify whether QP¬Q¬P¬Q
6 Is a contradiction or tautology. Justify your answer.
Prove that(PQ)(QR) (PR)
7 show that (pq)(rs),(qt)(su),(tu) and (pr)p
8 Prove that (x)(p(x)q(x))(x)p(x)(x)Q(X)
9 Show that (x)(P(x)→ Q( x)¿( x )(Q(x) → R (x))≡( x)(P ( x)→ R(x ))
10 Showthat “one student in class knows how to write program in java” and “ everyone
who knows how to write program in java can get a high paying job “ imply the
conclusion “ someone in this class can get the high paying job”.
11 Without constructing the truth table obtain the product of sums canonical form of
the formula:( PR) (QP). Hence find the sum of product canonical form.
12 Show that (PQ) (QR) (PR) is a tautology.
UNIT 2
1 Solve the recurrence relation
an=2(an−1−an−2),wheren≥2anda0=1,a1=2
2 prove that 8 n−3n is a multiple of 5 using mathematical induction
3 Find an explicit formula for the Fibonacci sequence.
4 Determine the number of positive integers n,
1 ≤n ≤2000 that are not divisible by 2,3, or 5 but are divisible by 7.
5 Solve D(k) – 7D(k-2)+6D(k-3) = 0 where D(0) = 8, D(1)=6, and D(2) =22
6 Solve the recurrence relation a n−7 a n−1 +10 a n−2 = 0 for n ≥ 2 given that a0 = 10, a1 = 41
using generating functions
7 Find the number of integers between 1 to 250 that are not divisible by any of integers 2, 3,
5 and 7.
+
8 3
Use mathematical induction to show that n -n is divisible by 3 ,for n∈Z
9 Prove that 1/ √ 1+1 / √ 2+… ..+1/√ n ≥ √ n for n ≥ 2using principle of mathematical
induction
