Misplaced Pages

#5994

68-635: In general, a necessary condition is one (possibly one of several conditions) that must be present in order for another condition to occur, while a sufficient condition is one that produces the said condition. The assertion that a statement is a "necessary and sufficient" condition of another means that the former statement is true if and only if the latter is true. That is, the two statements must be either simultaneously true, or simultaneously false. In ordinary English (also natural language ) "necessary" and "sufficient" indicate relations between conditions or states of affairs, not statements. For example, being

136-452: 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 as iff .) That is, having four sides

204-399: A conjunction can be reversed with no effect (by commutativity ): We define R {\displaystyle R} as equal to " ¬ Q {\displaystyle \neg Q} ", and S {\displaystyle S} as equal to ¬ P {\displaystyle \neg P} (from this, ¬ S {\displaystyle \neg S}

272-439: A subject and predicate where the existential impact of the copula implies the proposition as referring to a class with at least one member , in contrast to the conditional form of hypothetical or materially implicative propositions, which are compounds of other propositions, e.g. "If P, then Q" (P and Q are both propositions), and their existential impact is dependent upon further propositions where quantification existence

340-420: A "borderline case" and tolerate its use. In logical formulae , logical symbols, such as ↔ {\displaystyle \leftrightarrow } and ⇔ {\displaystyle \Leftrightarrow } , are used instead of these phrases; see § Notation below. The truth table of P ↔ {\displaystyle \leftrightarrow } Q is as follows: It

408-469: A biconditional directly. An alternative is to prove the disjunction "(P and Q) or (not-P and not-Q)", which itself can be inferred directly from either of its disjuncts—that is, because "iff" is truth-functional , "P iff Q" follows if P and Q have been shown to be both true, or both false. Usage of the abbreviation "iff" first appeared in print in John L. Kelley 's 1955 book General Topology . Its invention

476-409: A change in the quantity of the proposition from universal to particular . Also, notice that contraposition is a method of inference which may require the use of other rules of inference. The contrapositive is the product of the method of contraposition, with different outcomes depending upon whether the contraposition is full, or partial. The successive applications of conversion and obversion within

544-414: A contraposition can only exist in two simple conditionals. However, a contraposition may also exist in two complex, universal conditionals, if they are similar. Thus, ∀ x ( P x → Q x ) {\displaystyle \forall {x}(P{x}\to Q{x})} , or "All P {\displaystyle P} s are Q {\displaystyle Q} s,"

612-410: A distinction between these, in which the first, ↔, is used as a symbol in logic formulas, while ⇔ is used in reasoning about those logic formulas (e.g., in metalogic ). In Łukasiewicz 's Polish notation , it is the prefix symbol E {\displaystyle E} . Another term for the logical connective , i.e., the symbol in logic formulas, is exclusive nor . In TeX , "if and only if"

680-401: A family tree structure. To say that P is necessary and sufficient for Q is to say two things: One may summarize any, and thus all, of these cases by the statement " P if and only if Q ", which is denoted by P ⇔ Q {\displaystyle P\Leftrightarrow Q} , whereas cases tell us that P ⇔ Q {\displaystyle P\Leftrightarrow Q}

748-439: A given domain. It interprets only if as expressing in the metalanguage that the sentences in the database represent the only knowledge that should be considered when drawing conclusions from the database. In first-order logic (FOL) with the standard semantics, the same English sentence would need to be represented, using if and only if , with only if interpreted in the object language, in some such form as: Compared with

SECTION 10

#1732775950006

816-616: A line of a proof, it can be replaced with " ¬ Q → ¬ P {\displaystyle \neg Q\to \neg P} "; or as the statement of a truth-functional tautology or theorem of propositional logic. The principle was stated as a theorem of propositional logic by Russell and Whitehead in Principia Mathematica as where P {\displaystyle P} and Q {\displaystyle Q} are propositions expressed in some formal system . In first-order logic ,

884-533: A man is a necessary condition for being a brother, but it is not sufficient—while being a man sibling is a necessary and sufficient condition for being a brother. Any conditional statement consists of at least one sufficient condition and at least one necessary condition. In data analytics , necessity and sufficiency can refer to different causal logics, where necessary condition analysis and qualitative comparative analysis can be used as analytical techniques for examining necessity and sufficiency of conditions for

952-559: A necessary and sufficient condition for invertibility of a matrix M is that M has a nonzero determinant . Mathematically speaking, necessity and sufficiency are dual to one another. For any statements S and N , the assertion that " N is necessary for S " is equivalent to the assertion that " S is sufficient for N ". Another facet of this duality is that, as illustrated above, conjunctions (using "and") of necessary conditions may achieve sufficiency, while disjunctions (using "or") of sufficient conditions may achieve necessity. For

1020-423: A particular outcome of interest. In the conditional statement, "if S , then N ", the expression represented by S is called the antecedent , and the expression represented by N is called the consequent . This conditional statement may be written in several equivalent ways, such as " N if S ", " S only if N ", " S implies N ", " N is implied by S ", S → N , S ⇒ N and " N whenever S ". In

1088-417: A result, proving or disproving either one of these statements automatically proves or disproves the other, as they are logically equivalent to each other. A proposition Q is implicated by a proposition P when the following relationship holds: This states that, "if P {\displaystyle P} , then Q {\displaystyle Q} ", or, "if Socrates is a man , then Socrates

1156-550: A statement easier. For example, if one wishes to prove that every girl in the United States (A) has brown hair (B), one can either try to directly prove A → B {\displaystyle A\to B} by checking that all girls in the United States do indeed have brown hair, or try to prove ¬ B → ¬ A {\displaystyle \neg B\to \neg A} by checking that all girls without brown hair are indeed all outside

1224-475: A statement has its antecedent and consequent inverted and flipped . Conditional statement P → Q {\displaystyle P\rightarrow Q} . In formulas : the contrapositive of P → Q {\displaystyle P\rightarrow Q} is ¬ Q → ¬ P {\displaystyle \neg Q\rightarrow \neg P} . If P , Then Q . — If not Q , Then not P . " If it

1292-548: A sufficient condition (i.e., individually necessary and jointly sufficient), as shown in Example 5. If P is sufficient for Q , then knowing P to be true is adequate grounds to conclude that Q is true; however, knowing P to be false does not meet a minimal need to conclude that Q is false. The logical relation is, as before, expressed as "if P , then Q " or " P ⇒ Q ". This can also be expressed as " P only if Q ", " P implies Q " or several other variants. It may be

1360-445: A third facet, identify every mathematical predicate N with the set T ( N ) of objects, events, or statements for which N holds true; then asserting the necessity of N for S is equivalent to claiming that T ( N ) is a superset of T ( S ), while asserting the sufficiency of S for N is equivalent to claiming that T ( S ) is a subset of T ( N ). Psychologically speaking, necessity and sufficiency are both key aspects of

1428-448: Is a metalogical symbol meaning that ( ¬ Q → ¬ P ) {\displaystyle (\neg Q\to \neg P)} is a syntactic consequence of ( P → Q ) {\displaystyle (P\to Q)} in some logical system; or as a rule of inference: where the rule is that wherever an instance of " P → Q {\displaystyle P\to Q} " appears on

SECTION 20

#1732775950006

1496-412: Is a necessary and sufficient condition that it contain no odd-length cycles . Thus, discovering whether a graph has any odd cycles tells one whether it is bipartite and conversely. A philosopher might characterize this state of affairs thus: "Although the concepts of bipartiteness and absence of odd cycles differ in intension , they have identical extension . In mathematics, theorems are often stated in

1564-411: Is a proper or improper subset of P. "P if and only if Q" and "Q if and only if P" both mean that the sets P and Q are identical to each other. Iff is used outside the field of logic as well. Wherever logic is applied, especially in mathematical discussions, it has the same meaning as above: it is an abbreviation for if and only if , indicating that one statement is both necessary and sufficient for

1632-400: Is a sufficient condition for N , while the second implication suggests that S is a necessary condition for N . This is expressed as " S is necessary and sufficient for N ", " S if and only if N ", or S ⇔ N {\displaystyle S\Leftrightarrow N} . The assertion that Q is necessary for P is colloquially equivalent to " P cannot be true unless Q

1700-443: Is a valid form of immediate inference only when applied to "A" and "O" propositions. It is not valid for "I" propositions, where the obverse is an "O" proposition which has no valid converse . The contraposition of the "E" proposition is valid only with limitations ( per accidens ). This is because the obverse of the "E" proposition is an "A" proposition which cannot be validly converted except by limitation, that is, contraposition plus

1768-485: Is both necessary to be a quadrilateral, and alone sufficient to deem it a quadrilateral. In traditional logic , contraposition is a form of immediate inference in which a proposition is inferred from another and where the former has for its subject the contradictory of the original logical proposition's predicate . In some cases, contraposition involves a change of the former's quality (i.e. affirmation or negation). For its symbolic expression in modern logic, see

1836-429: Is contraposed to ∀ x ( ¬ Q x → ¬ P x ) {\displaystyle \forall {x}(\neg Q{x}\to \neg P{x})} , or "All non- Q {\displaystyle Q} s are non- P {\displaystyle P} s." The transposition rule may be expressed as a sequent : where ⊢ {\displaystyle \vdash }

1904-472: Is equal to ¬ ¬ P {\displaystyle \neg \neg P} , which is equal to just P {\displaystyle P} ): 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: By reverting R and S back into P {\displaystyle P} and Q {\displaystyle Q} , we then obtain

