www.wikidata.uk-ua.nina.az

Виключна диз юнкція Виняткова диз юнкція також операція XOR від англ eXclusive OR додавання за модулем два логічна та бі

Виключна диз'юнкція

Виняткова диз'юнкція, також операція XOR (від англ. eXclusive OR), додавання за модулем два — логічна та бітова операція, що набуває значення «істина» тоді й лише тоді, коли значення «істина» має суто один з її операндів. Виняткова диз'юнкція є запереченням логічної еквівалентності. У випадку двох змінних результат виконання операції є істинним тоді й тільки тоді, якщо лише один з аргументів є істинним. Для функції трьох і більше змінних результат виконання операції буде істинним тільки тоді, коли аргументів, рівних 1, на заданому наборі буде непарна кількість. Така операція природним чином виникає в кільці лишків за модулем 2, звідки й походить назва операції.

Рис. 1 Графік побітового виняткового «або»

Додавання за модулем 2 слід відрізняти від простого додавання булевих операндів, яке відповідає звичайному логічному «або», тобто логічній диз'юнкції.

Відповідною операцією в теорії множин є симетрична різниця множин істинності операндів.

Позначення

Запис може бути префіксний («польський запис») — знак операції ставиться перед операндами, інфіксний — знак операції ставиться між операндами і постфіксний — знак операції ставиться після операндів. За кількості операндів більше двох префіксний та постфіксний запис економніші за інфіксний. Найчастіше трапляються такі варіанти запису:


^ a ≠ b,

У таблиці символів Юнікод є символ для додавання за модулем 2 (CIRCLED PLUS) — U +2295 ( ⊕ ).

Виняткову диз'юнкцію деколи задають через інші логічні операції, наприклад:

Булева алгебра

У булевій алгебрі додавання за модулем 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

Визначення

Діаграма Венна для операції

Таблиця істинності виглядає таким чином:

хибність хибність хибність
хибність істина істина
істина хибність істина
істина істина хибність

Результат застосування виняткової диз'юнкції такий самий, як і від додавання за модулем 2. Тому й саму операцію часто називають додаванням за модулем 2.

Виняткова диз'юнкція є також запереченням еквівалентності, тобто

Відповідною операцією в теорії множин є симетрична різниця множин.

Властивості

Абелева група

  • елемент 0 є нейтральним:
  • кожен елемент є обернений сам до себе:

Таким чином є абелевою групою. Разом із операцією також утворюється поле Галуа .

Інші властивості

Функціональна повнота

Множина операцій є функціонально повною:

Виняткова диз'юнкція у природних мовах

Виняткові диз'юнкції найкраще відповідає український вислів «або …, або …». Твердження або А, або В є справедливим, коли справедливе А чи В, але не обоє водночас.

У природній мові операція «складання за модулем» еквівалентна двом виразам:

  1. «Результат істинний (дорівнює 1), якщо A не дорівнює B (A ≠ B)»;
  2. «Якщо A не дорівнює B (A ≠ B), то істина (1)».

На схожість між додаванням за модулем 2 і конструкцією «або …, або …» в природній мові часто вказують. Це точно відповідає визначенню операції в булевій алгебрі, якщо «істину» позначати як , а «хибність» як .

Цю операцію нерідко порівнюють із диз'юнкцією, тому що вони дуже схожі за властивостями, і обидві мають схожість зі сполучником «або» у повсякденній мові. Порівняйте правила для цих операцій:

  1. істинне, якщо істинне або , або обидва відразу.
  2. істинне, якщо істинне або , але не обидва відразу.

Операція не допускає останнього варіанту («обидва відразу»); саме тому її називають винятковим, ексклюзивним «АБО». Операція допускає останній варіант («обидва відразу»), тож іноді її називають звичним, інклюзивним «АБО». Неоднозначність природної мови полягає в тому, що сполучник «або» застосовують в обох випадках.

Альтернативні символи

Символ, використовуваний для виняткової диз'юнкції, варіюється від однієї області застосування до іншої. Окрім абревіатури «XOR», можуть траплятися:

  • Знак плюс (+). Це має сенс, тому що математично винятковій диз'юнкції відповідає додавання за модулем 2, яке має наступну таблицю:
