词条 | Contraposition | ||||||||||||||||||
释义 |
In logic, contraposition is an inference that says that a conditional statement is logically equivalent to its contrapositive. The contrapositive of the statement has its antecedent and consequent inverted and flipped: the contrapositive of is thus . For instance, the proposition "All cats are mammals" can be restated as the conditional "If something is a cat, then it is a mammal". The law of contraposition says that statement is true if, and only if, its contrapositive "If something is not a mammal, then it is not a cat" is true. The contrapositive can be compared with three other relationships between conditional statements:
Note that if is true and we are given that Q is false, , it can logically be concluded that P must be false, . This is often called the law of contrapositive, or the modus tollens rule of inference. Intuitive explanationConsider the Euler diagram shown. According to this diagram, if something is in A, it must be in B as well. So we can interpret "all of A is in B" as: It is also clear that anything that is not within B (the blue region) cannot be within A, either. This statement, is the contrapositive. Therefore, we can say that . Practically speaking, this makes trying to prove something easier. For example, if we want to prove that every girl in the United States (A) has brown hair (B), we can try to directly prove by checking all girls in the United States to see if they all have brown hair. Alternatively, we can try to prove by checking all girls without brown hair to see if they are all outside the US. This means that if we find at least one girl without brown hair within the US, we will have disproved , and equivalently . To conclude, for any statement where A implies B, then not B always implies not A. Proving or disproving either one of these statements automatically proves or disproves the other. They are fully equivalent. Formal definitionA proposition Q is implicated by a proposition P when the following relationship holds: This states that, "if P, then Q", or, "if Socrates is a man, then Socrates is human." In a conditional such as this, P is the antecedent, and Q is the consequent. One statement is the contrapositive of the other only when its antecedent is the negated consequent of the other, and vice versa. The contrapositive of the example is . That is, "If not-Q, then not-P", or, more clearly, "If Q is not the case, then P is not the case." Using our example, this is rendered "If Socrates is not human, then Socrates is not a man." This statement is said to be contraposed to the original and is logically equivalent to it. Due to their logical equivalence, stating one effectively states the other; when one is true, the other is also true. Likewise with falsity. Strictly speaking, a contraposition can only exist in two simple conditionals. However, a contraposition may also exist in two complex conditionals, if they are similar. Thus, , or "All Ps are Qs," is contraposed to , or "All non-Qs are non-Ps." Simple proof by definition of a conditionalIn first-order logic, the conditional is defined as: We have: Simple proof by contradictionLet: It is given that, if A is true, then B is true, and it is also given that B is not true. We can then show that A must not be true by contradiction. For, if A were true, then B would have to also be true (given). However, it is given that B is not true, so we have a contradiction. Therefore, A is not true (assuming that we are dealing with concrete statements that are either true or not true): We can apply the same process the other way round: We also know that B is either true or not true. If B is not true, then A is also not true. However, it is given that A is true; so, the assumption that B is not true leads to contradiction and must be false. Therefore, B must be true: Combining the two proved statements makes them logically equivalent: More rigorous proof of the equivalence of contrapositivesLogical equivalence between two propositions means that they are true together or false together. To prove that contrapositives are logically equivalent, we need to understand when material implication is true or false. This is only false when P is true and Q is false. Therefore, we can reduce this proposition to the statement "False when P and not-Q" (i.e. "True when it is not the case that P and not-Q"): The elements of a conjunction can be reversed with no effect (by commutativity): We define as equal to "", and as equal to (from this, is equal to , which is equal to just ): This reads "It is not the case that (R is true and S is false)", which is the definition of a material conditional. We can then make this substitution: When we swap our definitions of R and S, we arrive at the following: Comparisons
ExamplesTake the statement "All red objects have color." This can be equivalently expressed as "If an object is red, then it has color."
In other words, the contrapositive is logically equivalent to a given conditional statement, though not sufficient for a biconditional. Similarly, take the statement "All quadrilaterals have four sides," or equivalently expressed "If a polygon is a quadrilateral, then it has four sides."
Since the statement and the converse are both true, it is called a biconditional, and can be expressed as "A polygon is a quadrilateral if, and only if, it has four sides." (The phrase if and only if is sometimes abbreviated iff.) That is, having four sides is both necessary to be a quadrilateral, and alone sufficient to deem it a quadrilateral. Truth
ApplicationBecause the contrapositive of a statement always has the same truth value (truth or falsity) as the statement itself, it can be a powerful tool for proving mathematical theorems. A proof by contraposition (contrapositive) is a direct proof of the contrapositive of a statement.[1] However, indirect methods such as proof by contradiction can also be used with contraposition, as, for example, in the proof of the irrationality of the square root of 2. By the definition of a rational number, the statement can be made that "If is rational, then it can be expressed as an irreducible fraction". This statement is true because it is a restatement of a definition. The contrapositive of this statement is "If cannot be expressed as an irreducible fraction, then it is not rational". This contrapositive, like the original statement, is also true. Therefore, if it can be proven that cannot be expressed as an irreducible fraction, then it must be the case that is not a rational number. The latter can be proved by contradiction. The previous example employed the contrapositive of a definition to prove a theorem. One can also prove a theorem by proving the contrapositive of the theorem's statement. To prove that if a positive integer N is a non-square number, its square root is irrational, we can equivalently prove its contrapositive, that if a positive integer N has a square root that is rational, then N is a square number. This can be shown by setting {{radic|N}} equal to the rational expression a/b with a and b being positive integers with no common prime factor, and squaring to obtain N = a2/b2 and noting that since N is a positive integer b=1 so that N = a2, a square number. Correspondence to other mathematical frameworksProbability calculusContraposition represents an instance of Bayes' theorem which in a specific form can be expressed as: . In the equation above the conditional probability generalizes the logical statement , i.e. in addition to assigning TRUE or FALSE we can also assign any probability to the statement. The term denotes the base rate (aka. the prior probability) of . Assume that is equivalent to being TRUE, and that is equivalent to being FALSE. It is then easy to see that when i.e. when is TRUE. This is because so that the fraction on the right-hand side of the equation above is equal to 1, and hence which is equivalent to being TRUE. Hence, Bayes' theorem represents a generalization of contraposition [2]. Subjective logicContraposition represents an instance of the subjective Bayes' theorem in subjective logic expressed as: , where denotes a pair of binomial conditional opinions given by source . The parameter denotes the base rate (aka. the prior probability) of . The pair of inverted conditional opinions is denoted . The conditional opinion generalizes the logical statement , i.e. in addition to assigning TRUE or FALSE the source can assign any subjective opinion to the statement. The case where is an absolute TRUE opinion is equivalent to source saying that is TRUE, and the case where is an absolute FALSE opinion is equivalent to source saying that is FALSE. In the case when the conditional opinion is absolute TRUE the subjective Bayes' theorem operator of subjective logic produces an absolute FALSE conditional opinion and thereby an absolute TRUE conditional opinion which is equivalent to being TRUE. Hence, the subjective Bayes' theorem represents a generalization of both contraposition and Bayes' theorem [3]. See also
References1. ^{{citation|first1=Douglas|last1=Smith|first2=Maurice|last2=Eggen|first3=Richard|last3=St. Andre|title=A Transition to Advanced Mathematics|year=2001|publisher=Brooks/Cole|edition=5th|isbn=0-534-38214-2|page=37}} 2. ^Audun Jøsang 2016:2 3. ^Audun Jøsang 2016:92 Sources
External links
2 : Mathematical logic|Theorems in propositional logic |
||||||||||||||||||
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。