В статье показано решение одной задачи, которую меня попросили посмотреть.

Постановка задачи

Логическая функция $F$ задаётся выражением $(x \equiv (w \lor y)) \lor ((w \rightarrow z ) \land (y \rightarrow w))$.

Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции $F$.

Определите, какому столбцу таблицы истинности соответствует каждая из переменных $x$, $y$, $z$, $w$.

Переменная 1 Переменная 2 Переменная 3 Переменная 4 Функция
$?$ $?$ $?$ $?$ $F$
1     1 0
      1 0
1   1   0

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

Решение

Разбор выражения

Выражение $(x \equiv (w \lor y)) \lor ((w \rightarrow z) \land (y \rightarrow w))$ состоит из двух частей, соединенных операцией дизъюнкцией (логическое «ИЛИ»).

Так как в таблице все строки таблицы истинности равны $0$ (последний столбец), то, значит, обе части выражения $x \equiv (w \lor y)$ и $(w \rightarrow z) \land (y \rightarrow w)$ должны быть равные $0$, так как, если бы кто-то них был равен $1$, то выражение стало бы равным $F = 1$.

Чаще всего в выражениях используется переменная $w$, поэтому её и будем анализировать.

Первый случай

Пусть $w = 0$.

Тогда выражение $x \equiv (w \lor y)$ примет вид: $x \equiv (0 \lor y)$. Тут возможно два варианта:

Пусть $y = 0$.

Тогда $0 \lor y = 0 \lor 0 = 0$. Значит, чтобы $x \equiv 0$ было ложным, нужно, чтобы $x = 1$.

Пусть $y = 1$.

Тогда $0 \lor y = 0 \lor 1 = 1$. Значит, чтобы $x \equiv 1$ было ложным, нужно, чтобы $x = 0$.

Рассмотрим вторую часть выражения $(w \rightarrow z) \land (y \rightarrow w)$, которое также должно быть ложным. Так как мы считаем, что $w = 0$, то оно превращается в $(0 \rightarrow z) \land (y \rightarrow 0)$.

Так как две импликации соединены конъюнкцией, то для того, чтобы выражение было ложным, достаточно ложности хотя бы одной импликации.

Надо помнить, что импликация бывает ложной только в одном случае: $1 \rightarrow 0 = 0$.

Отсюда следует, что $(0 \rightarrow z)$ не может быть ложным ни при каких значениях $z$. Значит ложным должна быть импликация $y \rightarrow 0$. А это возможно только в случае, если $y = 1$.

Выше при рассматривании выражения $x \equiv (w \lor y)$ мы рассматривали два случая: когда $y = 0$ и когда $y = 1$. Но после рассмотрения выражения $(w \rightarrow z) \land (y \rightarrow w)$ вариант $y = 0$ можно исключить.

Из этих размышлений можно формулировать следующий вывод.

Вывод 1

Если $w = 0$, то $y = 1$, $x = 0$.

Второй случай

Пусть $w = 1$.

Тогда выражение $x \equiv (w \lor y)$ пр имеет вид: $x \equiv (1 \lor y)$. Так как в правой части используется дизъюнкция, то правая часть всегда будет истинной при любых значениях $y$. Значит, чтобы выражение было ложным, левая часть должна быть ложной, то есть $x = 0$.

Рассмотрим выражение $(w \rightarrow z) \land (y \rightarrow w)$, которое также должно быть ложным. Так как мы считаем, что $w = 1$, то оно превращается в $(1 \rightarrow z) \land (y \rightarrow 1)$.

Из свойств импликации следует, что вторая импликация никогда не может быть ложной. Следовательно, для ложности выражения необходима ложность первой импликации $1 \rightarrow z$, а это возможно только в случае $z = 0$.

Из вышесказанного можно сформулировать следующий вывод:

Вывод 2

Если $w = 1$, то $x = 0$, $z = 0$.

Эти два вывода будем использовать для анализа таблицы истинности.

