Wyłączne lub - Exclusive or

Wyłączne lub
XOR
Diagram Venna wyłączności lub
Tabela prawdy
Bramka logiczna XOR ANSI.svg
Normalne formy
Dysjunktywny
Łączący
Wielomian Żegalkina
Kraty posta
0-zachowanie tak
1-konserwujący nie
Monotonia nie
Affine tak
Venna z

Wyłączne lub lub wyłączne alternatywą jest logiczne działanie , które jest prawdziwe wtedy i tylko wtedy, jeśli jego argumenty różnią (jedno jest prawdziwe, drugie fałszywe).

Jest to symbolizowane przez operatora prefiksu J i przez Infix operatora XOR ( / ˌ ɛ k s ɔːr / lub / z ɔːr / ) EOR , EXOR , , , , , i . Negacja XOR jest logiczny biconditional , który daje prawdziwe wtedy i tylko wtedy, gdy oba wejścia są takie same.

Zyskuje nazwę „wyłączny lub”, ponieważ znaczenie „lub” jest niejednoznaczne, gdy oba operandy są prawdziwe; wyłączny lub operator wyklucza ten przypadek. Czasami jest to traktowane jako „jedno lub drugie, ale nie oba”. Można to zapisać jako „A lub B, ale nie A i B”.

Ponieważ jest asocjacyjny, może być uważany za operator n- argumentowy, który jest prawdziwy wtedy i tylko wtedy, gdy nieparzysta liczba argumentów jest prawdziwa. Oznacza to, że XOR b XOR ... może być traktowany jako XOR ( a , b ,...).

Tabela prawdy

Argumenty po lewej połączone przez XOR. Jest to binarna macierz Walsha (por. kod Hadamarda ).

Tablicą prawdy przedstawień XOR B, które wyprowadza prawdziwe gdy wejścia różnią:

Tabela prawdy XOR
Wejście Wyjście
A b
0 0 0
0 1 1
1 0 1
1 1 0
  • 0, fałsz
  • 1, prawda

Równoważności, eliminacja i wprowadzenie

Wyłączna alternatywa zasadniczo oznacza „albo jedno, ale nie oba ani żadne”. Innymi słowy, stwierdzenie jest prawdziwe wtedy i tylko wtedy, gdy jedno jest prawdziwe, a drugie fałszywe. Na przykład, jeśli dwa konie ścigają się, to jeden z nich wygra wyścig, ale nie oba. Wyłączna alternatywa , również oznaczana przez ? lub , może być wyrażona w postaci koniunkcji logicznej ("logiczne i", ), alternatywy ("logiczne lub", ) i negacji ( ) w następujący sposób:

Wyłączna alternatywa może być również wyrażona w następujący sposób:

Ta reprezentacja XOR może być użyteczna podczas konstruowania obwodu lub sieci, ponieważ ma tylko jedną operację i niewielką liczbę operacji i . Dowód tej tożsamości znajduje się poniżej:

Czasami przydaje się pisanie w następujący sposób:

lub:

Równoważność tę można ustalić, stosując dwukrotnie prawa De Morgana do czwartej linii powyższego dowodu.

Wyłączność lub jest również równoznaczna z negacją logicznego dwuwarunkowego , zgodnie z zasadami implikacji materialnej ( warunkowy materialny jest równoważny z negacją negacji jego poprzednika i jego konsekwencji) i materialnej równoważności .

Podsumowując, w notacji matematycznej i inżynierskiej mamy:

Negacja

Można zastosować ducha praw De Morgana, mamy:

Związek ze współczesną algebrą

Chociaż operatory ( koniunkcja ) i ( alternatywa ) są bardzo przydatne w systemach logicznych, zawodzą w bardziej uogólnionej strukturze w następujący sposób:

Systemy i są monoidami , ale nie są grupą . To niestety uniemożliwia połączenie tych dwóch systemów w większe struktury, takie jak pierścień matematyczny .

