How to choose between p->q and p^q

Question

How to express this in propositional logic

-- No largebird lives on honey

-- the correct answer as per author ¬∃x(Q(x) ∧ R(x)) where as

Q(x) - x is a large bird

R(x) - x lives on honey

-- But why not ¬∃x(Q(x) -> R(x))

This is a problem in Discrete mathematics and applications KENNETH ROSEN Chapter 1, Section 1.4 Example 27

Consider these statements, of which the first three are premises and the fourth is a valid conclusion. “All hummingbirds are richly colored.” “No large birds live on honey.” “Birds that do not live on honey are dull in color.” “Hummingbirds are small.”

∀x(P(x) → S(x)). ¬∃x(Q(x) ∧ R(x)). ∀x(¬R(x) → ¬S(x)). ∀x(P(x) → ¬Q(x))

I am unable to prove if I use ¬∃x(Q(x) -> R(x)) So how to choose the correct form.

Answer 1

The fact that you are unable to prove the conclusion (even though it clearly logically follows) if you use $\neg \exists x (Q(x) \to R(x))$ is of course a big clue that that isn't the right way to translate the sentence.

OK, but why not? What is wrong with $\neg \exists x (Q(x) \to R(x))$ and why should is $\neg \exists x (Q(x) \land R(x))$ the correct way to translate 'No Q are R'?

First, I hope that yo can see that $\neg \exists x (Q(x) \land R(x))$ totally works: this translates back to 'There is nothing that is both a Q and a R', and a little thinking shows that that is indeed the same as 'No Q are R'.

If there is nothing that can be both a Q and an R, then if you have something that is a Q, then it clearly cannot also be an R ... so No Q are R. And note that this shows that 'All Q are not R'

Vice versa, if 'No Q are R' then can you have something that is both a Q and an R? No, so 'Nothing can be both a Q and an R'.

OK, so 'No Q are R' and 'There is not something that is both a Q and an R' are the same, and since the latter straightforwardly translates to $\neg \exists x (Q(x) \land R(x))$, then that means that that is a correct logic expression to capture 'No Q are R' as well.

OK, but still, why doesn't $\neg \exists x (Q(x) \to R(x))$ work? Well, let's first ignore that leading negation, and just focus on the $\exists x (Q(x) \to R(x))$ part. Note that this statement is saying that 'There is something such that if it is a Q, then it is an R'. But also note that this would be true as soon as there is something in the domain that is not a Q!

For example, suppose Bob is part of the domain and Bob is not a Q. Well, then it is true that if Bob is a Q, then Bob is a R! And that's because in logic, any 'if...then...' is true as soon as the 'if' part is false. Likewise, any conditional is true as soon as the consequent is true. So, as soon as there is a R in the domain, the whole statement $\exists x (Q(x) \to R(x))$ becomes true as well. In sum: it is almost trivial to make $\exists x (Q(x) \to R(x))$ true: it says almost nothing at all! Indeed, the only way for it to be false is if everything is a Q, and nothing is an R ... and indeed $\neg \exists x (Q(x) \to R(x))$ turns out to be equivalent to $\forall x (Q(x) \land \neg R(x))$. So in effect, $\neg \exists x (Q(x) \to R(x))$ ends up saying that everything is a Q, and nothing is an R, which is clearly not the same as saying that 'No Q are R'.

Answer 2

The translation provided in the text is the correct one: "No largebird lives on honey" is: "there is no x which is both (Largebird x and lives on Honey x)", that is: $¬∃x(Q(x)∧R(x))$.

Why not ise $\to$? Assume a case where we have two objects $a,b$ such that $a$ is $Q$ and not $R$ and $b$ is $R$ and not $Q$.

We have that $¬∃x(Q(x)∧R(x))$ is TRUE while $¬∃x(Q(x)→R(x))$ is FALSE because we have that $Qb→Rb$ holds.

Having said that, the argument is:

$∀x(P(x) → S(x)), ¬∃x(Q(x) ∧ R(x)), ∀x(¬R(x) → ¬S(x))$;

therefore: $∀x(P(x) → ¬Q(x))$.

You have to exploit the fact that the 2nd premise: $¬∃x(Q(x) ∧ R(x))$ is equivalent to: $∀x(R(x) → ¬Q(x))$.

"Contraposing" 3rd premise you get: $∀x(S(x) → R(x))$, and thus you can "chain" all three formulas to reach the conclusion.