Solutions to selected exercises cos3761 PDF

Preview

Summary

Download Solutions to selected exercises cos3761 PDF

Description

ADDITIONAL NOTES FOR COS3761 – PART E SOLUTIONS TO SELECTED EXERCISES Chapter 1

Exercises 1.1 (p. 78)

1 (f)

Declarative sentence: “If interest rates go up, share prices go down” If we choose: p: "Interest rates go up". q:

"Share prices go down”.

the formula representing the above declarative sentence is

p→q

1(i) Declarative sentence: “If Dick met Jane yesterday, they had a cup of coffee together, or they took a walk in the park.” If we choose the proposition atoms as follows p: "Dick met Jane yesterday.” q:

"Dick and Jane had a cup of coffee together."

r:

"Dick and Jane had a walk in the park."

the resulting formula is: p→q∨r which reads as p → (q ∨ r) when we recall the binding priorities of the logical connectives.

2(c)

(p → q) →(r →(s ∨ t))

2(g)

The expression p ∨ q ∧ r is problematic since ∨ and ∧ have the same binding priorities, so we have to insist on additional brackets in order to resolve the conflict.

Exercises 1.2 (p. 78)

1(a) The proof of the validity of (p ∧ q) ∧ r, s ∧ t ⊢ q ∧ s is a straight-forward application of the rules that you know from Formal Logic 2:

1(x)

1

(p ∧ q) ∧ r

premise

2

s∧t

premise

3

p∧q

∧ e1 1

4

q

∧ e2 3

5

s

∧ e1 2

6

q∧s

∧ i 4, 5

We have to prove the validity of p → (q ∨ r), q → s, r → s ⊢ p → s.

We again apply the rules you know from Formal Logic 2, but make a few comments. Because the main connective of the goal is the implication →, we open a subproof box in line 4 with the assumption of the left hand side of the goal, namely p. The subproof ends with the right hand side of the goal (line 10) and then the → introduction rule is used in line 11 after the subproof box was exited. We require two subproofs (lines 6 to 7 and lines 8 to 9) so that the ∨ elimination rule can be used in line 10. Also note how the → elimination rule is used (lines 5, 7 and 9). If the application of these rules is not clear, work through the rules given in the prescribed book for Formal Logic 2 again. 1

p → (q ∨ r)

premise

2

q→s

premise

3

r→s

premise

4

p

assumption

5

q∨r

→ e 1, 4

6

q

assumption

7

s

→ e 2, 6

8

r

assumption

9

s

→ e 3, 8

10

s

∨ e 5, 6 – 7, 8 – 9

11

p→s

→ i 4 – 10

2(b)

We prove the validity of ¬p ∨ ¬q ⊢ ¬(p ∧ q) as follows: 1

¬p ∨ ¬q

premise

2

p∧q

assumption

3 4 5

¬p p ⊥

assumption ∧1 e 2 ¬ e 4, 3

6 7 8

¬q q ⊥

assumption ∧2 e 2 ¬ e 7, 6

9

⊥

∨ e 1, 3 – 5, 6 – 8

10

¬ (p ∧ q)

¬i 2–9

As you can see, we assume the negation of the goal in line 2 (the first statement of the outer assumption box) and derive the contradiction in line 9 (the last statement of this subproof) so that the goal can be derived in line 10 after the subproof box has been exited by using the ¬ introduction rule. Also note how the ∨ elimination rule is applied: we need two separate assumption boxes (lines 3 to 5 and lines 6 to 8), each box starting with one of the disjuncts of the formula in line 1 and each box ending on the same formula which is then derived in line 9 after the second assumption box has been exited. Note that all this happens inside the outer subproof box. Remember that the ¬ e rule was called the ⊥ Intro rule in Formal Logic 2 but the same requirements apply.

2(e)

We prove the validity of p → (q ∨ r), ¬q, ¬r ⊢ ¬p as follows: 1 2 3

p → (q ∨ r) ¬ q ¬ r

premise premise premise

4 5

p q∨r

assumption → e 1, 4

6 7

