Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to understand the fundamentals of mathematical logic in order to be able to study discrete mathematics and computer science soon.

I have a big problem understanding Implication. I understand the idea intuitively very well; for example:

$$ x >0 \implies 2x>0 .$$

Or

$$ x \text{ is a prime number} \implies x \geq 2 .$$

I notice that there is always a (connection) between the hypothesis and the conclusion; they seem to be related and fall in the same context.

What i don't understand is: according to the truth table, any two propositions can be linked through an implication even if they are not related at all, or they belong to different contexts.

For example :

$$ \text{A day is 24 hours} \implies \text{A cat has four legs and a tail} .$$

which is logically or mathematically TRUE, because both statements are true and according to the truth table when when both inputs are true for any two statements then the implication is true.

How can that be true?

Another example:

$$ 2 \text{ is a prime number} \implies \text{An hour is 60 minutes}.$$

again, which is logically or mathematically TRUE, because both statements are true and according to the truth table when when both inputs are true for any two statements, then the implication is true.

How can that be true? That's my first question.

The second question could be the same:

How can we use truth tables with implication anyway?

What i understand is truth tables are used to list the probabilities of the output based on the logical values of the inputs. So the value of the output of any line in the truth table depends (only) on the logical values of the inputs in that line and has nothing to do with the conditional connection between the two inputs.

How can we display a conditional statement in a truth table the same way we display a logic gate or so? In other words, how can I tell only from the values of $P$ and $Q$ that $P \implies Q$?

share|improve this question
    
In zeroth order logic (no quantifiers) a formula is true from the truth table standpoint, iff it can be deduced in propositional calculus using rules like Modus Ponens. In Propositional calculus, the meaning of implication is much closer to your intuition, although it ends up yielding the same true formulas. –  Grumpy Parsnip Oct 21 '11 at 1:42
2  
A recent blog post by Tim Gowers attempts to explain this in somewhat mind-numbing detail. It makes the central point that while the mathematical meaning of implication can feel arbitrary when it connects concrete statements, it is necessary and natural when $\Rightarrow$ connects two parameterized statements. –  Henning Makholm Oct 21 '11 at 2:01

5 Answers 5

Here is the truth table for an implication:

$$ \begin{array}{ccccc} P & & Q & & P \to Q \\ T & & T & & T \\ T & & F & & F \\ F & & T & & T \\ F & & F & & T \end{array} $$

You can think of an implication as a conditional promise. If you keep the promise, it's true. If you break the promise, it's false.

If I tell my kids, "I'll give you a cookie if you clean up." Then they clean up. I better give them a cookie. If I don't, I've lied. However, if they don't clean up, I can either give them a cookie or not. I didn't promise either if they didn't keep up their end of the bargain.

So in other words, an implication is false only if the hypothesis is true and conclusion is false.

Logically $P \to Q$ is equivalent to $\neg P \vee Q$

I had a computer science professor who was fond of promising his kids things given a false premise. This way he wasn't compelled to follow through. Example: "If the moon is made of green cheese, I'll give you an x-box."

share|improve this answer
1  
+1 very nice answer :-) –  mathmath8128 Oct 21 '11 at 5:59
    
Made my day! +1 –  Shashank Sawant Feb 17 at 2:26

Think about it this way:

If a day is 24 hours, does a cat have 4 legs and a tail?

Even though they are unrelated, the answer is yes, so a 24-hour day implies that a cat has 4 legs & tail.

If 2 is a prime number, does an hour have 60 minutes? Yes.

Going with the cookie idea, let's say you already have a cookie in your hand and you are about to give it to your kid. She says "If I clean my room, can I have a cookie?" You will likely say "yes!" Technically, it's true that you'll give her a cookie if she cleans her room. She doesn't need to know she was going to get it anyway.

share|improve this answer
3  
It's more interesting when the antecedent is false, e.g. ... If London is in Asia, is London in Europe? –  r.e.s. Oct 21 '11 at 5:48
    
@r.e.s. Yes, "If London is in Asia, then London is in Europe" comes as true given that the "if-then" gets interpreted via the material conditional of classical logic. –  Doug Spoonwood Oct 22 '11 at 23:36
    
