Сложные логические выражения (страница 4)

1. Рассмотрим первую строчку данного фрагмента. Предположим, что все переменные принимают значение 0, следовательно, \((z \equiv x) = 1,\) а значит, \(F = 1.\) Значит все переменные не могут быть равны 0. То есть во второй ячейке первой строки находится 1. Заметим, что для \(F = 0\) переменные \(z, \; x\) должны принимать разные значения. Значит во второй ячейке первой строки находится одна из этих переменных. Предположим, что это место занимает \(x.\) Однако тогда импликация во второй скобке будет истинной, а значит, и вся дизъюнкция будет истинной. Следовательно, второй столбец занят переменной \(z.\)

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

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

2. Рассмотрим вторую строчку. Если \(x\) занимает второй столбец, а \(y\) третий, то обе скобки будут истинны, а значит, и конъюнкция будет истинна. Значит, \(y\) занимает второй столбец, а \(x\) занимает третий столбец.

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

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

Упростим \((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.\)

Выражение содержит два операнда, связанных дизъюнкцией. В приведенном фрагменте \(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\) — это первый столбец.

В приведенном фрагменте во всех строках \(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.\)