8-900-374-94-44
[email protected]
Slide Image
Меню

Xor таблица – Практика применения XOR в программировании / Habr

Команда XOR


Как выучить английский

В наше время любой человек должен знать английский язык. А тем более программист. Потому что довольно большая часть документации существует только на английском. А профессионал не может ждать, пока кто-то переведёт ему документацию. Он должен уметь быстро получать нужную инфорамцию и использовать её, независимо от того, на каком она языке - на английском или на русском... Ссылки на курсы по английскому...

Команда XOR в Ассемблере выполняет операцию исключающего ИЛИ между всеми битами двух операндов. Результат операции XOR записывается в первый операнд. Синтаксис:

XOR ПРИЁМНИК, ИСТОЧНИК

Инструкция XOR всегда сбрасывает флаги CF и OF, а также (в зависимости от результата) изменяет флаги SF, ZF и PF. Значение флага AF может быть любым - оно не зависит от результата операции.

ПРИЁМНИК может быть одним из следующих:

  • Область памяти (MEM)
  • Регистр общего назначения (REG)

ИСТОЧНИК может быть одним из следующих:

  • Область памяти (MEM)
  • Регистр общего назначения (REG)
  • Непосредственное значение - константа (IMM)

С учётом ограничений, которые были описаны выше, комбинации ПРИЁМНИК-ИСТОЧНИК могут быть следующими:


REG,		MEM
MEM,		REG
REG,		REG
MEM,		IMM
REG,		IMM

Операция исключающего ИЛИ

При выполнении операции исключающего ИЛИ значение результата будет равно 1, если сравниваемые биты отличаются (не равны). Если же сравниваемые биты имеют одинаковое значение, то результат будет равен 0.

Потому эта операция и называется исключающей. Она исключает из сравнения одинаковые биты, а с неодинаковыми выполняет операцию логического ИЛИ.

Но, так как любая пара неодинаковых битов это 0 и 1, то операция логического ИЛИ в результате даст 1.

Таблица истинности исключающего ИЛИ

Таблица истинности XOR приведена ниже:


0     XOR     0     =     0
0     XOR     1     =     1
1     XOR     0     =     1
1     XOR     1     =     0

Особенности операции XOR

Операция XOR обладает свойством реверсивности. Если её выполнить дважды с одним и тем же операндом, то значение результата инвертируется. То есть если два раза выполнить эту операцию между битами X и Y, то в конечном результате мы получим исходное значение бита Х.


0     XOR     0     =     0     XOR     0     =     0
0     XOR     1     =     1     XOR     1     =     0
1     XOR     0     =     1     XOR     0     =     1
1     XOR     1     =     0     XOR     1     =     1

Это свойство можно использовать, например, для простейшего шифрования данных (об этом как-нибудь в другой раз).

Проверка флага чётности после операции XOR

Команда XOR работает с 8-, 16- и 32-разрядными операциями.

Иногда есть необходимость после выполнения операции проверить флаг чётности PF, для того, чтобы узнать, какое количество единичных битов (чётное или нечётное) содержится в младшем байте результата (это бывает необходимо не только в случае выполнения операции XOR, но и при выполнении других арифметических и логических операций).

Если флаг чётности установлен, то в результате получилось чётное количество единичных битов. Иначе флаг будет сброшен.

Можно также просто проверить на чётность любое число, не меняя значения результата. Для этого надо выполнить команду XOR с нулевым значением. То есть в ПРИЁМНИКЕ должно быть проверяемое число, а в ИСТОЧНИКЕ должен быть ноль. А затем надо проверить флаг чётности. Пример:


MOV  AL,  10110101b             ;Поместить в AL число с нечётным
                                ;количеством единичных битов (5)
XOR  AL,  0                     ;При этом флаг чётности PF не
                                ;устанавливается (PO)
MOV  AL,  10110111b             ;Поместить в AL число с чётным
                                ;количеством единичных битов (6)
XOR  AL,  0                     ;При этом флаг чётности PF 
                                ;будет установлен (PE)

В отладчиках обычно для обозначения чётного количества единиц в полученном результате используется сокращение PE (Parity Even), а для нечётного - PO (Parity Odd).

Чётность в 16-разрядных словах

Как уже было сказано, флаг чётности устанавливается в зависимости от количества единиц, содержащихся в младшем байте результата. Чтобы проверить чётность 16-разрядного операнда, надо выполнить команду XOR между старшим и младшим байтом этого числа:


MOV  AX,  64C1h         ;0110 0100 1100 0001 - 6 единичных битов 
XOR  AH,  AL            ;Флаг чётности будет установлен

Таким нехитрым способом 16-разрядный операнд разбивается на два байта (2 группы по 8 битов), и при выполнении команды XOR единичные биты, находящиеся в соответствующих разрядах двух 8-разрядных операндов, не будут учитываться. Потому что соответствующий бит результата равен нулю.

