Välistav disjunktsioon

Tehte $A\oplus B$Venni diagramm kuid mitte on

Tehte $A\oplus B\oplus C$Venni diagramm $\oplus$ $\iff$

Välistav disjunktsioon ehk välistav VÕI (kasutatakse ka termineid mitteekvivalents , antiekvivalents, range disjunktsioon ) on lausearvutuses binaarne tehe, mis on tõene parajasti siis, kui tema operandidel on erinevad väärtused (kui üks on tõene ja teine väär)

Seda tähistatakse järgmiste infiksoperaatoritega: XOR, EOR, EXOR, ⊻, ⩒, ⩛, ⊕, ↮, ja ≢. Poola kujul on vastav operaator J. Argumentide p ja q välistavat disjunktsiooni saab seega muuhulgas tähistada kõikidel järgnevatel viisidel: $p\oplus q$, $p$ ⩛ $q$, $\mathrm{J}pq$.

Tehte XOR eitus on loogiline ekvivalents, mille väljund on tõene parajasti siis, kui mõlemad sisendid on tõesed.

Nimi "välistav või" tuleb sellest, et tavaline disjunktsioon on tõene ka siis, kui mõlemad sisendid on tõesed; välistava või operaator n-ö välistab selle juhtumi ning tagastab sel juhul väära väärtuse. Loomulikus keeles on välistava disjunktsiooni indikaatoriteks väljendid "kas...või"; "emb-kumb". Näiteks lause "Kas järgid seadust või saad karistada" väljendab välistava või tehet.

Üldisemalt on XOR tõene ainult siis, kui paaritu arv sisendeid on tõesed. Ahel XOR tehetest – a XOR b XOR c XOR d (ja nii edasi) – on tõene siis, kui paaritu arv sisenditest on tõesed, ning väär siis, kui paarisarv sisenditest on tõesed.

Notatsioon

Välistava disjunktsiooni tähistus erineb olenevalt teksti valdkonnast või isegi sellest, milliseid omadusi soovitakse antud kontekstis rõhutada. Lisaks lühendile "XOR" kasutatakse ka kõiki järgnevaid sümboleid.

• +, plussmärk, mille eelis on see, et kõiki tavalisi ringide ja korpuste algebralisi omadusi saab kasutada ilma lisatäpsustusteta; plussmärki kasutatakse ka vahel tavalise disjunktsiooni tähisena.

$p$	$q$	$p+q$
0	0	0
0	1	1
1	0	1
1	1	0

• $\oplus$, plussmärk, millel on ring ümber; seda sümbolit kasutatakse matemaatikas ka otsesumma jaoks.
• J, nagu Jpq
• Kasutatakse ka tavalise disjunktsiooni sümbolit ($\vee$), mida on mingil moel muudetud, nagu järgnevalt
  • $\underset{\_}{\vee }$
  • $\dot{\vee }$
• ^, sisestusmärk (caret), kasutatakse mitmetes programmeerimiskeeltes, nagu C, C++, C#, D, Java, Perl, Ruby, PHP ja Python, tähistab bitikaupa tehtavat XOR operaatorit; seda ei kasutata programmeerimise kontekstidest väljaspool, sest seda saab liiga kergesti segamini ajada sama sümboli teiste kasutustega
• , vahel kujutatud ka järgnevalt
  • ><
  • >-<
• =1, IEC sümboloogias

Tõeväärtustabel

Vasakul pool olevad argumendid kombineeritud XOR tehtega. See on binaarne Walshi maatriks (cf. Hadamardi kood).

Tehte A XOR B tõeväärtustabel näitab, et tehte väärtus on tõene parajasti siis, kui sisendite väärtused on erinevad.

SISEND		VÄLJUND
$A$	$B$	$A\oplus B$
TÕENE	TÕENE	VÄÄR
TÕENE	VÄÄR	TÕENE
VÄÄR	TÕENE	TÕENE
VÄÄR	VÄÄR	VÄÄR

Ekvivalentsid, elimineerimine ja sissejuhatus

Välistavat disjunktsiooni $p\oplus q$ võib väljendada ka konjunktsiooni, disjunktsiooni ja eituse kaudu esitada järgnevalt:

$\begin{array}{ccc}p\oplus q& \equiv & (p\vee q)\wedge \mathrm{\neg }(p\wedge q)\end{array}$

Selle ekvivalentsi tõestus on antud järgmiselt:

$\begin{array}{ccccc}p\oplus q& \equiv & (p\wedge \mathrm{\neg }q)& \vee & (\mathrm{\neg }p\wedge q)\\ & \equiv & ((p\wedge \mathrm{\neg }q)\vee \mathrm{\neg }p)& \wedge & ((p\wedge \mathrm{\neg }q)\vee q)\\ & \equiv & ((p\vee \mathrm{\neg }p)\wedge (\mathrm{\neg }q\vee \mathrm{\neg }p))& \wedge & ((p\vee q)\wedge (\mathrm{\neg }q\vee q))\\ & \equiv & (\mathrm{\neg }p\vee \mathrm{\neg }q)& \wedge & (p\vee q)\\ & \equiv & \mathrm{\neg }(p\wedge q)& \wedge & (p\vee q)\end{array}$

Vahel on ka kasulik kirjutada $p\oplus q$ tehet järgmistel viisidel:

$\begin{array}{ccc}p\oplus q& =& \mathrm{\neg }((p\wedge q)\vee (\mathrm{\neg }p\wedge \mathrm{\neg }q))\end{array}$

