Thread: 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

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.

Or, equivalently, , which is perhaps closer to the English sentence.

Originally Posted by emakarov

Or, equivalently, , 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..

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.

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.