Виняткова диз'юнкція, також операція XOR (від англ. eXclusive OR), додавання за модулем два — логічна та бітова операція, що набуває значення «істина» тоді й лише тоді, коли значення «істина» має суто один з її операндів. Виняткова диз'юнкція є запереченням логічної еквівалентності. У випадку двох змінних результат виконання операції є істинним тоді й тільки тоді, якщо лише один з аргументів є істинним. Для функції трьох і більше змінних результат виконання операції буде істинним тільки тоді, коли аргументів, рівних 1, на заданому наборі буде непарна кількість. Така операція природним чином виникає в кільці лишків за модулем 2, звідки й походить назва операції.
XOR | |
---|---|
Визначення | |
Таблиця істинності | |
Логічний вентиль | |
Нормальні форми | |
Диз'юнктивна | |
Кон'юнктивна | |
Алгебрична | |
Ґратка Поста | |
(зберігає 0) | |
(зберігає 1) | ✗ |
(монотонна) | ✗ |
(лінійна) | |
(само-двоїста) | ✗ |
Додавання за модулем 2 слід відрізняти від простого додавання булевих операндів, яке відповідає звичайному логічному «або», тобто логічній диз'юнкції.
Відповідною операцією в теорії множин є симетрична різниця множин істинності операндів.
Булева алгебра
У булевій алгебрі додавання за модулем 2 — це функція двох, трьох і більше змінних (вони ж — операнди, вони ж — аргументи функції). Змінні можуть набувати значення з множин . Результат також належить множині . Обчислення результату відбувається за простим правилом, або за таблицею істинності. Замість значень можна використовувати будь-яку іншу пару відповідних символів, наприклад або , або «хибність», «істина»; але при цьому необхідно довизначити старшинство, наприклад, .
Таблиці істинності:
- Для бінарного додавання за модулем 2 (застосовується у двійкових напівсуматорах):
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
- Правило: результат дорівнює , якщо обидва операнди рівні; у всіх інших випадках результат дорівнює .
- Для тернарного додавання за модулем 2 (застосовується у двійкових повних суматорах):
X | Y | Z | ⊕(X,Y,Z) |
---|---|---|---|
0 | 0 | 0 | 0 |
1 | 0 | 0 | 1 |
0 | 1 | 0 | 1 |
1 | 1 | 0 | 0 |
0 | 0 | 1 | 1 |
1 | 0 | 1 | 0 |
0 | 1 | 1 | 0 |
1 | 1 | 1 | 1 |
Визначення
Таблиця істинності виглядає таким чином:
F | F | F |
F | T | T |
T | F | T |
T | T | F |
Результат застосування виняткової диз'юнкції такий самий, як і від додавання за модулем 2. Тому й саму операцію часто називають додаванням за модулем 2.
Виняткова диз'юнкція є також запереченням еквівалентності, тобто
Відповідною операцією в теорії множин є симетрична різниця множин.
Властивості
Абелева група
- елемент 0 є нейтральним:
- кожен елемент є обернений сам до себе:
Таким чином є абелевою групою. Разом із операцією також утворюється поле Галуа .
Інші властивості
Функціональна повнота
Множина операцій є функціонально повною:
Виняткова диз'юнкція у природних мовах
Виняткові диз'юнкції найкраще відповідає український вислів «або …, або …». Твердження або А, або В є справедливим, коли справедливе А чи В, але не обоє водночас.
У природній мові операція «складання за модулем» еквівалентна двом виразам:
- «Результат істинний (дорівнює 1), якщо A не дорівнює B (A ≠ B)»;
- «Якщо A не дорівнює B (A ≠ B), то істина (1)».
На схожість між додаванням за модулем 2 і конструкцією «або …, або …» в природній мові часто вказують. Це точно відповідає визначенню операції в булевій алгебрі, якщо «істину» позначати як , а «хибність» як .
Цю операцію нерідко порівнюють із диз'юнкцією, тому що вони дуже схожі за властивостями, і обидві мають схожість зі сполучником «або» у повсякденній мові. Порівняйте правила для цих операцій:
- істинне, якщо істинне або , або обидва відразу.
- істинне, якщо істинне або , але не обидва відразу.
Операція не допускає останнього варіанту («обидва відразу»); саме тому її називають винятковим, ексклюзивним «АБО». Операція допускає останній варіант («обидва відразу»), тож іноді її називають звичним, інклюзивним «АБО». Неоднозначність природної мови полягає в тому, що сполучник «або» застосовують в обох випадках.
Альтернативні символи
Символ, використовуваний для виняткової диз'юнкції, варіюється від однієї області застосування до іншої. Окрім абревіатури «XOR», можуть траплятися:
- Знак плюс (+). Це має сенс, тому що математично винятковій диз'юнкції відповідає додавання за модулем 2, яке має наступну таблицю:
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
- Використання знаку «плюс» має додаткову перевагу, бо всі звичайні алгебраїчні властивості математичного кільця і поля можна використати без зайвого клопоту. Тим не менш, знак плюс використовують також для ексклюзивної диз'юнкції у деяких позначеннях систем.
- Знаком плюс, зміненим певним чином, наприклад, взятим в коло (). Це викликає заперечення: цей же символ вже використовують у математиці для прямої суми алгебраїчних структур.
- Префікс J, як в Jpq.
- Символ диз'юнкції (), який певним чином змінюють: із підкресленням () або з точкою вгорі ().
- У деяких мовах програмування, таких як C, , C#, Java, Perl, MATLAB і Python, символ циркумфлекс (
^
) використовують для позначення оператора побітового XOR. Його не використовують поза контекстом програмування, бо в цьому разі його можна зрозуміти хибно.
Виняткова диз'юнкція у програмуванні
У мовах C/C++ (а також Java, C#, Ruby, PHP, JavaScript, Swift) цю операцію позначають символом «^»; у мовах Паскаль, Delphi, Ада — зарезервованим словом XOR. Додавання виконується побітово для двох операндів. Наприклад,
якщо | |
a = | |
b = | |
тоді | |
a ^ b = |
Виконання операції виняткове "або" для значень логічного типу (true, false) здійснюється в різних мовах програмування по-різному. Наприклад, у Delphi (Object Pascal) використовують вбудований оператор XOR (приклад: умова1 xor умова2). У мові C, починаючи зі стандарту C99, оператор «^» над операндами логічного типу повертає результат застосування логічної операції XOR. У оператор «^» для логічного типу bool повертає результат згідно з описаними правилами, для інших же типів він діє побітово.
За нестачі регістрів оператор XOR можна використати для обміну значеннями змінних.
У квантових комп'ютерах аналогом операції додавання за модулем 2 є вентиль CNOT.
Див. також
Посилання
- Disjunction [ 14 липня 2010 у Wayback Machine.] Stanford Encyclopedia of Philosophy(англ.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Vinyatkova diz yunkciya takozh operaciya XOR vid angl eXclusive OR dodavannya za modulem dva logichna ta bitova operaciya sho nabuvaye znachennya istina todi j lishe todi koli znachennya istina maye suto odin z yiyi operandiv Vinyatkova diz yunkciya ye zaperechennyam logichnoyi ekvivalentnosti U vipadku dvoh zminnih rezultat vikonannya operaciyi ye istinnim todi j tilki todi yaksho lishe odin z argumentiv ye istinnim Dlya funkciyi troh i bilshe zminnih rezultat vikonannya operaciyi bude istinnim tilki todi koli argumentiv rivnih 1 na zadanomu nabori bude neparna kilkist Taka operaciya prirodnim chinom vinikaye v kilci lishkiv za modulem 2 zvidki j pohodit nazva operaciyi XORViznachennyaa b displaystyle a oplus b Tablicya istinnosti 0110 displaystyle 0110 Logichnij ventilNormalni formiDiz yunktivnaa b a b displaystyle overline a cdot b a cdot overline b Kon yunktivna a b a b displaystyle overline a overline b cdot a b Algebrichnaa b displaystyle a oplus b Gratka PostaP0 displaystyle P 0 zberigaye 0 TakP1 displaystyle P 1 zberigaye 1 M displaystyle M monotonna L displaystyle L linijna TakS displaystyle S samo dvoyista Ris 1 Grafik pobitovogo vinyatkovogo abo Dodavannya za modulem 2 slid vidriznyati vid prostogo dodavannya bulevih operandiv yake vidpovidaye zvichajnomu logichnomu abo tobto logichnij diz yunkciyi Vidpovidnoyu operaciyeyu v teoriyi mnozhin ye simetrichna riznicya mnozhin istinnosti operandiv Buleva algebraU bulevij algebri dodavannya za modulem 2 ce funkciya dvoh troh i bilshe zminnih voni zh operandi voni zh argumenti funkciyi Zminni mozhut nabuvati znachennya z mnozhin 0 1 displaystyle 0 1 Rezultat takozh nalezhit mnozhini 0 1 displaystyle 0 1 Obchislennya rezultatu vidbuvayetsya za prostim pravilom abo za tabliceyu istinnosti Zamist znachen 0 1 displaystyle 0 1 mozhna vikoristovuvati bud yaku inshu paru vidpovidnih simvoliv napriklad false true displaystyle false true abo F T displaystyle F T abo hibnist istina ale pri comu neobhidno doviznachiti starshinstvo napriklad true gt false displaystyle true gt false Tablici istinnosti Dlya binarnogo dodavannya za modulem 2 zastosovuyetsya u dvijkovih napivsumatorah A displaystyle A B displaystyle B A B displaystyle A oplus B 000011101110Pravilo rezultat dorivnyuye 0 displaystyle 0 yaksho obidva operandi rivni u vsih inshih vipadkah rezultat dorivnyuye 1 displaystyle 1 Dlya ternarnogo dodavannya za modulem 2 zastosovuyetsya u dvijkovih povnih sumatorah X Y Z X Y Z 0 0 0 01 0 0 10 1 0 11 1 0 00 0 1 11 0 1 00 1 1 01 1 1 1ViznachennyaDiagrama Venna dlya operaciyi A B displaystyle A oplus B Tablicya istinnosti viglyadaye takim chinom A displaystyle A B displaystyle B A B displaystyle A oplus B FFFFTTTFTTTF Rezultat zastosuvannya vinyatkovoyi diz yunkciyi takij samij yak i vid dodavannya za modulem 2 Tomu j samu operaciyu chasto nazivayut dodavannyam za modulem 2 Vinyatkova diz yunkciya ye takozh zaperechennyam ekvivalentnosti tobto A B A B displaystyle A oplus B lnot A leftrightarrow B Vidpovidnoyu operaciyeyu v teoriyi mnozhin ye simetrichna riznicya mnozhin Vlastivostiasociativnista b c a b c displaystyle a oplus b oplus c equiv a oplus b oplus c komutativnista b b a displaystyle a oplus b equiv b oplus a distributivnista b c a b a c displaystyle a land b oplus c equiv a land b oplus a land c Abeleva grupa element 0 ye nejtralnim a 0 a displaystyle a oplus 0 a dd kozhen element ye obernenij sam do sebe a a 0 displaystyle a oplus a 0 dd Takim chinom 1 0 displaystyle 1 0 oplus ye abelevoyu grupoyu Razom iz operaciyeyu displaystyle wedge takozh utvoryuyetsya pole Galua F2 displaystyle F 2 Inshi vlastivostip 1 pp p 1p q p q p q p q p qp p q p qp p q p qp p q p q p p q p qp p q p qp p q p q displaystyle begin matrix p oplus 1 amp amp lnot p p oplus lnot p amp amp 1 p oplus q amp amp lnot p oplus lnot q lnot p oplus q amp amp lnot p oplus q amp amp p oplus lnot q p oplus lnot p land q amp amp p lor q p oplus p land lnot q amp amp p land q p oplus p lor q amp amp lnot p land q lnot p oplus p lor lnot q amp amp p lor q p land p oplus lnot q amp amp p land q p lor p oplus q amp amp p lor q end matrix Funkcionalna povnotaMnozhina operacij displaystyle oplus to ye funkcionalno povnoyu a a a a displaystyle lnot a equiv a to a oplus a a a a a displaystyle lnot a equiv a oplus a to a a b a b displaystyle a lor b equiv lnot a rightarrow b a b a b displaystyle a land b equiv lnot a rightarrow lnot b Vinyatkova diz yunkciya u prirodnih movahVinyatkovi diz yunkciyi najkrashe vidpovidaye ukrayinskij visliv abo abo Tverdzhennya abo A abo V ye spravedlivim koli spravedlive A chi V ale ne oboye vodnochas U prirodnij movi operaciya skladannya za modulem ekvivalentna dvom virazam Rezultat istinnij dorivnyuye 1 yaksho A ne dorivnyuye B A B Yaksho A ne dorivnyuye B A B to istina 1 Na shozhist mizh dodavannyam za modulem 2 i konstrukciyeyu abo abo v prirodnij movi chasto vkazuyut Ce tochno vidpovidaye viznachennyu operaciyi v bulevij algebri yaksho istinu poznachati yak 1 displaystyle 1 a hibnist yak 0 displaystyle 0 Cyu operaciyu neridko porivnyuyut iz diz yunkciyeyu tomu sho voni duzhe shozhi za vlastivostyami i obidvi mayut shozhist zi spoluchnikom abo u povsyakdennij movi Porivnyajte pravila dlya cih operacij A B displaystyle A lor B istinne yaksho istinne A displaystyle A abo B displaystyle B abo obidva vidrazu A B displaystyle A oplus B istinne yaksho istinne A displaystyle A abo B displaystyle B ale ne obidva vidrazu Operaciya displaystyle oplus ne dopuskaye ostannogo variantu obidva vidrazu same tomu yiyi nazivayut vinyatkovim eksklyuzivnim ABO Operaciya displaystyle lor dopuskaye ostannij variant obidva vidrazu tozh inodi yiyi nazivayut zvichnim inklyuzivnim ABO Neodnoznachnist prirodnoyi movi polyagaye v tomu sho spoluchnik abo zastosovuyut v oboh vipadkah Alternativni simvoliSimvol vikoristovuvanij dlya vinyatkovoyi diz yunkciyi variyuyetsya vid odniyeyi oblasti zastosuvannya do inshoyi Okrim abreviaturi XOR mozhut traplyatisya Znak plyus Ce maye sens tomu sho matematichno vinyatkovij diz yunkciyi vidpovidaye dodavannya za modulem 2 yake maye nastupnu tablicyu Dodavannya za modulem 2 p displaystyle p q displaystyle q p q displaystyle p q 0 0 00 1 11 0 11 1 0Vikoristannya znaku plyus maye dodatkovu perevagu bo vsi zvichajni algebrayichni vlastivosti matematichnogo kilcya i polya mozhna vikoristati bez zajvogo klopotu Tim ne mensh znak plyus vikoristovuyut takozh dlya eksklyuzivnoyi diz yunkciyi u deyakih poznachennyah sistem Znakom plyus zminenim pevnim chinom napriklad vzyatim v kolo displaystyle oplus Ce viklikaye zaperechennya cej zhe simvol vzhe vikoristovuyut u matematici dlya pryamoyi sumi algebrayichnih struktur Prefiks J yak v Jpq Simvol diz yunkciyi displaystyle lor yakij pevnim chinom zminyuyut iz pidkreslennyam displaystyle underline lor abo z tochkoyu vgori displaystyle dot vee U deyakih movah programuvannya takih yak C C C Java Perl MATLAB i Python simvol cirkumfleks vikoristovuyut dlya poznachennya operatora pobitovogo XOR Jogo ne vikoristovuyut poza kontekstom programuvannya bo v comu razi jogo mozhna zrozumiti hibno Vinyatkova diz yunkciya u programuvanniU movah C C a takozh Java C Ruby PHP JavaScript Swift cyu operaciyu poznachayut simvolom u movah Paskal Delphi Ada zarezervovanim slovom XOR Dodavannya vikonuyetsya pobitovo dlya dvoh operandiv Napriklad yakshoa 011001012 displaystyle 01100101 2 b 001010012 displaystyle 00101001 2 todia b 010011002 displaystyle 01001100 2 Vikonannya operaciyi vinyatkove abo dlya znachen logichnogo tipu true false zdijsnyuyetsya v riznih movah programuvannya po riznomu Napriklad u Delphi Object Pascal vikoristovuyut vbudovanij operator XOR priklad umova1 xor umova2 U movi C pochinayuchi zi standartu C99 operator nad operandami logichnogo tipu povertaye rezultat zastosuvannya logichnoyi operaciyi XOR U C operator dlya logichnogo tipu bool povertaye rezultat zgidno z opisanimi pravilami dlya inshih zhe tipiv vin diye pobitovo Za nestachi registriv operator XOR mozhna vikoristati dlya obminu znachennyami zminnih Kvantovi obchislennyaU kvantovih komp yuterah analogom operaciyi dodavannya za modulem 2 ye ventil CNOT Div takozhDodavannya Bitovi operaciyi Umovna diz yunkciya Diz yunkciya logika PosilannyaDisjunction 14 lipnya 2010 u Wayback Machine Stanford Encyclopedia of Philosophy angl