Exkluzivní nebo - Exclusive or

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: „Exkluzivní nebo“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Květen 2013) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Exkluzivní nebo

XOR
Pravdivá tabulka	${ displaystyle (0110)}$
Logická brána
Normální formy
Disjunktivní	${ displaystyle { overline {x}} cdot y + x cdot { overline {y}}}$
Spojovací	${ displaystyle ({ overline {x}} + { overline {y}}) cdot (x + y)}$
Zhegalkinový polynom	${ displaystyle x oplus y}$
Mřížky Postu
0-konzervování	Ano
1-konzervování	Ne
Monotónní	Ne
Afinní	Ano

Vennův diagram z ${ displaystyle scriptstyle A oplus B oplus C}$

Exkluzivní nebo nebo výlučná disjunkce je logická operace který vydává true pouze v případě, že se vstupy liší (jeden je pravdivý, druhý nepravdivý).^[1]

to je symbolizováno operátor předpony J^[2] a podle infix operátory XOR (/ˌɛksˈ.r/ nebo /ˈz.r/), EOR, EXOR, ⊻, ⩒, ⩛, ⊕, ↮, a ≢. The negace XOR je logická biconditional, jehož výstup je pravdivý, pouze pokud jsou dva vstupy stejné.

Získává název „exkluzivní nebo“, protože význam „nebo“ je nejednoznačný, když obojí operandy jsou pravdivé; výhradní nebo provozovatel vylučuje ten případ. Toto je někdy považováno za „jedno nebo druhé, ale ne obojí“. Mohlo by to být napsáno jako „A nebo B, ale ne, A a B“.

Obecněji platí, že XOR je pravdivý pouze v případě, že je splněn lichý počet vstupů. Řetěz XOR -A XOR b XOR C XOR d (a tak dále) - platí vždy, když je lichý počet vstupů pravdivý, a je nepravdivý, kdykoli je sudý počet vstupů pravdivý.

Pravdivá tabulka

Argumenty vlevo kombinované XOR. Toto je binární soubor Walshova matice (srov. Hadamardův kód ).

The pravdivostní tabulka of A XOR B ukazuje, že vydává true, kdykoli se vstupy liší:

• 0, nepravda
• 1, pravda

Ekvivalence, eliminace a úvod

Exkluzivní disjunkce v podstatě znamená „buď jedno, ale ne obojí ani žádné“. Jinými slovy, tvrzení je pravdivé kdyby a jen kdyby jeden je pravdivý a druhý nepravdivý. Pokud například závodí dva koně, vyhraje závod jeden z nich, ale ne oba. Exkluzivní disjunkce ${ Displaystyle p oplus q}$, také označeno ${ displaystyle p}$ ⩛ ${ displaystyle q}$ nebo ${ displaystyle operatorname {J} pq}$, lze vyjádřit pomocí logická spojka („logické a“, ${ displaystyle klín}$), disjunkce („logické nebo“, ${ displaystyle lor}$) a negace (${ displaystyle lnot}$) jak následuje:

${ displaystyle { begin {matrix} p oplus q & = & (p lor q) land lnot (p land q) end {matrix}}}$

Exkluzivní disjunkce ${ Displaystyle p oplus q}$ lze vyjádřit také následujícím způsobem:

${ displaystyle { begin {matrix} p oplus q & = & (p land lnot q) lor ( lnot p land q) end {matrix}}}$

Toto znázornění XOR může být užitečné při konstrukci obvodu nebo sítě, protože má pouze jeden ${ displaystyle lnot}$ provoz a malý počet ${ displaystyle klín}$ a ${ displaystyle lor}$ operace. Důkaz této identity je uveden níže:

${ displaystyle { begin {matrix} p oplus q & = & (p land lnot q) & lor & ( lnot p land q) [3pt] & = & ((p land lnot q) lor lnot p) & land & ((p land lnot q) lor q) [3pt] & = & ((p lor lnot p) land ( lnot q lor lnot p)) & land & ((p lor q) land ( lnot q lor q)) [3pt] & = & ( lnot p lor lnot q) & land & ( p lor q) [3pt] & = & lnot (p land q) & land & (p lor q) end {matrix}}}$

Někdy je užitečné psát ${ Displaystyle p oplus q}$ následujícím způsobem:

${ displaystyle { begin {matrix} p oplus q & = & lnot ((p land q) lor ( lnot p land lnot q)) end {matrix}}}$

nebo:

${ displaystyle { begin {matrix} p oplus q & = & (p lor q) land ( lnot p lor lnot q) end {matrix}}}$

Tuto rovnocennost lze stanovit použitím De Morganovy zákony dvakrát do čtvrtého řádku výše uvedeného důkazu.

