Chapter 18
Solutions for fourth week’s assignments

Also available as PDF.

18.1 Section 3.1

18.1.1 Problems 1-5

1.
Logical statement: there is enough data to verify the statement.
2.
Logical statement: again, there is enough data.
3.
Not a logical statement: rhetorical, not logical.
4.
Not a logical statement: this is a directive and not a statement.
5.
Logical statement: verifiable.

18.1.2 Problems 40, 42, 44

40.
He is not 48 years old.
42.
She has green eyes, he is 48 years old, or both.
44.
She has green eyes and he is not 48 years old.

18.1.3 Problems 49-54

49.
p ∧\mathop{}q
50.
\mathop{}p ∨\mathop{}q
51.
\mathop{}p ∨ q
52.
q ∧\mathop{}p
53.
\mathop{}(p ∨ q)
54.
(p ∨ q) ∧\mathop{}(p ∧ q)

18.2 Section 3.2

18.2.1 Problems 15-18

15.
\mathrel{⊧}\mathop{}(0 ∧\mathop{}1) ≡\mathop{}(0 ∧ 0) ≡\mathop{}0 ≡ 1.
16.
\mathrel{⊧}\mathop{}(\mathop{}0 ∨\mathop{}1) ≡\mathop{}(1 ∨ 0) ≡\mathop{}1 ≡ 0.
17.
\mathrel{⊧}\mathop{}\left [\mathop{}0 ∧ (\mathop{}1 ∨ 0)\right ] ≡\mathop{}(1 ∧ 0) ≡\mathop{}0 ≡ 1.
18.
\mathrel{⊧}\mathop{}\left [(\mathop{}0 ∧\mathop{}1) ∨\mathop{}1\right ] ≡\mathop{}(0 ∨ 0) ≡ 1.

18.2.2 Problems 37-40

37.
Two variables, so {2}^{2} = 4 rows.
38.
Three variables, {2}^{3} = 8 rows.
39.
Four variables, {2}^{4} = 16 rows.
40.
Five variables, {2}^{5} = 32 rows.

18.2.3 Problems 53-55

53.

pqp ∨\mathop{}qp ∧ q(p ∨\mathop{}q) ∧ (p ∧ q)
1 1 1 1 1
1 0 1 0 0
0 1 0 0 0
0 0 1 0 0

54.

pq\mathop{}p ∧\mathop{}q\mathop{}p ∨ q(\mathop{}p ∧\mathop{}q) ∨ (\mathop{}p ∨ q)
1 1 0 1 1
1 0 0 0 0
0 1 0 1 1
0 0 1 1 1

55.

pqr\mathop{}p ∧ q(\mathop{}p ∧ q) ∧ r
1 1 1 0 0
1 1 0 0 0
1 0 1 0 0
1 0 0 0 0
0 1 1 1 1
0 1 0 1 0
0 0 1 0 0
0 0 0 0 0

18.2.4 Problems 61, 62

61.
Symbolically, the statement is p ∨ q. So the negation is \mathop{}(p ∨ q) ≡\mathop{}p ∧\mathop{}q. Back into English: You cannot pay me now and you cannot pay me later.
62.
Again, the statement is \mathop{}p ∨ q and its negation is p ∧\mathop{}q. In English: I am going and she is not going.

18.3 Section 3.3

18.3.1 Problems 1-5

1.
If it is breathing, then it must be alive.
2.
If you see it on the Internet, then you can believe it.
3.
If it is summer, then Lorri Morgan visits Hawaii.
4.
If the number is Tom Shaffer’s area code, then the number is 216.

(Alternate from homeworks: If the area code is 216, then it is Tom Shaffer’s. This is another reasonable interpretation. As is: If you are Tom Shaffer, then your area code is 216.)

5.
If it is a picture, then it tells a story.

18.3.2 Problems 13, 15, 20

13.
If q is false, then the statement leads from a false premise and must be true. So assume q really is true. Then the validity of the statement depends on (p ∧ q) → q being true.

The clause p ∧ 1 simplifies, leading to p → 1. From the truth table, we see that the value of p does not matter and the result always is true. So the statement is true.

