6

I can prove that these two statements are equivalent, but I can't make sense of them logically. For instance, if P = "have a cold", Q = "have a headache", and R = "go see a doctor" then the statement:

If you have a cold then go see a doctor or if you have a headache then go see a doctor.

Is equivalent to:

If you have a cold and a headache then go see a doctor?

This to me does not make sense because the left side is saying if you have a cold OR a headache see a doctor, but the right side of the equation is saying if you have a cold AND a headache go see a doctor.

Can someone help clarify this for me?

EDIT:

I forgot to add that this is from the book "How to Prove It" by Daniel Velleman, of which I double checked and the equivalence is written in the book just as I wrote it.

Also, I think the author is trying to make me see a contrast between the two statements:

(i) (P→R)∧(Q→R)≡(P∨Q)→R [I understand this statement]

(ii) (P→R)∨(Q→R)≡(P∧Q)→R [I don't understand this statement].

Both statements, at least as written in the book, are true.

Bavneet
  • 121
  • 6
  • In light of your edit, I've given a counterexample in my post. – not all wrong Apr 14 '13 at 21:42
  • Oh, sorry, let me completely revise this, and give a completely new answer. There is a huge subtlety in the notion of implication which comes up here. – not all wrong Apr 14 '13 at 22:04
  • I've added a much expanded answer. – not all wrong Apr 14 '13 at 22:41
  • The problem with translating propositions like these into English and testing their "real world sense" is that mathematics is not 100% compatible with the real world. When you harass little kids with "Who do you love more, mommy or daddy?" the answer "Yes." is not the one you'd expect, but mathematically it is a correct one. – Asaf Karagila Apr 15 '13 at 14:21

5 Answers5

6

Notions of implication

The problem lies in the interpretation of the $\implies$ symbol. There are two competing definitions, and we normally get away with conflating them.

  • Day to day language: $A \implies B$ is equivalent to regardless of anything else, if $A$ holds, then $B$ holds.
  • Logic: $A \implies B$ is equivalent to $(\neg A) \vee B$ or either $B$ holds or $A$ doesn't.

Why are these not the same? Because of the "regardless of anything else" bit, which put simply isn't a thing in logic. You have to evaluate the whole formula to interpret this part correctly.

For example, $(\{m \ge 0\} \implies \{x = 1\}) \vee \{x \neq 1\}$ with an implicit $\forall x$ is a true logical statement. It is however obviously not necessarily the case that either $\forall x :\{x \neq 1\}$ or $\forall x:\{m \ge 0\} \implies \{x = 1\}$. The problem lies in the $\forall x$ part, which is an incredibly subtle aspect of implication.

Logic interpretation

Let's start with the maths. The left-hand side is $(P \implies R) \vee (Q \implies R)$. This is exactly $(\neg P \vee R) \vee (\neg Q \vee R)$ or rearranging $R \vee \neg P \vee \neg Q$.

But $\neg(P\wedge Q) \equiv \neg P \vee \neg Q$ and therefore$$(P \implies R) \vee (Q \implies R) \quad \equiv \quad R \vee \neg (P\wedge Q) \quad \equiv \quad (P\wedge Q) \implies R$$

What does this mean in words? It's as follows:

Suppose we know whether you have a cold ($P$), whether you have a headache ($Q$) and whether you should go to the doctors ($R$). Then "you DON'T have a cold, OR you DON'T have a headache, OR you're going to the doctors" is exactly the same as "you DON'T have both a cold AND a headache, OR you're going to the doctors".

Which is obviously true. But it's weird when we rephrase in terms of implications - but this is because the implications become trivial. Let's look at some particular examples in the truth table.

Something that seems weird is that you can deduce from the RHS things where only one of $P,Q$ hold. Let's suppose you only have a cold, so $P$ but $\neg Q$. There are two cases; either $R$ or $\neg R$.

  • Suppose you have a cold, but you shouldn't go to the doctors. $P$, $\neg Q$, $\neg R$. Then the right-hand side $(P\wedge Q) \implies R$ evaluates to true! Woah. Weird, huh? It's saying that the implication is trivially satisfied because its condition isn't. What about the left-hand side? Here, the headache implication $Q\implies R$ is trivially satisfied, so we get true here too.
  • If we switched to $\neg P$ and $Q$, then it would be a different implication on the left-hand side which was true!
  • Suppose you should go to the doctors. $P$, $\neg Q$, $R$. Then the RHS is true because we know you should go to the doctors, and both terms on the LHS are also true, for the same reason!

Thus the fact that implications are true when their arguments are not satisfied makes the whole statement completely perverse. Nobody you'll meet in real life ever says $\forall x: (A(x) \implies B(x)) \vee (C(x) \implies D(x))$; the quantifiers are in the wrong place! They would say $(\forall x : A(x) \implies B(x)) \vee (\forall x : C(x) \implies D(x))$. Unfortunately, the logical notation does not lend itself at all well to what sane humans mean by implication.

Standard language interpretation

As written, interpreted as standard English, that isn't actually the correct interpretation of the LHS either.

For P = "have a cold", Q = "have a headache", R = "go to the doctor", the statement you wrote is

At least one of the two symptoms of cold and headache is serious enough to make a visit to the doctor necessary [but we're not sure which]. $(P \implies R) \vee (Q \implies R)$

It does not say

If you have at least one of the two symptoms of cold and headache, it is serious enough to make a visit to the doctor necessary [regardless of which you have]. $(P \vee Q) \implies R$

As Henry Swanson pointed out, there is not an equivalence if one talks in day to day English between either of these statements and

If you have both of the two symptoms of cold and headache, it is serious enough to make a visit to the doctor necessary. $(P \wedge Q) \implies R$

However, both of the previous statements do imply this one. (Since $P\wedge Q$ allows us to assume both $P$ and $Q$ in considering the implications above.)

To give a concrete counterexample to the stated equivalence in day to day language, suppose $P$ is "$x \le 0$", $Q$ is "$x \ge 0$" and $R$ is "$x = 0$".

Then $P \wedge Q \implies R$ is definitely true.

However, $P \implies R$ is not true. Also, $Q \implies R$ is not true. Therefore $(P \implies R) \vee (Q \implies R)$ is not true.

Consequently, the two statements are not the same.

Community
  • 1
not all wrong
  • 16,178
  • 2
  • 35
  • 57
3

(edited because I can't symbolic logic)

They aren't equivalent, but the left implies the right. They are equivalent. The left side means "If you have a cold, go to the doctor" or "If you have a headache, go to the doctor". The right is, "If you have both, no matter which one implies "go to the doctor", go to the doctor".

You can demonstrate this with truth tables, or use some identities: $$(P \implies R) \vee (Q \implies R)$$ $$(\lnot P \vee R) \vee (\lnot Q \vee R)$$ $$(\lnot P \vee \lnot Q) \vee R$$ $$\lnot(P \wedge Q) \vee R$$ $$(P \wedge Q) \implies R$$

Henry Swanson
  • 12,972
  • If you bother to work out the truth tables, you will see that the statements in the question are equivalent. On the other hand $(P\to R)\vee (Q\to R)$ is not equivalent to $(P\vee Q)\to R$, and $(P\to R)\land(Q\to R)$ is not equivalent to $(P\land Q)\to R$. You derserve an F, but I will let you of with a downvote this time. – Wouter Stekelenburg Apr 15 '13 at 08:06
  • Ah, I see what I did wrong now. Not the most polite way of putting it, but thanks! – Henry Swanson Apr 15 '13 at 14:09
3

The mathematical aspect of the question has already been answered, so let me say something about the intuitive aspect, which caused the difficulty in the first place. I think the problem (or at least part of it) is that we are not accustomed to thinking about disjunctions of implications. We see implications all the time, for example in civil laws, but we don't often have a choice of which law to obey. But I think, once the issue is brought into the open, we can think about such disjunctions without too much difficulty. In the example at hand, suppose that you had a choice between obeying a law that says "If you have a cold, then you must go to the doctor" and another law that says "If you have a headache, then you must go to the doctor." In such a situation, if you had a cold and a headache, you would have to go to the doctor. Even though you can choose which law to obey, either choice will require you to go to the doctor. But if you had only a cold or only a headache, then you could avoid going to the doctor, by choosing to obey the law that doesn't apply to your actual condition. So the ultimate effect of the two laws and your option of choosing between them is exactly the same as the ultimate effect of a single law saying "If you have both a cold and a headache, then you must go to the doctor."

Andreas Blass
  • 71,833
  • The disjunction of implications problem is even more striking with $(P \to Q) \lor (Q \to P)$. So, either "If I had a headache yesterday then I went to the doctor yesterday" or "If I went to the doctor yesterday then I had a headache yesterday" must be true. – Carl Mummert Apr 15 '13 at 15:06
1

One reason that this particular equivalence is hard to understand is that it depends on the idea in classical logic that each formula is either true or false, in the following way.

If we substitute "$P \land Q$" for $R$, we obtain $$ (P \to (P \land Q)) \lor (Q \to (P \land Q)) \equiv (P \land Q) \to (P \land Q) $$ Then, since the right side is trivial, if the equivalence holds we see that $$ (P \to (P \land Q)) \lor (Q \to (P \land Q)). $$ However, $P \to (P \land Q)$ is equivalent to $P \to Q$, and $Q \to (P \land Q)$ is equivalent to $Q \to P$. Therefore, if we assume the original equivalence holds, we can derive $$ (P \to Q) \lor (Q \to P). $$ This says that one of $P \to Q$ and $Q \to P$ must hold regardless what $P$ and $Q$ actually say. That is not a property of the "natural language" if/then operator.

In particular, because the original equivalence can be used to give a constructive derivation of $(P \to Q) \lor (Q \to P)$, and the latter cannot be derived constructively, the original equivalence cannot be derived constructively. Here "constructively" has a particular formal meaning, but to get a general sense, think of constructive proofs of propositional formulas as ones that use the "meaning" of the statements rather than truth table calculations and the material implication rule.

As an informal pattern, whenever we have a true statement, e.g. the original equivalence, that cannot be proved constructively, it is often hard to see "why" the statement holds, and the verification will come down to simply checking all the possible cases with a truth table (or something equivalent).

Carl Mummert
  • 81,604
1

the left side is absolutely not saying "if you have a cold OR a headache see a doctor", it is saying "if I have a headache I will go to the doctor, or if I have a cold I will go to the doctor", which is a rather strange sentence (maybe you are secretely immune to one of colds or headaches, but not both at once, and you don't know which one you are immune to)

Suppose you are going to pass an exam. You don't know exactly what it is going to be about, but someone told you it would be either about norwegian or about french. Say P is "I studied norwegian", Q is "I studied french", and R is "I passed the mystery exam".

Then, since you have "(the exam is about norwegian) or (the exam is about french)", you get that the sentence "(if I study norwegian, I pass the exam) or (if I study french, I pass the exam)" is indeed true.

What should you do in this situation ? of course if you study both languages, you will pass the exam for sure, which is what the equivalence is saying.

mercio
  • 50,180