Eksklusiivinen disjunktio
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.
Lauseen A XOR B totuustaulu osoittaa, että yhdistetty lause on tosi, jos yhdistettävillä lauseilla on eri totuusarvo
jossa:
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 formula_1 eli J"pq", voidaan ilmaista loogisen konjunktion ("looginen ja", formula_2) disjunktion ("looginen tai", formula_3) ja negaation (formula_4) avulla seuraavasti:
Eksklusiivinen disjunktio formula_1 voidaan ilmaista myös seuraavasti:
Tämä esitysmuoto on usein hyödyllinen muodostettaessa loogisia piirejä tai verkkoja, koska siinä on vain yksi formula_4-operaatio ja pieni määrä formula_2- ja formula_3 -operaatioita. Että tämä on yhtäpitävä eksklusiivisen disjunktion kanssa, voidaan todistaa seuraavasti:
Joskus on edullista kirjoittaa formula_1 seuraavaan tapaan:
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:
Propositiologiikassa lauseet muodostavat eräänlaisen algebrallisen struktuurin, jossa laskutoimituksina toimivat esimerkiksi formula_15 (konjunktio) ja formula_3. Vaikka nämä kaksi laskutoimitusta ovat hyvin hyödyllisiä loogisissa systeemeissä, seuraavassa mielessä niistä ei muodostaa yleistettävämpää struktuuria.
Systeemit formula_17 ja formula_18 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 formula_19 on Abelin ryhmä. Yhdessä laskutoimitukset formula_15 ja formula_21 joukossa formula_22 muodostavat kunnan formula_23. Tämä kunta voi esittää mitä tahansa logiikkaa, joka saadaan systeemistä formula_24, ja lisäetuna on, että käytettävissä ovat kuntien algebrallisen analyysin tulokset.
Erityisesti jos totuusarvoa formula_25 (epätosi) merkitään 0:lla ja arvoa formula_26 1:llä, looginen "JA"-operaatio voidaan tulkita kerto­laskuksi ja eksklusiivinen disjunktio "XOR" yhteen­laskuksi kunnassa formula_23:
formula_28
Kun Boolen algebraa käsitellään tältä pohjalta, puhutaan algebrallisesta normaali­muodosta.
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ä:
modulo 2, jolle pätee seuraava taulukko ja joka on selvästi isomorfinen edellä esitetyn kanssa:Unicodessa alleviivatun disjunktiomerkin formula_31 koodiarvo heksadesimaalilukuna on U+22BB, kun taas ympyröidyn plusmerkin formula_21 koodiarvo on U+2295. Kymmenjärjestelmässä edellinen vastaa lukua 8891, jälkimmäinen lukua 8853, minkä vuoksi HTML:ssä ne voidaan merkitä koodeilla ⊻ ja ⊕. Jälkimmäiselle on HTML:ssä myös merkintä &⊕.
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
Liitännäisyys
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:
Monotonisuus ei päde:
Totuuden säilyttävä validiteetti ei päde:
Kun kaikki yhdistettävät lauseet ovat tosia, eksklusiivinen disjunktio ei ole tosi.
Epätotuuden säilyttävä validiteetti pätee:
Kun kaikki yhdistettävät lauseet ovat epätosia, eksklusiivinen disjunktio on myös epätosi.
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.
Eksklusiivista disjunktiota käytetään usein biteittäisiin laskutoimituksiin. Esimerkiksi:
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 formula_35.
Tietotekniikassa biteittäisellä eksklusiivisella disjunktiolla eli XOR-operaatiolla on useita käyttökohteita:
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:eissa RAID 3–6 pariteettitiedon tuottamiseen. Esimerkiksi RAID voi "varmuuskopioida" tavut codice_2 ja codice_3 kahdelta kovalevyltä suorittamalla XOR-operaation vain näille tavuille, jolloin tuloksena on bittijono (codice_4), 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 codice_3, katoaa, tavut codice_2 ja codice_4 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.