q ⊥

assumption ¬ e 6, 2

8 9

r ⊥

assumption ¬ e 8, 3

10

⊥

∨ e 5, 6 – 7, 8 – 9

11 ¬ p •

¬ i 4 – 10

The proof is very similar to the proof in question 2(b) above (assumption of negation of the goal and use of the ∨ e rule thereby requiring two sub-subproofs).

•

Please note how the → e rule is applied (line 5): the right hand side of an implication is derived if the left hand side appears on an earlier line.

3(q)

We prove the validity of ⊢ (p → q) ∨ (q → r) as follows: 1

q∨¬q

LEM

2

q

assumption

3 4

p q

assumption copy 2

5 6

p→q (p → q) ∨ (q → r)

→i 3–4 ∨ i1 5

7

¬q

assumption

8 9 10

q ⊥ r

assumption ¬ e 8, 7 ⊥e 9

11 12

q→r (p → q) ∨ (q → r)

→ i 8 – 10 ∨ i2 11

13

(p → q) ∨ (q → r)

∨ e 1, 2 – 6, 7 – 12

Note that all the subproofs are essential. Most of the rules which are used above have been explained in the previous exercises except the ∨ i rule that are used in lines 6 and 12. The ∨ introduction rule is very simple: once a formula has been derived any formula may be connected to it with the ∨ connective.

5(d) We have to prove the validity of ⊢ (p → q) → ((¬ p → q) → q). You will find nothing new in the proof given below. Note, however, again, that a new subproof box has to be opened whenever an assumption is made. 1

p → q

assumption

2

¬p → q

assumption

3

p ∨ ¬p

LEM

4 5

p q

assumption → e 1, 4

6 7

¬p q

assumption → e 2, 6

8

q

∨ e 3, 4 – 5, 6 – 7

9

(¬ p → q) → q

→i 2– 8

10

(p → q) → ((¬ p → q) → q)

→i 1–9

Exercises 1.3 (p. 81)

1(c) In order to draw the parse tree for the formula, we have to determine the main connective. Since ∧ binds more strongly than →, we could re-write this formula as (p ∧ ¬ q) → ¬ p This shows that the main connective of this formula is →, which places it at the root of the parse tree, shown below: →

∧

p

¬

¬

p

q

The height of this parse tree is 1 + 3 = 4, since the longest path from root to leaf is 3.

4(b)

Here, parentheses are used to override the binding priorities of the connectives, making the last ∨ the main connective of the formula. The parse tree, whose height is 1 + 5 = 6, is shown below:

∨

¬

→

∨

s

→

p

r

∧

¬

p

r

q

