Eksklusiivinen disjunktio

Lausetta $\scriptstyle A\oplus B$ vastaava Venn-diagrammi mutta ei on

Lausetta $\scriptstyle A\oplus B\oplus C$ vastaava Venn-diagrammi $~\oplus ~$ $~\Leftrightarrow ~$

Eksklusiivinen disjunktio eli eksklusiivinen tai on looginen konnektiivi, jolla muodostettu yhdistetty lause on tosi, jos ja vain jos yhdistettävillä lauseilla on eri totuusarvot (toinen on tosi ja toinen epätosi). Sen merkkinä käytetään etuliitettä J tai lauseiden väliin merkittyä operaattoria XOR, EOR, EXOR, ⊻, ⊕, ↮ tai ≢. Eksklusiivisen disjunktion negaatio on lauseiden looginen ekvivalenssi, joka on tosi, jos ja vain jos molemmilla lauseilla on sama totuusarvo.

Eksklusiivinen disjunktio vastaa tavanomaisen kielen ilmaisua "joko... tai... mutta ei molemmat". Myös sanaa tai käytetään usein vastaavassa merkityksessä. Määritettä eksklusiivinen eli poissulkeva käytetään, koska sanan "tai" merkitys tavanomaisessa kielessä ei ole yksiselitteinen, kun molemmat lauseet ovat tosia. Eksklusiivinen disjunktio sulkee pois tämän mahdollisuuden, toisin kuin propositio­logiikassa yleisemmin käytetty inklusiivinen disjunktio, joka on tosi myös, jos molemmat lauseet ovat tosia.

Kun eksklusiivisella disjunktiolla yhdistetään useampia kuin kaksi lausetta, yhdistetty lause on tosi vain, jos yhdistettävistä lauseista pariton määrä on tosia. Niinpä lause a XOR b XOR c XOR d on tosi, jos lauseista a, b, c ja d pariton määrä on tosia, ja epätosi, jos niistä parillinen määrä on tosia.

Elektroniikassa ja tietotekniikassa eksklusiivista disjunktiota vastaava looginen portti on XOR-portti.

Totuustaulu

Vasemmalla olevien argumenttien yhdistelmät XOR-konnektiivilla.
Tämä on binäärinen Walshin matriisi
(vertaa Hadamardin koodiin)

Lauseen A XOR B totuustaulu osoittaa, että yhdistetty lause on tosi, jos yhdistettävillä lauseilla on eri totuusarvo

Totuustaulu: XOR

Yhdistettävät lauseet		Yhdistetty lause
A	B
0	0	0
0	1	1
1	0	1
1	1	0

jossa:

0 = epätosi

1 = tosi

Yhtäpitäviä muotoiluja

Eksklusiivinen disjunktio merkitsee oleellisesti: 'jompikumpi mutta ei molemmat'. Toisin sanoen se merkitsee, että toinen vaihto­ehdoista toteutuu, jos ja vain jos toinen ei toteudu. Esimerkiksi kahdesta hevosesta jompikumpi voittaa ravikilpailussa, mutta eivät molemmat. Eksklusiivinen disjunktio $p\oplus q$ eli Jpq, voidaan ilmaista loogisen konjunktion ("looginen ja", $\land$) disjunktion ("looginen tai", $\lor$) ja negaation ($\lnot$) avulla seuraavasti:

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

Eksklusiivinen disjunktio $p\oplus q$ voidaan ilmaista myös seuraavasti:

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

Tämä esitysmuoto on usein hyödyllinen muodostettaessa loogisia piirejä tai verkkoja, koska siinä on vain yksi $\lnot$-operaatio ja pieni määrä $\land$- ja $\lor$ -operaatioita. Että tämä on yhtäpitävä eksklusiivisen disjunktion kanssa, voidaan todistaa seuraavasti:

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

Joskus on edullista kirjoittaa $p\oplus q$ seuraavaan tapaan:

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

Tämä voidaan osoittaa yhtäpitäväksi eksklusiivisen disjunktion kanssa soveltamalla De Morganin lakeja kahteen kertaan edellisen todistuksen neljännelle riville.

Eksklusiivinen disjunktio on myös yhtäpitävä loogisen bikonditionaalin negaation kanssa.

Kaiken kaikkiaan matematiikassa ja insinööri­tieteissä käytettyjä merkintöjä käyttäen pätevät seuraavat tulokset:

