Exklusivt "eller"

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 1 april 2022; kontroller kräver 2 redigeringar .

Exklusivt "eller"
Modulo 2 tillägg, XOR
Venn diagram
sanningstabell	$(0110)$
logisk port
normala former
Disjunktiv	$\overline {x}\cdot y+x\cdot \overline {y}$
konjunktival	$(\överlinje {x}+\överlinje {y})\cdot (x+y)$
Zhegalkin polynom	$x\plus y$
Medlemskap i förfullbordade klasser
Sparar 0	Ja
Sparar 1	Inte
Monoton	Inte
linjär	Ja
Självdubbel	Inte

Exklusivt "eller" ( modulo 2 addition , XOR , strikt disjunktion , bitvis addition , maskinversion , Zhegalkin addition , logisk subtraktion , logisk disparitet ) är en boolesk funktion , såväl som en logisk och bitoperation , i fallet med två variabler, resultatet av operationen är sant om och endast om ett av argumenten är sant och det andra är falskt. För en funktion av tre (ternär addition modulo 2) eller fler variabler, kommer resultatet av operationen att vara sant endast när antalet argument lika med 1 som utgör den aktuella mängden är udda. En sådan operation uppstår naturligt i ringen av rester modulo 2 , därav namnet på operationen.

Modulo 2-tillägg kallas "exklusiv eller" och "strikt disjunktion" för att skilja det från "vanlig" (icke-exklusiv) logisk "eller" - icke-strikt logisk disjunktion . I mängdteorin motsvarar additionsmodulo 2 funktionen för den symmetriska skillnaden mellan två uppsättningar.

Notation

Inspelning kan vara prefix (" polsk post ") - operationstecknet placeras före operanderna, infix - operationstecknet placeras mellan operanderna och postfixet - operationstecknet placeras efter operanderna. När antalet operander är fler än två är prefix- och postfix-notation mer ekonomiska än infix-notation. Den vanligaste notationen är: ^ a ≠ b,
$\oplus _{2}(a,b),~a$ $b,~a\oplus b,a\oplus _{2}b,a+_{2}b,$ $a\neq b,(a,b)\oplus _{2},a~XOR~b$

Unicode har symboler för modulo 2-addition: U+22BB ⊻ xor , U+2295 ⊕ inringat plus och U+2A27 ⨧ plustecken med nedsänkt två , U+2A52 ⩒ logisk eller med punkt ovanför , och en symbol för modulo summa 2: U +2A0A ⨊ modulo två summa .

Egenskaper

$a\oplus 1={\bar a}$ ( förnekelse )
$a\oplus a=0$ ( självreversibilitet )
$a\oplus b=b\oplus a$ ( kommutativitet )
$(a\oplus b)\oplus c=a\oplus (b\oplus c)$ ( associativitet )
$(a\oplus b)\oplus b=a$ ( reversibilitet )
${\bar a}\oplus b=a\oplus {\bar b}=(a\equiv b)$ ( modulo jämförelser )

Boolesk algebra

I boolesk algebra är addition modulo 2 en funktion av två, tre eller fler variabler (de är också operander för en operation, de är också argument för en funktion). Variabler kan ta värden från en uppsättning . Resultatet hör också till uppsättningen . Resultatet beräknas enligt en enkel regel, eller enligt sanningstabellen . Istället för värden kan vilket annat par lämpliga tecken som helst användas, till exempel eller eller "falskt", "sant", men samtidigt är det nödvändigt att definiera prioritet, till exempel . $\{0,1\}$ $\{0,1\}$ $0.1$ $false,true$ $F,T$ $sant > falskt$

Sanningstabeller:

för binär addition modulo 2 (används i binära halvadderare ) [1] :55–61 :

$a$	$b$	$a\oplus b$
0	0	0
0	ett	ett
ett	0	ett
ett	ett	0

Regel: resultatet är lika om båda operanderna är lika; i alla andra fall är resultatet . $0$ $ett$

för ternär addition modulo 2 (används i binära fulladderare ):

$a$	$b$	$c$	$a\oplus b\oplus c$
0	0	0	0
0	0	ett	ett
0	ett	0	ett
0	ett	ett	0
ett	0	0	ett
ett	0	ett	0
ett	ett	0	0
ett	ett	ett	ett

Regel: resultatet är , om antalet lika stora operander är jämnt (noll är också ett jämnt tal), annars blir resultatet . $0$ $ett$ $ett$

Programmering

I C / C++ , Java , C# , Ruby , PHP , JavaScript , Python , etc., betecknas den bitvisa komplementoperationen med symbolen " ^ ", i Pascal , Delphi , Ada , Visual Basic med det reserverade ordet xor , i assembly språk - det logiska kommandot med samma namn. I detta fall utförs modulo 2-addition för alla bitar av vänster och höger operande i par. Till exempel,

$a=01100101_{2}$

$b=00101001_{2}$

sedan

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

Den exklusiva "eller" -operationen för värden av en boolesk typ (sant, falskt) utförs på olika sätt i olika programmeringsspråk. Till exempel använder Delphi den inbyggda XOR-operatorn (exempel: condition1 xor condition2 ). I C , sedan C99-standarden , returnerar operatorn " ^ " på operander av boolesk typ resultatet av att tillämpa den logiska XOR-operationen. I C++ returnerar operatorn " ^ " för booltypen bool resultatet enligt de beskrivna reglerna, medan den för andra typer tillämpas bitvis.

Genom att använda det bitvisa exklusiva "eller" kan du byta värden för heltalsvariabler utan att använda ytterligare minne .

Förhållande till naturligt språk

I naturligt språk är operationen "modulo addition" ekvivalent med två uttryck:

"resultatet är sant (lika med 1) om A inte är lika med B (A≠B)";
" om A inte är lika med B (A≠B), då sant(1)".

Likheten mellan modulo 2-addition och "antingen ... eller ..."-konstruktionen i naturligt språk påpekas ofta. Det sammansatta påståendet "antingen A eller B" är sant när antingen A eller B är sant/falskt, men inte båda; annars är det sammansatta uttalandet falskt. Detta motsvarar exakt definitionen av en operation i boolesk algebra, om "sant" betecknas med , och "falskt" med . $ett$ $0$

Denna operation jämförs ofta med disjunktion eftersom de är väldigt lika i egenskaper, och båda liknar facket "eller" i dagligt tal. Jämför reglerna för dessa operationer:

$A\lor B$ sant om antingen är sant , eller båda (" minst en av de två"). $A$ $B$
$A\oplus B$ sant om eller är sant , men inte båda (" endast en av två"). $A$ $B$

Operationen utesluter det sista alternativet ("båda på en gång") och kallas därför exklusivt "ELLER". Operationen inkluderar det sista alternativet ("båda på en gång") och kallas ibland ett inkluderande "ELLER" av denna anledning. Tvetydigheten i naturligt språk är att konjunktionen "eller" kan användas i båda fallen. $\ plus$ $\lor$

Quantum Computing

I kvantdatorer är analogen för modulo 2-addition CNOT- grinden .

Digital teknik

Se även

Notera

↑ Shilo V.L. Populära digitala mikrokretsar: Handbok - M .: Radio och kommunikation, 1987. - 352 sid. - (Massradiobibliotek. Nummer 1111).

Externa länkar

Algebra för logik och digitala datorer: Modulo 2-additionsfunktion (xor).

booleska operationer
Disjunktion (ELLER) Konjunktion (AND) Förnekelse (INTE) Exklusivt "eller" (XOR) Pierce Arrow (NOR) Schaeffer stroke (NAND) Ekvivalens (XNOR) inblandning Villkorlig disjunktion (ternär)

$a$	$b$	$c$	$a\oplus b\oplus c$
0	0	0	0
0	0	ett	ett
0	ett	0	ett
0	ett	ett	0
ett	0	0	ett
ett	0	ett	0
ett	ett	0	0
ett	ett	ett	ett

$a$	$b$	$c$	$a\oplus b\oplus c$
0	0	0	0
0	0	ett	ett
0	ett	0	ett
0	ett	ett	0
ett	0	0	ett
ett	0	ett	0
ett	ett	0	0
ett	ett	ett	ett

$a$	$b$	$c$	$a\oplus b\oplus c$
0	0	0	0
0	0	ett	ett
0	ett	0	ett
0	ett	ett	0
ett	0	0	ett
ett	0	ett	0
ett	ett	0	0
ett	ett	ett	ett