Exclusiv sau"

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 1 aprilie 2022; verificările necesită 2 modificări .

Exclusiv sau"
Adăugarea Modulului 2, XOR
diagrama Venn
tabelul de adevăr	$(0110)$
poarta logica
forme normale
Disjunctiv	$\overline {x}\cdot y+x\cdot \overline {y}$
conjunctivala	$(\overline {x}+\overline {y})\cdot (x+y)$
polinomul Zhegalkin	$x\oplus y$
Calitatea de membru la cursuri precompletate
Salvează 0	da
Salvează 1	Nu
Monoton	Nu
liniar	da
Auto-dual	Nu

„sau” exclusiv ( adunare modulo 2 , XOR , disjuncție strictă , adunare pe biți , inversare masca , adunare Zhegalkin , scădere logică , disparitate logică ) - Funcție booleană , precum și operație logică și pe biți, în cazul a două variabile, rezultatul operației este adevărat dacă și numai dacă unul dintre argumente este adevărat și celălalt este fals. Pentru o funcție de trei (adunare ternară modulo 2) sau mai multe variabile, rezultatul operației va fi adevărat numai atunci când numărul de argumente egal cu 1 care alcătuiesc mulțimea curentă este impar. O astfel de operație apare în mod natural în inelul de reziduuri modulo 2 , de unde și numele operației.

Adăugarea la Modulul 2 se numește „exclusiv sau” și „disjuncție strictă” pentru a o deosebi de „sau” logică „obișnuită” (neexclusivă) - disjuncție logică nestrictă . În teoria mulțimilor, adăugarea modulo 2 corespunde funcționării diferenței simetrice a două mulțimi.

Notație

Înregistrarea poate fi prefix (" înregistrare poloneză ") - semnul operației este plasat înaintea operanzilor, infix - semnul operației este plasat între operanzi și postfix - semnul operației este plasat după operanzi. Când numărul de operanzi este mai mare de doi, notațiile prefix și postfix sunt mai economice decât notația infix. Cea mai comună notație este: ^ 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 are simboluri pentru adăugarea modulo 2: U+22BB ⊻ xor , U+2295 ⊕ plus încercuit și U+2A27 ⨧ semnul plus cu indice doi , U+2A52 ⩒ logic sau cu punct deasupra și un simbol pentru suma modulo 2: U +2A0A ⨊ sumă modulo doi .

Proprietăți

$a\oplus 1={\bar a}$ ( negarea )
$a\oplus a=0$ ( auto-reversibilitate )
$a\oplus b=b\oplus a$ ( comutativitate )
$(a\oplus b)\oplus c=a\oplus (b\oplus c)$ ( asociativitate )
$(a\oplus b)\oplus b=a$ ( reversibilitate )
${\bar a}\oplus b=a\oplus {\bar b}=(a\equiv b)$ ( comparații modulo )

Algebră booleană

În algebra booleană, adăugarea modulo 2 este o funcție a două, trei sau mai multe variabile (sunt și operanzii unei operații, sunt și argumentele unei funcții). Variabilele pot lua valori dintr-un set . Rezultatul aparține și setului . Rezultatul este calculat după o regulă simplă sau după tabelul de adevăr . În loc de valori , poate fi folosită orice altă pereche de caractere adecvate, de exemplu, sau sau „fals”, „adevărat”, dar în același timp este necesar să se definească precedența, de exemplu, . $\{0,1\}$ $\{0,1\}$ $0,1$ $false,true$ $F,T$ $adevărat > fals$

Tabelele de adevăr:

pentru adunare binară modulo 2 (utilizată în semi-adunatoare binare ) [1] :55–61 :

$A$	$b$	$a\oplus b$
0	0	0
0	unu	unu
unu	0	unu
unu	unu	0

Regula: rezultatul este egal dacă ambii operanzi sunt egali; în toate celelalte cazuri rezultatul este . $0$ $unu$

pentru adiția ternară modulo 2 (utilizată în sumatoarele binari complete ):

$A$	$b$	$c$	$a\oplus b\oplus c$
0	0	0	0
0	0	unu	unu
0	unu	0	unu
0	unu	unu	0
unu	0	0	unu
unu	0	unu	0
unu	unu	0	0
unu	unu	unu	unu

Regula: rezultatul este , dacă numărul de operanzi egal este par (zero este și un număr par), în caz contrar rezultatul este . $0$ $unu$ $unu$

Programare

În C / C++ , Java , C# , Ruby , PHP , JavaScript , Python etc., operația de complement pe biți se notează prin simbolul " ^ ", în Pascal , Delphi , Ada , Visual Basic prin cuvântul rezervat xor , în asamblare limba - comanda logică cu același nume. În acest caz, adăugarea modulo 2 este efectuată pentru toți biții operandului din stânga și din dreapta în perechi. De exemplu,

dacă

$a=01100101_{2}$

$b=00101001_{2}$

apoi

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

Operația exclusivă „sau” pentru valori de tip boolean (adevărat, fals) este efectuată diferit în diferite limbaje de programare. De exemplu, Delphi folosește operatorul XOR încorporat (exemplu: condition1 xor condition2 ). În C , de la standardul C99 , operatorul " ^ " pe operanzi de tip boolean returnează rezultatul aplicării operației XOR logice. În C++ , operatorul „ ^ ” pentru tipul bool boolean returnează rezultatul conform regulilor descrise, în timp ce pentru alte tipuri este aplicat pe biți.

Utilizarea exclusivă „sau” pe biți vă permite să schimbați valorile variabilelor întregi fără a utiliza memorie suplimentară .

Relația cu limbajul natural

În limbajul natural, operația „modulo addition” este echivalentă cu două expresii:

„rezultatul este adevărat (egal cu 1) dacă A nu este egal cu B (A≠B)”;
„ dacă A nu este egal cu B (A≠B), atunci adevărat(1)”.

Asemănarea dintre adăugarea modulo 2 și construcția „fie... fie...” în limbaj natural este adesea subliniată. Afirmația compusă „fie A sau B” este adevărată atunci când A sau B este adevărat/fals, dar nu ambele; altfel afirmaţia compusă este falsă. Aceasta corespunde exact cu definiția unei operații din algebra booleană, dacă „adevărat” este notat cu , iar „fals” cu . $unu$ $0$

Această operație este adesea comparată cu disjuncția deoarece sunt foarte asemănătoare ca proprietăți și ambele sunt similare cu uniunea „sau” în vorbirea de zi cu zi. Comparați regulile pentru aceste operațiuni:

$A\lor B$ adevărat dacă oricare este adevărat , sau ambele (" cel puțin unul dintre cei doi"). $A$ $B$
$A\oplus B$ adevărat dacă sau este adevărat , dar nu ambele (" doar unul din două"). $A$ $B$

Operația exclude ultima opțiune („ambele deodată”) și din acest motiv se numește exclusiv „SAU”. Operația include ultima opțiune („ambele deodată”) și uneori este numită „SAU” inclusiv din acest motiv. Ambiguitatea în limbajul natural este că conjuncția „sau” poate fi folosită în ambele cazuri. $\oplus$ $\lor$

Calcul cuantic

În calculatoarele cuantice, analogul adunării modulo 2 este poarta CNOT .

Tehnologia digitală

Vezi și

Notă

↑ Shilo V.L. Microcircuite digitale populare: Manual.- M .: Radio și comunicare, 1987. - 352 p. - (Bibliotecă radio de masă. Numărul 1111).

Link- uri externe

Algebra calculatoarelor logice și digitale: Modulul 2 Funcția de adăugare (xor).

Operații booleene
Disjuncție (SAU) Conjuncție (ȘI) Refuzarea (NU) Exclusiv „sau” (XOR) Pierce Arrow (NOR) Accident vascular cerebral Schaeffer (NAND) Echivalență (XNOR) implicare Disjuncție condiționată (ternară)

$A$	$b$	$c$	$a\oplus b\oplus c$
0	0	0	0
0	0	unu	unu
0	unu	0	unu
0	unu	unu	0
unu	0	0	unu
unu	0	unu	0
unu	unu	0	0
unu	unu	unu	unu

$A$	$b$	$c$	$a\oplus b\oplus c$
0	0	0	0
0	0	unu	unu
0	unu	0	unu
0	unu	unu	0
unu	0	0	unu
unu	0	unu	0
unu	unu	0	0
unu	unu	unu	unu

$A$	$b$	$c$	$a\oplus b\oplus c$
0	0	0	0
0	0	unu	unu
0	unu	0	unu
0	unu	unu	0
unu	0	0	unu
unu	0	unu	0
unu	unu	0	0
unu	unu	unu	unu