Solution to Exercise 2.1.1.1
a 
b 
(a ∨ b) 
false 
false 
false 
false 
true 
true 
true 
false 
true 
true 
true 
true 
Solution to Exercise 2.1.1.2
a 
¬a 
false 
true 
true 
false 
Solution to Exercise 2.1.1.3
a 
b 
(a ⇒ b) 
false 
false 
true 
false 
true 
true 
true 
false 
false 
true 
true 
true 
Solution to Exercise 2.1.1.4
Exactly one is true if either (a is true, and b is false) or (a is false, and b is true). So, one way to define it is a ⊕ b ≡ a ∧¬b ∨¬a ∧ b. The two halves of that formula also correspond to the two true rows of xor's truth table:
a 
b 
(a ⊕ b) 
false 
false 
false 
false 
true 
true 
true 
false 
true 
true 
true 
false 
Solution to Exercise 2.1.1.5
 Inclusive.
 Exclusive.
 Inclusive.
 Exclusive (hopefully).
Solution to Exercise 2.1.2.1
Unsatisfable.
Solution to Exercise 2.1.2.2
Tautology, arguably.
Solution to Exercise 2.1.2.3
Unsatisfable, unless of course you interpret "nobody" as "nobody of note".
Solution to Exercise 2.1.2.4
Neither. If you interpret "gets late" as a social issue but "early" as a clock issue, then the statement might be true, depending on where "here" is.
Solution to Exercise 2.1.2.5
Unsatisfable, except perhaps in a karmic^{37} sense.
Solution to Exercise 2.2.1.1
a 
b 
c 
(a ⇒ (b ⇒ c)) 
((a ⇒ b) ⇒ c) 
false 
false 
false 
true 
false 
false 
false 
true 
true 
true 
false 
true 
false 
true 
false 
false 
true 
true 
true 
true 
true 
false 
false 
true 
true 
true 
false 
true 
true 
true 
true 
true 
false 
false 
false 
true 
true 
true 
true 
true 
Table 2.28 Truth table to check associativity of implication
By inspecting the two rightmost columns, we see that the formulas are indeed not equivalent. They have different values for two truthsettings, those with a = false and c = false.
Solution to Exercise 2.2.1.2
In the original code, we return value2 when the first case is false, but the second case is true. Using a WFF, when ¬ (a ∧ b) ∧ (a ∨ b). Is this equivalent to the WFF a ∧¬b ∨¬a ∧ b? Here is a truth table:
a 
b 
¬ (a ∧ b) 
(a ∨ b) 
(¬ (a ∧ b) ∧ (a ∨ b)) 
(a ∧ ¬b) 
(¬a ∧ b) 
((a ∧ ¬b) ∨ (¬a ∧ b)) 
false 
false 
true 
false 
false 
false 
false 
false 
false 
true 
true 
true 
true 
false 
true 
true 
true 
false 
true 
true 
true 
true 
false 
true 
true 
true 
false 
true 
false 
false 
false 
false 
Yes, looking at the appropriate two columns we see they are equivalent.
Solution to Exercise 2.2.2.1
 2 variables: As we're seen, 4 rows.
 3 variables: 8 rows.
 5 variables: 32 rows.
 10 variables: 1024 rows.
 n variables: 2^{n} rows.
Solution to Exercise 2.2.2.2
 With 2 variables, we have 4 rows. How many different ways can we assign true and false to those 4 positions? If you write them all out, you should get 16 combinations.
 With 3 variables, we have 8 rows and a total of 256 different functions.
 With n variables, we have 2^{n} rows and a total of 2^{2n} different functions. That's a lotl
Solution to Exercise 2.3.1.1
1 
a ∧ (a ⇒ b) ⇒ b 

2 
≡ a ∧ (¬a ∨ b) ⇒ b 
Definition of ⇒ 
3 
≡ a ∧ ¬a ∨ a ∧ b ⇒ b 
Distributivity of ∨ over ∧ 
4 
≡ false ∨ a ∧ b ⇒ b 
Complement 
5 
≡ a ∧ b ∨ false ⇒ b 
Commutativity of ∨ 
6 
≡ a ∧ b ⇒ b 
Identity of ∨ 
7 
≡ ¬ (a ∧ b) ∨ b 
Definition of ⇒ 
8 
≡ ¬a ∨ ¬b ∨ b 
DeMorgan's law 
9 
≡ ¬a ∨ ¬b ∨ b 
Associativity of ∨ 
10 
≡ ¬a ∨ b ∨ ¬b 
Commutativity of ∨ 
11 
≡ ¬a ∨ true 
Complement 
12 
≡ true 
Dominance of ∨ 
Solution to Exercise 2.3.1.2
1 
(a ∨ b) ∧ b 

2 
≡ (a ∨ b) ∧ (b ∨ false) 
Identity of ∨ 
3 
≡ (b ∨ a) ∧ (b ∨ false) 
Commutativity of ∨ 
4 
≡ b ∨ a ∧ false 
Distributivity of ∨ over ∧ 
5 
≡ b ∨ false 
Dominance of ∧ 
6 
≡ b 
Identity of ∨ 
Solution to Exercise 2.3.2.1
 CNF: (a ∨ b) ∧ (¬a ∨ b ∨ c) ∧ (¬a ∨¬b)
 DNF: (¬a ∧ b) ∨ (a ∧¬b ∧ c)
ASIDE: Karnaugh maps^{38} are a general technique for finding minimal CNF and DNF formulas.
They are most easily used when only a small number of variables are involved. We won't worry about minimizing formulas ourselves, though.
Solution to Exercise 2.3.3.1
We can indeed reduce the question of Tautology to the question of Equivalence: if somebody asks you whether φ is true, you can just turn around and ask your friend whether the following two formulas are equivalent: φ, and true. Your friend's answer for this variant question will be your answer to your customer's question about φ. Thus, the Tautology problem isn't particularly harder than the Equivalence problem.
But also, Equivalence can be reduced to Tautology: if somebody asks you whether φ is equivalent to ψ, you can construct a new formula (φ ⇒ ψ) ∧ (ψ ⇒ φ). This formula is true exactly when φ and ψ are equivalent. So, you ask your friend whether this bigger formula is a tautology, and you then have your answer to whether the two original formulas were equivalent. Thus, the Equivalence problem isn't particularly harder than the Tautology probleml
Given these two facts (that each problem reduces to the other), we realize that really they are essentially the same problem, in disguise.
Solution to Exercise 2.3.3.2
Compare the last two columns in the following:
a 
b 
¬a ∨ b 
a ∧ (¬a ∨ b) 
a ∧ b 
false 
false 
true 
false 
false 
false 
true 
true 
false 
false 
true 
false 
false 
false 
false 
true 
true 
true 
true 
true 
Solution to Exercise 2.4.1.1
Intuitively, this is straightforward. Since A − has − 2, then both of its two neighbors, including B, must be unsafe. For this problem, let's be a bit more formal and use WFFs instead of prose in the steps.
1 
A − has − 2 
Premise 
2 
A − has − 2 ⇒ B − unsafe ∧ F − unsafe 
WaterWorld domain axiom, i.e., defnition of A − has − 2 
3 
B − unsafe ∧ F − unsafe 
lines 1,2 
4 
B − unsafe 
line 3 
Solution to Exercise 2.4.1.2
Again a similar idea, if A − has − 1, then at least one of A's two neighbors must be unsafe. But, since we know that one of these, G isn't unsafe, then the other, B, must be unsafe.
1 
A − has − 1 ⇒ B − safe ∧ G − unsafe ∨ B − unsafe ∧ G − safe 
WaterWorld domain axiom 
2 
A − has − 1 
Premise 
3 
B − safe ∧ G − unsafe ∨ B − unsafe ∧ G − safe 
lines 1,2 
4 
G − safe 
Premise 
5 
B − unsafe ∧ G − safe 
lines 3,4 
6 
B − unsafe 
line 5 
Solution to Exercise 2.4.1.3
Here, we'll show only χ ∧ υ ∧ ω f χ ∧ υ ∧ ω and leave the other direction (and ∨'s associativity) to the reader. These are all very similar to the previous commutativity example (Example 2.14).
1 
χ ∧ υ ∧ ω 
Premise 
2 
χ ∧ υ 
∧Elim (left), line 1 
3 
χ 
∧Elim (left), line 2 
4 
υ 
∧Elim (right), line 2 
5 
ω 
∧Elim (right), line 1 
6 
υ ∧ ω 
∧Intro, lines 4,5 
7 
χ ∧ υ ∧ ω 
∧Intro, lines 3,6 
Note that we omitted the detailed explanation of how each rule applies, since this should be clear in each of these steps.
Solution to Exercise 2.4.1.4
First, if we know , then that means there is some written proof... we know , simply by
If we know f φ ⇒ ψ, then if we add a premise φ, then ψ follows by ⇒Elim. Note how this proof is about other proofsl (However, while we reason about this particular inference system, we're not using this system while proving things about it this proof is necessarily outside the inference system.
Solution to Exercise 2.4.2.1
1 
α ⇒ β 
Premise 

2 
¬β 
Premise 

3 
subproof:α f false 

3.a 
α 
Premise for subproof 

3.b 
β 
⇒Elim, lines 1,3.a 

3.c 
false 
falseIntro, lines 2,3.b 

4 
¬α 
RAA, line 3 
Solution to Exercise 2.4.3.1
It would be sound: Look at all the possible proofs that can be made in the original system; all those proofs lead to true conclusions (since that original system is sound, as we're claiming). If we just discard all those that include RAA, the remaining proofs are still all true, so the smaller system is sound.
It would not be complete, though: As pointed out, RAA is our only way to prove negations without premises. There are negated formulas that are true (and have no premises) for example ¬false. Without RAA, we cannot provide a proof of ¬false, so the smaller system is incomplete.
Solution to Exercise 2.5.1
Lots of possible counterexamples. " It is bad to be depressed. Doing homework makes me depressed; so it's good to not do my homework. " Or, " It is bad for people to be in physical pain. Childbirth causes pain. Therefore childbirth needs be avoided by all people. " If the original conclusion is really correct, Tracy needs to elucidate some of his unspoken assumptions.
The faw seems to be along the lines of, " avoiding bad in the short run may not always be good in the long run " (or equivalently, sometimes you have to choose the lesser of two evils). No, you weren't asked to name a specifc faw, and reasonable people can difer on precisely what the faw is. (And, formal logic is not particularly helpful here.) Nonetheless, uncovering hidden assumptions in arguments often helps understand the real issues involved.
ASIDE: For fun, pick up the front page of the daily newspaper, and see how many arguments use faulty rules of inference andjor rely on unspoken premises (which not all might agree with). In particular, political issues as spun to the mainstream press are often riddled with error, even though there are usually reasonable arguments on both sides which policymakers and courts debate.
Solution to Exercise 2.5.2
" Terry claims that encouraging humanrights is more important than playing Tetris. But Terry played Tetris yesterday rather than volunteering with Amnesty International^{39} . " Most people wouldn't condemn Terry as a hypocrite just because of this; even the most dedicated of people are entitled to some free time. If your friend wants to prove Terry hypocritical, they'll have to provide further evidence or arguments.
Or similarly, "Politician X claims to support science funding, but voted against a proposal to shift all Medicare funds to NASA. "
Solution to Exercise 2.5.3
 It can be socially acceptable to wear my swimsuit into a fastfood restaurant. My underwear is less revealing than my swimsuit, and yet it would still raise many more eyebrows to go to that restaurant in my underwear, than my swimsuit. Clothes (and style in general) somehow encompass a form of communication, and people may object to an outft's mood or message without actually objecting to how much the outft reveals. (Other examples of communicationthroughstyle include team logos, tshirts with humorous slogans, and arm bands.)
 Buses are a lot cheaper than light rail. Yet, the lightrail here in Houston demonstrates that many people who wouldn't routinely take a bus are willing to take light rail. (Only after we recognize this, can we try to fgure out what why the diference exists, and then brainstorm to find a better overall solution.)
Solution to Exercise 2.5.5
 r ∧¬q
 r ⇒ p Think of the English being reworded to " If you got an A in this class, you must have gotten an A on the fnal. "
 3. p ∧ q ⇒ r
Solution to Exercise 2.5.7
Poppins ⇒ Mary
Solution to Exercise 2.5.10
 There are many simple answers, such as Y − has − 1, ¬W − has − 1, ...
 There are many simple answers, such as a, N − has − 1, J − has − 3, ...
For each, there are also many such formulas composed with connectives such as ∧ and ∨.
Solution to Exercise 2.5.16



false 
false 
true 
false 
true 
false 
true 
false 
false 
true 
true 
true 
This is the "equals" for Booleans. It is also represented by the connective ifandonlyif (Example 2.1).
If you said something like "the bothorneither function", that's not quite good enough, as it's a roundabout way of expressing the simple idea of equivalence. Granted, it takes some practice to internalize Booleans as values, and that equality is as valid for them as for any other value.
Solution to Exercise 2.5.23
list merge sorted lists(list list1, list list2) { if (is empty(list1)) return list2; else if (is empty(list2)) return list1; else { if (first element(list1) < first element(list2)) return make list(first element(list1), merge sorted lists(rest_elements(list1),list2)); else return make list(first element(list2), merge sorted lists(list1,rest elements(list2))); } }
Alternatively, we could test the emptiness of the lists in the other order.
Solution to Exercise 2.5.25
First we show that we can write negation in terms of ↓, or more specifically, ¬θ ≡ θ ↓ θ. Checking this on a truth table is pretty easy (there are only two rows to check). But for this question we need to use algebraic manipulation. This can be derived in a couple of simple steps:
1 
¬θ 

2 
≡ ¬θ ∧ ¬θ 
Idempotency of ∧ 
3 
≡ ¬ (θ ∨ θ) 
DeMorgan's law 
4 
≡ θ ↓ θ 
Defnition of nor 
We use this lemma to show our ultimate goal:
1 
δ ∧ E 

2 
≡ ¬¬ (δ ∧ E) 
Double Complementation 
3 
≡ ¬ (¬δ ∨ ¬E) 
DeMorgan's law 
4 
≡ ¬ ((δ ↓ δ) ∨ ¬E) 
Lemma, with [θ→δ] 
5 
≡ ¬ ((δ ↓ δ) ∨ (E ↓ E)) 
Lemma, with θ = E 
6 
≡ δ ↓ δ ↓ E ↓ E 
Defnition of nor, where φ = δ ↓ δ, and ψ = E ↓ E 
Note that we judiciously used new metavariables δ and E rather than reusing φ and ψ (which would still be correct, but would make the graders need to pay much closer attention to the scope of those variables).
Solution to Exercise 2.6.4
1 
¬ (φ ∨ ψ) 
Premise 

2 
subproof: 

2.a 
φ 
Premise for subproof 

2.b 
φ ∨ ψ 
∨Intro, line 2a 

2.c 
false 
falseIntro, lines 1,2b 

3 
¬φ 
RAA, line 2 
Table 2.40
Solution to Exercise 2.6.14
1 
Q − has − 1 
Premise 

2 
X − has − 1 
Premise 

3 
¬Y − unsafe 
Premise 

4 
W − unsafe ∨ Y − unsafe 
Theorem: above problem (Exercise 2.6.13), line 2 

5 
Y − unsafe ∨ W − unsafe 
Theorem: ∨ commutes, line 4 

6 
W − unsafe 
CaseElim, lines 3,5 

7 
subproof: 

7.a 
¬¬ (P − safe ∧ W − safe 
) Premise for subproof 

7.b 
P − safe ∧ W − safe 
¬Elim, line 7.a 

7.c 
W − safe 
∧Elim, line 7.b 

7.d 
W − safe ⇒ ¬W − unsafe 
WaterWorld axiom 

7.e 
¬W − unsafe 
⇒Elim, lines 7.c,7.d 

7.f 
false 
falseIntro, lines 6,7.e 

8 
¬ (P − safe ∧ W − safe) 
RAA, line 7 

9 
subproof: 

9.a 
¬¬ (R − safe ∧ W − safe 
) Premise for subproof 

9.b 
R − safe ∧ W − safe 
¬Elim, line 9.a 

9.c 
W − safe 
∧Elim, line 9.b 

9.d 
W − safe ⇒ ¬W − unsafe 
WaterWorld axiom 

9.e 
¬W − unsafe 
⇒Elim, lines 9.c,9.d 

9.f 
false 
falseIntro, lines 6,9.e 

10 
¬ (R − safe ∧ W − safe) 
RAA, line 9 

11 
Q − has − 1 ⇒ P − safe ∧ R − safe ∨ P − safe ∧ W − safe ∨ R − safe ∧ W − safe 
Theorem: Allowed by problem statement 

12 
P − safe ∧ R − safe ∨ P − safe ∧ W − safe ∨ R − safe ∧ W − safe 
⇒Elim, lines 1,11 

13 
R − safe ∧ W − safe ∨ P − safe ∧ R − safe ∨ P − safe ∧ W − safe 
Theorem: ∨ commutes, line 12 

14 
P − safe ∧ R − safe ∨ P − safe ∧ W − safe 
CaseElim, lines 8,13 

15 
P − safe ∧ W − safe ∨ P − safe ∧ R − safe 
Theorem: ∨ commutes, line 14 

16 
P − safe ∧ R − safe 
CaseElim, lines 10,15 

17 
P − safe 
∧Elim, line 16 
Alternatively, the subproofs could easily have been pulled out into lemmas. Just like using subroutines in a program, that would make the proof somewhat clearer, even though in this case each lemma would be used only once.
Observe how the two subproofs have some identical lines (7.c7.f and 9.c9.f). It would be incorrect to replace those lines in the second subproof with a citation of the results of the first subproof. First, because the previous subproof had been completed, and moreover, the two subproofs have different premises. This is analogous to two subroutines that happen to have some identical code lines, even through they are called separately and have different parameters.
Solution to Exercise 2.6.16
1 
¬¬φ 
Premise 

2 
subproof: 

2.a 
¬φ 
Premise for subproof 

2.b 
false 
falseIntro, lines 1,2.a 

3 
φ 
RAA, line 2 
 12458 reads