Implication
(point to WP article that's about what this article is actually talking about) 

(26 intermediate revisions by 4 users not shown)  
Line 1:  Line 1:  
−  '''Implication''' is a [[logic]]al operation on two variables. "P implies Q" is  +  {{wikipediaMaterial conditional}}<! note: lots of stuff in bold because of incoming redirects > 
+  '''Implication''' is a [[logic]]al operation on two statements, typically represented by the variables P and Q. "P '''implies''' Q" is written symbolically as "P → Q". Equivalent statements include:  
+  * "'''if''' P '''then''' Q"  
+  * "P is '''sufficient''' for Q"  
+  * "Q is '''necessary''' for P"  
+  
+  The statement "if P then Q" is called a '''conditional''' statement; P is known as the '''antecedent''' and Q the '''consequent'''.  
+  
+  The statement "P '''if and only if''' Q", a '''biconditional''' statement, means the same thing as "P implies Q, and Q implies P". Other equivalent meanings include:  
+  * "P is '''logically equivalent''' to Q"  
+  * "P is a necessary and sufficient condition for Q".  
+  
+  The phrase "if and only if" is often abbreviated '''iff''', especially in mathematics.  
+  
+  Other related concepts, discussed below, include:<! again, because of incoming redirects >  
+  * [[#Unless and only if'''unless''' and '''only if''']]  
+  * [[#Transformations of conditionals'''contrapositive''', '''inverse''', and '''converse''']]  
+  <! not sure what to do with "material implication" incoming redirect... (see Talk) >  
==Definition==  ==Definition==  
Implication, the result of "P → Q" is defined by the following table:  Implication, the result of "P → Q" is defined by the following table:  
−  {  +  { class="wikitable" 
 '''P'''   '''P'''  
 '''Q'''   '''Q'''  
Line 25:  Line 42:  
}  }  
−  +  Note that if P is true, then Q must also be true for the implication to hold (be true). However, if P is false, Q ''may or may not'' be true and the implication still holds.  
−  +  To illustrate the latter fact, consider a teacher who tells her class that any student who gets 100% on the final exam will pass the class. In other words:  
−  : '''P''': A student gets 100% on the final  +  : '''P''': A student gets 100% on the final. 
−  : '''Q''': That student passes the class  +  : '''Q''': That student passes the class. 
−  : '''P → Q''':  +  : '''P → Q''': If a student gets 100% on the final, then that student passes the class. 
−  Now  +  Now consider the case in which two students do poorly on the final exam; one of them did well enough on the other exams to pass the course, but the other did not. Did the teacher lie? 
−  No. She said nothing about students who do not get 100% on the final (i.e., the case where P is false). Unless there is a student who both got 100% on the final and did not pass the course, the teacher told the truth.  +  No. She said nothing about students who do ''not'' get 100% on the final (i.e., the case where P is false). Unless there is a student who both got 100% on the final and did not pass the course, the teacher told the truth. 
For this reason, "P → Q" can be restated as "¬(P ∧ ¬ Q)" or "not (P and not Q)", or "it is not the case that P is true and Q is false".  For this reason, "P → Q" can be restated as "¬(P ∧ ¬ Q)" or "not (P and not Q)", or "it is not the case that P is true and Q is false".  
−  ==  +  In summary, the following statements are equivalent: 
−  +  { class="wikitable"  
+  ! In symbols !! In English  
+    
+   P → Q  P implies Q; if P then Q; P sufficient for Q; Q necessary for P  
+    
+   ¬(P ∧ ¬Q)  not(P and not Q)  
+    
+   ¬P ∨ Q  (not P) or Q [equivalent by [[De Morgan's laws]]]  
+    
+   ¬Q → ¬P  not Q implies not P  
+  }  
+  
+  ==Unless and only if==  
+  <! this section is linked to from above in this same article >  
+  The statement "P '''unless''' Q" can be translated using implication as "if not Q, then P".  
+  
+  The statement "P '''only if''' Q" is equivalent to "if not Q, then not P", or just "if P then Q". (Note that it is ''not'' equivalent to the superficially similar "P if Q", which means "if Q then P".)  
+  
+  Often "unless" is used in statements with the first proposition negated: "not P unless Q" means "if not Q then not P", or "if P then Q", and so is equivalent to "P only if Q".  
+  
+  To illustrate how "only if" and "unless" statements work, consider a concrete example:  
+  : I will pass the class only if I study hard.  
+  What this means is:  
+  : If I don't study hard, then I won't pass the class.  
+  Or, equivalently (as explained [[#Definitionabove]]):  
+  : I can't both not study hard ''and'' pass the class.  
+  If the last statement were not equivalent to the original, then I might be able to not study and still pass the class — but this contradicts my original assertion that it was ''only'' by studying hard that I would pass.  
+  
+  Using an "unless" statement to say the same thing:  
+  : I won't pass the class unless I study hard.  
+  This means I'll want to study hard to give myself a ''chance'' to pass, but it doesn't ''guarantee'' that I will pass; on the other hand, ''not'' studying will guarantee that I don't pass.  
+  
+  Symbolically, using  
+  : S = I (do/will) study hard.  
+  : P = I (do/will) pass the class.  
+  all of these statements can be written as  
+  : '''¬ S → ¬ P''': If I don't study hard, then I won't pass the class.  
+  or, equivalently  
+  : '''P → S''': If I do pass the class then I will study hard.  
+  
+  Rephrasing the last statement to make more sense grammatically:  
+  : If I end up passing the class, then I must have studied hard.  
+  
+  ==Transformations of conditionals==  
+  <! this section is linked to from above in this same article >  
+  Given a conditional statement "if P then Q", there are many ways of transforming the statement to other conditionals that may or may not be logically equivalent.  
+  : '''Original''': P → Q ("P implies Q")  
+  : '''Contrapositive''': ¬Q → ¬P ("not Q implies not P") — this is logically equivalent  
+  : '''Inverse''': ¬P → ¬Q ("not P implies not Q") — ''not'' equivalent  
+  : '''Converse''': Q → P ("Q implies P") — ''not'' equivalent  
+  
+  For more information, see [[Wikipedia:Contraposition]].  
+  
+  ==Quantifiers==  
+  In [[predicate logic]], statements containing "all" or "for all" can be reexpressed as conditional statements in [[propositional logic]] in the following way:  
+  : ''Statement in predicate logic'': All squares are rectangles.  
+  : ''Statement in propositional logic'': If a figure is a square, then it is a rectangle.  
+  Note how the statement in propositional logic refers to a larger context (figures) that is not explicitly stated in the predicatelogic version.  
+  
+  An interesting effect of "all" statements being equivalent to "if" statements is that the following "nonsensical" statement is actually true:  
+  * All positive numbers that are both even and odd are divisible by 17.  
+  How can this be? Clearly there are no positive numbers that are both even and odd, so how can they be divisible by 17? Well, the above statement is equivalent to the following:  
+  * If there is any positive number that is both even and odd, then it will be divisible by 17.  
+  The antecedent here (the "if" part) is false, but we have seen that a conditional statement is true when its antecedent is false, no matter what the consequent is; so the statement is true.  
+  
+  {{Formal logic}}  
+  
+  [[Category:Logic]] 
Latest revision as of 06:12, 16 July 2012
Implication is a logical operation on two statements, typically represented by the variables P and Q. "P implies Q" is written symbolically as "P → Q". Equivalent statements include:
 "if P then Q"
 "P is sufficient for Q"
 "Q is necessary for P"
The statement "if P then Q" is called a conditional statement; P is known as the antecedent and Q the consequent.
The statement "P if and only if Q", a biconditional statement, means the same thing as "P implies Q, and Q implies P". Other equivalent meanings include:
 "P is logically equivalent to Q"
 "P is a necessary and sufficient condition for Q".
The phrase "if and only if" is often abbreviated iff, especially in mathematics.
Other related concepts, discussed below, include:
Contents 
Definition
Implication, the result of "P → Q" is defined by the following table:
P  Q  P→Q 
True  True  True 
True  False  False 
False  True  True 
False  False  True 
Note that if P is true, then Q must also be true for the implication to hold (be true). However, if P is false, Q may or may not be true and the implication still holds.
To illustrate the latter fact, consider a teacher who tells her class that any student who gets 100% on the final exam will pass the class. In other words:
 P: A student gets 100% on the final.
 Q: That student passes the class.
 P → Q: If a student gets 100% on the final, then that student passes the class.
Now consider the case in which two students do poorly on the final exam; one of them did well enough on the other exams to pass the course, but the other did not. Did the teacher lie?
No. She said nothing about students who do not get 100% on the final (i.e., the case where P is false). Unless there is a student who both got 100% on the final and did not pass the course, the teacher told the truth.
For this reason, "P → Q" can be restated as "¬(P ∧ ¬ Q)" or "not (P and not Q)", or "it is not the case that P is true and Q is false".
In summary, the following statements are equivalent:
In symbols  In English 

P → Q  P implies Q; if P then Q; P sufficient for Q; Q necessary for P 
¬(P ∧ ¬Q)  not(P and not Q) 
¬P ∨ Q  (not P) or Q [equivalent by De Morgan's laws] 
¬Q → ¬P  not Q implies not P 
Unless and only if
The statement "P unless Q" can be translated using implication as "if not Q, then P".
The statement "P only if Q" is equivalent to "if not Q, then not P", or just "if P then Q". (Note that it is not equivalent to the superficially similar "P if Q", which means "if Q then P".)
Often "unless" is used in statements with the first proposition negated: "not P unless Q" means "if not Q then not P", or "if P then Q", and so is equivalent to "P only if Q".
To illustrate how "only if" and "unless" statements work, consider a concrete example:
 I will pass the class only if I study hard.
What this means is:
 If I don't study hard, then I won't pass the class.
Or, equivalently (as explained above):
 I can't both not study hard and pass the class.
If the last statement were not equivalent to the original, then I might be able to not study and still pass the class — but this contradicts my original assertion that it was only by studying hard that I would pass.
Using an "unless" statement to say the same thing:
 I won't pass the class unless I study hard.
This means I'll want to study hard to give myself a chance to pass, but it doesn't guarantee that I will pass; on the other hand, not studying will guarantee that I don't pass.
Symbolically, using
 S = I (do/will) study hard.
 P = I (do/will) pass the class.
all of these statements can be written as
 ¬ S → ¬ P: If I don't study hard, then I won't pass the class.
or, equivalently
 P → S: If I do pass the class then I will study hard.
Rephrasing the last statement to make more sense grammatically:
 If I end up passing the class, then I must have studied hard.
Transformations of conditionals
Given a conditional statement "if P then Q", there are many ways of transforming the statement to other conditionals that may or may not be logically equivalent.
 Original: P → Q ("P implies Q")
 Contrapositive: ¬Q → ¬P ("not Q implies not P") — this is logically equivalent
 Inverse: ¬P → ¬Q ("not P implies not Q") — not equivalent
 Converse: Q → P ("Q implies P") — not equivalent
For more information, see Wikipedia:Contraposition.
Quantifiers
In predicate logic, statements containing "all" or "for all" can be reexpressed as conditional statements in propositional logic in the following way:
 Statement in predicate logic: All squares are rectangles.
 Statement in propositional logic: If a figure is a square, then it is a rectangle.
Note how the statement in propositional logic refers to a larger context (figures) that is not explicitly stated in the predicatelogic version.
An interesting effect of "all" statements being equivalent to "if" statements is that the following "nonsensical" statement is actually true:
 All positive numbers that are both even and odd are divisible by 17.
How can this be? Clearly there are no positive numbers that are both even and odd, so how can they be divisible by 17? Well, the above statement is equivalent to the following:
 If there is any positive number that is both even and odd, then it will be divisible by 17.
The antecedent here (the "if" part) is false, but we have seen that a conditional statement is true when its antecedent is false, no matter what the consequent is; so the statement is true.
