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

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

2. Рассмотрим вариант, когда \(y\) занимает второй столбец, а \(x\) занимает третий. Так как \(y\) и \(z\) принимают разные значения, а строчки не могут повторяться, то первая ячейка третьей строки равна 1, а вторая ячейка равна 0. В таком случае вторая скобка будет истинной, а значит, дизъюнкция будет истинной. Следовательно, второй столбец занимает \(x,\) а третий столбец занимает \(y.\)

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

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

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

\(\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.\)

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\) может быть любой, так как в упрощенной формуле переменная \(у\) отсутствует, значит, не влияет на ответ).

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.\)

Так как конъюнкция истинна тогда и только тогда, когда все высказывания, входящие в нее, истинны, то \((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.\)

\(\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.\) Все верно.