Задача
Миша заполнял таблицу истинности логической функции F
но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Функция F задана выражением
зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.
В этом случае первому столбцу соответствует переменная y, в второму столбцу - переменная x. В ответе следует написать: xy.
Решение (аналитическое)
Поскольку логическая функция состоит из двух частей соединенных конъюнкцией (логическое умножение), то результат 1 может быть тогда и только тогда, когда все части выражения истинны:
Рассмотрим первую часть логической функции:
Инверсия истинная тогда, когда подинверсионное выражение ложно:
Вспомним таблицы истинности импликации и эквиваленции:
Таким образом получаем, что:
Рассмотрим вторую часть логической функции:
Поскольку таблицу истинности импликации была рассмотрена выше, то получаем:
Теперь нам необходимо сопоставить две полученные части таблицы истинности, чтобы получить итоговую. Именно эту таблицу мы будем сравнивать с условием.
В исходной таблице третий столбец не содержит нулей, это y.
Четвертый столбец содержит два нуля - z.
Первая строка содержит три единицы - первый столбец w.
Следовательно, второй столбец - x.
Ответ: wxyz.
Решение (программа, Python)
Импликацию в логической функции мы заменим на <=, знак эквиваленции (≡) - логическим равно (==), инверсия (¬) соответствует логическому оператору not(), конъюнкция - and.
Во вложенных циклах мы будем перебирать значения переменных (x, y, z, w) и проверять, соответствует ли результат логической функции истине.
Программа на языке программирования Python будет иметь следующий вид:
print('x y z w')
for x in 0,1:
for y in 0,1:
for z in 0,1:
for w in 0,1:
if (not(y <= (x == w)) and (z <= x)) == 1:
print(x,y,z,w)
Программа напечатает следующее подобие таблицы истинности:
В исходной таблице третий столбец не содержит нулей, это y.
Четвертый столбец содержит два нуля - z.
Первая строка содержит три единицы - первый столбец w.
Следовательно, второй столбец - x.
Ответ: wxyz.