Free Website Builder: Create free websites | Webs



VINAYAKA MISSIONS UNIVERSITY, INDIA

VINAYAKA MISSION’S KIRUPANANDA VARIYAR ENGINEERING COLLEGE

SALEM – 636308.

DISCRETE MATHEMATICS

(Common to:CSE AND CSSE)

Fifth Semester

Academic Year - 2011-2012

Batch: 2009 – 2013

QUESTION BANK

UNIT I

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 [pic]

8.Construct the truth table for [pic]

9.Show that [pic] is Tautology?

10.Construct the truth table for [pic]

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 [pic] is tautologically implied by [pic]

Part B

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

(ii) Construct the truth table for [pic] (6 Marks)

2 (i) Show that [pic] (6 Marks)

(ii) Prove that [pic] [pic] (6 Marks)

3(i) Obtain the DNF of [pic] (6 Marks)

(ii) Obtain the CNF of [pic] (6 Marks)

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

5. (i) Obtain the PDNF of [pic] (6 Marks)

(ii) Obtain the PCNF of [pic] (6 Marks)

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

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

[pic] (5Marks) (ii) Prove that [pic] is tautologically implied by

[pic] (7 Marks)

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

[pic] (6 Marks)

(ii) Prove by indirect method, [pic] (6 Marks)

9.(i)Prove that [pic] 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)[pic]

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

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) [pic]

12.Show that [pic]

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) [pic] (ii) [pic]

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

PART B

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

[pic]

(ii) Show that [pic] (6 Marks)

2. (i) Prove that [pic] (6 Marks)

(ii) Prove that [pic] follows logically the premises

[pic] and [pic] (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)

(c) R(1,4) (d) R(16,2) (6 Marks)

(ii) Show that [pic]

(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 [pic] follows logically from [pic]and

[pic] (4 marks)

5.Prove that [pic],[pic]

(12 marks)

6.Prove the derivation [pic],[pic], [pic] (12 marks)

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

(ii) Show that [pic] (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 [pic] (12 marks)

10.Show that [pic] follows logically from:

(a) [pic]

(b) [pic] (12 marks)

[pic]

[pic]

[pic]

UNIT III

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 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download