Looking for a Computer Science Worksheet Templates? Download it for free!

COT3100 – Discrete Structures and Applications- HomeWork 2 Solution 2

Solution

ApplyingExercise11,we want to show that the conclusion r follows from the five premises (p∧t)→(r∨s),

q→(u∧t), u→p, ¬s, and q. From q and q→(u∧t) we get u∧t by modus ponens. From there we get

both u and t by simplification(and the commutative law).From u and u→p we get p by modus ponens.

From p and t we get p∧t by conjunction. From that and (p∧t)→(r∨s) we get r∨s by modus ponens.

From that and ¬s we finally get r by disjunctive syllogism.

Problem 5 [Section 1.6 Exercise 15 (10 points)]

For each of these arguments determine whether the argument is correct or incorrect and briefly

explain why (no more than two lines for each question).

a) All students in this class understand logic. Xavier is a student in this class. Therefore,

Xavier understands logic.

b) Every computer science major takes discrete mathematics. Natasha is taking discrete mathematics.

Therefore, Natasha is a computer science major.

c) All parrots like fruit. My pet bird is not a parrot. Therefore, my pet bird does not like fruit.

d) Everyone who eats granola every day is healthy. Linda is not healthy. Therefore, Linda does

not eat granola every day.

Solution

a) Correct , using Universal instantiation and modus ponens

b) Invalid, fallacy of affirming the conclusion

c) Invalid; fallacy of denying the hypothesis

d) Correct , using Universal instantiation and modus tollens

Problem 6 [Section 1.6 Exercise 20 (10 points)]

Determine whether these are valid arguments.

a) If x is a positive real number, then x2 is a positive real number. Therefore, if a2 is positive, where a is a

real number, then a is a positive real number.

b) If x2 != 0, where x is a real number, then x 6 = 0. Let a be a real number with a2 != 0; then a != 0.

Solution

a)This is invalid. It is the fallacy of affirming the conclusion. Letting a=−2provides a counter example.

b)This is valid; it is modus ponens.

Problem 7 [Section 1.7 Exercise 7 (10 points)]

Use a direct proof to show that every odd integer is the difference of two squares.

Solution

If n is odd , we can write n = 2k + 1, some integer k.

Then , taking the difference , (k+1)

– k

= 2k + 1 = n.

Thus , every odd integer is the difference of two squares.

Problem 8 [Section 1.7 Exercise 18 (10 points)]

Prove that if n is an integer and n3 + 5 is odd, then n is even using

a)a proof by contraposition

b)a proof by contradiction

Solution

a)We must prove the contrapositive: If n is odd, then 3n+2is odd. Assume that n is odd. Then we can

written =2k+1for some integer k. Then3n+2=3(2k+1)+2=6k+5=2(3k+2)+1. Thus 3n + 2 is two times some

integer plus 1,so it is odd.

b)Suppose that 3n+2is even and that n is odd.Since3n+2is even, so is 3n. If we add subtract an odd

Cot3100 - Discrete Structures And Applications - Homework 2 Solution - University Of Florida Page 2

Related Articles

Related forms

Related Categories