Jednak system korzysta z wyłączności lub jest grupą abelową . Kombinacja operatorów i ponad elementów tworzy dobrze znane pole . Pole to może reprezentować dowolną logikę dostępną w systemie i ma dodatkową zaletę arsenału narzędzi do analizy algebraicznej pól.

Dokładniej, jeśli skojarzymy z 0 i 1, można zinterpretować logiczną operację "AND" jako mnożenie, a operację "XOR" jako dodawanie na :

Używanie tej podstawy do opisu systemu logicznego jest określane jako algebraiczna forma normalna .

Wyłączne „lub” w języku naturalnym

Dysjunkcja jest często rozumiana wyłącznie w językach naturalnych . W języku angielskim słowo dysjunktywne „lub” jest często rozumiane wyłącznie, szczególnie w połączeniu z cząstką „either”. Poniższy angielski przykład byłby zwykle rozumiany w rozmowie jako sugestia, że ​​Mary nie jest jednocześnie śpiewaczką i poetką.

1. Maryja jest piosenkarką lub poetką.

Jednak alternatywę można również rozumieć inkluzywnie, nawet w połączeniu z „albo”. Na przykład pierwszy przykład poniżej pokazuje, że „albo” może być trafnie użyte w połączeniu z wyraźnym stwierdzeniem, że oba rozłączenia są prawdziwe. Drugi przykład pokazuje, że wnioskowanie wyłączne znika w kontekstach opadających . Gdyby w tym przykładzie rozdzielenie było rozumiane jako wykluczające, pozostawiłoby to otwartą możliwość, że niektórzy ludzie jedli zarówno ryż, jak i fasolę.

2. Maryja jest śpiewaczką, poetką lub obydwoma.
3. Nikt nie jadł ani ryżu, ani fasoli.

Przykłady takie jak powyższe motywują analizy wnioskowania wyłączności jako pragmatycznych implikatur konwersacyjnych obliczonych na podstawie inkluzywnej semantyki . Implikatury są zazwyczaj anulowane i nie powstają w kontekstach pociągających w dół, jeśli ich obliczenie zależy od Maksimum ilości . Jednak niektórzy badacze potraktowali wyłączność jako bona fide semantyczne implikacje i zaproponowali nieklasyczną logikę, która by ją uprawomocniła.

To zachowanie angielskiego „lub” występuje również w innych językach. Jednak wiele języków ma konstrukcje dysjunktywne, które zdecydowanie wykluczają się, takie jak francuski soit... soit .

Alternatywne symbole

Symbol używany do wyłącznej alternatywy różni się w zależności od dziedziny zastosowania, a nawet zależy od właściwości podkreślanych w danym kontekście dyskusji. Oprócz skrótu „XOR” można również zobaczyć dowolny z następujących symboli:

  • +, znak plus, który ma tę zaletę, że wszystkie zwykłe własności algebraiczne pierścieni i pól matematycznych mogą być użyte bez dalszych ceregieli; ale znak plus jest również używany do inkluzywnej alternatywy w niektórych systemach notacji; zauważ, że alternatywa wyłączna odpowiada dodawaniu modulo 2, które ma następującą tabelę dodawania, wyraźnie izomorficzną do powyższej:
     
0 0 0
0 1 1
1 0 1
1 1 0
  • , zmodyfikowany znak plus; ten symbol jest również używany w matematyce dla bezpośredniej sumy struktur algebraicznych
  • J, jak w J pq
  • Inkluzywny symbol alternatywy ( ), który został w jakiś sposób zmodyfikowany, na przykład
  • ^, karetka , używana w kilku językach programowania , takich jak C , C++ , C# , D , Java , Perl , Ruby , PHP i Python , oznaczająca bitowy operator XOR; nie jest używany poza kontekstami programistycznymi, ponieważ zbyt łatwo można go pomylić z innymi zastosowaniami karetki
  • X-lub.svg, czasami pisane jako
    • ><
    • >-<
  • =1, w symbolice IEC

