Чтобы решить задание № 2 из ЕГЭ по информатике, нужно построить таблицу истинности логической функции. Это можно сделать как вручную (аналитически), так и написав код. Такое решение задания — шаблонное, его могут выполнить даже те ученики, которые не очень хорошо программируют.
Мы рекомендуем освоить и аналитический способ решения, чтобы суметь адаптироваться к возможным изменениям в задании или просто перепроверить свой ответ вручную.
Задача 1. Построение таблицы истинности
В подобных задачах нам даётся логическая функция, состоящая из нескольких простых выражений в скобках, между которыми стоит конъюнкция или дизъюнкция. Это позволяет решать задачу постепенно, не строя полную таблицу истинности функции из условия.
Важно отметить, что фрагмент таблицы истинности, который дан в условии, не содержит повторяющихся строк. То есть даже с учётом пропущенных значений мы не можем получить, например, такие строки:
Перейдём к разбору нашего задания.
Функция $(\lnot x \to z) \land (w \lor \lnot y) \land \lnot z$ делится на три части, соединённые между собой логическим И (конъюнкцией): $\lnot x \to z$, $w \lor \lnot y$ и $\lnot z$. Поскольку во фрагменте из условия для всех строчек значение функции равно единице, каждая из этих частей должна быть равна единице. Выражение с конъюнкцией истинно тогда, когда истинны все входящие в него переменные.
Построим таблицы истинности для каждого простого выражения.
$\lnot x \to z$
$w \lor \lnot y$
Рассмотрим подробнее, как из получившихся двух таблиц сформировать итоговую. В ней останутся только те комбинации значений переменных, при которых функция равна единице. (В следующей задаче сделаем это проще и быстрее.)
Возьмём из получившихся таблиц строки, в которых выражения равны единице, и составим для них все возможные комбинации значений переменных. Например, для $x = 0, z = 1$ надо дописать все возможные комбинации значений переменных $w$ и $y$: $w = 0, y = 0$; $w = 1, y = 0$; $w = 1, y = 1$. Так, для каждой строки из первой таблицы в результате получатся три строки.
Выражение $\lnot z$ равно единице тогда, когда переменная $z$ равна нулю, поэтому возьмём из таблицы истинности только строки с этим значением.
Теперь мы можем поставить переменные на их места в исходном фрагменте таблицы.
Порядок строк в таблице истинности из условия и в построенной нами таблице может не совпадать. Внимательно подбирайте похожие строки.
В первую очередь анализировать нужно уникальные строки, например содержащие только одну единицу при всех остальных нулевых значениях, или столбцы — в них больше всего нулей или единиц.
Только в одном столбце можно поставить три единицы, так как во всех остальных встречается хотя бы один ноль. Заполним его и поставим в заголовке $x$.
Также только в одном столбце можно записать три нуля (ведь в остальных есть хотя бы одна единица). Это столбец $z$.
В первой строке две единицы и два нуля. В построенной нами таблице только одна такая строка. Значит, если одна единица соответствует $x$, вторая — это переменная $w$.
Оставшийся незаполненным столбец соответствует переменной $y$.
Важно правильно записать ответ. Нам нужно переписать переменные именно в том порядке, в котором они выстроились при заполнении фрагмента таблицы истинности из условия задачи. В нашем случае это $ywxz$.
Ответ: $ywxz$
Задача 2. Построение таблицы истинности
В отличие от предыдущей задачи, функция состоит из трёх выражений, которые объединены логическим ИЛИ (дизъюнкцией): $x \land \lnot y$, $y \equiv z$ и $\lnot w$. Во всех строках таблицы значение функции равно нулю. Значит, нам нужно найти такие ситуации, в которых все выражения равны нулю (дизъюнкция ложна только тогда, когда ложны значения всех переменных).
Построим таблицу истинности выражения $x \land \lnot y$:
Таблица истинности выражения $y \equiv z$ выглядит так:
В обоих выражениях есть переменная $y$, поэтому при составлении итоговой таблицы мы должны взять только те комбинации переменных, в которых значения $y$ будут одинаковыми. Так, паре $x = 0, y = 0$ соответствует $z = 1$, а парам $x = 0, y = 1$ и $x = 1, y = 1$ соответствует $z = 0$. Выражение $\lnot w$ равно нулю тогда, когда переменная $w$ равна единице. Значит, мы просто допишем единицу в столбце $w$ для всех комбинаций $x$, $y$ и $z$. Получится так:
Проанализируем таблицу из условия и расставим переменные на свои места.
Во всех столбцах, кроме первого, есть нули, поэтому именно он соответствует переменной $w$, равной единице:
В построенной нами таблице есть одна строка, которая содержит три единицы, а единственный ноль соответствует переменной $z$. Следовательно, в таблице из условия можно заполнить только последнюю строку, поэтому переменная $z$ должна быть во втором столбце:
Теперь мы видим, что в последней незаполненной ячейке должна находиться единица. В построенной нами таблице в строке с двумя единицами одна из них — это переменная $w$, а вторая — $y$. Значит, третий столбец в таблице из условия соответствует переменной $y$, а четвёртый — $x$.
Ответ: $wzyx$
Задача 3. Анализ функции
В этот раз мы не будем ничего строить, а попробуем восстановить данные только через анализ функции.
1. В этом случае функция содержит логическое И, которое объединяет три простых логических выражения: $c$, $a \lor d$ и $d \to b$. Во всех известных из условия строках таблицы истинности значение функции равно единице. Нам нужно будет подобрать такое положение переменных, которое обеспечит единицу для каждого из трёх простых выражений\
2. Начнём с выражения, которое содержит одну переменную — $c$, равную единице. В таблице есть только один столбец, в который можно записать три единицы. Его и обозначим как $c$:
3. Обратим внимание на нижнюю строку, которая теперь заполнена полностью. С её помощью мы сможем найти местоположение ещё одной переменной. Для этого будем последовательно подставлять значение 1 каждой из оставшихся переменных: $a$, $b$ и $d$. Получим:\
a. $c = 1, a = 1$: $1 \land (1 \lor 0) \land (0 \to 0) = 1 \land 1 \land 1 = 1$\
b. $c = 1, b = 1$: $1 \land (0 \lor 0) \land (0 \to 1) = 1 \land 0 \land 1 = 0$\
c. $c = 1, d = 1$: $1 \land (0 \lor 1) \land (1 \to 0) = 1 \land 1 \land 0 = 0$
Мы видим, что функция равна единице, только если $a = 1$. Значит, мы нашли место для ещё одной переменной:
4. Теперь попробуем с помощью первой строки определить местоположение оставшихся двух переменных. В ней нам неизвестны значения ячеек в первом и третьем столбцах, но мы знаем, что третий — это $a$. Также нам известно, что одна из искомых переменных равна нулю (четвёртый столбец).\
Попробуем снова посмотреть, какие значения получатся у функции в зависимости от того, где мы разместим переменные $b$ и $d$.
Вариант 1: $c = 1, b = 0$: $1 \land (a \lor d) \land (d \to 0)$.\
В этом случае $d$ не может быть равна единице, иначе выражение $(d \to 0)$ станет равно нулю. Но если $d = 0$, то $a$ должна быть равна единице, чтобы выражение $a \lor d$ было равно единице. Тогда наша таблица будет выглядеть так:
А это противоречит условию задачи о том, что все строки должны быть различны
Вариант 2: $c = 1, d = 0$: $1 \land (a \lor 0) \land (0 \to b)$.\
В этом случае переменная $a$ также должна быть равна единице, чтобы выражение $a \lor 0$ стало равно ей же. А вот переменная $b$, которую мы помещаем в первый столбец, может принять значение 1. Таблица будет выглядеть так:
В этом случае условие, что все строки в таблице должны быть разными, выполняется, а значит, мы нашли место для всех переменных.
Ответ: $bcad$
Заключение
Чтобы решать задание № 2 аналитически, нужно понимать основы логики и уметь работать с таблицами истинности. Хотя программирование кажется более простым способом справиться с задачей, владение аналитическим методом даёт важные преимущества на экзамене.
Ключевые выводы:
-
Разбивайте сложные логические функции на простые части\
Это основа аналитического подхода. Работайте с каждым выражением отдельно, а затем объединяйте результаты. -
Помните о свойствах логических операций\
Конъюнкция истинна, только когда все части истинны, дизъюнкция ложна, только когда все части ложны. -
Ищите уникальные столбцы и строки\
Они помогают быстро определить расположение переменных в таблице. Начинайте анализ с самых очевидных случаев. -
Проверяйте условие об отсутствии повторяющихся строк\
Это важное ограничение, которое поможет исключить неверные варианты размещения переменных. -
Будьте внимательны при записи ответа\
Переменные нужно записывать в том порядке, в котором они расположены в исходной таблице из условия. -
Используйте аналитический метод для проверки\
Даже если вы решаете задачу с помощью программирования, полезно уметь проверить результат вручную.
Владение обоими методами решения, программированием и аналитикой, поможет вам адаптироваться к любым изменениям в формате задания и уверенно справиться с задачами разной сложности. Потренироваться принять эти навыки предлагаем на подборке задач.