WordPress.com



DISCRETE MATHEMATICS

UNIT – I LOGIC AND PROOFS

PART - A

1. Write down the two propositions P and Q for which Q[pic] P is true

but P[pic]Q is false.

Sol. When Q is false and P is true, we get Q[pic] P is true and P[pic]Q is false.

P: New Delhi is capital of India

Q: 4 is an odd number.

2. State the truth value of “If tigers have wings then the earth travels

round the sun”.

Sol. Let P: Tigers have wings have truth value F

Q: The earth travels round the sun have truth value T

Therefore, P[pic]Q has the truth value T.

3. Construct truth table for (P[pic]Q) [pic](P[pic]Q).

Sol.

|P |Q |P[pic]Q |P[pic]Q |(P[pic]Q) [pic](P[pic]Q) |

|T |T |T |T |T |

|T |F |F |F |T |

|F |T |T |F |F |

|F |F |T |F |F |

4. Prove that (P[pic]Q) [pic]((P[pic]Q) is a contradiction.

Sol.

|P |Q |P[pic]Q |P[pic]Q |((P[pic]Q) |(P[pic]Q) [pic]((P[pic]Q) |

|T |T |T |T |F |F |

|T |F |F |T |F |F |

|F |T |F |T |F |F |

|F |F |F |F |T |F |

[pic](P[pic]Q) [pic]((P[pic]Q) is a contradiction.

5. Give an example of tautology and contradiction.

Sol. P[pic]((P) is a tautology and P[pic]((P) is a contradiction.

6. Prove that (P[pic]Q)[pic] (P[pic](Q is a tautology.

Sol.

|P |Q |(P |(Q |P[pic]Q |((P[pic]Q) |(P[pic](Q |(1) [pic](2) |

| | | | | |(1) |(2) | |

|T |T |F |F |T |F |F |T |

|T |F |F |T |T |F |F |T |

|F |T |T |F |T |F |F |T |

|F |F |T |T |F |T |T |T |

Since (1) [pic](2) are all true, ((P[pic]Q)[pic] (P[pic](Q is a tautology.

7. Prove that P[pic] Q [pic](P[pic]Q

Sol.

|P |Q |(P |P[pic]Q |(P[pic]Q |(1) [pic](2) |

| | | |(1) |(2) | |

|T |T |F |T |T |T |

|T |F |F |F |F |T |

|F |T |T |T |T |T |

|F |F |T |T |T |T |

Since (1) [pic](2) are all true, it is tautology.

[pic] (1) [pic](2)

(i.e) P[pic]Q [pic](P[pic]Q

8. Prove that P[pic](Q[pic]R) [pic]( P[pic]Q) [pic]R.

Sol. P[pic](Q[pic]R) [pic]P[pic](7Q[pic]R)

[pic]7P[pic](7Q[pic]R)

[pic](7P[pic]7Q) [pic]R

[pic]7(P[pic]Q) [pic]R

[pic](P[pic]Q) [pic] R.

9. Find the converse and contrapositive of the implication

“If it is raining then I get wet.”

Sol. Let P : It is raining and Q : I get wet

Then the given statement is P[pic]Q .

The converse of P[pic]Q is Q[pic]P

The contrapositive of P[pic]Q is (Q [pic](P

10. Prove that (Q [pic]( P[pic]Q) [pic] (P

Sol. Assume (Q [pic]( P[pic]Q) is true.

(i.e) Both (Q and P[pic]Q is true

If (Q is true then Q is false.

and P[pic]Q is true, when P is false and Q is false.

(i.e) P is false

Hence (P is true.

11. Define functionally complete set of connectives and give an example.

Sol. A set of connectives in which every formula can be expressed in

terms of an equivalent formula containing the connectives from

this set is called functionally complete set of connectives.

Eg : P[pic]Q [pic] (P[pic]Q) [pic](Q[pic]P)

[pic]((P[pic]Q) [pic]((Q[pic]P).

12. Show that [pic] is not functionally complete.

Sol. Consider the statement (P.

(P cannot be expressed using the connectives [pic],[pic].

Hence [pic] is not functionally complete.

13. Show that [pic] is minimal functionally complete set.

Sol. We can express (, [pic],[pic] in terms of [pic] alone.

P[pic]P[pic]((P[pic]P)

[pic](P

(P[pic]Q) [pic](P[pic]Q) [pic]((P[pic]Q)

[pic]((((P[pic]Q))

[pic]P[pic]Q

(P[pic]P) [pic](P[pic]P) [pic](P[pic](Q

[pic](((P[pic](Q)

[pic]((((P[pic]Q))

[pic]P[pic]Q

[pic][pic] is minimal functionally complete set.

14. Show that [pic] is minimal functionally complete set.

Sol. We can express (, [pic],[pic] in terms of [pic] alone.

P[pic]P[pic]((P[pic]P)

[pic](P

(P[pic]Q) [pic] (P[pic]Q) [pic]((P[pic]Q)

[pic]((((P[pic]Q))

[pic]P[pic]Q

(P[pic]P) [pic] (P[pic]P) [pic](P[pic](Q

[pic](((P[pic](Q)

[pic]((((P[pic]Q))

[pic]P[pic]Q

[pic][pic] is minimal functionally complete set.

15. Define Principal disjunctive normal form.

Sol. For a given formula, an equivalent formula consisting of disjunction

of minterms only is known as Principal disjunctive normal form.

16. Define Principal conjunctive normal form.

Sol. For a given formula, an equivalent formula consisting of conjunction

of maxterms only is known as Principal conjunctive normal form.

17. Define the two rules of inference for statement calculus.

Sol. Rule P : A premise can be introduced at any point in the derivation.

Rule T : A formula S can be introduced in a derivation if S is tautologically

implied by any one or more of the preceding formulas in the derivation.

18. When the set of premises [pic] is said to be inconsistent.

Sol. The set of premises [pic] are said to be inconsistent provided

their conjunction implies a contradiction.

19. Show that (Q, P[pic]Q [pic](P.

Sol. Argument

1. (Q Rule P

2. P[pic]Q Rule P

3. (Q [pic](P Rule T

4. 7P Rule T ( From 1,3)

20. Show that ((P[pic]Q) follows from (P[pic](Q by using indirect method.

Sol. Argument

1. ((((P[pic]Q)) Rule P ( assumed premise)

2. P[pic]Q Rule T

3. P Rule T

4. (P[pic](Q Rule P

5. (P Rule T

6. P[pic](P Rule T

which is a contradiction.

21. Symbolize the statement: “If Vani attends classes regularly and if either

she is attentive in the class or studies well then she gets the top grade.”

Sol. Let P: Vani attends classes regularly.

Q: She is attentive in the class

R: She studies well

S: She gets the top grade.

The given statement can be written as P[pic](Q[pic]R)[pic]S.

22. Show that ((P[pic]Q) [pic]((P[pic]((P[pic]Q)) [pic](P[pic]Q.

Sol. ((P[pic]Q) [pic]((P[pic]((P[pic]Q)) [pic](P[pic]Q) [pic]((P[pic]((P[pic]Q))

[pic] (P[pic]Q) [pic](((P[pic](P) [pic]Q)

[pic] (P[pic]Q) [pic]((P[pic]Q)

[pic] [P[pic]((P[pic]Q)] [pic][Q[pic]((P[pic]Q)]

[pic] [(P[pic](P) [pic]Q] [pic][(Q[pic]Q)[pic](P]

[pic] (T[pic]Q) [pic](Q[pic](P)

[pic] T[pic]((P[pic]Q)

[pic] ((P[pic]Q).

23. Express the premises in symbols for the following argument:

If I like mathematics, then I will study. Either I study or fail.

Therefore, if I fail then I do not like mathematics.

Sol. Let P: I like mathematics

Q: I will study

R: I fail

The given premises are P[pic]Q, Q[pic]R [pic]R[pic](P.

24. Find PCNF of P[pic]Q if the PDNF of P[pic]Q is (P[pic]Q) [pic]((P[pic](Q)

Sol. Given P[pic]Q [pic](P[pic]Q) [pic]((P[pic]Q)

Now, (A [pic] ((P[pic]Q) [pic](P[pic](Q)

(((A) [pic]([((P[pic]Q) [pic](P[pic](Q)]

A [pic] ([(P[pic]Q] [pic]([P[pic](Q]

A [pic] (P[pic](Q) [pic]((P[pic]Q), which is PCNF.

25. Prove that P[pic]Q [pic](Q[pic](P.

Sol. P[pic]Q [pic](P[pic]Q

[pic]Q[pic](P

[pic](((Q) [pic](P

[pic] (Q[pic](P.

26. Define Tautology.

Sol. A statement formula which is True regardless of the truth values

of the statements which replace the variables in it is called a Tautology.

(i.e) The proposition P (P1,P2,……) is a tautology if it contains only T

in the last column of its truth values.

27. Define Contradiction.

Sol. A statement formula which is False regardless of the truth values

of the statements which replace the variables in it is called a Contradiction.

(i.e) The proposition P (P1,P2,……) is a contradiction if it

contains only F in the last column of its truth values.

28. Test whether the following formula P [pic](Q [pic]P) is a tautology?

Sol. P [pic](Q [pic]P) [pic]P [pic]((Q [pic]P)

[pic](P [pic](P [pic](Q)

[pic]((P [pic]P) [pic](Q

[pic]T [pic](Q

[pic] T

Hence P [pic](Q [pic]P) is a tautology.

29. Show that ((P[pic]Q) [pic](P[pic](Q

Sol. ((P[pic]Q) [pic]([((P[pic]Q)]

[pic]([(P[pic](Q]

[pic](P[pic](Q.

30. Establish P[pic]Q [pic](P[pic]Q) [pic]((P[pic](Q)

Sol.

|P |Q |P [pic]Q |P[pic]Q |(P |(Q |(P[pic](Q |(P[pic]Q) [pic]((P[pic](Q) |

|T |T |T |T |F |F |F |T |

|T |F |F |F |F |T |F |F |

|F |T |F |F |T |F |F |F |

|F |F |T |F |T |T |T |T |

Hence P[pic]Q [pic](P[pic]Q) [pic]((P[pic](Q).

31. Define Predicate Calculus

Sol.: The logic based upon the analysis of predicates of any statement is called

Predicate logic (or) Predicate calculus.

32. Define simple statement function with an example

Sol. It is defined to be an expression consisting of a predicate symbol and an

individual variable.

Ex: Let B be the predicate “is a Bachelor” and j the name “Mr.John”, c “Mr. Chandran”

and s “Mr. Senthil”, then B(j), B(c) and B(s) are all simple statement function.

33. Define compound statement function with an example

Sol. It is obtained by combining one or more simple statement function with logical

connectives.

Ex: M(x) [pic]H(x), M(x) [pic]H(x), M(x) [pic]H(x), 7H(x), etc.

34. Define Universal Quantifier with an example

Sol. The Quantifiers which are introduced to symbolize expressions such as “for all”,

“every” and “for any” is called Universal Quantifier.

Ex: All roses are red. (i.e) If x is rose then x is red.

Let A(x): x is rose, B(x): x is red.

Then the statement “All roses are red” can be written as “For all x, if x is a rose

then x is red” and it is ([pic]x)[A(x)[pic]B(x)] or (x) [A(x)[pic]B(x)]

35. Define Existential Quantifier with an example

Sol. The Quantifiers which are introduced to symbolize expressions such as “for some”, “there is at least one” and “there exists some” is called Existential Quantifier.

Ex: Some men are clever.

Let M(x): x is a man

C(x): x is clever

Then the statement “Some men are clever” can be written as “There exists some x such that x is a man and x is clever” and it is ([pic]x) [M(x) [pic]C(x)]

36. Write the following statement in the symbolic form “Some monkeys have no tails”

Sol. Let M(x): x is a monkey

T(x): x has a tail

The given statement can be written as “There is an x such that x is a monkey and x has no tail” and it is ([pic]x) [M(x) [pic]7 T(x)]

37. Write the following statement in the symbolic form

“It is not true that all roads lead to Rome”

Sol. Let R(x): x is a road

L(x): x lead to Rome

The given statement can be written as “It is not true that for all x if x is a road then x leads to Rome” or “ There is an x such that x is a road and x does not lead to Rome” and it is

7([pic]x) [R(x)[pic]L(x)] (or) ([pic]x) [R(x) [pic]7 L(x)].

38. Symbolize : “For any x and for any y , if x is taller than y then y is not taller than x”

Sol. Let T(x,y) : x is taller than y.

The given statement can be written as “For any x and for any y, if x is taller than y then it is not true that y is taller than x” and it is

([pic]x) ([pic]y)[T(x,y) [pic]7 T(y,x)]

39. Express [pic] is an irrational number using quantifiers.

Sol. Consider the equation [pic] It does not posses any integer solution. Hence we can express [pic] is an irrational number as

7([pic]x) ([pic]).

40. Symbolize: For every x, there exists a y such that

[pic]

Sol. Let P(x,y) : [pic]For every x, there exists a y such that [pic] can be symbolized as ([pic]x) ([pic]y) P(x,y).

41. Symbolize : For any given positive integer, there is a greater positive integer.

Sol. Let P(x): x is a positive integer

G(x,y): x is greater than y

The statement can be written as “For any x, if x is a positive integer then there exists some y such that y is a positive integer and y is greater than x” and it is ([pic]x)[P(x) [pic]([pic]y)( P(y) [pic]G(y,x))]

42. Symbolize: Some people are not admired by everyone.

Sol. Let P(x): x is a person

A(x,y): x admires y

The given statement can be written as “There is a person who is not admired by some person” and it is ([pic]x) ([pic]y)[P(x) [pic]P(y) [pic]7 A(x,y)]

43. Symbolize: Every book with a blue cover is a mathematics book.

Sol. Let P(x) : x is a book

B(x) : x has a blue cover

M(x) : x is a mathematics book

The statement can be written as “For all x, if x is a book and x has a blue cover then x is a mathematics book” and it is ([pic]x)[P(x)[pic]B(x)[pic]M(x)]

44. Symbolize: Every one who likes fun will enjoy each of these plays.

Sol. Let L(x) : x likes fun

P(y) : y is a play

E(x,y) : x will enjoy y.

The statement can be written as “For each x, if x likes fun and for each y, if y is a play, then x enjoys y” and it is

([pic]x)([pic]y)[ L(x)[pic]P(y)[pic]E(x,y)]

45. Symbolize: Every one should help his neighbours or his neighbours will not help him.

Sol. Let N(x,y) : x and y are neighbours

H(x,y) : x should help y

P(x,y) : x will help y

The statement can be written as “For every person x and every person y, if x and y are neighbors, then either x should help y or y will not help x” and it is ([pic]x) ([pic]y)[ N(x,y) [pic]( H(x,y) [pic]7 P(y,x))]

46. Symbolize : Every one who is healthy can do all kinds of work.

Sol. Let H(x) : x is a healthy person

W(y): y is a kind of work

D(x,y): x can do y

The statement can be written as “For all x, if x is healthy and for all y, if y is a kind of work then x can do y” and it is

([pic]x) ([pic]y)[ H(x) [pic]W(y) [pic]D(x,y)]

47. Symbolize: Some people who trust others are rewarded.

Sol. Let P(x): x is a person

T(x): x trust others

R(x): x is rewarded

The statement can be written as “There is one x such that x is a person, x trust others and x is rewarded” and it is ([pic]x)[P(x) [pic]T(x) [pic]R(x)]

48. Symbolize: If any one is good then John is good.

Sol. Let P(x): x is a person

G(x) : x is good

G(j) : John is good

The statement can be written as “If there is one x such that x is a person and x is good then John is good” and it is ([pic]x)[P(x) [pic]G(x)] [pic] G(j).

49. Symbolize: He is ambitious or no one is ambitious.

Sol. Let P(x): x is a person

A(x): x is ambitious

‘He’ represents a particular person. Let that person be y. So the statement is “y is ambitious or for all x, if x is a person then x is not ambitious” and it is A(y)[pic]([pic]x)[ P(x)[pic]7 A(x)].

50. Symbolize: Every student in this class has studied calculus.

Sol. Let S(x) : x is a student in this class

C(x) : x has studied calculus

The statement can be written as “For all x, if x is a student in this class then x has studied calculus” and it is ([pic]x)[ S(x) [pic]C(x)].

[pic]

PART - B

1. Prove that ((P[pic]Q)[pic]7(7P[pic](7Q [pic]7R)))[pic](7P[pic]7Q)[pic](7P[pic]7R)

is a Tautology.

Sol. ((P[pic]Q)[pic]7(7P[pic](7Q [pic]7R)))[pic](7P[pic]7Q)[pic](7P[pic]7R)

[pic]((P[pic]Q) [pic]7(7P[pic]7(Q[pic]R))) [pic]7(P[pic]Q) [pic]7(P[pic]R)

[pic]((P[pic]Q) [pic](P[pic](Q[pic]R)))) [pic]7[(P[pic]Q) [pic](P[pic]R)]

[pic]((P[pic]Q) [pic](P[pic]Q) [pic](P[pic]R)) [pic]7[P[pic](Q[pic]R)]

[pic]((P([pic]Q) [pic](P[pic]R)) [pic] 7[P[pic](Q[pic]R)]

[pic][P[pic](Q[pic]R)] [pic] 7[P[pic](Q[pic]R)]

[pic] T.

Hence the given statement formula is a tautology.

2. Show that 7(P[pic]Q) [pic](7P[pic](7P[pic]Q)) [pic](7P[pic]Q)

and hence prove that (P[pic]Q) [pic](7P[pic](7P[pic]Q)) [pic](7P[pic]Q).

Sol. 7(P[pic]Q) [pic](7P[pic](7P[pic]Q)) [pic](P[pic]Q) [pic](7P[pic](7P[pic]Q))------(1)

[pic](P[pic]Q) [pic]((7P[pic]7P) [pic]Q)

[pic](P[pic]Q) [pic](7P[pic]Q)

[pic][P[pic](7P[pic]Q)] [pic][Q[pic](7P[pic]Q)]

[pic][(P[pic]7P) [pic]Q] [pic][(Q[pic]Q) [pic]7P]

[pic](T[pic]Q) [pic](Q[pic]7P)

[pic] T[pic](7P[pic]Q)

[pic](7P[pic]Q).

From (1) we have

(P[pic]Q) [pic](7P[pic](7P[pic]Q)) [pic](7P[pic]Q)

Its dual is (P[pic]Q) [pic](7P[pic](7P[pic]Q)) [pic](7P[pic]Q).

3. If H1,H2,…..Hm and P imply Q then H1,H2,…..Hm imply P[pic]Q.

Sol. We know that A [pic]B iff A [pic]B is a tautology.

Given that H1,H2,…..Hm and P imply Q

(i.e) (H1 [pic] H2 [pic] .….. [pic] Hm [pic]P) [pic]Q

(i.e) (H1 [pic] H2 [pic] .….. [pic] Hm [pic]P) [pic] Q is a tautology.

----------(1)

Since we know that

A [pic](B[pic]C) [pic](A[pic]B) [pic]C

Equation (1) becomes

(H1 [pic] H2 [pic] .….. [pic] Hm ) [pic] (P [pic] Q) is a tautology

(i.e) H1 [pic] H2 [pic] .….. [pic] Hm [pic] (P [pic]Q).

{Hint: A [pic](B [pic]C) [pic]A [pic](7B [pic]C)

[pic]7A [pic](7B [pic]C)

[pic](7A [pic]7B) [pic]C

[pic]7(A [pic]B) [pic]C

[pic](A [pic]B) [pic]C }

4. Obtain PDNF of (P [pic]Q) [pic]R [pic]7P and hence find its PCNF.

Sol. (P [pic]Q) [pic]R [pic]7P

[pic]7[(P[pic]Q) [pic]R] [pic]7P

[pic][7(P[pic]Q) [pic]7R] [pic]7P

[pic][(7P[pic]7Q) [pic]7R] [pic]7P

[pic](7P[pic]7R) [pic](7Q[pic]7R) [pic]7P

[pic][(7P[pic]7R) [pic](Q[pic]7Q)] [pic] [(7Q[pic]7R) [pic](P[pic]7P)]

[pic] [7P[pic](Q[pic]7Q)]

[pic](7P[pic]7R[pic]Q) [pic](7P[pic]7R[pic]7Q) [pic](7Q[pic]7R[pic]P)

[pic](7Q[pic]7R[pic]7P) [pic](7P[pic]Q) [pic](7P[pic]7Q)

[pic](7P[pic]Q[pic]7R) [pic](7P[pic]7Q[pic]7R) [pic](P[pic]7Q[pic]7R)

[pic][(7P[pic]Q)[pic](R[pic]7R)][pic][(7P[pic]7Q) [pic](R[pic]7R)]

[pic](7P[pic]Q[pic]7R) [pic](7P[pic]7Q[pic]7R)[pic] (P[pic]7Q[pic]7R)

[pic](7P[pic]Q[pic]R)[pic](7P[pic]Q[pic]7R) [pic](7P[pic]7Q[pic]R)

[pic](7P[pic]7Q[pic]7R)

[pic] (7P[pic]Q[pic]7R) [pic](7P[pic]7Q[pic]7R)[pic](P[pic]7Q[pic]7R)

[pic](7P[pic]Q[pic]R)[pic](7P[pic]7Q[pic]R), which is PDNF.

Now, 7A [pic] (P[pic]Q[pic]R) [pic](P[pic]Q[pic]7R) [pic](P[pic]7Q[pic]R)

7(7A) [pic] 7[(P[pic]Q[pic]R) [pic](P[pic]Q[pic]7R) [pic](P[pic]7Q[pic]R)]

A [pic] 7(P[pic]Q[pic]R) [pic]7(P[pic]Q[pic]7R) [pic]7(P[pic]7Q[pic]R)

A [pic] (7P [pic]7Q [pic]7R) [pic](7P [pic]7Q [pic]R) [pic](7P [pic]Q [pic]7R)

which is PCNF.

5. Obtain the PCNF of (7P [pic]R) [pic](Q[pic]P) and hence find

its PDNF.

Sol. (7P [pic]R) [pic](Q[pic]P)

[pic](P[pic]R) [pic](Q[pic]P) [pic](P[pic]Q)

[pic](P[pic]R) [pic](7Q[pic]P) [pic](7P[pic]Q)

[pic][(P[pic]R) [pic](Q[pic]7Q)] [pic][(7Q[pic]P)[pic](R[pic]7R)]

[pic][(7P[pic]Q) [pic](R[pic]7R)]

[pic](P[pic]R[pic]Q) [pic](P[pic]R[pic]7Q) [pic](7Q[pic]P[pic]R) [pic](7Q[pic]P[pic]7R)

[pic](7P[pic]Q[pic]R) [pic](7P[pic]Q[pic]7R)

[pic](P[pic]Q[pic]R) [pic](P[pic]7Q[pic]R)[pic](P[pic]7Q[pic]7R) [pic](7P[pic]Q[pic]R)

[pic](7P[pic]Q[pic]7R) which is PCNF.

Now, 7A [pic] (7P[pic]7Q[pic]R) [pic](7P[pic]7Q[pic]7R) [pic](P[pic]Q[pic]7R)

7(7A) [pic]7[(7P[pic]7Q[pic]R) [pic](7P[pic]7Q[pic]7R) [pic](P[pic]Q[pic]7R)]

A [pic]7(7P[pic]7Q[pic]R) [pic]7(7P[pic]7Q[pic]7R) [pic]7(P[pic]Q[pic]7R)

A [pic] (P [pic]Q [pic]7R)[pic](P [pic]Q [pic]R)[pic](7P[pic]7Q [pic]R)

which is PDNF.

6. Using truth tables, verify if 7P is a valid conclusion from the

premises 7P [pic]Q, 7(Q [pic]7R) and 7R.

Sol. Let H1:7P [pic]Q , H2: 7(Q [pic]7R) , H3: 7R C: 7P

|P |Q |R |C:7P |H3:7R |H1:7P[pic]Q |Q[pic]7R |H2:7(Q[pic]7R) |

|T |T |T |F |F |T |F |T |

|T |T |F |F |T |T |T |F |

|T |F |T |F |F |F |F |T |

|T |F |F |F |T |F |F |T |

|F |T |T |T |F |T |F |T |

|F |T |F |T |T |T |T |F |

|F |F |T |T |F |T |F |T |

|F |F |F |T |T |T |F |T |

In the 8th row, H1, H2, H3 are all true and C is also true.

Hence the argument is valid.

7. Show that P[pic]Q, Q[pic]7R, R, P[pic](J[pic]S) [pic]J[pic]S

Sol.

Argument

1. P[pic]Q Rule P

2. Q[pic]7R Rule P

3. P[pic]7R Rule T (From 1,2)

4. R[pic]7P Rule T

5. R Rule P

6. 7P Rule T (From 4,5)

7. P[pic](J[pic]S) Rule P

8. 7P[pic](J[pic]S) Rule T

9. J[pic]S Rule T (From 6,8)

[pic] The argument is valid.

8. Prove the validity of the following argument:

If I get the job and work hard, then I will get promoted. If I

get promoted, then I will be happy. I will not be happy.

Therefore, either I will not get the job or I will not work hard.

Sol. Let P: I get the job

Q: I work hard

R: I will get promoted

S: I will be happy

Then the given premises are

(P[pic]Q) [pic]R, R[pic]S , 7S and the conclusion is 7P[pic]7Q.

Argument

1. (P[pic]Q) [pic]R Rule P

2. R[pic]S Rule P

3. (P[pic]Q) [pic]S Rule T (From 1,2)

4. 7S[pic]7(P[pic]Q) Rule T

5. 7S Rule P

6. 7(P[pic]Q) Rule T (From 5,4)

7. 7P[pic]7Q Rule T

[pic] The argument is valid.

9. Using Rule CP,derive P[pic](Q[pic]S) from P[pic](Q[pic]R), Q[pic](R[pic]S).

Sol. Argument

1. P Rule CP (Assumed premise)

2. P[pic](Q[pic]R) Rule P

3. Q [pic]R Rule T

4. 7Q [pic]R Rule T

5. Q[pic](R[pic]S) Rule P

6. 7Q [pic](R [pic]S) Rule T

7. [7Q [pic]R] [pic][7Q [pic](R [pic]S)] Rule T

8. 7Q [pic][R [pic](R [pic]S)] Rule T

9. 7Q [pic]S Rule T

10. Q [pic]S Rule T

11. P [pic](Q [pic]S) Rule CP

[pic] The argument is valid.

10. Determine the validity of the following argument:

My father praises me only if I can be proud of myself. Either I

do well in sports or I can’t be proud of myself. If I study hard, then

I can’t do well in sports. Therefore if father praises me, then I do

not study well.

Sol. Let P: My father praises me

Q: I can be proud of myself

R: I do well in sports

S: I study hard

Given premises are

P[pic]Q, R[pic]7Q, S[pic]7R and the conclusion is P[pic]7S

Argument

1. P Rule CP (Assumed premise)

2. P [pic]Q Rule P

3. Q Rule T

4. R [pic]7Q Rule P

5. 7Q [pic]R Rule T

6. Q [pic]R Rule T

7. R Rule T

8. S [pic]7R Rule P

9. R [pic]7S Rule T

10. 7S Rule T

11. P [pic]7S Rule CP

[pic] The argument is valid.

11. Show that the conclusion R follows from P[pic]Q , Q[pic]R , P[pic]R by

using indirect method.

Sol. 1. 7R Rule P (Assumed premise)

2. P[pic]R Rule P

3. R[pic]P Rule T

4. 7R[pic]P Rule T

5. P Rule T

6. P[pic]Q Rule P

7. Q Rule T

8. Q[pic]R Rule P

9. R Rule T

10. R[pic]7R Rule T

which is a contradiction.

12. Show that the following set of premises is inconsistent.

If the contract is valid then John is liable for penality. If John is

liable for penality then he will go bankrupt. If the bank will loan

him money then he will not go bankrupt. As a matter of fact, the

contract is valid and the bank will loan him money.

Sol. Let P: The contract is valid

Q: John is liable for penality

R: He will go bankrupt

S: The bank will loan him money

Given premises are

P[pic]Q , Q[pic]R , S[pic]7R , P[pic]S

1. P[pic]Q Rule P

2. Q[pic]R Rule P

3. P[pic]R Rule T

4. S[pic]7R Rule P

5. R[pic]7S Rule T

6. P[pic]7S Rule T

7. 7P[pic]7S Rule T

8. 7(P[pic]S) Rule T

9. P[pic]S Rule P

10. (P[pic]S) [pic]7(P[pic]S) Rule T

which is a contradiction.

13. Test whether the following formula Q[pic](P[pic]7Q) [pic](7P[pic]7Q)

is a tautology or contradiction without constructing the truth

table.

Sol. Q[pic](P[pic]7Q) [pic](7P[pic]7Q) [pic][(Q [pic]P) [pic](Q [pic]7Q)] [pic]7(P [pic]Q)

[pic][(P [pic]Q) [pic]T] [pic]7(P [pic]Q)

[pic](P [pic]Q) [pic]7(P [pic]Q)

[pic] T

[pic]The given formula is tautology.

14. Obtain PCNF of (Q[pic]P) [pic](7P[pic]Q) and hence find its PDNF.

Sol. (Q[pic]P) [pic](7P[pic]Q)

[pic](7Q[pic]P) [pic]7P [pic]Q

[pic](P[pic]7Q) [pic][7P[pic](Q[pic]7Q)] [pic][Q[pic](P[pic]7P)]

[pic](P[pic]7Q) [pic](7P[pic]Q) [pic](7P[pic]7Q) [pic](Q[pic]P) [pic](Q[pic]7P)

[pic](P[pic]7Q) [pic](7P[pic]Q) [pic](7P[pic]7Q) [pic](P[pic]Q)

which is PCNF.

Here PDNF does not exists.

15. Obtain PDNF of the formula (P[pic](Q[pic]R)) [pic](7P[pic](7Q[pic]7R)).

Hence obtain the PDNF of its negation.

Sol. (P[pic](Q[pic]R)) [pic](7P[pic](7Q[pic]7R))

[pic](7P[pic](Q[pic]R)) [pic](P[pic](7Q[pic]7R))

[pic](7P[pic]P) [pic](7P[pic]7Q[pic]7R) [pic](Q[pic]R[pic]P)

[pic](Q[pic]R[pic]7Q[pic]7R)

[pic] F[pic](7P[pic]7Q[pic]7R) [pic](P[pic]Q[pic]R) [pic] F

[pic](7P[pic]7Q[pic]7R) [pic](P[pic]Q[pic]R) , which is PDNF.

Its negation is

(P[pic]Q[pic]7R) [pic](P[pic]7Q[pic]R) [pic](P[pic]7Q[pic]7R)

[pic](7P[pic]Q[pic]R) [pic](7P[pic]Q[pic]7R) [pic](7P[pic]7Q[pic]R).

16. Verify the validity of the following argument.

“All men are mortal. Socrates is a man. Therefore Socrates is a mortal.”

Sol. Let H(x): x is a man

M(x): x is a mortal

s: Socrates

We need to show ([pic]x)[H(x) [pic]M(x)], H(s) [pic]M(s)

Argument

1. ([pic]x)[H(x) [pic]M(x)] Rule P

2. H(s) [pic]M(s) Rule US

3. H(s) Rule P

4. M(s) Rule T

[pic]The argument is valid.

17. Verify the validity of the following argument.

Lions are dangerous animals. There are Lions. Therefore, there are dangerous animals.

Sol. Let L(x) : x is a Lion

D(x) : x is a dangerous animal

We need to show ([pic]x)[L(x) [pic]D(x)], ([pic]x) L(x) [pic]([pic]x) D(x)

Argument

1. ([pic]x) L(x) Rule P

2. L(a) Rule ES

3. ([pic]x)[L(x) [pic]D(x)] Rule P

4. L(a) [pic]D(a) Rule US

5. D(a) Rule T

6. ([pic]x) D(x) Rule EG

[pic]The argument is valid.

18. Verify the validity of the following argument.

Every living thing is a plant or an animal. John’s gold fish is alive and it is not a plant. All animals have hearts. Therefore John’s gold fish has a heart.

Sol. Let P(x) : x is a plant

A(x) : x is an animal

H(x) : x has a heart

g : John’s gold fish

We need to show

([pic]x)[P(x) [pic]A(x)] , 7P(g) ,([pic]x)[A(x) [pic]H(x)] [pic]H(g)

Argument

1. ([pic]x)[P(x) [pic]A(x)] Rule P

2. P(g) [pic]A(g) Rule US

3. 7P(g) Rule P

4. A(g) Rule T [ From 2,3 i.e.

7P, P[pic]Q[pic]Q]

5. ([pic]x)[A(x) [pic]H(x)] Rule P

6. A(g) [pic]H(g) Rule US

7. H(g) Rule T

[pic]The argument is valid.

19. Verify the validity of the following argument.

All integers are rational numbers. Some integers are powers of 2. Therefore, some rational numbers are powers of 2.

Sol. Let P(x) : x is an integer

R(x) : x is a rational number

S(x) : x is a power of 2

We need to show ([pic]x) [P(x)[pic]R(x)], ([pic]x)[P(x)[pic]S(x)]

[pic]([pic]x)[R(x) [pic]S(x)]

Argument

1. ([pic]x)[P(x)[pic]S(x)] Rule P

2. P(a) [pic]S(a) Rule ES

3. P(a) Rule T

4. S(a) Rule T

5. ([pic]x)[P(x)[pic]R(x)] Rule P

6. P(a) [pic]R(a) Rule US

7. R(a) Rule T ( From 3,6 )

8. R(a) [pic]S(a) Rule T ( From 7,4 )

9. ([pic]x)[R(x) [pic]S(x)] Rule EG.

[pic]The argument is valid.

20. Show that ([pic]x)[P(x) [pic]Q(x)], ([pic]x)[R(x) [pic]7 Q(x)]

[pic]([pic]x)[R(x) [pic]7 P(x)]

Sol. Argument

1. R(a) Rule CP( assumed premise)

2. ([pic]x)[R(x) [pic]7 Q(x)] Rule P

3. R(a) [pic]7 Q(a) Rule US

4. 7 Q(a) Rule T (From 1,3)

5. ([pic]x)[P(x) [pic]Q(x)] Rule P

6. P(a) [pic]Q(a) Rule US

7. 7 Q(a) [pic]7 P(a) Rule T

8. 7 P(a) Rule T (From 4,7)

9. R(a) [pic]7 P(a) Rule CP

10. ([pic]x)[R(x) [pic]7 P(x)] Rule UG.

21. Give a proof that the conclusion ([pic]x)[F(x) [pic]7 S(x)]

follows from the premises

([pic]x)[F(x)[pic]S(x)][pic]([pic]y)[M(y)[pic]W(y)] and

([pic]y)[M(y) [pic]7 W(y)].

Sol. Argument

1. ([pic]y)[M(y) [pic]7 W(y)] Rule P

2. M(a) [pic]7 W(a) Rule ES

3. 7 [M(a) [pic]W(a)] Rule T

[[pic]P[pic]7Q[pic]7(P[pic]Q)]

4. ([pic]y) 7[M(y) [pic]W(y)] Rule EG

5. 7([pic]y)[M(y) [pic]W(y)] Rule T

6. ([pic]x)[F(x)[pic]S(x)][pic]([pic]y)[M(y)[pic]W(y)] Rule P

7. 7([pic]x)[F(x) [pic]S(x)] Rule T

8. ([pic]x) 7[F(x) [pic]S(x)] Rule T

9. 7 [F(a) [pic]S(a)] Rule US

10. F(a)[pic]7 S(a) Rule T[[pic]7(P[pic]Q)[pic]P[pic]7Q)]

11. ([pic]x)[F(x)[pic]7 S(x)] Rule UG.

22. Prove that ([pic]x)[P(x)[pic]Q(x)] [pic]([pic]x)P(x) [pic]([pic]x)Q(x)

Sol. Argument

1. ([pic]x)[P(x)[pic]Q(x)] Rule P

2. P(a) [pic]Q(a) Rule ES

3. P(a) Rule T

4. Q(a) Rule T

5. ([pic]x)P(x) Rule EG

6. ([pic]x)Q(x) Rule EG

7. ([pic]x)P(x) [pic]([pic]x)Q(x) Rule T.

23. Prove that ([pic]x)[P(x)[pic]Q(x)] [pic]([pic]x)P(x) [pic]([pic]x)Q(x)

Sol. Argument

1. ([pic]x)[P(x)[pic]Q(x)] Rule P

2. P(a) [pic]Q(a) Rule US

3. P(a) Rule T

4. Q(a) Rule T

5. ([pic]x)P(x) Rule UG

6. ([pic]x)Q(x) Rule UG

7. ([pic]x)P(x) [pic]( [pic]x)Q(x) Rule T.

24. Prove that ([pic]x)[P(x) [pic]Q(x)] [pic]([pic]x)P(x) [pic]([pic]x)Q(x)

Sol. We shall use indirect method.

Argument

1. 7[([pic]x)P(x) [pic]([pic]x)Q(x)] Rule P (assumed premise)

2. 7([pic]x)P(x) [pic]7([pic]x)Q(x) Rule T

3. 7([pic]x)P(x) Rule T

4. 7([pic]x)Q(x) Rule T

5. ([pic]x)7P(x) Rule T

6. ([pic]x)7Q(x) Rule T

7. 7P(a) Rule ES

8. 7Q(a) Rule US

9. 7P(a) [pic]7Q(a) Rule T

10. 7[P(a) [pic]Q(a)] Rule T

11. ([pic]x)[P(x) [pic]Q(x)] Rule P

12. P(a) [pic]Q(a) Rule US

13. [P(a)[pic]Q(a)][pic]7[P(a)[pic]Q(a)] Rule T

which is a contradiction.

25. Prove that ([pic]x)P(x) [pic]([pic]x)Q(x) [pic]([pic]x)[P(x) [pic]Q(x)]

Sol. We shall use indirect method.

Argument

1. 7([pic]x)[P(x) [pic]Q(x)] Rule P (assumed premise)

2. ([pic]x)7[P(x) [pic]Q(x)] Rule T

3. ([pic]x)[7P(x) [pic]7Q(x)] Rule T

4. 7P(a) [pic]7Q(a) Rule T

5. 7P(a) Rule T

6. 7Q(a) Rule T

7. ([pic]x)7P(x) Rule EG

8. ([pic]x)7Q(x) Rule EG

9. ([pic]x)7P(x) [pic]([pic]x)7Q(x) Rule T

10. 7([pic]x)P(x) [pic]7([pic]x)Q(x) Rule T

11. 7[([pic]x)P(x) [pic]([pic]x)Q(x)] Rule T

12. ([pic]x)P(x) [pic]([pic]x)Q(x) Rule P

13. [([pic]x)P(x)[pic]([pic]x)Q(x)][pic]7[([pic]x)P(x)[pic]([pic]x)Q(x)] Rule T

which is a contradiction.

26. Prove that ([pic]x)[P(x) [pic]Q(x)], ([pic]y)P(y) [pic]([pic]z)Q(z)

by using indirect method.

Sol. Argument

1. 7([pic]z)Q(z) Rule P (assumed premise)

2. ([pic]z)7Q(z) Rule T

3. 7Q(a) Rule US

4. ([pic]y)P(y) Rule P

5. P(a) Rule ES

6. P(a) [pic]7Q(a) Rule T

7. 7[P(a) [pic]Q(a)] Rule T

8. ([pic]x)[P(x) [pic]Q(x)] Rule P

9. P(a) [pic]Q(a) Rule US

10. [P(a)[pic]Q(a)] [pic]7[P(a)[pic]Q(a)] Rule T

which is a contradiction.

27. Verify the validity of the following inference.

If one person is more successful than another, then he has worked harder to deserve success. John has not worked harder than Peter. Therefore John is not more successful than Peter.

Sol. Let S(x,y) : x is more successful than y

W(x,y) : x has worked harder than y to deserve success.

a : John

b : Peter

We need to show

([pic]x) ([pic]y)[S(x,y) [pic]W(x,y)] , 7W(a,b) [pic]7S(a,b)

Argument

1. ([pic]x) ([pic]y)[S(x,y) [pic]W(x,y)] Rule P

2. ([pic]y)[S(a,y) [pic]W(a,y)] Rule US1

3. S(a,b) [pic]W(a,b) Rule US2

4. 7W(a,b) [pic]7S(a,b) Rule T

5. 7W(a,b) Rule P

6. 7S(a,b) Rule T

[pic]The argument is valid.

28. Symbolize the expression“x is the father of the mother of y”

Sol. We can note that in the expression “x is the father of the mother of y”, in between x and y there is a person. Let z be a person as the mother of y.

Let P(z) : z is a person

F(x,z) : x is the father of z

M(z,y) : z is the mother of y

“x is the father of z and z is the mother of y” is true only for some z and it is ([pic]z)[P(z)[pic]F(x ,z) [pic]M(z ,y)].

29. Symbolize the expression “All world loves a lover”

Sol. All world loves a lover means that Everybody loves a lover.

Let P(x) : x is a person

S(x ,y) : x loves y

Let y be any person who is a lover.

P(y) : y is a person

L(y) : y is a lover

The statement is “For all x, if x is a person then for all y, if y

be any person who is a lover then x loves y” and it is

([pic]x)[P(x) [pic]([pic]y){(P(y) [pic]L(y)) [pic]S(x,y)}].

[pic]

| |

[pic]

| |

UNIT 2 COMBINATORICS

PART A

1. Find the number of non-negative integer solutions of the equation [pic]

2. Find the recurrence relation for the Fibonacci sequence.

3. If seven colours are used to paint 50 bicycles, then show that at least 8 bicycles will be the

same colour.

4. State the Pigeonhole principle.

5. Find the no. of arrangements of the letters in SCIENCE. How many of these arrangements have

no adjacent E’s ?

6. Find n if [pic]

7. Solve the recurrence relation y(k) – 8y(k-1) + 16y(k-2) = 0 for k ( 2, where y(2) = 16 and y(3) = 80.

8. What is the solution of the recurrence relation [pic] + 2 [pic]?

9. How many students must be in a class to guarantee that atleast two students receive the same score

on the final exam if the exam is graded on a scale from 0 to 100 points.

PART B

1. Use mathematical induction to prove that [pic] is divisible by 8, for all [pic].

2. Solve [pic] with [pic].

3. Find the generating function of Fibonacci sequence.

4. Determine the number of positive integers [pic] that are not divisible by 2, 3 or 5 but divisible by 7.

5. A bit is either 0 or 1. A byte is a sequence of 8 bits. Find the number of bytes. Among these

how many are (1) Starting with 11 and ending with 00.

(2) Starting with 11 but not ending with 00 or not starting with 11 but ending with 00?

6. Using mathematical induction, prove that 2 + 22 + …..+ 2n = 2n+1 – 2 for all non-negative integers n.

7. A question paper has 3 parts, Part A, Part B and Part C having 12, 4 and 4 questions respectively. A

student has to answer 10 questions from Part A and 5 questions from Part B and Part C put together

selecting at least 2 from each one of these two parts. In how many ways the selection of questions can

be done?

8. Using generating functions, solve the recurrence relation [pic] given that

[pic]

9. Prove by mathematical induction, that for all n ( 1, n3 + 2n is a multiple of 3.

10. Using the generating function, solve the difference equation [pic]

11. How many positive integers n can be formed using the digits 3, 4, 4, 5, 5, 6, 7 if n has to exceed

5000000?

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

any of the integers 2, 3, 5, 7.

13. Using Mathematical induction show that [pic]

14. There are 2500 students in a college, of these 1700 have taken a course in C, 1000 have taken a course

Pascal and 550 have taken a course in Networking. Further 750 have taken courses in both C and

Pascal, 400 have taken courses in both C and Networking, and 275 have taken courses in both Pascal

and Networking. If 200 of these students have taken courses in C, Pascal and Networking

1) How many of these 2500 students have taken a course in any of these three courses C, Pascal

and Networking?

2) How many of these 2500 students have not taken a course in any of these three courses C,

Pascal and Networking?

15. Using generating function solve [pic] with [pic]

16. A box contains six white balls and five red balls. Find the number of ways four balls can be drawn

from the box if (1) They can be any colour. (2) Two must be white and two red.

(3) They must all be the same colour.

17. If n Pigeonholes are occupied by (kn+1) pigeons, where k is positive integer, prove that at least

one Pigeonhole is occupied by (k+1) or more Pigeons. Hence, find the minimum number of m

integers to be selected from S = {1, 2,…,9} so that the sum of two of the m integers are even.

18. Solve the recurrence relation [pic]

19. Use mathematical induction to show that [pic]( (n , n ( 2.

20. Use the method of generating function to solve the recurrence relation

[pic] given that [pic]

21. Prove by the principle of mathematical induction, for ‘n’ a positive integer,

[pic]

22. Find the number of distinct permutations that can be formed from all the letters of each word

(1) RADAR (2) UNUSUAL.

23. Solve the recurrence relation, S(n) = S(n-1) + 2(n-1), with S(0) = 3, S(1) = 1, by finding its

generating function.

24. Use mathematical induction to prove the inequality n ................
................

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

Google Online Preview   Download