CS 173, Spring 2009

Homework 1 Solutions
1. [9 points] Translate the following sentences into propositional logic,
making the meaning of your propositional variables clear. See page
11 of the textbook for some examples of translating English sentences
into propositional logic.

(a) Neither the storm blast nor the flood did any damage to the
house.
Solution: Let p and q represent “the storm blast damaged the
house” and “the flood damaged the house” respectively. Then the
above can be written as ¬(p ∨ q) or (¬p) ∧ (¬q).
(b) If global warming isn’t controlled, more forests will die in the
Pacific Northwest.
Solution:Let p and q represent “global warming isn’t controlled”
and “more forests will die in the Pacific Northwest” respectively.
Then the above can be written as p → q or (¬p) ∨ q
(c) Drivers should neither drive over 65 miles per hour nor cross the
red light, or they will get a ticket.
Solution: Let p, q and r represent “Drivers drive over 65 miles
per hour”, “Drivers cross the red light” and “Drivers will get a
ticket” respectively. Then the above can be written as ¬(p ∨ q) ∨ r
or (p ∨ q) → r.

2. [11 points]
Show that the following logical equivalences are correct. For (a), use
a truth table. For (b) and (c), use the logical equivalences given on
pages 24 and 25 of the textbook (in Tables 6 through 8).
Note that for (b) and (c) you should be very picky about explicitly
using associative laws, commutative laws, double negation laws, etc.
Refer to the examples on page 26 of Rosen to get an idea of what your
proofs should look like.

(a) (3 points) (p ⊕ q) ≡ (((¬p) → q) ∧ (q → (¬p)))

Solution:
Note: (¬p) → q ≡ p ∨ q and q → (¬p) ≡ ((¬q) ∨ (¬p)) ≡ ¬(q ∧ p)

1
 p q ¬p (¬p) → q q → (¬p) ((¬p) → q) ∧ (q → (¬p)) p⊕q
T T F T F F F
T F F T T T T
F T T T T T T
F F T F T F F
(b) ((¬p) → (r ∨ q)) ≡ ((¬r) → ((¬p) → q))
Solution: Note that there are many different ways of arriving at
the solution. However, your solution should have followed the
rules from the table in a picky manner, since that was the point
of this problem.

(¬p) → (r ∨ q)
≡ (¬(¬p)) ∨ (r ∨ q) (from Table 7)
≡ p ∨ (r ∨ q) (Double negation Law)
≡ r ∨ (p ∨ q) (Associative laws)
≡ (¬(¬r)) ∨ (p ∨ q) (Double Negation Law)
≡ (¬r) → (p ∨ q) (from Table 7)
≡ (¬r) → ((¬(¬p)) ∨ q) (Double Negation Law)
≡ (¬r) → ((¬p) → q) (from Table 7)

(c) (p → (r → q)) ≡ (p → q) ∨ ¬r
Solution:

(p → (r → q))
≡ (¬p) ∨ (r → q) (from Table 7)
≡ (¬p) ∨ ((¬r) ∨ q) (from Table 7)
≡ ((¬p) ∨ q) ∨ (¬r) (Associative Laws)
≡ (p → q) ∨ (¬r) (from Table 7)

3. [9 points] Rewrite the following statements using predicate logic short-

hand, making clear the meaning of your predicates and simple propo-
sitions, as well the types of any variables bound by quantifiers. For
example, the English sentence

Anyone who thinks 173 is fun is either crazy or an instructor .

2
can be rewritten as follows, assuming that P is the set of all people.

 
∀x ∈ P ThinksFun(x, 173) → (Crazy(x) ∨ Instuctor(x))

For this problem, assume that any use of the word “or” refers to inclu-
sive or (∨), not exclusive or (⊕).

(a) No prime number except 3 is divisible by 3.

Solution: Assume N is the set of all natural numbers.
 
∀x ∈ N x 6= 3 ∧ Prime(x) → (¬DivisibleBy3(x))

or  
¬∃x ∈ N x 6= 3 ∧ Prime(x) ∧ DivisibleBy3(x)

(b) Every CS 173 student has to solve a homework and at least one
CS 173 student must shovel snow.
Solution: Assume S stands for the set of all CS173 students.
 
∀x ∈ S HasToSolveHomework(x)] ∧ ∃x ∈ S MustShovelSnow(x)]

(c) It is easy to drive when it does not rain or snow.

