Exkluzivní "nebo"

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 1. dubna 2022; kontroly vyžadují 2 úpravy .

Exkluzivní "nebo"
Přídavek Modulo 2, XOR
Vennův diagram
pravdivostní tabulka	$(0110)$
logická brána
normální formy
Disjunktivní	$\overline {x}\cdot y+x\cdot \overline {y}$
spojivkové	$(\overline {x}+\overline {y})\cdot (x+y)$
Zhegalkinův polynom	$x\oplus y$
Členství v předkompletních třídách
Ušetří 0	Ano
Ušetří 1	Ne
Monotónní	Ne
lineární	Ano
Self-duální	Ne

Exkluzivní "nebo" ( modulo 2 sčítání , XOR , striktní disjunkce , bitové sčítání , inverze masky , Zhegalkinovo sčítání , logické odčítání , logická disparita ) - Booleovská funkce , stejně jako logické a bitové operace, v případě dvou proměnných je výsledek operace pravdivý tehdy a jen tehdy, když je jeden z argumentů pravdivý a druhý nepravdivý. Pro funkci tří (ternární sčítání modulo 2) nebo více proměnných bude výsledek operace pravdivý pouze tehdy, když je počet argumentů rovný 1, které tvoří aktuální množinu, lichý. Taková operace přirozeně vzniká v kruhu zbytků modulo 2 , odtud název operace.

Sčítání Modulo 2 se nazývá „exkluzivní nebo“ a „přísná disjunkce“, aby se odlišilo od „obyčejné“ (nevýhradní) logické „nebo“ - nepřísné logické disjunkce . V teorii množin odpovídá sčítání modulo 2 operaci symetrického rozdílu dvou množin.

Notace

Záznam může být prefix (" polský záznam ") - znak operace je umístěn před operandy, infix - znak operace je umístěn mezi operandy a postfix - znak operace je umístěn za operandy. Když je počet operandů větší než dva, jsou prefixové a postfixové zápisy ekonomičtější než infixové zápisy. Nejběžnější zápis je: ^ 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 má symboly pro sčítání modulo 2: U+22BB ⊻ xor , U+2295 ⊕ zakroužkované plus a U+2A27 ⨧ znaménko plus s dolním indexem dva , U+2A52 ⩒ logické nebo s tečkou nad , a symbol pro modulo součet 2: U +2A0A ⨊ modulo dva součet .

Vlastnosti

$a\oplus 1={\bar a}$ ( popírání )
$a\oplus a=0$ ( samovratnost )
$a\oplus b=b\oplus a$ ( komutativnost )
$(a\oplus b)\oplus c=a\oplus (b\oplus c)$ ( asociativita )
$(a\oplus b)\oplus b=a$ ( reverzibilita )
${\bar a}\oplus b=a\oplus {\bar b}=(a\ekviv b)$ ( modulo srovnání )

Booleovská algebra

V Booleově algebře je sčítání modulo 2 funkcí dvou, tří nebo více proměnných (jsou to také operandy operace, jsou také argumenty funkce). Proměnné mohou nabývat hodnot z množiny . Výsledek také patří do sestavy . Výsledek se vypočítá podle jednoduchého pravidla nebo podle pravdivostní tabulky . Místo hodnot lze použít libovolnou jinou dvojici vhodných znaků, např. nebo nebo „false“, „true“, ale zároveň je nutné definovat prioritu např . . $\{0,1\}$ $\{0,1\}$ $0.1$ $false,true$ $F,T$ $pravda > nepravda$

Pravdivé tabulky:

pro binární sčítání modulo 2 (používá se v binárních polovičních sčítačkách ) [1] :55–61 :

$A$	$b$	$a\oplus b$
0	0	0
0	jeden	jeden
jeden	0	jeden
jeden	jeden	0

Pravidlo: výsledek je stejný , pokud jsou oba operandy stejné; ve všech ostatních případech je výsledkem . $0$ $jeden$

pro ternární sčítání modulo 2 (používá se v binárních úplných sčítačkách ):

$A$	$b$	$C$	$a\oplus b\oplus c$
0	0	0	0
0	0	jeden	jeden
0	jeden	0	jeden
0	jeden	jeden	0
jeden	0	0	jeden
jeden	0	jeden	0
jeden	jeden	0	0
jeden	jeden	jeden	jeden

Pravidlo: výsledek je , pokud je počet operandů rovný sudý (nula je také sudé číslo), jinak je výsledek . $0$ $jeden$ $jeden$

Programování

V C / C++ , Java , C# , Ruby , PHP , JavaScript , Python atd. je operace bitového doplňku označena symbolem " ^ ", v Pascalu , Delphi , Ada , Visual Basic vyhrazeným slovem xor , v assembleru jazyk - stejnojmenný logický příkaz. V tomto případě se sčítání modulo 2 provádí pro všechny bity levého a pravého operandu v párech. Například,

-li

$a=01100101_{2}$

$b=00101001_{2}$

pak

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

Výhradní operace „nebo“ pro hodnoty typu boolean (true, false) se v různých programovacích jazycích provádí odlišně. Například Delphi používá vestavěný operátor XOR (příklad: condition1 xor condition2 ). V C od standardu C99 vrací operátor " ^ " na operandech typu boolean výsledek použití logické operace XOR. V C++ operátor „ ^ “ pro bool booleovský typ vrací výsledek podle popsaných pravidel, zatímco pro ostatní typy je aplikován bitově.

Použití bitového exkluzivního „nebo“ vám umožňuje zaměnit hodnoty celočíselných proměnných bez použití další paměti .

Vztah k přirozenému jazyku

V přirozeném jazyce je operace „sčítání modulo“ ekvivalentní dvěma výrazům:

"výsledek je pravdivý (rovná se 1) , pokud A není rovno B (A≠B)";
" pokud se A nerovná B (A≠B), pak true(1)".

Často se poukazuje na podobnost mezi přidáním modulo 2 a konstrukcí „buď ... nebo ...“ v přirozeném jazyce. Složený výrok „buď A nebo B“ je pravdivý, když buď A nebo B je pravdivý/nepravdivý, ale ne oba; jinak je složený příkaz nepravdivý. To přesně odpovídá definici operace v Booleově algebře, pokud "true" je označeno a "false" je označeno . $jeden$ $0$

Tato operace je často přirovnávána k disjunkci , protože mají velmi podobné vlastnosti a obě jsou podobné sjednocení „nebo“ v běžné řeči. Porovnejte pravidla pro tyto operace:

$A\lor B$ true , pokud buď je pravda , nebo obojí (" alespoň jeden ze dvou"). $A$ $B$
$A\oplus B$ true if or is true , ale ne obojí (" pouze jeden ze dvou"). $A$ $B$

Operace vylučuje poslední možnost ("obě najednou") az tohoto důvodu se nazývá exkluzivní "OR". Operace zahrnuje poslední možnost ("obě najednou") a z tohoto důvodu se někdy nazývá inkluzivní "OR". Nejednoznačnost v přirozeném jazyce spočívá v tom, že spojku „nebo“ lze použít v obou případech. $\oplus$ $\lor$

Quantum Computing

V kvantových počítačích je analogem sčítání modulo 2 brána CNOT .

Digitální technologie

Viz také

Poznámka

↑ Shilo V.L. Populární digitální mikroobvody: Příručka - M .: Rádio a komunikace, 1987. - 352 s. - (Hromadná rozhlasová knihovna. Vydání 1111).

Externí odkazy

Algebra logických a digitálních počítačů: Funkce sčítání Modulo 2 (xor).

Booleovské operace
Disjunkce (OR) Konjunkce (AND) Odmítnutí (NE) Exkluzivní "nebo" (XOR) Pierce Arrow (NOR) Schaefferův zdvih (NAND) Ekvivalence (XNOR) implikace Podmíněná disjunkce (ternární)