Nieruchomości

Przemienność : tak
        
Venn0110.svg          Venn0110.svg
Łączność : tak
        
Venn 0101 0101.svg Venn 0011 1100.svg          Venn 0110 1001.svg          Venn 0110 0110.svg Venn 0000 1111.svg
Dystrybucja :
Wyłączność lub nie rozprowadza się na żadnej funkcji binarnej (nawet na siebie), ale logiczne połączenie rozprowadza się na wyłączność lub . (Koniunkcja i wykluczenie lub forma operacji mnożenia i dodawania pola GF(2) , i jak w każdej dziedzinie podlegają prawu rozdzielności.)
Idempotencja : nie
                 
Venn01.svg Venn01.svg          Venn00.svg          Venn01.svg
Monotoniczność : nie
        
Venn 1011 1011.svg          Venn 1011 1101.svg          Venn 0101 1010.svg Venn 0011 1100.svg
Zachowanie prawdy: nie
Gdy wszystkie dane wejściowe są prawdziwe, dane wyjściowe nie są prawdziwe.
        
Venn0001.svg          Venn0110.svg
Zachowanie fałszu: tak
Gdy wszystkie dane wejściowe są fałszywe, dane wyjściowe są fałszywe.
        
Venn0110.svg          Venn0111.svg
Widmo Walsha : (2,0,0,−2)
Nie- liniowość : 0
Funkcja jest liniowa.

Jeśli używasz wartości binarnych dla prawdy (1) i fałszu (0), to wyłączne lub działa dokładnie tak, jak dodawanie modulo 2.

Informatyka

Tradycyjna symboliczna reprezentacja bramki logicznej XOR

Operacja bitowa

Nimber dodatkiem jest wyłącznym lub z nieujemnych liczb całkowitych w binarnej reprezentacji. Jest to również dodawanie wektorów w .

Dysjunkcja wyłączna jest często używana w operacjach bitowych. Przykłady:

  • 1 XOR 1 = 0
  • 1 XOR 0 = 1
  • 0 XOR 1 = 1
  • 0 XOR 0 = 0
  • 1110 2 XOR 1001 2 = 0111 2 (odpowiada to dodaniu bez przeniesienia )

Jak wspomniano powyżej, ponieważ wykluczająca alternatywa jest identyczna z dodawaniem modulo 2, bitowa alternatywa wykluczająca dwóch n- bitowych łańcuchów jest identyczna ze standardowym wektorem dodawania w przestrzeni wektorowej .

W informatyce wykluczenie wyłączne ma kilka zastosowań:

  • Mówi, czy dwa bity są nierówne.
  • Jest to opcjonalny przerzutnik bitów (decydujące dane wejściowe wybierają, czy odwrócić dane wejściowe).
  • Mówi, czy istnieje nieparzysta liczba 1 bitów ( jest prawdą, jeśli nieparzysta liczba zmiennych jest prawdziwa).

W obwodach logicznych można wykonać prosty sumator z bramką XOR do dodawania liczb oraz szeregiem bramek AND, OR i NOT, aby utworzyć wyjście przeniesienia.

W niektórych architekturach komputerowych bardziej wydajne jest przechowywanie zera w rejestrze przez XOR-owanie rejestru ze sobą (bity XOR-z samym sobą są zawsze zerowe) zamiast ładowania i przechowywania wartości zero.

W prostych sieciach neuronowych aktywowanych progiem modelowanie funkcji XOR wymaga drugiej warstwy, ponieważ XOR nie jest funkcją liniowo separowaną .

Exclusive-lub jest czasami używany jako prosta funkcja miksowania w kryptografii , na przykład z jednorazowymi padami lub systemami sieciowymi Feistel .

Exclusive-lub jest również intensywnie używany w szyfrach blokowych, takich jak AES (Rijndael) lub Serpent oraz w implementacji szyfrowania blokowego (CBC, CFB, OFB lub CTR).

