You are here

Solutions to Exercises in Chapter 2

26 July, 2019 - 12:03
Available under Creative Commons-ShareAlike 4.0 International License. Download for free at http://cnx.org/contents/383d4b87-2d7b-454e-99fe-2eaa43eae8ff@20.20

Solution to Exercise 2.1.1.1

Table 2.6 Truth table for ∨ (OR)

a

b

(ab)

false

false

false

false

true

true

true

false

true

true

true

true

 

Solution to Exercise 2.1.1.2

Table 2.7 Truth table for ¬ (NOT)

a

¬a

false

true

true

false

 

Solution to Exercise 2.1.1.3

Table 2.8 Truth table for ⇒ (IMPLIES)

a

b

(ab)

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 aba ∧¬b ∨¬ab. The two halves of that formula also correspond to the two true rows of xor's truth table:

Table 2.9 Truth table for xor

a

b

(ab)

false

false

false

false

true

true

true

false

true

true

true

false

 

Solution to Exercise 2.1.1.5

  1. Inclusive.
  2. Exclusive.
  3. Inclusive.
  4. 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 karmic37 sense.

Solution to Exercise 2.2.1.1

a

b

c

(a ⇒ (bc))

((ab) ⇒ 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 right-most columns, we see that the formulas are indeed not equivalent. They have different values for two truth-settings, 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 ¬ (ab) ∧ (ab). Is this equivalent to the WFF a ∧¬b ∨¬ab? Here is a truth table:

Table 2.10 Truth table for comparing conditionals' equivalence

a

b

¬ (ab)

(ab)

(¬ (ab) ∧ (ab))

(a ∧ ¬b)

ab)

((a ∧ ¬b) ∨ (¬ab))

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: 2n 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 2n rows and a total of 22n different functions. That's a lotl

Solution to Exercise 2.3.1.1

1

a ∧ (ab) ⇒ b

 

2

a ∧ (¬ab) ⇒ b

Definition of ⇒

3

a ∧ ¬aabb

Distributivity of ∨ over ∧

4

≡ false ∨ abb

Complement

5

ab ∨ false ⇒ b

Commutativity of ∨

6

abb

Identity of ∨

7

≡ ¬ (ab) ∨ b

Definition of ⇒

8

≡ ¬a ∨ ¬bb

DeMorgan's law

9

≡ ¬a ∨ ¬bb

Associativity of ∨

10

≡ ¬ab ∨ ¬b

Commutativity of ∨

11

≡ ¬a ∨ true

Complement

12

≡ true

Dominance of ∨

Solution to Exercise 2.3.1.2

1

(ab) ∧ b

 

2

≡ (ab) ∧ (b ∨ false)

Identity of ∨

3

≡ (ba) ∧ (b ∨ false)

Commutativity of ∨

4

ba ∧ false

Distributivity of ∨ over ∧

5

b ∨ false

Dominance of ∧

6

b

Identity of ∨

Solution to Exercise 2.3.2.1

  • CNF: (ab) ∧ (¬abc) ∧ (¬a ∨¬b)
  • DNF: (¬ab) ∨ (a ∧¬bc)

ASIDE: Karnaugh maps38 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:

Table 2.11 Truth table to prove validity of conjunctive Redundancy

a

b

¬ab

a ∧ (¬ab)

ab

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 \phi \vdash \psi, then that means there is some written proof... we know \vdash \phi \Rightarrow \psi, simply by

\Rightarrow intro.

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 policy-makers and courts debate.

Solution to Exercise 2.5.2

" Terry claims that encouraging human-rights is more important than playing Tetris. But Terry played Tetris yesterday rather than volunteering with Amnesty International39 . " 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

  1. It can be socially acceptable to wear my swimsuit into a fast-food 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 communication-through-style include team logos, t-shirts with humorous slogans, and arm bands.)
  2. Buses are a lot cheaper than light rail. Yet, the light-rail 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

  1. r ∧¬q
  2. rp 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. 3. pqr

Solution to Exercise 2.5.7

Poppins Mary

Solution to Exercise 2.5.10

  1. There are many simple answers, such as Y − has − 1, ¬W − has − 1, ...
  2. 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

Table 2.12 Truth table for xnor

\phi

\psi

\phi xnor\psi

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 if-and-only-if (Example 2.1).

If you said something like "the both-or-neither 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 meta-variables δ and E rather than re-using φ 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:\phi\vdash false

   

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:\dashv \dashv \left ( P-safe\wedge W-safe \right )\vdash false

 

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:\dashv \dashv \left ( R-safe\wedge W-safe \right )\vdash false

 

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.c-7.f and 9.c-9.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.

Note: Interestingly, we didn't need to use R − safe as a premise. (In fact, we nearly proved that ¬R − safe would have been inconsistent with the other premises.)

Solution to Exercise 2.6.16

1

¬¬φ

 

Premise

2

subproof:\dashv \phi\vdash false

   

2.a

 

¬φ

Premise for subproof

2.b

 

false

falseIntro, lines 1,2.a

3

φ

 

RAA, line 2