$\begin{array}{ccc}p\oplus q& \equiv & (p\wedge \mathrm{\neg }q)\vee (\mathrm{\neg }p\wedge q)\end{array}$

$\begin{array}{ccc}p\oplus q& \equiv & (p\vee q)\wedge (\mathrm{\neg }p\vee \mathrm{\neg }q)\end{array}$

Viimast ekvivalentsi saab tõestada, kasutades eelnevalt mainitud tõestuse neljandal real kaks korda De Morgani seadusi.

Välistav disjunktsioon on samuti samaväärne loogilise ekvivalentsiga, implikatsiooni ja ekvivalentsi teisendusreeglite tõttu.

Kokkuvõttes on meil järgnevad samaväärsused matemaatilises notatsioonis ja tehnilises notatsioonis (engineering notation):

$\begin{array}{ccccccc}p\oplus q& \equiv & (p\wedge \mathrm{\neg }q)& \vee & (\mathrm{\neg }p\wedge q)& =& p\bar{q}+\bar{p}q\\ & \equiv & (p\vee q)& \wedge & (\mathrm{\neg }p\vee \mathrm{\neg }q)& =& (p+q)(\bar{p}+\bar{q})\\ & \equiv & (p\vee q)& \wedge & \mathrm{\neg }(p\wedge q)& \equiv & (p+q)(\overline{pq})\end{array}$

Omadused

kommutatiivsus: jah

$A\oplus B$	$\iff$	$B\oplus A$
	$\iff$

assotsiatiivsus: jah

$A$	$\oplus$	$(B\oplus C)$	$\iff$			$(A\oplus B)$	$\oplus$	$C$
	$\oplus$		$\iff$		$\iff$		$\oplus$

distributiivsus: Välistaval võil ei kehti distributiivsus ühegi binaarse funktsiooniga (isegi mitte iseendaga), aga loogilisel konjunktsioonil kehtib distributiivsus välistava võiga. $C\wedge (A\oplus B)=C\wedge \oplus C\wedge B$

idempotentsus: ei

$A$	$\wedge$	$A$	$\iff$	$0$	$\nLeftrightarrow$	$A$
	$\wedge$		$\iff$		$\nLeftrightarrow$

monotoonsus: ei

$A\to B$	$\nRightarrow$			$(A\oplus C)$	$\to$	$(B\oplus C)$
	$\nRightarrow$		$\nLeftrightarrow$		$\to$

tõesust säilitav: ei

Kui kõik sisendid on tõesed, ei ole väljund tõene

$A\wedge B$	$\nRightarrow$	$A\oplus B$
	$\nRightarrow$

väärsust säilitav: jah

Kui kõik sisendid on väärad, on ka väljund väär.

$A\oplus B$	$\Rightarrow$	$A\vee B$
	$\Rightarrow$

Walshi spektrum: (2,0,0,-2)

Mittelineaarsus: 0 (funktsioon on lineaarne)

Kasutades binaarseid väärtuseid tõese (1) ja väära (0) jaoks, siis käitub välistav disjunktsioon täpselt nagu liitmine mooduli 2 järgi.

"Välistav või" loomulikus keeles

"Eesti keele seletav sõnaraamat" selgitab lausestruktuuri "kas ... või" järgnevalt :Mall:Quote

Rakendusi informaatikas

XOR loogikavärava tavapärane tähistus

Loogikatehted

Nimber liitmine on mittenegatiivsetele täisarvudele binaarsüsteemis vastav välistava või tehe. See on ka vektorite liitmine $(\mathbb{Z}/2\mathbb{Z}{)}^4$korral.

Välistavat võid kasutatakse tihti bitikaupa tehtavaid loogikatehetes. Näited:

• 1 XOR 1 = 0
• 1 XOR 0 = 1
• 0 XOR 1 = 1
• 0 XOR 0 = 0

Nagu eespool mainitud, on välistav disjunktsioon ekvivalentne liitmine modulo 2-ga. Kahe n-bitise stringi välistav disjunktsioon on ekvivalentne standardse liitmisvektoriga vektorruumis $(\mathbb{Z}/2\mathbb{Z}{)}^n$.

Informaatikas on välistaval disjunktsioonil mitmeid kasutusi:

• See ütleb, millal on kaks bitti üksteisest erinevad
• Seda saab kasutada kontrollitava bittide muutjana (otsustav sisend määrab ära, kas teise sisendi väärtust muuta või mitte).
• Selle abil saab kindlaks teha, kas bitte väärtusega 1 on paaritu arv. ($A\oplus B\oplus C\oplus D\oplus E$ on tõene parajasti siis, kui paaritu arv muutujaid on tõesed).

Mõnes arvutiarhitektuuris on efektiivsem hoiustada registris väärtust null nii, et XOR-itakse register iseendaga (bitid, mis XOR-itakse iseendaga tagastavad alati nulli) selle asemel, et nulli väärtust liigutada ja hoiustada.

Arvutigraafikas kasutatakse välisata disjunktsiooni tehet esemete liigutamise kujutamiseks.

Kodeeringud

Peale ASCII koodide on välistav või kodeeritud kui U+22BB ⊻ XOR (HTML ⊻) ja U+2295 ⊕ CIRCLED PLUS (HTML ⊕ · ⊕).

Välislingid

• Näide XOR kasutamisest krüptograafias