Discrete! #9: Discrete Mathematics and Its Applications 1.2C

Logical Equivalences Involving Conditionals

So, we’re continuing on page 25 with the two charts at the top.

p→q≡¬p∨q

This one still fucks with my head, so I’m gonna linger on it a bit. Intuitively, you want to say “how can a conditional by the same as a disjunction you piece of shit?!”

Well, once again, you’ve got to consider the possibilities.

On the left, the statement is true (i.e. non-false) under the following circumstances: 1) p is true and q is true, 2) p is false and q is false, 3) p is false and q is true. It is only false if p is true but q is false.

On the right, the statement is only false when (¬p) is false AND q is false. That is, when p is true and q is false.

Okay, so it’s still weird on the brain. I’m convinced most of the confusion results form the difficulty in understanding “True” to simply mean “not known to be false.”

Let’s look at in example.

p: You just met Zach Weiner.

q: You are mad with lust.

p→q: If you just met Zach Weiner, then you are mad with lust.

Now, we don’t know if that conditional is true. So, we make some observations on you.

If p is true and q is true, the conditional true. That is, if whenever you meet Zach Weiner you go mad with lust, we can say p→q is true.

If p is true and q is false, the conditional is false. Whenever you meet Zach Weiner, inexplicably, you don’t go mad with lust. So, p→q is false.

If p is false, then we can’t say anything about the conditional, since the result of p being false is unknown. That is, we don’t know what you’ll do if you haven’t just met Zach Weiner. You may go mad with lust (q = true) or you may not (q = false). Either way, we don’t know if the statement is true, since we only know what we’re asking if p is true.

So, the two possibilities where p is false are, based on the information in the conditional, non-false. Thus, they are true because the definition of trueness here includes being non-false.

Now let’s go back to the right side of our above equivalence, p→q≡¬p∨q

The right side is basically saying this: If p is false, the whole statement is true, since this is an inclusive OR proposition. This is the same as what we said for the conditional. The other circumstance in which the right side is true is when p is true and q is true. Since it’s an OR proposition, there’s only one way for it to be false: when both connected statements are false: ¬p is false and q is false. That is, the propositional overall is false when p is true but q is false. This is the same as what we just said about the left hand side.

Got it? These are different seeming frameworks, but they produce the same set of possibilities. They feel different because the left side in a human sense produces 3 possibilities: true, false, and I don’t know, whereas the right side only produces true and false. But, in this framework, “I don’t know” is the same as non-false, which is the same as true.

Wow, that was a lot of work for a single equivalence.

p→q≡¬q→¬p

This we know from earlier as the contrapositive, so I won’t linger on it.

p∨q≡¬p→q

This is very similar to the first thing we discussed. Using what we learned there, think of this equivalence thus: p∨q is only false when both p and q are false. So, the right hand side is telling you that, for it to be true, IF not-p turns out to be the case, q must be true.

See how that makes sense? p OR q leaves 3 possible ways to be true: p is true, q is true, or both are true. If p is declared false, then the only way to keep the statement true is to have q be true.

p∧q≡¬(p→¬q)

Similar logic here again. If the left side is true, then p AND q are both true. So, the right side is saying “It’s not the case that if p is true q is false.”

¬(p→q)≡p∧¬q

The left side here is saying “It is NOT the case that if p is true then q is true.” Remember, out of the 4 possible true and false combinations, p→q is only false if p is true and q is false. And that’s what the right hand side is saying. You might read this line is “If the conditional is false, then it must be the case that the conclusion is false when the premise is true.” Or, to go back to our example, you might say “I say a lady who saw Zach Weiner AND didn’t go mad with lust.” That’d be equivalent to saying “It’s not the case that ladies always go mad with lust when they see Zach Weiner.”

(p→q)∧(p→r)≡p→(r∧q)

This is pretty simple. If p implies q and p implies r, then if you know p to be true, you know the other two are true.

For example:

p: I’m at home alone.

q: I’m in my underwear.

r: I’m eating pizza.

