Логическая функция F задаётся выражением (x → y) ∧ (y ≡ ¬z) ∧ (z ∨ w). На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.
| ? | ? | ? | ? | F |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | |
| 1 | 1 | 1 | ||
| 1 | 1 |
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Заметим, что, чтобы выражение было истинным, выражения во всех скобках должны быть истинными.
Рассмотрим первую строку таблицы истинности. Для того чтобы первая скобка была истинной, переменная y должна быть равна единице. Тогда скобка (y ≡ ¬z) будет принимать значение 1 только при z = 0. Значит, переменной z соответствует третий столбец таблицы истинности.
Рассмотрим вторую строку таблицы истинности. Переменная z = 1, тогда скобка (y ≡ ¬z) будет принимать значение истинности только при y = 0. Чтоб скобка (x → y) принимала значение 1, x не должна равняться 1. Значит, переменной w соответствует второй столбец таблицы.
Рассмотрим третью строку таблицы истинности. Предположим, что первому столбцу таблицы истинности соответствует переменная x, тогда выражение может быть истинным только при x = 1, y = 1, z = 0, w = 1, но такой набор соответствует первой строке таблицы, а строки не должны повторяться. При любых других значениях, стоящих в остальных столбцах, значение выражения будет ложным. Следовательно, первому столбцу соответствует переменная y, а четвёртому — переменная x.
Приведём другое решение.
Составим таблицу истинности для выражения (x → y) ∧ (y ≡ ¬z) ∧ (z ∨ w) вручную или при помощи языка 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(x) or y) and (y == (not(z))) and (z or w):
print(x, y, z, w)
Далее выпишем те наборы переменных, при которых данное выражение равно 1. В наборах переменные запишем в порядке х, y, z, w. Получим следующие наборы:
(0, 0, 1, 0),
(0, 0, 1, 1),
(0, 1, 0, 1),
(1, 1, 0, 1).
Сопоставим эти наборы с приведенным в задании фрагментом таблицы истинности.
Первая строка таблицы истинности (как минимум три единицы) может соответствовать только набору (1, 1, 0, 1). Следовательно, третий столбец соответствует переменной z.
Рассмотрим вторую строку таблицы истинности. В ней переменная z равна 1, и есть еще одна переменная, равная 1. Следовательно, вторая строка может соответствовать только набору (0, 0, 1, 1), тогда второй столбец соответствует переменной w.
Заметим, что переменная, стоящая в первом столбце таблицы, принимает значение 1 как минимум в двух наборах значений. Следовательно, первый столбец не может соответствовать переменной x, принимающей единичное значение только в одном наборе.
Тогда первый столбец — это у, а четвертый столбец — это x.
Ответ: ywzx.