Сложные логические выражения

Заметим, что во всех трех строках \(F = 1.\) Чтобы конъюнкция была истинна (все высказывания, входящие в нее, должны быть истинны), \(w\) всегда должна равняться единице. Этому условию соответствует только первый столбец, т.к в других присутствует хотя бы один ноль. Также \(x \vee\overline y\) и \(\overline {w \equiv z}\) должны быть истинны, чтобы конъюнкция была истинна.

Если \((\overline {w \equiv z}) = 1,\) то \((w \equiv z) = 0.\)

Мы уже знаем, что \(w = 1.\) Тогда чтобы операция эквивалентности \(w \equiv z\) была ложна, \(z\) должна быть равна 0 (операция эквивалентности ложна, если одно высказывание, входящее в нее, ложно, а другое истинно). Тогда \(z\) — это второй или третий столбец, потому что первый — это уже \(w,\) а в четвертом во второй строке содержится единица.

Рассмотрим вторую строчку. Её удобно рассматривать, так как нам известно, что в первом столбце будет единица (так как он соответствует \(w),\) значит, нам известны все значения в этой строке. Таким образом, в этой строке две единицы и два нуля. Если \(y = 1,\) то \(x = 0\) (так как в строке всего две единицы, которые при таком предположении уже соответствуют \(w\) и \(y).\) Но тогда \(x \vee \overline y = 0 \vee 0 = 0.\) Такое нам не подходит, ведь функция \(F\) должна быть истинна. Значит, \(x\) должна быть равна 1. Она будет соответствовать четвертому столбцу.

Разберемся со вторым и третьим столбцами. Предположим, что \(z\) соответствует третьему столбцу, тогда \(y\) - это второй столбец. Рассмотрим первую строку. \(x = 0,\) значит, чтобы \(x \vee \overline y\) была истинна, \(\overline y\) должна быть равна 1 и \(y = 0.\) Тогда таблица истинности из условия будет выглядеть так:

\[\begin{array}{|c|c|c|c|c|} \hline w &y & z & x & F \\ \hline 1 & 0 & 0 & 0 & 1 \\ \hline 1 & 0 & 0 & 1 & 1 \\ \hline 1 & 0 & 0 & ??? & 1 \\ \hline \end{array}\]

Нам сказано, что в приведенном фрагменте таблицы истинности содержатся неповторяющиеся строки. Если \(x = 1,\) то третья строка будет совпадать со второй. Если \(x = 0,\) то третья строка будет совпадать с первой. Значит, наше предположение было неверным. Тогда второй столбец — это \(z,\) а третий — это \(y.\)

Тогда таблица будет выглядеть так:

\[\begin{array}{|c|c|c|c|c|} \hline w & z & y & x & F \\ \hline 1 & 0 & 0 & 0 & 1 \\ \hline 1 & 0 & 0 & 1 & 1 \\ \hline 1 & 0 & ??? & ??? & 1 \\ \hline \end{array}\]

Если \(y = 1,\) то \(x = 1\) (чтобы \(x \vee \overline y\) была истинна). Если \(y = 0,\) то \(x\) может быть любым (так как одно из высказываний, входящих в дизъюнкцию, уже истинно), но такие значения уже содержатся в первых двух строках.

Значит, итоговая таблица будет выглядеть так:

\[\begin{array}{|c|c|c|c|c|} \hline w & z &y & x& F\\ \hline 1 & 0 & 0 & 0 & 1 \\ \hline 1 & 0 & 0 & 1 & 1 \\ \hline 1 & 0 & 1 & 1 & 1 \\ \hline \end{array}\]

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

Операция эквивалентности \((w \equiv z)\) ложна, если одно высказывание ложно, а другое истинно.

Конъюнкция ложна, если ложно хотя бы одно из высказываний, входящих в нее.