15.
The truth table for an if-then rule or conditional has one false entry. The negation of the conditional thus has only one true entry and so is not a conditional itself. So the statement is false.
20.
From a false hypothesis, anything can follow. The statement is true.

18.3.3 Problems 35-38

35.
\mathop{}b →\mathop{}r
36.
p →\mathop{}r
37.
b ∨ (p → r)
38.
p ∧ (r →\mathop{}b)

18.3.4 Problems 58, 60

58.

pq\mathop{}q →\mathop{}p(\mathop{}q →\mathop{}p) →\mathop{}q
1 1 1 0
1 0 0 1
0 1 1 0
0 0 1 1

60.

pqp ∧ qp ∨ q(p ∧ q) → (p ∨ q)
1 1 1 1 1
1 0 0 1 0
0 1 0 1 0
0 0 0 0 1

18.3.5 Problems 67, 68

67.
That is an authentic Persian rug and I am not surprised.
68.
Ella reaches that note and she does not shatter glass.

Quick note on Problem 67. Authentic Persian rugs and other rugs from that region must have flaws in the design. That is a religious requirement. And you can tell if it’s hand-made by checking the seams near the edges. If the seams are too small, the rug was machine-made.

18.3.6 Problems 74, 75

74.
The check is not in the mail or I am surprised.
75.
She does or he will.

18.4 Section 3.4

18.4.1 Problems 1, 3, 6

1.
Converse: If you were an hour, then beauty would be a minute. Inverse: If beauty were not a minute, then you would not be an hour. Contrapositive: If you were not an hour, then beauty is not a minute.
3.
Converse: If you don’t fix it, it ain’t broke. Inverse: If it is broke, then you fix it. Contrapositive: If you fix it, it is broke.
6.
Converse: If it contains calcium, then it is milk. Inverse: If it is not milk, then it does not contain calcium. Contrapositive: If it does not contain calcium, then it is not milk.

18.4.2 Problem 51, 57, 58

51.
By the rules, this must be contrary.
57.
x = 1 and z = 37. x = 2 and the Coen brothers are funny. There are no other rules governing these, so they must be consistent.
58.
x = 1 and x = 2. y = 1 and y = 2. A variable cannot have two values, so this is contrary.

18.5 Section 3.1 again

18.5.1 Problems 55, 56

