Addition modulo 2

Addition modulo 2
Addition modulo 2
	Exclusive OR, XOR
	; Venn diagram
Truth table
Logic gate
Normal forms
Disjunctive
Conjunctival
Polina Zhegalkina
Belonging to pre-complete classes
Saves 0	Yes
Saves 1	Not
Monotone	Not
Linane	Yes
Self-dual	Not

Modulo 2 ( excluding “or” , XOR , strict disjunction , bitwise addition , mask inverting , Zhegalkin addition , logical subtraction , logical inequality ) - Boolean function , as well as logical and bitwise operation , in the case of two variables, the result of the operation is true if and only if one of the arguments is true and the second is false. For a function of three (ternary addition modulo 2) and more variables, the result of the operation will be true only when the number of arguments equal to 1 that make up the current set is odd. Such an operation occurs naturally in the residue ring modulo 2 , whence the name of the operation occurs.

Schedule bit exclusive "or"

Addition modulo 2 is called "exclusive" or "" and "strict disjunction" to distinguish it from the "ordinary" (non-exclusive) logical "or" - a non-severe logical disjunction . In set theory, addition modulo 2 corresponds to the operation of the symmetric difference of two sets.

Legend

The record can be prefix (“ Polish record ”) - the operation sign is placed before the operands, the infix sign - the operation sign is placed between the operands and the postfix one - the operation sign is placed after the operands. With more than 2 operands, the prefix and postfix entries are more economical than the infix entries. The most common recording options are:
$\oplus _{2}(a,b),~a$ ${\ displaystyle \ oplus _ {2} (a, b), ~ a}$ $\oplus _{2}(a,b),~a$ ^ $b,~a\oplus b,a\oplus _{2}b,a+_{2}b,$ ${\ displaystyle b, ~ a \ oplus b, a \ oplus _ {2} b, a + _ {2} b,}$ $b,~a\oplus b,a\oplus _{2}b,a+_{2}b,$ a ≠ b, $a\neq b,(a,b)\oplus _{2},a~XOR~b$ ${\ displaystyle a \ neq b, (a, b) \ oplus _ {2}, a ~ XOR ~ b}$ $a\neq b,(a,b)\oplus _{2},a~XOR~b$

Unicode has characters for modulo 2 addition: XOR - U + 22BB (⊻), CIRCLED PLUS - U + 2295 (⊕) and PLUS SIGN WITH SUCSCRIPT TWO - U + 2A27 (⨧), as well as the symbol for the modulo 2 sum : MODULO TWO SUM - U + 2A0A (⨊).

Properties

$a\oplus 0=a$ ${\ displaystyle a \ oplus 0 = a}$ $a\oplus 0=a$ ( idempotency )
$a\oplus 1={\bar {a}}$ ${\ displaystyle a \ oplus 1 = {\ bar {a}}}$ $a\oplus 1={\bar a}$ ( denial )
$a\oplus a=0$ ${\ displaystyle a \ oplus a = 0}$ $a\oplus a=0$ ( self-reversibility )
$a\oplus b=b\oplus a$ ${\ displaystyle a \ oplus b = b \ oplus a}$ ( commutativity )
$(a\oplus b)\oplus c=a\oplus (b\oplus c)$ ${\ displaystyle (a \ oplus b) \ oplus c = a \ oplus (b \ oplus c)}$ ( associativity )
$(a\oplus b)\oplus b=a$ ${\ displaystyle (a \ oplus b) \ oplus b = a}$ ( )
${\bar {a}}\oplus b=a\oplus {\bar {b}}=(a\equiv b)$ ${\ displaystyle {\ bar {a}} \ oplus b = a \ oplus {\ bar {b}} = (a \ equiv b)}$ ( comparisons by module )

Boolean algebra

In Boolean algebra, addition modulo 2 is a function of two, three, or more variables (they are also the operands of the operation, and they are the arguments of the function). Variables can take values from a set $\{0,1\}$ ${\ displaystyle \ {0,1 \}}$ . The result also belongs to the set $\{0,1\}$ ${\ displaystyle \ {0,1 \}}$ . The result is calculated by a simple rule or by a truth table . Instead of values $0,1$ ${\ displaystyle 0,1}$ any other suitable pair of characters can be used, for example $f a l s e, t r u e$ ${\ displaystyle false, true}$ or $F, T$ ${\ displaystyle F, T}$ or “false”, “true”, but it is necessary to define seniority, for example, $true>false$ ${\ displaystyle true> false}$ .

Truth tables:

for binary modulo 2 addition (used in binary half-adders ):

