Exercise 8.1 - Validity, Contingency, and Unsatisfiability
Say whether each of the following sentences is valid, contingent, or unsatisfiable.
a.
∀x.p(x) ⇒ ∃x.p(x)
If ∀x.p(x) is true, then p must true of every element in the Herbrand universe. Consequently, there must be at least one element for which p is true and so ∃x.p(x) must be true. (Note that the Herbrand universe must always contain at least one element.) Since the consequent is true whenever the antecedent is true, the implication as a whole is valid.
b.
∃x.p(x) ⇒ ∀x.p(x)
Consider a world with two objects (named a and b), and consider the truth assignment shown below. In this case, the antecedent is true and the consequent is also true. Hence the sentence as a whole is true.
p(a)
→
1
p(b)
→
1
Now consider the following truth assignment. In this case, the antecedent is true, but the consequent is false. Hence the sentence as a whole is false.
p(a)
→
0
p(b)
→
1
Since there is one truth assignment that makes the sentence true and another that makes it false, the sentence is contingent.
c.
∀x.p(x) ⇒ p(x)
This sentence is equivalent to ∀x.(∀x.p(x) ⇒ p(x)), which is equivalent to ∀x.p(x) ⇒ ∀x.p(x), and this sentence is always true.
d.
∃x.p(x) ⇒ p(x)
This sentence is equivalent to ∀x.(∃x.p(x) ⇒ p(x)), which is equivalent to ∃x.p(x) ⇒ ∀x.p(x), and this sentence might be true but also might be false.
e.
p(x) ⇒ ∀x.p(x)
Consider a world with two objects (named a and b), and consider the truth assignment shown below.
p(a)
→
0
p(b)
→
1
By definition, a sentence with a free variable is true if an only if all instances are true. In order for p(x) ⇒ ∀x.p(x) to be true in the truth assignment just mentioned, the following instances must be true.
p(a) ⇒ ∀x.p(x)
p(b) ⇒ ∀x.p(x)
Since p(a) is false, the first of these instances is true. Unfortunately, the second instance is false, since p(b) is true but ∀x.p(x) is false.
Of course, there are other truth assignments in which the sentence is true, e.g. one where p(a) and p(b) are both true. Since the sentence is sometimes true and sometimes false, it is contingent.
Another way to understand this is to realize that (p(x) ⇒ ∀x.p(x)) is equivalent to the sentence ∀x.(p(x) ⇒ ∀x.p(x)), and this is equivalent to (∃x.p(x) => ∀x.p(x)). The fact that ∃x.p(x) is true does not in general mean that ∀x.p(x) is true.
f.
p(x) ⇒ ∃x.p(x)
This sentence is equivalent to ∀x.(p(x) ⇒ ∃x.p(x)). This is equivalent to ∀x.(¬p(x) ∨ ∃x.p(x)). This is equivalent to ∀x.¬p(x) ∨ ∃x.p(x). This is equivalent to ¬∃x.p(x) ∨ ∃x.p(x). This is equivalent to ∃x.p(x) ⇒ ∃x.p(x). And this sentence is always true.
g.
∀x.∃y.p(x,y) ⇒ ∃y.∀x.p(x,y)
Consider the truth assignment shown below. Given this truth assignment, the antecedent is true, but the consequent is false. Therefore, the implication as a whole is false.
p(a,a)
→
0
p(a,b)
→
1
p(b,a)
→
1
p(b,b)
→
0
Now consider the truth assignment shown below. In this case, both the antecedent and the consequent are true; hence the implication as a whole is true.
p(a,a)
→
0
p(a,b)
→
1
p(b,a)
→
0
p(b,b)
→
1
Since there is a truth assignment in which the implication is true and there is a truth assignment in which it is false, the sentence is contingent.
h.
∀x.(p(x) ⇒ q(x)) ⇒ ∃x.(p(x) ∧ q(x))
Consider the truth assignment shown below. Given this truth assignment, the antecedent is true, and the consequent is true. Therefore, the implication as a whole is true.
p(a)
→
1
p(b)
→
0
q(a)
→
1
q(b)
→
0
Now consider the truth assignment shown below. In this case, the antecedent is true but the consequent is false; hence the implication as a whole is false.
p(a)
→
0
p(b)
→
0
q(a)
→
0
q(b)
→
0
Since there is a truth assignment in which the implication is true and there is a truth assignment in which it is false, the sentence is contingent.
i.
∀x.(p(x) ⇒ q(x)) ∧ ∃x.(p(x) ∧ ¬q(x))
The first conjunct tells us that, if p is true of an object, then q is also true. The second conjunct tells us that there is an object for which p is true but q is false. These two conditions cannot be satisfied by any truth assignment, so the sentence is unsatisfiable.
Consider a world with two objects (named a and b), and consider the truth assignment shown below. In this case, the antecedent is true and the consequent is also true. Hence the sentence as a whole is true.
p(a)
→
1
p(b)
→
1
Now consider the following truth assignment. In this case, the antecedent is true, but the consequent is false. Hence the sentence as a whole is false.
p(a)
→
0
p(b)
→
1
Since there is one truth assignment that makes the sentence true and another that makes it false, the sentence is contingent.
j.
(∃x.p(x) ⇒ ∀x.q(x)) ∨ (∀x.q(x) ⇒ ∃x.r(x))
This sentence matches the pattern (φ ⇒ ψ) ∨ (ψ ⇒ χ). If ψ is true, then the first disjunct is true. If ψ is false, then the second disjunct is true. Consequently, the disjunction as a whole is always true.