Команда XOR удаляет из результата любые пересекающиеся единичные биты двух 8-разрядных операндов и добавляет в результат непересекающиеся единичные биты. То есть чётность полученного нами 8-разрядного числа будет такой же, как и чётность исходного 16-разрядного числа.


0110 0100 1100 0001 - исходное 16-разрядное число

0     XOR     1     =     1
1     XOR     1     =     0
1     XOR     0     =     1
0     XOR     0     =     0
0     XOR     0     =     0
1     XOR     0     =     1
0     XOR     0     =     0
0     XOR     1     =     1

В результате 4 единицы, то есть флаг PF будет установлен

Чётность в 32-разрядных двойных словах

Ну а если надо определить чётность в 32-разрядном числе?

Тогда число разбивается на четыре байта, и поочерёдно с этими байтами выполняется операция исключающего ИЛИ.

Например, мы разбили 32-разрядное число B на четыре байта B0, B1, B2, B3, где В0 - это младший байт.

Тогда для определения чётности числа В нам надо будет использовать следующую формулу:

B0 XOR B1 XOR B2 XOR B3

Но в ассемблере такая запись недопустима. Поэтому придётся немного подумать.

Ну и напоследок о происхождении мнемоники XOR. В английском языке есть слово eXception - исключение. Сокращением от этого слова является буква Х (так повелось). Вы наверняка встречали такое в рекламе или в названии продуктов, производители которых претендуют (ну или думают, что претендуют) на исключительность. Например, Лада XRAY, Sony XPeria и т.п. Так что XOR - это аббревиатура, собранная из двух слов - eXception OR - исключающее ИЛИ.



av-assembler.ru

xor Википедия

График побитового исключающего «или»

Сложе́ние по мо́дулю 2 (исключа́ющее «или», XOR, строгая дизъюнкция, поразрядное дополнение, инвертирование по маске, жегалкинское сложение, логическое вычитание, логи́ческая неравнозна́чность) — булева функция, а также логическая и битовая операция, в случае двух переменных результат выполнения операции истинен тогда и только тогда, когда один из аргументов истинен, а второй — ложен. Для функции трёх (тернарное сложение по модулю 2) и более переменных — результат выполнения операции будет истинным только тогда, когда количество аргументов, равных 1, составляющих текущий набор, — нечётное. Такая операция естественным образом возникает в кольце вычетов по модулю 2, откуда и происходит название операции.

Сложение по модулю 2 называется «исключающим „или“» и «строгой дизъюнкцией» для отличения от «обычного» (неисключающего) логического «или» — нестрогой логической дизъюнкции. В теории множеств сложению по модулю 2 соответствует операция симметрической разности двух множеств.

Обозначения

Запись может быть префиксной («польская запись») — знак операции ставится перед операндами, инфиксной — знак операции ставится между операндами и постфиксной — знак операции ставится после операндов. При числе операндов более 2 префиксная и постфиксная записи экономичнее инфиксной записи. Чаще всего встречаются следующие варианты записи:
⊕2(a,b), a{\displaystyle \oplus _{2}(a,b),~a} ^ b, a⊕b,a⊕2b,a+2b,{\displaystyle b,~a\oplus b,a\oplus _{2}b,a+_{2}b,} a ≠ b, a≠b,(a,b)⊕2,a XOR b{\displaystyle a\neq b,(a,b)\oplus _{2},a~XOR~b}

В юникоде есть символы для сложения по модулю 2: XOR — U+22BB (⊻), CIRCLED PLUS — U+2295 (⊕) и PLUS SIGN WITH SUCSCRIPT TWO — U+2A27 (⨧), а также символ для суммы по модулю 2: MODULO TWO SUM — U+2A0A (⨊).

Свойства

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

В булевой алгебре сложение по модулю 2 — это функция двух, трёх и более переменных (они же — операнды операции, они же — аргументы функции). Переменные могут принимать значения из множества {0,1}{\displaystyle \{0,1\}}. Результат также принадлежит множеству {0,1}{\displaystyle \{0,1\}}. Вычисление результата производится по простому правилу, либо по таблице истинности. Вместо значений 0,1{\displaystyle 0,1} может использоваться любая другая пара подходящих символов, например false,true{\displaystyle false,true} или F,T{\displaystyle F,T} или «ложь», «истина», но при этом необходимо доопределять старшинство, например, true>false{\displaystyle true>false}.

Таблицы истинности:

a{\displaystyle a} b{\displaystyle b} a⊕b{\displaystyle a\oplus b}
0 0 0
1 0 1
0 1 1
1 1 0

Правило: результат равен 0{\displaystyle 0}, если оба операнда равны; во всех остальных случаях результат равен 1{\displaystyle 1}.

a{\displaystyle a} b{\displaystyle b} c{\displaystyle c} a⊕b⊕c{\displaystyle a\oplus b\oplus c}
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

Правило: результат равен 0{\displaystyle 0}, если нет операндов, равных 1{\displaystyle 1}, либо их чётное количество.

