Основные логические операции. AND, NOT, OR и XOR (исключающее или)
В этой статье мы поговорим о некоторых битовых операциях. Рассмотрим основные из них: XOR (исключающее ИЛИ), AND (И), NOT (НЕ) а также OR (ИЛИ).
Как известно, минимальной единицей измерения информации является бит, который хранит одно из 2-х значений: 0 (False, ложь) либо 1 (True, истина). Таким образом, битовая ячейка может одновременно находиться лишь в одном из двух возможных состояний.
Для манипуляций с битами используют определённые операции — логические или булевые. Они могут применяться к любому биту, вне зависимости от того, какое у него значение — ноль или единица. Что же, давайте посмотрим на примеры использования трёх основных логических операций.
Логическая операция AND (и)
AND обозначается знаком & .
Оператор AND выполняется с 2-мя битами, возьмём, к примеру, a и b. Результат выполнения операции AND равен 1, если a и b равняются 1. В остальных случаях результат равен 0. Например, с помощью AND вы можете узнать, чётное число или нет.
Посмотрите на таблицу истинности операции AND:
Логическая операция OR (ИЛИ)
Оператор OR также выполняется с 2-мя битами (a и b). Результат равен 0, если a и b равны 0, иначе он равен 1. Смотрим таблицу истинности.
Логическая операция XOR (исключающее ИЛИ)
Оператор XOR обозначается ^ .
XOR выполняется с 2-мя битами (a и b). Результат выполнения операции XOR (исключающее ИЛИ) равен 1, когда один из битов b или a равен 1. В остальных ситуациях результат применения оператора XOR равен 0.
Таблица истинности логической операции для XOR (исключающее ИЛИ) выглядит так:
Используя XOR (исключающее ИЛИ), вы можете поменять значения 2-х переменных одинакового типа данных, не используя временную переменную. А ещё, посредством XOR можно зашифровать текст, например:
Согласен, XOR — далеко не самый надёжный метод шифрования, но это не значит, что его нельзя сделать частью какого-либо шифровального алгоритма.
Логическая операция NOT (НЕ)
Это побитовое отрицание, поэтому выполняется с одним битом и обозначается
Результат зависит от состояния бита. Если он в нулевом состоянии, то итог операции — единица и наоборот. Всё предельно просто.
Эти 4 логические операции следует запомнить в первую очередь, т. к. с их помощью можно получить практически любой возможный результат. Также существуют такие операции, как << (побитовый сдвиг влево) и >> (побитовый сдвиг вправо).
§ 4. Логические операции И и ИЛИ
Логика высказываний позволяет строить составные высказывания. Они создаются из нескольких простых высказываний путем соединения их друг с другом с помощью логических операций НЕ, И, ИЛИ и др.
4.1. Логическая операция И
Определение истинности или ложности составного высказывания зависит от того, являются ли истинными или ложными простые высказывания, входящие в его состав, а также от той логической операции, которая их связывает.
Составное высказывание А И В, образованное в результате объединения двух простых высказываний А и B логической операцией И, истинно тогда и только тогда, когда А и В одновременно истинны (пример 4.1 и пример 4.2).
Операцию И называют логическим умножением. Равенства 1 · 1 = 1, 1 · 0 = 0, 0 · 1 = 0, 0 · 0 = 0, верные для обычного умножения, верны и для логического умножения.
Представим таблицу истинности для логической операции И:
А И В
Если хотя бы одно из простых высказываний, связанных операцией И, будет ложным, то и составное высказывание будет ложным.
Для записи логической операции И используют следующие обозначения: A И B, A AND B, A · B, A * B, A ∧ B, A & B.
4.2. Логическая операция ИЛИ
Составное высказывание А ИЛИ В, образованное в результате объединения двух простых высказываний А и B логической операцией ИЛИ, ложно тогда и только тогда, когда А и В одновременно ложны (пример 4.3).
Другими словами, составное высказывание А ИЛИ В будет истинным, если истинно хотя бы одно из двух составляющих его простых высказываний (пример 4.4).
Таблица истинности для логической операции ИЛИ имеет следующий вид:
Операцию ИЛИ называют логическим сложением. Равенства 1 + 0 = 1, 0 + 1 = 1, 0 + 0 = 0, верные для обычного сложения, верны и для логического сложения.
Для записи логической операции ИЛИ можно использовать следующие выражения: A ИЛИ B, A OR B, A + B, A ∨ B, A | B.
Если в логическом выражении присутствует несколько логических операций, то важно определить порядок их выполнения. Наивысшим приоритетом обладает операция НЕ. Логическая операция И, т. е. логическое умножение, выполняется раньше операции ИЛИ — логического сложения (пример 4.5* и пример 4.6*).
Для изменения порядка выполнения логических операций используют скобки: в этом случае сначала выполняются операции в скобках, а затем — все остальные.
Логические операции И и ИЛИ подчиняются переместительному закону:
A И B = B И A ;
A ИЛИ B = B ИЛИ A .
Чтобы определить значение составного логического выражения, иногда достаточно знать значение только одного простого высказывания.
Так, если в составном высказывании с операцией И значение хотя бы одного простого высказывания является ложным, то и значение составного высказывания будет ложным. Если в составном высказывании с операцией ИЛИ значение хотя бы одного простого будет истинным, то и значение составного высказывания будет истинным (пример 4.7).
Данное высказывание является составным, поскольку оно содержит два простых высказывания:
«Число 456 трехзначное» (высказывание А) и «Число 456 четное» (высказывание В). Высказывания А и В соединены вместе логической операцией И, в результате получено составное высказывание А И B. Высказывание А истинно, высказывание В истинно. Поэтому высказывание А И B истинно: (А И B) = 1.
Пример 4.2. Высказывание А: «Геракл — герой древнегреческой мифологии». Истинно, А = 1.
Высказывание В: «Геракл — сын бога Зевса». Истинно, B = 1.
Высказывание А И В: «Геракл — герой древнегреческой мифологии И сын бога Зевса». Истинно, (А И В) = 1.
Пример 4.3. Проанализируем высказывание «Семиклас-сники изучают философию или астрономию».
Данное составное высказывание образовано из двух простых высказываний: «Семиклассники изучают философию» (высказывание А), «Семиклас-сники изучают астрономию» (высказывание В), которые связаны логической операцией ИЛИ. В результате получилось составное высказывание А ИЛИ B. Высказывание А ложно, высказывание В ложно. Поэтому высказывание А ИЛИ B ложно: (А ИЛИ B) = 0.
Пример 4.4. Высказывание А: «Франциск Скорина — белорусский первопечатник». Истинно, А = 1.
Высказывание В: «Стефан Баторий — турецкий султан». Ложно, B = 0.
Высказывание «Франциск Скорина — белорусский первопечатник, ИЛИ Стефан Баторий — турецкий султан» будет истинным, (А ИЛИ В) = 1.
Пример 4.5*.
Рассмотрим выражение: А ИЛИ B И НЕ С. Распишем по действиям вычисление значения логического выражения:
- 1) D = НЕС;
- 2) E = BИD;
- 3) F = АИЛИE.
Значение высказывания F, полученное в 3-м действии, определит значение исходного логического выражения.
Пример 4.6*.
Пусть высказывание А = 1, B = 0, С = 0. Найдем значение логического выражения: А ИЛИ B И НЕ С.
- 1) D = НЕС = 1;
- 2) E = BИD = 0 И 1 = 0;
- 3) F = АИЛИE = 1 ИЛИ 0 = 1.
Значит, при начальных значениях А = 1, B = 0, С = 0 значение логического выражения А ИЛИ B И НЕ С истинно.
Пример 4.7. Высказывание А: «Прогноз погоды обещает дожди». Высказывание В: «Сейчас на улице идет дождь».
Высказывание А И B будет ложным, если мы увидели, что на улице нет дождя (независимо от того, что обещал прогноз погоды).
1 В каких условиях составное высказывание А И В может быть истинным?
- Если А истинно, а В ложно.
- Если А истинно и В истинно.
- Если А ложно и В истинно.
- Если А ложно, а В истинно.
2 В каких случаях составное высказывание А ИЛИ В может быть ложным?
- Если А истинно и В истинно.
- Если А ложно, а В истинно.
- Если А ложно и В ложно.
- Если А истинно, а В ложно.
- Мяч круглый, ИЛИ Земля плоская.
- Кролики — домашние животные, И баобаб растет в Беловежской пуще.
- Клавиатура — устройство ввода информации, ИЛИ винчестер — устройство вывода информации.
- М. Ю. Лермонтов написал стихотворение «Парус», И И. А. Крылов написал басню «Квартет».
- Сосна — хвойное дерево, И кедр — не хвойное дерево.
- Процессор — устройство обработки информации в компьютере, ИЛИ наушники — не устройство ввода информации.
- Континенты и острова — это большие участки суши.
2 О том, как прошли летние каникулы, Кира рассказала своим друзьям следующее:
- Я была у бабушки в деревне, и рядом с деревней было озеро.
- По озеру плавала лодка или утка.
- Мы с бабушкой насобирали малины и смородины.
- Я составила букет из цветов. В нем были ромашки или гвоздики.
Подготовьте к каждому из высказываний Киры рисунки, учитывая, что все высказывания истинны.
3 Откройте файл с рисунком и разложите грибы по корзинкам так, чтобы было истинным следующее высказывание: «В большой корзине все грибы съедобные, и в маленькой корзине все грибы несъедобные». 
4 Откройте файл с рисунком и поставьте все цветы в вазы так, чтобы было истинным высказывание: «В синей вазе все цветы розы, или в красной вазе все цветы не красного цвета». 
5* Найдите значения логических выражений, если А = 1, B = 1, С = 0, D = 0.
Основные логические операции (and, or, xor, not)
Бит — это минимальная единица измерения объёма информации, так как она хранит одно из двух значений — 0 (False) или 1 (True). False и True в переводе на русский ложь и истина соответственно. То есть одна битовая ячейка может находиться одновременно лишь в одном состоянии из возможных двух. Напомню, два возможных состояния битовой ячейки равны — 1 и 0.
Есть определённые операции, для манипуляций с битами. Эти операции называются логическими или булевыми операциями, названные в честь одного из математиков — Джорджа Буля (1815-1864), который способствовал развитию этой области науки.
Все эти операции могут быть применены к любому биту, независимо от того, какое он имеет значение — 0(нуль) или 1(единицу). Ниже приведены основные логические операции и примеры их использования.
Логическая операция И (AND)
Логическая операция И выполняется с двумя битами, назовем их a и b. Результат выполнения логической операции И будет равен 1, если a и b равны 1, а во всех остальных (других) случаях, результат будет равен 0. Смотрим таблицу истинности логической операции and.
| a(бит 1) | b(бит 2) | a(бит 1) & b(бит 2) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Логическая операция ИЛИ (OR)
Логическая операция ИЛИ выполняется с двумя битами (a и b). Результат выполнения логической операции ИЛИ будет равен 0, если a и b равны 0 (нулю), а во всех остальных (других) случаях, результат равен 1 (единице). Смотрим таблицу истинности логической операции OR.
| a(бит 1) | b(бит 2) | a(бит 1) | b(бит 2) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Логическая операция исключающее ИЛИ (XOR).
Обозначение XOR: ^
Логическая операция исключающее ИЛИ выполняется с двумя битами (a и b). Результат выполнения логической операции XOR будет равен 1 (единице), если один из битов a или b равен 1 (единице), во всех остальных случаях, результат равен 0 (нулю). Смотрим таблицу истинности логической операции исключающее ИЛИ.
| a(бит 1) | b(бит 2) | a(бит 1) ^ b(бит 2) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Логическая операция НЕ (not)
Логическая операция НЕ выполняется с одним битом. Результат выполнения этой логической операции напрямую зависит от состояния бита. Если бит находился в нулевом состоянии, то результат выполнения NOT будет равен единице и наоборот. Смотрим таблицу истинности логической операции НЕ.
Запомните эти 4 логические операции. Используя эти логические операции, мы можем получить любой возможный результат. Подробно об использовании логических операций в С++ читаем тут.
Основы булевой алгебры: True, False, XOR, NOR и логические символы
Все мы любим компьютеры. Они могут делать столько удивительных вещей. За пару десятилетий компьютеры произвели самую настоящую революцию почти во всех аспектах человеческой жизни.
Они могут справляться с задачами различной степени сложности, просто переворачивая нули и единицы. Просто удивительно, как такое простое действие может привести к такому уровню сложности.
Но я уверен, что вы все знаете, что такой сложности нельзя добиться (практически нельзя) простым случайным переворачиванием чисел. Но за этим стоит определенные логические рассуждения. Есть правила, которые определяют, как это все должно происходить. В данной статье мы обсудим эти правила и увидим, как они управляют «мышлением» компьютера.
Что такое булева алгебра?
Это правила, о которых я упоминал выше, описываются некой областью математики, называемой булевой алгеброй.
В своей книге 1854 года британский математик Джордж Буль предложил использовать систематический набор правил для работы со значениями истинности. Эти правила положили математическую основу для работы с логическими высказываниями. А эти основы привели к развитию булевой алгебры.
Для того, чтобы понять, что из себя представляет булева алгебра, сначала мы должны понять сходства и различия между ней и другими формами алгебры.
Алгебра в целом занимается изучением математических символов и операций, которые можно выполнять над этими символами.
Эти символы сами по себе ничего не значат. Они обозначают некую величину. Именно эти величины и придают ценность этим символам, и именно с этими величинами и выполняются операции.
Булева алгебра также имеет дело с символами и правилами, позволяющими выполнять различные операции над этими символами. Разница заключается в том, что эти символы что-то значат.
В случае обычной алгебры символы обозначают действительные числа. А в булевой алгебре они обозначают значения истинности.
На рисунке ниже представлен весь набор действительных чисел. Набор действительных чисел включает натуральные числа (1, 2, 3, 4, …) , положительные целые числа (все натуральные числа и 0 ), целые числа (…, -2, -1, 0, 1, 2, 3, …) и т.д. Обычная алгебра имеет дело со всем этим набором чисел.
Для сравнения, значения истинности состоят из набора, который включает в себя только два значения: True и False. Здесь я хотел бы отметить, что мы можем использовать любые другие символы для обозначения этих значений.
Например, в информатике, как правило, эти значения обозначают через 0 и 1 ( 0 используется в качестве False , 1 – в качестве True ).
Вы также можете сделать это более оригинальным способом, обозначая значения истинности какими-то другими символами, например, кошки и собаки или бананы и апельсины.
Суть здесь в том, что смысл этих значений останется неизменным, как бы вы их не обозначили. Но убедитесь, что вы не меняете символы в процессе выполнения операций.
Теперь вопрос в том, что если ( True и False ), ( 0 и 1 ) – это просто обозначения, то что же они пытаются обозначить?
Смысл, лежащий в основе значений истинности, исходит из области логики, где значения истинности используются для того, чтобы определить, является ли высказывание «Истинным» ( True ) или «Ложным» ( False ). Здесь значения истинности обозначают соответствие высказывания истине, то есть показывают, является ли высказывание истинным или ложным.
Высказывание – это просто некоторое утверждение, что-то вроде «Все кошки милые».
Если приведенное выше высказывание верно, то мы присваиваем ему значение истинности «Истина» ( True ) или «1», в противном случае мы присваиваем ему значение истинности «Ложь» ( False ) или «0».
В цифровой электронике значения истинности используются для обозначения состояний электронных схем «включено» и «выключено». Подробнее об этом мы поговорим позже в этой же статье.
Логические операции и таблицы истинности
Как и в обычной алгебре, в булевой алгебре также можно применять операции к значениям для получения некоторых результатов. Однако эти операции не похожи на операции в обычной алгебре, поскольку, как мы уже упоминали ранее, булева алгебра работает со значениями истинности, а не с действительными числами.
В булевой алгебре есть три основные операции.
OR: OR или «ИЛИ», также известная как дизъюнкция. Эта операция выполняется над двумя логическими переменными. Результатом операции OR будет 0 , если оба операнда равны 0 , иначе будет 1 .
Для того, чтобы более наглядно продемонстрировать принцип работы этой операции, визуализируем ее с помощью таблицы истинности.
Таблицы истинности дают нам хорошее представление о том, как работают логические операции. Также это удобный инструмент для выполнения логических операций.
| Переменная 1 | Переменная 2 | Результат |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
AND: AND или «И», также известная как конъюнкция. Эта операция выполняется над двумя логическими переменными. Результатом операции AND будет 1 , если оба операнда равны 1 , иначе будет 0 . Таблица истинности выглядит следующим образом.
| Переменная 1 | Переменная 2 | Результат |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
NOT: NOT или «НЕ», также известное как отрицание. Эта операция выполняется только над одной переменной. Если значение переменной равно 1 , то результатом этой операции будет 0 , и наоборот, если значение переменной равно 0 , то результатом операции будет 1 .
| Переменная 1 | Результат |
| 0 | 1 |
| 1 | 0 |
Булева алгебра и цифровые схемы
Булева алгебра после своего появления очень долго оставалась одним из тех понятий в математике, которые не имели какого-то значительного практического применения.
В 1930-х годах Клод Шеннон, американский математик, обнаружил, что булеву алгебру можно использовать в схемах, где двоичные переменные могут обозначать сигналы «низкого» и «высокого» напряжения или состояния «включено» и «выключено».
Эта простая идея создания схем с помощью булевой алгебры привела к развитию цифровой электроники, которая внесла большой вклад в разработку схем для компьютеров.
Цифровые схемы реализуют булеву алгебру при помощи логических элементов – схем, обозначающих логическую операцию. Например, элемент OR будет обозначать операцию OR. То же самое относится и к элементам AND и NOT.
Наряду с основными логическими элементами существуют и логические элементы, которые можно создать путем комбинирования основных логических элементов.
NAND: элемент NAND, или «И-НЕ», образован комбинацией элементов NOT и AND. Элемент NAND дает на выходе 0 , если на обоих входах 1 , в противном случае – 1 .
Элемент NAND обладает свойством функциональной полноты. Это означает, что любая логическая функция может быть реализована только с помощью элементов NAND.
| Вход 1 | Вход 2 | Результат |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
NOR: элемент NOR, или «ИЛИ-НЕ», образован комбинацией элементов NOT и OR. Элемент NOR дает на выходе 1 , если на обоих входах 0 , в противном случае – 0 .
Элемент NOR, как и элемент NAND, обладает свойством функциональной полноты. Это означает, что любая логическая функция может быть реализована только с помощью элементов NOR.
| Вход 1 | Вход 2 | Результат |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
Большинство цифровых схем построены с использованием элементов NAND и NOR из-за их функциональной полноты, а также из-за простоты изготовления.
Помимо элементов, рассмотренных выше, существуют также особые элементы, которые служат для определенных целей. Вот они:
XOR: элемент XOR, или «исключающее ИЛИ», — это особый тип логических элементов, который дает на выходе 0 , если оба входа равны 0 или 1 , в противном случае – 1 .
| Вход 1 | Вход 2 | Результат |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
XNOR: элемент XNOR, или «исключающее ИЛИ-НЕ», — это особый тип логических элементов, который дает на выходе 1 , когда оба входа равны 0 или 1 , в противном случае – 0 .
| Вход 1 | Вход 2 | Результат |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Заключение
Итак, на этом мы можем закончить обсуждение булевой алгебры. Надеюсь, что к текущему моменту у вас сложилась неплохая картина того, что же такое булева алгебра. Это, конечно, далеко не все, что вам следует знать о булевой алгебре. В ней есть множество понятий и деталей, которые мы не обсудили в данной статье.