Disjunction

First published Sat Jan 6, 2001; substantive revision Wed Oct 1, 2008

Disjunction is a binary truth-function, the output of which is a sentence true if at least one of the input sentences (disjuncts) is true, and false otherwise. Disjunction, together with negation, provide sufficient means to define all other truth-functions. Its supposed connection with the or words of natural language has intrigued and mystified philosophers for many centuries, and the subject has inspired much creative myth-making, particularly since the advent of truth-tables early in the twentieth century. In this article some of those myths are set out and dispelled.

1. Introduction

A disjunction is a kind of compound sentence historically associated by English-speaking logicians and their students with indicative sentences compounded with eitheror, such as

Either I am very rich or someone is playing a cruel joke.

But nowadays the term disjunction is more often used in reference to sentences (or well-formed formulae) of associated form occurring in formal languages. Logicians distinguish between

(a) the abstracted form of such sentences and the roles that sentences of that form play in arguments and proofs,

(b) the meanings that must be assigned to such sentences to account for those roles.

The former represents their syntactic and proof-theoretic interests, the latter their semantic or truth-theoretic interest in disjunction. Introductory logic texts are sometimes a little unclear as to which should provide the defining characteristics of disjunction. Nor are they clear as to whether disjunctions are primarily features of natural or of formal languages. Here we consider formal languages first.

2. Syntax

The definition of a formal system, either axiomatic or natural deductive, requires the definition of a language, and here the formal vocabulary of disjunction makes its first appearance. If the disjunctive constant ∨ (historically suggestive of Latin vel (or)) is a primitive constant of the language, there will be a clause, here labeled [∨] in the inductive definition of the set of well-formed formulae (wffs). Using α and β as metalogical variables, ranging over wffs, such a clause would read:

[∨] If α is a wff and β is a wff, then α ∨ β is a wff

perhaps accompanied by an instruction that α ∨ β is to be referred to as the disjunction of the wffs α and β, and read as "[name of first wff] vel (or ‘vee’, or ‘or’) [name of second wff]". Thus, on this instruction, the wff pq is the disjunction of p and q, and is pronounced as ‘pea vel queue’ or ‘pea vee queue’ or ‘pea or queue’. In this case, p and q are the disjuncts of the disjunction.

If ∨ is a non-primitive constant of the language, then typically it will be introduced by an abbreviative definition. In presentations of classical systems in which the conditional constant → or ⊃ and the negational constant ¬ are taken as primitive, the disjunctive constant ∨ might be introduced in the abbreviation of a wff ¬α → β (or ¬α ⊃ β) as α ∨ β. Alternatively, if the conjunctive & has already been introduced either as a primitive or as a defined constant, ∨ might be introduced in the abbreviation of a wff ¬(¬α & ¬β) as α ∨ β.

3. Proof Theory

Much as we would understand the conversational significance of vocabulary more generally if we had a complete set of instructions for initiating its use in a conversation, and for suitable responses to its introduction by an interlocutor, we give the proof-theoretic significance of a connective by providing rules for its introduction into a proof and for its elimination. In the case of ∨, these might be the following:

[∨-introduction] For any wffs α and β, a proof having a subproof of α from an ensemble Σ of wffs, can be extended to a proof of α ∨ β from Σ.

[∨-elimination] For any wffs α, β, γ, a proof that includes

  • a subproof of α ∨ β from an ensemble of wffs Σ,
  • a subproof of γ from an ensemble Δ ∪ {α}, and
  • a subproof of γ from an ensemble Θ ∪ {β},

can be extended to a proof of γ from Σ ∪ Δ ∪ Θ.

Intuitively, the former would correspond to a rule of conversation that permitted us to assert A or B (for any B) given the assertion that A. Thus if we are told that Nicholas is in Paris, we can infer that Nicholas is either in Paris or in Toulouse.

Intuitively, the latter rule would correspond to a rule that, given the assertion that A or B, would permit the assertion of anything that is permitted both by the assertion of A and by the assertion of B. For example, given the assertion on certain grounds that Nicholas is in Paris or Toulouse, we are warranted in asserting on the same grounds plus some geographical information, that Nicholas is in France, since that assertion is warranted (a) by the assertion that Nicholas is in Paris together with some of the geographical information and (b) by the assertion that Nicholas is in Toulouse together with the rest of the geographical information. More generally we may sum the matter up by saying that the rule corresponds to the conversational rule that lets us extract information from an or-sentence without the information of either of its clauses. In the example, we are given the information that Nicholas is in Paris or Toulouse, but we are given neither the information that Nicholas is in Paris nor the information that he is in Toulouse.

4. Semantics

In its simplest, classical, semantic analysis, a disjunction is understood by reference to the conditions under which it is true, and under which it is false. Central to the definition is a valuation, a function that assigns to every atomic, or unanalysable sentence of the language a value in the set {1, 0}. In general the inductive truth-definition for a language corresponds, clause by clause to the definition of its well-formed formulae. Thus for a propositional language it will take as its basis, a clause according to which an atom is true or false accordingly as the valuation maps it to 1 or to 0. In systems in which ∨ is a primitive constant, the clause corresponding to disjunction takes α ∨ β to be true if at least one of α, β is true, and takes it to be false otherwise. Where ∨ is introduced by either of the definitions earlier mentioned, that truth-condition can be computed for α ∨ β from those of the conditional (→ or ⊃) or conjunction (&) and negation (¬).

Now the truth-definition can be regarded as an extension of the valuation from the atoms of the language to the entire set of wffs with 1 understood as the truth-value, true, and 0 understood as the truth-value, false. Thus, classically, disjunction is semantically interpreted as a binary truth-function from the set of pairs of truth-values to the set {0, 1}. The tabulated graph of this function, as dictated by the truth-definition, is called the truth-table for disjunction. That table is the following:

α β α ∨ β
1 1
1 0
0 1
0 0
1
1
1
0

5. Inclusive and Exclusive disjunctions

Authors of introductory logic texts generally take this opportunity to distinguish the disjunction we have been discussing from another binary truth-function whose graph is tabulated by the table:

α β α β
1 1
1 0
0 1
0 0
0
1
1
0

where α β is read α xor β. This truth-function is referred to variously as exclusive disjunction, as 0110 disjunction (after the succession of values in its main column), and as logical difference. The wff α β is true when exactly one of α, β is true; false otherwise. To make matters explicit, the earlier discussed truth-function ∨ is called inclusive, or non-exclusive or 1110 disjunction.

6. Natural Language

It is an assumption, at any rate a claim, of many textbook authors that there are both uses of or in English that correspond to 1110 disjunction and uses that correspond to 0110 disjunction, and this supposition generally motivates the introduction and discussion of the xor connective. Since we are following the usual order of textbook exposition, this is perhaps the moment to make a few observations on this score. The first are purely syntactic. The or of English that such authors cite is a coordinator (or coordinating conjunction). It can coordinate syntactic elements of virtually any grammatical type, not merely whole sentences. Moreover, if we consider only its uses joining whole sentences, we must notice that it can join sentences of virtually any mood: interrogative sentences and imperatives as well as indicative sentences can be joined by or in English. And again, if we restrict our attention to its uses joining indicative sentences, we must note that or is by no means restricted to the binary cases in this role. Indeed, there is no theoretical finite limit to the number of clauses that it can join. This is perhaps the most fundamental relevant syntactic difference between or on the one hand and ∨ and on the other. The sentence

Nathalie has been and gone or Nathalie will arrive today or Nathalie will not arrive at all

is a perfectly correct sentence and not ambiguous as between

(Nathalie has been and gone or Nathalie will arrive today) or Nathalie will not arrive at all

and

