Логическая функция F задаётся выражением ((x ∧ y) ∨ (y ∧ z)) ≡ ((x → w) ∧ (w → z)).
Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F.
Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.
| Переменная 1 | Переменная 2 | Переменная 3 | Переменная 4 | Функция |
|---|---|---|---|---|
| ??? | ??? | ??? | ??? | F |
| 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | |
| 0 | 1 | 0 | 1 |
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:
| Переменная 1 | Переменная 1 | Функция |
|---|---|---|
| ??? | ??? | F |
| 0 | 1 | 0 |
Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.
Поскольку строки в таблице не должны повторяться, заполним пустые ячейки в таблице:
| Переменная 1 | Переменная 2 | Переменная 3 | Переменная 4 | Функция |
|---|---|---|---|---|
| ??? | ??? | ??? | ??? | F |
| 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 |
Рассмотрим данное выражение. Логическая функция принимает значение 1, когда обе части выражения принимают значения 1 или 0. Первая часть выражения принимает значение 1 при наборах переменных x, y, z, равных соответственно 011, 110, 111. Вторая часть выражения принимает значение 1 при наборах переменных x, z, w, равных соответственно 000, 010, 011, 111. Первая часть выражения принимает значение 0 при наборах переменных x, y, z, равных соответственно 000, 001, 010, 100, 101. Вторая часть выражения принимает значение 0 при наборах переменных x, z, w, равных соответственно 001, 100, 110, 101. Заметим, что x соответствует первому столбцу таблицы истинности, а z и y — третьему и четвёртому столбцам таблицы истинности. Значит, второму столбцу таблицы истинности соответствует w.
Ответ: xwzy.
Приведем другое решение.
Составим таблицу истинности для выражения (x ∧ y) ∨ (y ∧ z)) ≡ ((x → w) ∧ (w → 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 ((x and y) or (y and z)) == ((x <= w) and (w <=z)):
print(x, y, z, w)
Далее выпишем те наборы переменных, при которых данное выражение равно 1. В наборах переменные запишем в порядке х, y, z, w.
Получим следующие наборы:
(0, 0, 0, 1)
(0, 1, 0, 1)
(0, 1, 1, 0)
(0, 1, 1, 1)
(1, 0, 0, 0)
(1, 0, 0, 1)
(1, 0, 1, 0)
(1, 1, 1, 1)
Заметим, что имеется только один набор, содержащий ровно три единицы: (0, 1, 1, 1). Этому набору соответствует первая строка приведенного фрагмента таблицы истинности. Следовательно, первый столбец соответствует переменной x. Тогда третья строка фрагмента таблицы соответствует набору (0, 0, 0, 1). Следовательно, второй столбец — это переменная w.
Тогда вторая строка фрагмента таблицы соответствует набору (0, 1, 0, 1). Следовательно, третий столбец — это переменная z, а четвертый столбец — переменная y.
Приведем решение Михаила Глинского.
Заполним пустые ячейки в таблице, как это сделано в основном решении.
Составим таблицу истинности для выражения ((x ∧ y) ∨ (y ∧ z)) ≡ ((x → w) ∧ (w → z)) и выпишем те наборы переменных, при которых данное выражение равно 1. В наборах будем записывать переменные в порядке x, y, z, w. Получим следующие наборы:
(0, 0, 0, 1)
(0, 1, 0, 1)
(0, 1, 1, 0)
(0, 1, 1, 1)
(1, 0, 0, 0)
(1, 0, 0, 1)
(1, 0, 1, 0)
(1, 1, 1, 1)
Заметим, что имеется только один набор, содержащий ровно три единицы: (0, 1, 1, 1). Этому набору соответствует первая строка приведенного фрагмента таблицы истинности. Следовательно, первый столбец соответствует переменной x. Тогда третья строка фрагмента таблицы соответствует набору (0, 0, 0, 1). Следовательно, второй столбец — это переменная w.
Тогда вторая строка фрагмента таблицы соответствует набору (0, 1, 0, 1). Следовательно, третий столбец — это переменная z, а четвертый столбец — переменная y.
Для составления таблицы истинности можно воспользоваться программой на языке Паскаль:
var x,y,z,w: boolean;
begin
for x:=false to true do
for y:=false to true do
for z:=false to true do
for w:=false to true do
if((x and y) or (y and z)) = ((x<=w) and (w<=z)) then
writeln(ord(x), ord(y),ord(z), ord(w));
end.