55. Literally translated, \mathop{∀}k ∈\text{Items}\kern 1.66702pt \mathop{∀}s ∈\text{Stores} : \mathop{}(k\text{ is available in }s). We can pull out the negation to see that this is the same as \mathop{}(\mathop{∃}k ∈\text{Items}\kern 1.66702pt \mathop{∃}s ∈\text{Stores} : k\text{ is available in }s. So no item is available in any store. This is not the correct statement. The advertisement means to state that some items may not be available in all stores. We do not have the proper symbols to translate may.

56. The direct translation is \mathop{∀}p ∈\text{People} : \mathop{}(p\text{ has time to maintain his/her car properly}). We can pull the negation out to see that \mathop{}(\mathop{∃}p : p\text{ has time to maintain his/her car properly}), and the original statement says that no one maintains his/her car properly. The intent likely was that some people do not have time to maintain their cars properly, or \mathop{∃}p : \mathop{}(p\text{ has time to maintain his/her car properly}).

18.5.2 Problems 60-64

60.
A, B
61.
A, C
62.
C
63.
B
64.
A, C: “Not every” is both \mathop{}\mathop{∀}x : P(x) and \mathop{∃}x : \mathop{}P(x). Using the latter, \mathop{∃}p : \mathop{}(\mathop{}(F(p))), where F(p) asserts that p has a frame. So the statement is \mathop{∃}p : F(p), or there is a framed picture.

18.5.3 Problem 75

The first statement is about every student, \mathop{∀}s : \mathop{}(s\text{ passed the test})

The second negates the entire thing, so there exists some student who did not pass, because \mathrel{⊧}\mathop{}\mathop{∀}s : s\text{ passed the test} ≡\mathop{∃}s : s\text{ did not pass the test}.

Note that the latter statement is still true if no student passed. So you cannot infer that anyone passed in either statement.

18.5.4 Problem 76

Hint: Quantifiers do not necessarily exclude each other.

Both statements are true but they have different quantifiers.

The original statement (for some real number) is true if you pick one number (say zero) and demonstrate its truth ({0}^{2} = 0 ≥ 0).

Your friend’s statement applies to all real numbers. To demonstrate its validity, the statement must be proven to be true regardless of the value of x.

18.6 Negating statements

There is a number p for all numbers q such that the difference between p and q is 2.

Symbolically,

\mathop{∀}q\mathop{∃}p : |p - q| = 2.

Note the order of the quantifiers. So the negation is

\mathop{}(\mathop{∀}q\mathop{∃}p : |p - q| = 2) ≡\mathop{∃}q\mathop{∀}p : |p - q|≠2.

And in English:

For some number q, for all numbers p, the difference between p and q is not 2.

Quite often the phrasing is less bizarre if you push the negation only part-way through. Here, negating just the initial \mathop{∀}q gives the phrase:

For some number q there is no number p such that the difference between p and q is 2.

The initial statement is true, and its negation is false.

For all sets A, for all sets B, there is a set C such that A ∩ B = C and C is not .

Translating:

\mathop{∀}A\mathop{∀}B\mathop{∃}C : A ∩ B = C ∧ C≠∅.

Pushing the negation through the quantifiers and applying De Morgan’s laws,

\mathop{}(\mathop{∀}A\mathop{∀}B\mathop{∃}C : A ∩ B = C ∧ C≠∅) ≡\mathop{∃}A\mathop{∃}B\mathop{∀}C : A ∩ B≠C ∨ C = ∅.

Back into English:

There is a set A for which there is a set B such that for all C, A ∩ B≠C or C = ∅.

Note that the statement

\mathop{∀}A\mathop{∀}B\mathop{∃}C : A ∩ B = C ∧ C≠∅

is false. If two sets A and B are disjoint, then A ∩ B = ∅. Thus the negation is true.

18.7 Function from truth table

Derive a logic expression from the following truth table. Attempt to simplify it remembering the distributive property, De Morgan’s laws, and that \mathrel{⊧}z ∨\mathop{}z ≡ 1 and \mathrel{⊧}z ∧\mathop{}z ≡ 0.

pqrf(p,q,r)
1 1 1 1
1 1 0 0
1 0 1 1
1 0 0 1
0 1 1 0
0 1 0 0
0 0 1 0
0 0 0 0

There are fewer true values, so we start by listing individual conditions where the function is true. These are p ∧ q ∧ r, p ∧\mathop{}q ∧ r, and p ∧\mathop{}q ∧\mathop{}r. Joining these with or,

\mathrel{⊧}f(p,q,r) ≡ (p ∧ q ∧ r) ∨ (p ∧\mathop{}q ∧ r) ∨ (p ∧\mathop{}q ∧\mathop{}r).

Using the distributive property, we can pull out a p. Then

\mathrel{⊧}f(p,q,r) ≡ p ∧ ((q ∧ r) ∨ (\mathop{}q ∧ r) ∨ (\mathop{}q ∧\mathop{}r)).

Now we can pull out either \mathop{}q or r to try simplifying inside the parenthesis. With the former:

\mathrel{⊧}f(p,q,r) ≡ p ∧ ((q ∧ r) ∨ (\mathop{}q ∧ (r ∨\mathop{}r))).

Because \mathrel{⊧}r ∨\mathop{}r ≡ 1,

\mathrel{⊧}f(p,q,r) ≡ p ∧ ((q ∧ r) ∨\mathop{}q).

Now re-distribute \mathop{}q and simplify to see

\eqalignno{ \mathrel{⊧}f(p,q,r) & ≡ p ∧ (q ∨\mathop{}q) ∧ (r ∨\mathop{}q) & & \cr & ≡ p ∧ (r ∨\mathop{}q). & & }

So a simplified form is \mathrel{⊧}f(p,q,r) ≡ p ∧ (r ∨\mathop{}q). Another equivalent form is \mathrel{⊧}f(p,q,r) ≡ p ∧ (r → q).