1972-639: Is equivalent to that produced by the XNOR gate , and opposite to that produced by the XOR gate . The corresponding logical symbols are " ↔ {\displaystyle \leftrightarrow } ", " ⇔ {\displaystyle \Leftrightarrow } ", and ≡ {\displaystyle \equiv } , and sometimes "iff". These are usually treated as equivalent. However, some texts of mathematical logic (particularly those on first-order logic , rather than propositional logic ) make

2040-548: Is human ." In a conditional such as this, P {\displaystyle P} is the antecedent , and Q {\displaystyle 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. Thus a contrapositive generally takes the form of: That is, "If not- Q {\displaystyle Q} , then not- P {\displaystyle P} ", or, more clearly, "If Q {\displaystyle Q}

2108-404: Is identical to P ⇒ Q ∧ Q ⇒ P {\displaystyle P\Rightarrow Q\land Q\Rightarrow P} . For example, in graph theory a graph G is called bipartite if it is possible to assign to each of its vertices the color black or white in such a way that every edge of G has one endpoint of each color. And for any graph to be bipartite, it

Necessity and sufficiency - Misplaced Pages Continue

2176-420: Is instantiated (existential instantiation), not on the hypothetical or materially implicative propositions themselves. Full contraposition is the simultaneous interchange and negation of the subject and predicate, and is valid only for the type "A" and type "O" propositions of Aristotelian logic , while it is conditionally valid for "E" type propositions if a change in quantity from universal to particular

