Алгебра логики. Задача 4-37*

Логическая функция F задаётся выражением ((x→y)→z)→¬x  На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий не повторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z.

? ? ? F
1 1   1
  1 1 1
1     1

В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Ответ
zyx
Решение

Преобразуем выражение: \( ((x→y)→z)→\overline{x} = ((\overline{x} + y)→z)→\overline{x} = (\overline{(\overline{x} + y)} + z)→\overline{x}  =  \overline{ (\overline{(\overline{x} + y)} + z) } + \overline{x} =  (\overline{x} + y)⋅ \overline{z} + \overline{x} \)

В первой строке не заполнен столбец 3, Предположим, что там 1, то есть все переменные равны 1, подставим в выражение: \( (\overline{1} + 1)⋅ \overline{1} + \overline{1} =  (0+1)⋅0+0 = 0 \). Но в таблице значение функции равно 1, поэтому в первой строке, в третьем столбце может быть только 0.

Аналогично рассуждая, приходим к выводу, что во второй строке, в первом столбце может быть только 0.

В третьей строке, во втором столбце может быть только 0, потому что набор 1, 1, 1 противоречит значению функции, а набор 1,1,0 уже есть в первой строке. Полученная таблица:

? ? ? F
1 1 0 1
0 1 1 1
1 0   1

Логическое выражение представляет собой дизъюнкцию, поэтому оба ее члена не должны быть равны 0 одновременно на наборах данных таблицы. Следовательно, при x = 1, z и y  должны быть равны 0 и 1 соответственно.

Предположим, что x соответствует первому столбцу, тогда  z - третий столбец, а  y  - второй. Но для третьей строки, если подставить  x = 1, y = 0  в выражение, получим его значение равно 0, при любом значении в третьем столбце для  z .

Предположим, что x соответствует третьему столбцу, тогда z - первый столбец, а y - второй. Если подставить значения третьей строки z = 1, y = 0  в выражение, то его значение будет равно 1, при  x = 0  в третьем столбце.

Ответ: zyx