Homework 1 (assigned June 22, due June 28)

Reading: Rosen chapter 1, sections 1.1–1.4; 1.6–1.7.

Written assignment : Solve the following "Do" exercises and assigned problems. Only solutions to the assigned problems should be turned in. Note: You are responsible for the material covered in both "Do" exercises and assigned problems.

"Do" Exercises (not to be handed in):

1. For each of the following propositions, construct an equivalent proposition that contains no logical connectives other than negation and implication, and no variables other than p, q, and r.
   1. p ∧ q
   2. p ∨ q
   3. ¬(p ∨ q)
   4. (p ∧ ¬ q) ∨ r
   5. p ↔ q

2. Show that every (simple or compound) proposition is logically equivalent to a proposition in DNF. Assume the proposition has n distinct variables. Do the same for CNF.

3. The logical connective ↓ (the Peirce arrow) is defined by the following truth table. Show that {↓} is a functionally complete logical connective, i.e., that we can write negation, conjunction, and disjunction in terms of ↓.

   p	q	p ↓ q
   T	T	F
   T	F	F
   F	T	F
   F	F	T

4. Two opposite corner squares are deleted from an 8 × 8 checkerboard (see figure below). Prove that the remaining squares cannot be covered exactly by dominoes (rectangles consisting of two adjacent squares). Hint: Use the method of contradiction.
   

5. Prove the following statement about the integers: n is odd if and only if 8  |  (n² − 1).

6. Abraham Lincoln said: "You can fool all of the people some of the time, and you can fool some of the people all of the time, but you can't fool all of the people all of the time." Write this sentence in logical notation, negate the symbolic sentence, and state the negation in English. Which statement seems true?

7. Describe the logic: what it would mean for the first player to have a "winning strategy" in Tic-Tac-Toe?

Assigned problems (to be handed in):

1. For each of the following propositions, construct an equivalent proposition that contains no logical connectives other than negation and implication, and no variables other than p, q, and r. (2 points each)
   1. ¬(p ∧ q)
   2. ¬p ∨ q
   3. ¬p ∧ q
   4. ¬p ∨ ¬q ∨ r
   5. ¬(p ↔ q)

2. Propositions P and Q are defined by the following truth tables.

   p	q	r	P(p, q, r)	Q(p, q, r)
   T	T	T	F	F
   T	T	F	T	T
   T	F	T	F	F
   T	F	F	T	F
   F	T	T	T	F
   F	T	F	F	F
   F	F	T	T	T
   F	F	F	T	F

   1. Represent P(p, q, r) as a proposition that contains no logical connectives other than negation, conjunction, and disjunction, and no variables other than p, q, and r. Hint: Refer to "Do" exercise 2 above. Is your formula in CNF or DNF? Why? (3 points)
   2. Represent Q(p, q, r) as a proposition that contains no logical connectives other than negation, conjunction, and disjunction, and no variables other than p, q, and r. Refer to "Do" exercise 2 above. Is your formula in CNF or DNF? Why? (3 points)

3. The logical connective † is defined by the following truth table.

   p	q	p † q
   T	T	F
   T	F	T
   F	T	T
   F	F	T

   Show that {†} is a functionally complete logical connective, i.e., show that the logical connectives in some functionally complete set can be defined in terms of †. (5 points)

4. Consider tokens that have some letter written on one side and some integer written on the other, in unknown combinations. The tokens are laid out, some with the letter side up, some with the number side up. Explain which tokens must be turned over to determine whether the following statements are true.
   1. Whenever the letter side is a vowel, the number side is odd. (5 points)
   2. The letter side is a vowel if and only if the number side is odd. (5 points)

5. A fraternity has a rule for new members: each must always tell the truth or always lie. They know who does which. If you meet 3 of them on the street and they make the statements below, which ones (if any) should you believe?
   A says: "All three of us are liars."
   B says: "Exactly two of us are liars."
   C says: "The other two are liars."
   Justify your answer. (5 points)

6. Prove each of the following statements about the integers. (8 points each)
   1. If n is an integer, then n² + 2 is not divisible by 4.
   2. n is odd if and only if n² + 2n + 1 is even.

7. Express each of the following statements using predicates, quantifiers, logical connectives, and mathematical operators where the domain consists of all the integers. (4 points each)
   1. The product of two negative integers is positive.
   2. The average of two positive integers is positive.
   3. The difference of two negative integers is not necessarily negative.
   4. The absolute value of the sum of two integers does not exceed the sum of the absolute value of these integers.