Solution: It’s not clear whether this part requires a quantifier. If
you follow our general pattern of ignoring time, it would be

(¬Raining) ∧ (¬Snowing) → EasytoDrive

The English is vague about whether the “does not” applies to rain
and snow individually, or to the conjunction “rain or snow”. So
you could also have given

(¬Raining) ∨ (¬Snowing) → EasytoDrive

The version with “and” is slightly preferable because it makes

more real-world sense, but both answers are full-credit.
If you wanted to explicitly model time, using a set of times T ,
then the translation might look like:


∀t ∈ T (¬Raining(t)) ∧ (¬Snowing(t)) → EasytoDrive(t)]

3
4. [9 points]
Rewrite each of the following propositions as unambiguous English
sentences. The relevant predicates are defined as follows: Again, let’s
let P be a set of all people.

• A(x) means “x is teaching CS 173.”

• T (x) means “x is taking CS 473.”
• F (x) means “x has a Facebook page.”
• C(x) means “x likes to cook.”

For example, the proposition ∃x ∈ P [A(x) ∧ C(x)] could be translated

as “There is a person who is teaching CS 173 and likes to cook.”

(a) ∀x ∈ P [T (x) → F (x)]

Solution: Every person who is taking CS 473 has a Facebook
page.
(b) ∃z ∈ P [T (z) ∧ A(z)]
Solution: There is a person who is taking CS 473 and teaching
CS 173.
(c) ¬∀x ∈ P [T (x) → (F (x) ∨ C(x))]
Solution: It is not the case that everyone taking CS 473 has a
Facebook page or likes to cook.

5. [12 points]
Give the negation of the following logical expressions, using logical
equivalences to move the “not” operators onto the smallest elements
possible. For example, to negate ∀x[P (x) → Q(x)], we first negate
the whole thing ¬∀x[P (x) → Q(x)], then convert this to ∃x[¬(P (x) →
Q(x))], and finally to ∃x[P (x) ∧ ¬Q(x)]. (For simplicity, we’ve omitted
the domains for the quantified variables.)

(a) ∀x[P (x) ∨ Q(x)]

Solution:

¬∀x[P (x) ∨ Q(x)]

≡ ∃x[¬(P (x) ∨ Q(x))]
≡ ∃x[(¬P (x)) ∧ (¬Q(x))]

4
(b) ∃y[P (y) ∧ (Q(y) ∧ R(y))]
Solution:

¬∃y[P (y) ∧ (Q(y) ∧ R(y))]

≡ ∀y[¬(P (y) ∧ (Q(y) ∧ R(y)))]
≡ ∀y[(¬P (y)) ∨ ¬(Q(y) ∧ R(y))]
≡ ∀y[(¬P (y)) ∨ ((¬Q(y)) ∨ (¬R(y))]

(c) ∃x[(P (x) ∧ Q(x)) ∨ (Q(x) ∧ ¬P (x)]

Solution:

¬∃x[(P (x) ∧ Q(x)) ∨ (Q(x) ∧ ¬P (x)]

≡ ∀x[¬((P (x) ∧ Q(x)) ∨ (Q(x) ∧ ¬P (x)))]
≡ ∀x[(¬(P (x) ∧ Q(x))) ∧ ¬(Q(x) ∧ ¬P (x))]
≡ ∀x[(¬P (x) ∨ ¬Q(x)) ∧ (¬Q(x) ∨ ¬(¬P (x)))]
≡ ∀x[(¬P (x) ∨ ¬Q(x)) ∧ (¬Q(x) ∨ P (x))]

(d) ∀z[P (z) → (¬Q(z) → P (z))]

Solution:

¬∀z[P (z) → (¬Q(z) → P (z))]

≡ ∃z[¬(P (z) → (¬Q(z) → P (z)))]
≡ ∃z[¬((¬P (z) ∨ (¬Q(z) → P (z))))]
≡ ∃z[¬(¬P (z)) ∧ (¬(¬Q(z) → P (z)))]
≡ ∃z[P (z) ∧ (¬(¬(¬Q(z)) ∨ P (z)))]
≡ ∃z[P (z) ∧ (¬(Q(z) ∨ P (z)))]
≡ ∃z[P (z) ∧ (¬(Q(z)) ∧ ¬(P (z)))]
≡ ∃z[(P (z) ∧ ¬(P (z))) ∧ (¬Q(z))]
≡ False