${\begin{matrix}p\oplus q&=&(p\land \lnot q)&\lor &(\lnot p\land q)&=&p{\overline {q}}+{\overline {p}}q\\\\&=&(p\lor q)&\land &(\lnot p\lor \lnot q)&=&(p+q)({\overline {p}}+{\overline {q}})\\\\&=&(p\lor q)&\land &\lnot (p\land q)&=&(p+q)({\overline {pq}})\end{matrix}}$

Eksklusiivinen disjunktio ja moderni algebra

Propositiologiikassa lauseet muodostavat eräänlaisen algebrallisen struktuurin, jossa laskutoimituksina toimivat esimerkiksi $\wedge$ (konjunktio) ja $\lor$. Vaikka nämä kaksi laskutoimitusta ovat hyvin hyödyllisiä loogisissa systeemeissä, seuraavassa mielessä niistä ei muodostaa yleistettävämpää struktuuria.

Systeemit $(\{T,F\},\wedge )$ ja $(\{T,F\},\lor )$ ovat molemmat monoideja, eivät ryhmiä. Tämän vuoksi näitä kahta ei voida yhdistää laajemmiksi struktuureiksi kuten renkaaksi.

Jos kuitenkin laskutoimitukseksi valitaan eksklusiivinen disjunktio, systeemi $(\{T,F\},\oplus )$ on Abelin ryhmä. Yhdessä laskutoimitukset $\wedge$ ja $\oplus$ joukossa $\{T,F\}$ muodostavat kunnan $F_{2}$. Tämä kunta voi esittää mitä tahansa logiikkaa, joka saadaan systeemistä $(\land ,\lor )$, ja lisäetuna on, että käytettävissä ovat kuntien algebrallisen analyysin tulokset.

Erityisesti jos totuusarvoa $F$ (epätosi) merkitään 0:lla ja arvoa $T$ 1:llä, looginen "JA"-operaatio voidaan tulkita kerto­laskuksi ja eksklusiivinen disjunktio "XOR" yhteen­laskuksi kunnassa $F_{2}$:

${\begin{matrix}r=p\land q&\Leftrightarrow &r=p\cdot q{\pmod {2}}\\\\r=p\oplus q&\Leftrightarrow &r=p+q{\pmod {2}}\\\end{matrix}}$

Kun Boolen algebraa käsitellään tältä pohjalta, puhutaan algebrallisesta normaali­muodosta.

Vaihtoehtoisia merkintöjä

Eksklusiiviselle disjunktiolle käytetään eri yhteydessä eri merkintöjä, jotka riippuvat siitäkin, mitä ominaisuuksia kulloinkin tähdennetään. Lyhenteen "XOR" ohella käytetään seuraavia merkintöjä:

• Plusmerkki (+). Tämä on matemaattisesti perusteltua, koska eksklusiivinen disjunktio vastaa yhteenlaskua

modulo 2, jolle pätee seuraava taulukko ja joka on selvästi isomorfinen edellä esitetyn kanssa:

Yhteenlasku Modulo 2

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

• • Plusmerkin käytöllä on se lisäetu, että kaikki matemaattisen renkaan ja kunnan algebralliset ominaisuudet pätevät sellaisenaan myös konjunktion ja eksklusiivisen disjunktion muodostamalle loogiselle systeemille. Kuitenkin joissakin yhteyksissä plusmerkillä tarkoitetaan myös inklusiivista disjunktiota.
• Eri tavoin muotoiltu, esimerkiksi ympyröity plus­merkki ($\oplus$). Tätä käytäntöä vastaan on huomautettu, että samaa symbolia käytetään matematiikassa myös algebrallisten systeemien suoralle summalle.
• Etuliite J, kuten merkinnässä pq.
• Inklusiivisen disjunktion symbolia ($\lor$) eri tavoin muotoiltuna, esimerkiksi alleviivattuna (${\underline {\lor }}$) tai lisäämällä sen yläpuolelle piste (${\dot {\vee }}$).
• Joissakin ohjelmointikielissä kuten C:ssä, C++:ssa, C#:ssa, Javassa, Perlissä, Rubyssä ja Pythonissa biteittäisen eksklusiivisen disjunktion merkkinä käytetään "hattu­merkkiä" (^). Tätä ei käytetä muissa yhteyksissä kuin ohjelmoinnissa, koska se voisi helposti sekaantua merkin muihin merkityksiin.
• Symboli , joka joskus kirjoitetaan myös as >< tai as >-<.
• IEC symbologiassa eksklusiivisen disjunktion merkki on "=1".

