Computer Science 260 Assignment 4

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