By definition, a formula φ is a subformula of another formula 𝜓 if and only if the formation tree of formula φ appears as a subtree of the formation tree of formula 𝜓. The following is a list of all the subformulas of ((p → ¬ q) ∨ (p ∧ r) → s) ∨ ¬ r: p q r s ¬r ¬q (p → ¬q) (p ∧ r) (p → ¬q) ∨ (p ∧ r) ((p → ¬q) ∨ (p ∧ r) → s) ((p → ¬q) ∨ (p ∧ r) → s) ∨ ¬r The purpose of all the parentheses is to override precedence rules and binding orders. We can parse a fully parenthesized formula recursively and mechanically (i.e. we don't need to worry about the interpretation of the symbols). Parsing a wff lets us build a parse-tree for

the formula, in which the root node corresponds to the final rule that was applied in the building of the formula, and the leaves are the atomic propositions in the formula.

Exercises 1.4 (p. 82)

2(c)

The complete truth table for p ∨ (¬ (q ∧ (r → q))) is p T T T T F F F F

5

q T T F F T T F F

r T F T F T F T F

r →q q ∧ T T F T T T F T

(r →q) T T F F T T F F

¬(q

∧ (r →q)) F F T T F F T T

p ∨ (¬(q ∧ (r →q))) T T T T F F T T

The formula of the parse tree in figure 1.10 on page 44 is the following: ¬ ((q → ¬ p) ∧ (p → (r ∨ q))) We give the truth table below. p T T T T F F F F

q T T F F T T F F

r T F T F T F T F

¬p q→¬p r∨q p → (r∨q) (q → ¬p) ∧ (p→(r ∨q)) F F T T F F F T T F F T T T T F T F F F T T T T T T T T T T T T T T T T T F T T

¬((q→¬p)∧(p→(r ∨ q))) T T F T F F F F

The formula is not valid since it evaluates to F for several assignments. However, this formula is satisfiable: for example, if q and p evaluate to T then q → ¬p renders F and so the entire formula evaluates to T.

13(b)

An example is: Let p represent “There are clouds in the sky” and let q represent “It rains”. Then ¬p → ¬q holds (“if there are no clouds in the sky, then it does not rain”), but ¬q → ¬p is false (“if it does not rain, then there are no clouds in the sky”) because, as we know, there may well be clouds in the sky even if it does not rain.

Exercises 1.5 (p.87) 2 p T T T T F F F F

q T T F F T T F F

r T F T F T F T F

¬p ¬q ¬r ¬p∨r F F F F T T T T

F F T T F F T T

F T F T F T F T

T F T F T T T T

q∧ ¬r F T F F F T F F

p∧¬r F T F T F F F F

¬q ∧¬r F F F T F F F T

q∨ r T T T F T T T F

a T T T F T T T T

b T T T T T F T T

c T T T F T T T T

d T T T F T T T T

p→(q ∨ r) T T T F T T T T

As may be seen in the last five columns of the truth table below the formulas given in (a), (c) and (d) are semantically equivalent to p → (q ∨ r) but the formula given in (b) is not. The truth value of the formula given in (b) does not correspond to that of p → (q ∨ r) in lines 4 and 6 while the truth values of (a), (c) and (d) are identical to those of p → (q ∨ r) in all lines.

7(a)

We construct the formula φ1 in CNF as explained in section 1.5.1 in both the prescribed book and the additional notes: (¬p ∨ ¬q) ∧ (p ∨ ¬q) ∧ (¬p ∨ q) Note how these principal conjuncts correspond to the lines in the table where the φ1 entry is F.

15(g) Applying the HORN algorithm to (T → q) ∧ (T → s) ∧ (w → ⊥) ∧ (p ∧ q ∧ s → v) ∧ (v → s) ∧ (T → r) ∧ (r → p), firstly marks all occurrences of T (we indicate marking by underlining): (T → q) ∧ (T → s) ∧ (w → ⊥) ∧ (p ∧ q ∧ s → v) ∧ (v → s) ∧ (T → r) ∧ (r → p) Each Horn clause is now investigated: if everything to the left of → is marked, the right hand side is marked everywhere it appears. Thus: All occurrences of q, s, and r are marked in the first iteration of the while-loop: (T → q) ∧ (T → s) ∧ (w → ⊥) ∧ (p ∧ q ∧ s → v) ∧ (v → s) ∧ (T → r) ∧ (r → p) In the second iteration, both occurrences of p get marked: (T → q) ∧ (T → s) ∧ (w → ⊥) ∧ (p ∧ q ∧ s → v) ∧ (v → s) ∧ (T → r) ∧ (r → p) and in the third iteration v is marked: (T → q) ∧ (T → s) ∧ (w → ⊥) ∧ (p ∧ q ∧ s → v) ∧ (v → s) ∧ (T → r) ∧ (r → p) Nothing further can be marked. Because ⊥ is not marked, the Horn formula is satisfiable. (We allocate T to q, s, r, p and v, and F to w.)

Chapter 2

Exercises 2.1 (p. 157) 1 (a)

∀x(P(x) → A(m,x))

Remember that P(x) is not a term, so cannot be the argument of a predicate. (b)

∃x(P(x) ∧ A(x,m))

(d)

∀x(S(x) → (∃y(L(y) ∧ ¬B(x,y)))), or, equivalently, ¬∃x(S(x)∧∀y(L(y) → B(x,y))).

Exercises 2.2 (p. 158) ∃x 4(a)

∧

P

y

∀y

z

∨

¬

P

y

Q

y

x

z

4(b)

4(d)

From the parse tree of the previous item we see that all occurrences of z are free, all occurrences of x are bound, and the leftmost occurrence of y is free, whereas the other two occurrences of y are bound.

(i)

• φ [w/x] is simply φ again since there are no free occurrences of x in φ that could be substituted by w. • φ[w/y] is ∃x(P(w, z) ∧ (∀y(¬Q(y, x) ∨ P(y, z)))) since we replace the sole free occurrence of y with w. • If we simply replace the sole free occurrence of y with f(x), we get that φ [f(x)/y] is ∃x(P(f(x), z) ∧ (∀y(¬Q(y, x) ∨ P(y, z)))). Note, however, that we created a problem by this substitution because the variable x occurs in f(x) and after the substitution it occurs within the scope of ∃x. We should actually first rename x in the given formula by, say, u to get ∃u(P(y, z) ∧ (∀y(¬Q(y, u) ∨ P(y, z)))) and then do the substitution: ∃u(P(f(x), z) ∧ (∀y(¬Q(y, u) ∨ P(y, z)))). • If we simply replace all (free) occurrences of z with g(y, z) we get that φ [g(y, z)/z] is ∃x(P(y, g(y, z)) ∧ ∀y(¬Q(y, x) ∨ P(y, g(y, z)))). By doing this we again created a problem because the variable y occurs in g(y, z) and after the substitution it occurs within the scope of ∀y. We should actually first rename the bound occurrences of y in the given formula by, say, u to get ∃x(P(y, z) ∧ ∀u(¬Q(u, x) ∨ P(u, z)))) and then do the substitution: ∃x(P(y, g(y, z)) ∧

∀u(¬Q(u, x) ∨ P(u, g(y, z)))).