Разбор таблицы истинности

В предыдущей части мы взяли за основу переменную $w$. Её и возьмём для анализа таблицы истинности.

Первый столбец

Пусть $w$ располагается в первом столбце таблицы истинности:

Переменная 1 Переменная 2 Переменная 3 Переменная 4 Функция
$w$ $?$ $?$ $?$ $F$
1     1 0
      1 0
1   1   0

По второму выводу следует, что, если $w = 1$, то минимум две переменных должно быть равно $0$ ($x = 0$, $z = 0$).

Так как в первой строке $w = 1$, а четвертый столбец занят $1$, то, значит, второй и третий столбец должны быть равны $0$. И какой-то из этих столбцов будет содержать переменную $x$, а какой-то $z$. То есть, из первой строки следует, что, если, первый столбец равен $1$, то второй и третий равны $0$.

Но третья строка также содержит значение $w = 1$, а третий столбец содержит значение, равное $1$. А согласно первой строке, там должен находится $0$.

Мы пришли к противоречию. Значит, $w$ не может располагаться в первом столбце.

Второй столбец

Пусть $w$ располагается во втором столбце таблицы истинности:

Переменная 1 Переменная 2 Переменная 3 Переменная 4 Функция
$?$ $w$ $?$ $?$ $F$
1     1 0
      1 0
1   1   0

Пусть в первой строке $w = 1$:

Переменная 1 Переменная 2 Переменная 3 Переменная 4 Функция
$?$ $w$ $?$ $?$ $F$
1 1   1 0
      1 0
1   1   0

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

Пусть в первой строке $w = 0$:

Переменная 1 Переменная 2 Переменная 3 Переменная 4 Функция
$?$ $w$ $?$ $?$ $F$
1 0   1 0
      1 0
1   1   0

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

Переменная 1 Переменная 2 Переменная 3 Переменная 4 Функция
$?$ $w$ $x$ $?$ $F$
1 0 0 1 0
      1 0
1   1   0

Но согласно первому и второму выводу $x$ всегда равен $0$, а в третьей строчке мы видим, что в третьем столбце $1$.

Мы пришли к противоречию. Значит, $w$ не может располагаться во втором столбце.

Третий столбец

Пусть $w$ располагается в третьем столбце таблицы истинности:

Переменная 1 Переменная 2 Переменная 3 Переменная 4 Функция
$?$ $?$ $w$ $?$ $F$
1     1 0
      1 0
1   1   0

Так как согласно обоим выводам $x = 0$, то только во втором столбце может располагаться $x$, так как во всех остальных есть хотя бы одна $1$:

Переменная 1 Переменная 2 Переменная 3 Переменная 4 Функция
$?$ $x$ $w$ $?$ $F$
1 0   1 0
  0   1 0
1 0 1   0

Рассмотрим последнюю строчку. В ней $w = 1$, следовательно, нужно два столбца, равных $0$. Второй занят для $x$, первый содержит $1$. Значит, $z = 0$ может располагаться только в четвертом столбце. А первый столбец тогда будет закреплен за оставшейся переменной $y$:

Переменная 1 Переменная 2 Переменная 3 Переменная 4 Функция
$y$ $x$ $w$ $z$ $F$
1 0   1 0
  0   1 0
1 0 1 0 0

Так как в первой строке только одно значение $0$, то $w$ может быть равен только $0$, так как при $w = 1$ нужно два нулевых значения:

Переменная 1 Переменная 2 Переменная 3 Переменная 4 Функция
$y$ $x$ $w$ $z$ $F$
1 0 0 1 0
  0   1 0
1 0 1 0 0

Во второй строчке $z = 1$, следовательно, w может быть равен только $0$:

Переменная 1 Переменная 2 Переменная 3 Переменная 4 Функция
$y$ $x$ $w$ $z$ $F$
1 0 0 1 0
  0 0 1 0
1 0 1 0 0

А из первого вывода следует, что $y = 1$ в таком случае:

Переменная 1 Переменная 2 Переменная 3 Переменная 4 Функция
$y$ $x$ $w$ $z$ $F$
1 0 0 1 0
1 0 0 1 0
1 0 1 0 0

Мы получили таблицу истинности с двумя одинаковыми строчками, что невозможно.

Мы пришли к противоречию. Значит, $w$ не может располагаться в третьем столбце.

Четвертый столбец

Пусть $w$ располагается в четвертом столбце таблицы истинности:

Переменная 1 Переменная 2 Переменная 3 Переменная 4 Функция
$?$ $?$ $?$ $w$ $F$
1     1 0
      1 0
1   1   0

Так как из двух выводов следует, что $x = 0$, то для этого есть только второй столбец, как мы выяснили выше. Следовательно, таблица истинности примет вид:

Переменная 1 Переменная 2 Переменная 3 Переменная 4 Функция
$?$ $x$ $?$ $w$ $F$
1 0   1 0
  0   1 0
1 0 1   0

Из второго вывода следует, что если $w = 1$, то $z = 0$. В первой строчке в первом столбце стоит $1$, во втором столбце находится $x$. Следовательно, для $z$ остается только третий столбец, а $y$ следом уходит в первый столбец:

Переменная 1 Переменная 2 Переменная 3 Переменная 4 Функция
$y$ $x$ $z$ $w$ $F$
1 0 0 1 0
  0   1 0
1 0 1   0

Можно на этом остановиться, то разберем все строчки таблицы истинности на всякий случай.

Во второй строке $w = 1$. Значит, по второму выводу $z = 0$:

Переменная 1 Переменная 2 Переменная 3 Переменная 4 Функция
$y$ $x$ $z$ $w$ $F$
1 0 0 1 0
  0 0 1 0
1 0 1   0

Если во второй строке $y = 1$, то получим две одинаковые строчки в таблице истинности, что допустить нельзя. Проверим наше главное выражение $(x \equiv ( w \lor y)) \lor ((w \rightarrow z ) \land (y \rightarrow w))$ для второй строчки при $y = 0$: $(0 \equiv ( 1 \lor 0)) \lor ((1 \rightarrow 0 ) \land (0 \rightarrow 1)) = (0 \equiv 1) \lor (0 \land 1) = 0 \lor 0 = 0$. То есть получаем ложное выражение, как нам и нужно. Следовательно, мы можем вот так заполнить вторую строчку:

Переменная 1 Переменная 2 Переменная 3 Переменная 4 Функция
$y$ $x$ $z$ $w$ $F$
1 0 0 1 0
0 0 0 1 0
1 0 1   0

Осталась последняя строка.

Пусть $w = 0$.

Тогда $(x \equiv ( w \lor y)) \lor ((w \rightarrow z ) \land (y \rightarrow w)) = (0 \equiv ( 0 \lor 1)) \lor ((0 \rightarrow 1 ) \land (1 \rightarrow 0)) = (0 \equiv 1) \lor (1 \land 0) = 0 \lor 0 = 0$.

Пусть $w = 1$.

Тогда $(x \equiv ( w \lor y)) \lor ((w \rightarrow z ) \land (y \rightarrow w)) = (0 \equiv ( 1 \lor 1)) \lor ((1 \rightarrow 1 ) \land (1 \rightarrow 1)) = (0 \equiv 1) \lor (1 \land 1) = 0 \lor 1 = 1$.

Получается, что при $w = 1$ мы получаем истину, хотя должны были получить ложь. А при $w = 0$ получаем ожидаемую ложь. Следовательно, $w = 0$:

Переменная 1 Переменная 2 Переменная 3 Переменная 4 Функция
$y$ $x$ $z$ $w$ $F$
1 0 0 1 0
0 0 0 1 0
1 0 1 0 0

То есть мы смогли расставить все переменные по столбцам и получить однозначную заполненную таблицу истинности.

Ответ

$yxzw$