Merkit Unicodessa ja HTML:ssä

Unicodessa alleviivatun disjunktiomerkin ${\underline {\lor }}$ koodiarvo heksadesimaalilukuna on U+22BB, kun taas ympyröidyn plusmerkin $\oplus$ koodiarvo on U+2295. Kymmenjärjestelmässä edellinen vastaa lukua 8891, jälkimmäinen lukua 8853, minkä vuoksi HTML:ssä ne voidaan merkitä koodeilla &#8891; ja &#8853;. Jälkimmäiselle on HTML:ssä myös merkintä &⊕.

Ominaisuudet

Eksklusiivinen disjunktio noudattaa lasku­lakeja, jotka pitkälti ovat analogisia esi­merkiksi reaalilukujen lasku­säännöille. Niinpä sille pätevät vaihdanta- ja liitäntälaki. Tätä havainnollistavat seuraavat kaaviot:
Vaihdannaisuus

$A\oplus B$	$\Leftrightarrow$	$B\oplus A$
	$\Leftrightarrow$

Liitännäisyys

$~A$	$~~~\oplus ~~~$	$(B\oplus C)$	$\Leftrightarrow$			$(A\oplus B)$	$~~~\oplus ~~~$	$~C$
	$~~~\oplus ~~~$		$\Leftrightarrow$		$\Leftrightarrow$		$~~~\oplus ~~~$

Osittelulaki: Eksklusiivinen disjunktio ei ole ositeltavissa minkään toisen loogisen konnektiivin eikä myöskään itsensä kanssa, mutta looginen konjunktio on ositeltavissa eksklusiivisen disjunktion suhteen. Tämä seuraa siitä, että konjunktio ja eksklusiivinen disjunktio vastaavat kerto- ja yhteenlaskua kunnassa GF(2),

Idempotenssi ei päde:

$~A~$	$~\oplus ~$	$~A~$	$\Leftrightarrow$	$~0~$	$\nLeftrightarrow$	$~A~$
	$~\oplus ~$		$\Leftrightarrow$		$\nLeftrightarrow$

Monotonisuus ei päde:

$A\rightarrow B$	$\nRightarrow$			$(A\oplus C)$	$\rightarrow$	$(B\oplus C)$
	$\nRightarrow$		$\Leftrightarrow$		$\rightarrow$

Totuuden säilyttävä validiteetti ei päde:
Kun kaikki yhdistettävät lauseet ovat tosia, eksklusiivinen disjunktio ei ole tosi.

$A\land B$	$\nRightarrow$	$A\oplus B$
	$\nRightarrow$

Epätotuuden säilyttävä validiteetti pätee:
Kun kaikki yhdistettävät lauseet ovat epätosia, eksklusiivinen disjunktio on myös epätosi.

$A\oplus B$	$\Rightarrow$	$A\lor B$
	$\Rightarrow$

Walshin spektri: (2,0,0,-2)

Epälineaarisuus: 0 (funktio on lineaarinen)

Jos arvoille tosi ja epätosi käytetään binäärilukuarvoja 1 ja 0, eksklusiivinen tai toimii aivan samoin kuin yhteenlasku modulaari­aritmetiikassa modulo 2.

Eksklusiivinen disjunktio tietotekniikassa

Biteittäinen operaatio

Nimberien eli Grundyn lukujen yhteenlasku on binäärimuodossa esitettyjen ei-negatiivisten kokonaislukujen eksklusiivinen disjunktio. Samalla se vastaa myös vektorien yhteenlaskua joukossa $(\mathbb {Z} /2\mathbb {Z} )^{4}$.

Eksklusiivista disjunktiota käytetään usein biteittäisiin laskutoimituksiin. Esimerkiksi:

• 1 xor 1 = 0
• 1 xor 0 = 1
• 0 xor 1 = 1
• 0 xor 0 = 0
• 1110 xor 1001 = 0111 (tämä vastaa yhteenlaskua ilman muistinumeroa.)

Kuten edellä todettiin, eksklusiivinen disjunktio vastaa täysin yhteenlaskua modulo 2. Tästä seuraa, että kahden n-bittisen jonon biteittäinen eksklusiivinen disjunktio vastaa vektorien yhteenlaskua vektoriavaruudessa $(\mathbb {Z} /2\mathbb {Z} )^{n}$.

