Disjunction

Disjunction
Disjunction
	OR, OR
	; Venn diagram
Definition
Truth table
Logic gate
Normal forms
Disjunctive
Conjunctival
Polynomial Zhegalkin
Belonging to pre-class
Saves 0	Yes
Saves 1	Yes
Monotone	Yes
Lineina	No
Self-dual	No

Symbols with similar faces: V · v · Ѵ · ѵ · Ⅴ · ν

Disjunction (from Latin disjunctio - separation), logical addition , logical OR , including OR ; sometimes just OR - a logical operation , in its application as close as possible to the union “or” in the sense of “either this, or this, or both at once” ^[1] .

A disjunction can be a binary operation (having two operands), or $n$ ${\ displaystyle n}$ $n$ -ary (having $n$ ${\ displaystyle n}$ $n$ operands) for arbitrary $n$ ${\ displaystyle n}$ $n$ .

A record can be prefix - the operation sign is before operands ( Polish notation ), infix - the operation sign is between operands or postfix - the operation sign is after operands. With more than two operands, prefix and postfix entries are more economical.

Content

1 Designations
2 Boolean algebra
3 multi-valued logic
4 Classic logic
5 Circuitry
6 Set Theory
7 Programming
8 Relationship with natural language
9 notes
10 Literature

Conventions

The most common notation for disjunction surgery is:

a\lor b,\;a

{\ displaystyle a \ lor b, \; a}

a\lor b,\;a

||

b,\;a

{\ displaystyle b, \; a}

b,\;a

|

b,\;a~{\mbox{OR}}\,\,b

{\ displaystyle b, \; a ~ {\ mbox {OR}} \, \, b}

b,\;a~{\mbox{OR}}\,\,b

,\;\max(a,b).

{\ displaystyle, \; \ max (a, b).}

,\;\max(a,b).

Moreover, the designation $a\lor b$ ${\ displaystyle a \ lor b}$ $a\lor b$ recommended by the international standard ISO 31-11 , the most widely used in modern mathematics and mathematical logic ^[2] . It did not appear immediately: George Boole , who laid the foundation for the systematic application of the symbolic method to logic, did not work with disjunction (using instead of it a strict disjunction , which was denoted by + ), and William Jevons proposed the sign ·|· for the disjunction. Ernst Schroeder and P. S. Poretsky again used the + sign, but with reference to the usual disjunction ^[3] . Symbol $\lor$ ${\ displaystyle \ lor}$ $\lor$ as a designation of disjunction, first encountered in the article “Mathematical Logic Based on Type Theory” ^{[4] by} Bertrand Russell (1908); it is formed from lat. vel , which means "or" ^[5] ^[6] .

The notation ⋁ for disjunction was also used in the early programming language Algol 60 ^[7] . However, due to the lack of a corresponding character in standard character sets (for example, in ASCII or EBCDIC ) used on most computers , other notation for disjunction was provided in the most widely used programming languages. So, in Fortran IV and PL / I , the designations .OR. were used, respectively .OR. and | (with the possibility of replacing the latter with the keyword OR ) ^[8] ; in the languages of Pascal and Ada , the reserved word or ^[9] ^{[10] is used} ; in C and C ++, the notation | for bitwise disjunction and || for logical disjunction ^[11] ).

Finally, in the natural ordering of truth values of two-valued logic (when it is believed that $0<1$ ${\ displaystyle 0 <1}$ ), it turns out that $(a\lor b)\,=\,\max(a,b).$ ${\ displaystyle (a \ lor b) \, = \, \ max (a, b).}$ Thus, the disjunction is a special case of the operation of calculating the maximum ; this opens up the most natural way to determine the disjunction operation in multi - valued logic systems ^[12] ^[13] .

Boolean Algebra

The logical function MAX in two-valued (binary) logic is called a disjunction ( logical “OR” , logical addition or simply “OR” ). The result is equal to the largest operand.

In Boolean algebra, disjunction is a function of two, three or more variables (they are the operands of the operation, and they are the arguments of the function). So the result is $0$ ${\ displaystyle 0}$ if all operands are equal $0$ ${\ displaystyle 0}$ ; in all other cases, the result is $one$ ${\ displaystyle 1}$ .

Truth table
$a$ ${\ displaystyle a}$	$b$ ${\ displaystyle b}$	$a\lor b$ ${\ displaystyle a \ lor b}$
$0$ ${\ displaystyle 0}$	$0$ ${\ displaystyle 0}$	$0$ ${\ displaystyle 0}$
$0$ ${\ displaystyle 0}$	$one$ ${\ displaystyle 1}$	$one$ ${\ displaystyle 1}$
$one$ ${\ displaystyle 1}$	$0$ ${\ displaystyle 0}$	$one$ ${\ displaystyle 1}$
$one$ ${\ displaystyle 1}$	$one$ ${\ displaystyle 1}$	$one$ ${\ displaystyle 1}$

The truth table for ternary (three-operand) disjunction:

$a$ ${\ displaystyle a}$	$b$ ${\ displaystyle b}$	$c$ ${\ displaystyle c}$	$a\lor b\lor c$ ${\ displaystyle a \ lor b \ lor c}$
0	0	0	0
0	0	one	one
0	one	0	one
0	one	one	one
one	0	0	one
one	0	one	one
one	one	0	one
one	one	one	one

Multi-valued logic

An operation called a disjunction in binary logic is called a maximum in multivalued logics : $max(a,b)$ ${\ displaystyle max (a, b)}$ where $a,b\in [0,...,n-1]$ ${\ displaystyle a, b \ in [0, ..., n-1]}$ , but $n$ ${\ displaystyle n}$ - the significance of logic. Other options are possible. ^{[ what?} ^] . As a rule, they try to maintain compatibility with Boolean algebra for operand values $0,1$ ${\ displaystyle 0,1}$ .

It should be noted that the name of this operation has a maximum meaning in logics with any significance, including binary logic, and the names disjunction , logical “OR” , logical addition and simply “OR” are typical for binary logic, and when switching to multi-valued logicians are used less often.

Classical Logic

In the classical propositional calculus, disjunction properties are determined using axioms . The classical propositional calculus can be defined by different systems of axioms, and some of them will describe the properties of disjunction. One of the most common options includes 3 axioms for disjunction:

$a\to a\lor b$ ${\ displaystyle a \ to a \ lor b}$
$b\to a\lor b$ ${\ displaystyle b \ to a \ lor b}$
$(a\to c)\to ((b\to c)\to ((a\lor b)\to c))$ ${\ displaystyle (a \ to c) \ to ((b \ to c) \ to ((a \ lor b) \ to c))}$

Using these axioms, other formulas containing a disjunction operation can be proved. Note that in the classical propositional calculus, the result is not calculated by the values of the operands (as in Boolean algebra), but it is required to prove the formula as a whole based on axioms and inference rules.

Circuitry

Logic Element 2 OR

The mnemonic rule for a disjunction with any number of inputs is: Output will be:

“1” if and only if at least one input has “1”,
“0” if and only if at all inputs “0”

Set Theory

From the point of view of set theory , a disjunction is similar to a union operation.

Programming

In computer languages, two main options for disjunction are used: logical “OR” and bitwise “OR”. For example, in C / C ++ / Perl / PHP, the logical "OR" is indicated by the symbol "||", and bitwise - by the symbol "|". In Pascal / Delphi languages, both types of disjunction are indicated using the keyword “ or ”, and the result of the action is determined by the type of operands. If the operands are of a logical type (for example, Boolean), a logical operation is performed, if an integer (for example, Byte) is bitwise.

The logical "OR" is used in conditional branch operators or in similar cases when obtaining a result is required $f a l s e$ ${\ displaystyle false}$ or $t r u e$ ${\ displaystyle true}$ . For example:

  if ( a || b )
 {
     / * some actions * /
 };

The result will be equal $f a l s e$ ${\ displaystyle false}$ if both operands are equal $f a l s e$ ${\ displaystyle false}$ or $0$ ${\ displaystyle 0}$ . In any other case, the result will be equal to $t r u e$ ${\ displaystyle true}$ .

The standard convention applies: if the value of the left operand is equal to $t r u e$ ${\ displaystyle true}$ , then the value of the right operand is not calculated (instead of $b$ ${\ displaystyle b}$ can be a complex formula). Such an agreement speeds up program execution and serves as a useful technique in some cases. The Delphi compiler supports a special directive that includes

  {$ B-}

or off

  {$ B +}

similar behavior. For example, if the left operand checks to evaluate the right operand:

  if ( a == NULL || a -> x == 0 )
 {
     / * some actions * /
 };

In this example, thanks to checking in the left operand, the null pointer will never be dereferenced in the right operand.

The bitwise "OR" performs the usual operation of Boolean algebra for all bits of the left and right operand in pairs. For example,

if
a =	$01100101_{2}$ ${\ displaystyle 01100101_ {2}}$
b =	$00101001_{2}$ ${\ displaystyle 00101001_ {2}}$
then
a OR b =	$01101101_{2}$ ${\ displaystyle 01101101_ {2}}$

Natural Language Relationship

Often indicate the similarity between the disjunction and the union "or" in natural language, when it is used in the sense of "either this, or that, or both at once." In legal documents they often write: “and (or)”, sometimes “and / or”, meaning “either this, or that, or both at once”. The compound statement “A and / or B” is considered false when both statements A and B are false, otherwise the compound statement is true. This corresponds exactly to the definition of disjunction in Boolean algebra, if “truth” is denoted as $one$ ${\ displaystyle 1}$ , and “false” as $0$ ${\ displaystyle 0}$ .

The ambiguity of the natural language lies in the fact that the union “or” is used in two meanings: either to indicate a disjunction, or for another operation, a strict disjunction ( excluding “OR” ).

Notes

