Implication in Propositional and Predicate Logic

[sktsasus]

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?

 

[Dr.Peterson]

To avoid complication, let's just look at the first two, which are more similar:

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

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.

However, my reasoning is not very strong for either.

a) You're right that the opposite implication is not valid, because you can make examples where P ⇒ Q is true, but Q is false. (For example, F ⇒ F is true.)

But you don't want to just assume that Q implies P ⇒ Q. Can you think of a reason why this is true? What relevant facts do you know?

b) What you say sounds like pure guess, not "reasoning" at all!

How about this: starting on the left, think about what you can be sure is true, if you know that S ∧ (P ⇒ Q) ∧ ((¬P) ⇒ Q) is true. Since these three statements are connected by "and", you know that S is true; and what else? What can you conclude?

Note also the S is not present on the right, so you don't have to pay too much attention to it on the left.

Now do the same sort of thinking on the right: what do you know is true, if Q ∨ R is true? And, again, since R doesn't appear on the left, it doesn't matter what you find out about R on the right.

Let me know what ideas you have about this. Once you've got some good thinking going on these two questions, you can show your thinking about the other three. You'll want to first look at what you've learned about rules for predicate logic; tell us what rules you think are relevant to a given question, and how they would apply. For example, is there a rule that says you can swap the order of ∀y ∃x? Feelings don't count.