$a$ ${\ displaystyle a}$	$b$ ${\ displaystyle b}$	$a\oplus b$ ${\ displaystyle a \ oplus b}$
0	0	0
one	0	one
0	one	one
one	one	0

Rule: result is $0$ ${\ displaystyle 0}$ if both operands are equal; in all other cases, the result is $one$ ${\ displaystyle 1}$ .

for ternary addition modulo 2 (used in full binary adders ):

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

Rule: result is $0$ ${\ displaystyle 0}$ if there are no operands equal to $one$ ${\ displaystyle 1}$ or their even number.

Programming

In C / C ++ , Java , C # , Ruby , PHP , JavaScript , Python, and so on. Bitwise complement bit operation is denoted by the symbol “ ^ ”; in Pascal , Delphi , Ada , Visual Basic languages , the reserved word xor ; in Assembly language - logical command of the same name. In this case, addition modulo 2 is performed for all bits of the left and right operand in pairs. For example,

if a

$a=01100101_{2}$ ${\ displaystyle a = 01100101_ {2}}$

$b=00101001_{2}$ ${\ displaystyle b = 00101001_ {2}}$

that

$a{\hat {\ }}b=01001100_{2}$ ${\ displaystyle a {\ hat {\}} b = 01001100_ {2}}$

The exclusive or operation for logical type values (true, false) is performed in different programming languages in different programming languages. For example, Delphi uses the built-in XOR operator (example: condition1 xor condition2 ). In the C language, starting with the C99 standard , the “ ^ ” operator on the operands of the logical type returns the result of applying the logical XOR operation. In C ++, the “ ^ ” operator for the boolean boolean type returns the result according to the described rules, while for the other types, its bitwise application is performed.

Using the bitwise exclusive "or" allows you to swap the values of integer variables without using additional memory .

Natural language relationship

In natural language, the operation “addition modulo” is equivalent to two expressions:

“The result is true (equal to 1) if A is not equal to B (A ≠ B)”;
" If A is not equal to B (A ≠ B), then true (1)".

Often indicate the similarity between the addition of modulo 2 and the construction of "either ... or ..." in natural language. The compound statement “either A or B” is considered true when either A or B is true, but not both at once; otherwise, the compound statement is false. This exactly corresponds to the definition of an operation in Boolean algebra, if “truth” is denoted as $one$ ${\ displaystyle 1}$ , and "lie" as $0$ ${\ displaystyle 0}$ .

This operation is often compared with a disjunction because they are very similar in properties, and both have similarities with the “or” union in everyday speech. Compare the rules for these operations:

$A\lor B$ ${\ displaystyle A \ lor B}$ true if true $A$ ${\ displaystyle A}$ or $B$ ${\ displaystyle B}$ , or both at once (" at least one of the two").
$A\oplus B$ ${\ displaystyle A \ oplus B}$ true if true $A$ ${\ displaystyle A}$ or $B$ ${\ displaystyle B}$ , but not both at once (“ only one of the two”).

Operation $\oplus$ ${\ displaystyle \ oplus}$ excludes the last option (“both at once”) and for this reason is called exclusive “OR”. Operation $\lor$ ${\ displaystyle \ lor}$ includes the last option (“both at once”) and for this reason is sometimes called including “OR”. The ambiguity of natural language is that the conjunction "or" can be used in both cases.

Quantum Computing

In quantum computers, the analogue of the modulo 2 addition operation is the CNOT valve .

Links

Logic Algebra and Digital Computers: Addition function modulo 2 (xor)

Addition modulo 2
Exclusive OR, XOR
Venn diagram
Truth table	$(0110)$ ${\ displaystyle (0110)}$ $(0110)$
Logic gate
Normal forms
Disjunctive	${\overline {x}}\cdot y+x\cdot {\overline {y}}$ ${\ displaystyle {\ overline {x}} \ cdot y + x \ cdot {\ overline {y}}}$ $\ overline {x} \ cdot y + x \ cdot \ overline {y}$
Conjunctival	$({\overline {x}}+{\overline {y}})\cdot (x+y)$ ${\ displaystyle ({\ overline {x}} + {\ overline {y}}) \ cdot (x + y)}$ $(\ overline {x} + \ overline {y}) \ cdot (x + y)$
Polina Zhegalkina	$x\oplus y$ ${\ displaystyle x \ oplus y}$ $x \ oplus y$
Belonging to pre-complete classes
Saves 0	Yes
Saves 1	Not
Monotone	Not
Linane	Yes
Self-dual	Not

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

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