Nathalie has been and gone or (Nathalie will arrive today or Nathalie will not arrive at all).

By contrast, the wff pqr, far from being ambiguous as between (pq) ∨ r and p ∨ (qr), is, on the inductive definition of well-formedness, not a wff. If the parenthesis-free notation is tolerated in general logical exposition, this is because ∨ is associative, that is, the wffs (pq) ∨ r and p ∨ (qr) are syntactically interderivable, and semantically have identical truth-conditions. The formal account of disjunction could readily be liberalized to accommodate that fact, and even conveniently in languages in which ∨ was primitive. In that case our inductive definition of the language could permit any such string as ∨(α1, … , αi, … , αn) to be well-formed if α1, … , αi, … and αn are. The relevant clause of the truth-definition would accordingly be modified in such a way as to give ∨(α1, … , αi, … , αn) the maximum of the truth-values of α1, … , αi, … and αn. Moreover, this accords well with such cases as the one cited in which or joins more than two simple clauses: such a sentence is true if at least one of its clauses is true; false otherwise.

The fact that English or is not binary does not accord so well with the claim made by many textbook authors that there are uses of or that require representation by 0110 disjunction. To be sure, is associative, so that a notational liberalization would be possible, parallel to the one described for ∨. But, as Hans Reichenbach seems first to have pointed out (in Reichenbach [1947]), the truth-definition for 1, … , αi, … , αn) would have to be such as to give it the value 1 if any odd number of α1, … , αi, … , αn have the value 1; the value 0 otherwise. The result is evident from the truth-table where n > 2. For n = 3, suppose that α β γ has the value 1. The truth-definition as given by the table requires that exactly one of α β, γ has the value 1. Let γ have the value 1; then α β has the value 0. Then α and β have the same value. That is, either both α and β have the value 0, or both α and β have the value 1. In the former case exactly one of α, β, γ has the value 1; in the latter, all three have the value 1. That is, the disjunction will take the value 1 if and only if an odd number of disjuncts have the value 1. A simple induction will prove that this result holds for an exclusive disjunction of any finite length. It is sufficient for present purposes to note that, in the case where n = 3, 1, α2, α3) will be true if all of its disjuncts are true. Now there is no naturally occurring coordinator in any natural language matching the truth-conditional profile of such a connective. There is certainly no use of or in English in accordance with which five sentences A, B, C, D, and E can be joined to form a sentence A or B or C or D or E, which is true if and only if either exactly one of the component sentences is true, or exactly three of them are true or exactly five of them are true.

Most of the texts make no claims about exclusive disjunctive uses of either English or Latin or-words beyond the two-disjunct case. But it is a fair presumption that the belief in exclusive disjunctive uses of or in English includes just such three-disjunct uses of or. Such a use of or, would be one in accordance with which three sentences A, B, and C can be joined to form a sentence A or B or C, which is true if and only if exactly one of the component sentences is true. Though not a 0110-disjunctive use of or, this would be a general use representable as 0110 disjunction in the two-disjunct case.[1]

The question as to whether there is such a use of or in English, or any other natural language goes to the very heart of the conception of truth conditional semantics. For it seems certain that there are conversational uses of or that invite the inference of exclusivity, but which do not seem to require exclusivity for their truth. Thus, for example, if one says (as in Tarski [1941], 21) ‘We are going on a hike or we are going to a theater’, even with charged emphasis upon the or, one will have spoken falsely if in the event we do both, unless, as in Tarski's example, one has also denied the conjunction.

Some authors have sought examples of 0110 disjunction in or-sentences whose clauses are mutually exclusive. For example, Kegley and Kegley discuss the case (Kegley and Kegley [1978], 232):

John is at the play, or he is studying in the library

