In logic, necessity and sufficiency are terms used to describe a conditional or implicational relationship between statements. For example, in the conditional statement "If P then Q", we say that "Q is necessary for P" because P cannot be true unless Q is true. 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.
Mi a szükséges és mi a elegendő feltétel?
In ordinary English, "necessary" and "sufficient" indicate relations between conditions or states of affairs, not statements. 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. In the above situation, we say that N is a necessary condition for S. In common language this is 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).
Phrased differently, the antecedent S cannot be true without N being true. In the above situation, we can also say S is a sufficient condition for N. Again, consider 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, "S guarantees N".
Kétirányú kapcsolat: szükségesség és elegendőség
A necessary and sufficient condition requires that both of the implications and (which can also be written as ) hold. From the first of these we see that S is a sufficient condition for N, and from the second that S is a necessary condition for N. The assertion that Q is necessary for P is colloquially equivalent to "P cannot be true unless Q is true" or "if Q is false, then P is false".
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".
Példák a mindennapi beszédben
Consider thunder, the sound caused by lightning. We say that thunder is necessary for lightning, since lightning never occurs without thunder. Whenever there's lightning, there's thunder. The thunder does not cause the lightning (since lightning causes thunder), but because lightning always comes with thunder, we say that thunder is necessary for lightning.
Szenátus. If you are under 30 years old, then it is impossible for you to be a senator. In algebra, for some set S together with an operation to form a group, it is necessary that be associative. It is also necessary that S include a special element e such that for every x in S it is the case that e x and x e both equal x.
It is also necessary that for every x in S there exist a corresponding element x″, such that both x x″ and x″ x equal the special element e. 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. Example: "John is a king" implies that John is male.
Formális viszonyok és bizonyítás
Congress passes a bill, the president's signing of the bill is sufficient to make it law. Note that the case whereby the president did not sign the bill, e.g. That the center of a playing card should be marked with a single large spade (♠) is sufficient for the card to be an ace. Three other sufficient conditions are that the center of the card be marked with a diamond (♦), heart (♥), or club (♣), respectively.
Being in the purple region is sufficient for being in A, but not necessary. Being in A is necessary for being in the purple region, but not sufficient. A condition can be either necessary or sufficient without being the other. 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".
Duálitás és bizonyítási elvek
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.
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 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.
Matematikai szemlélet és bizonyítások
In mathematics, theorems are often stated in the form "P is true if and only if Q is true". Their proofs normally first prove sufficiency, e.g. 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. is equivalent to , if P is necessary and sufficient for Q, then Q is necessary and sufficient for P.
