Placement of Quantifiers and their rules
Goh, Yong Kwang
I was stupefied by a question in my tutorial when my tutor gave a
different answer from mine and I asked him about it. But he didn't
give me concise explanation in his reply and I thought it may be good
to ask it here.
OK. In my tutorial I came up with an answer,
ForAll x, m, n Exists in Z (x is even) AND (x > 2) -> (m is prime) AND
(n is prime) AND (m + n = x)
The answer he gave me was:
ForAll x Exists in Z (x is even) AND (x > 2) -> ForAll m, n Exists in
Z (m is prime) AND (n is prime) AND (m + n = x)
As we can see, my tutor's answer shifted the quantifier for m and n
after the -> while I place all my quantifiers in front.
He dismissed me by saying that:
(1) my answer is equivalent to his (and so not worry about the
difference?)
(2) there are rules for quantifier placements (quantifier rules)
(3) quantifier rules are _not_ covered within the module syllabus
What I hope to do is to prevent from making mistakes in my quantifier
placements by learning more about how it works.
Can anyone point out to me on how to place the quantifiers? When
should it be in front and when in the middle?
Regards,
Goh, Yong Kwang
Singapore
gohyon...@hotmail.com
Goh, Yong Kwang
William Hale
I am not aware of any rules for quantifier placements.
I prefer to have all the quantifiers outside of the statement
being quantified, as you did in the example you gave.
-- Bill Hale
David Ziskind
<01c3ea09$b1d77ac0$5e4e36d1@default> about the rules for placing
quantifiers in quantificational logic statements.
In the OP, there is a slight complication to the main question here,
the complication being the “predicate”: 'exists in Z'. To simplify the
issue and focus on the main matter, let us imagine that 'exists in Z'
has been stricken. We can now look at the two versions and see that
they are in fact logically identical (this assumes that parentheses are
placed in a plausible way). The two versions are shown to be identical
by repeated application of the first of the following four theorems:
[Note: E means: there exists; A means: for all.]
Th 1: (Ax)(p implies F(x))
IFF [p implies (Ax)(F(x)]
Th 2: (Ex)(p implies F(x))
IFF [p implies (Ex)(F(x)]
Th 3: (Ax)(F(x) implies p)
IFF [(Ex)(F(x)) implies p]
Th 4: (Ex)(F(x) implies p)
IFF [(Ax)(F(x)) implies p]
In other words, when importing (or exporting) a quantifier inside
(outside) a statement of the type considered, the quantifier (remains
the same) (reverses) as the quantified proposition occurs as
(consequent) (antecedent).
To prove all four, use the truth-table method (TTM):
(Ax)(F(x)) IFF [F(x1) & F(x2)]; (Ex)(F(x)) IFF [F(x1) or F(x2)] . (TTM
works in these cases because there is a single quantifier.)
Hence, the tutor's answer part (1), deals with the issue and is really
all that is required (although yes, of course, there are rules).
Although only Th 1 is used in the present situation, the set of 1
through 4 have an obvious relationship and are used constantly.
David Ziskind
zis...@ntplx.net
Torkel Franzen
> OK. In my tutorial I came up with an answer,
>
> ForAll x, m, n Exists in Z (x is even) AND (x > 2) -> (m is prime) AND
> (n is prime) AND (m + n = x)
>
> The answer he gave me was:
> ForAll x Exists in Z (x is even) AND (x > 2) -> ForAll m, n Exists in
> Z (m is prime) AND (n is prime) AND (m + n = x)
I take it that you are trying to formulate Goldbach's conjecture,
that every even number greater than 2 is the sum of two primes. Your
version makes no obvious sense - "Exists" doesn't even have any
accompanying variable. A correct formulation (writing (x) for "for all
x" and (En) for "exists n such that") is
(1) (x)(Em)(En)(x is even & x>2 -> m is prime & n is prime & x=m+n)
Your tutor's version, as you present it, doesn't make any sense
either. A formulation logically equivalent to (1) is however
(x) (x is even & x>2 -> (Em)(En)(m is prime & n is prime & x=m+n))
Torkel Franzen
> ForAll x, m, n Exists in Z (x is even) AND (x > 2) -> (m is prime) AND
> (n is prime) AND (m + n = x)
>
> The answer he gave me was:
> ForAll x Exists in Z (x is even) AND (x > 2) -> ForAll m, n Exists in
> Z (m is prime) AND (n is prime) AND (m + n = x)
I had trouble understanding your notation, but the response by David
Ziskind suggests to me that your version is to be understood as
For all x,m,n in Z (x is even & x>2 -> m is prime & n is prime &
m+n=x)
If so, the second formula is indeed equivalent:
For all x in Z(x is even & x>2 -> For all m,n in Z(m is prime & n is
prime & x=m+n))
However, I strongly suspect that the problem to which you gave the
above solution was to formulate Goldbach's conjecture (that every even
number greater than 2 is the sum of two primes), in which case your
answer is wrong.
Goh, Yong Kwang
newsgroup. And yes the question asked the student to write down the
Goldberg Conjecture symbolically, given a description in English.
Torkel Franzen <tor...@sm.luth.se> wrote in message news:<vcbvfmo...@beta13.sm.luth.se>...
> gohyon...@hotmail.com (Goh, Yong Kwang) writes:
>
>
> > OK. In my tutorial I came up with an answer,
> >
> > ForAll x, m, n Exists in Z (x is even) AND (x > 2) -> (m is prime) AND
> > (n is prime) AND (m + n = x)
This should be:
ForAll x Exists in Z, ForSome m, n Exists in Z (x is even) AND (x > 2)
-> (m is prime) AND (n is prime) AND (m + n = x)
> >
> > The answer he gave me was:
> > ForAll x Exists in Z (x is even) AND (x > 2) -> ForAll m, n Exists in
> > Z (m is prime) AND (n is prime) AND (m + n = x)
And my tutor's answer should be:
ForAll x Exists in Z (x is even) AND (x > 2) -> ForSome m, n Exists in
Z (m is prime) AND (n is prime) AND (m + n = x)
>
> I take it that you are trying to formulate Goldbach's conjecture,
> that every even number greater than 2 is the sum of two primes. Your
> version makes no obvious sense - "Exists" doesn't even have any
> accompanying variable. A correct formulation (writing (x) for "for all
> x" and (En) for "exists n such that") is
>
> (1) (x)(Em)(En)(x is even & x>2 -> m is prime & n is prime & x=m+n)
>
> Your tutor's version, as you present it, doesn't make any sense
> either. A formulation logically equivalent to (1) is however
>
> (x) (x is even & x>2 -> (Em)(En)(m is prime & n is prime & x=m+n))
I messed up the bounding of variables. Sorry for creating so much
confusion.
Goh, Yong Kwang
Singapore