of which the authors remark, "There is no mistaking the sense of or here: John cannot be in both places at once". If their example were an example of exclusive disjunction, we could safely infer from it that the play is not being performed in the library, that the theatre is not in the library, that John is not swotting in the stalls between acts while his companion fights her way to the bar to fetch the drinks. In fact, even, perhaps particularly, when the disjuncts are genuinely mutually exclusive, there are no grounds for the supposition that the or represents 0110 disjunction. Were there such grounds the ∨ of formal logic would require distinct semantic accounts for the wffs pq and p ∨ ¬p. As Barrett and Stenner point out (Barrett and Stenner [1971]), the case requires quite the reverse. Since the truth-tables of ∨ and differ exactly in the output value of the first row, what alone would clinch the case for the existence of an exclusive or would be a sentence in which both disjuncts were true, and the disjunction therefore false. No author has yet produced such an example.

7. The Myth of Vel and Aut

If the logic texts dictate the structure and content of our discussion, it is perhaps as well to dispel another current myth — namely that the notational choice of ∨, (read as vel) as the connective of inclusive disjunction, and the claim that the English or has 0110-disjunctive uses are supported by the facts of the Latin language. I. Copi is as explicit as any (Copi [1971], 241):

The Latin word "vel" expresses weak or inclusive disjunction, and the Latin word "aut" corresponds to the word "or" in its strong or exclusive sense.

The idea is, first, that whereas English has only one or-word, Latin has two: vel and aut, and secondly, that the uses of vel in Latin would be representable as 1110 disjunction and the uses of aut as 0110 disjunction. As to the first, the very shape of the claim is likely to mislead. The case is not that Latin had two words for or, but rather that Latin had more than one word that gets translated into English as or. In fact, Latin had many words that are translated into English as or, including, besides the two listed, at least seu, sive and the enclitic ve. So does English have many words that can be translated into English as or, including unless, if … not, but (It does not rain but it pours) and so on. All vocabulary has a history, and languages accumulate vocabulary that becomes adapted to nuanced uses.

Now the supposition that Latin had a 0110 coordinator must suffer from the same implausibilities as the corresponding supposition about English. What of the two-disjunct case? If any general tendency can be detected in actual Latin usage, say in the classical period, that would distinguish the uses of vel from those of aut, it is that aut tended to be brought into use in the formation of lists of disjoint or contrasted or opposed items, categories or classes or states, as for example

Omne enuntiatum aut verum aut falsum est [Every statement is either true or false] (Cicero, De Fato, 222).

The difficulty with these examples is that the exclusiveness of the states independendently of the choice of connective must mask any disjointness that the connective could itself impose. That it does not impose any disjointness itself is best seen in its list-forming uses. Consider the list (Cicero, De Officiis):

tribunos aut plebes [the magistrates or the mob, (accusative plural)]

to be sure the categories are disjoint, and this fact might be supposed to contribute to the selection of aut. But the mutual exclusion in such cases need not survive the addition of a verb.

Timebat tribunos aut plebes [one feared the magistrates or the mob]

does not exclude the case in which one feared both. However, what clinches the refutation of this mythical supposition is that if that whole clause is brought within the scope of a negator, the resulting sentence will expect a reading along the lines of 1110 disjunction.

Nemo timebat tribunos aut plebes [No one feared the magistrates or the mob]

just means no one feared either. It does not mean everyone either feared neither or feared both. Since the negation of a 0110 disjunction is a 1110 disjunction (either both disjuncts are true or both disjuncts are false), this use of aut cannot be a 0110 disjunctive use.

In fact, in classical Latin, aut was favoured over vel in constructions involving negations, and in that use, aut behaves analogously to ∨. But pretty well anywhere an aut could be used, a vel could be substituted, and vice versa. The resulting sentence would have a different flavour, and in some instances would be mildly eccentric, but would not have a different truth condition. The uses of vel reflected its origins as an imperative form of volo. The flavour of

Nemo timebat vel tribunos vel plebes

would be closer to that of