Если \((w \equiv z) = 0,\) то \(w = 0\) и \(z = 1\) или \(w = 1\) и \(z = 0.\) Рассмотрим вначале случай, когда \(w = 1.\) Чтобы конъюнкция \(x \wedge w\) была ложна, \(x\) должна быть равна нулю (иначе \(1 \wedge 1 = 1).\) Чтобы эквивалентность была ложна, \(z = 0.\) Получили подходящий набор \((x,\) \(w,\) \(z)\): (0, 1, 0). Рассмотрим случай, когда \(w = 0.\) Теперь \(x\) может быть равен как нулю, так и единице, потому что одно из высказываний, входящих в конъюнкцию, уже ложно. Переменная \(z\) должна быть истинна, чтобы эквивалентность была ложна. Получили еще два подходящих набора: (0, 0, 1), (1, 0, 1).

Количество подходящих наборов совпадает с количеством строк в таблице истинности, что облегчает задачу. Заметим, что \(z\) истинна в двух наборах, в то время как \(x\) и \(w\) истинны только единожды. Значит, первому столбцу соответствует \(z.\)

Когда \(z = 0,\) то \(w = 1\) и \(y = 0.\) В первой строке (где \(z = 0)\) есть три нуля и одно неизвестное значение в четвертом столбце. Мы уже определили, что этой строке соответствует набор \((x,\) \(y,\) \(z,\) \(w)\) = (0, 0, 0, 1), значит, четвертому столбцу соответствует \(w.\) Тогда третьему столбцу соответствует \(y\) (такой вывод мы сделали из рассуждений в первом абзаце), а \(x\) — второму.

В приведенном фрагменте во всех строках \(F = 0.\) Функция представляет из себя два операнда дизъюнкции. Так как дизъюнкция ложна, если ложны все высказывания, входящие в нее, то (\((x \rightarrow y) \equiv (z \rightarrow w))\) = 0 и \(x \wedge w = 0.\)

Если \(((x \rightarrow y) \equiv (z \rightarrow w)) = 0,\) то одно из высказываний должно быть ложным, а другое истинным (так как операнды связаны между собой операцией эквивалентности). Каждый из операндов представляет собой импликацию, которая ложна, если из истины следует ложь, и истинна в остальных случаях.

Если \((x \rightarrow y) = 0,\) то \(x = 1,\) \(y = 0,\) а \((z \rightarrow w) = 1.\) Так как \(x \wedge w = 0,\) а \(x = 1,\) то \(w\) должна быть ложна (так как конъюнкция ложна, если ложно хотя бы одно из высказываний, входящих в нее). Тогда чтобы \((z \rightarrow w)\) была истинна, \(z\) тоже должна быть ложна (иначе \(1 \rightarrow 0 = 0).\) Значит, в таком случае \(x = 1, \; y = 0, \; w = 0, \; z = 0.\)

Если \((x \rightarrow y) = 1,\) то \((z \rightarrow w) = 0.\) Значит, \(z = 1, \; w = 0.\) Тогда \(x \wedge w = x \wedge 0 = 0\) при любом \(x.\) Составим таблицу истинности для \(z = 1\) и \(w = 0:\)

\[\begin{array}{|c|c|c|c|c|} \hline x&y & z & w & F\\ \hline 0 & 0 & 1 & 0 & 0 \\ \hline 0 & 1 & 1 & 0 & 0 \\ \hline 1 & 1 & 1 & 0 & 0 \\ \hline 1 & 0 & 1 & 0 & 1 \\ \hline \end{array}\]

Из таблицы видим, что нам не подходит только последняя строка, так как при таких \(x\) и \(y\) эквивалентность истинна, следовательно, одно из выражений, входящих в дизъюнкцию, тоже истинно.

Мы разобрали все случаи, при которых функция ложна. Выпишем строки таблицы истинности, где \(F = 0.\)

