HOME

TheInfoList




In
logic Logic is an interdisciplinary field which studies truth and reasoning. Informal logic seeks to characterize Validity (logic), valid arguments informally, for instance by listing varieties of fallacies. Formal logic represents statements and ar ...

logic
, disjunction is a
logical connective In logic Logic is an interdisciplinary field which studies truth and reasoning Reason is the capacity of consciously making sense of things, applying logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, la ...
typically notated \lor whose meaning either refines or corresponds to that of natural language expressions such as "or". In
classical logic Classical logic (or standard logic) is the intensively studied and most widely used class of deductive logic Deductive reasoning, also deductive logic, is the process of reasoning from one or more statements (premises) to reach a logical conclusio ...
, it is given a
truth function In logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, label=none, lit=possessed of reason, intellectual, dialectical, argumentative, translit=logikḗ)Also related to (''logos''), "word, thought, idea, argument, ac ...
al
semantics Semantics (from grc, σημαντικός ''sēmantikós'', "significant") is the study of reference Reference is a relationship between objects in which one object designates, or acts as a means by which to connect to or link to, another o ...
on which \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 Exclusive or or exclusive disjunction is a logical operation In logic Logic is an interdisciplinary field which studies truth and reasoning Reason is the capacity of consciously making sense of things, applying logic Logic ...
. 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 In the philosophy of logic, a rule of inference, inference rule or transformation rule is a logical form consisting of a function which takes premises, ana ...
and
disjunction elimination In propositional logic Propositional calculus is a branch of logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, label=none, lit=possessed of reason, intellectual, dialectical, argumentative, translit=logikḗ)Al ...
. 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 ''contingency (philosophy), contingent:'' neither necessarily true nor necessarily false. The problem of future contingents ...
,
Heisenberg Werner Karl Heisenberg (; ; 5 December 1901 – 1 February 1976) was a German theoretical physicist and one of the key pioneers of quantum mechanics Quantum mechanics is a fundamental Scientific theory, theory in physics that provides a de ...
's
uncertainty principle In quantum mechanics Quantum mechanics is a fundamental Scientific theory, theory in physics that provides a description of the physical properties of nature at the scale of atoms and subatomic particles. It is the foundation of all quant ...

uncertainty principle
, as well the numerous mismatches between classical disjunction and its nearest equivalents in natural language.


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 The electron is a subatomic particle In physical sciences, subatomic particles are smaller than ...
, as well as \vert and \vert\!\vert in many
programming language A programming language is a formal language In logic, mathematics, computer science, and linguistics, a formal language consists of string (computer science), words whose symbol (formal), letters are taken from an alphabet (computer science) ...

programming language
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. He was born in Lemberg, a city in the Austrian Galicia, Galician Kingdom of Austria-Hungar ...

Jan Łukasiewicz
's prefix notation for logic, the operator is A, short for Polish ''alternatywa'' (English: alternative).


Classical disjunction


Semantics

Classical disjunction is a
truth function In logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, label=none, lit=possessed of reason, intellectual, dialectical, argumentative, translit=logikḗ)Also related to (''logos''), "word, thought, idea, argument, ac ...
al operation which returns the
truth value In logic Logic is an interdisciplinary field which studies truth and reasoning Reason is the capacity of consciously making sense of things, applying logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, la ...
"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 Mathematical tables are lists of numbers showing the results of a calculation with varying arguments. Tables of trigonometric functions were used in ancient Greece and India for applications to astronomy ...

truth table
:


Defined by other operators

In systems where logical disjunction is not a primitive, it may be defined as :A \lor B = \neg A \to B . This 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 Validity (logic), valid rule ...
: a \lor (b \lor c) \equiv (a \lor b) \lor c *
Commutativity In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

Commutativity
: a \lor b \equiv b \lor a *
Distributivity In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
: (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 Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), an ...
: a \lor a \equiv a *
Monotonicity Figure 3. A function that is not monotonic In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus ...
: (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 Logic is an interdisciplinary field which studies truth and reasoning Reason is the capacity of consciously making sense of things, applying logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, la ...
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 Logic is an interdisciplinary field which studies truth and reasoning Reason is the capacity of consciously making sense of things, applying logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, la ...
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 formal language In logic, mathematics, computer science, and linguistics, a formal language consists of string (computer science), words whose symbol (formal), letters are taken from an alphabet (computer science) ...

programming language
s.


Bitwise operation

Disjunction is often used for
bitwise operation In computer programming, a bitwise operation operates on a bit string, a bit array or a Binary numeral system, 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 le ...
s. 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 Image:Hash table 3 1 1 0 1 0 0 SP.svg, 315px, A data structure known as a hash table. In computer science, a data structure is a data organization, management, and storage format that enables efficient access and ...
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. 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 was a Cold War contingency plan of the Government of the United Kingdom, British Government for the continuity of government in the event of Nuclear warfare, nuclear war. Background Following the report of the Strath Committee in 1955, the ...
and
JavaScript JavaScript (), often abbreviated JS, is a programming language A programming language is a formal language In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), ma ...

