UMBC CMSC203 Discrete Structures, Section 06, Spring 2016

Homework 3, Due Thursday, 02/18

1. Tautologies.

   Use a truth table to show that the following proposition is a tautology. You must show the intermediate steps in the truth table. (Note: ⊕ means exclusive or.)

   (~ (p ∨ q)) ⊕ ( (~p) → q)

   
   
   
2. Tautologies, again. [From Rosen 5/e.]

   Show that the following proposition is a tautology using algebraic manipulation of logical equivalences (i.e., without using a truth table). Show all your work.

   ( ( p ∨ q) ∧ ( p → r) ∧ ( q → r) ) → r

   You should use the logical equivalences in Theorem 2.1.1 of Epp 4/e (p. 35) or Theorem 1.1.1 of Epp 3/e (p. 14).
   
   

3. Logical Equivalences. [From Rosen 5/e.]

   Show that ~ p → (q → r) and q → (p ∨ r) are logically equivalent without using truth tables.

   You should use the logical equivalences in Theorem 2.1.1 of Epp 4/e (p. 35) or Theorem 1.1.1 of Epp 3/e (p. 14).
   
   

4. Knights and Knaves. [From "A Whole Slew of Computer-Generated Knights and Knaves Puzzles" by Zac Ernst, 1999.]

   Statements made by knights are true. Statements made by knaves are false. You meet three people: Xavier, Yolanda and Zain. You know that each is either a knight or a knave. This is what they said:

   Xavier: "It is not the case that Zain is a knave."
   Yolanda: "Zain and Xavier are both knights."
   Zain: "Xavier is a knight or Yolanda is a knave."

   Which of Xavier, Yolanda and Zain are knights? which are knaves? Show your reasoning. Follow the format in Example 2.3.14 in Epp 4/e (p. 60) or Example 1.3.16 in Epp 3/e (p. 39).