ГДЗ по информатике, 10 класс, Поляков, номер 16.8: Логические операции

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

Иными словами, для обратимой операции f существует такая операция g, что применение g к результату f(x_1,x_2,…,x_n) возвращает нам кортеж (x_1,x_2,…,x_n). Если же разным наборам входных данных соответствует один и тот же результат, то операцию назвать обратимой нельзя, так как мы не сможем понять, какой именно из наборов был исходным.

Рассмотрим основные булевы операции:

• Конъюнкция (land), дизъюнкция (lor), импликация (→), эквивалентность (↔) : эти операции являются необратимыми . Например, если конъюнкция двух переменных равна 0, то возможны три варианта: (0,0), (0,1) или (1,0). Мы не можем точно сказать, какие были исходные значения.
• Отрицание (¬) : это унарная операция. Если y=¬x, то x=¬y. По результату всегда можно однозначно найти аргумент. Следовательно, отрицание — обратимая операция.

Помимо отрицания, в алгебре логики существуют специфические бинарные и более сложные операции, обладающие свойством обратимости. К ним относятся:

1. Стрелка Пирса (↓) и штрих Шеффера (|) : сами по себе они необратимы в обычном смысле восстановления обоих аргументов только по одному выходу, но часто рассматриваются в контексте функциональной полноты. Однако строго говоря, классически обратимыми считаются следующие:
2. Сложение по модулю 2 (строгая дизъюнкция, XOR, ⊕) : Операция определяется как x⊕y. Она обладает свойством: если известен результат z=x⊕y и один из аргументов (например, x), то второй аргумент находится однозначно: y=z⊕x. В широком смысле, система уравнений с использованием XOR разрешима.
3. Операция «Не-И» (NAND) и «Не-Или» (NOR) в комбинации с сохранением одного из входов (как в вентилях Тоффоли или Фредкина), но в чистом виде бинарных функций от двух аргументов к истинно обратимым (где выход содержит всю информацию о входах) относятся:
4. Тождественная функция (f(x)=x) и Отрицание (f(x)=¬x).

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

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

Проверим утверждение на примере отрицания:

Проверим на примере конъюнкции:

Ответ: Обратимой называется логическая операция, позволяющая по результату однозначно восстановить исходные аргументы. Из основных логических операций обратимой является отрицание (¬). Также обратимыми считаются тождественная операция и некоторые специализированные функции (например, сложение по модулю 2 при наличии одного из операндов), но в рамках базового списка связок выделяется именно отрицание.