The left side says: “If I’m at home alone, I’m in my underwear. Also, if I’m at home alone, I’m eating pizza.” The right side is just more succinct: “If I’m at home, I’m in my underwear and eating pizza.”

(p→r)∧(q→r)≡(q∨p)→r

This is essentially saying there are two ways to reach r. Let’s do an example.

p: You practice piano a lot.

q: You kill all the competition.

r: You perform at Carnegie Hall.

The left side says “If you practice piano a lot, you’ll perform at Carnegie Hall. Also, if you kill all the competition, you’ll perform at Carnegie Hall.” The right side says a more human version: “If you practice piano a lot, or you kill all the competition, or hey, if you do both, you’ll perform at Carnegie Hall.”

(p→q)∨(p→r)≡p→(q∨r)

The left side is setting up two conditionals, at least one of which is true, and both of which depend on p.

So, for example:

p: You have ice cream.

q: You are happy.

The right side says “If you have ice cream you’re happy. Or if you have ice cream, your hand is cold. OH, or if you have ice cream, you’re happy and your hand is cold.” The right side is something like “If you have ice cream, at least one of these is true: you’re happy, you have cold hands.”

(p→r)∨(q→r)≡(p∧q)→r

This one might trip you up because we’re back to our old nemesis, not-false.

Let’s look at the right side. You may be tempted to say it means “In order for this side to be true, both p and q must be true.” This is incorrect. Remember, if the antecedent is false, then we don’t know if the conditional is true or false. So, we must call it non-false. In fact, the right side is only false if p AND q are true and r is false.

Now, look at the left side. Because it’s an OR proposition, for it to be false, both conditionals must be false. And, conditionals are only false when their antecedents are true but their conclusions are false. So, the left side is only false when r is false and BOTH of p and q are true.

To make it more clear, consider the contrapositive of the right side: ¬r→¬(p∧q). That is, if r is false, then p and q can’t both be true. Or, you might say, if r is false, at least one of p and q is also false. This is what the left side says as well.

OOF! Once again, this ended up longer than I intended it to. But, it’s important to go over these things and not just memorize them. It’s the only way to break down your intuitive logic and build up your… well… logic.

I’ll have to leave the conclusion of this section for the next blog.

Next up: Biconditionals and making up your own rules!

This entry was posted in Autodidaction, Discrete Math. Bookmark the permalink.

12 Responses to Discrete! #9: Discrete Mathematics and Its Applications 1.2C

1. Chris says:

What have you been using to typeset your math on this blog? If you’re looking to to physics up to graduate level (I’d recommend doing math, too), then you should learn LaTeX. There’s also a little bit of code you can add to your website to use MathJax, which allows you to type LaTeX math directly into your blog:

MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\$','\$']]}, TeX: {
extensions: ["AMSmath.js","AMSsymbols.js","noErrors.js","noUndefined.js"]
}});

2. Chris says:

The code was cut off:

MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\$','\$']]}, TeX: {
extensions: ["AMSmath.js","AMSsymbols.js","noErrors.js","noUndefined.js"]
}});

3. Alexis Beingessner says:

Accepting the transformation from implication to disjunction, and accepting De Morgan’s Law, are probably the two most important things in this part of discrete math. These are the two rules you will tend to instantiate the most in trying to manipulate propositions.

Personally I find the most intuitive way to consider an implication is “If someone told me this, it’s false if it’s a lie, and true otherwise”. So basically, if they say “if p then q”, then if p is false, all bets are off, no matter what happens to q, it’s not going to be a lie, so the whole must be true. If p is true, then they aren’t lying iff q is also true. If p is true and q is false, then and only then have they lied to me, and then and only then is it false. If they promised “if it is sunny, then we will go to the beach”, and it was sunny but we did not go to the beach, then someone just lied to me about awesome beach times, so their statement was false.

You can apply similar logic to all the other propositions too. If someone promises “p or q” and neither p nor q is true, then the whole proposition is false because it is a lie. If someone promises “p and q”, and either p or q is false, then once more we’ve been lied to.