Name which group (of the two) you will: no one feared them.
Aut was adversative: no one feared either social extremity. (For more examples and a more detailed discussion, see Jennings [1994], 239–251.)

8. The Or of Natural Language

There are undoubtedly disjunctive uses of or in English, and of corresponding vocabulary in other natural languages. But the uses of or after the pattern of the logic texts:

Either Argentina will boycott the conference or the value of lead will diminish

and so on constitute only a very small proportion, certainly fewer than 5% of the occurrences of or in English, and, it can be supposed, of corresponding words in all other natural languages as well. It is therefore not surprising that it should be some of these non-disjunctive uses that have been misidentified as instances of exclusive disjunction. The example cited (in Richards [1978], 84) is a good representative example of one such common misidentification:

So how can we find a clear-cut case of the exclusive ‘or’? Imagine a boy who asks for ice cream and strawberries for tea. He is told as a sort of refusal:
‘You can have ice cream or strawberries for tea’.

Here there is no doubt: not both may be had.

Once again there is a difficulty in trying to account for the exclusivity by reference to truth-conditions, though, if we are permitted to consult the intentions of the speaker (as Richards himself does) we may be in no doubt as to the prohibition of strawberries and icecream, however curious such a prohibition might seem. But this example, in company with the many others like it (which this author has sometimes referred to collectively as the argument from confection) suffers from the even more serious flaw that it is not a disjunction at all. The problem is not that the or does not join whole clauses. Even if we expand the example to

’You can have ice cream for tea or you can have strawberries for tea’,

the sentence cannot be construed as a disjunction. The reason is that the child would be correct in inferring that he can have ice cream for tea, and would be correct in inferring that he can have strawberries for tea. Such sentences are elliptical for conjunctions, not for disjunctions, even on a truth-conditional construal. It just happens that for such conjunctions, questions of exclusivity, or rather non-combinativity also arise.

Not every or of English (nor every counterpart of or in other languages) is disjunctive, even among those that join pairs of indicative sentences.

Bibliography

  • Barrett, Robert B., and Stenner, Alfred J., 1971, "The Myth of the Exclusive ‘Or’", Mind, 80(317): 116–121.
  • Cicero, Marcus Tullius, De Fato, Translated by H. Rackham. Cambridge, Mass 1942.
  • Cicero, Marcus Tullius, De Officiis, Translated by Walter Miller. Cambridge, Mass 1975.
  • Copi, I.M., 1971, Introduction to Logic, New York: Macmillan.
  • Jennings, R.E., 1994, The Genealogy of Disjunction, New York: Oxford University Press.
  • Kegley, Charles W., 1978, and Kegley, Jacquelyn Ann, Introduction to Logic, Lanham, MD: University Press.
  • McCawley, J., 1993, Everything that Linguists Have Always Wanted to Know About Logic, 2nd edition, Chicago: University of Chicago Press.
  • Pelletier, F.J. and Hartline, A.J., 2008, "Ternary exclusive or", Logic Journal of the IGPL, 16(1): 75–83.
  • Pelletier, F.J. and Martin, N., 1990, "Proving Post's functional completeness theorem", Notre Dame Journal of Formal Logic, 31: 462–475.
  • Post, E., 1941, The Two-Valued Iterative Systems of Mathematical Logic, Princeton: Princeton University Press.
  • Reichenbach, Hans, 1947, Elements of Symbolic Logic, New York: MacMillan.
  • Richards, T.A., 1978, The Language of Reason, Rushcutters Bay, NSW.
  • Alfred Tarski, 1941, Introduction to Logic and to the Methodology of the Deductive Sciences, New York: Oxford University Press, second edition, revised, translated by Olaf Helmer, 1963.

Other Internet Resources

[Please contact the author with suggestions.]

Copyright © 2008 by
Ray Jennings
Andrew Hartline

Open access to the SEP is made possible by a world-wide funding initiative.
Please Read How You Can Help Keep the Encyclopedia Free