@Doug Spoonwood: Right. (I wasn't actually asking this question, but was citing it as an example.) –  r.e.s. Oct 23 '11 at 11:34
    
@r.e.s. I suspected that, but I thought I'd say that just in case you were asking a question. –  Doug Spoonwood Oct 23 '11 at 23:07

As long as all atomic propositions P, Q, R, ... within a compound formula C get assigned truth values in {0, 1}, it holds that C will take on a truth value in {0, 1}. Here 0 indicates falsity and 1 truth. By atomic proposition, I mean any variable such a "p", "q", or "r" or constant such as "1" or "0". This consists of a way of stating the principle of truth-functionality in classical propositional logic. So, as long as p and q get assigned truth values in {0, 1}, (p->q) will have a truth value in {0, 1} by this principle. Here "->" indicates a truth function of two arguments, specifically the material conditional.

So, if you assign both p and q a truth value of 1, then just by the principle of truth-functionality (p->q) will have a value in {0, 1}. So, if p is true, and q is true, is (p->q) false or true? Well, you pointed out above, (x >0) ====> (2x>0) is true, when (x>0) is true and (2x>0) is true. So, you know of at least one instance with (p->q) true with both p true and q true as well. Now, if you were to accept a single instance of (p->q) as false with both p true and q true as well, then you would either have a violation of the principle of truth-functionality in classical propositional logic, or you would render it inconsistent (since (p->q) takes on truth value true in one case where p and q come as true, and another where (p->q) takes on truth value false in another case where p and q come as true). Both come as problematic for classical propositional logic. So, basically to speak consistently you have to accept (p->q) as true in classical propositional logic anytime you have p true and q true.

The catch lies in that the truth values of the atomic propositions (the variables or constants) and the definitions of the logical operations (truth-functions) completely determine the truth value of a particular instance of something like (p->q). The meaning of the "p" and "q" bears utterly no relevance on the truth value of (p->q), only the truth values of "p" and "q" do. The principle of truth-functionality entails this.

Now, there do exist other ways to interpret a word like "implies" other than by "->", or some other symbol which might get used for the material conditional. As one well-known example, some logicians have interpreted "implies" as a strict conditional. However, these interpretations refer to something which is not truth-functional. To reiterate, a true statement A can "imply" a seemingly unrelated statement B, because of the principle of truth-functionality. The meaning of something like (p->q) isn't so much that p implies q in the sense of some sort of connection between p and q, but rather that it is not the case that p stands as true and q stands as false simultaneously.

Truth tables don't list probabilities. They tell you what logical value of the output IS on the basis of the input(s). The truth table depends on the values of the inputs, AND the function, that is the connective, which links them together. The truth tables for conjunction and the material conditional have the same inputs, however, they have different connectives linking together the variables, and thus have different outputs in their final column.

As this truth table indicates:

p   q  (p->q)
0   0     1
0   1     1
1   0     0
1   1     1

If p is false, then (p->q) is true. If q is true, then (p->q) is true. If p is true, then (p->q) has the same truth value as that of q. If q is false, then (p->q) has the same truth value as the negation of p.

Addendum: In classical logic any given true statement (tautology) comes as related to any other true statement and belongs to the same context as any other true statement. They come as related in that given any true statement, you can derive any other true statement. They belong to the same context in that they exist within the scope of a single derivation.

share|improve this answer

Yes, implication like this is weird. You feel like the antecedent must be somehow relevant to the consequent. It just turns out that it makes mathematical reasoning much ...cleaner... if you operate with it using the truth table rules.

The way you should think of implication in mathematical setting is by how upset you would be if some one claimed 'P implies Q' based on which of P and Q are true or not. The only situation where you should be upset is if P is true and Q is false (that definitely goes against what implication means). If P is true and Q is true, then obviously implication works out. What if P is false? Should you be mad/upset whatever Q is? I don't think so.

Convince yourself that it should be OK. And anyway mathematical culture has accepted that such a (stipulated) definition (of implication as only being false when P is true and Q is false) is the most useful way to define it.

This is really just a wordy explanation of the truth table; also an explanation that sometimes things are just defined that way to make things easier. Take for example the natural number 1. Is it a prime? by most informal definitions of 'prime' it is. It just turns out that number theory theorems and proofs are simpler to state if you treat 1 separately (and call it 'unit').

share|improve this answer

Our common thinking of implication ($P \implies Q$) is that P allows us to say wether Q is true. But if we already know that Q is true, this way of thinking does not make sense anymore.

Your confusion stems from the fact that you think P would have any implication on Q, which cannot be the case because Q is already given. The statement is true nevertheless, see here.

Take the example given in an other answer, where "clean up" implies "get cookie". I think it helps understanding a special case, but it is not a good one, because we can assume "clean up" would lead to "get cookie", if "get cookie" were false. But the statement holds true even for things that will never lead to "get cookie". In other words, if it is really decided, that "get cookie" is true, you can say anything in your if-sentence and the statement still holds:

If you crash the car, I will give you a cookie.

Our common understanding of this sentence is, that the cookie is the reward for crashing the car. But this does not make sense in this situation, so nobody would normally formulate it this way, but rather:

You can do anything, I will give you a cookie.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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