Discrete Mathematics: A. Recursion
Discrete Mathematics: A. Recursion
Discrete Mathematics: A. Recursion
K1 Level Questions
UNIT I
UNIT II
Unit III
11. Which of the following statements is the negation of the statements “4 is odd or -9 is
positive”?
a) 4 is even or -9 is not negative
b) 4 is odd or -9 is not negative
c) 4 is even and -9 is negative
d) 4 is odd and -9 is not negative
12. Which of the following represents: ~A (negation of A) if A stands for “I like badminton
but hate maths”?
a) I hate badminton and maths
b) I do not like badminton or maths
c) I dislike badminton but love maths
d) I hate badminton or like maths
13. The compound statement A v ~(A ∧ B) is always
a) True
b) False
c)Tautology
d)not a tautology
14. Which of the following are De-Morgan’s law
a) P ∧ (Q v R) Ξ ( P ∧ Q ) v ( P ∧ R )
b) ~(P ∧ R) Ξ ~P v ~R , ~(P v R) Ξ ~P ∧ ~R
c) P v ~P Ξ True , P ∧ ~P Ξ False
d) None of the mentioned
15. What is the dual of (A ∧ B) v ( C ∧ D) ?
a) (A V B) v ( C v D)
b) (A V B) ^ ( C v D)
c) (A V B) v ( C ∧ D)
d) (A ∧ B) v ( C v D)
Unit IV
1. If P is always against the testimony of Q ,then the compound statement P→(P v ~Q) is a
a) Tautology
b) Contradiction
c) Contingency
d) None of the mentioned
2. Propositional logic uses symbols to stand for statements and..
a. Nonstatements
b. The relationships between subject and predicate
c. Truth values
d. The relationships between statements
a. p→q
b. p&q
c. pvq
d. ~p
4. In a disjunction, even if one of the statements is false, the whole disjunction is still...
a. False
b. Negated
c. True
d. Both true and false
5. In a conditional statement, the first part is the antecedent and the second part is the...
a. Predicate
b. Consequent
c. Subject
d. Disjunct
a. Contradiction
b. Disjunctive syllogism
c. Modus tollens
d. Tautology
7. In a truth table for a two-variable argument, the first guide column has the following truth
values:
a. T, T, F, F
b. F, F, T, T
c. T, F, T, F
d. T, F, F, F
8. In using the short method, your overall goal is to see if you can...
a. Show that all the statements of the argument are true
b. Prove invalidity in the most efficient way possible
c. Prove validity in the most efficient way possible
d. Prove that the conclusion is false
a. pvq
b. p→q
c. p*q
d. p&q
a. A negation
b. The conjunct
c. The consequent
d. The antecedent
a. A true conclusion
b. A negated conclusion
c. A conditional
d. A false conclusion
14. The special variables T and F are called -------- of each other.
a. Duals
b. Ordered pairs
c. Truth values
d. Both a and c
15. A sum of elementary products is called---------
a. disjunctive normal form
b. PDNF
c. PCNF
d. Both b and c
16. A product of elementary sums is called -------------
a. conjunctive normal form
b. PCNF
c. PDNF
d. none
17. Disjunctions of minterms is known as ----------Principal disjunctive normal form
a. DNF
b. CNF
c. PDNF
d. PCNF
Unit V
1. If aRa for all a,b belongs to R then it is called ----------
a. Reflexive
b. Transitive
c. Anti-symmetric
d. symmetric
2. If aRb implies bRa for all a, b belongs to R then the relation is called -------------
a. Reflexive
b. Transitive
c. Anti-symmetric
d. symmetric
3. If aRb and bRa implies a = b for all a, b belongs to R then the relation is called -----------
a. Reflexive
b. Transitive
c. Anti-symmetric
d. symmetric
4. If aRb implies bRc implies aRc for all a, b belongs to R then the relation is called --------
a. Reflexive
b. Transitive
c. Anti-symmetric
d. symmetric
Answer: A procedure that contains a procedure call to itself is known as Recursion procedure
A function is said to be One to one if and only if f(a) = f(b) implies that a = b for all a and
b in the domain of f.
8. What is the Cartesian product of A = {1, 2} and B = {a, b}?
ANSWER: {(1, a), (2, a), (1, b), (2, b)
9. What is the rank, in direct insertion order, of the permutation 5, 4, 6, 3, 2,
1? ANSWER: 717
10. Find the roots of the equations a2-8a+16=0
a. 4,4
UNIT II
1. What is solving the relation
The process of finding a closed from expression for the terms of a sequence from its recurrence
relation is called solving the relation
2. Define Closed form
The process repeated for finding S(K) is called Closed form
3. Define Sequence of integers
A function from N into Z is called Sequence of integers
4. Define Discrete Function
A sequence of integers are called discrete function
5. Define Initial condition
The terms not defined by the formula are said to form the Initial conditions
6. Define Discrete relation
The linear recurrence relation with constant co efficient is simply called Discrete relation
7. Find the order of D(K)-3D(K-1)=0
ANSWER: 1
8. Find the degree C(K) – 5C(K-1) + 6 C(K-2)= 2K-7
ANSWER: 2
9. Find the order of S(K)-4S(K-1)-11S(K-2)+30S(K-3)=4K
ANSWER: 3
10. Find the roots of the equations a2+10a+9=0
ANSWER: 1, 9
UNIT III
UNIT IV
1. Define Tautology.
3. In a conditional statement, what is the name of the first part of the statement?
antecedent
4. In a conditional statement, what is the name of the first part of the statement?
Consequent
5. In a truth table for a two-variable argument, What are the truth values of first guide column ?
T, T, F, F
UNIT V
1. What is the condition for reflexive?
If aRa for all a,b belongs to R then it is called Reflexive
2. How to define symmetric condition in relation?
If aRb implies bRa for all a, b belongs to R then the relation is called symmetric
3. How to define anti-symmetric condition?
If aRb and bRa implies a = b for all a, b belongs to R then the relation is called
Anti-symmetric
4. If aRb implies bRc implies aRc for all a, b belongs to R then the relation is called:
Transitive
5. If R satisfies reflexive, anti-symmetric and transitive then it is called--------
Partial order relation
6. If R satisfies reflexive, symmetric and transitive then it is called--------
Equivalence relation
7. If a poset satisfies either a<=b or b<=a then it is called ----------
Total order
8. Define Lattice.
Both LUB and GLB are exists for a poset then it is called Lattice
9. What is the name of a graphical representation of poset.
Hasse diagram
K3 Level Questions
UNIT I
Unit II
UNIT III
Unit IV
1. Verify whether (p ∨ q) → p is a tautology
2. Verify whether (p ∨ q) → r is a contradiction or tautology.
3. Using truth table prove that q ⇒ p → q.
4. Write any four logical identities with truth table.
5. Using replacement process show that (Z → ∧ Z → ) ⟺ (Z ∨ → )
6. By replacement process show that q ∨ (p ∧ ~ q) ∨ (~p ∧ ~ q) is a tautology.
7. Write the procedure to obtain a disjunctive normal form of a formula.
8. Define DNF and CNF with example.
9. Obtain a DNF of p → ((p → q) ∧ ~ (~ q ∧ ~ p)
10. Obtain a CNF of p → ((p → q) ∧ ~ (~ q ∧ ~ p).
Unit V
Unit IV
Unit V
1. Prove that ( L× M, ∧,∨) is a lattice.
2. Draw the Hasse diagram for the lattice P({1,2,3,4},⊆).
3. Prove: Every distributive lattice is modular.
4. Prove: Every chain is distributive lattice.
5. Show that the direct product of any two distributive lattices is a distributive lattice.