Exkluzivní nebo je také ekvivalentní negaci a logická biconditional, pravidly hmotné implikace (a materiál podmíněný je ekvivalentem disjunkce jeho negace předchůdce a jeho důsledek) a materiální rovnocennost.

Stručně řečeno, v matematické a technické notaci máme:

${ displaystyle { begin {matrix} p oplus q & = & (p land lnot q) & lor & ( lnot p land q) & = & p { overline {q}} + { overline { p}} q [3pt] & = & (p lor q) & land & ( lnot p lor lnot q) & = & (p + q) ({ overline {p}} + { overline {q}}) [3pt] & = & (p lor q) & land & lnot (p land q) & = & (p + q) ({ overline {pq}}) end {matrix}}}$

Vztah k moderní algebře

Ačkoliv operátory ${ displaystyle klín}$ (spojení ) a ${ displaystyle lor}$ (disjunkce ) jsou velmi užitečné v logických systémech, selhávají zobecnitelnější strukturou následujícím způsobem:

Systémy ${ displaystyle ( {T, F }, klín)}$ a ${ displaystyle ( {T, F }, lor)}$ jsou monoidy, ale ani to není skupina. To bohužel brání kombinaci těchto dvou systémů do větších struktur, například a matematický prsten.

Systém však používá exkluzivní nebo ${ displaystyle ( {T, F }, oplus)}$ je an abelianská skupina. Kombinace operátorů ${ displaystyle klín}$ a ${ displaystyle oplus}$ přes prvky ${ displaystyle {T, F }}$ produkovat známé pole ${ displaystyle F_ {2}}$. Toto pole může představovat jakoukoli logiku, kterou lze v systému získat ${ displaystyle ( land, lor)}$ a má další výhodu arzenálu nástrojů algebraické analýzy pro pole.

Přesněji řečeno, pokud se někdo přidruží ${ displaystyle F}$ s 0 a ${ displaystyle T}$ s 1 lze logickou operaci "AND" interpretovat jako násobení ${ displaystyle F_ {2}}$ a operace „XOR“ jako doplněk na ${ displaystyle F_ {2}}$:

${ displaystyle { begin {matrix} r = p land q & Leftrightarrow & r = p cdot q { pmod {2}} [3pt] r = p oplus q & Leftrightarrow & r = p + q { pmod {2}} end {matrix}}}$

Použití tohoto základu k popisu booleovského systému se označuje jako algebraická normální forma.

Exkluzivní „nebo“ v angličtině

Oxfordský anglický slovník vysvětluje „buď ... nebo“ následovně:

Primární funkce buď, atd., je zdůraznit dokonalá lhostejnost ze dvou (nebo více) věcí nebo kurzů ...; ale sekundární funkcí je zdůraznit vzájemnou výlučnost, = jednu ze dvou, ale ne obě.^[3]

Výhradní - nebo výslovně uvádí „jeden nebo druhý, ale ne ani jeden, ani oba.“ Nicméně, mapování korespondence mezi formální Booleovský operátory a spojky přirozeného jazyka zdaleka nejsou jednoduché nebo individuální: je studován po celá desetiletí lingvistika a analytická filozofie.^{[Citace je zapotřebí ]}

Po tomto druhu intuice zdravého rozumu o „nebo“ se někdy tvrdí, že v mnoha přirozených jazycích Angličtina zahrnuto, slovo „nebo“ má „výlučný“ význam.^[4] The výlučná disjunkce dvojice propozic, (p, q), to má znamenat to p je pravda nebo q je pravda, ale ne obojí. Lze například tvrdit, že běžným záměrem výroku typu „Můžeš si dát kávu nebo čaj?“ Je stanovit, že může platit přesně jedna z podmínek. Za určitých okolností by jistě měla být věta jako tento příklad brána jako zakazující možnost přijmout obě možnosti.

V angličtině se konstrukt „buď ... nebo“ obvykle používá k označení výlučné nebo a a „nebo“ obecně používaný pro inkluzivní.^{[pochybný – diskutovat]} Ve španělštině však může být slovo „o“ (nebo) použito ve tvaru „p Ó q„(včetně) nebo formulář„ o p Ó q"(exkluzivní). Někteří mohou tvrdit, že jakýkoli binární nebo jiný n-ary exkluzivní „nebo“ je pravdivé právě tehdy, má-li lichý počet skutečných vstupů (není to však jediná rozumná definice; například digitální brány xor s více vstupy tuto definici obvykle nepoužívají), a že tam není žádná spojka v angličtině, která má tuto obecnou vlastnost. Například Barrett a Stenner tvrdí v článku z roku 1971 „The Myth of the Exclusive 'Or'„(Mind, 80 (317), 116–121), že žádný autor neprodukoval příklad anglické věty nebo věty, která se jeví jako nepravdivá, protože oba její vstupy jsou pravdivé, a opráší nebo věty jako„ Světlo žárovka je buď zapnutá nebo vypnutá „spíše než povahu slova„ nebo “odráží konkrétní fakta o světě.holičský paradox „- Všichni ve městě se holí nebo ho holí holič, kdo holí holiče? - by nemělo být paradoxní, kdyby„ nebo “nemohlo být výlučné (i když by purista mohl říci, že ve výroku paradoxu je vyžadováno„ buď “) ).

