Математика ЕГЭ
Русский язык ЕГЭ
Математика 5-7
Математика ОГЭ
Информатика
Физика
Обществознание
Кликните, чтобы открыть меню

2. Таблицы истинности

1. Вспоминай формулы по каждой теме
2. Решай новые задачи каждый день
3. Вдумчиво разбирай решения

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

Задание 1 #10043

Логическая функция \(F\) задаётся выражением \(w \wedge (x \vee \overline y) \wedge \overline{w \equiv z}.\)

Ниже представлен фрагмент таблицы истинности функции \(F,\) содержащий неповторяющиеся строки, при которых функция \(F\) истинна.

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

Определите, какому столбцу таблицы истинности функции \(F\) соответствует каждая переменная \(w,\) \(x,\) \(y,\) \(z.\)

Заметим, что во всех трех строках \(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}\]

Ответ: wzyx

Задание 2 #10044

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

Ниже представлен фрагмент таблицы истинности функции \(F,\) содержащий неповторяющиеся строки, при которых функция \(F\) ложна.

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

Определите, какому столбцу таблицы истинности функции \(F\) соответствует каждая переменная \(w,\) \(x,\) \(y,\) \(z.\)

 

Выражение содержит три операнда \((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\) — второму.

Ответ: zxyw

Задание 3 #10045

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

Ниже представлен фрагмент таблицы истинности функции \(F,\) содержащий неповторяющиеся строки, при которых функция \(F\) ложна.

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

Определите, какому столбцу таблицы истинности функции \(F\) соответствует каждая переменная \(w,\) \(x,\) \(y,\) \(z.\)

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

Ответ: zyxw

Задание 4 #10047

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

Ниже представлен фрагмент таблицы истинности функции \(F,\) содержащий неповторяющиеся строки, при которых функция \(F\) истинна.

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

Определите, какому столбцу таблицы истинности функции \(F\) соответствует каждая переменная \(x,\) \(y,\) \(z, \; w.\)

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

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

Конъюнкция истинна, если истинны все высказывания, входящие в нее. Значит, \(\overline w = 1,\) \(z \vee (y \wedge \overline x) = 1,\) \(y \vee x = 1.\)

Если \(\overline w = 1,\) то \(w = 0.\) Так как только в четвертом столбце нет единиц, то четвертому столбцу соответствует \(w.\)

Для удобства составим таблицу истинности. Так как \(w\) всегда должна быть равна нулю, чтобы \(F = 1,\) то будем составлять таблицу истинности только для трех переменных. В ней будет \(2^3 = 8\) строчек. Если значение выражения \((z \vee (y \wedge \overline x)) \wedge (y \vee x)\) будет истинно, то и вся функция будет истинна.

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

Есть только 4 строки, в которых \(F = 1.\) Значит, надо сопоставить каждую из них с фрагментом таблицы истинности из условия. В восьмой строке составленной таблицы истинности две единицы и один ноль. В третьей строке фрагмента тоже есть две единицы (в остальных строках или 3 единицы или 1 или их нет вообще). В этой строке ноль — это значение \(x.\) Значит, первому столбцу фрагмента соответствует \(x.\)

Рассмотрим третью строку составленной нами таблицы истинности. Там есть одна единица и два нуля. Во второй строке фрагмента из условия также 3 нуля и одна единица. Эта единица — значение \(y\) (второй столбец).

Тогда третьему столбцу соответствует \(z.\)

Ответ: xyzw

Задание 5 #10048

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

Ниже представлен фрагмент таблицы истинности функции \(F,\) содержащий неповторяющиеся строки, при которых функция \(F\) ложна.

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

Определите, какому столбцу таблицы истинности функции \(F\) соответствует каждая переменная \(x,\) \(y,\) \(z, \; w.\)

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

Ответ: xywz

Задание 6 #10049

Логическая функция \(F\) задаётся выражением \(((x \vee y) \wedge (\overline x \vee y) \wedge (\overline x \vee \overline y) \wedge z \wedge (z \vee y)) \vee (\overline x \wedge \overline z)\)

Ниже представлен фрагмент таблицы истинности функции \(F,\) содержащий неповторяющиеся строки, при которых функция \(F\) истинна.

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

Определите, какому столбцу таблицы истинности функции \(F\) соответствует каждая переменная \(x,\) \(y,\) \(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.\)

Ответ: yzx