Implication (Discrete math logic)

[janac]

The truth table for implication looks like this

p|q| p -> q
------------
T|T | T
T|F | F
F|T | T <----I'm trying to make sense of this one. My prof warned us that its strange.
F|F | T

I that implication means:
"If p, then q"
"q is necessary for p"
"p is sufficient for q"
"p, only if q"

How can p be false, and q be true, result in a true implication?
How does something false imply something true?

"If 1 + 1 =5 then apples are blue" is a true implication, according to this.

I'm not sure if I have included enough detail about my confusion. I feel like I'm on the verge of understanding, can anyone push me in the right direction?

 

[Number Nine]

That particular case is a convention that's been decided upon because...well, it's convenient in some ways. Essentially, we declare an implication to be false iff p is true and q is false, and all other cases are "true by default" in some sense. Consider that the above case is actually the only situation with the capacity to falsify the implication; since we only have two options for the statement (true or false), it makes some amount of sense to declare all others to be "true".

 

[janac]

Okay, I understand that there are conventions in math, but I find it hardly likely that in a course like Discrete Math (which has a lot to do with proofs), that there would be an arbitrary convention based on the simple reason that its convenient.

Okay fine, let us define a case which is false iff p is true and q is false, and let's say that this is the ONLY case it is false.

Why call this an implication?

How does p imply q, if p is false in the first place. <--this is my main argument
Why does anything false imply true?

The strangest part is that I feel like I can't find much information about this.

Oh and Thanks for the quick reply NumberNine :)

 

[Number Nine]

Actually, quite a few conventions have to do with convenience. For instance, the notion of the "empty set" (which, if you haven't discussed it yet, you will discuss soon) exists, to a great extent, so that we don't have to do things like prove the existence of an intersection before talking about the intersection of two sets (which would be tedious and boring). Note that we're essentially selecting axioms here; we're choosing the rules that govern the logical deductions we'll be making in the future (i.e. we're setting up a logical system, not making inferences based on that system).

The fact is that a statement, by definition, has a truth value (that's what makes it a statement). The implication p -> q has to be either true or false, so you have to assign a truth value to the case where p is false. Since the case where p is false cannot falsify the statement (the implication is, by definition, only false when p is true and q is false), it makes sense to select the only other option, which is "true".

 

[Stephen Tashi]

One way to think about it:

\neg ( p \implies q) \equiv p \ and \neg q

is a natural definition to make because, by the common interpretation of "If p then q", the only way to show that the statement "If p then q" is false is to show a case where p is true but q is false. You can't disprove "If p then q" by giving examples when p isn't true.

So

p \implies q \equiv \neg ( p \ and \neg q)

The truth table for \neg (p \ and \neg q) will match the truth table that you listed for "If p then q".

 

[Erland]

Also in ordinary language, we sometimes use implications in this way. Cosider the following conversation:

A: I read in the newspaper that a population of surviving dinosaurs was discovered in Africa.
B: Hah, if a population of surviving dinosaurs was discovered in Africa then I'm Mickey Mouse!

If we let P be the sentence "A population of surviving dinosaurs was discovered in Africa" and let Q be "B is Mickey Mouse", then both P and Q are false (at least B believes so), yet B pronounces "P implies Q" and intend this to be a true sentence. Since both A and B certainly agree that Q is false, what B actually means is that P is also false, and B expresses it this way in order to ridicule A:s statement.

 

[janac]

Okay, so here are the facts I've picked out about implication. Please let me know if any of them are incorrect.

p -> q

-math has certain conventions to make life easier. Such as bedmas/pemdas, empty set, and the implication truth table

-If the premise is false, the conclusion can be true or false

-If p is false, it has no "power" to falsify q, and since an entire implication statement is only false when p is true and q is false, the entire implication statement must have a truth value, the only option left is, true (since nothing was able to falsify q).

-If implication is defined as the case which is false only when "p is true and q is false" then it can be written as NOT(p AND (NOTq))

-If I am trying to disprove the statement p -> q, regardless of how many examples of false p's I give, the statement still holds true, since the definition of implication didn't mention anything about p being false causing the implication to become false also.

right?




-

 

[Stephen Tashi]

right?

I'll say Yes. The others must speak for themselves.

It is much harder to make sense of the conventions about "p implies q" intutively when p and q are statements (i.e. things that are definitely true or false) versus when they are variables representing statements and proceeded by a quantifier such as "There exists" or "For each".

If you think of a quantified statement like "For each number p and for each number q, if (p > q and q > 3) then p > 3" then it isn't so disturbing to say that the case of p = 1 and q = 2 can't disprove it. In an intuitive way, such a case is part of the "truth" of the quantified statement. You can think of it as verification that the "If..." part correctly chopped out that case from being seriously considered.

Edit: I'm using p and q as variables representing numbers in the example, instead of "variables representing statements". It would have been clearer if I used a variable representing a statement or a "statement function" like A(p,q) = "(p > q and q > 3)", but I hope the basic idea is clear anyway.

 

[Number Nine]

I'll say Yes. The others must speak for themselves.

I'll say yes as well. Keep in mind that the purpose of mathematical logic is to abstract and generalize the reasoning process we use intuitively when dealing with more concrete statements. This generalization can make certain specific examples seem strange (e.g. "If the sky is green, then pigs can fly" is true), even though the rules are, in a sense, the best possible in general.

 

[HallsofIvy]

Suppose that, at the beginning of the semester, your teacher says "if you get an "A" on every test, you will get an "A" for the semester".

You do, in fact, get an "A" on every test except one and you get "B+" on that one.

You get an "A" for the semester. Did your teacher make a true statement?

(Notice that your teacher did not say that this is the only way to get an "A" for the semester, just that it was one way.)

I would argue that there is no way, from the information given here, to know what would happen if you had got an "A" on every test- but certainly there is nothing here that would imply if you had got an "A" on that one test, you would not have gotten an "A" for the semester! I think of it as "innocent until proven guilty"!

 

[janac]

Alright! I actually get it now! It is much easier to understand with variables and quantifiers, as opposed to english propositions.

HallsofIvy, your example did break through to me quite well.

This thread really motivated me to help other people on this forum.

Much appreciation to everyone who helped!

 

[Bacle2]

You may want to do some reading on material implication:

http://www.cuil.pt/r.html?cx=004604...10&ie=UTF-8&q=paradox+of+material+implication

Wikipedia has the basics.