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
/\
~ pq
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
/\
~ pq
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
/\
~ pq
X X

The tree closes, the argument form is valid.

2.

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

The tree closes, the argument form is valid.

3.

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

The tree is closed. The argument form is valid.

4.

p
q ⊃ p
~ q
/\
~ qp
^^
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
/\
~ pq ⊃ r
X /\
~ qr
XX

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
/\
~ pq
/\X
~ rp
X X

The tree closes. The argument form is valid.

12.

p ⊃ q
~(~ q ⊃ ~ p)
|
~ q
~~ p
/\
~ pq
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
/\
~ pp ⊃ q
X X

The tree closes, the argument form is valid.

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

15.

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

The tree closes, the argument form is valid.

16.

p ∨ q
~ q ∨ r
~ (p ∨ r)
|
~ p
~ r
/\
pq
X /\
~ qr
XX

The tree closes, the argument form is valid.

17.

p ⊃ q
~(q ⊃ p)
|
q
~ p
/\
~ pq
^^
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
/\
/\
/\
~ pq ⊃ r
/\/\
~ pq~ pq
^^/\/\
~ qr~ qr
^X XX

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
/\
~ pq
X /\
~ qr
X/\
~ rs
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
~ BB

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