Логическая операция исключающее или доклад
Обновлено: 02.05.2024
Эта лицензия позволяет другим редактировать, поправлять и брать за основу ваше произведение в некоммерческих целях до тех пор пока они указывают вас в качестве автора и лицензируют их новые творения на идентичных условиях.
Основы логики. Логические операции и таблицы истинности
На данной странице будут рассмотрены 6 логических операций: конъюнкция, дизъюнкция, инверсия, импликация, эквивалентность и исключающие или, которых вам будет достаточно для решения сложных логических выражений. Также мы рассмотрим порядок выполнения данных логических операций в сложных логических выражениях и представим таблицы истинности для каждой логической операции.
Высказывание - это повествовательное предложение, про которое можно определенно сказать истинно оно или ложно (истина (логическая 1), ложь (логический 0)).
Логические операции - мыслительные действия, результатом которых является изменение содержания или объема понятий, а также образование новых понятий.
Логическое выражение - устное утверждение или запись, в которое, наряду с постоянными величинами, обязательно входят переменные величины (объекты). В зависимости от значений этих переменных величин (объектов) логическое выражение может принимать одно из двух возможных значений: истина (логическая 1) или ложь (логический 0).
Сложное логическое выражение - логическое выражение, состоящее из одного или нескольких простых логических выражений (или сложных логических выражений), соединенных с помощью логических операций.
Конъюнкция - это сложное логическое выражение, которое считается истинным в том и только том случае, когда оба простых выражения являются истинными, во всех остальных случаях данное сложенное выражение ложно.
| A | B | F |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 0 |
2) Логическое сложение или дизъюнкция:
Дизъюнкция - это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно и ложно тогда и только тогда, когда оба простых логических выраженbя ложны.
Обозначение: F = A v B.
Таблица истинности для дизъюнкции
| A | B | F |
| 1 | 1 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
3) Логическое отрицание или инверсия:
Инверсия - это сложное логическое выражение, если исходное логическое выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное логическое выражение ложно, то результат отрицания будет истинным. Другими простыми слова, данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО.
Обозначение: F = ¬ A.
Таблица истинности для инверсии
| A | ¬ А |
| 1 | 0 |
| 0 | 1 |
4) Логическое следование или импликация:
Импликация - это сложное логическое выражение, которое истинно во всех случаях, кроме как из истины следует ложь. То есть данная логическая операция связывает два простых логических выражения, из которых первое является условием (А), а второе (В) является следствием.
Обозначение: F = A → B.
Таблица истинности для импликации
| A | B | F |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
5) Логическая равнозначность или эквивалентность:
Эквивалентность - это сложное логическое выражение, которое является истинным тогда и только тогда, когда оба простых логических выражения имеют одинаковую истинность.
| A | B | F |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
6) Операция XOR (исключающие или)
Обозначение: F = A ⊕ B .
| A | B | F |
| 1 | 1 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
Порядок выполнения логических операций в сложном логическом выражении
1. Инверсия;
2. Конъюнкция;
3. Дизъюнкция;
4. Импликация;
5. Эквивалентность.
Для изменения указанного порядка выполнения логических операций используются скобки.
Таблицы истинности можно составить и для произвольной логической функции F(a, b, c…).
В общем случае таблицы истинности имеют размер 2 N строк комбинаций для N независимых логических переменных.
Поскольку таблица истинности выражения состоит из строк со всеми возможными комбинациями значений переменных, она полностью определяет значение выражения.
Законы алгебры логики
Те, кому лень учить эти законы, должны вспомнить алгебру, где знание нескольких способов преобразования позволяет решать очень сложные уравнения.
Строго говоря, это не законы, а теоремы. Но их доказательство не входит в программу изучения. Впрочем, доказательство обычно основывается на построении полной таблицы истинности.
Замечание. Знаки алгебры логики намеренно заменены на сложение и умножение.
Замена операций импликации и эквивалентности
Операций импликации и эквивалентности иногда нет среди логических операций конкретного компьютера или транслятора с языка программирования. Однако для решения многих задач эти операции необходимы. Существуют правила замены данных операций на последовательности операций отрицания, дизъюнкции и конъюнкции.
Так, заменить операцию импликации можно в соответствии со следующим правилом:
A → B = ¬ A \/ B
Для замены операции эквивалентности существует два правила:
В справедливости данных формул легко убедиться, построив таблицы истинности для правой и левой частей обоих тождеств.
В этой статье мы поговорим о некоторых битовых операциях. Рассмотрим основные из них: 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 логические операции следует запомнить в первую очередь, т. к. с их помощью можно получить практически любой возможный результат. Также существуют такие операции, как (побитовый сдвиг влево) и >> (побитовый сдвиг вправо).
В данной статье я расскажу о битовой операции XOR (исключающее ИЛИ) и приведу наиболее интересные примеры ее применения на JAVA.
XOR обладает следующими свойствами:
a XOR 0 = a
a XOR a = 0
a XOR b = b XOR a
(a XOR b) XOR b = a
Обмен значений переменных без использования дополнительной переменной
С использованием операции XOR можно реализовать обмен значений однотипных пременных без использования дополнительной переменной:
или в более короткой записи:
Таким образом можно, например, реализовать реверс текстовой строки:
Следует, однако, заметить, что такой код не дает выигрыша в скорости по сравнению с кодом использующим временную переменную.
Шифрование
Шифрование на основе операций XOR использует свойство:
(a XOR k) XOR k = a
где k – выступает в роли ключа
Простая реализация шифрования строки:
Попробуем зашифровать строку “Съешь ещё этих мягких французских булок, да выпей чаю.” И в качестве ключа возьмем слово “хабра”:
Узким местом такого шифрования является то, что зная часть зашифрованного текста можно с легкостью восстановить ключ и, соответственно, расшифровать весь текст. Поэтому в чистом виде он редко используется на практике, хотя его применяют как часть более сложных алгоритмов шифрования.
Интересно, что в свое время данный алгоритм использовался Microsoft для шифрования содержимого документов в Office 95.
Генератор случайных чисел XORShift
В 2003 году Джордж Марсаглия представил миру быстрый алгоритм генерации случайных чисел с использованием XOR – XORShift.
Одна из возможных его рализаций:
Тут “магические“ числа 21, 35 и 4 подобраны для генерации лучшей последовательности (полный период равен 2 64 -1).
Проинициализировав генератор числом 1111111111, получим такую последовательность для первых 10 чисел:
39462749392662495
4596835458788324745
-7932128052244037525
-2502212788642280052
3288035714308340525
-8561046377475020727
-812160615072319265
-3869866974339671508
-7329504029400927428
3890915262874757420
В заключение просьба тем, у кого есть другие красивые примеры применения XOR, не вошедшие в статью, рассказать о них.
В этой статье я расскажу вам о том, как работают битовые операции. С первого взгляда они могут показаться вам чем-то сложным и бесполезным, но на самом деле это совсем не так. В этом я и попытаюсь вас убедить.
Введение
Побитовые операторы проводят операции непосредственно на битах числа, поэтому числа в примерах будут в двоичной системе счисления.
Я расскажу о следующих побитовых операторах:
- | (Побитовое ИЛИ (OR)),
- & (Побитовое И (AND)),
- ^ (Исключающее ИЛИ (XOR)),
- ~ (Побитовое отрицание (NOT)),
- > (Побитовый сдвиг вправо).
Битовые операции изучаются в дискретной математике, а также лежат в основе цифровой техники, так как на них основана логика работы логических вентилей — базовых элементов цифровых схем. В дискретной математике, как и в цифровой технике, для описания их работы используются таблицы истинности. Таблицы истинности, как мне кажется, значительно облегчают понимание битовых операций, поэтому я приведу их в этой статье. Их, тем не менее, почти не используют в объяснениях побитовых операторов высокоуровневых языков программирования.
О битовых операторах вам также необходимо знать:
- Некоторые побитовые операторы похожи на операторы, с которыми вы наверняка знакомы (&&, ||). Это потому, что они на самом деле в чем-то похожи. Тем не менее, путать их ни в коем случае нельзя.
- Большинство битовых операций являются операциями составного присваивания.
Побитовое ИЛИ (OR)
Побитовое ИЛИ действует эквивалентно логическому ИЛИ, но примененному к каждой паре битов двоичного числа. Двоичный разряд результата равен 0 только тогда, когда оба соответствующих бита в равны 0. Во всех других случаях двоичный результат равен 1. То есть, если у нас есть следующая таблица истинности:
38 | 53 будет таким:
| A | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|
| B | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| A | B | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
В итоге мы получаем 1101112 , или 5510 .
Побитовое И (AND)
Побитовое И — это что-то вроде операции, противоположной побитовому ИЛИ. Двоичный разряд результата равен 1 только тогда, когда оба соответствующих бита операндов равны 1. Другими словами, можно сказать, двоичные разряды получившегося числа — это результат умножения соответствующих битов операнда: 1х1 = 1, 1х0 = 0. Побитовому И соответствует следующая таблица истинности:
Пример работы побитового И на выражении 38 & 53:
| A | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|
| B | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| A & B | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
Как результат, получаем 1001002 , или 3610 .
С помощью побитового оператора И можно проверить, является ли число четным или нечетным. Для целых чисел, если младший бит равен 1, то число нечетное (основываясь на преобразовании двоичных чисел в десятичные). Зачем это нужно, если можно просто использовать %2 ? На моем компьютере, например, &1 выполняется на 66% быстрее. Довольно неплохое повышение производительности, скажу я вам.
Исключающее ИЛИ (XOR)
Разница между исключающим ИЛИ и побитовым ИЛИ в том, что для получения 1 только один бит в паре может быть 1:
Например, выражение 138^43 будет равно…
| A | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|
| B | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| A ^ B | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
С помощью ^ можно поменять значения двух переменных (имеющих одинаковый тип данных) без использования временной переменной.
Также с помощью исключающего ИЛИ можно зашифровать текст. Для этого нужно лишь итерировать через все символы, и ^ их с символом-ключом. Для более сложного шифра можно использовать строку символов:
Исключающее ИЛИ не самый надежный способ шифровки, но его можно сделать частью шифровального алгоритма.
Побитовое отрицание (NOT)
Побитовое отрицание инвертирует все биты операнда. То есть, то что было 1 станет 0, и наоборот.
Вот, например, операция ~52:
| A | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 |
|---|---|---|---|---|---|---|---|---|
| ~A | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
Результатом будет 20310
При использовании побитового отрицания знак результата всегда будет противоположен знаку исходного числа (при работе со знаковыми числами). Почему так происходит, узнаете прямо сейчас.
Дополнительный код
Здесь мне стоит рассказать вам немного о способе представления отрицательных целых чисел в ЭВМ, а именно о дополнительном коде (two’s complement). Не вдаваясь в подробности, он нужен для облегчения арифметики двоичных чисел.
Главное, что вам нужно знать о числах, записанных в дополнительном коде — это то, что старший разряд является знаковым. Если он равен 0, то число положительное и совпадает с представлением этого числа в прямом коде, а если 1 — то оно отрицательное. То есть, 10111101 — отрицательное число, а 01000011 — положительное.
Чтобы преобразовать отрицательное число в дополнительный код, нужно инвертировать все биты числа (то есть, по сути, использовать побитовое отрицание) и добавить к результату 1.
Например, если мы имеем 109:
| A | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
| ~A | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| ~A+1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
Представленным выше методом мы получаем -109 в дополнительном коде.
Только что было представлено очень упрощенное объяснение дополнительного кода, и я настоятельно советую вам детальнее изучить эту тему.
Побитовый сдвиг влево
Побитовые сдвиги немного отличаются от рассмотренных ранее битовых операций. Побитовый сдвиг влево сдвигает биты своего операнда на N количество битов влево, начиная с младшего бита. Пустые места после сдвига заполняются нулями. Происходит это так:
Побитовый сдвиг вправо
Как вы могли догадаться, >> сдвигает биты операнда на обозначенное количество битов вправо.
Если операнд положительный, то пустые места заполняются нулями. Если же изначально мы работаем с отрицательным числом, то все пустые места слева заполняются единицами. Это делается для сохранения знака в соответствии с дополнительным кодом, объясненным ранее.
Так как побитовый сдвиг вправо — это операция, противоположная побитовому сдвигу влево, несложно догадаться, что сдвиг числа вправо на N количество позиций также делит это число на 2 N . Опять же, это выполняется намного быстрее обычного деления.
Вывод
Итак, теперь вы знаете больше о битовых операциях и не боитесь их. Могу предположить, что вы не будете использовать >>1 при каждом делении на 2. Тем не менее, битовые операции неплохо иметь в своем арсенале, и теперь вы сможете воспользоваться ими в случае надобности или же ответить на каверзный вопрос на собеседовании.
Читайте также: