ASSIGNMENT
1. Solve the following nonlinear recurrence relations.
1 1 3 2 4 6 2 0
2. Let a) 𝐴 = [ ] b) 𝐴 = [ ] c) 𝐴 = [ ], d) 𝐴 = [ ] then find An
1 0 1 4 1 5 1 3
3. Solve the following divide and conquer relations
4. Prove that the following are tautologies
5. Determine whether each of the following inference is valid or invalid
6. Prove that [{~ r → (s → ~ t)} (~ r w) (~ p → s) ~ w] → (t → p).
7. Verify that the following argument is valid by using the rules of inference
If Clifton does not live in France, then he does not speak French
Clifton does not drive a Ford
If Clifton lives in France, then he rides a bicycle
Either Clifton speaks French, or he drives a Ford
Hence, Clifton rides a bicycle.
8. Prove or disprove the validity of the following argument using the rules of inferences
If Ram is irregular, then he fails in the examination
If Ram fails in an examination, then he is uneducated
If Ram reads a lot of books, then he is not uneducated
Hence, Ram is irregular and reads a lot of books
9. Prove or disprove the validity of the following argument using the rules of inferences
If I like Discrete Mathematics, then I will study
Either I don’t study or I pass Discrete Mathematics
If I don’t graduate, then I don’t pass Discrete Mathematics
Hence If I graduate, then I studied.
10. Prove or disprove the validity of the following argument
a. Students of average intelligence can do arithmetic
A student without average intelligence is not a capable student
Your students cannot do arithmetic
Therefore, your students are not capable
b. If there is a man, who is a Teacher, then all Scientists are Engineers
There is a Scientist who is not an Engineer.
Hence, all men are not Teachers.
c. Every living thing is a plant or an animal.
David’s dog is alive and it is not a plant.
All animals have hearts.
Hence, David’s dog has a heart
d. If there is an integer, which is a powers of 3, then all multiples of 3 are odd numbers.
There is a multiple of 3 which is not an odd number.
Hence, all integers are not powers of 3.
e. Babies are illogical
Nobody is despised who can manage crocodile
Illogical people are despised
Hence, babies cannot manage crocodiles.
11. Show that from (x) (f(x) s(x)) → (y)(m(y) → w(y)), (y) (m(y) ~ w(y)) the conclusion (x)(f(x)
→ ~ s(x)) follows.
12. Obtain disjunctive normal form of p → (( p → q) ~(~q v ~p))
13. Obtain Principal conjunctive normal form of (~p → r) (q p)
14. Find pdnf and pcnf for the formula (p q) v (~p q) v (q r)
15. Find PDNF from PCNF of p v (~p → (q v ( ~q → r)))
16. Using Warshalls algorithm, compute the adjacency matrix of the digraph G=({a,b,c,d,e} {(a,b), (b,c),
(c,d), (d,e), (e,d)})
17. Compute the adjacency matrix of R+ using Warshall Algorithm
18. Let R be a reflexive relation on a set A. Show that R is an equivalence relation if and only if aRb and
aRc imply that bRc
19. Let R and S be two equivalence relations on a set A. Show that RS is an equivalence relation but that
RS need not be an equivalence relation
20. Define the relation R on the set A of positive integers by aRb if and only if a/b can be expressed in the
form 2m, where m in an arbitrary integer. Prove that R is an equivalence relation and determine the
equivalence class under R
21. Show that the relation R on he set Z of all integers is an equivalence relation where R is defined as aRb
if and only inf a2 – b2 is an integral multiple of 2. Find the equivalence classes determined by R
22. Define a relation R on the set Z of all integers by aRb if and only if a2 b2 mod7. Show that R is
equivalence relation on Z. Determine the number of equivalence classes.