0
$\begingroup$

I have a slight problem in solving the following question. Let $P$ and $Q$ be statements. Which of the following strategies is "NOT" a valid way to show that "$P$ implies $Q$"?

  1. Assume that $P$ is true, and then use this to show that $Q$ is true.
  2. Assume that $Q$ is false, and then use this to show that $P$ is false.
  3. Show that either $P$ is false, or $Q$ is true, or both.
  4. Assume that $P$ is true, and $Q$ is false, and deduce a contradiction.
  5. Assume that $P$ is false, and $Q$ is true, and deduce a contradiction.
  6. Show that $P$ implies some intermediate statement $R$, and then show that $R$ implies $Q$.
  7. Show that some intermediate statement $R$ implies $Q$, and then show that $P$ implies $R$.

I know that 5. is not a valid way but i'm really struggling with parts 6. and 7.

For part 6. I tried doing it this way:

Let $P$ be the statement "germany borders china", let $R$ be the statement "$2+2=4$" and $Q$ be the statement "pigs fly". Then $P$ will vacuously imply the intermediate statement $R$ but $R$ will not imply $Q$ because $R$ is true and $Q$ is false. Hence 6. is not a valid way.

Is this a correct way to check the validity of part 6. and 7.? If not, then what is?

$\endgroup$
6
  • 2
    $\begingroup$ More line breaks. $\endgroup$
    – Asaf Karagila
    Oct 14, 2014 at 21:34
  • $\begingroup$ "Which of the following is NOT a valid way..." Had the problem said "Which of the following are NOT a valid way..." then it would be possible to have more than one answer. The answer IS e. QED. $\endgroup$ Oct 14, 2014 at 21:37
  • $\begingroup$ (f) and (g) work since implication is transitive. $\endgroup$
    – gamma
    Oct 14, 2014 at 21:37
  • $\begingroup$ thanks nick,is there a proof for the transitivity of implication? $\endgroup$ Oct 14, 2014 at 21:39
  • $\begingroup$ @Noel.campbell04091992 In logic threre are two "ways" to prove a statement, using truth tables or using axioms and deduction. To help you, we need to know what are you studying, or what is the approach, e.g., mathematical logic, or discrete mathematics, etc. For now, your question is open. $\endgroup$ Oct 14, 2014 at 21:59

4 Answers 4

1
$\begingroup$

It is no the same question but there is a partial answer to your question here. A simple way to see the tautologies is using truth tables. For instance, you can "prove" 6. by the truth table of $[(P \implies R) \land (R \implies Q)] \implies (P \implies Q)$.

The point 7. other way to say the same that 6., because you can write this by $[(R \implies Q) \land (P \implies R)] \implies (P \implies Q)$, since the conjunction is commutative.



Edit. If you want a "formal proof" for 6., you can try this (but I do not think is what you are looking for).

Using modus ponens (MP), i.e., if we have $P$ and $P \implies Q$, then we conclude $Q$. Now, we want to prove $P \implies Q$. Also, we know that $P \implies R$ and $R \implies Q$. Then

$$ \begin{array}{lll} 1 & \quad P \implies R & \quad\text{Assumption}\\ 2 & \quad R \implies Q & \quad\text{Assumption}\\ \quad 3 & \quad P & \quad\text{Hypothesis}\\ \quad 4 & \quad R & \quad\text{MP 1, 3}\\ \quad 5 & \quad Q & \quad\text{MP 2, 4}\\ 6 & \quad P \implies Q \end{array} $$

$\endgroup$
1
$\begingroup$

That is not a correct way to check the validity of 6. and 7.

You did pick a statement $R$ for 6. that did not imply $Q$, so that is not an application of the rule described in 6. As the comments mentioned, 6. works because of transitivity.

If you already showed that everything excluding 5. - 7. is a valid strategy to prove stuff, you can use 1. - 4. to show 6.

You can use 3. - "$P$ implies $Q$" is the same as "$P$ is false or $Q$ is true or both", and use that for "$P$ implies $R$" and "$R$ implies $Q$".

Another option is a proof via contradiction, e.g. option 4.:
Assume $P$ implies $R$, $R$ implies $Q$, but assume also that $P$ does not imply $Q$. What can you deduce about the truth values of $Q$ if $P$ is true or false?

$\endgroup$
1
  • $\begingroup$ thank you very much for your valuable answers and opinions cristhian and planckh $\endgroup$ Oct 14, 2014 at 22:46
0
$\begingroup$

(1) Answer

"Which of the following strategies is "NOT" a valid way to show that "P implies Q"?"

(5) is not a valid way to show that "P implies Q"

All the other alternatives are valid ways of showing that "P implies Q".


(2) Justification

I first apologize if my symbolism may confuse to you, but I do assure you that they are necessary for a good understanding of your question.

Recall the definition of the meaning of the logical connective '$\to$':

$v(ϕ → ψ) = 1 ⇔ v(ϕ) \leq v(ψ)$

where $v$ is a valuation function.

Then it follows that (1), (2), (3), (4) are equivalent ways of stating that $v(ϕ → ψ) = 1$:

(1) $v(P → Q) = 1 ⇔ v(P) \leq v(Q)$ $ ⇔$ $ $if $v(P)=1$ then $v(Q)=1$

(2) $v(P → Q) = 1 ⇔ v(P) \leq v(Q)$ $ ⇔ $ if $v(Q)=0$ then $v(P)=0$

(3) $v(P → Q) = 1 ⇔ v(P) \leq v(Q)$ $ ⇔ $ $v(P)=0$ or $v(Q)=1$

(4) $v(P → Q) = 1 ⇔ v(P) \leq v(Q)$ $ ⇔$ $ v(P)=1$ and $v(Q)=0$ is a contradiction

Actually (6) and (7) too:

(6) $v(P → R) = 1$ and $v(R → Q) = 1$ $ ⇔$ $ v(P) \leq v(R) \leq v(Q)$ ⇔ v(P → Q) = 1$

Explanation: First, it says that we should assume that $P \to R$ is true, i.e. $v(P → Q) = 1$. Now this is the same as $v(P) \leq v(Q)$. Then since we assume that $R \to Q$ is also true then $v(P) \leq v(R) \leq v(Q)$. This shows that $P \to Q$ is true.

(7) goes simillarly:

(7) $v(R → Q) = 1$ and $v(P → R) = 1 ⇔ v(P) \leq v(R) \leq v(Q)$ ⇔ v(P → Q) = 1$

Explanation: it says we should assume that $R \to Q$ is true, i.e. $v(R → Q) = 1$. Now this is the same as $v(R) \leq v(Q)$. Then since we assume that $P \to R$ is also true then $v(P) \leq v(R) \leq v(Q)$. This shows that $P \to Q$ is true.

$\endgroup$
0
$\begingroup$

(5) is NOT valid. All other options are fine. $P \implies Q $ is FALSE iff $P$ is FALSE and $Q$ is TRUE.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.