Podobnie XOR może być używany do generowania pul entropii dla sprzętowych generatorów liczb losowych . Operacja XOR zachowuje losowość, co oznacza, że ​​losowy bit XOR z nielosowym bitem da w wyniku losowy bit. Wiele źródeł potencjalnie losowych danych można łączyć za pomocą XOR, a nieprzewidywalność danych wyjściowych gwarantuje co najmniej tak dobre, jak najlepsze pojedyncze źródło.

XOR jest używany w RAID 3–6 do tworzenia informacji o parzystości. Na przykład, RAID może "tworzyć kopię zapasową" bajtów 10011100 2 i 01101100 2 z dwóch (lub więcej) dysków twardych przez XORowanie wspomnianych bajtów, co daje ( 11110000 2 ) i zapisuje je na innym dysku. Zgodnie z tą metodą, jeśli którykolwiek z trzech dysków twardych zostanie utracony, utracony bajt może zostać odtworzony przez XORing bajtów z pozostałych dysków. Na przykład, jeśli dysk zawierający 01101100 2 zostanie utracony, 10011100 2 i 11110000 2 można wykonać XOR, aby odzyskać utracony bajt.

XOR jest również używany do wykrywania przepełnienia w wyniku operacji arytmetycznej ze znakiem binarnym. Jeśli skrajny lewy zachowany bit wyniku nie jest taki sam, jak nieskończona liczba cyfr po lewej stronie, oznacza to, że wystąpiło przepełnienie. XORing tych dwóch bitów da „1” w przypadku przepełnienia.

XOR może być użyty do zamiany dwóch zmiennych numerycznych w komputerach za pomocą algorytmu zamiany XOR ; jest to jednak uważane za bardziej ciekawostkę i nie jest to zalecane w praktyce.

Połączone listy XOR wykorzystują właściwości XOR w celu zaoszczędzenia miejsca na reprezentowanie podwójnie połączonych struktur danych list .

W grafice komputerowej metody rysowania oparte na XOR są często używane do zarządzania takimi elementami, jak obwiednie i kursory w systemach bez kanałów alfa lub płaszczyzn nakładek.

Kodowanie

Jest również nazywany „strzałką nie lewo-prawo” (\nleftrightarrow) w przecenach opartych na lateksie ( ). Oprócz kodów ASCII, operator jest zakodowany jako U+22BBXOR (HTML  · ) i U + 2295CIRCLED PLUS (HTML  · ), oba w blokowych operatorach matematycznych . &#8891;  &veebar; &#8853;  &CirclePlus;, &oplus;

Zobacz też

Uwagi

  1. ^ Germundsson, Roger; Weisstein, Eric. "XOR" . MatematykaŚwiat . Badania Wolframa . Źródło 17 czerwca 2015 .
  2. ^ Craig Edward, wyd. (1998), Routledge Encyclopedia of Philosophy , 10 , Taylor i Francis, s. 496, ISBN 9780415073103
  3. ^ a b c d Aloni, Maria (2016), Zalta, Edward N. (red.), "Disjunction" , The Stanford Encyclopedia of Philosophy (red. Zima 2016), Metaphysics Research Lab, Stanford University , pobrane 2020-09- 03
  4. ^ Jennings cytuje wielu autorów, którzy twierdzą, że słowo „lub” ma sens wyłączny. Patrz rozdział 3, „Pierwszy mit 'Or'”:
    Jennings, RE (1994). Genealogia rozdzielenia . Nowy Jork: Oxford University Press.
  5. ^ Davies, Robert B (28 lutego 2002). „Ekskluzywne OR (XOR) i sprzętowe generatory liczb losowych” (PDF) . Pobrano 28 sierpnia 2013 .
  6. ^ Nobel, Rickard (26 lipca 2011). "Jak faktycznie działa RAID 5" . Źródło 23 marca 2017 .

Zewnętrzne linki