Vinayaka Missions University, India

VINAYAKA MISSIONS UNIVERSITY, INDIA

VINAYAKA MISSION’S KIRUPANANDAVARIYARENGINEERINGCOLLEGE

SALEM – 636308.

DISCRETE MATHEMATICS

(Common to:CSE AND CSSE)

Fifth Semester

Academic Year - 2011-2012

Batch: 2009 – 2013

QUESTION BANK

UNITI

Propositional Calculus

Part A

1.Define Proposition.

2.Define Atomic statement, What are the possible truth values for this statement. Define compound statement.

3.Define connectives.

4.Define truth table.

5.Define disjunction.

6.Write about Molecular and Conditional statement.

7Construct the truth table for

8.Construct the truth table for

9.Show that is Tautology?

10.Construct the truth table for

11.Define Tautology,Contradiction,Contingency.

12.Define equivalence.

13.Define Tautological implication.

14.Define Dual of a statement formula.

15.Define Elementary Sum and Product.

16.Define Disjunctive Normal Forms.

17.Define Conjunctive Normal Forms.

18.Define Minterms with example.

19.Define Maxterms with example.

20.Define Principal Disjunctive Normal Form.

21.Define Principal Conjunctive Normal Form.

22.Write about the Implication Rules.

23.Define Consistency and Inconsistency of Premises.

24.What is inference theory?

25.Show that is tautologically implied by

Part B

1. (i)Construct the truth table for (6 Marks)

(ii) Construct the truth table for (6 Marks)

2 (i) Show that (6 Marks)

(ii) Prove that (6 Marks)

3(i) Obtain the DNF of (6 Marks)

(ii) Obtain the CNF of (6 Marks)

4. Without using truth table obtain the PCNF and PDNF of the formula (12 Marks)

5. (i) Obtain the PDNF of (6 Marks)

(ii) Obtain the PCNF of (6 Marks)

6 . Obtain the DNF and CNF for (12 Marks)

7.(i) Show that logically follows from the premises

(5Marks) (ii) Prove that is tautologically implied by

(7 Marks)

8. (i) Prove that follows logically from the Premises

(6 Marks)

(ii) Prove by indirect method, (6 Marks)

9.(i)Prove that are inconsistent. (6 marks)

(ii)Check the following set of premises are inconsistent.

(1) If Tharun gets his degree, he will go for a job.

(2) If he goes for a job. He will get married soon.

(3) If he goes for higher study, he will not get married.

(4) Tharun gets his degree and goes for higher study. (6 marks)

10.(i)Show the following argument is valid.

Father praises Yashwanth only if Yashwanth can be proud of himself. Either Yashwanth do well in sports or Yashwanth cannot be proud of himself. If study hard, then Yashwanth cannot do well in sports. Therefore, if father praises Yashwanth, then Yashwanth do not study well. (6 marks)

(ii)Derive using the rule CP if necessary, from (6 marks)

UNIT II

PREDICATE CALCULUS

PART A

1.Define 1 – place predicate

2.Define 2 – place predicate

3.Define 3- place predicate

4.Define 4- place predicate

5.Define n – place predicate

6.Define Universal Quantifier

7.Define Existential quantifier

8.Let M(x) : x is a mammal

W(x) : x is warm blooded

Translate into formula: Every mammal is warm blooded

9.Let G(x,y) : x is taller than y

Translate the following into formula

For any x and any y if x is taller than y then it is not true that y is taller than x.

10. Define free and bound variables.

11.Let P(x): x=x2 be the statement. If the universe of discourse is the set of integers, what are

the truth values of (a) P(-1) (b)

12.Show that

13.Define universally valid statement.

14.Define existentially valid statement.

15.Explain the rule “Existential Generalisation”.

16.What are the two types of Quantifiers.

17.Symbolise the expression ”Every city in India is clean”.

18.Explain the rule “Existential Specification”.

19.Explain the rule “Universal Generalisation”.

20.Explain the rule “Universal Specification”.

21.Symbolise the expression “ x is the father of the mother of y”.

22.Express in symbolized notation “ All world loves a lover”.

23.Symbolise the following expression” For any given positive integer, there is a greater positive integer”.

24.Let A={1,2,3,4,5,6}. Determine the truth value of each of the following:

(i) (ii)

25.Let A={1,2,3,4,5,6}. Determine the truth value of

PART B

1 . (i) Show that Find the truth value of with P(x): x = 1, Q(x): x = 2 and the universe of discourse is A = {1,2}. (6 Marks)

(ii) Show that (6 Marks)

2. (i) Prove that (6 Marks)

(ii) Prove that follows logically the premises

and (6 Marks)

3.(i) Let P(x): x is an even integer and R(x,y): x is divisible by y. Let the universe of discourse be the set U= {1,2,4,8,16,32}. Find the truth values of the following (a) P(16) (b) P(4)

