# Predicate Logic

• Mar 23rd 2011, 08:40 AM
Newskin01
Predicate Logic
The domain of the following predicates is all integers greater than 1.
P(x) = “x is prime”
Q(x,y) = “x divides y”
Consider the following statement.
“For every x that is not prime, there is some prime y that divides it”

i. Write the statement in predicate logic.
ii. Formally negate the statement so that no quantifier lies in the scope of the
negation.
iii. Write the English translation of your negated statement

I tried this and I got

i. ∀x¬P(x)∃xQ(x,y)

ii. ∃xP(x)∀x¬Q(x,y)

iii. There exists a x that is prime, there is y for every prime that does not divide it.

Thanks
• Mar 23rd 2011, 09:13 AM
Plato
Quote:

Originally Posted by Newskin01
The domain of the following predicates is all integers greater than 1.
P(x) = “x is prime”
Q(x,y) = “x divides y”
Consider the following statement.
“For every x that is not prime, there is some prime y that divides it”
i. Write the statement in predicate logic.
ii. Formally negate the statement so that no quantifier lies in the scope of the negation.
iii. Write the English translation of your negated statement

I would say that first one is:
i. $\left( {\forall x} \right)\left( {\exists y} \right)\left[ {P(x) \vee \left( {P(y) \wedge Q(y,x)} \right)} \right]$
• Mar 23rd 2011, 11:55 AM
emakarov
Or, equivalently, $\forall x\,(\neg P(x)\to\exists y\,(P(y)\land Q(y,x))$, which is perhaps closer to the English sentence.
• Mar 23rd 2011, 12:04 PM
Plato
Quote:

Originally Posted by emakarov
Or, equivalently, $\forall x\,(\neg P(x)\to\exists y\,(P(y)\land Q(y,x))$, which is perhaps closer to the English sentence.

There can be no doubt that is "closer to the English sentence".
The reason I did not use that was these instructions: i. Formally negate the statement so that no quantifier lies in the scope of the negation..
• Mar 23rd 2011, 12:39 PM
emakarov
Quote:

The reason I did not use that was these instructions: i. Formally negate the statement so that no quantifier lies in the scope of the negation.
What difference does it make? This instruction says, after negating the formula, to move the negation inside so that it is inside the quantifiers' scopes. It has nothing to do with the original formula, which in any case has no quantifiers in the scope of the negation.
• Mar 23rd 2011, 01:05 PM
Plato
Quote:

Originally Posted by emakarov
What difference does it make? This instruction says, after negating the formula, to move the negation inside so that it is inside the quantifiers' scopes. It has nothing to do with the original formula, which in any case has no quantifiers in the scope of the negation.

I thought is was less confusing. That is all.