Логическая функция F задаётся выражением ((x ∨ ¬y) ∧ (¬z ≡ w)) → (y ∧ z). На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.
| ? | ? | ? | ? | F |
|---|---|---|---|---|
| 1 | 1 | 1 | 0 | |
| 0 | 0 | 0 | 0 | |
| 0 | 1 | 0 |
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Рассмотрим первую строку таблицы истинности. Заметим, что одна из переменных y и z должна принимать значения 0. Если переменная y будет равна 0, тогда скобка (y ∧ z) тоже будет равна 0, но вторая часть выражения ((x ∨ ¬y) ∧ (¬z ≡ w)) будет принимать значение 0, и тогда импликация примет значение 1. Значит, второму столбцу соответствует переменная z, и в первой строке во втором столбце будет стоять значение 0.
Рассмотрим вторую строку таблицы истинности. Скобка (y ∧ z) равна 0. Заметим, что, чтобы скобка ((x ∨ ¬y) ∧ (¬z ≡ w)) была равна 0, переменная w должна быть равна 1. Значит, третьему столбцу таблицы истинности соответствует переменная w, и во второй строке в третьем столбце будет стоять значение 1.
Рассмотрим третью строку таблицы истинности. Она может выглядеть так: 0001, 0101 или 0111. Предположим, что первому столбцу таблицы истинности соответствует переменная x. Тогда во всех трёх случаях выражение будет истинным. Значит, первому столбцу таблицы истинности соответствует переменная y, а четвёртому — x.
Ответ: yzwx.
Приведем другое решение.
Составим таблицу истинности для выражения ((x ∨ ¬y) ∧ (¬z ≡ w)) → (y ∧ z) вручную или при помощи языка Python:
print("x y z w")
for x in range(0, 2):
for y in range(0, 2):
for z in range(0, 2):
for w in range(0, 2):
if not(not((x or not(y)) and (not(z) == w)) or (y and z)):
print(x, y, z, w)
Далее выпишем те наборы переменных, при которых данное выражение равно 0. В наборах переменные запишем в порядке х, y, z, w. Получим следующие наборы:
(0, 0, 0, 1),
(0, 0, 1, 0),
(1, 0, 0, 1),
(1, 0, 1, 0),
(1, 1, 0, 1).
Сопоставим эти наборы с приведенным в задании фрагментом таблицы истинности.
Первая строка таблицы может соответствовать только набору (1, 1, 0, 1). Следовательно, во втором столбце первой строки стоит 0 и второй столбец соответствует переменной z.
Вторая строка может соответствовать только набору (0, 0, 0, 1). Следовательно, в третьем столбце второй строки стоит 1 и третий столбец соответствует переменной w.
Третья строка может соответствовать как набору (1, 0, 0, 1), так и набору (1, 0, 1, 0). В обоих наборах переменная x принимает значение 1, а переменная y принимает значение 0. Следовательно, переменная x соответствует четвертому столбцу таблицы, а переменная y — первому столбцу. Получаем последовательность yzwx.
Примечание.
В программе избавляемся от импликации используя свойство импликации: x → y = ¬x + y.