Программирование

В языках C/C++, Java, C#, Ruby, PHP, JavaScript, Python и т. д. битовая операция поразрядного дополнения обозначается символом «^», в языках Паскаль, Delphi, Ada, Visual Basic — зарезервированным словом xor, в языке ассемблера — одноимённой логической командой. При этом сложение по модулю 2 выполняется для всех битов левого и правого операнда попарно. Например,

если

a=011001012{\displaystyle a=01100101_{2}}

b=001010012{\displaystyle b=00101001_{2}}

то

a ^b=010011002{\displaystyle a{\hat {\ }}b=01001100_{2}}

Выполнение операции исключающее «или» для значений логического типа (true, false) производится в разных языках программирования по-разному. Например, в Delphi используется встроенный оператор XOR (пример: условие1 xor условие2). В языке C, начиная со стандарта C99, оператор «^» над операндами логического типа возвращает результат применения логической операции XOR. В С++ оператор «^» для логического типа bool возвращает результат согласно описанным правилам, для остальных же типов производится его побитовое применение.

Использование побитового исключающего «или» позволяет поменять местами значения целых переменных без использования дополнительной памяти.

Связь с естественным языком

В естественном языке операция «сложение по модулю» эквивалентна двум выражениям:

  1. «результат истинен (равен 1), если A не равно B (A≠B)»;
  2. «если A не равно B (A≠B), то истина (1)».

Часто указывают на сходство между сложением по модулю 2 и конструкцией «либо … либо …» в естественном языке. Составное утверждение «либо A, либо B» считается истинным, когда истинно либо A, либо B, но не оба сразу; в противном случае составное утверждение ложно. Это в точности соответствует определению операции в булевой алгебре, если «истину» обозначать как 1{\displaystyle 1}, а «ложь» как 0{\displaystyle 0}.

Эту операцию нередко сравнивают с дизъюнкцией потому, что они очень похожи по свойствам, и обе имеют сходство с союзом «или» в повседневной речи. Сравните правила для этих операций:

  1. A∨B{\displaystyle A\lor B} истинно, если истинно A{\displaystyle A} или B{\displaystyle B}, или оба сразу («хотя бы один из двух»).
  2. A⊕B{\displaystyle A\oplus B} истинно, если истинно A{\displaystyle A} или B{\displaystyle B}, но не оба сразу («только один из двух»).

Операция ⊕{\displaystyle \oplus } исключает последний вариант («оба сразу») и по этой причине называется исключающим «ИЛИ». Операция ∨{\displaystyle \lor } включает последний вариант («оба сразу») и по этой причине иногда называется включающим «ИЛИ». Неоднозначность естественного языка заключается в том, что союз «или» может применяться в обоих случаях.

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

В квантовых компьютерах аналог операции сложения по модулю 2 — вентиль CNOT.

Ссылки

wikiredia.ru

XOR - это... Что такое XOR?

Сложе́ние по модулю 2 (исключа́ющее «ИЛИ», XOR, «сумма по модулю 2») — ло­ги­чес­кая опе­ра­ция, по сво­ему при­ме­не­нию мак­си­маль­но при­бли­жен­ная к грам­ма­ти­чес­кой кон­струк­ции «либо … либо …».

Это бинарная инфиксная опе­ра­ция, то есть она имеет два опе­ранда и ста­вит­ся между ними. Чаще всего встре­ча­ют­ся сле­ду­ю­щие ва­ри­анты за­пи­си:
^ .

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

В булевой алгебре сложение по модулю 2 — это функция двух переменных (они же — операнды операции). Переменные могут принимать значения из множества . Результат также принадлежит множеству . Вычисление результата производится по простому правилу, либо по таблице истинности. Вместо значений может использоваться любая другая пара подходящих символов, например или или «ложь», «истина».

Правило: результат равен , если оба операнда равны; во всех остальных случаях результат равен .

Таблица истинности:

Программирование