2244-429: Is made ( partial contraposition ). Since the valid obverse is obtained for all the four types (A, E, I, and O types) of traditional propositions, yielding propositions with the contradictory of the original predicate, (full) contraposition is obtained by converting the obvert of the original proposition. For "E" statements, partial contraposition can be obtained by additionally making a change in quantity. Because nothing

2312-530: Is necessary and sufficient for P . We can write P ⇔ Q ≡ Q ⇔ P {\displaystyle P\Leftrightarrow Q\equiv Q\Leftrightarrow P} and say that the statements " P is true if and only if Q , is true" and " Q is true if and only if P is true" are equivalent. If and only if ↔⇔≡⟺ Logical symbols representing iff    In logic and related fields such as mathematics and philosophy , " if and only if " (often shortened as " iff ")

2380-474: Is necessary for that someone to be N amed. Similarly, in order for human beings to live, it is necessary that they have air. One can also say S is a sufficient condition for N (refer again to the third column of the truth table immediately below). If the conditional statement is true, then if S is true, N must be true; whereas if the conditional statement is true and N is true, then S may be true or be false. In common terms, "the truth of S guarantees

2448-409: Is not the case that B is not true. Therefore, B must be true: Combining the two proved statements together, we obtain the sought-after logical equivalence between a conditional and its contrapositive: Logical 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

2516-427: Is not the case, then P is not the case." Using our example, this is rendered as "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, and when one is false, the other is also false. Strictly speaking,

2584-408: Is not true (assuming that we are dealing with bivalent statements that are either true or false): We can apply the same process the other way round, starting with the assumptions that: Here, 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 a contradiction, which means that it

2652-652: Is often credited to Paul Halmos , who wrote "I invented 'iff,' for 'if and only if'—but I could never believe I was really its first inventor." It is somewhat unclear how "iff" was meant to be pronounced. In current practice, the single 'word' "iff" is almost always read as the four words "if and only if". However, in the preface of General Topology , Kelley suggests that it should be read differently: "In some cases where mathematical content requires 'if and only if' and euphony demands something less I use Halmos' 'iff'". The authors of one discrete mathematics textbook suggest: "Should you need to pronounce iff, really hang on to

2720-494: Is often more natural to express if and only if as if together with a "database (or logic programming) semantics". They give the example of the English sentence "Richard has two brothers, Geoffrey and John". In a database or logic program , this could be represented simply by two sentences: The database semantics interprets the database (or program) as containing all and only the knowledge relevant for problem solving in

2788-411: Is paraphrased by the biconditional , a logical connective between statements. The biconditional is true in two cases, where either both statements are true or both are false. The connective is biconditional (a statement of material equivalence ), and can be likened to the standard material conditional ("only if", equal to "if ... then") combined with its reverse ("if"); hence the name. The result

Necessity and sufficiency - Misplaced Pages Continue

2856-452: Is proven below, using the following lemmas proven here : We also use the method of the hypothetical syllogism metatheorem as a shorthand for several proof steps. The proof is as follows: Take 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

2924-469: Is raining, then I wear my coat" — "If I don't wear my coat, then it isn't raining." The law of contraposition says that a conditional statement is true if, and only if, its contrapositive is true. Contraposition ( ¬ Q → ¬ P {\displaystyle \neg Q\rightarrow \neg P} ) can be compared with three other operations: Note that if P → Q {\displaystyle P\rightarrow Q}

2992-515: Is rational ( S ) is sufficient but not necessary to x {\displaystyle x} being a real number ( N ) (since there are real numbers that are not rational). A condition can be both necessary and sufficient. For example, at present, "today is the Fourth of July " is a necessary and sufficient condition for "today is Independence Day in the United States ". Similarly,

3060-433: Is said in the definition of contraposition with regard to the predicate of the inferred proposition , it can be either the original subject, or its contradictory, resulting in two contrapositives which are the obverts of one another in the "A", "O", and "E" type propositions. By example: from an original, 'A' type categorical proposition, which presupposes that all classes have members and the existential import presumed in

3128-450: Is shown as a long double arrow: ⟺ {\displaystyle \iff } via command \iff or \Longleftrightarrow. In most logical systems , one proves a statement of the form "P iff Q" by proving either "if P, then Q" and "if Q, then P", or "if P, then Q" and "if not-P, then not-Q". Proving these pairs of statements sometimes leads to a more natural proof, since there are not obvious conditions in which one would infer

3196-406: Is that the truth of either one of the connected statements requires the truth of the other (i.e. either both statements are true, or both are false), though it is controversial whether the connective thus defined is properly rendered by the English "if and only if"—with its pre-existing meaning. For example, P if and only if Q means that P is true whenever Q is true, and the only case in which P

3264-441: Is true and one is given that Q {\displaystyle Q} is false (i.e., ¬ Q {\displaystyle \neg Q} ), then it can logically be concluded that P {\displaystyle P} must be also false (i.e., ¬ P {\displaystyle \neg P} ). This is often called the law of contrapositive , or the modus tollens rule of inference . In

3332-575: Is true is if Q is also true, whereas in the case of P if Q , there could be other scenarios where P is true and Q is false. In writing, phrases commonly used as alternatives to P "if and only if" Q include: Q is necessary and sufficient for P , for P it is necessary and sufficient that Q , P is equivalent (or materially equivalent) to Q (compare with material implication ), P precisely if Q , P precisely (or exactly) when Q , P exactly in case Q , and P just in case Q . Some authors regard "iff" as unsuitable in formal writing; others consider it

3400-491: Is true or false. This is only false when P {\displaystyle P} is true and Q {\displaystyle Q} is false. Therefore, we can reduce this proposition to the statement "False when P {\displaystyle P} and not- Q {\displaystyle Q} " (i.e. "True when it is not the case that P {\displaystyle P} and not- Q {\displaystyle Q} "): The elements of

3468-474: Is true" or "if Q is false, then P is false". By contraposition , this is the same thing as "whenever P is true, so is Q ". The logical relation between P and Q is expressed as "if P , then Q " and denoted " P ⇒ Q " ( P implies Q ). It may also be expressed as any of " P only if Q ", " Q , if P ", " Q whenever P ", and " Q when P ". One often finds, in mathematical prose for instance, several necessary conditions that, taken together, constitute

SECTION 50

#1732775950006

3536-450: The Euler diagram shown, 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, which can be expressed as: is the contrapositive of the above statement. Therefore, one can say that In practice, this equivalence can be used to make proving

3604-454: The only if half of the definition is interpreted as a sentence in the metalanguage stating that the sentences in the definition of a predicate are the only sentences determining the extension of the predicate. Euler diagrams show logical relationships among events, properties, and so forth. "P only if Q", "if P then Q", and "P→Q" all mean that P is a subset , either proper or improper, of Q. "P if Q", "if Q then P", and Q→P all mean that Q

3672-423: The rule of transposition . Contraposition also has philosophical application distinct from the other traditional inference processes of conversion and obversion where equivocation varies with different proposition types. In traditional logic , the process of contraposition is a schema composed of several steps of inference involving categorical propositions and classes . A categorical proposition contains

3740-420: The "if" of a definition is interpreted as meaning "if and only if". The majority of textbooks, research papers and articles (including English Misplaced Pages articles) follow the linguistic convention of interpreting "if" as "if and only if" whenever a mathematical definition is involved (as in "a topological space is compact if every open cover has a finite subcover"). Moreover, in the case of a recursive definition ,

3808-414: The 'ff' so that people hear the difference from 'if'", implying that "iff" could be pronounced as [ɪfː] . Conventionally, definitions are "if and only if" statements; some texts — such as Kelley's General Topology — follow this convention, and use "if and only if" or iff in definitions of new terms. However, this usage of "if and only if" is relatively uncommon and overlooks the linguistic fact that

3876-455: The US. In particular, if one were to find at least one girl without brown hair within the US, then one would have disproved ¬ B → ¬ A {\displaystyle \neg B\to \neg A} , and equivalently A → B {\displaystyle A\to B} . In general, for any statement where A implies B , not B always implies not A . As

3944-448: The above situation of "N whenever S," N is said to be a necessary condition for S . In common language, this is equivalent to saying that if the conditional statement is a true statement, then the consequent N must be true—if S is to be true (see third column of " truth table " immediately below). In other words, the antecedent S cannot be true without N being true. For example, in order for someone to be called S ocrates, it

4012-401: The application of logic programming to the representation of legal texts and legal reasoning. Contraposition In logic and mathematics , contraposition , or transposition , refers to the inference of going from a conditional statement into its logically equivalent contrapositive , and an associated proof method known as § Proof by contrapositive . The contrapositive of

4080-417: The case that several sufficient conditions, when taken together, constitute a single necessary condition (i.e., individually sufficient and jointly necessary), as illustrated in example 5. A condition can be either necessary or sufficient without being the other. For instance, being a mammal ( N ) is necessary but not sufficient to being human ( S ), and that a number x {\displaystyle x}

4148-412: The classical view of concepts. Under the classical theory of concepts, how human minds represent a category X, gives rise to a set of individually necessary conditions that define X. Together, these individually necessary conditions are sufficient to be X. This contrasts with the probabilistic theory of concepts which states that no defining feature is necessary or sufficient, rather that categories resemble

SECTION 60

#1732775950006

4216-410: The conditional is defined as: which can be made equivalent to its contrapositive, as follows: Let: 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 (by Modus Ponens ). However, it is given that B is not true, so we have a contradiction. Therefore, A

4284-578: The desired contrapositive: In Hilbert-style deductive systems for propositional logic, only one side of the transposition is taken as an axiom, and the other is a theorem. We describe a proof of this theorem in the system of three axioms proposed by Jan Łukasiewicz : (A3) already gives one of the directions of the transposition. The other side, ( ψ → ϕ ) → ( ¬ ϕ → ¬ ψ ) {\displaystyle (\psi \to \phi )\to (\neg \phi \to \neg \psi )} ,

4352-418: The form " P is true if and only if Q is true". Because, as explained in previous section, necessity of one for the other is equivalent to sufficiency of the other for the first one, e.g. P ⇐ Q {\displaystyle P\Leftarrow Q} is equivalent to Q ⇒ P {\displaystyle Q\Rightarrow P} , if P is necessary and sufficient for Q , then Q

4420-426: The form of categorical propositions, one can derive first by obversion the 'E' type proposition, The contrapositive of the original proposition is then derived by conversion to another 'E' type proposition, The process is completed by further obversion resulting in the 'A' type proposition that is the obverted contrapositive of the original proposition, The schema of contraposition: Notice that contraposition

4488-419: The other. This is an example of mathematical jargon (although, as noted above, if is more often used than iff in statements of definition). The elements of X are all and only the elements of Y means: "For any z in the domain of discourse , z is in X if and only if z is in Y ." In their Artificial Intelligence: A Modern Approach , Russell and Norvig note (page 282), in effect, that it

4556-462: The standard semantics for FOL, the database semantics has a more efficient implementation. Instead of reasoning with sentences of the form: it uses sentences of the form: to reason forwards from conditions to conclusions or backwards from conclusions to conditions . The database semantics is analogous to the legal principle expressio unius est exclusio alterius (the express mention of one thing excludes all others). Moreover, it underpins

4624-588: The truth of N ". For example, carrying on from the previous example, one can say that knowing that someone is called S ocrates is sufficient to know that someone has a N ame. A necessary and sufficient condition requires that both of the implications S ⇒ N {\displaystyle S\Rightarrow N} and N ⇒ S {\displaystyle N\Rightarrow S} (the latter of which can also be written as S ⇐ N {\displaystyle S\Leftarrow N} ) hold. The first implication suggests that S

#5994