JavaScript
), 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 In programming language theory and proof theory Proof may refer to: * Proof (truth), argument or sufficient evidence for the truth of a proposition * Alcohol proof, a measure of an alcoholic drink's strength Formal sciences * Formal proof, a c ...
relates a constructivist form of disjunction to
tagged unionIn computer science, a tagged union, also called a variant type, 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 fixe ...
types.


Set theory

The
membership Member may refer to: * Military juryA United States military "jury" (or "Members", in military parlance) serves a function similar to an American civilian jury, but with several notable differences. Only a Courts-martial in the United States, Gene ...
of an element of a union set in
set theory Set theory is the branch of mathematical logic that studies Set (mathematics), 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, i ...
is defined in terms of a logical disjunction: x\in A\cup B if and only if (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 Validity (logic), valid rule ...
,
commutativity In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

commutativity
,
distributivity In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
, and
de Morgan's laws In propositional calculus, propositional logic and Boolean algebra, De Morgan's laws are a pair of transformation rules that are both Validity (logic), valid rule of inference, rules of inference. They are named after Augustus De Morgan, a 19th ...
, identifying
logical conjunction In logic Logic is an interdisciplinary field which studies truth and reasoning Reason is the capacity of consciously making sense of things, applying logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, ...
with
set intersection In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...

set intersection
,
logical negation In logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, label=none, lit=possessed of reason, intellectual, dialectical, argumentative, translit=logikḗ)Also related to (''logos''), "word, thought, idea, argume ...
with
set complement In , the complement of a , often denoted by (or ), are the not in . When all sets under consideration are considered to be s of a given set , the absolute complement of is the set of elements in that are not in . The relative complement of ...
.


Natural language