4(d)

(ii)

4(d)

(iii)

4(f)

All of them, for there are no free occurrences of x in φ to begin with.

The terms of w and g(y, z) are free for y in φ , but f(x) is not free for y in the formula since the x in f(x) would be captured by ∃x in that substitution process as noted above.

Now, the scope of ∃x is only the formula P(y,z) since the inner quantifier ∀x binds all occurrences of x (and overrides the binding of ∃x) in the formula (¬Q(x,x) ∨ P(x,z)).

Exercises 2.3 (p. 160)

7(c)

The proof of the validity of ∃x∀yP(x, y) ⊢ ∀y∃xP(x, y) is given below. This proof illustrates both the ∃ and ∀ introduction and elimination rules. We comment on that below the proof. 1 2 3 4 5

∃x∀yP(x, y)

premise

y0 x0

∀yP(x0, y) P(x0, y0) ∃xP(x, y0)

assumption ∀y e 3 ∃x i 4

6

∃xP(x, y0)

∃x e 1, 3 − 5

7

∀y∃xP(x, y)

∀y i 2 − 6

([x0/x])

We open a y0-box first, since we want to derive a formula of the form ∀y φ. Then we open an x0-box to be able to use ∃x e later on. Note how the elimination and introduction rules for both ∃ and ∀ are applied above:

∃ elimination: (i) a formula starting with ∃ (line 1), (ii) a new subproof box starting with the choice of a free variable which then substitutes the relevant variable in the formula now without ∃, namely ∀yP(x, y) (line 3), (iii) the subproof ends on a formula that does not contain the free variable (line 5), (iv) the ∃ e rule is cited outside the subproof (line 6) with the same formula on which the subproof ends in line 5. ∃ introduction: (i) a formula containing a free variable (line 4), (ii) the ∃ i rule is cited and ∃ is attached to the formula with the free variable replaced by the same variable that is attached to ∃ (line 5).

∀ elimination: (i) a formula starting with ∀ (line 3), (ii) the ∀ e rule is cited with the formula without the ∀ and the relevant variable replaced by a free variable y0 (line 4).

