Disambiguate Expressions with Quantifier Elimination
Consider the following sentence:
If anyone loves someone, then John is bald.
And let's fix the following dictionary for the purposes of evaluating this sentence in standard FOL:
D: {a, j}
a: Alex
j: John
L_ _: _ loves _
B_: _ is bald
When translating into our language, note there are at least two plausible candidate translations (I will use “V” for universal quantifiers and “E” for existentials):
(1) VxEyLxy -> Bj
(2) Vx(EyLxy -> Bj)
These are not logically equivalent. The main connective of (1) is a material conditional. The main connective of (2) is a universal quantifier. We might express the difference in English as:
(1') If anyone loves someone then John is bald
(2') Out of anyone, if that person loves someone then John is bald
These still might sound rather similar. They are nevertheless distinct, as can perhaps be shown by the fact that (1) and (2), and so presumably (1*) and (2*), have different truth-values when comparing interpretations.
For our purposes, an interpretation is a dictionary combined with a visual diagram representing elements of the domain as satisfying some, all, or none of the dictionary elements. Recall, we can show two sentences are not logically equivalent in our language with respect to a given dictionary, by providing an interpretation where one is true while the other is false. This should sound familiar, since we had a similar procedure when we didn't have quantifiers in the language. There we observed two sentences to be logically equivalent just in case they had the same truth table assignments. Indeed, interpretations are analogous to truth tables in this way, enough to make the following statements:
In propositional logic, expression A is logically equivalent to expression B if and only if A and B are true in all and only the same truth table rows
In quantifier logic, expression A is logically equivalent to expression B if and only if A and B are true in all and only the same interpretations
This is just to say that if (1) and (2) are distinct, as I claim they are, then there is at least one interpretation in which one of the pair is true and the other is false.
This, however, might not be easy to see given how similar the expressions are. At this point, it will be useful to practice an expansion technique for evaluating the truth or falsity of quantifier expressions. To see how this works, note that in finite domains - the only sort of domain you'll be working with in this class - universal quantifiers are just conjunctions while existentials are simply disjunctions. More specifically, consider the following dictionary:
D: {a, j}
j: John
a: Alex
B_: _ is bald
Now observe the following are true:
"VxBx" can be replaced with "Ba & Bj"
"ExBx" can be replaced with "Ba v Bj"
This should seem intuitive. Since the domain consists only of Alex and John, if we say something about everything in the domain, that simply means we're saying something about Alex and John. Similarly, if we say something about someone in the domain, that means we're saying something about Alex or John.
To see how this helps with our motivating ambiguity, return to our initial dictionary:
D: {a, j}
a: Alex
j: John
L_ _: _ loves _
B_: _ is bald
And expressions:
(1) VxEyLxy -> Bj
(2) Vx(EyLxy -> Bj)
Starting with (1), we replace the universal, then existential:
(1*) Ey(Lay & Ljy) -> Bj
(1**) ((Laa \/ Laj) & (Lja \/ Ljj)) -> Bj
Consider next expansion of (2):
(2*) (EyLay -> Bj) & (EyLjy -> Bj)
(2**) ((Laa \/ Laj) -> Bj) & ((Lja \/ Ljj) -> Bj)
To see how these come apart, let the following be true in our interpretation:
~Bj & ~Laa & ~Laj & Lja & Ljj
In (1**), since Laa and Laj are false, then the left-hand side of the conjunction in the antecedent is false, which means the antecedent is false, so (1**) is vacuously true. On the other hand, in (2**) we have a vacuously true left-hand side of the conjunction, but the right-hand side has a true antecedent and false consequent. Hence, (2**) is false.
We have, then, found an interpretation where (1) is true and (2) is false. That’s sufficient to show they're not logically equivalent. Hopefully, this has also gone some way in illustrating how (1') and (2') are distinct in natural language. It might be worth reviewing the respective sentences with the preceding interpretations in mind.