Below are listed several pairs of sentences, both in propositional logic and in predicate logic. In each pair, one of the sentences implies the other. Decide which of the two logically implies the other one, and give justification for your answer.
(a) Q; P ⇒ Q
(b) S ∧ (P ⇒ Q) ∧ ((¬P) ⇒ Q); Q ∨ R
(c) ∀y ∃x R(x, y); ∃x ∀y R(x, y)
(d) (∀x P(x)) ⇒ (∃x P(x)); ∀x (P(x) ⇒ Q(x))
(e) (∀x P(x)) ∨ (∀x ¬P(x)); (∃x P(x)) ⇒ (∀x P(x))
I tried to approach each of these using reasoning rather than truth tables. But I must admit it ended up being more of a guessing game than anything. So I need some help.
For a), I thought that Q implies P ⇒ Q because when in some cases when P ⇒ Q is true, Q is still false.
For b), I thought Q ∨ R implies S ∧ (P ⇒ Q) ∧ ((¬P) ⇒ Q) because Q is present in the larger statement and R is not so I thought the smaller statement could just be considered as Q only.
For c), I thought ∀y ∃x R(x, y) implies ∃x ∀y R(x, y) because I thought that if all x existed for all y, then there would be an x for all y.
For d), I thought ∀x (P(x) ⇒ Q(x)) implies(∀x P(x)) ⇒ (∃x P(x)) because when P(x) exists for all x, then it exists regardless of Q(x).
For e), I thought (∃x P(x)) ⇒ (∀x P(x)) implies (∀x P(x)) ∨ (∀x ¬P(x)) because P(x) either exists or doesn't depending on x.
However, my reasoning is not very strong for either.
Any help?
Yeah, your reasoning is pretty poor, sorry to say. Sometimes you got the wrong answer, and sometimes you don't (and below I'll try not to give away the answers), and even when you did get the right answer, your reasoning didn't really justify it correctly.
OK, some hints:
a) you haven't really showed why $P \rightarrow Q$ does not imply $Q$ ... and I think that, more importantly, you should show why $Q$ does imply $P \rightarrow Q$. Try referring to what would make $P \rightarrow Q$ true or false.
b) No, you can't really reason in terms of what terms are there or not. For example, there is a $Q$ in $P \land Q$ that is not in $P$, but that does not mean that $P$ implies $P \land Q$ ... in fact for this case it is just the other way around. So, you'll need to do more analysis on the two statements you have for b)
c) You got that just the wrong way around. Maybe it helps to first think of a more concrete example, with $P(x,y)$ interpreted as '$x$ likes $y$' ...
d) I am not following your reasoning here .. Neither of the two statements say that $P(x)$ for all $x$. Try again .. and maybe once again first try a concrete example, like '$P(x): x is a unicorn'
e) No. I think you're interpreting the first statement as saying that 'either everything is a $P$ or not' .. which would make it a tautology, and thus it would be implied by the other statement ... but the first statement is not a tautology. Think carefully what the first statement says. ... and then look at the second statement.