Discrete Mathematics Answers

2. Obtain the product of sums canonical form of the following formula

i)(P^Q^R)V (¬P^Q^R)V(¬P^¬Q^¬R)

2. Let P(x) and Q(x) be the statements x3 < 50 and x+2 < 5 respectively. Find the truth values of following quantifications, where the domain consists of all real numbers.

(i) ∃x P(x)

(ii) ∀x P(x)

(iii) ∀x Q(x)

(iv) ∃x Q(x)

(v) ∀x (¬P(x))

(vi) ∃x (¬Q(x))

(vii) ∃x> 0 (P(x))

(viii) ∀x> 0 (¬Q(x))

(ix) ∀x (P(x) ∨ Q(x))

(x) ∃x (P(x) ∧¬Q(x))

Which of the following pairs of statements are logically equivalent? I.

Statement 1: It is not true that either I watched 'Crashlanding on You' or you watched 'Money Heist'.

Statement 2: I did not watch 'Crashlanding on You' and you watched 'Money Heist'.



II.Statement 1: Joe tells you that he is an engineer and he studied in Mapua.

Statement 2: If Joe is lying, then Joe is not an engineer or he did not study in Mapua.

Let n be a natural number. Use mathematical induction to prove that

4

n−1 > n2

for all n ≥ 3.

(a) Let P(x) be the statement x

2 ≥ x.

(i) What are truth values of the propositions P(1) , P(-1) , P(0) and P( 1

2

)?

(ii) What is the truth value of the proposition ∀xP(x), where the domain consists of all

real numbers?

(iii) What is the truth value of the proposition ∀xP(x), where the domain consists of all

integers?

(b) Let Q(x,y,z) be the statement x

2 + y

2 = z

2

. What are the truth values of

(i) ∀(x,y,z) Q(x,y,z)

(ii) ∃(x,y,z) Q(x,y,z) Where the domain consists of all real numbers.

What is the De Morgan’s law for quantifiers?

(b) Write the negation of following statements.

(i) ∃x (x

2 + 2 < 1)

(ii) ∀x (x - 2 ≥ 3)

(iii) ∀x (x

2 ≥ 0 and x + 2 < 1)

(iv) ∃x (x

2 + 2 < 0 or x - 5 ≥ 0)

(v) ∀x (x - 2 ≥ 3 and x

3 + 5 ≤ 2)

(vi) ∀x (x

2 = 2)

(vii) There is a student in our class who likes chemistry.

(viii) Every fox is cunning.

Using direct method, prove the following.

(i) If n is an even integer then -n is even.

(ii) If n is an even integer then 3n + 5 is odd.

(iii) If n is an odd integer then n

2 + 3n is even.

(iv) If m is an even integer and n is an odd integer then m2

- 2n is even.

(v) If m and n are even integers then mn + r is an odd integer. Where r is an odd

integer.

(vi) The sum of any two odd integers is even.

(vii) Let x and y be positive real numbers. If x ≤ y then √

x ≤

√y.

(viii) For any integers a,b and c if a divides b and b divides c then a divides c.

(Hint - if a divides b then we can write b = ka for some integer k)

Combinations:

(a) A class contains 10 students with 6 men and 4 women. Find the number of ways to:

i. Select a 4-member committee from the students

ii. Select a 4-member committee with 2 men and 2 women

iii. Elect a president, vice president, and secretary

(b) A box contains 8 blue socks and 6 red socks. Find the number of ways two socks can be drawn

from the box if:

i. They can be any color.

ii. They must be the same color.

There are four train routes between A and B, and three train routes between B and C. Find

the number of ways that a person can travel by train:

i. from A to C by way of B;

ii. roundtrip from A to C by way of B;

iii. roundtrip from A to C by way of B without using a train lines more than once.

1. Discuss two examples on binary trees both quantitatively and qualitatively.