The nice thing about this is that there is no room for a “half-truth” because you can’t “half-lie”. Either you lied to me or you didn’t. Half-truths and lies are a concept we leave to language (unless we’re exiting the beautiful world of Booleans). This notion of “this is a lie” is really handy, but it’s important to keep in mind that what we would call a lie in math is not necessarily what we would call a lie otherwise. For instance, if I say if p then q, but p and q are completely unrelated, you may be inclined to call me a liar, but it may be the case that, mathematically, it is a true statement. Consider “if the sky is blue, then circumference of a circle is 2*pi*r”. These have no real association, and in fact it doesn’t even matter what colour the sky is, since the second part is always true. I am not lying, but perhaps being a bit dishonest by suggesting an association.

At the end of the day we have to decouple this sort of thing from its linguistic roots and our notions of logical fallacies (Such as “strawmen” or “tu quoque”, not “affirming the consequent” which is indeed a relevant fallacy), unless we’re in some sort of philosophy or linguistics class. Math exists independently of the real world, and can be used to describe it, but any failing in pairing the two does not imply a failing in the math, but rather a failing in the transformation we have applied between the two.

However most mathematical applications of logical statements are of the form P(x)->Q(x), where the truth of P and Q are dependent on x. In other words we rarely, in practice, actually see situations where the antecedent and consequent are logically disjoint; they tend to be associated somehow. For instance the statement “If n is odd, then n^2 is odd” is a more realistic expression to consider.

Oof, that went on for a while. I actually TA a discrete math course that uses this book (by Kenneth H. Rosen, right?). If you want to supplement the book at all, here’s the course webpage with all the prof’s notes, plus sample assignments and tests if you want to actually challenge your understanding beyond the book’s boring sample problems.

4. Kemp says:

“Because it’s an OR proposition, for it to be false, both conditionals must be false. And, conditionals are only false when their antecedents are true but their conclusions are false. So, the left side is only false when r is true and BOTH of p and q are false.”

Referring to “(p→r)∨(q→r)”. Surely it’s only false when r is false and both of p and q are true?

• ZachWeiner says:

Yep! Fixed.

5. sam says:

So one way to think of this (it seems like this is how you’re thinking of it, but maybe not explicitly) is in terms of “lying”. This is just a heuristic.

We want to reason about “if P then Q”, i.e. P -> Q. When should it be true, when should it be false? Let us say that P->Q is false exactly when whenever I present an argument of the form “if P then Q”, that I am lying (it is “invalid”).

P = “we go on a date”
Q = “I sleep with you”.

If P and Q are true, my argument was not a lie. I said that if we go on a date, then I’ll sleep with you, and… that’s what happened. I’m not lying.

What about if P is false? That is, we didn’t go on a date. Well…it doesn’t really matter what Q is then — I won’t be lying either way. If we don’t go on a date and I don’t sleep with you, then that’s hardly unexpected (I’m not lying), whilst if we don’t go on a date and I DO sleep with you…that’s a bonus, but I hardly ruled that out. I’m not lying independent of what Q is.

P True, Q True means P -> Q True
P False, Q True means P -> Q True
P False, Q False means P-> Q True

So, surely then, if our “conditional implication” isn’t just tautology, then NECESSARILY we must have that P True Q False means P->Q False. But this makes sense anyway.

If I go on a date with you, and I don’t sleep with you…after saying that if I go on a date with you, then I’ll sleep with you…I have lied.

————————-

This sort of reasoning makes the truth table seem sensible.

And it helps in another respect: when was I lying? When I told you I would do something Q given a condition P, and then P happened, and I didn’t do Q.

~(P->Q) = P and ~Q.

To prove a statement by contradiction you must LIVE and BREATHE negations like that. That’s because our theorems essentially have the form P->Q.

anyway I’ll stop here, rock on dude

6. John says:

I’m mad with lust. It’s a pity you are married.

7. Jeremy says:

What book are you using for Discrete? Looking to pick one up myself.

• ZachWeiner says:

Discrete Mathematics and Its Applications, 6th Ed. by Rosen.

8. Jeff says:

I was filling out a questionnaire earlier today for some medical stuff, and one of the questions was “if female, have you been pregnant in the last six months?”.