Кроме уже известных операций НЕ, И, ИЛИ существуют и другие логические функции. Например, с двумя переменными можно придумать 16 функций, некоторые из которых имеют свои собственные названия: импликация, эквивалентность и исключающее или.
Операция импликации обозначается стрелкой вправо (→). Эта операция возвращает ложь (0) только тогда, когда первое утверждение истинно (1), а второе ложно (0).
Вывод через базис логических операций: (НЕ А) ИЛИ В.
Таблица истинности:
Таблица истинности с операцией импликации
Операция эквивалентности обозначается стрелкой в обе стороны (↔). Эта операция возвращает правду (1) только тогда, когда первое утверждение по истинности такое же как и второе.
Вывод через базис логических операций: ( (НЕ А) И (НЕ В) ) ИЛИ (А И В).
Таблица истинности:
Таблица истинности с операцией эквивалентности
Операция исключающее или (XOR) – это логическая операция, которая выдает истину (1), если число истинных (1) входных значений нечетно, и ложь (0) в противном случае.
Таким образом выходной сигнал операции XOR равен 1 только в том случае, если число входных сигналов равных 1 нечетно. В противном случае выходной сигнал равен 0.
Вывод через базис логических операций: (A И (НЕ B)) ИЛИ ((НЕ A) И B).
Таблица истинности:
Таблица истинности с операцией исключающее или
Для того, чтобы зашифровать какую-то битовую последовательность длины N необходимо придумать битовый ключ также длины N. Затем применяется операция побитового XOR и получившееся значение – результат шифрования.
Для того, чтобы расшифровать какую-то битовую последовательность длины N необходимо взять битовый ключ, которым эта последовательность была зашифрована. Затем применяется операция побитового XOR и получившееся значение – исходная битовая последовательность.
Пример шифрования:
Пусть исходная битовая последовательность: 10110010. Ключ: 10101010. Тогда результат шифрования равен: 00011000.
1 XOR 1 = 0
0 XOR 0 = 0
1 XOR 1 = 0
1 XOR 0 = 1
0 XOR 1 = 1
0 XOR 0 = 0
1 XOR 1 = 0
0 XOR 0 = 0
Пример расшифровки:
Пусть есть зашифрованная битовая последовательность 00011000 и ключ которым ее зашифровали: 10101010. Тогда результат расшифровки равен 10110010 – исходному значению.
0 XOR 1 = 1
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
0 XOR 0 = 0
0 XOR 1 = 1
0 XOR 0 = 0
В логике импликация (A → B) – это утверждение, которое истинно во всех случаях, кроме когда A истинно, а B ложно; эквиваленция (A ↔ B) – это утверждение, истинное только при одинаковых значениях A и B; исключающее ИЛИ (XOR) – это утверждение, истинное только при нечетном количестве истинных входных переменных. Исключающее ИЛИ обладает интересным свойством, которое пригодно для простого шифрования.