Page 132 - Discrete Mathematics and Its Applications

Supplementary Exercises 111

RESULTS De Morgan’s laws for quantifiers.
The logical equivalences given in Tables 6, 7, and 8 in Sec- Rules of inference for propositional calculus.
tion 1.3. Rules of inference for quantified statements.

Review Questions

1. a) Define the negation of a proposition. b) Give an example of a predicate P(x, y) such that
b) What is the negation of “This is a boring course”? ∃x∀yP(x, y) and ∀y∃xP(x, y) have different truth
values.
2. a) Define (using truth tables) the disjunction, conjunc-
tion, exclusive or, conditional, and biconditional of 8. Describe what is meant by a valid argument in proposi-
the propositions p and q. tional logic and show that the argument “If the earth is
flat, then you can sail off the edge of the earth,” “You can-
b) What are the disjunction, conjunction, exclusive or, not sail off the edge of the earth,” therefore, “The earth is
conditional, and biconditional of the propositions “I’ll not flat” is a valid argument.
go to the movies tonight” and “I’ll finish my discrete
9. Use rules of inference to show that if the premises “All
mathematics homework”?
zebras have stripes” and “Mark is a zebra” are true, then
3. a) Describe at least five different ways to write the con- the conclusion “Mark has stripes” is true.
ditional statement p → q in English.
10. a) Describe what is meant by a direct proof, a proof by
b) Definetheconverseandcontrapositiveofaconditional contraposition, and a proof by contradiction of a con-
statement. ditional statement p → q.
c) State the converse and the contrapositive of the con- b) Give a direct proof, a proof by contraposition and a
ditional statement “If it is sunny tomorrow, then I will proof by contradiction of the statement: “If n is even,
go for a walk in the woods.” then n + 4 is even.”
4. a) What does it mean for two propositions to be logically 11. a) Describe a way to prove the biconditional p ↔ q.
equivalent? b) Prove the statement: “The integer 3n + 2 is odd if and
b) Describe the different ways to show that two com- only if the integer 9n + 5 is even, where n is an inte-
pound propositions are logically equivalent. ger.”
c) Show in at least two different ways that the compound 12. To prove that the statements p 1 , p 2 , p 3 , and p 4 are equiva-
propositions ¬p ∨ (r →¬q) and ¬p ∨¬q ∨¬r are lent, is it sufficient to show that the conditional statements
equivalent. p 4 → p 2 , p 3 → p 1 , and p 1 → p 2 are valid? If not, pro-
vide another collection of conditional statements that can
5. (Depends on the Exercise Set in Section 1.3)
be used to show that the four statements are equivalent.
a) Given a truth table, explain how to use disjunctive nor- 13. a) Suppose that a statement of the form ∀xP(x) is false.
mal form to construct a compound proposition with How can this be proved?
this truth table.
b) Show that the statement “For every positive integer n,
b) Explain why part (a) shows that the operators ∧, ∨, n ≥ 2n” is false.
2
and ¬ are functionally complete. 14. What is the difference between a constructive and non-
c) Is there an operator such that the set containing just constructive existence proof? Give an example of each.
this operator is functionally complete?
15. What are the elements of a proof that there is a unique
6. What are the universal and existential quantifications of element x such that P(x), where P(x) is a propositional
a predicate P(x)? What are their negations? function?
7. a) What is the difference between the quantification 16. Explain how a proof by cases can be used to prove a result
∃x∀yP(x, y) and ∀y∃xP(x, y), where P(x, y) is a about absolute values, such as the fact that |xy|=|x||y|
predicate? for all real numbers x and y.

Supplementary Exercises

1. Let p be the proposition “I will do every exercise in b) I will get an “A” in this course and I will do every
this book” and q be the proposition “I will get an “A” exercise in this book.
in this course.” Express each of these as a combination of
p and q. c) Either I will not get an “A” in this course or I will not
do every exercise in this book.
a) I will get an “A” in this course only if I do every exer- d) For me to get an “A” in this course it is necessary and
cise in this book. sufficient that I do every exercise in this book.