
Introduction to Logic

Tools for Thought

Evaluation for Relational Logic is similar to evaluation for Propositional Logic. The only difference is that we need to deal with quantifiers. In order to evaluate a universally quantified sentence, we check that all instances of the scope are true. (We are in effect treating it as the conjunction of all those instances.) In order to evaluate an existentially quantified sentence, we check that at least one instance of the scope. (We are in effect treating it as the disjunction of those instances.)

Assume we have a language with a unary relation constant p, a binary relation constant q, and object constants a and b; and consider our truth assignment from the last section.
p(a)  →  1 
p(b)  →  0 
q(a,a)  →  1 
q(a,b)  →  0 
q(b,a)  →  1 
q(b,b)  →  0 

What is the truth value of the sentence ∀x.(p(x) ⇒ q(x,x)) under this assignment? There are two instances of the scope of this sentence. See below.
(p(a) ⇒ q(a,a)) 
(p(b) ⇒ q(b,b)) 
We know that p(a) is true and q(a,a) is true, so the first instance is true. q(b,b) is false, but so is p(b) so the second instance is true as well.
(p(a) ⇒ q(a,a))  →  1 
(p(b) ⇒ q(b,b))  →  1 
Since both instances are true, the original quantified sentence is true as well.
∀x.(p(x) ⇒ q(x,x)) → 1

Now let's consider a case with nested quantifiers. Is ∀x.∃y.q(x,y) true or false for the truth assignment shown above? As before, we know that this sentence is true if every instance of its scope is true. The two possible instances are shown below.

To determine the truth of ∃y.q(a,y), we must find at least one instance of q(a,y) that is true. The possibilities are shown below.
Looking at our truth assignment, we see that the first of these is true and the second is false.
Since one of these instances is true, the existential sentence as a whole is true.
∃y.q(a,y) → 1

Now, we do the same for the second existentially quantified. The possible instances in this case are shown below.
Of these, the first is true, and the second is false.
Again, since one of these instances is true, the existential sentence as a whole is true.
∃y.q(b,y) → 1

At this point, we have truth values for our two existential sentences.
∃y.q(a,y) → 1 
∃y.q(b,y) → 1 
Since both instances of the scope of our original universal sentence are true, the sentence as a whole must be true as well.
∀x.∃y.q(x,y) → 1

Use the arrow keys to navigate.