The classical denotation for \lor does not precisely match the
denotation The denotation of a word is its central sense A sense is a biological system used by an organism for sensation, the process of gathering information about the world and responding to Stimulus (physiology), stimuli. (For example, in the human bod ...
of disjunctive statements in
natural language In neuropsychology Neuropsychology is a branch of psychology. It is concerned with how a person's cognition and behavior are related to the brain and the rest of the nervous system. Professionals in this branch of psychology often focus on ...
s such as
English English usually refers to: * English language English is a West Germanic languages, West Germanic language first spoken in History of Anglo-Saxon England, early medieval England, which has eventually become the World language, leading lan ...

English
. Notably, classical disjunction is inclusive while natural language disjunction is often understood exclusively. :1. Mary is patriotic or quixotic. ::\rightsquigarrow Mary is not both patriotic and quixotic. This inference has sometimes been understood as an
entailment Logical consequence (also entailment) is a fundamental concept Concepts are defined as abstract ideas A mental representation (or cognitive representation), in philosophy of mind Philosophy of mind is a branch of philosophy that studies th ...
, for instance by
Alfred Tarski Alfred Tarski (; January 14, 1901 – October 26, 1983), born Alfred Teitelbaum,School of Mathematics and Statistics, University of St Andrews ''School of Mathematics and Statistics, University of St Andrews''. was a Polish-American logician ...
, who suggested that natural language disjunction is
ambiguous Ambiguity is a type of meaning in which a phrase, statement or resolution is not explicitly defined, making several interpretations plausible. A common aspect of ambiguity is uncertainty Uncertainty refers to Epistemology, epistemic sit ...
between a classical and a nonclassical interpretation. More recent work in
pragmatics In linguistics Linguistics is the scientific study of language, meaning that it is a comprehensive, systematic, objective, and precise study of language. Linguistics encompasses the analysis of every aspect of language, as well as the m ...
has shown that this inference can be derived as a
conversational implicature 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 saying everything we want to communicate. This phenom ...
on the basis of a
semantic Semantics (from grc, σημαντικός ''sēmantikós'', "significant") is the study of reference Reference is a relationship between objects in which one object designates, or acts as a means by which to connect to or link to, another ...
denotation which behaves classically. However, disjunctive constructions including
HungarianHungarian may refer to: * Hungary, a country in Central Europe * Kingdom of Hungary, state of Hungary, existing between 1000 and 1946 * Hungarians, ethnic groups in Hungary * Hungarian algorithm, a polynomial time algorithm for solving the assignmen ...
''vagy... vagy'' and ''soit... soit'' have been argued to be inherently exclusive, rendering un
grammaticality In linguistics Linguistics is the science, scientific study of language. It encompasses the analysis of every aspect of language, as well as the methods for studying and modeling them. The traditional areas of linguistic analysis include ...
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, where certain modal operators trigger a
conjunction Conjunction may refer to: * Conjunction (astronomy), in which two astronomical bodies appear close together in the sky * Conjunction (astrology), astrological aspect in horoscopic astrology * Conjunction (grammar), a part of speech * Logical conjun ...
-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 A geographical pole or geographic pole is either of the two points on Earth where its axis of rotation intersects its surface. The North Pole lies in the Arctic Ocean ...
asking whether it's true that Mary is either a philosopher or a linguist, it can also be interpreted as an
alternative question ''AlterNative: An International Journal of Indigenous Peoples'' (formerly ''AlterNative: An International Journal of Indigenous Scholarship'') is a quarterly peer-reviewed academic journal An academic or scholarly journal is a periodical publica ...
asking which of the two professions is hers. The role of disjunction in these cases has be analyzed using nonclassical logics such as
alternative semanticsAlternative semantics (or Hamblin semantics) is a framework in formal semantics and logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, label=none, lit=possessed of reason, intellectual, dialectical, argumentative, t ...
and
inquisitive semantics Inquisitive semantics is a framework in logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, label=none, lit=possessed of reason, intellectual, dialectical, argumentative, translit=logikḗ)Also related to (''logos' ...
, 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 (list of glossing abbreviations, abbreviated or ) is a part of speech that connects words, phrases, or clauses that are called the conjuncts of the conjunctions. This definition may overlap with that of other parts of s ...
. 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 noun A noun (from Latin ''nōmen'', literally ''name'') is a word that functions as the ...
. 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 * Maricopa ...
, disjunction is marked using a verb
suffix In linguistics Linguistics is the scientific study of language A language is a structured system of communication used by humans, including speech (spoken language), gestures (Signed language, sign language) and writing. Most languag ...
. 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 logic, deductive argument takes the following logical form: :A or B :A :Therefore, not B ...

Affirming a disjunct
*
Bitwise OR In computer programming Computer programming is the process of designing and building an executable computer program to accomplish a specific computing result or to perform a specific task. Programming involves tasks such as: analysis, gener ...
*
Boolean algebra (logic) In mathematics and mathematical logic, Boolean algebra is the branch of algebra in which the values of the variable (mathematics), variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, respectively. Instead of elementary a ...
* Boolean algebra topics *
Boolean domain In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...
*
Boolean function In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ge ...
*
Boolean-valued function A Boolean-valued function (sometimes called a predicate or a proposition In linguistics and logic, a proposition is the meaning of a declarative sentence. In philosophy, "Meaning (philosophy), meaning" is understood to be a non-linguistic enti ...
*
Disjunctive syllogism In classical logicClassical logic (or standard logic) is the intensively studied and most widely used class of deductive logic. Classical logic has had much influence on analytic philosophy, the type of philosophy most often found in the English-s ...
*
Disjunction elimination In propositional logic Propositional calculus is a branch of logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, label=none, lit=possessed of reason, intellectual, dialectical, argumentative, translit=logikḗ)Al ...
*
Disjunction introduction Disjunction introduction or addition (also called or introduction) is a rule of inference In the philosophy of logic, a rule of inference, inference rule or transformation rule is a logical form consisting of a function which takes premises, ana ...
*
First-order logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal system A formal system is an used for inferring theorems from axioms according to a set of rules. These rul ...
*
Fréchet inequalitiesIn probabilistic logicThe aim of a probabilistic logic (also probability logic and probabilistic reasoning) is to combine the capacity of probability theory to handle uncertainty with the capacity of deductive logic to exploit structure of formal pr ...
*
Free choice inferenceFree choice is a phenomenon in natural language where a disjunction In logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, label=none, lit=possessed of reason, intellectual, dialectical, argumentative, translit=lo ...
* Hurford disjunction * Logical graph *
Logical value In logic Logic is an interdisciplinary field which studies truth and reasoning Reason is the capacity of consciously making sense of things, applying logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, la ...
* Operation *
Operator (programming) In computer programming Computer programming is the process of designing and building an executable computer program to accomplish a specific computing result or to perform a particular task. Programming involves tasks such as analysis, ge ...
*
OR gate The OR gate is a digital logic gate that implements logical disjunctionit behaves according to the truth table to the right. A HIGH output (1) results if one or both the inputs to the gate are HIGH (1). If neither input is high, a LOW output ( ...

OR gate
*
Propositional calculus Propositional calculus is a branch of logic Logic is an interdisciplinary field which studies truth and reasoning. Informal logic seeks to characterize Validity (logic), valid arguments informally, for instance by listing varieties of fal ...
* Simplification of disjunctive antecedents


Notes

*
George Boole George Boole (; 2 November 1815 – 8 December 1864) was a largely self-taught Autodidacticism (also autodidactism) or self-education (also self-learning and self-teaching) is education Education is the process of facil ...

George Boole
, closely following analogy with ordinary mathematics, premised, as a necessary condition to the definition of "x + y", that x and y were mutually exclusive. , 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 \lor whose meaning either refines or corresponds to that of natural language expressions such as "or". In classical logic, it is given a truth functional semantics of logic, sema ...
Semantics Formal semantics (natural language)