∃x∀y∃z[Qx∧(My→Pyx)∧Wz ∧Pzx] ∨ ∃x[Qx∧∀y(My→Pyx)∧∃z(Wz∧Pzx)]?

September 6, 2009 10:28 AM

∃x∀y∃z[Qx∧(My→Pyx)∧Wz ∧Pzx] ∨ ∃x[Qx∧∀y(My→Pyx)∧∃z(Wz∧Pzx)] ?

1. ∃x∀y∃z[Qx∧(My→Pyx)∧Wz ∧Pzx]
2. ∃x[Qx∧∀y(My→Pyx)∧∃z(Wz∧Pzx)]

I’m fairly new to predicate logic. When writing it, I’m naturally drawn to getting all the quantifiers out of the way at the start of the relevant scope (as in 1), as opposed to embedding them within that scope (as in 2). As far as I can tell, 1 and 2 are logically equivalent, and so choosing between them is simply a matter of notational convention, readability, etc. I have some questions:

A: Am I right? Are 1 and 2 logically equivalent? If not, why not?
B: Is there any circumstance where doing things my way would cause a problem?
C: Any further advice/comments?

Thanks in advance!

PS: If needed, here is some further info:

Let’s say our universe/domain is: people and their qualities.
Qx: x is a quality.
Mx: x is a man.
Wx: x is a woman.
Pxy: x has quality y.

Assume I’m trying to say “There exists a person/quality that is a quality and found in every man and found in at least one woman.”

posted by ed\26h to religion & philosophy (9 comments total)

My own reading of this (and I'm no professional logician, but I've got enough of a CS background to know what you're saying here) is that those two statements are logically equivalent. I don't think doing things your way causes a problem, but it's harder to read. What you're saying, translated into English, goes something like:

"For some x, it's the case that for all y, there exists a z such that x is a quality, and if y is a man, y has the quality x, and z is a woman, and z has quality x."

The second one, translated, reads like this:

"For some x, x is a quality and for all y such that y is a man, y has quality x. Also, there exists some z where z is a woman and z has quality x."

They're equivalent, but the second is easier to follow because it puts the quantifiers closer to the phrases they quantify.
posted by wanderingmind at 10:49 AM on September 6

If your worrying about such formal logic, you're quite often worrying about quantifier elimination (model theory), normal forms (predicate logic), or representation theorems (non-standard logics), which are all commonly facilitated by writing the quantifiers out front. In other words, predicate logic is not used to facilitate human thought or communication, predicate logic exists because you can prove useful theorems about it.

I did once convince a coauthor that an argument was true by explaining a transformation upon formulas in a generic type quite formally, but we sure as hell rewrote the argument using proper human language once I convinced him.
posted by jeffburdges at 10:49 AM on September 6

A. Yes, they are. See prenex normal form, or google it for tons of examples/discussions.
B. Yes, certainly. It has to do with the potential problem of "free variables". Again, here or google free variable for lots of interesting stuff. Basically, you don't want to "capture" with a quantifier a variable of the same name that the quantifier shouldn't be talking about. Just because they are (confusingly) called the same, they are not if the capture problem can arise.
C. As I use this professionally and haven't had a chance to teach it in a long while, I'm a bit out of touch with online resources/textbooks that would be nice to poke around. Googling for "predicate logic course" might give you something you like, and I'd be glad to give you my opinion of how good it looks to me on the technical parts if you post the links.
posted by Iosephus at 10:56 AM on September 6

It may come down to personal preference, but I find the first one to be marginally easier to understand. However, if you get into situations where you have really long complicated sentences, the first approach might leave you with too much information bundled up front to easily interpret. Logically it shouldn't make any difference.
posted by bluejayk at 10:57 AM on September 6

Please note that neither statement is a WFF. You don't have enough parentheses in there, and it's ambiguous what the two different statements actually are. If you don't understand this, or need help, let me know and I'll be able to give you more advice.

Once you figure out what the WFFs actually are in each case, they should be equivalent. A way to test, however, is to see if you can derive one WFF from the other.
posted by Ms. Saint at 11:08 AM on September 6 [1 favorite has favorites]

I thought I should mention this but forgot, Ms. Saint: I've assumed that (A∧B∧C) is shorthand for (A∧(B∧C)), and thus a WFF. Is that what you meant? If there are other reasons why either or both are not WFF, sure, please let me know.
posted by ed\26h at 11:23 AM on September 6

Re: WFFs and parenthisation. Yes, in last instance everything should be full of parenthesis or you have lots of ambiguity about the formula's interpretation. However, and what the OP seems to be doing, it is common to assume a set of "precedence rules" for the logical connectives. This typically goes "first negation and quantifiers, then conjunction, then disjunction (these two in the opposite order is also common), finally implication", and the associativity is ignored (as I see previewing right now mentioned too) when safe, which is always so for conjunction/disyunction. This "precedence" convention is similar to what one does when writing, say, polynomials.
posted by Iosephus at 11:31 AM on September 6

You can figure this out from the wiki page on prenex normal form linked above, but there are several cases where you can't simply move the quantifiers outside to do the conversion. (That is, every sentence has a prenex normal form, but sometimes the translation is more complicated than in your example.) These are (i) when there are multiple instances of variables with the same name bound by different quantifiers (e.g. ((∃xPx) ∧ (∀xQx)) is not equivalent to ∃x∀x(Px ∧ Qx)), (ii) when the quantified expression is in the scope of a negative operator (you need to switch the quantifier when moving negation inside), and (iii) cases where the quantified expression is in the antecedent (left operator) of material implication (there you also need to switch the quantifier).

I also want to warn you that, even setting those issues aside, most people will find prenex normal form more difficult to read. The reason is that natural language has only restricted or binary quantification, which in classical predicate logic looks like "(∃x (Px ∧ Qx))" or "(∀x (Px → Qx))". That is, whenever we quantify in natural language we first restrict the quantification to a domain (sometimes called the "restrictor", in the above formulas "P", corresponding to the noun phrase in e.g. "every boy"), and then make some claim about all/some/most/etc members of just that domain (sometimes called the "nuclear scope", "Q" in the above formulas, corresponding to a verb phrase such as "is tall" in "every boy is tall"). Even words like "everyone" or "everything" have some domain built in -- people or things respectively. Quantification in classical predicate logic is by its nature unrestricted, and consequently not as easy to translate without a restrictor present. Translation to prenex normal form necessarily involves syntactically separating quantifiers from their restrictor, if they have one; with a lot of quantifiers this becomes really complex to translate into natural language restrictor / nuclear scope paraphrases. So your formula 2 is very easy to translate back into natural language, but 1 takes a bit more work. (Note that your paraphrase syntactically mirrors 2, not 1.)
posted by advil at 12:38 PM on September 6

cases where the quantified expression is in the antecedent (left operator) of material implication

er, left argument, not left operator.
posted by advil at 12:42 PM on September 6