∀ introduction: (i) a subproof box starting with the choice of a free variable (line 2), (ii) the subproof ends on a formula containing the free variable (line 6), (iii), the ∀ i rule is cited outside the subproof (line 7) with the same formula on which the subproof ends in line 6, but with ∀ attached to it and the free variable replaced by the same variable that is attached to ∀.

9(d)

We prove the validity of ∀xP(x) → S ⊢ ∃x(P(x) → S) below. •

Note that we may not apply the ∀ elimination rule directly to the premise because ∀x is not in front of the whole rest of the formula, i.e. we do not have ∀x(P(x) →S). The

∀ elimination rule is applicable to formulas of the type ∀x φ only. •

This is not a simple proof and you will not generally be asked to give such a proof in an examination. However, it demonstrates the application of several rules. Make sure that you understand it. 1

∀xP(x) → S

premise

2

¬∃x(P(x) → S)

assumption

3

x0

4

¬P(x0)

5 6 7

P(x0) ⊥ S

assumption assumption ¬e 5, 4 ⊥e 6

8 9 10

P(x0) → S ∃x(P(x) → S) ⊥

→i 5–7 ∃x i 8 ¬e 9, 2

11 12

¬¬P(x0) P(x0)

¬i 4 – 10 ¬¬e 11

13 14

∀xP(x) S

∀x i 3 – 12 → e 1, 13

15 16

P(t) S

assumption copy 14

17 18 19

P(t) → S ∃x(P(x) → S) ⊥

→ i 15 – 16 ∃x i 17 ¬e 18, 2

20 21

¬¬∃x(P(x) → S) ∃x(P(x) → S)

¬i 2 – 19 ¬¬e 20

9(r)

We prove the validity of ¬∃xP(x) ⊢ ∀x¬P(x) as follows: 1

¬∃xP(x)

premise

2

x0

3 4 5

P(x0) ∃xP(x) ⊥

assumption ∃x i 3 ¬e 4, 1

6

¬P(x0)

¬i 3 – 5

7

∀x¬P(x)

∀x i 2 – 6

There is nothing new in this proof. We choose a free variable in line 2, thereby opening a new subproof box, so that the ∀x introduction rule can be cited once the subproof is exited (line 7). The “trick” to assume the negation of something that we want to prove is illustrated in the subproof from line 3 (where P(x0) is assumed) to line 5 (where the contradiction is derived) and then the ¬i rule is cited in the next line after this subproof box has been exited (i.e. line 6).

13(a)

We show the validity of ∀xP(a, x, x), ∀x∀y∀z(P(x, y, z) → P(ƒ(x), y, ƒ(z))) ⊢ P(ƒ(a), a, ƒ(a)) as follows: 1 2 3 4 5 6 7

∀xP(a, x, x) ∀x∀y∀z(P(x, y, z) → P(ƒ(x), y, ƒ(z))) P(a, a, a) ∀y∀z(P(a, y, z) → P(ƒ(a), y, ƒ(z))) ∀z(P(a, a, z) → P(ƒ(a), a, ƒ(z))) P(a, a, a) → P(ƒ(a), a, ƒ(a)) P(ƒ(a), a, ƒ(a))

premise premise ∀x e 1 ∀x e 2 ∀y e 4 ∀z e 5 → e 6, 3

Note that no subproofs are necessary for the application of the ∀elimination rule: any free variable may be used for the substitution.

Exercises 2.4 (p. 163)

1.

This formula ∀x∀yQ(g(x, y), g(y, y), z) contains a free variable z, thus we will also need a look-up table. First model M: We choose the universe of discrete values A to be the set of integers, the function gM (a, b) to be the result of subtracting b from a In this way g(y, y) is interpreted as 0) and the predicate Q M is interpreted to be such that a triple of integers (a, b, c) is in Q M if, and only if, c equals the product of a and b. Thus our formula says that, for all integers x and y, we have that (x – y) times 0 is equal to z. If we define lA(z) def 0, the formula holds in the above model. Second model M’: We choose this model identical to M above but define a different look-up table: let lA (z) def 1. The formula is now false.

12(g) The following model shows that the formula is...