In logic, the law of the excluded middle states that the propositional calculus formula "P ∨ ¬P" ("P or not-P") can be deduced from the calculus under investigation. It is one of the defining properties of classical systems of logic. However, some systems of logic have different but analogous laws, while others reject the law of excluded middle entirely.
The law is also known as the law (or principle) of the excluded third, or, in Latin, principium tertii exclusi. Yet another Latin designation for this law is Tertium non datur: "there is no third (possibility)".
The law of excluded middle is related to the principle of bivalence, which is a semantic principle instead of a law that can be deduced from the calculus.
For some finite n-valued logics, there is an analogous law called the law of excluded n+1th. If negation is cyclic and '∨' is a "max operator", then the law can be expressed in the object language by (P ∨ ~P ∨ ~~P ∨ ... ∨ ~...~P), where '~...~' represents n-1 negation signs and '∨ ... ∨' n-1 disjunction signs. It is easy to check that the sentence must receive at least one of the n truth values (and not a value that is not one of the n).
For example, if P is the proposition:
then the law of excluded middle holds that the logical disjunction:
is true by virtue of its form alone. That is, the "middle" position, that Socrates is neither mortal nor immortal, is excluded by logic, and therefore either the first possibility (Socrates is mortal) or its negation (Socrates is not mortal) must be true.
An example of an argument that depends on the law of excluded middle follows. We seek to prove that there exist two irrational numbers and such that
It is known that is irrational. Consider the number
Clearly (excluded middle) this number is either rational or irrational. If it is rational, we are done: and . If it is irrational, then let
and 2 is certainly rational. This concludes the proof.
In the above argument, the assertion "this number is either rational or irrational" invokes the law of excluded middle. An intuitionist, for example, would not accept this argument without further support for that statement. This might come in the form of a proof that the number in question is in fact irrational (or rational, as the case may be); or a finitistic algorithm that could determine whether the number is rational or not.
By non-constructive Davis means that "a proof that there actually are mathematic entities satisfying certain conditions would have to provide a method to exhibit explicitly the entities in question." (p. 85). Such proofs presume the existence of a totality that is complete, a notion disallowed by intuitionists when extended to the infinite -- for them the infinite can never be completed:
Indeed, Hilbert and Brouwer both give examples of the law of excluded middle extended to the infinite. Hilbert's example: "the assertion that either there are only finitely many prime numbers or there are infinitely many" (quoted in Davis 2000:97); and Brouwer's: "Every mathematical species is either finite or infinite." (Brouwer 1923 in van Heijenoort 1967:336).
In general, intuitionists allow the use of the law of excluded middle when it is confined to discourse over finite collections (sets), but not when it is used in discourse over infinite sets (e.g. the natural numbers). Thus intuitionists absolutely disallow the blanket assertion: "For all propositions P concerning infinite sets D: P or ~P" (Kleene 1952:48).
Putative counterexamples to the law of excluded middle include the liar paradox or Quine's Paradox. Certain resolutions of these paradoxes, particularly Graham Priest's dialetheism as formalised in LP, have the law of excluded middle as a theorem, but resolve out the Liar as both true and false. In this way, the law of excluded middle is true, but because truth itself, and therefore disjunction, is not exclusive, it says next to nothing if one of the disjuncts is paradoxical, or both true and false.
One more counterexample to LEM may be noted: Gödel's First Incompleteness Theorem  provides a constructive example of a contingent proposition, which is neither deductively (syntactically) true nor false. An intuitionist would point out that the negation of the "G-sentence" has only infinite (non-standard) models, and is thus another demonstration of the unsoundness of LEM with respect to infinite domains.
It is impossible, then, that 'being a man' should mean precisely 'not being a man', if 'man' not only signifies something about one subject but also has one significance. … And it will not be possible to be and not to be the same thing, except in virtue of an ambiguity, just as if one whom we call 'man', and others were to call 'not-man'; but the point in question is not this, whether the same thing can at the same time be and not be a man in name, but whether it can be in fact. (Metaphysics 4.4, W.D. Ross (trans.), GBWW 8, 525–526).
Aristotle's assertion that "...it will not be possible to be and not to be the same thing", which would be written in propositional logic as ¬ (P ∧ ¬P), is not the statement a modern logician would call the law of excluded middle (P ∨ ¬P). The former claims that no statement is both true and false; the latter requires that no statement is neither true nor false.
However, Aristotle also writes, "since it is impossible that contradictories should be at the same time true of the same thing, obviously contraries also cannot belong at the same time to the same thing" (Book IV, CH 6, p. 531). He then proposes that "there cannot be an intermediate between contradictories, but of one subject we must either affirm or deny any one predicate" (Book IV, CH 7, p. 531). In the context of Aristotle's traditional logic, this is a remarkably precise statement of the law of excluded middle, P ∨ ¬P.
Its usual form, "Every judgment is either true or false" [footnote 9]..."(from Kolmogorov in van Heijenoort, p. 421) footnote 9: "This is Leibniz's very simple formulation (see Nouveaux Essais, IV,2)...." (ibid p 421)
- Law of identity: 'Whatever is, is.'
- Law of noncontradiction: 'Nothing can both be and not be.'
- Law of excluded middle: 'Everything must either be or not be.'
These three laws are samples of self-evident logical principles... (p. 72)
It is correct, at least for bivalent logic — i.e. it can be seen with a Karnaugh map — that Russell's Law (2) removes "the middle" of the inclusive-or used in his law (3). And this is the point of Reichenbach's demonstration that some believe the exclusive-or should take the place of the inclusive-or.
About this issue (in admittedly very technical terms) Reichenbach observes:
The tertium non datur
is not exhaustive in its major terms and is therefore an inflated formula. This fact may perhaps explain why some people consider it unreasonable to write (29) with the inclusive-'or', and want to have it written with the sign of the exclusive-'or'
- (x)[f(x) ∨ ~f(x)]
in which form it would be fully exhaustive and therefore nomological in the narrower sense. (Reichenbach, p. 376)
- (x)[f(x) ⊕ ~f(x)], where the symbol " ⊕ " signifies exclusive-or
In line (30) the "(x)" means "for all" or "for every", thus an example of the expression would look like this:
What Aristotle and Russell believed is characteristic of traditional logic, but this view implicitly depends on a particular notion of truth in which every statement is either true or false.
Principia Mathematica (PM) defines the law of excluded middle formally:
Example: Either it is true that “this is red”, or it is true that “this is not red”. Hence it is true that “this is red or this is not red”. (See below for more about how this is derived from the primitive axioms).
- *2.1 : ~p ∨ p (PM p. 101)
So just what is "truth" and "falsehood"? At the opening PM quickly announces some definitions:
Truth-values. The “truth-values” of a proposition is truth if it is true and falsehood if it is false* [*This phrase is due to Frege]...the truth-value of “p ∨ q” is truth if the truth-value of either p or q is truth, and is falsehood otherwise ... that of “~ p” is the opposite of that of p...” (p. 7-8)
This is not much help. But later, in a much deeper discussion, ("Definition and systematic ambiguity of Truth and Falsehood" Chapter II part III, p. 41 ff ) PM defines truth and falsehood in terms of a relationship between the "a" and the "b" and the "percipient". For example "This 'a' is 'b'" (e.g. "This 'object a' is 'red'") really means "'object a' is a sense-datum" and "'red' is a sense-datum", and they "stand in relation" to one another and in relation to "I". Thus what we really mean is: "I perceive that 'This object a is red'" and this is an undeniable-by-3rd-party "truth".
PM further defines a distinction between a "sense-datum" and a "sensation":
That is, when we judge (say) “this is red”, what occurs is a relation of three terms, the mind, and “this”, and “red“. On the other hand, when we perceive “the redness of this”, there is a relation of two terms, namely the mind and the complex object “the redness of this” (p. 43-44).
Russell reiterated his distinction between "sense-datum" and "sensation" in his book The Problems of Philosophy (1912) published at the same time as PM (1910 – 1913):
Let us give the name of ‘sense-data’ to the things that are immediately known in sensation: such things as colours, sounds, smells, hardnesses, roughnesses, and so on. We shall give the name ‘sensation’ to the experience of being immediately aware of these things… The colour itself is a sense-datum, not a sensation. (p. 12)
Russell further described his reasoning behind his definitions of "truth" and "falsehood" in the same book (Chapter XII Truth and Falsehood).
From the law of the excluded middle, formula *2.1 in Principia Mathematica, Whitehead and Russell derive some of the most powerful tools in the logician's argumentation toolkit.
The proof of *2.1 is roughly as follows: “primitive idea” *1.08 defines p → q = ~p ∨ q. Substituting p for q in this rule yields p → p = ~p ∨ p. Since p → p is true (this is Theorem 2.08, which is proved separately), then ~p ∨ p must be true.
Most of these theorems--in particular *2.1, *2.11, and *2.14--are rejected by intuitionism. These tools are recast into another form that Kolmogorov cites as "Hilbert's four axioms of implication" and "Hilbert's two axioms of negation" (Kolmogorov in van Heijenoort, p. 335).
Propositions *2.12 and *2.14, "double negation": The intuitionist writings of L. E. J. Brouwer refer to what he calls "the principle of the reciprocity of the multiple species, that is, the principle that for every system the correctness of a property follows from the impossibility of the impossibility of this property" (Brouwer, ibid, p. 335).
This principle is commonly called "the principle of double negation" (cf PM p. 101-102). From the law of excluded middle *2.1 and *2.11 PM derives principle *2.12 immediately. We substitute ~p for p in *2.11 to yield ~p ∨ ~(~p), and by the definition of implication (i.e. *1.01 p → q = ~p ∨ q) then ~p ∨ ~(~p)= p → ~(~p). QED (The derivation of 2.14 is a bit more involved.)