↑ Gutnikov V.S. Integrated Electronics in Measuring Instruments. - L .: Energy , 1974. - 144 p. - S. 14-16.
↑ Kondakov, 1975 , p. 534.
↑ Styazhkin N.I. Formation of mathematical logic. - M .: Nauka , 1967 .-- 508 p. - S. 320, 349, 352, 368.
↑ Russell B. Mathematical Logic as Based on the Theory of Types // American Journal of Mathematics . - 1908. - Vol. 30, no. 3. - P. 222-262.
↑ Earliest Uses of Symbols of Set Theory and Logic (neopr.) . // Website Jeff Miller Web Pages . Date of treatment February 5, 2016.
↑ Kondakov, 1975 , p. 149-150.
↑ Kondakov, 1975 , p. thirty.
↑ Pratt T. Programming Languages: Development and Implementation. - M .: Mir , 1979.- 574 p. - S. 352, 439.
↑ Grogono P. Programming in Pascal. - M .: Mir , 1982.- 384 p. - S. 51.
↑ Wegner P. Programming in the language of Hell. - M .: Mir , 1983 .-- 240 p. - S. 68.
↑ Ellis M. , Stroustrup B. C ++ Programming Language Reference with Comments. - M .: Mir , 1992 .-- 445 p. - ISBN 5-03-002868-4 . - S. 65, 86–87.
↑ S. Yablonsky. Introduction to discrete mathematics. - M .: Nauka , 1979.- 272 p. - S. 9-10, 37.
↑ Rvachev V. L. The theory of R- functions and some of its applications. - Kiev: Naukova Dumka , 1982. - 552 p. - S. 38, 66.

Literature

Kondakov N.I. Logical dictionary-reference book. 2nd ed . - M .: Nauka , 1975 .-- 720 p.

[1] Gutnikov V.S. Integrated Electronics in Measuring Instruments. - L .: Energy , 1974. - 144 p. - S. 14-16.

[_40cb5d7f8bb907a6-2] Kondakov, 1975 , p. 534.

[3] Styazhkin N.I. Formation of mathematical logic. - M .: Nauka , 1967 .-- 508 p. - S. 320, 349, 352, 368.

[4] Russell B. Mathematical Logic as Based on the Theory of Types // American Journal of Mathematics . - 1908. - Vol. 30, no. 3. - P. 222-262.

[5] Earliest Uses of Symbols of Set Theory and Logic (neopr.) . // Website Jeff Miller Web Pages . Date of treatment February 5, 2016.

[_7190c3b666e893de-6] Kondakov, 1975 , p. 149-150.

[_c2001532e79a92d3-7] Kondakov, 1975 , p. thirty.

[8] Pratt T. Programming Languages: Development and Implementation. - M .: Mir , 1979.- 574 p. - S. 352, 439.

[9] Grogono P. Programming in Pascal. - M .: Mir , 1982.- 384 p. - S. 51.

[10] Wegner P. Programming in the language of Hell. - M .: Mir , 1983 .-- 240 p. - S. 68.

[11] Ellis M. , Stroustrup B. C ++ Programming Language Reference with Comments. - M .: Mir , 1992 .-- 445 p. - ISBN 5-03-002868-4 . - S. 65, 86–87.

[12] S. Yablonsky. Introduction to discrete mathematics. - M .: Nauka , 1979.- 272 p. - S. 9-10, 37.

[13] Rvachev V. L. The theory of R- functions and some of its applications. - Kiev: Naukova Dumka , 1982. - 552 p. - S. 38, 66.

Disjunction
OR, OR
Venn diagram
Definition	$x+y$ ${\ displaystyle x + y}$ $x + y$
Truth table	$(0111)$ ${\ displaystyle (0111)}$ $(0111)$
Logic gate
Normal forms
Disjunctive	$x+y$ ${\ displaystyle x + y}$ $x + y$
Conjunctival	$x+y$ ${\ displaystyle x + y}$ $x + y$
Polynomial Zhegalkin	$x\oplus y\oplus xy$ ${\ displaystyle x \ oplus y \ oplus xy}$ $x \ oplus y \ oplus xy$
Belonging to pre-class
Saves 0	Yes
Saves 1	Yes
Monotone	Yes
Lineina	No
Self-dual	No

$a$ ${\ displaystyle a}$	$b$ ${\ displaystyle b}$	$c$ ${\ displaystyle c}$	$a\lor b\lor c$ ${\ displaystyle a \ lor b \ lor c}$
0	0	0	0
0	0	one	one
0	one	0	one
0	one	one	one
one	0	0	one
one	0	one	one
one	one	0	one
one	one	one	one

$a$ ${\ displaystyle a}$	$b$ ${\ displaystyle b}$	$c$ ${\ displaystyle c}$	$a\lor b\lor c$ ${\ displaystyle a \ lor b \ lor c}$
0	0	0	0
0	0	one	one
0	one	0	one
0	one	one	one
one	0	0	one
one	0	one	one
one	one	0	one
one	one	one	one