Программный метод решения
В прошлой статье мы научились решать 2 задания ручным способом и перебирать значения переменных с помощью Python. Можно сказать, что это два уровня «автоматизации» решения:
- Самостоятельно подбираем значения для каждой переменной и сопоставляем их с таблицей из условия
- Программа подбирает значения за нас, а мы лишь сопоставляем их с таблицей
Но существует и третий уровень, где не придётся ни подбирать значения, ни сопоставлять их. Программа самостоятельно проанализирует логическое выражение, переберёт возможные комбинации и выдаст готовый ответ.
В этой статье мы напишем универсальный код для автоматического решения задания 2, а затем опробуем его на нескольких примерах. Приступаем!
Алгоритм решения
Определим стратегию работы нашей программы:
- Подбираем значения для пустых ячеек таблицы истинности
- Для каждого варианта заполнения пробуем разные расстановки имён переменных по столбцам
- Если при какой-то комбинации значение логической функции совпадёт с заданным в условии — бинго! Мы нашли верный порядок имён
Теперь разберём каждый этап нашей стратегии по порядку.
Давайте вспомним, что мы делаем, когда нужно подобрать значение переменной? Перебираем все варианты из диапазона, пока не найдём подходящий.
Теперь представим, что нам нужно подобрать сразу несколько таких значений, допустим, 5. К счастью, в алгебре логики переменные принимают значения только 0 или 1. Вручную мы бы перебирали так:
- 0, 0, 0, 0, 0
- 0, 0, 0, 0, 1
- 0, 0, 0, 1, 0
И так далее. Ничего не напоминает? Ведь то же самое делает функция product() из модуля itertools. Именно её мы применяли ранее, когда решали 8 задания.
Напишем цикл для перебора пяти переменных. Назовём их a1, a2, a3, a4, a5. Параметр repeat должен равняться количеству перебираемых переменных — в нашем случае 5:
Отлично! Эти значения и есть пропущенные числа в таблице истинности.
Вместо вывода значений сформируем список кортежей, представляющий таблицу истинности. Известные числа запишем в соответствующие позиции, а пропуски последовательно заполним переменными a.
Предположим, что в условии дана такая таблица:
Заполним все пустые ячейки:
Ну а в коде это будет выглядеть так:
Таким образом, на каждой итерации цикла мы будем получать «предполагаемую» таблицу истинности. Но есть один нюанс!
В таблице не может быть одинаковых строк — иначе она была бы неинформативна. Наш код пока не защищён от дублирования. Решение простое: проверим, что количество элементов в списке совпадает с количеством уникальных элементов:
Мы превращаем список в множество, которое автоматически удаляет дубликаты. Если длина не изменилась — дубликатов не было, и такая таблица корректна.
После проверки переходим к следующему этапу — подбору имён переменных.
Теперь таблица заполнена, но неизвестно, какой столбец соответствует x, y, z или w. Нужно перебрать все порядки букв. Для этого идеально подходит функция permutations() все из того же itertools.
Эта функция вернёт нам 24 варианта перестановок букв x, y, z, w, которые мы будем поочерёдно перебирать в цикле for:
Осталась ключевая часть — самая важная и одновременно самая сложная для понимания. Имея таблицу и предполагаемую расстановку букв, нужно проверить, подходят ли наши значения под логическую функцию из условия.
Для начала, конечно же, нужно написать саму логическую функцию. Сделаем это в виде отдельной функции f() и предположим, что нам дана вот такая функция в условии: F = (x ∨ y) ∧ ¬ (y ≡ z) ∧ ¬ w. Записывается это так:
Вставим этот код в нашу программу:
Теперь подставим числа из каждой строки таблицы в функцию f(), но в порядке, заданном текущей перестановкой p.
Сразу покажем код, а затем разберём его:
Что происходит в последней строке:
- zip(p, t): берёт буквы текущей расстановки (например, w, z, y, x) и числа из строки таблицы (например, 1, 1, 0, 0), склеивая их в пары: (w, 1), (z, 1), (y, 0), (x, 0)
- dict(…): превращает пары в словарь: {‘w’: 1, ‘z’: 1, ‘y’: 0, ‘x’: 0}
- Оператор распаковки **: распределяет значения словаря по одноимённым аргументам функции f(). Это гарантирует, что каждое число займёт правильную позицию: x получит своё значение, y — своё и так далее. Например, вызов будет выглядеть как f(0, 0, 1, 1), а не f(1, 1, 0, 0)
- В конце формируем список результатов функции f() для всех строк таблицы и сравниваем с заданными значениями из условия ([0, 0, 0])
Если всё совпало, выводим текущую перестановку:
Готово! Теперь создадим универсальный шаблон:
Этот шаблон готов к использованию — меняются только части выделенные жёлтым цветом под конкретную задачу.
Давайте опробуем этот код на задании с такой формулировкой:
«Миша заполнял таблицу истинности логической функции F = (w ≡ z) ∨ ¬(y → w) ∨ ¬x, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы.»
Импортируем нужные функции и перепишем логическое выражение из условия в виде функции:
Далее нам нужно заполнить пустые ячейки таблицы из условия следующим образом:
И то же самое добавим в код:
Теперь допишем оставшуюся часть кода:
Смело запускаем его и получаем такую строку: zwxy. Она и будет ответом на это задание.
Пример 1
Решим еще одно задание этим методом:
«Миша заполнял таблицу истинности логической функции F = ¬(y → (x ≡ z)) ∧ (w → x), но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w,x,y,z.
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы.»
Как и в прошлый раз импортируем функции и переписываем логическое выражение:
Добавляем цикл с перебором значений пустых ячеек:
И последнюю часть с проверкой:
Запускаем этот код и видим на экране ответ: zxwy.
Пример 2
И для закрепления решим еще одно задание:
«Миша заполнял таблицу истинности логической функции F = ¬(w → (x ≡ y)) ∧ (z → x), но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w,x,y,z.
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы.»
В этот раз уже не будем подробно останавливаться на каждой части кода и напишем его целиком:
Запустив его, получим нужный нам ответ: yxwz.
Как видите, ничего сложного в использовании этого универсального кода нет. Достаточно лишь правильно переписать логическое выражение из условия, соблюдая порядок операций. Остальное программа сделает за вас и выдаст верный ответ.
Больше заданий данного типа с подробным решением вы можете найти в нашем тренажёре.
<<< Предыдущая статья Первая статья >>>