Reasoning: An Introduction to Logic, Sets, and Functions

Subsection 4.4.3 Validity and Satisfiability in Predicate Logic

Are there analogous definitions for predicate logic sentences? When we start to write proofs (which we’re about to do), we’ll want to be able to say that we’ve proved that a sentence must be true “no matter what”. In other words, that it’s valid.

We can start the same way:

• A predicate logic sentence w is valid if it is true in all interpretations. In other words, it is true regardless of what the constant, function, and predicate symbols “mean”.

• A predicate logic sentence w is satisfiable if there exists some interpretation in which w is true.

• A predicate logic sentence is unsatisfiable (i.e., it is a contradiction) if it is not satisfiable (in other words, there exists no interpretation in which it is true). As before, we note that any sentence w is valid just in case ¬w is unsatisfiable.

But now things change. There is no longer any guarantee that we can write out a finite sized truth table that enumerates all the possible interpretations. It’s true that we’ll only have a finite set of predicates. And each predicate, when applied to a particular value or set of values (for example, Bear(Smokey)) must evaluate to one of the two values, T or F. But there may be a very large, or even infinite, domain from which the values can be chosen. And what the predicate evaluates to typically depends on the values to which it’s applied. For example, we’ll generally assert that Bear(Smokey) is true but Bear(Bambi) is not.

So, while validity and satisfiability are as important now as they were in Boolean logic, the techniques that we’ll use to prove them will have to be different. What we’ll see, in the next section of this course, is that while we can’t build on the truth table techniques that served us well in Boolean logic, we can build on the natural deduction approach that we described at the end of our Boolean logic discussion.

Consider:

[1] \(\forall \) x (P(x) \(\rightarrow \) (P(x) \(\vee \) Q(x)))

It’s straightforward, in Boolean logic, to show that p \(\rightarrow \) (p \(\vee \) q) is a tautology. We’ll import into our predicate logic reasoning engine all of the rules that let us do that. Then we’ll add new rules that will let us argue that this claim must be true for any individual x and so it must be true for all x. This is so, regardless of what P or Q means. So [1] is a tautology. Alternatively, it is valid. It is, of course, also satisfiable since, being true in all interpretations, it is true in at least one of them.

Next, consider:

[2] \(\neg \)(\(\forall \)x (P(x) \(\vee \) \(\rightarrow \)P(x)))

Again, let’s exploit our Boolean inference rules. For any individual x, either P is true of it or P is true of it (remember the Law of the Excluded Middle). So, without the negation, [2] would be valid. Since that means it’s true in all interpretations, the negation of it cannot be true in any. So [2] is unsatisfiable.

Finally, consider:

[3] \(\forall \)x (P(x, x))

[3] is not valid but it is satisfiable. Suppose that the universe is the integers and P is the predicate LessThanOrEqualTo. Then P is true for all values of x. But, again with the integers as the universe, suppose that P is the predicate LessThan. Now P is false for all values of x (you can’t be less than yourself). Finally, let the universe be the set of all people and let P be the predicate HasConfidenceInTheAbilityOf. Now P is true of some values of x (i.e., of those people who have self-confidence) and false of others