В прошлой статье мы научились решать задание 2 ручным способом и перебирать значения переменных с помощью Python. Можно сказать, что это два уровня «автоматизации» решения:
Самостоятельно подбираем значения для каждой переменной и сопоставляем их с таблицей из условия
Программа подбирает значения за нас, а мы лишь сопоставляем их с таблицей
Но существует и третий уровень, где не придётся ни подбирать значения, ни сопоставлять их. Программа самостоятельно проанализирует логическое выражение, переберёт возможные комбинации и выдаст готовый ответ.
В этой статье мы создадим универсальный код для автоматического решения задания 2, а затем опробуем его на нескольких примерах. Приступаем!
Алгоритм решения
Определим стратегию работы нашей программы:
Подбираем значения для пустых ячеек таблицы истинности
Для каждого варианта заполнения пробуем разные расстановки имён переменных по столбцам
Если при какой-то комбинации значение логической функции совпадёт с заданным в условии — бинго! Мы нашли верный порядок имён
Теперь разберём каждый этап нашей стратегии по порядку.
Давайте вспомним, что мы делаем, когда нужно подобрать значение переменной? Перебираем все варианты из диапазона, пока не найдём подходящий.
Теперь представим, что нам нужно подобрать сразу несколько таких значений, допустим, 5. К счастью, в алгебре логики переменные принимают значения только 0 или 1. Вручную мы бы перебирали так:
0, 0, 0, 0, 0
0, 0, 0, 0, 1
0, 0, 0, 1, 0
И так далее. Ничего не напоминает? Ведь то же самое делает функция product()из модуля itertools.
Напишем цикл для перебора пяти переменных. Назовём их a1, a2, a3, a4, a5. Параметр repeat должен равняться количеству перебираемых переменных — в нашем случае 5:
from itertools import product
for a1, a2, a3, a4, a5 in product([0, 1], repeat=5):
print(a1, a2, a3, a4, a5)
Отлично! Эти значения и есть пропущенные числа в таблице истинности.
Вместо вывода значений сформируем список кортежей, представляющий таблицу истинности. Известные числа запишем в соответствующие позиции, а пропуски последовательно заполним переменными a.
Предположим, что в условии дана такая таблица:
Заполним все пустые ячейки:
Ну а в коде это будет выглядеть так:
from itertools import product
for a1, a2, a3, a4, a5 in product([0, 1], repeat=5):
table = [(1, 1, a1, a2),
(a3, 0, 0, a4),
(1, a5, 1, 1)]
Таким образом, на каждой итерации цикла мы будем получать «предполагаемую» таблицу истинности. Но есть один нюанс!
По условию фрагмент состоит из различных строк, поэтому одинаковые наборы значений нужно отбросить. Наш код пока этого не проверяет. Решение простое: сравним количество строк с количеством уникальных строк:
if len(table) == len(set(table)):
Мы превращаем список в множество, которое автоматически удаляет дубликаты. Если длина не изменилась, все строки различны и такой вариант можно проверять дальше.
После проверки переходим к следующему этапу — подбору имён переменных.
Теперь таблица заполнена, но неизвестно, какой столбец соответствует x, y, z или w. Нужно перебрать все порядки букв. Для этого идеально подходит функция permutations() из того же itertools.
Эта функция вернёт нам 24 варианта перестановок букв x, y, z, w, которые мы будем поочерёдно перебирать в цикле for:
from itertools import permutations, product
for a1, a2, a3, a4, a5 in product([0, 1], repeat=5):
table = [(1, 1, a1, a2),
(a3, 0, 0, a4),
(1, a5, 1, 1)]
if len(table) == len(set(table)):
for p in permutations('xyzw'):
Осталась ключевая часть — самая важная и одновременно самая сложная для понимания. Имея таблицу и предполагаемую расстановку букв, нужно проверить, подходят ли наши значения под логическую функцию из условия.
Для начала, конечно же, нужно написать саму логическую функцию. Сделаем это в виде отдельной функции f() и предположим, что нам дана вот такая функция в условии: F = (x ∨ y)∧ ¬ (y ≡ z) ∧ ¬ w. Записывается это так:
def f(x, y, z, w):
return (x or y) and not (y == z) and not w
Вставим этот код в нашу программу:
from itertools import permutations, product
def f(x, y, z, w):
return (x or y) and not (y == z) and not w
for a1, a2, a3, a4, a5 in product([0, 1], repeat=5):
table = [(1, 1, a1, a2),
(a3, 0, 0, a4),
(1, a5, 1, 1)]
if len(table) == len(set(table)):
for p in permutations('xyzw'):
Теперь подставим числа из каждой строки таблицы в функцию f(), но в порядке, заданном текущей перестановкой p.
Сразу покажем код, а затем разберём его:
from itertools import permutations, product
def f(x, y, z, w):
return (x or y) and not (y == z) and not w
for a1, a2, a3, a4, a5 in product([0, 1], repeat=5):
table = [(1, 1, a1, a2),
(a3, 0, 0, a4),
(1, a5, 1, 1)]
if len(table) == len(set(table)):
for p in permutations('xyzw'):
u = [f(**dict(zip(p, t))) for t in table] == [0, 0, 0]
Что происходит в последней строке:
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])
Если всё совпало, выводим текущую перестановку:
from itertools import permutations, product
def f(x, y, z, w):
return (x or y) and not (y == z) and not w
for a1, a2, a3, a4, a5 in product([0, 1], repeat=5):
table = [(1, 1, a1, a2),
(a3, 0, 0, a4),
(1, a5, 1, 1)]
if len(table) == len(set(table)):
for p in permutations('xyzw'):
u = [f(**dict(zip(p, t))) for t in table] == [0, 0, 0]
if u:
print(*p)
Этот первый фрагмент нужен только для разбора устройства алгоритма. Учебная таблица здесь не гарантирует единственный ответ, поэтому запускать её как готовое экзаменационное решение не нужно. Ниже мы применим шаблон к полноценным условиям.
Готово! Теперь создадим универсальный шаблон:
from itertools import permutations, product
def f(x, y, z, w):
return 'Логическое выражение из условия'
# Количество переменных = количеству пустых ячеек
# Значение repeat = количеству переменных
for a1, a2, a3, a4, a5 in product([0, 1], repeat=5):
table = '''Таблица из условия
пропуски заменяем
переменными a'''
if len(table) == len(set(table)):
for p in permutations('xyzw'):
u = ([f(**dict(zip(p, t))) for t in table] == 'Значение логического выражения')
if u:
print(*p)
Этот шаблон готов к использованию — меняются только части, выделенные жёлтым цветом под конкретную задачу.
Давайте опробуем этот код на задании с такой формулировкой:
Миша заполнял таблицу истинности логической функции F = (w ≡ z) ∨ ¬(y → w) ∨ ¬x, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
F
0
1
0
0
1
1
0
0
0
0
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Импортируем нужные функции и перепишем логическое выражение из условия в виде функции:
from itertools import permutations, product
def f(x, y, z, w):
return (w == z) or not (y <= w) or not x
Далее нам нужно заполнить пустые ячейки таблицы из условия следующим образом:
И то же самое добавим в код:
from itertools import permutations, product
def f(x, y, z, w):
return (w == z) or not (y <= w) or not x
for a1, a2, a3, a4, a5 in product([0, 1], repeat=5):
table = [(a1, 0, 1, 0),
(a2, 1, 1, a3),
(0, a4, a5, 0)]
Теперь допишем оставшуюся часть кода:
from itertools import permutations, product
def f(x, y, z, w):
return (w == z) or not (y <= w) or not x
for a1, a2, a3, a4, a5 in product([0, 1], repeat=5):
table = [(a1, 0, 1, 0),
(a2, 1, 1, a3),
(0, a4, a5, 0)]
if len(table) == len(set(table)):
for p in permutations('xyzw'):
u = [f(**dict(zip(p, t))) for t in table] == [0, 0, 0]
if u:
print(*p)
Смело запускаем его и получаем такую строку: zwxy. Она и будет ответом на это задание.
Пример 1
Решим ещё одно задание этим методом:
Миша заполнял таблицу истинности логической функции F = ¬(y → (x ≡ z)) ∧ (w → x), но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w,x,y,z.
F
0
0
1
0
0
1
1
1
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Как и в прошлый раз импортируем функции и переписываем логическое выражение:
from itertools import permutations, product
def f(x, y, z, w):
return not (y <= (x == z)) and (w <= x)
Добавляем цикл с перебором значений пустых ячеек:
from itertools import permutations, product
def f(x, y, z, w):
return not (y <= (x == z)) and (w <= x)
for a1, a2, a3, a4, a5, a6, a7 in product([0, 1], repeat=7):
table = [(a1, 0, 0, a2),
(0, a3, 0, a4),
(a5, 1, a6, a7)]
И последнюю часть с проверкой:
from itertools import permutations, product
def f(x, y, z, w):
return not (y <= (x == z)) and (w <= x)
for a1, a2, a3, a4, a5, a6, a7 in product([0, 1], repeat=7):
table = [(a1, 0, 0, a2),
(0, a3, 0, a4),
(a5, 1, a6, a7)]
if len(table) == len(set(table)):
for p in permutations('xyzw'):
u = [f(**dict(zip(p, t))) for t in table] == [1, 1, 1]
if u:
print(*p)
Запускаем этот код и видим на экране ответ: zxwy.
Пример 2
И для закрепления решим ещё одно задание:
Миша заполнял таблицу истинности логической функции F = ¬(w → (x ≡ y)) ∧ (z → x), но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w,x,y,z.
F
0
1
0
1
0
0
1
1
1
1
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
В этот раз уже не будем подробно останавливаться на каждой части кода и напишем его целиком:
from itertools import permutations, product
def f(x, y, z, w):
return not (w <= (x == y)) and (z <= x)
for a1, a2, a3, a4, a5 in product([0, 1], repeat=5):
table = [(a1, 0, 1, 0),
(0, a2, a3, 0),
(a4, 1, 1, a5)]
if len(table) == len(set(table)):
for p in permutations('xyzw'):
u = [f(**dict(zip(p, t))) for t in table] == [1, 1, 1]
if u:
print(*p)
Запустив его, получим нужный нам ответ: yxwz.
Как видите, ничего сложного в использовании этого универсального кода нет. Достаточно лишь правильно переписать логическое выражение из условия, соблюдая порядок операций. Остальное программа сделает за вас и выдаст верный ответ.
Итоги
Перед запуском универсального кода проверьте: количество переменных a совпадает с числом пустых ячеек, каждая из них использована ровно один раз, строки таблицы различны, а список результатов F совпадает с последним столбцом условия.
Если программа выводит несколько разных перестановок, не выбирайте ответ наугад. Сначала проверьте логическое выражение, таблицу и значение функции: в корректно переписанном задании ответ должен определяться однозначно.
А попрактиковаться в решении заданий данного типа вы можете в нашем тренажёре.
Разберём эту тему на бесплатном пробном занятии
Преподаватель покажет, как решать такие задачи, и подскажет, с чего начать подготовку. Группы до 8 человек, очно в Калининграде и онлайн.
Мы используем файлы cookie. Необходимые обеспечивают работу сайта: корзину и вход в личный кабинет. С вашего согласия мы также используем сервис Яндекс Метрика, чтобы анализировать посещаемость и улучшать сайт.
Подробнее — в политике конфиденциальности.
