# Logic Text Chapter 4 Solutions

## Chapter 4: Trees Basic

### Basic

Question {4.1}

You should get exactly the same answers as you got with truth tables. Here are the solutions for the exercises in Questions {3.2} and {3.4}. First, the formulas from {3.2}

1.

 ~(p ⊃ ((p ⊃ q) ⊃ q)) | p ~((p ⊃ q) ⊃ q) | p ⊃ q ~ q / \ ~ p q X X

The tree closes, so the formula is a tautology.

2.

 ~ (p ∨ (p ⊃ q)) | ~ p ~ (p ⊃ q) | p ~ q X

The tree closes, so the formula is a tautology.

3.

 ~((p & (p ⊃ q)) ⊃ q) | p & (p ⊃ q) ~ q | p p ⊃ q / \ ~ p q X X

The tree closes, so the formula is a tautology.

4.

 ~(((p & q) ⊃ r) ⊃ (p ⊃ r)) | (p & q) ⊃ r ~(p ⊃ r) | p ~ r / \ ~(p & q) r / \ X ~ p ~ q X ^ open

The tree is open. A countermodel is as follows:

p = 1 q = 0 r = 0

This makes the premise true and the conclusion false. The argument is invalid.

5.

 ~((p ⊃ q) ⊃ p) ⊃ p) | (p ⊃ q) ⊃ p ~ p / \ ~(p ⊃ q) p | X p ~ q X

The tree is closed, the formula is a tautology.

Now the argument forms from {3.4}

1.

 p p ⊃ q ~ q / \ ~ p q X X

The tree closes, the argument form is valid.

2.

 p q ~(p ≡ q) / \ p ~ p ~ q q X X

The tree closes, the argument form is valid.

3.

 p & q ~(p ≡ q) | p q / \ p ~ p ~ q q X X

The tree is closed. The argument form is valid.

4.

 p q ⊃ p ~ q / \ ~ q p ^ ^ open open

The tree remains open. A countermodel p = 1 and q = 0 makes the premises true and the conclusion false.

The argument form is invalid.

5.

 p q ~(p & q) / \ ~ p ~ q X X

The tree is closed. The argument form is valid.

6.

 p ~(p ∨ q) | ~ p ~ q X

The tree is closed. The argument form is valid.

7.

 p ≡ q p ≡ ~ q ~~ p | p / \ p ~ p q ~ q / \ X p ~ p ~ q ~~ q X X

The tree is closed, the argument form is valid.

8.

 p ⊃ (q ⊃ r) ~(q ⊃ (p ⊃ r)) | q ~(p ⊃ r) | p ~ r / \ ~ p q ⊃ r X / \ ~ q r X X

The tree closes, the argument form is valid.

9.

 p ⊃ ~ p ~~ p / \ ~ p ~ p X X

The tree closes, the argument form is valid.

10.

 ~~ p ~ p X

The tree closes, the argument form is valid.

11.

 p ⊃ q ~((r ⊃ p) ⊃ (r ⊃ q)) | r ⊃ p ~(r ⊃ q) | r ~ q / \ ~ p q / \ X ~ r p X X

The tree closes. The argument form is valid.

12.

 p ⊃ q ~(~ q ⊃ ~ p) | ~ q ~~ p / \ ~ p q X X

The tree closes, the argument form is valid.

13.

 p ~(~ p ⊃ q) | ~ p ~ q X

The tree closes, the argument form is valid.

14.

 p ⊃ (p ⊃ q) ~(p ⊃ q) | p ~ q / \ ~ p p ⊃ q X X

The tree closes, the argument form is valid.

Note that we can close the right branch using pq and its negation. There is no need to resolve the formula pq.

15.

 p ~(q ⊃ q) | q ~ q X

The tree closes, the argument form is valid.

16.

 p ∨ q ~ q ∨ r ~ (p ∨ r) | ~ p ~ r / \ p q X / \ ~ q r X X

The tree closes, the argument form is valid.

17.

 p ⊃ q ~(q ⊃ p) | q ~ p / \ ~ p q ^ ^ open open

The tree is open.

The counterexample p = 0 and q = 1 makes the premises true, and the conclusion false.

So, the argument is invalid.

18.

 p ⊃ (q ⊃ r) ~((p ⊃ q) ⊃ r) | p ⊃ q ~ r / \ / \ / \ ~ p q ⊃ r / \ / \ ~ p q ~ p q ^ ^ / \ / \ ~ q r ~ q r ^ X X X

The tree is open (see any of the branches marked with `^’). Any evaluation of the propositions with p and r false (see the first branch) will make the premises true and the conclusion false. So:

p = 0 q = 0 r = 0

p = 0 q = 1 r = 0

are both countermodels.

The argument is invalid.

19.

 (p & q) ⊃ r ~(p ⊃ (~ q ∨ r)) | p ~(~ q ∨ r) | ~~ q ~ r / \ ~ (p & q) r / \ X ~ p ~ q X X

The tree closes, the argument form is valid.

20.

 p ⊃ q r ⊃ s ~((q ⊃ r) ⊃ (p ⊃ s)) | q ⊃ r ~(p ⊃ s) | p ~ s / \ ~ p q X / \ ~ q r X / \ ~ r s X X

The tree is closed. The argument form is valid.

Question {4.2}

An exclusive disjunction A x B is true when A is true and B isn’t, or when B is true and A isn’t. So the rule for an exclusive disjunction should be:

 A x B / \ A ~ A ~ B B

If you get a negated exclusive disjunction, you have a different rule. A x B is false when A and B are both true, or when they are both false. So, you get:

 ~(A x B) / \ A ~ A B ~ B

Question {4.3}

The Sheffer Stroke A | B is false when A and B are both true, and true otherwise. The negated rule is easiest.

 ~(A | B) | A B

The formula A | B is true just when either A is false, or B is false. So you can use the rule:

 A | B / \ ~ A ~ B