(ii) Show that

(6 marks)

4.(i)Test the validity of the following argument:

If an integer is divisible by 10 then it is divisible by 2. If an integer is divisible by 2, then it is divisible by 3. The integer divisible 10 is also divisible by 3. (8 marks)

(ii) Show that follows logically from and

(4 marks)

5.Prove that ,

(12 marks)

6.Prove the derivation ,, (12 marks)

7.(i) Express “ is an irrational number” using quantifiers. (6 marks)

(ii) Show that (6 marks)

8.(i) Verify the validity of the following argument:

Lions are dangerous animals. There are lions. There are dangerous animals. (6 marks)

(ii) Show that the premises “ one student in this class knows how to write programs in JAVA” and “ everyone who knows how to write programs in JAVA can get a high-paying job” imply the conclusion” someone in this class can get a high-paying job”. (6 marks)

9.Prove that (12 marks)

10.Show that follows logically from:

(a)

(b) (12 marks)

UNITIII

COMBINATORICS

Part A

01. How many words of three distinct letters can be formed from the letters of the

word ‘MASTER’.

02. How many different words are there in the word MATHEMATICS?

03. State the principle of Mathematical induction.

04. Using Mathematical induction, prove that n<2n

05. State Pigeon hole principle.

06. In how many ways can 9 people be seated in a circle?

07. If 13 people are assembled in a room, show that atleast 2 of them must have their

birthday in the same month.

08. Find the generating function of the following sequence

09. Explain generating function with example.

10. Find the recurrence relation for the recurrence s(k) =2k+9 ?

11. How many different bit strings are there of length nine?

12. A coin is tossed four times and the result of each toss is recorded. How many different

sequences of heads and tails are possible?

13. Compute the number of distinct 13 card hands that can be dealt from a deck of 52 cards.

14. Find the minimum number of students need to guarantee that five of them belong to the

same subject , having the majors as physics, chemistry, mathematics and history.

15. Among 100 people, show that atleast 9 of them were born in the same month?

16. Find the generating function for the sequence 1,2,3,4,5?

17. Find the recurrence relation and basis for the sequence of

18. The sequence is given by . Find the recurrence relation?

19. Write the characteristic equation of

20. Show that if seven colors are used to paint 50 bicycles atleast 8 bicycles will be the same

color.

21. Show that if 30 dictionaries in a library contain a total of 61,327 pages, then one of the

dictionaries must have atleast 2045 pages.

22There are 18 Mathematical major and 143 Computer Science students in a college. How

many ways are their to pick one of the students who is either Mathematics major or

Computer Science major. .

23. Show that if any eleven numbers from 1 to 20 are chosen, then two of them will add

upto 21.

24. How many teams of six with a captain can be selected from 12 persons?

25. How many numbers from 1 to 10,000 have digit sum of 7?

Part B

1 (i) Using Mathematical induction method, Prove that

r = (6Marks)

(ii)Using Mathematical induction method, Prove that

(6 Marks)

2 (i) Using Mathematical induction to prove that

1+2+22+ ……..+ = 2n+1-1. (6 Marks)

(ii) Let p(n) = 8n – 3n be a multiple of 5. Prove that p(n) is a tautology.(n

(6 Marks)

3 (i) State and prove the Pigeon hole principle. (6 Marks)

(ii) Show that if n Pigeons are assigned to m Pigeon holes, then one of the

Pigeon must contain at least + 1 Pigeons. (6 Marks)

4. Find the number of integers between 1 and 250 both inclusive that are not divisible by

any of the integers 2,3,5 and 7

. (12 Marks)

5 (i) How many positive integers not exceeding 1000 are divisible by 7 or 11?. (4 Marks)

(ii) State and Prove the Principle of inclusion – exclusion using mathematical induction.

(8 Marks)

6. Solve the recurrence relation f(n) – 8f(n-1) + 16f(n-2) = 0;

Where f(2) = 16, f(3) = 80. (12 Marks)

7. Find the generating function of Fibonacci sequence

F(n) = F(n-1) + F(n-2) , with F(0) = F(1) = 1. (12 Marks)

8. (i) Solve the recurrence relation

S(k) – 7S(k-1) + 6S(k-2) = 0 , for, S(0) = 8, S(1) = 6. (8 Marks)

(ii)Define recurrence relation and find characteristic equation of

S(k) – 10S(k-1) + 9S(k-2) = 0, (4 Marks)

9. Solve the following recurrence relation

S(k) – 5S(k-1) + 6S(k-2) = 2, with S(0) = 1, S(1) = -1. (12 Marks)

10. Solve : S(k) + 5S(k-1) + 6S(k-2) = 3k2 – k + 1. (12 Marks)

UNIT IV

GROUPS

Explain the term semi group with an example.
Explain the term monoid with an example.
Find the identity element of the group of integers with the binary operation defined

by .

Explain the term a Permutation group.
Prove that is a generator of G if a is generator of a cyclic group G?
Explain the term Kernal of the homomorphism.
Show that in a group if for any , then must be abelian.
State any two properties of a ring.
Define ring with unity?
Explain the term field with an example.

11. Show that the set of integer Z with addition as an operation (Z.+) is monoid

12. Prove that if ‘a’ is a generator of a cyclic group G, then is also a generator of G.

13. Verify that (Q,+) is monoid where Q is the set of all rational numbers under usual

addition.

14. Write a short note about semigroup homomorphism

15. What is monoid homomorphism?

16. Prove that if G is a finite group and then .

17. If ,find ?

18. Define normal sub-group?

19. Define commutative ring?

20. Prove that every group of prime order is cyclic

21. How many generators are there in a cyclic group of order 10?

22. What is integral domain?

23. Define field by using ring?

24. What is ring and give an example of a ring with zero devisors?

25. Define zero divisor of a ring?

Part B

1(i) Prove that for any commutative monoid (m,*) , the set of idempotent elements of M

forms a sub monoid. (6 Marks)

(ii)Let (G, * ) be a finite group generated by an element aG . If G is of order n,

Prove that an = e and G = {a,a2,…. an = e } where n is the least positive integer for

which an = e. (6 Marks)

2. Prove that every finite group of order n is isomorphic to a permutation group of degree n.

(12 Marks)

3. Prove that if G be a group and N be the normal subgroup of G then is a group.

(12Marks)

4.(i) Prove that the Kernel of a homomorphism ‘f ’ from group (G,*). to a group

is a sub group of (G,*).(6 Marks)

(ii) Show that Every Cyclic group is abelian. (6 Marks)

5.Prove that a subset of G is a subgroup of iff for any (12 Marks)

6. State and Prove that Lagrange’s Theorem. (12 Marks)

7. State and Prove Fundamental Theorem on homomorphism of groups or if f is a

homomorphism of G onto with Kernal K, then . (12Marks)

8. Prove that every subgroup of a cyclic group is cyclic. (12 Marks)

9. (i) Prove that the following, Let (R, +, . ) be a ring , then for all a R. (6 Marks)

(i) a.0 = 0.a = 0 (ii) a.(-b) = (-a).b = -(a.b)

(iii) a.(b-c) = (a . b) – (a .c)

(ii) Prove that the order of an element divides the order of the group (6 Marks)

10. Show that is a cyclic group of n th roots of unity under multiplication. (12 Marks)

UNITV

LATTICES

Part A

01. Explain the term Poset.

02. Explain the term totally ordered set with an example.

03. Define distributive lattice?

04. Let X = {2,3,6,12,24,36} and the relation less than or equal to be such that x y if

x divides y . Draw the Hasse diagram of (x, ).

05. Explain the term a Lattice with an example.

06. Define Sub lattice?

07. Explain the term Boolean algebra.

08. Write any two Boolean identities.

09. Find the values of the following Boolean expressions.

10. Solve the following in any Boolean algebra.

11. Prove that if the least element and greatest element in a poset exist then they are

unique.

12. Define dual lattice.

13. Write any two properties of algebraic lattices?

14. Draw the diagram for, and be a relation such that

15. Give an example for Hasse diagram in lattices

16. Write the properties of algebraic lattices

17. What is bounded lattices?

18. Write a short note about lattice homomorphism.

19. What is order isomorphic?

20. Explain the term modular in lattices?

21. What is a complete lattice?

22. Write two properties of Boolean algebra?

23. Write De morgan’s law and absorption laws hold in a Boolean algebra?

24. Show that in any Boolean algebra.

25. Show that the absorption laws are valid in a Boolean algebra.

Part B

(i) Let (L, ) be a lattice. For any a, bL, if and only if if and only

if (6 Marks)

(ii) Every finite Lattice is bounded (6 Marks)

2. Prove that any Chain is Moduler(12 Marks)

3. Prove that every chain is a distributive lattice. (12 Marks)

4. Let ( ) be a distributive lattice and then Show that if

and , then (12 Marks)

5. If ( ) is a complemented distributive lattice , then the De Morgan’s Laws are valid and , (12 Marks)

6. Show that De Morgan’s Laws hold is a Boolean Algebra. Ie, and

(12 Marks)

7. (i) Find the value of (8 Marks)

(ii) Show that (4 Marks)

In Boolean Algebra Show that following

(i) if and only if (4 Marks)

(ii) (4 Marks)

(iii) (4 Marks)

9. With the use of Boolean Sum and Boolean Product Verify

(i) and (identity law) (2 Marks)

(ii) and ( De Margon’s Law) (4 Marks)

(iii) and (distributive Law) (6 Marks)

10i) Show that (4 Marks)

(ii)Prove or disprove (8 Marks)