В языках C/C++ (а также Java, C#, Ruby, PHP, JavaScript и т. д.) эта операция обозначается символом «^», в языках Паскаль, Delphi, Ada - зарезервированным словом XOR, в языке ассемблера - одноименной логической командой. Сложение по модулю 2 выполняется для всех битов левого и правого операнда попарно. Например,

если
a =
b =
то
a ^ b =

Выполнение операции XOR для значений логического типа (true, false) производится в разных языках программирования по-разному. Например в Delphi используется встроенный оператор XOR (пример: condition1 xor condition2). В языке C, начиная со стандарта С++ оператор «^» для логического типа bool возвращает результат согласно описанным правилам, для остальных же типов проихводится его побитовое применение. Перегрузка для стандартных типов невозможна, но операцию XOR над ними можно реализовать, исходя из принципа "исключающего ИЛИ". Выглядит это так:

(condition1 || condition2) && (condition1 != condition2)

(при этом нет разницы, применяются ли побитовые операторы & и |, или же логические && и ||)

Связь с естественным языком

Часто указывают на сходство между сложением по модулю 2 и конструкцией «либо … либо …» в естественном языке. Составное утверждение «либо A, либо B» считается истинным, когда истинно либо A, либо B, но не оба сразу; в противном случае составное утверждение ложно. Это в точности соответствует определению операции в булевой алгебре, если «истину» обозначать как 1, а «ложь» как 0.

Эту операцию нередко сравнивают с дизъюнкцией потому, что они очень похожи по свойствам, и обе имеют сходство с союзом «или» в повседневной речи. Сравните правила для этих операций:

  1. истинно, если истинно или , или оба сразу.
  2. истинно, если истинно или , но не оба сразу.

Операция исключает последний вариант («оба сразу») и по этой причине называется исключающим «ИЛИ». Операция включает последний вариант («оба сразу») и по этой причине иногда называется включающим «ИЛИ». Неоднозначность естественного языка заключается в том, что союз «или» может применяться в обоих случаях.

См. также

Wikimedia Foundation. 2010.

dic.academic.ru

Магия исключающего ИЛИ

Вступление

В математике обычное ИЛИ (включающее, OR) встречается гораздо чаще исключающего (также называемого XOR).

Например, когда Вы пишете выражение pVq, которое читается ”p ИЛИ q”, это так называемое включающее ИЛИ. В этом случае это выражение ИСТИНА (true), если p = ИСТИНА или q = ИСТИНА, или и p = ИСТИНА и q = ИСТИНА.

Включающее ИЛИ используется в обычном понимании операции ИЛИ (OR), оно используется чаще в логике, нежели исключающее ИЛИ (XOR).


Зачастую мы используем логику исключающего ИЛИ в предложениях. Например, если человек говорит: «Этим летом я поеду в Лондон или в Париж», он таким образом говорит нам, что хочет поехать либо в Лондон, либо в Париж, но не в оба. Даже если его заявление не кажется нам неверным,если он съездит в оба эти города, скорее всего иметься в ввиду будет поездка только в один из этих городов.

 

Вы можете подумать, что XOR не является интересным оператором. Он похож на OR, почему он должен быть интереснее чем OR?

Но это так.

Сначала приведём таблицу истинности операции XOR для булевых переменных:

x

y

x(+)y

false

false

false

true

false

true

false

true

true

true

true

false

 

 

Различные видения XOR

Мы можем увидеть XOR с различных сторон.

Предположим, что p и q — булевы переменные (переменные, которые могут принимать два взаимоисключающих значения (0 или 1, либо ИСТИНА И НЕИСТИНА, либо true и false)).

Также предположим, что p1, p2, p3pn – булевы переменные.

Обозначим (+) операцию XOR (обозначается плюсом в кружочке). Тут мы имеем ввиду операцию XOR над булевыми переменными,а не побитовую операцию XOR, речь о побитовой XOR пойдёт немного дальше.

Для операций над булевыми переменными мы увидим, что:

  • p(+)q = true, если ТОЛЬКО ОДНА из переменных p и q равна true, это общепринятое определение XOR;

  • p1(+)p2(+)...(+)pn = true, если число переменных со значением true является нечётным, или равно false

wow-only.ru

Проект "логика для чайников". Параграф 26.

Простейшие логические операции

Простейшие логические операции относятся к двузначной логике. Их 4 штуки: “НЕ”, “И”, “ИЛИ”, “XOR”. Также для обозначения этих операций используют разные значки (“~”, “&” и т.п.).

При записи логических формул вместо слов “истина” и “ложь” обычно используют стандартные международные обозначения:
Вместо “истина” пишут: true, T, t, 1.
Вместо “ложь” пишут: false, F, f, 0.

“НЕ”

Операция “НЕ” преобразует истину в ложь, а ложь в истину:

НЕ true = false
НЕ false = true

У этой операции бывают разные другие названия: “логическое НЕ”, “отрицание”, “логическое отрицание”, “инверсия”, “логическая инверсия”. Для международных обозначений вместо “НЕ” пишут “NOT”.

В естественном языке этой операции соответствует добавление слов “неправда, что...” в начале высказывания. Например:

“Сурков должен мне денег”. (1)

Применение операции “НЕ” к высказыванию (1):

“Неправда, что Сурков должен мне денег”. (2)

Если высказывание (1) ложно, то высказывание (2) истинно. Если высказывание (2) ложно, то высказывание (1) истинно.

Нетрудно понять, что двойное применение “НЕ” возвращает нас к прежней истинности.

“Неправда, что неправда, что Сурков должен мне денег”. (3)

Истинность высказывания (3) всегда совпадает с истинностью высказывания (1).

“И”

Операция “И” применяется к двум высказываниям. Ее результат “истина”, только если оба высказывания истинны (а иначе “ложь”):

false И false = false
false И true = false
true И false = false
true И true = true

У этой операции бывают разные другие названия: “логическое И”, “конъюнкция”, “логическое умножение”. Для международных обозначений вместо “И” пишут “AND”.

В естественном языке этой операции соответствует вставка союза “и” между высказываниями. Например:

“Сурков должен мне денег”. (1)
“Петров должен мне денег”. (2)

Применение операции “И” к высказываниям (1) и (2):

“Сурков должен мне денег, и Петров должен мне денег”. (3)

Эту фразу можно сократить, сохранив прежний смысл:

“Сурков и Петров должны мне денег”. (3)

Высказывание (3) истинно только тогда, когда истинны оба высказывания: (1) и (2). Если хотя бы одно из них ложно, то результат тоже ложен. Если оба ложны – тоже.

То есть, если Петров мне денег не задолжал, а задолжал только Сурков, тогда высказывание (3) не будет “полуправдой” или “полуложью”, а будет просто ложью.

“ИЛИ”

Операция “ИЛИ” применяется к двум высказываниям. Ее результат “истина”, если хотя бы одно высказывание истинно (а иначе “ложь”):

false ИЛИ false = false
false ИЛИ true = true
true ИЛИ false = true
true ИЛИ true = true

У этой операции бывают разные другие названия: “логическое ИЛИ”, “включающее ИЛИ”, “дизъюнкция”, “логическое сложение”. Для международных обозначений вместо “ИЛИ” пишут “OR”.
В естественном языке этой операции соответствует вставка союза “или” между высказываниями, но... не всегда (см. ниже об операции “XOR”). Например:

“Я хочу попить”. (1)
“Я хочу поесть”. (2)

Применение операции “ИЛИ” к высказываниям (1) и (2):

“Я хочу попить, или я хочу поесть”. (3)

По-русски звучит правильно, но коряво, и эту фразу можно сократить, сохранив прежний смысл:

“Я хочу попить или поесть ”. (3)

Высказывание (3) истинно тогда, когда истинно хотя бы одно из высказываний (1) и (2), а можно оба. Если оба высказывания ложны, то результат тоже ложен.

То есть, если я хочу есть, но не пить, тогда высказывание (3) истинно. Если я не прочь и поесть, и попить, выказывание (3) тоже истинно. Ложно оно тогда, когдя я не хочу ни того, ни другого.

“XOR”

Операция “XOR” применяется к двум высказываниям. Ее результат “истина”, если ровно одно из высказываний истинно (а иначе “ложь”):

false XOR false = false
false XOR true = true
true XOR false = true
true XOR true = false

У этой операции бывают разные другие названия: “исключающее ИЛИ”, “сложение по модулю 2”, “логическое сложение по модулю 2”. “XOR” – это международное обозначение, общепринятого “русского” аналога нет.

В естественном языке этой операции соответствует вставка союза “или” между высказываниями – так же, как в случае с операцией “ИЛИ”. Например:

“Я собираюсь просить прибавки к зарплате”. (1)
“Я попытаюсь сэкономить ”. (2)

Применение операции “XOR” к высказываниям (1) и (2):

“Я собираюсь просить прибавки к зарплате или я попытаюсь сэкономить”. (3)

Сокращенно:

“Я собираюсь просить прибавки к зарплате или попытаюсь сэкономить”. (3)

Высказывание (3) истинно тогда, когда истинно ровно одно из высказываний (1) и (2). Если я не собираюсь ни просить прибавки, ни экономить, тогда фраза ложна. Также, я имел в виду, что не собираюсь делать и то, и другое одновременно.

Обратите внимание на разницу между операциями “ИЛИ” и “XOR”. Она заключается только в последнем правиле:

true ИЛИ true = true
true XOR true = false

В естественном языке обе операции изображаются одним и тем же союзом “или”. Это – пример неоднозначности естественного языка. Если помните, омонимы и многозначные слова могут иметь больше одного значения. Союз “или” именно такой: он имеет два возможных значения. Первое выражается логической операцией “ИЛИ”, второе – логической операцией “XOR”.

В английском языке существуют те же проблемы: союз “or” имеет те же два значения. А вот древним римлянам было проще, так как в латыни есть два разных слова: “vel” (операция “ИЛИ”) и “aut” (операция “XOR”).

Поскольку разница между операциями “ИЛИ” и “XOR” невелика (всего одно последнее правило), то иногда эта разница не имеет значения. Иногда о том, что имеется в виду, можно догадаться по интонации, или по контексту. Иногда определить точный смысл так и не удается.

psilogic.livejournal.com

Логические элементы

В данной статье расскажем что такое логические элементы, рассмотрим самые простые логические элементы.

Любое цифровое устройство — персональный компьютер, или современная система автоматики состоит из цифровых интегральных микросхем (ИМС), которые выполняют определённые сложные функции. Но для выполнения одной сложной функции необходимо выполнить несколько простейших функций. Например, сложение двух двоичных чисел размером в один байт происходит внутри цифровой микросхемы называемой «процессор» и выполняется в несколько этапов большим количеством

логических элементов находящихся внутри процессора. Двоичные числа сначала запоминаются в буферной памяти процессора, потом переписываются в специальные «главные» регистры процессора, после выполняется их сложение, запоминание результата в другом регистре, и лишь после результат сложения выводится через буферную память из процессора на другие устройства компьютера.

Процессор состоит из функциональных узлов: интерфейсов ввода-вывода, ячеек памяти – буферных регистров и «аккумуляторов», сумматоров, регистров сдвига и т.д. Эти функциональные узлы состоят из простейших логических элементов, которые, в свою очередь состоят из полупроводниковых транзисторов, диодов и резисторов. При конструировании простых триггерных и других электронных импульсных схем, сложные процессоры не применить, а использовать транзисторные каскады – «прошлый век». Тут и приходят на помощь – логические элементы.

Логические элементы, это простейшие «кубики», составные части цифровой микросхемы, выполняющие определённые логические функции. При этом, цифровая микросхема может содержать в себе от одного, до нескольких единиц, десятков, …и до нескольких сотен тысяч логических элементов в зависимости от степени интеграции. Для того, чтобы разобраться, что такое логические элементы, мы будем рассматривать самые простейшие из них. А потом, наращивая знания, разберёмся и с более сложными цифровыми элементами.


Начнём с того, что единица цифровой информации это «один бит». Он может принимать два логических состояния – логический ноль «0», когда напряжение равно нулю (низкий уровень), и состояние логической единицы «1», когда напряжение равно напряжению питания микросхемы (высокий уровень).

Поскольку простейший логический элемент это электронное устройство, то это означает, что у него есть входы (входные выводы) и выходы (выходные выводы). И входов и выходов может быть один, а может быть и больше.

Для того, чтобы понять принципы работы простейших логических элементов используется «таблица истинности». Кроме того, для понимания принципов работы логических элементов, входы, в зависимости от их количества обозначают: Х1, Х2, … ХN, а выходы: Y1, Y2, … YN.

Функции, выполняемые простейшими логическими элементами, имеют названия. Как правило, впереди функции ставится цифра, обозначающая количество входов. Простейшие логические элементы всегда имеют лишь один выход.

 

 

Рассмотрим простейшие логические элементы

 

«НЕ» (NOT) – функция отрицания (инверсии сигнала). Потому его чаще называют — «инвертор». Графически, инверсия обозначается пустым кружочком вокруг вывода элемента (микросхемы). Обычно кружок инверсии ставится у выхода, но в более сложных логических элементах, он может стоять и на входе. Графическое обозначение элемента «НЕ» и его таблица истинности представлены на рисунке слева.

У элемента «НЕ» всегда один вход и один выход. По таблице истинности следует, что при наличии на входе элемента логического нуля, на выходе будет логическая единица. И наоборот, при наличии на входе логической единицы, на выходе будет логический ноль. Цифра «1» внутри прямоугольника обозначает функцию «ИЛИ», её принято рисовать и внутри прямоугольника элемента «НЕ», но это ровным счётом ничего абсолютно не значит.

Обозначение D1.1 означает, что D — цифровой логический элемент, 1 (первая) — номер микросхемы в общей схеме, 1 (вторая) — номер элемента в микросхеме. Точно также расшифровываются и другие логические элементы.

Часто, чтобы отличить цифровые микросхемы от аналоговых микросхем, применяют обозначения из двух букв: DD – цифровая микросхема, DA – аналоговая микросхема. В последующем, мы не будем заострять внимание на это обозначение, а вернёмся лишь тогда, когда это будет необходимым.

Самой распространённой микросхемой «транзисторно-транзисторной логики» (ТТЛ), выполняющей функцию «НЕ», является интегральная микросхема (ИМС) К155ЛН1, внутри которой имеется шесть элементов «НЕ». Нумерация выводов этой микросхемы показана справа.


«И» (AND) – функция сложения (если на всех входах единица, то на выходе будет единица, в противном случае, если хотя бы на одном входе ноль, то и на выходе всегда будет ноль). В алгебре-логике элемент «И» называют «конъюнктор». Графическое обозначение элемента «2И» и его таблица истинности представлены слева.

Название элемента «2И» обозначает, что у него два входа, и он выполняет функцию «И». На схеме внутри прямоугольника микросхемы рисуется значок «&», что на английском языке означает «AND» (в переводе на русский — И).

По таблице истинности следует, что на выходе элемента «И» будет логическая единица только в одном случае — когда на обоих входах будет логическая единица. Если хотя бы на одном входе ноль, то и на выходе будет ноль.

Самой распространённой микросхемой «транзисторно-транзисторной логики» (ТТЛ), выполняющей функцию «2И», является интегральная микросхема (ИМС) К155ЛИ1, внутри которой имеется четыре элемента «2И». Нумерация выводов этой микросхемы показана справа.

Для того, чтобы вам было понятнее что такое «2И», «3И», «4И», и т.д., приведу графическое обозначение и таблицу истинности элемента «3И».

По таблице истинности следует, что на выходе элемента «3И» будет логическая единица только в том случае — когда на всех трёх входах будет логическая единица. Если хотя бы на одном входе будет логический ноль, то и на выходе элемента также будет логический ноль. Самой распространённой микросхемой ТТЛ, выполняющей функцию «3И», является микросхема К555ЛИ3, внутри которой имеется три элемента «3И».


«И-НЕ» (NAND) – функция сложения с отрицанием (если на всех входах единица, то на выходе будет ноль, в противном случае на выходе всегда будет единица). Графическое обозначение элемента «2И-НЕ» и его таблица истинности приведены слева.

По таблице истинности следует, что на выходе элемента «2И-НЕ» будет логический ноль только в том случае, если на обоих входах будет логическая единица. Если хотя бы на одном входе ноль, то на выходе будет единица.

Самой распространённой микросхемой ТТЛ, выполняющей функцию «2И-НЕ», является ИМС К155ЛА3, а микросхемами КМОП (комплементарный металлооксидный полупроводник) – ИМС К561ЛА7 и К176ЛА7, внутри которых имеется четыре элемента «2И-НЕ». Нумерация выводов этих микросхем показана справа.

Сравнив таблицы истинности элемента «2И-НЕ» и элемента «2И» можно догадаться об эквивалентности схем:

Добавив к элементу «2И» элемент «НЕ» мы получили элемент «2И-НЕ». Так можно собрать схему, если нам необходим элемент «2И-НЕ», а у нас в распоряжении имеются только элементы «2И» и «НЕ».

И наоборот:

Добавив к элементу «2И-НЕ» элемент «НЕ» мы получили элемент «2И». Так можно собрать схему, если нам необходим элемент «2И», а у нас в распоряжении имеются только элементы «2И-НЕ» и «НЕ».

Аналогичным образом, путём соединения входов элемента «2И-НЕ» мы можем получить элемент «НЕ»:

Обратите внимание, что было введено новое в обозначении элементов – дефис, разделяющий правую и левую часть в названии «2И-НЕ». Этот дефис непременный атрибут при инверсии на выходе (функции «НЕ»).


«ИЛИ» (OR) – функция выбора (если хотя бы на одном из входов – единица, то на выходе – единица, в противном случае на выходе всегда будет ноль). В алгебре-логике, элемент «ИЛИ» называют «дизъюнктор». Графическое обозначение элемента «2ИЛИ» и его таблица истинности приведены слева.

Самой распространённой микросхемой ТТЛ, выполняющей функцию «2ИЛИ», является ИМС К155ЛЛ1, внутри которой имеется четыре элемента «2ИЛИ». Нумерация выводов этой микросхемы показана справа.

Предположим, что нам в схеме необходим элемент, выполняющий функцию «2ИЛИ», но у нас есть в распоряжении только элементы «НЕ» и «2И-НЕ», тогда можно собрать схему, которая будет выполнять функцию «2ИЛИ»:


«ИЛИ-НЕ» (NOR) – функция выбора (если хотя бы на одном из входов – единица, то на выходе – ноль, в противном случае на выходе всегда будет единица). Как вы поняли, элемент «ИЛИ-НЕ» выполняет функцию «ИЛИ», а потом инвертирует его функцией «НЕ».

Графическое обозначение элемента «2ИЛИ-НЕ» и его таблица истинности приведена слева.

Самой распространённой микросхемой ТТЛ, выполняющей функцию «2ИЛИ-НЕ», является ИМС К155ЛЕ1, а микросхемами КМОП – К561ЛЕ5 и К176ЛЕ5, внутри которых имеется четыре элемента «2ИЛИ-НЕ». Нумерация выводов этих микросхем показана справа.

Предположим, что нам в схеме необходим элемент, выполняющий функцию «2ИЛИ-НЕ», но у нас есть в распоряжении только элементы «НЕ» и «2И-НЕ», тогда можно собрать следующую схему, которая будет выполнять функцию «2ИЛИ-НЕ»:

По аналогии с элементом «2И-НЕ», путём соединения входов элемента «2ИЛИ-НЕ» мы можем получить элемент «НЕ»:


«Исключающее ИЛИ» (XOR) — функция неравенства двух входов (если на обоих входах элемента одинаковые сигналы, то на выходе – ноль, в противном случае на выходе всегда будет единица). Операция, которую он выполняет, часто называют «сложение по модулю 2».

Графическое обозначение элемента «Исключающее ИЛИ» и его таблица истинности приведены слева.

Самой распространённой микросхемой ТТЛ, выполняющей функцию «Исключающее ИЛИ», является ИМС К155ЛП5, а микросхемами КМОП – К561ЛП2 и К176ЛП2, внутри которых имеется четыре элемента «Исключающее ИЛИ». Нумерация выводов этих микросхем показана справа.

Предположим, что нам в схеме необходим элемент, выполняющий функцию «Исключающее ИЛИ», но у нас есть в распоряжении только элементы «2И-НЕ», тогда можно собрать следующую схему, которая будет выполнять функцию «Исключающее ИЛИ»:


В цифровой схемотехнике процессоров главная функция — «Суммирование двоичных чисел», поэтому сложный логический элемент – «Сумматор» является неотъемлемой частью арифметико-логического устройства любого, без исключения процессора. Составной частью сумматора является набор логических элементов, выполняющих функцию «Исключающее ИЛИ с переносом остатка». Что это такое? В соответствии с наукой «Информатика», результатом сложения двух двоичных чисел, две единицы одного разряда дают ноль, при этом формируется «единица переноса» в следующий старший разряд, который участвует в операции суммирования в старшем разряде. Для этого в схему добавляется ещё один вывод «переноса» — «Р».

Графическое обозначение элемента «Исключающее ИЛИ с переносом» и его таблица истинности представлена слева.

Такая функция сложения одноразрядных чисел в простых устройствах обычно не используется, и как правило, интегрирована в состав одной микросхемы – сумматора, с минимальным количеством разрядов – четыре, для сложения четырехбитных чисел. По причине слабого спроса, промышленность таких логических элементов не выпускает. Поэтому, в случае необходимости, функцию «Исключающее ИЛИ с переносом» можно собрать по следующей схеме из элементов «2И-НЕ» и «2ИЛИ-НЕ», которая активно применяется как внутри простых сумматоров, так и во всех сложных процессорах (в том числе Pentium, Intel-Core, AMD и других, которые появятся в будущем):


Вышеперечисленные логические элементы выполняют статические функции, а на основе них строятся более сложные статические и динамические элементы (устройства): триггеры, регистры, счётчики, шифраторы, дешифраторы, сумматоры, мультиплексоры.

meanders.ru

Исключающее или - это... Что такое Исключающее или?

Сложе́ние по модулю 2 (исключа́ющее «ИЛИ», XOR, «сумма по модулю 2») — ло­ги­чес­кая опе­ра­ция, по сво­ему при­ме­не­нию мак­си­маль­но при­бли­жен­ная к грам­ма­ти­чес­кой кон­струк­ции «либо … либо …».

Это бинарная инфиксная опе­ра­ция, то есть она имеет два опе­ранда и ста­вит­ся между ними. Чаще всего встре­ча­ют­ся сле­ду­ю­щие ва­ри­анты за­пи­си:
^ .

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

В булевой алгебре сложение по модулю 2 — это функция двух переменных (они же — операнды операции). Переменные могут принимать значения из множества . Результат также принадлежит множеству . Вычисление результата производится по простому правилу, либо по таблице истинности. Вместо значений может использоваться любая другая пара подходящих символов, например или или «ложь», «истина».

Правило: результат равен , если оба операнда равны; во всех остальных случаях результат равен .

Таблица истинности:

Программирование

В языках C/C++ (а также Java, C#, Ruby, PHP, JavaScript и т. д.) эта операция обозначается символом «^», в языках Паскаль, Delphi, Ada - зарезервированным словом XOR, в языке ассемблера - одноименной логической командой. Сложение по модулю 2 выполняется для всех битов левого и правого операнда попарно. Например,

если
a =
b =
то
a ^ b =

Выполнение операции XOR для значений логического типа (true, false) производится в разных языках программирования по-разному. Например в Delphi используется встроенный оператор XOR (пример: condition1 xor condition2). В языке C, начиная со стандарта С++ оператор «^» для логического типа bool возвращает результат согласно описанным правилам, для остальных же типов проихводится его побитовое применение. Перегрузка для стандартных типов невозможна, но операцию XOR над ними можно реализовать, исходя из принципа "исключающего ИЛИ". Выглядит это так:

(condition1 || condition2) && (condition1 != condition2)

(при этом нет разницы, применяются ли побитовые операторы & и |, или же логические && и ||)

Связь с естественным языком

Часто указывают на сходство между сложением по модулю 2 и конструкцией «либо … либо …» в естественном языке. Составное утверждение «либо A, либо B» считается истинным, когда истинно либо A, либо B, но не оба сразу; в противном случае составное утверждение ложно. Это в точности соответствует определению операции в булевой алгебре, если «истину» обозначать как 1, а «ложь» как 0.

Эту операцию нередко сравнивают с дизъюнкцией потому, что они очень похожи по свойствам, и обе имеют сходство с союзом «или» в повседневной речи. Сравните правила для этих операций:

  1. истинно, если истинно или , или оба сразу.
  2. истинно, если истинно или , но не оба сразу.

Операция исключает последний вариант («оба сразу») и по этой причине называется исключающим «ИЛИ». Операция включает последний вариант («оба сразу») и по этой причине иногда называется включающим «ИЛИ». Неоднозначность естественного языка заключается в том, что союз «или» может применяться в обоих случаях.

См. также

Wikimedia Foundation. 2010.

dic.academic.ru

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *