Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Math 150: Discrete Mathematics

Midterm 1

October 11, 2018

1.  (15 points)

(a) Find the conjunction of the propositions p and q where p is the proposition Jill’s Mac

has more than 16GB free hard disk space” and q is the proposition The processor in Jill’s Mac runs faster than 1GHz .

(b) Let p be the statement All dogs have ees and are brown” .  Write down the negation of p (i.e -p) as an English sentence.

(c)  Construct a truth table for the proposition (p A -q) → (p V q).

2.  (15 points)

Prove that the following are logically equivalent using truth tables.

(a) p → q = -p ^ q .

(b) -(p n q) = -p ^ -q .

(c)  (p q) ^ (p r)  p (q ^ r).

3.  (15 points)

Translate the following statements into a logical expressions using the standard set notation. (a)  “The sum of two positive integers is always positive” .

(b)  For every positive integer, there exists another integer greater than the square root of

the first integer” .

(c)  There do not exist integers such that the sum of their cubes is a perfect cube” .

4.  (20 points)

Prove that ^3 is not a rational number.

5.  (20 points)

Prove the following identities.

(a) A ∩ B = A u B .

(b) A u B = A ∩ B . 

(c)  (A) = A.

6.  (15 points)

(a) Use the bubble sort algorithm to order the following integers:

2, 4, 6, 5, 1, 7, 10.

(b) Use the binary search algorithm to nd the number 7 in the (ordered) list you produce in part (a).