\[\begin{array}{|c|c|c|c|c|} \hline x&y & z & w & F\\ \hline 0 & 0 & 1 & 0 & 0 \\ \hline 0 & 1 & 1 & 0 & 0 \\ \hline 1 & 1 & 1 & 0 & 0 \\ \hline 1 & 0 & 0 & 0 & 0 \\ \hline \end{array}\]

Таблица 1.

Сопоставим таблицу 1 и фрагмент, приведенный в условии. Рассмотрим данную строку:

\[\begin{array}{|c|c|c|c|c|} \hline x&y & z & w & F\\ \hline 1 & 1 & 1 & 0 & 0 \\ \hline \end{array}\]

В ней все переменные равны 1 и только \(w = 0.\) В третьей строке фрагмента из условия тоже есть три единицы и один ноль. Значит, четвертый столбец — это \(w.\)

Аналогично и с этой строкой:

\[\begin{array}{|c|c|c|c|c|} \hline x&y & z & w & F\\ \hline 0 & 1 & 1 & 0 & 0 \\ \hline \end{array}\]

Во второй строке фрагмента из условия тоже две единицы. Мы уже знаем, что четвертому столбцу соответствует \(w,\) значит, третьему столбцу соответствует \(x,\) который должен быть равен нулю.

Осталось определить первый и второй столбцы. В фрагменте таблицы истинности из условия первый столбец всегда равен единице. Если внимательно посмотреть на таблицу 1, то можно увидеть, что \(z\) равна 1 в трех строках. Остальные переменные равны 1 в двух строках и менее. Значит, \(z\) - это первый столбец фрагмента таблицы истинности из условия. Так как переменных всего 4, а три мы уже определили, то второй столбец — это \(y.\)

Выражение содержит два операнда, связанных дизъюнкцией. В приведенном фрагменте \(F = 0\) во всех строках. Дизъюнкция ложна, если все высказывания, входящие в нее, ложны. Таким образом, нам необходимо, чтобы выполнялись следующие условия:

\(y \equiv (z \vee x) = 0\) (1)

\((z \rightarrow w) \wedge (x \rightarrow z) = 0\) (2)

Чтобы операция эквивалентности (1) была ложна, одно высказывание должно быть ложным, а другое истинным. Тогда \(y = 0\) и \(z \vee x = 1\) или \(y = 1\) и \(z \vee x = 0.\)

Рассмотрим вначале случай, когда \(y = 0.\) Тогда \(z \vee x\) должно быть истинно. Чтобы дизъюнкция была истинна, хотя бы одно из высказываний, входящих в нее, должно быть истинно, то есть \(z = 1\) и/или \(x = 1.\) Так как получается несколько случаев, составим таблицу истинности для \(y = 0\) и различных значений \(z\) и \(x.\)

\[\begin{array}{|c|c|c|c|c|} \hline x&y & z& z \vee x& y \equiv (z \vee x)\\ \hline 0 & 0 & 1 & 1 & 0 \\ \hline 0 & 0 & 0 & 0 & 1 \\ \hline 1 & 0 & 1 & 1 & 0 \\ \hline 1 & 0 & 0 & 1 & 0 \\ \hline \end{array}\]

Видим, что \((y \equiv (z \vee x)) = 0\) для следующих наборов \((y,\) \(z,\) \(x:)\) (0, 1, 0), (0, 0, 1), (0, 1, 1).

Проверим, ложно ли \((z \rightarrow w) \wedge (x \rightarrow z)\) при данных значениях \((y,\) \(z,\) \(x).\)

