Простейшие логические выражения

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

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

Проверим наше предположение на двух оставшихся строчках.

Рассмотрим вторую строчку. \(\overline 0 \vee 0 \; = \; 1.\) Дизъюнкция будет истинной.

Рассмотрим третью строчку. \(\overline 1 \vee 1 \; = \; 1.\) Дизъюнкция будет истинной. Таким образом, \(x\)отвечает за третий столбец, а \(y\)— за первый.

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

Рассмотрим \((\overline{\overline y \vee z}).\) Это выражение должно быть ложно, значит дизъюнкция \(\overline y \vee z\) должна быть истинна. Дизъюнкция истинна, если хотя бы одно из высказываний, входящих в нее, истинно. Так как \(z = 1,\) то \(y\) может быть любым.

Так как \(z = 1,\) то первому столбцу соответствует \(z.\) Так как \(x = 0,\) то третьему столбцу соответствует \(x.\) Так как \(y\) может быть любым, то второму столбцу соответствует \(y.\)

\(\overline {\overline x},\) так как если \(x = 0,\) то \(\overline x = 1,\)\(\overline {\overline x} = \overline 1 = 0 = x,\) а если \(x = 1,\) то \(\overline x = 0,\) а \(\overline {\overline x} = \overline 0 = 1 = x.\)

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

Рассмотрим высказывание \(x \vee \overline w.\) Оно истинно, когда \(x = 1\) и/или \(\overline w = 1,\) то есть \(w = 0\) (так как дизъюнкция истинна, когда хотя бы одно высказывание, входящее в нее, истинно). Рассмотрим третью строку. Как мы определили выше, первый столбец отвечает за \(z.\) Если второй — это \(x,\) то \(w\) должна быть равна 1 (так как \(0 \vee \overline w = 1,\) если \(\overline w = 1,\) то есть \(w = 0).\) Но переменная в третьем столбце равна 1, значит, предположение, что второй столбец — это \(x,\) было неверным. Значит, второй столбец — это \(w,\) а третий — это \(x.\)

Проверим это предположение на первой и второй строчках. Подставим соответствующие значения в функцию. Первая строка: \(F = (1 \vee \overline 0) \wedge 1 = 1 \wedge 1 = 1.\) Вторая строка: \(F = (0 \vee \overline 0) \wedge 1 = (0 \vee 1) \wedge 1 = 1 \wedge 1 = 1.\) Все верно.

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

Рассмотрим \((y \rightarrow z).\) Нам нужно, чтобы данная импликация была истинна. Легче исключить один случай, когда импликация ложна, так как она ложна тогда и только тогда, когда из истины следует ложь, то есть когда \(y = 1,\) a \(z = 0.\) Рассмотрим вторую строку. Видим, что переменная \(y\) не может соответствовать третьему столбцу, так как тогда \(y = 1,\)\(z = 0\) и \(y \rightarrow z = 1 \rightarrow 0,\)\(F = 0.\) Получается, третьему столбцу соответствует \(z,\) а первому — \(y.\)

1. Упростим \((x \wedge y) \vee (x \wedge \overline y).\)

По закону диструбитивности \((y \wedge x) \vee (x \wedge \overline y)\) = \( x \wedge (y \vee \overline y).\)\(y \vee \overline y = 1\) (если \(y = 0,\) то \(\overline y \vee y = 1 \vee 0 = 1,\) если \(y = 1,\) то \(\overline y \vee y = 0 \vee 1 = 1).\) Тогда \( x \wedge (y \vee \overline y) = x \wedge 1 = x.\)

2. Упростим \((y\wedge \overline z) \vee (\overline z \wedge x).\) По закону дистрибутивности \((y\wedge \overline z) \vee (\overline z \wedge x) = \overline z \wedge (y \vee x).\)

3. Получим: \((x \wedge y) \vee (x \wedge \overline y) \vee (y\wedge \overline z) \vee (\overline z \wedge x) = x \vee (\overline z \wedge (y \vee x)).\)

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

1. Так как \(a \rightarrow b = \overline a \vee b,\) преобразуем левую часть функции:

\((\overline y \rightarrow (x \rightarrow (y \rightarrow z))) = y \vee (x \rightarrow (y \rightarrow z)) = y \vee \overline x \vee (y \rightarrow z) = y \vee \overline x \vee \overline y \vee z. \)

2. \(y \vee \overline y = 1,\) так как, если \(y = 1,\) то \(y \vee \overline y = 1 \vee 0 = 1,\) если \(y = 0,\) то \(y \vee \overline y = 0 \vee 1 = 1.\)

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

Составим таблицу истинности.

\(\begin{array}{|l|l|l|l|l|l|l|} \hline x&y&z&\overline{z}&\overline{y}&x\wedge\overline{y}&\overline{z}\vee x\wedge \overline{y}\\ \hline 0&0&0&1&1&0&1\\ \hline 0&0&1&0&1&0&0\\ \hline 0&1&0&1&0&0&1\\ \hline 0&1&1&0&0&0&0\\ \hline 1&0&0&1&1&1&1\\ \hline 1&0&1&0&1&1&1\\ \hline 1&1&0&1&0&0&1\\ \hline 1&1&1&0&0&0&0\\ \hline \end{array}\)

Выпишем отдельно те строки, которые нам подходят:

\(\begin{array}{|l|l|l|l|l|l|l|} \hline x&y&z&\overline{z}&\overline{y}&x\wedge\overline{y}&\overline{z}\vee x\wedge \overline{y}\\ \hline 0&0&0&1&1&0&1\\ \hline 0&1&0&1&0&0&1\\ \hline 1&0&0&1&1&1&1\\ \hline 1&0&1&0&1&1&1\\ \hline 1&1&0&1&0&0&1\\ \hline \end{array}\)

У нас есть две строки, где только одна единица. В роли этих единиц выступают \(x, \; y.\) Значит, третья переменная — это \(z.\)

Рассмотрим третью строку. \(z = 1.\) А такая строка у нас только одна. Отсюда однозначно определяем столбцы и пишем в ответ: \(xyz.\)