Додавання за модулем 2
0 0 0
0 1 1
1 0 1
1 1 0
  • Знаком плюс, зміненим певним чином, наприклад, взятим в коло (). Це викликає заперечення: цей же символ вже використовують у математиці для прямої суми алгебраїчних структур.
  • Префікс J, як в Jpq.
  • Символ диз'юнкції (), який певним чином змінюють: із підкресленням () або з точкою вгорі ().
  • У деяких мовах програмування, таких як C, 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. У C++ оператор «^» для логічного типу bool повертає результат згідно з описаними правилами, для інших же типів він діє побітово.

За нестачі регістрів оператор XOR можна використати для обміну значеннями змінних.

Квантові обчислення

У квантових комп'ютерах аналогом операції додавання за модулем 2 є вентиль CNOT.

Див. також

Посилання

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
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 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 Zmist 1 Poznachennya 2 Buleva algebra 3 Viznachennya 4 Vlastivosti 4 1 Abeleva grupa 5 Inshi vlastivosti 6 Funkcionalna povnota 7 Vinyatkova diz yunkciya u prirodnih movah 8 Alternativni simvoli 9 Vinyatkova diz yunkciya u programuvanni 10 Kvantovi obchislennya 11 Div takozh 12 PosilannyaPoznachennya RedaguvatiZapis mozhe buti prefiksnij polskij zapis znak operaciyi stavitsya pered operandami infiksnij znak operaciyi stavitsya mizh operandami i postfiksnij znak operaciyi stavitsya pislya operandiv Za kilkosti operandiv bilshe dvoh prefiksnij ta postfiksnij zapis ekonomnishi za infiksnij Najchastishe traplyayutsya taki varianti zapisu 2 a b a displaystyle oplus 2 a b a b a b a 2 b a 2 b displaystyle b a oplus b a oplus 2 b a 2 b a b a b a b 2 a X O R b displaystyle a neq b a b oplus 2 a XOR b U tablici simvoliv Yunikod ye simvol dlya dodavannya za modulem 2 CIRCLED PLUS U 2295 Vinyatkovu diz yunkciyu dekoli zadayut cherez inshi logichni operaciyi napriklad a b a b displaystyle a oplus b neg a leftrightarrow b a b a b a b displaystyle a oplus b a land neg b lor neg a land b Buleva algebra RedaguvatiU 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 f a l s e t r u e displaystyle false true abo F T displaystyle F T abo hibnist istina ale pri comu neobhidno doviznachiti starshinstvo napriklad t r u e gt f a l s e 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 0 displaystyle 0 0 displaystyle 0 0 displaystyle 0 0 displaystyle 0 1 displaystyle 1 1 displaystyle 1 1 displaystyle 1 0 displaystyle 0 1 displaystyle 1 1 displaystyle 1 1 displaystyle 1 0 displaystyle 0 Pravilo 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 1Viznachennya Redaguvati Diagrama 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 hibnist hibnist hibnisthibnist istina istinaistina hibnist istinaistina istina hibnistRezultat 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 Vlastivosti Redaguvatiasociativnista 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 Redaguvati 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 F 2 displaystyle F 2 Inshi vlastivosti Redaguvatip 1 p p p 1 p q p q p q p q p q p p q p q p p q p q p p q p q p p q p q p p q p q p 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 povnota RedaguvatiMnozhina 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 movah RedaguvatiVinyatkovi 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 simvoli RedaguvatiSimvol 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 programuvanni RedaguvatiU 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 01100101 2 displaystyle 01100101 2 b 00101001 2 displaystyle 00101001 2 todia b 01001100 2 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 obchislennya RedaguvatiU kvantovih komp yuterah analogom operaciyi dodavannya za modulem 2 ye ventil CNOT Div takozh RedaguvatiDodavannya Bitovi operaciyi Umovna diz yunkciya Diz yunkciya logika Posilannya RedaguvatiDisjunction Arhivovano 14 lipnya 2010 u Wayback Machine Stanford Encyclopedia of Philosophy angl Otrimano z https uk wikipedia org w index php title Viklyuchna diz 27yunkciya amp oldid 36043811