Конъюнкция (2) ложна, если хотя бы одно высказывание, входящее в нее, ложно, значит, \(z \rightarrow w = 0\) и/или \(x \rightarrow z = 0.\) Импликация ложна, если из истины следует ложь \((1 \rightarrow 0),\) и истинна во всех остальных случаях. Подставим первый набор \((y,\) \(z,\) \(x)\) = (0, 1, 0) в (2): \((1 \rightarrow w) \wedge (0 \rightarrow 1) = 1 \rightarrow w.\) Чтобы одно из высказываний, входящих в конъюнкцию, было ложно, \(w = 0\) (иначе \(1 \wedge 1 = 1).\) Значит, нам подходит такой набор \((x, \; y, \; z, \; w)\) = (0, 0, 1, 0). Подставим второй набор (0, 0, 1) в (2): \((0 \rightarrow w) \wedge (1 \rightarrow 0) = 1 \wedge 0 = 0.\) Так как \(0 \rightarrow w\) истинно при любом \(w,\) то есть еще два подходящих набора: (1, 0, 0, 0) и (1, 0, 0, 1). Наконец, подставим третий набор (0, 1, 1): \((1 \rightarrow w) \wedge (0 \rightarrow 1) = (1 \rightarrow w) \wedge 1 = (1 \rightarrow w.\) Если \(w = 0,\) то \(1 \rightarrow w = 1 \rightarrow 0 = 0.\) Еще один подходящий набор (1, 0, 1, 0). Если \(w = 1,\) то \(1 \rightarrow w = 1 \rightarrow 1 = 1,\) что нам не подходит.

Теперь рассмотрим случай, когда \(y = 1.\) Чтобы высказывание (1) было ложно, \(z \vee x\) должно быть ложно. Дизъюнкция ложна, если ложны все высказывания, входящие в нее, значит \(z = 0\) и \(x = 0.\) Подставим в (2): \((0 \rightarrow w) \wedge (0 \rightarrow 0) = 1 \wedge 1 = 1.\) Получается, что (2) истинно при любом значении \(w,\) что нам не подходит.

Выпишем строки таблицы истинности, где \(F = 0.\)

\[\begin{array}{|c|c|c|c|c|} \hline x&y & z & w & F\\ \hline 0 & 0 & 1 & 0 & 0\\ \hline 1 & 0 & 0 & 0 & 0\\ \hline 1 & 0 & 0 & 1 & 0 \\ \hline 1 & 0 & 1 & 0 & 0\\ \hline \end{array}\]

Таблица (*).

Видим, что во всех четырех строках составленной таблицы истинности \(y = 0.\) Единственным столбцом фрагмента таблицы истинности из условия, в котором нет нулей, является второй. Значит, второму столбцу соответствует \(y.\)

Также заметим, что в фрагменте таблицы истинности из условия во всех столбцах, кроме второго и третьего, по две единицы. Если посмотреть на таблицу (*), то увидим, что \(w = 1\) только в одной строке. Так как второй столбец — это \(y,\) то третий - это \(w.\)

Мы можем определить, что третья строка фрагмента соответствует второй строке таблицы (*) (так как там \(w = 1).\)

\[\begin{array}{|c|c|c|c|c|} \hline x&y & z & w & F\\ \hline 1 & 0 & 0 & 1 & 0\\ \hline \end{array}\]

Тогда в четвертом столбце должен быть ноль. В этой строке только две переменных равны нулю \((z\) и \(y),\) но соответствие \(y\) уже определено. Значит, четвертому столбцу соответствует \(z.\)

Тогда \(x\) — это первый столбец.

Упростим \((x \vee y) \wedge (\overline x \vee y) \wedge (\overline x \vee \overline y).\) По закону дистрибутивности \((x \vee y) \wedge (\overline x \vee y)\) = \(y \vee (x \wedge \overline x).\) \(x \wedge \overline x = 0\) при любом значении \(x\) (если \(x = 0,\) то \(\overline x = 1\) и \(1 \wedge 0 = 0.\) Если \(x = 1,\) то \(\overline x = 0\) и \(0 \wedge 1 = 0).\) Тогда \(y \vee (x \wedge \overline x) = y \vee 0 = y.\) Теперь упрощаемое выражение выглядит так: \(y \wedge (\overline x \vee \overline y).\) По закону дистрибутивности это равносильно \((y \wedge \overline x) \vee (y \wedge \overline y) = (y \wedge \overline x) \vee 0 = y \wedge \overline x.\)

Упростим \(z \wedge (z \vee y).\) По закону поглощения данное выражение равно \(z\) (докажем это, применив несколько раз закон дистрибутивности: выражение равносильно \((z \wedge z) \vee (z \wedge y) = z \vee (z \wedge y) = z \wedge (1 \vee y) = z.\) \(1 \vee y = 1\) при любом значении \(y,\) так как дизъюнкция истинна, если истинно хотя бы одно из высказываний, входящих в нее).

Тогда теперь логическая функция выглядит так: \(F = (y \wedge \overline x \wedge z) \vee (\overline x \wedge \overline z).\) Последний раз преобразуем функцию, чтобы она выглядела еще приятнее, по закону дистрибутивности: \((\overline x \wedge z \wedge y) \vee (\overline x \wedge \overline z) = \overline x \wedge ((y \wedge z) \vee \overline z).\)

Во всех строках представленного фрагмента \(F = 1.\) Конъюнкция истинна, если истинны все высказывания, входящие в нее. Тогда \(\overline x = 1\) \((x = 0)\) и \(((y \wedge z) \vee \overline z) = 1.\) Мы уже можем сделать вывод, что третьему столбцу соответствует \(x,\) так как это единственный столбец, в котором нет единиц.

Рассмотрим высказывание \((y \wedge z) \vee \overline z.\) Это дизъюнкция, которая истинна, если истинно хотя бы одно из высказываний, входящих в нее, то есть если \(y \wedge z = 1\) и/или \(\overline z = 1.\) Для удобства составим таблицу истинности для функции \(G = (y \wedge z) \vee \overline z.\)

\[\begin{array}{|c|c|c|c|} \hline y & z & \text{$(y \wedge z) \vee \overline z$}\\ \hline 0 & 0 & 1 \\ \hline 1 & 0 & 1 \\ \hline 0 & 1 & 0 \\ \hline 1 & 1 & 1 \\ \hline \end{array}\]

Таким образом, под условие подходят следующие наборы \((y, \; z)\): (0, 0), (1, 0), (1, 1).

Сопоставим это с фрагментом таблицы истинности из условия и поймем, что первому столбцу соответствует \(y,\) второму — \(z.\)

1. Конъюнкция истинна, когда обе скобки будут истинны. Обратим внимание на вторую и третью строчки. Они примечательны тем, что в них \(F = 1\) тогда, когда две переменные принимают значение 1, а третья переменная значение 0. Заметим, что если \(y = 0, \; z = 1, \; x = 1,\) то \(F = 0,\) так как первая скобка будет ложной. Используя вторую и третью строчки, мы поймём, что \(y\) не может занимать первый и второй столбец, следовательно, \(y\) занимает третий столбец.

2. Обратимся к первой строчке. В ней \(y = 0.\) Следовательно, \((\overline y \vee z) = 1.\) В таком случае \(x = 0\) для истинности эквивалентности. Значит, \(x\) занимает первый столбец, а \(z\) занимает второй.

1. Импликация будет ложна, когда первая скобка будет истинна, а вторая будет ложна. Рассмотрим третью строчку. Предположим, что \(x\) занимает третий столбец. Но тогда первая скобка будет ложной, а значит, импликация будет истинной. Если \(z\) занимает третий столбец, то аналогично первая скобка будет ложной, и, как следствие, импликация будет истинной. Значит, можно убедиться в том, что \(y\) занимает третий столбец в данном фрагменте таблицы истинности.

2. Обратимся ко второй строке. Рассмотрим два варианта: когда \(x = 1, \; z = 0,\) и вариант, когда \(x = 0, \; z = 1.\) Во втором случае первая скобка будет ложной, а значит, импликация будет истинной. Из этого можно сделать вывод, что подойдёт первый вариант, \(x\) будет занимать первый столбец, а \(z\) занимать второй.