In logic and mathematics, necessity and sufficiency are terms used to describe a conditional or implicational relationship between two statements. For example, in the conditional statement: "If P then Q", Q is necessary for P, because the truth of Q is guaranteed by the truth of P. (Equivalently, it is impossible to have P without Q, or the falsity of Q ensures the falsity of P.) [1] Similarly, P is sufficient for Q, because P being true always implies that Q is true, but P not being true does not always imply that Q is not true. [2]
In general, a necessary condition is one (possibly one of multiple conditions) that must be present in order for another condition to occur, while a sufficient condition is one that produces the said condition. [3] 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. [4] [5] [6]
In ordinary English (also natural language) "necessary" and "sufficient" indicate relations between conditions or states of affairs, not statements. For example, being a male is a necessary condition for being a brother, but it is not sufficient—while being a male 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, [7] where necessary condition analysis and qualitative comparative analysis can be used as analytical techniques for examining necessity and sufficiency of conditions for 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". [8]
In 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 Nmust 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 Socrates, it is necessary for that someone to be Named. Similarly, in order for human beings to live, it is necessary that they have air. [9]
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 the truth of N". [9] For example, carrying on from the previous example, one can say that knowing that someone is called Socrates is sufficient to know that someone has a Name.
A necessary and sufficient condition requires that both of the implications and (the latter of which can also be written as ) hold. The first implication suggests that S 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 | |||
---|---|---|---|---|
T | T | T | T | T |
T | F | F | T | F |
F | T | T | F | F |
F | F | T | T | T |
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". [9] [1] 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 a sufficient condition (i.e., individually necessary and jointly sufficient [9] ), 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 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 is rational (S) is sufficient but not necessary to 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, 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 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 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. [10] This contrasts with the probabilistic theory of concepts which states that no defining feature is necessary or sufficient, rather that categories resemble 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 , whereas cases tell us that is identical to .
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 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 [11] might characterize this state of affairs thus: "Although the concepts of bipartiteness and absence of odd cycles differ in intension, they have identical extension. [12]
In mathematics, theorems are often stated in 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. is equivalent to , if P is necessary and sufficient for Q, then Q is necessary and sufficient for P. We can write 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.
In propositional logic, affirming the consequent, sometimes called converse error, fallacy of the converse, or confusion of necessity and sufficiency, is a formal fallacy of taking a true conditional statement under certain assumptions, and invalidly inferring its converse, even though that statement may not be true under the same assumptions. This arises when the consequent has other possible antecedents.
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over non-logical objects, and allows the use of sentences that contain variables, so that rather than propositions such as "Socrates is a man", one can have expressions in the form "there exists x such that x is Socrates and x is a man", where "there exists" is a quantifier, while x is a variable. This distinguishes it from propositional logic, which does not use quantifiers or relations; in this sense, propositional logic is the foundation of first-order logic.
In logic and related fields such as mathematics and philosophy, "if and only if" 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, and can be likened to the standard material conditional combined with its reverse ("if"); hence the name. The result is that the truth of either one of the connected statements requires the truth of the other, 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 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 logic, a logical connective is a logical constant. Connectives can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary connective can be used to join the two atomic formulas and , rendering the complex formula .
In propositional logic, modus ponens, also known as modus ponendo ponens, implication elimination, or affirming the antecedent, is a deductive argument form and rule of inference. It can be summarized as "P implies Q.P is true. Therefore, Q must also be true."
In mathematics and logic, a vacuous truth is a conditional or universal statement that is true because the antecedent cannot be satisfied. It is sometimes said that a statement is vacuously true because it does not really say anything. For example, the statement "all cell phones in the room are turned off" will be true when no cell phones are present in the room. In this case, the statement "all cell phones in the room are turned on" would also be vacuously true, as would the conjunction of the two: "all cell phones in the room are turned on and turned off", which would otherwise be incoherent and false.
In mathematics, the distributive property of binary operations is a generalization of the distributive law, which asserts that the equality
In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such as Russell's paradox. Today, Zermelo–Fraenkel set theory, with the historically controversial axiom of choice (AC) included, is the standard form of axiomatic set theory and as such is the most common foundation of mathematics. Zermelo–Fraenkel set theory with the axiom of choice included is abbreviated ZFC, where C stands for "choice", and ZF refers to the axioms of Zermelo–Fraenkel set theory with the axiom of choice excluded.
In logic, negation, also called the logical not or logical complement, is an operation that takes a proposition to another proposition "not ", standing for " is not true", written , or . It is interpreted intuitively as being true when is false, and false when is true. Negation is thus a unary logical connective. It may be applied as an operation on notions, propositions, truth values, or semantic values more generally. In classical logic, negation is normally identified with the truth function that takes truth to falsity. In intuitionistic logic, according to the Brouwer–Heyting–Kolmogorov interpretation, the negation of a proposition is the proposition whose proofs are the refutations of .
In logic and mathematics, the logical biconditional, also known as material biconditional or equivalence or biimplication or bientailment, is the logical connective used to conjoin two statements and to form the statement " if and only if ", where is known as the antecedent, and the consequent.
In mathematics, constructive analysis is mathematical analysis done according to some principles of constructive mathematics.
In logic, a truth function is a function that accepts truth values as input and produces a unique truth value as output. In other words: the input and output of a truth function are all truth values; a truth function will always output exactly one truth value, and inputting the same truth value(s) will always output the same truth value. The typical example is in propositional logic, wherein a compound statement is constructed using individual statements connected by logical connectives; if the truth value of the compound statement is entirely determined by the truth value(s) of the constituent statement(s), the compound statement is called a truth function, and any logical connectives used are said to be truth functional.
Predicate transformer semantics were introduced by Edsger Dijkstra in his seminal paper "Guarded commands, nondeterminacy and formal derivation of programs". They define the semantics of an imperative programming paradigm by assigning to each statement in this language a corresponding predicate transformer: a total function between two predicates on the state space of the statement. In this sense, predicate transformer semantics are a kind of denotational semantics. Actually, in guarded commands, Dijkstra uses only one kind of predicate transformer: the well-known weakest preconditions.
The situation calculus is a logic formalism designed for representing and reasoning about dynamical domains. It was first introduced by John McCarthy in 1963. The main version of the situational calculus that is presented in this article is based on that introduced by Ray Reiter in 1991. It is followed by sections about McCarthy's 1986 version and a logic programming formulation.
In mathematical optimization, the Karush–Kuhn–Tucker (KKT) conditions, also known as the Kuhn–Tucker conditions, are first derivative tests for a solution in nonlinear programming to be optimal, provided that some regularity conditions are satisfied.
In propositional logic, transposition is a valid rule of replacement that permits one to switch the antecedent with the consequent of a conditional statement in a logical proof if they are also both negated. It is the inference from the truth of "A implies B" to the truth of "Not-B implies not-A", and conversely. It is very closely related to the rule of inference modus tollens. It is the rule that
In logic, a functionally complete set of logical connectives or Boolean operators is one that can be used to express all possible truth tables by combining members of the set into a Boolean expression. A well-known complete set of connectives is { AND, NOT }. Each of the singleton sets { NAND } and { NOR } is functionally complete. However, the set { AND, OR } is incomplete, due to its inability to express NOT.
In mathematics, a set is inhabited if there exists an element .
In logic, conditioned disjunction is a ternary logical connective introduced by Church. Given operands p, q, and r, which represent truth-valued propositions, the meaning of the conditioned disjunction [p, q, r] is given by:
In logic and mathematics, contraposition 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 a statement has its antecedent and consequent inverted and flipped.