Tietotekniikassa biteittäisellä eksklusiivisella disjunktiolla eli XOR-operaatiolla on useita käyttökohteita:

• Se kertoo, ovatko kahdella bitillä sama arvo.
• Sillä voidaan vaihtaa tiettyjen bittien arvot käyttämällä toisena syötteenä sopivasti valittua bittijonoa.
• Sillä voidaan selvittää bittijonon pariteetti eli onko tietyssä bittijonossa parillinen vai pariton määrä ykkösiä (koska $A\oplus B\oplus C\oplus D\oplus E$ on tosi, jos ja vain jos pariton määrä yhdistettävistä lauseista on tosia)

Loogisissa piireissä XOR-portin avulla voidaan rakentaa yksinkertainen summain lukujen yhteen­laskemiseksi. Muistinumeron huomioon ottaminen edellyttä kuitenkin, että piiriin on kytkettävä myös AND-, OR- ja NOT-portteja.

Joissakin tietokone­arkkitehtuureissa on tehokkaampaa nollata rekisteri suorittamalla sen sisällöllä XOR-operaatio itsensä kanssa (jolloin tuloksena on aina nolla) kuin ladata ja tallentaa sinne suoraan arvo nolla.

Yksinkertaisissa kynnysaktivoiduissa neuroverkoissa 'XOR'-funktion mallintaminen kuuluu toiselle tasolle, koska 'XOR' ei ole lineaarisesti separoituva funktio.

Eksklusiivista disjunktiota käytetään joskus yksin­kertaisena sekoitus­funktiona kryptografiasa, esimerkiksi One-time pad- ja Feistelin verkkojärjestelmissä.

Samaan tapaan XOR-operaatiolla voidaan generoida entropia-allas satunnais­luku­generaattoreja varten. XOR-operaatio säilyttää satunnaisuuden, mikä tarkoittaa, että jos satunnaisesti arvotulle bitille suoritetaan XOR-operaatio ei-satunnaisen bitin kanssa, tuloksena on satunnainen bitti. Eri lähteistä saatuja potenti­aali­sesti satunnaisia syötteitä voidaan yhdistää XOR-operaatiolla, ja tuloksen ennakoimatto­muus on tällöin varmasti vähintään yhtä hyvä kuin parhaan yksittäisen lähteen.

XOR-operaatiota käytetään RAID-levyjärjestelmissä RAID tasoilla 3–6 pariteettitiedon tuottamiseen. Esimerkiksi RAID voi "varmuuskopioida" tavut 10011100 ja 01101100 kahdelta kovalevyltä suorittamalla XOR-operaation vain näille tavuille, jolloin tuloksena on bittijono (11110000), joka voidaan tallentaa toiselle levylle. Niinpä jos yksi kolmesta levystä katoaa tai vioittuu, kadonnut tavu voidaan palauttaa suorittamalla jäljellä olevien levyjen vastaavissa kohdissa oleville tavuille XOR. Jos esimerkiksi levy, jossa on tavu 01101100, katoaa, tavut 10011100 ja 11110000 voidaan yhdistää XOR:lla kadonneen tavun palauttamiseksi.

XOR-operaatiota käytetään myös sen toteamiseen, onko jokin yksin­kertainen lasku­toimitus johtanut ylivuotoon.

XOR-operaatiota voidaan myös käyttää kahden luvun vaihtamiseen keskenään tietokoneen muistissa. Tällä XOR-vaihtoalgoritmilla on kuitenkin lähinnä kuriositeetti­arvoa eikä sitä suositella käytännössä toteutettavaksi.

XOR-linkitetyissä listoissa käytetään hyväksi XOR-funktion ominaisuuksia tilan säästämiseksi esitettäessä kaksinkertaisesti linkitetyiksi listoiksi muodostettuja tieto­rakenteita.

Tietokonegrafiikassa XOR-pohjaisia piirustus­menetelmiä käytetään usein rajoitettujen laatikoiden ja kohdistimen käsittelyyn.

Katso myös

• Boolen algebra
• Propositiologiikka
• Konjunktio
• Disjunktio
• XOR-portti

Aiheesta muualla

• Esimerkki kryptografiassa käytetystä eksklusiivisesta disjunktiosta