Discrete Mathematics

PARTA

Each question is worth 2 points.

DO NOT INCLUDE PROOFS OR COMMENTS FOR YOUR WORK IN THIS SECTION.

– – – – – – – – – – – – – – – – – – – – – – – – – – –

1. “Lansing is the capital of Michigan” and “It never rains in

Phoenix.” are statements that are True.

True or False

2. The compound statement ” p ^ (p v q) -> q ” is False only when p

is False.

True or False

3. The disjunction of p and q is the same as (p v q).

True or False

4. An OR function is the inverse of a NOR function.

True or False

5. The truth table of the biconditional statement, p <=> q , is the

inverse of p XOR q

True or False.

6. A proof that tries all possible cases to determine the result is

termed an exhaustive proof.

True or False

7. The converse of the contrapositive of a proposition is the same as

the original statement.

True or False

8. p NOR p = p AND p only when p = F.

True or False

9. The proposition (p OR FALSE) is True only when p is TRUE.

True or False

10. The contrapositive of a proposition is the inverse of the

original statement.

True or False

11. The relation

NOT (q OR p) AND (q NOR NOT p)

is True only when q is FALSE.

True or False

12. A statement that is neither a tautology nor a contingency is

termed a contrdiction.

True or False

13. Lemmas and axioms are both used to construct a proof.

True or False

14. The sum of the first 42 even integers is 1806.

True or False

PART B

Each question is worth 6 points. Divided questions are worth 3 points for each section. Show all work (within reason) in intermediate steps. Partial credit will be given, as appropriate.

Note: ANSWERS WITHOUT INTERMEDIATE WORK WILL BE GRADED AS ZERO!

Clearly identify the answer.

– – – – – – – – – – – – – – – – – – – – – – – – – – – –

1. Generate the Truth Table for

(p ^ s) ^ (NOT p ^ s)

2. How many rows will a Truth Table require if there are five

conditions and three variables? Defend your answer.

3. Construct a Truth Table for the statement NOT p -> p

4. Construct a Truth Table for the statement “p XOR (p v q)”

5. Given the bit strings 1111 1000 and 1001 1011, define the

a. bitwise AND

b. bitwise OR

6. Let:

A = {1,2,3,4,5,6,7,10,11)

B = {1,4,5,6,8,9,11}

C = {1,3,4,5,7,9,10}

Find the bitwise:

a. A XOR B

b. C DIFF A

7. Using the provided statement, what are the associated logic and prose statements for the:

a) converse; and,

b) contrapositive of the statement:

“If it is not Monday night, I will go to the movies”.

8. Using a Truth Table or equivalent, determine if:

(q AND NOT p) and (NOT(NOT q OR p)) are equivalent.

9. Let:

A = {a,b,f,g,h,i,l},

B = {b,c,d,f,g,j,m}, and

C = {a,c,d,f,g,i,j,l,m}.

Define each of the following bitwise operations:

a) (A NOR B) OR C

b) (A – B) – C

10. Determine whether p v NOT( p ^ q) -> q is True only when q is

False.

———————————————————-

OPTIONAL EXTRA CREDIT QUESTION (2 Points or no points). DO ONE.

A. Provide the Basis Step (ONLY) for:

What is the sum of the first n odd positive integers?

Defend your answer with six examples.

B. Is the following statement a Tautology? If not, what?

[(p 6 q) ^ (p -> r) v (q -> r) } -> r

Defend your answer.

END.

502q1c13c.