HOME

TheInfoList



OR:

In
logic Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...
, disjunction is a
logical connective In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary ...
typically notated as \lor and read aloud as "or". For instance, the
English English usually refers to: * English language * English people English may also refer to: Peoples, culture, and language * ''English'', an adjective for something of, from, or related to England ** English national ide ...
language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor S , assuming that R abbreviates "it is raining" and S abbreviates "it is snowing". In classical logic, disjunction is given a
truth function 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 o ...
al semantics according to which a formula \phi \lor \psi is true unless both \phi and \psi are false. Because this semantics allows a disjunctive formula to be true when both of its disjuncts are true, it is an ''inclusive'' interpretation of disjunction, in contrast with exclusive disjunction. Classical proof theoretical treatments are often given in terms of rules such as
disjunction introduction Disjunction introduction or addition (also called or introduction) is a rule of inference of propositional logic and almost every other deduction system. The rule makes it possible to introduce disjunctions to logical proofs. It is the infer ...
and
disjunction elimination In propositional logic, disjunction elimination (sometimes named proof by cases, case analysis, or or elimination), is the valid argument form and rule of inference that allows one to eliminate a disjunctive statement from a logical proof. It ...
. Disjunction has also been given numerous non-classical treatments, motivated by problems including
Aristotle's sea battle argument Future contingent propositions (or simply, future contingents) are statements about states of affairs in the future that are '' contingent:'' neither necessarily true nor necessarily false. The problem of future contingents seems to have been fi ...
,
Heisenberg Werner Karl Heisenberg () (5 December 1901 – 1 February 1976) was a German theoretical physicist and one of the main pioneers of the theory of quantum mechanics. He published his work in 1925 in a breakthrough paper. In the subsequent series ...
's
uncertainty principle In quantum mechanics, the uncertainty principle (also known as Heisenberg's uncertainty principle) is any of a variety of mathematical inequalities asserting a fundamental limit to the accuracy with which the values for certain pairs of physic ...
, as well the numerous mismatches between classical disjunction and its nearest equivalents in
natural language In neuropsychology, linguistics, and philosophy of language, a natural language or ordinary language is any language that has evolved naturally in humans through use and repetition without conscious planning or premeditation. Natural languages ...
s.


Inclusive and exclusive disjunction

Because the logical "or" means a formula is when either or both are true, it is referred to as an ''inclusive'' disjunction. This is in contrast with an exclusive disjunction, which is true when one or the other of the arguments are true, but not both (referred to as "''exclusive or''", or "XOR"). When it is necessary to clarify whether inclusive or exclusive "or" is intended, English speakers sometimes uses the phrase " and/or". In terms of logic, this phrase is identical to "or", but makes the inclusion of both being true explicit.


Notation

In logic and related fields, disjunction is customarily notated with an infix operator \lor. Alternative notations include +, used mainly in
electronics The field of electronics is a branch of physics and electrical engineering that deals with the emission, behaviour and effects of electrons using electronic devices. Electronics uses active devices to control electron flow by amplification ...
, as well as \vert and \vert\!\vert in many
programming language A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language. The description of a programming ...
s. The English word "or" is sometimes used as well, often in capital letters. In
Jan Łukasiewicz Jan Łukasiewicz (; 21 December 1878 – 13 February 1956) was a Polish logician and philosopher who is best known for Polish notation and Łukasiewicz logic His work centred on philosophical logic, mathematical logic and history of logic. ...
's prefix notation for logic, the operator is A, short for Polish ''alternatywa'' (English: alternative).


Classical disjunction


Semantics

In the
semantics of logic In logic, the semantics of logic or formal semantics is the study of the semantics, or interpretations, of formal and (idealizations of) natural languages usually trying to capture the pre-theoretic notion of entailment. Overview The truth cond ...
, classical disjunction is a
truth function 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 o ...
al
operation Operation or Operations may refer to: Arts, entertainment and media * ''Operation'' (game), a battery-operated board game that challenges dexterity * Operation (music), a term used in musical set theory * ''Operations'' (magazine), Multi-Ma ...
which returns the
truth value In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth, which in classical logic has only two possible values (''true'' or '' false''). Computing In some progr ...
"true" unless both of its arguments are "false". Its semantic entry is standardly given as follows: :: \models \phi \lor \psi     if     \models \phi     or     \models \psi     or     both This semantics corresponds to the following
truth table A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional argumen ...
:


Defined by other operators

In classical logic systems where logical disjunction is not a primitive, it can be defined in terms of the primitive "
and or AND may refer to: Logic, grammar, and computing * Conjunction (grammar), connecting two words, phrases, or clauses * Logical conjunction in mathematical logic, notated as "∧", "⋅", "&", or simple juxtaposition * Bitwise AND, a boolea ...
" (\land) and " not" (\lnot) as: :A \lor B = \neg ((\neg A) \land (\neg B)) . Alternatively, it may be defined in terms of " implies" (\to) and "not" as: :A \lor B = (\lnot A) \to B . The latter can be checked by the following truth table:


Properties

The following properties apply to disjunction: *
Associativity In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement ...
: a \lor (b \lor c) \equiv (a \lor b) \lor c * Commutativity: a \lor b \equiv b \lor a *
Distributivity In mathematics, the distributive property of binary operations generalizes the distributive law, which asserts that the equality x \cdot (y + z) = x \cdot y + x \cdot z is always true in elementary algebra. For example, in elementary arithmeti ...
: (a \land (b \lor c)) \equiv ((a \land b) \lor (a \land c)) :::(a \lor (b \land c)) \equiv ((a \lor b) \land (a \lor c)) :::(a \lor (b \lor c)) \equiv ((a \lor b) \lor (a \lor c)) :::(a \lor (b \equiv c)) \equiv ((a \lor b) \equiv (a \lor c)) *
Idempotency Idempotence (, ) is the property of certain operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence arises in a number of pl ...
: a \lor a \equiv a *
Monotonicity In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of orde ...
: (a \rightarrow b) \rightarrow ((c \lor a) \rightarrow (c \lor b)) :::(a \rightarrow b) \rightarrow ((a \lor c) \rightarrow (b \lor c)) *Truth-preserving: The interpretation under which all variables are assigned a
truth value In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth, which in classical logic has only two possible values (''true'' or '' false''). Computing In some progr ...
of 'true', produces a truth value of 'true' as a result of disjunction. *Falsehood-preserving: The interpretation under which all variables are assigned a
truth value In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth, which in classical logic has only two possible values (''true'' or '' false''). Computing In some progr ...
of 'false', produces a truth value of 'false' as a result of disjunction.


Applications in computer science

Operators Operator may refer to: Mathematics * A symbol indicating a mathematical operation * Logical operator or logical connective in mathematical logic * Operator (mathematics), mapping that acts on elements of a space to produce elements of another sp ...
corresponding to logical disjunction exist in most
programming language A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language. The description of a programming ...
s.


Bitwise operation

Disjunction is often used for bitwise operations. Examples: * 0 or 0 = 0 * 0 or 1 = 1 * 1 or 0 = 1 * 1 or 1 = 1 * 1010 or 1100 = 1110 The or operator can be used to set bits in a
bit field A bit field is a data structure that consists of one or more adjacent bits which have been allocated for specific purposes, so that any single bit or group of bits within the structure can be set or inspected. A bit field is most commonly used to ...
to 1, by or-ing the field with a constant field with the relevant bits set to 1. For example, x = x , 0b00000001 will force the final bit to 1, while leaving other bits unchanged.


Logical operation

Many languages distinguish between bitwise and logical disjunction by providing two distinct operators; in languages following C, bitwise disjunction is performed with the single pipe operator (, ), and logical disjunction with the double pipe (, , ) operator. Logical disjunction is usually short-circuited; that is, if the first (left) operand evaluates to true, then the second (right) operand is not evaluated. The logical disjunction operator thus usually constitutes a
sequence point A sequence point defines any point in a computer program's execution at which it is guaranteed that all side effects of previous evaluations will have been performed, and no side effects from subsequent evaluations have yet been performed. They are ...
. In a parallel (concurrent) language, it is possible to short-circuit both sides: they are evaluated in parallel, and if one terminates with value true, the other is interrupted. This operator is thus called the parallel or. Although the type of a logical disjunction expression is boolean in most languages (and thus can only have the value true or false), in some languages (such as
Python Python may refer to: Snakes * Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia ** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia * Python (mythology), a mythical serpent Computing * Python (pro ...
and
JavaScript JavaScript (), often abbreviated as JS, is a programming language that is one of the core technologies of the World Wide Web, alongside HTML and CSS. As of 2022, 98% of websites use JavaScript on the client side for webpage behavior, of ...
), the logical disjunction operator returns one of its operands: the first operand if it evaluates to a true value, and the second operand otherwise.


Constructive disjunction

The Curry–Howard correspondence relates a constructivist form of disjunction to
tagged union In computer science, a tagged union, also called a variant, variant record, choice type, discriminated union, disjoint union, sum type or coproduct, is a data structure used to hold a value that could take on several different, but fixed, types. O ...
types.


Set theory

The
membership Member may refer to: * Military jury, referred to as "Members" in military jargon * Element (mathematics), an object that belongs to a mathematical set * In object-oriented programming, a member of a class ** Field (computer science), entries in ...
of an element of a union set in
set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly conce ...
is defined in terms of a logical disjunction: x\in A\cup B\Leftrightarrow (x\in A)\vee(x\in B). Because of this, logical disjunction satisfies many of the same identities as set-theoretic union, such as
associativity In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement ...
, commutativity,
distributivity In mathematics, the distributive property of binary operations generalizes the distributive law, which asserts that the equality x \cdot (y + z) = x \cdot y + x \cdot z is always true in elementary algebra. For example, in elementary arithmeti ...
, and
de Morgan's laws In propositional logic and Boolean algebra, De Morgan's laws, also known as De Morgan's theorem, are a pair of transformation rules that are both valid rules of inference. They are named after Augustus De Morgan, a 19th-century British math ...
, identifying
logical conjunction In logic, mathematics and linguistics, And (\wedge) is the truth-functional operator of logical conjunction; the ''and'' of a set of operands is true if and only if ''all'' of its operands are true. The logical connective that represents this ...
with
set intersection In set theory, the intersection of two sets A and B, denoted by A \cap B, is the set containing all elements of A that also belong to B or equivalently, all elements of B that also belong to A. Notation and terminology Intersection is writt ...
, logical negation with
set complement In set theory, the complement of a set , often denoted by (or ), is the set of elements not in . When all sets in the universe, i.e. all sets under consideration, are considered to be members of a given set , the absolute complement of is th ...
.


Natural language

Disjunction in
natural language In neuropsychology, linguistics, and philosophy of language, a natural language or ordinary language is any language that has evolved naturally in humans through use and repetition without conscious planning or premeditation. Natural languages ...
s does not precisely match the interpretation of \lor in classical logic. Notably, classical disjunction is inclusive while natural language disjunction is often understood exclusively, as the following
English English usually refers to: * English language * English people English may also refer to: Peoples, culture, and language * ''English'', an adjective for something of, from, or related to England ** English national ide ...
typically would be. :1. Mary is eating an apple or a pear. This inference has sometimes been understood as an
entailment Logical consequence (also entailment) is a fundamental concept in logic, which describes the relationship between statements that hold true when one statement logically ''follows from'' one or more statements. A valid logical argument is one ...
, for instance by
Alfred Tarski Alfred Tarski (, born Alfred Teitelbaum;School of Mathematics and Statistics, University of St Andrews ''School of Mathematics and Statistics, University of St Andrews''. January 14, 1901 – October 26, 1983) was a Polish-American logician a ...
, who suggested that natural language disjunction is ambiguous between a classical and a nonclassical interpretation. More recent work in
pragmatics In linguistics and related fields, pragmatics is the study of how context contributes to meaning. The field of study evaluates how human language is utilized in social interactions, as well as the relationship between the interpreter and the in ...
has shown that this inference can be derived as a
conversational implicature In pragmatics, a subdiscipline of linguistics, an implicature is something the speaker suggests or implies with an utterance, even though it is not literally expressed. Implicatures can aid in communicating more efficiently than by explicitly sayi ...
on the basis of a semantic denotation which behaves classically. However, disjunctive constructions including Hungarian ''vagy... vagy'' and French ''soit... soit'' have been argued to be inherently exclusive, rendering un grammaticality in contexts where an inclusive reading would otherwise be forced. Similar deviations from classical logic have been noted in cases such as free choice disjunction and
simplification of disjunctive antecedents In formal semantics and philosophical logic, simplification of disjunctive antecedents (SDA) is the phenomenon whereby a disjunction in the antecedent of a conditional appears to distribute over the conditional as a whole. This inference is show ...
, where certain modal operators trigger a
conjunction Conjunction may refer to: * Conjunction (grammar), a part of speech * Logical conjunction, a mathematical operator ** Conjunction introduction, a rule of inference of propositional logic * Conjunction (astronomy), in which two astronomical bodies ...
-like interpretation of disjunction. As with exclusivity, these inferences have been analyzed both as implicatures and as entailments arising from a nonclassical interpretation of disjunction. :2. You can have an apple or a pear. ::\rightsquigarrow You can have an apple and you can have a pear (but you can't have both) In many languages, disjunctive expressions play a role in question formation. For instance, while the following English example can be interpreted as a
polar question Polar may refer to: Geography Polar may refer to: * Geographical pole, either of two fixed points on the surface of a rotating body or planet, at 90 degrees from the equator, based on the axis around which a body rotates *Polar climate, the cli ...
asking whether it's true that Mary is either a philosopher or a linguist, it can also be interpreted as an
alternative question A question is an utterance which serves as a request for information. Questions are sometimes distinguished from interrogatives, which are the grammatical forms typically used to express them. Rhetorical questions, for instance, are interrogative ...
asking which of the two professions is hers. The role of disjunction in these cases has been analyzed using nonclassical logics such as
alternative semantics Alternative semantics (or Hamblin semantics) is a framework in formal semantics and logic. In alternative semantics, expressions denote ''alternative sets'', understood as sets of objects of the same semantic type. For instance, while the word "Le ...
and
inquisitive semantics Inquisitive semantics is a framework in logic and natural language semantics. In inquisitive semantics, the semantic content of a sentence captures both the information that the sentence conveys and the issue that it raises. The framework provides ...
, which have also been adopted to explain the free choice and simplification inferences. :3. Is Mary a philosopher or a linguist? In English, as in many other languages, disjunction is expressed by a
coordinating conjunction In grammar, a conjunction (abbreviated or ) is a part of speech that connects words, phrases, or clauses that are called the conjuncts of the conjunctions. That definition may overlap with that of other parts of speech and so what constitutes a ...
. Other languages express disjunctive meanings in a variety of ways, though it is unknown whether disjunction itself is a
linguistic universal A linguistic universal is a pattern that occurs systematically across natural languages, potentially true for all of them. For example, ''All languages have nouns and verbs'', or ''If a language is spoken, it has consonants and vowels.'' Research ...
. In many languages such as Dyirbal and
Maricopa Maricopa can refer to: Places * Maricopa, Arizona, United States, a city ** Maricopa Freeway, a piece of I-10 in Metropolitan Phoenix ** Maricopa station, an Amtrak station in Maricopa, Arizona * Maricopa County, Arizona, United States * Marico ...
, disjunction is marked using a verb suffix. For instance, in the Maricopa example below, disjunction is marked by the suffix ''šaa''.


See also

*
Affirming a disjunct The formal fallacy of affirming a disjunct also known as the fallacy of the alternative disjunct or a false exclusionary disjunct occurs when a deductive argument takes the following logical form: :A or B :A :Therefore, not B Or in logical op ...
*
Bitwise OR In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operati ...
* Boolean algebra (logic) *
Boolean algebra topics This is a list of topics around Boolean algebra and propositional logic. Articles with a wide scope and introductions * Algebra of sets Talk:Algebra of sets, * Boolean algebra (structure) Talk:Boolean algebra (structure), * Boolean algebra ...
*
Boolean domain In mathematics and abstract algebra, a Boolean domain is a set consisting of exactly two elements whose interpretations include ''false'' and ''true''. In logic, mathematics and theoretical computer science, a Boolean domain is usually written as ...
*
Boolean function In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth function ...
*
Boolean-valued function A Boolean-valued function (sometimes called a predicate or a proposition) is a function of the type f : X → B, where X is an arbitrary set and where B is a Boolean domain, i.e. a generic two-element set, (for example B = ), whose elements are i ...
*
Disjunctive syllogism In classical logic, disjunctive syllogism (historically known as ''modus tollendo ponens'' (MTP), Latin for "mode that affirms by denying") is a valid argument form which is a syllogism having a disjunctive statement for one of its premise ...
*
Disjunction elimination In propositional logic, disjunction elimination (sometimes named proof by cases, case analysis, or or elimination), is the valid argument form and rule of inference that allows one to eliminate a disjunctive statement from a logical proof. It ...
*
Disjunction introduction Disjunction introduction or addition (also called or introduction) is a rule of inference of propositional logic and almost every other deduction system. The rule makes it possible to introduce disjunctions to logical proofs. It is the infer ...
*
First-order logic 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 quantifie ...
*
Fréchet inequalities In probabilistic logic, the Fréchet inequalities, also known as the Boole–Fréchet inequalities, are rules implicit in the work of George BooleBoole, G. (1854). ''An Investigation of the Laws of Thought, On Which Are Founded the Mathematical Theo ...
*
Free choice inference Free choice is a phenomenon in natural language where a linguistic disjunction appears to receive a logical conjunctive interpretation when it interacts with a modal operator. For example, the following English sentences can be interpreted to mean ...
*
Hurford disjunction In formal semantics, a Hurford disjunction is a disjunction in which one of the disjuncts entails the other. The concept was first identified by British linguist James Hurford. The sentence "Mary is in the Netherlands or she is in Amsterdam" is a ...
*
Logical graph A logical graph is a special type of diagrammatic structure in any one of several systems of graphical syntax that Charles Sanders Peirce developed for logic. In his papers on '' qualitative logic'', '' entitative graphs'', and '' existential grap ...
*
Logical value In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth, which in classical logic has only two possible values (''true'' or '' false''). Computing In some progra ...
*
Operation Operation or Operations may refer to: Arts, entertainment and media * ''Operation'' (game), a battery-operated board game that challenges dexterity * Operation (music), a term used in musical set theory * ''Operations'' (magazine), Multi-Ma ...
*
Operator (programming) In computer programming, operators are constructs defined within programming languages which behave generally like functions, but which differ syntactically or semantically. Common simple examples include arithmetic (e.g. addition with ), c ...
*
OR gate The OR gate is a digital logic gate that implements logical disjunction. The OR gate returns true if either or both of its inputs are true; otherwise it returns false. The input and output states are normally represented by different voltage le ...
*
Propositional calculus Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations ...
*
Simplification of disjunctive antecedents In formal semantics and philosophical logic, simplification of disjunctive antecedents (SDA) is the phenomenon whereby a disjunction in the antecedent of a conditional appears to distribute over the conditional as a whole. This inference is show ...


Notes

*
George Boole George Boole (; 2 November 1815 – 8 December 1864) was a largely self-taught English mathematician, philosopher, and logician, most of whose short career was spent as the first professor of mathematics at Queen's College, Cork in ...
, closely following analogy with ordinary mathematics, premised, as a necessary condition to the definition of "x + y", that x and y were mutually exclusive. Jevons, and practically all mathematical logicians after him, advocated, on various grounds, the definition of "logical addition" in a form which does not necessitate mutual exclusiveness.


References


External links

* * *Eric W. Weisstein
"Disjunction."
From MathWorld—A Wolfram Web Resource {{Authority control
Disjunction In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor S ...
Semantics Formal semantics (natural language)