Computer Science 260

Assignment 4

1. Give a formal derivation of ∃xP(x) ∨ ∀xQ(x) given the premise

∀x(P(x) ∨ Q(x)). State the laws of inference used and the lines involved in your

derivation. You may use U.I, U.G. and the deduction theorem as well as the other laws

of equivalence or inference.

2. There are two rules of inference regarding the universal quantifier, namely UI, which

removes the universal quantifier, and UG, which adds the universal quantifier. There

are similarly two rules regarding the existential quantifier, namely EI and EG, which

remove, respectively add the existential quantifier. EI always creates a new variable,

which we will call existential variable. The rules UI, UG, EI and EG must obey the

following restrictions.

Illegal Substitution (IS) U.I. is illegal if a free variable is converted into a bound

variable, e.g. ∀x∃yP(x, y) does not allow one to conclude ∃yP(y, y).

UG over a committed variable (CV) If a variable appears free in any premise, it

is committed, and one is not allowed to generalize over committed variables. For

instance, if P(x) is a premise, x is committed, and one is not allowed to conclude

from Q(x) that ∀xQ(x) is true.

UG over a existential variable (EV) One is not allowed to generalize over a variable created by existential instantiation.

Previous use of EI variable (EIV) A variable created by existential instantiation

must not have been used as a free variable in any previous statement, or in any

premise.

EI in the presence of free variables (EIFV) One must not use EI for any expression containing free variables. For instance, ∃xQ(x, y) does not usually imply

Q(a, y).

All of the following derivations violate one of these restrictions. For each indicate the

first line where a violation occurs, and state the type of the restriction violated, using

the abbreviations IS, CV, EV, EIV or EIFV. Also state whether or not the conclusion

follows logically from the premises. If it does, redo the proof.

From premise ∃xP(x) ∧ ∃x∃yQ(x, y) conclude ∃x∃y(P(x) ∧ Q(x, y))

Statement Justification

1. ∃xP(x) ∧ ∃x∃yQ(x, y) premise

2. ∃xP(x) 1, specialization

3. ∃x∃yQ(x, y) 1, specialization

4. P(x) 2, E.I.

5. ∃yQ(x, y) 3, E.I.

6. Q(x, y) 5, E.I.

7. P(x) ∧ Q(x, y) 4,6 Conjunction

8. ∃y(P(x) ∧ Q(x, y)) 7, E.G.

9. ∃x∃y(P(x) ∧ Q(x, y)) 8, E.G.

From premise ∃xP(x) ∧ ∼(∃y(P(y) ∧ Q(y))) conclude ∼ ∃xQ(x)

Statement Justification

1. ∃xP(x) ∧ ∼(∃y(P(y) ∧ Q(y))) premise

2. ∃xP(x) 1, specialization

3. ∼(∃y(P(y) ∧ Q(y))) 1, specialization

4. ∀y ∼(P(y) ∧ Q(y)), 3, negation of ∃

5. ∀y(∼P(y) ∨ ∼Q(y)) 4, De Morgan

6. P(x) 2, E.I.

7. ∼P(x) ∨ ∼Q(x) 5, U.I.

8. ∼Q(x) 6,7 elimination

9. ∀x ∼Q(x) 8, U.G.

10. ∼ ∃xQ(x) 9, negation of ∃

From premise ∀z∃xQ(x, z) conclude ∀zQ(z, z)

Statement Justification

1. ∀z∃xQ(x, z) premise

2. ∃xQ(x, x) 1, U.I.

3. Q(z, z) 2, E.I.

4. ∀zQ(z, z) 3, U.G.

From premise ∀yP(y) ∧ ∃xQ(x) conclude ∼ ∀z(P(z) →∼Q(z))

Statement Justification

1. ∀yP(y) ∧ ∃xQ(x) premise

2. ∀yP(y) 1, specialization

3. ∃xQ(x) 1, specialization

4. P(z) 2, U.I.

5. Q(z) 3, E.I.

6. P(z) ∧ Q(z) 4,5 conjunction

7. ∼(∼P(z) ∨ ∼Q(z)) 6, De Morgan, double negation

8. ∃z ∼(∼P(z) ∨ ∼Q(z)) 7,E.G.

9. ∼ ∀z(∼P(z) ∨ ∼Q(z)) 8, Negation of ∀

10. ∼ ∀z(P(z) →∼Q(z)) 9, introduction of conditional