Информатика. Учебник для 9 класса (по учебнику К. Ю. Полякова, Е.А. Еремина, базовый уровень)
§10. Другие логические операции.
Импликация
Ключевые слова:
• импликация • исключающее ИЛИ • эквиваленция
Мы изучили две логические операции с двумя переменными — Ии ИЛИ. Существуют ли другие? И сколько их?
В таблице истинности любой логической операции с двумя переменными всего четыре строки, и эти таблицы отличаются только четырьмя значениями функции в последнем столбце. Поэтому можно придумать всего 16 = 24 различных логических операций с двумя переменными.
На уроках математики вы доказывали теоремы, в которых встречались выражения «если …, то…», «тогда и только тогда, когда…». Эти связки тоже обозначают логические операции, с которыми мы сейчас и познакомимся.
Слово «импликация» означает «следование» — из одного утверждения следует другое. Если истинно первое, то истинно и второе. Например, возьмём высказывание
X = Если идёт дождь, то Лена раскрывает зонтик.
Если ввести обозначения для простых высказываний:
А = Идёт дождь,
В = Лена раскрывает зонтик, то можно записать высказывание X в символьном виде:
X = А → В.
Стрелка вправо обозначает логическую операцию «импликация».
Используя дополнительные источники, выясните, от какого иностранного слова произошло слово «импликация». Что оно означает?
Теперь давайте разберёмся, когда такое высказывание будет истинно, а когда — ложно. Если дождь идёт (А = 1) и Лена раскрывает зонтик (В = 1), то импликация, очевидно, истинна. Если же при дожде Лена зонтик не раскрыла, импликация ложна (из А не следует B!).
А если дождя нет (А = 0)? Тогда о состоянии зонтика Лены мы ничего сказать не можем, потому что он может быть как закрыт, так и открыт. И в обоих случаях импликация будет истинна, потому что не исключено, что из А следует В (возможно, что, когда пойдёт дождь, Лена откроет зонтик). Говорят, что «из истины следует истина, а из лжи — что угодно»
Рис. 2.13
Таблица истинности операции импликация показана на рис. 2.13. Как видим, эта функция равна нулю только при одном значении исходных данных: 1 → 0 = 0, во всех остальных случаях она равна 1.
Обычно, говоря «если…, то…», мы имеем в виду причинно-следственную связь, когда одно вызывает другое. Например, «Если светит солнце, то лужи высыхают» (именно потому, что светит солнце!). Импликация не говорит о причине и следствии, а показывает возможность такой связи. Например, может быть истинной импликация «если сегодня вторник, то Эльбрус покрыт снегом».
Импликация часто используется при решении логических задач. Например, формулировку вида «если А, то В» можно записать как А → В = 1.
Постройте таблицу истинности логической функции В → А 1). Сравните её с таблицей истинности функции А → B. Выполняется ли для импликации переместительный закон (если поменять местами А и B, то результат не изменяется)?
1) В этой и следующих трёх задачах сохраняйте порядок столбцов в таблице истинности: в первом столбце записывайте значение А, во втором — значение B.
Постройте таблицу истинности логической функции А + B. Сравните её с таблицами истинности известных вам функций с двумя переменными. Какую формулу вы сейчас доказали?
Постройте таблицу истинности логической функции B → А. Сравните её с таблицами истинности известных вам функций с двумя переменными. Какую формулу вы сейчас доказали?
Постройте таблицу истинности логической функции (А → В) и (В → А). Как бы вы назвали эту функцию?
Эквиваленция
Таблица истинности, которую вы построили в последнем задании, определяет логическую операцию «эквиваленция» (её также называют «равнозначность» или «логическое равенство»), которая обозначается знаком ↔. Эта операция соответствует связке «тогда и только тогда». Высказывание А ↔ В истинно в том и только в том случае, когда А и В равны (рис. 2.14).
Рис. 2.14
Используя дополнительные источники, выясните, какие знаки кроме ↔также используются для обозначения эквиваленции.
Постройте таблицу истинности логической функции А • В + А • B. Сравните её с таблицами истинности известных вам функций с двумя переменными. Какую формулу вы только что доказали?
Постройте таблицу истинности логической функции (А + B) • (А + В). Сравните её с таблицами истинности известных вам функций с двумя переменными. Какую формулу вы только что доказали?
Постройте таблицу истинности логической функции А • B + А • В. Сравните её с таблицами истинности известных вам функций с двумя переменными. Какую формулу вы только что доказали?
Исключающее ИЛИ
Функция, которую вы исследовали в последнем задании, называется исключающее ИЛИ. Её результат равен 1, если значения входных сигналов не равны (рис. 2.15).
Рис. 2.15
Исключающее ИЛИ обозначается знаком ⊕. Смысл этой операции хорошо передаёт поговорка «либо пан, либо пропал»: возможен только один вариант из двух, но не оба одновременно.
Сравните таблицы истинности обычной операции «ИЛИ» и «исключающего ИЛИ».
Сравните таблицы истинности логических функций А ⊕ В и А ↔ В. Какая формула связывает две эти операции?
Операция исключающее ИЛИ иначе называется разделительной дизъюнкцией (это значит «один или другой, но не оба вместе») или сложением по модулю два. Второе название связано с тем, что её результат равен остатку от деления арифметической суммы А + В на 2:
А ⊕ В = (А + В) mod 2.
Здесь mod обозначает операцию взятия остатка от деления.
Составьте таблицы истинности логических функций А ⊕ 0, А ⊕ 1 и А ⊕ А. Сравните значения каждой функции со столбцом А. Как можно упростить эти формулы?
Сравните таблицу истинности логической функции А • B + А • В (см. задание выше) с таблицей истинности операции исключающее ИЛИ. Какую формулу вы только что доказали?
Постройте таблицу истинности логической функции (А + В) • (А + B). Сравните её с таблицами истинности известных вам функций с двумя переменными. Какую формулу вы только что доказали?
Составьте таблицу истинности логической функции (А ⊕ В) ⊕ В. Сравните столбец значений функции со столбцом А. Какую формулу можно записать в результате сравнения?
Из результатов выполнения последнего задания следует важный вывод: если два раза применить к значению А операцию исключающее ИЛИ с одним и тем же значением В, то мы восстановим исходное значение А. В этом смысле исключающее ИЛИ — обратимая операция.
Какие ещё обратимые логические операции вы знаете?
Используя дополнительные источники, выясните, в каких языках программирования есть логическая операция «исключающее ИЛИ» и как она обозначается.
Запишите в тетради формулы, с помощью которых можно представить операции импликацию, эквиваленцию и исключающее ИЛИ через базовые логические операции: НЕ, И и ИЛИ.
Используйте результаты выполнения заданий в рабочей тетради.
Шифрование
Формулу (А ⊕ В) ⊕ В = А можно использовать для шифрования данных. Пусть А и В — это двоичные коды одинаковой длины. Чтобы зашифровать данные А с использованием ключа B, надо применить операцию исключающее ИЛИ отдельно для каждого двоичного разряда А и B. Для расшифровки ещё раз применяется исключающее ИЛИ с тем же ключом B. Нужно отметить, что такой метод шифрования очень нестойкий: для достаточно длинных текстов его легко взломать.
Например, пусть Алиса хочет секретно передать Борису число 9 в виде четырёхбитной двоичной цепочки 1001. Для шифрования они заранее договорились использовать ключ — двоичную цепочку 0101. Алиса шифрует каждый бит отдельно, выполняя операцию исключающее ИЛИ с соответствующим битом ключа, в результате получается цепочка 1100 (рис. 2.16).
Рис. 2.16
Борис, получив цепочку 1100, применяет для расшифровки тот же ключ 0101 и получает исходное сообщение — 1001 (рис. 2.17).
Рис. 2.17
Работа в парах. Договоритесь с напарником, какой четырёхбитный ключ вы будете использовать для шифровки. Зашифруйте год, когда произошло какое-нибудь известное историческое событие (четырёхбитный код каждой цифры отдельно с тем же ключом), и передайте напарнику зашифрованное сообщение. Попросите его назвать это событие.
Выводы
• Импликация А → B истинна во всех случаях, кроме А = 1 и B = 0.
• Эквиваленция А ↔ B истинна тогда и только тогда, когда А и Б имеют одинаковые значения.
• Исключающее ИЛИ А ⊕ Б принимает значение «истина» тогда и только тогда, когда значения А и B различны.
• Операция исключающее ИЛИ обратима: если взять любое значение А и выполнить дважды исключающее ИЛИ с любой постоянной, то получится исходное значение А. Эту особенность можно использовать для простого шифрования.
• Логические функции А → B, А ↔ В и А ⊕ В можно выразить через базовые логические операции НЕ, И и ИЛИ:
Нарисуйте в тетради интеллект-карту этого параграфа.
Вопросы и задания
1. Известно, что высказывание «Если X делится на 6, то X делится на 15» истинно. Будет ли верно это высказывание для чисел 7, 15, 18, 90?
2. Известно, что высказывание «Если Алиса ходила в поход, то Борис тоже ходил» ложно. Кто ходил в поход?
3. В лесу живут два медведя. Известно, что в берлоге всегда находится один медведь, а два медведя в берлогу не помещаются. С помощью какой логической операции можно сформулировать это высказывание?
4. Выполните по указанию учителя задания в рабочей тетради.
Подготовьте сообщение
а) «Логическая операция штрих Шеффера»
б) «Логическая операция стрелка Пирса»
в) «Частотный анализ текста»
Практическая работа № 8 «Шифрование»
1) Работа в парах. Договоритесь с напарником, какой четырёхбитный ключ вы будете использо-вать для шифровки. Зашифруйте год, когда произошло какое-нибудь известное историческое событие (четырёхбитный код каждой цифры отдельно с тем же ключом), и передайте напар-нику зашифрованное сообщение. Выполните задание 51 в рабочей тетради.
2) Перейдите в каталог work-8. Откройте в браузере тренажёр enigma.html.
3) Выберите для шифрования четырёхбитный ключ (число от 0 до 15) и зашифруйте какую-нибудь известную фразу с помощью этого ключа. Передайте напарнику полученный двоичный код в виде текстового файла и попросите расшифровать (не сообщая ключ!).
§10. Другие логические операции.