Alternativní symboly

Symbol používaný pro výlučnou disjunkci se liší od jedné oblasti aplikace k další a dokonce závisí na vlastnostech zdůrazňovaných v daném kontextu diskuse. Kromě zkratky „XOR“ lze také vidět některý z následujících symbolů:

• +, znaménko plus, které má tu výhodu, že všechny běžné algebraické vlastnosti matematické prsteny a pole lze použít bez dalších okolků; ale znaménko plus se také používá pro inkluzivní disjunkce v některých notačních systémech; Všimněte si, že výhradní disjunkce odpovídá přidání modulo 2, který má následující tabulku sčítání, jasně izomorfní na výše uvedenou:

${ displaystyle p}$	${ displaystyle q}$	${ displaystyle p + q}$
0	0	0
0	1	1
1	0	1
1	1	0

• ${ displaystyle oplus}$, upravené znaménko plus; tento symbol se také používá v matematice pro přímý součet algebraických struktur
• J, jako v J.pq
• Včetně symbolu disjunkce (${ displaystyle lor}$), který je nějakým způsobem upraven, například
  • ${ displaystyle { underline { lor}}}$
  • ${ displaystyle { dot { vee}}}$
• ^, stříška, použitý v několika programovací jazyky, jako C, C ++, C#, D, Jáva, Perl, Rubín, PHP a Krajta, označující bitový Operátor XOR; nepoužívá se mimo programovací kontexty, protože je příliš snadno zaměnitelná s jiným použitím stříšky
• , někdy psáno jako
  • ><
  • >-<
• =1, v symbolice IEC

Vlastnosti

Komutativita: Ano

${ displaystyle A oplus B}$	${ displaystyle Leftrightarrow}$	${ displaystyle B oplus A}$
	${ displaystyle Leftrightarrow}$

Asociativita: Ano

${ displaystyle ~ A}$	${ displaystyle ~~~ oplus ~~~}$	${ displaystyle (B oplus C)}$	${ displaystyle Leftrightarrow}$			${ displaystyle (A oplus B)}$	${ displaystyle ~~~ oplus ~~~}$	${ displaystyle ~ C}$
	${ displaystyle ~~~ oplus ~~~}$		${ displaystyle Leftrightarrow}$		${ displaystyle Leftrightarrow}$		${ displaystyle ~~~ oplus ~~~}$

Distribuce:

Exkluzivní nebo nedistribuuje přes žádnou binární funkci (dokonce ani samotnou), ale logická spojka se distribuuje přes exkluzivní nebo. ${ displaystyle C land (A oplus B) = (C land A) oplus (C land B)}$ (Spojovací a výlučné nebo tvoří operace násobení a sčítání a pole GF (2) a stejně jako v jakékoli oblasti dodržují distributivní zákon.)

Idempotence: Ne

${ displaystyle ~ A ~}$	${ displaystyle ~ oplus ~}$	${ displaystyle ~ A ~}$	${ displaystyle Leftrightarrow}$	${ displaystyle ~ 0 ~}$	${ displaystyle nLeftrightarrow}$	${ displaystyle ~ A ~}$
	${ displaystyle ~ oplus ~}$		${ displaystyle Leftrightarrow}$		${ displaystyle nLeftrightarrow}$

Monotónnost: Ne

${ displaystyle A rightarrow B}$	${ displaystyle nRightarrow}$			${ displaystyle (A oplus C)}$	${ displaystyle rightarrow}$	${ displaystyle (B oplus C)}$
	${ displaystyle nRightarrow}$		${ displaystyle Leftrightarrow}$		${ displaystyle rightarrow}$

Zachování pravdy: ne

Pokud jsou všechny vstupy pravdivé, výstup není pravdivý.

${ displaystyle A land B}$	${ displaystyle nRightarrow}$	${ displaystyle A oplus B}$
	${ displaystyle nRightarrow}$

Zachování lži: ano

Když jsou všechny vstupy nepravdivé, výstup je nepravdivý.

${ displaystyle A oplus B}$	${ displaystyle Rightarrow}$	${ displaystyle A lor B}$
	${ displaystyle Rightarrow}$

Walshovo spektrum: (2,0,0,−2)

Ne-linearita: 0

Funkce je lineární.

Pokud používáte binární potom hodnoty pro true (1) a false (0) exkluzivní nebo funguje přesně jako přidání modulo 2.

Počítačová věda

Tradiční symbolické znázornění XOR logická brána

Bitová operace

Nimber sčítání je exkluzivní nebo z nezáporná celá čísla v binární zastoupení. Toto je také přidání vektoru v ${ displaystyle ( mathbb {Z} / 2 mathbb {Z}) ^ {4}}$.

Exkluzivní disjunkce se často používá pro bitové operace. Příklady:

• 1 XOR 1 = 0
• 1 XOR 0 = 1
• 0 XOR 1 = 1
• 0 XOR 0 = 0
• 11102 XOR 10012 = 01112 (to je ekvivalent přidání bez nést )

Jak je uvedeno výše, protože výlučná disjunkce je identická s přidáním modulo 2, bitová výlučná disjunkce dvou n-bitové řetězce jsou identické se standardním vektorem sčítání v souboru vektorový prostor ${ displaystyle ( mathbb {Z} / 2 mathbb {Z}) ^ {n}}$.

V informatice má výlučná disjunkce několik využití:

• Říká, zda jsou dva bity nerovné.
• Jedná se o volitelný nástroj pro převrácení bitů (rozhodující vstup určuje, zda se má invertovat zadávání dat).
• Říká, zda existuje zvláštní počet 1 bitů (${ displaystyle A oplus B oplus C oplus D oplus E}$ je pravda iff lichý počet proměnných je pravdivý).

V logických obvodech jednoduché zmije lze vyrobit s XOR brána přidat čísla a řadu bran AND, OR a NOT k vytvoření výstupu carry.

Na některých počítačových architekturách je efektivnější ukládat nulu do registru tak, že XOR vytvoří sám registr (bity XOR-ed jsou samy o sobě vždy nulové) namísto načítání a ukládání hodnoty nula.

V jednoduchém prahu aktivován neuronové sítě, modelování funkce XOR vyžaduje druhou vrstvu, protože XOR není lineárně oddělitelná funkce.

Exkluzivní nebo se někdy používá jako jednoduchá směšovací funkce v kryptografie například s jednorázová podložka nebo Síť Feistel systémy.^{[Citace je zapotřebí ]}

Exkluzivní - nebo se také velmi používá v blokových šiferách, jako je AES (Rijndael) nebo Serpent, a při implementaci blokových šifer (CBC, CFB, OFB nebo CTR).

Podobně lze XOR použít při generování entropické bazény pro hardwarové generátory náhodných čísel. Operace XOR zachovává náhodnost, což znamená, že náhodný bit XORed s nenáhodným bitem bude mít za následek náhodný bit. Pomocí XOR lze kombinovat více zdrojů potenciálně náhodných dat a nepředvídatelnost výstupu je zaručeně alespoň tak dobrá jako nejlepší jednotlivý zdroj.^[5]

XOR se používá v NÁLET 3–6 pro vytváření paritních informací. Například RAID může „zálohovat“ bajty 100111002 a 011011002 ze dvou (nebo více) pevných disků XORing právě zmíněných bajtů, což má za následek (111100002) a zápis na jinou jednotku. V rámci této metody, pokud dojde ke ztrátě některého ze tří pevných disků, může být ztracený bajt znovu vytvořen bajty XORing ze zbývajících jednotek. Například pokud jednotka obsahující 011011002 je ztracen, 100111002 a 111100002 může být XOR pro obnovení ztraceného bytu.^[6]

XOR se také používá k detekci přetečení ve výsledku podepsané binární aritmetické operace. Pokud nejlevnější ponechaný bit výsledku není stejný jako nekonečný počet číslic vlevo, znamená to, že došlo k přetečení. XORing těchto dvou bitů dá „1“, pokud dojde k přetečení.

XOR lze použít k výměně dvou numerických proměnných v počítačích pomocí Algoritmus swapu XOR; toto je však považováno za spíše kuriozitu a není v praxi podporováno.

Propojené seznamy XOR využívat vlastnosti XOR za účelem úspory místa k reprezentaci dvojnásobně propojený seznam datové struktury.

v počítačová grafika, Ke správě položek jako jsou často používány metody kreslení založené na XOR ohraničující boxy a kurzory na systémech bez alfa kanály nebo překrýt letadla.

Kódování

Kromě kódů ASCII je operátor kódován na U + 22BB ⊻ XOR (HTML⊻ · & veebar;) a U + 2295 ⊕ KRUHOVÉ PLUS (HTML⊕ · & CirclePlus ;, & oplus;), oba v bloku matematické operátory.

Viz také

Poznámky

externí odkazy

• Příklad použití XOR v kryptografii
• Vše o XOR
• Důkazy vlastností XOR a aplikací XOR, CS103: Mathematical Foundations of Computing, Stanford University