Поскольку в прошлой статье мы уже разобрались с операциями алгебры логики и научились их записывать на языке Python, то теперь можем смело перейти к разбору задания 2 ЕГЭ по информатике.
Задание 2 ЕГЭ по информатике проверяет умение строить таблицы истинности и анализировать логические выражения. Это задание базового уровня. Решать его можно как вручную, так и с помощью любого доступного языка программирования — обычно таким является Python.
В этом задании вам даётся логическая функция и её таблица истинности, которая заполнена не до конца. Вам предстоит заполнить эту таблицу истинности и определить, к какому столбцу таблицы соответствует каждая переменная логической функции. В ответ требуется дать названия переменных в том порядке, в котором идут соответствующие им столбцы таблицы истинности.
Разделения на типы в этом задании нет, все формулировки буквально идентичны и отличаются только логической функцией и таблицей истинности.
Но мы всё равно разделим повествование на две статьи. В этой статье научимся решать задание 2 вручную и немного затронем программный способ перебора значений переменных.
А всю следующую статью посвятим универсальному коду, который позволяет без каких-либо сложностей решать любые варианты задания 2 ЕГЭ. Также нам предстоит вспомнить некоторые термины и функции языка Python и вывести этот код для более глубокого понимания.
Но это всё в будущем. Сейчас же давайте сконцентрируемся на самом базовом ручном методе и выведем алгоритм действий для успешного решения задания 2.
Алгоритм решения
Для начала давайте вкратце опишем алгоритм наших действий. Итак, взглянув на логическую функцию, нужно сразу разделить её на части. Например, функцию F = (x ∧ ¬y) ∨ (y ≡ z) ∨ w в первую очередь следует разделить на три части по дизъюнкции:
Первая часть: конъюнкция x и инвертированного значения y — x ∧ ¬y
Вторая часть: эквивалентность y и z — y ≡ z
Третья часть: переменная w
И дальше следует анализировать, какие значения должны принимать эти части исходя из нужных значений самой функции. Так, если нужно, чтобы функция принимала только ложные значения, то все три части также должны быть ложными. Ведь при дизъюнкции достаточно хотя бы одного истинного значения аргумента, чтобы вся функция приняла истинное значение.
Отсюда уже можно делать вывод, что w будет принимать ложные значения. Ищем в таблице истинности из условия подходящий столбец и закрепляем за ним переменную w.
Следом смотрим на оставшиеся столбцы и предполагаем, где какая переменная может находиться. Здесь же у переменных y и z должны быть разные значения, чтобы эквивалентность y ≡ z возвращала ложь. А переменные x и y не могут принимать значения 1 и 0, соответственно, чтобы не допустить истинности конъюнкции x ∧ ¬y.
Можно как сразу работать с таблицей истинности из условия и дописывать в неё недостающие значения, так и составлять свою. Во втором случае останется лишь сверить свои значения с теми, что даны в условии, и соотнести столбцы обеих таблиц, чтобы получить верное расположение переменных.
В целом, на этом алгоритм и завершён. Главное — помнить порядок операций алгебры логики, таблицы истинности всех функций и тогда решение не будет представлять никаких сложностей.
Давайте опробуем алгоритм в деле и разберём задание с такой формулировкой:
Миша заполнял таблицу истинности логической функции F = ¬(x → z) ∨ (y ≡ w) ∨ y, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
F
1
0
0
1
0
0
0
0
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Здесь в выражении мы видим похожую ситуацию, что и в примере выше. Разделим все выражение на три части:
¬ (x → z)
y≡ w
y
И, поскольку у нас тут снова дизъюнкция и выражение должно быть ложным, то все эти три части тоже должны принимать только ложные значения. С переменной y все понятно. Давайте для наглядности составим свою таблицу истинности, куда будем записывать возможные значения для каждой переменной.
Во второй части имеем эквивалентность y ≡ w, которая должна быть ложной. Значения для y мы уже знаем, следовательно, w должна принимать противоположные значения, то есть истинные.
Дальше чуть сложнее. Отрицание импликации ¬(x → z) должно быть ложным, значит, сама импликация x → z должна быть истинной. Она истинна во всех случаях, кроме сочетания x = 1 и z = 0.
То есть переменная x может принимать значения 0, 0, 1, а z — 0, 1, 1. Иначе говоря, в каждой строке должно выполняться условие x ≤ z. Так и запишем в таблицу.
Переходим к сопоставлению нашей таблицы истинности и той, которую не дописал Миша из условия этой задачи. Сверху разместим таблицу из условия, а снизу — нашу. Сразу видим, что нули отсутствуют только в одном столбце — четвёртом. Его и отведём под истинные значения переменной w.
По аналогии найдём столбец и для переменной y — это третий столбец, ведь только в нём нет единиц.
Осталось лишь сопоставить две переменные: x и z. Обратите внимание на первую строку таблицы истинности из условия. Мы ранее уже выяснили, что значения x должны быть меньше или равны значениям z. Тогда получается, что первый столбец следует соотнести с переменной z, а второй — с x.
В итоге получаем заполненную таблицу истинности из условия.
Чтобы дать ответ на это задание, достаточно просто переписать буквы из заголовка этой таблицы в том же порядке — zxyw.
Пример 1
Для закрепления решим ещё одно задание:
Миша заполнял таблицу истинности логической функции F =(z → ¬(y→ x)) ∨ w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
F
1
0
0
0
0
0
1
0
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
И снова нам предстоит работать с дизъюнкцией. Правда, теперь выражение делится всего на две части:
z → ¬ (y → x)
w
Повторяться не будем, как и в прошлом примере здесь переменная w будет принимать только ложные значения.
Переходим к выражению z → ¬(y → x). Чтобы вся импликация была ложной, её первая часть должна быть истинной, а вторая — ложной. Поэтому z = 1, а выражение ¬(y → x) = 0.
Убираем отрицание: раз ¬(y → x) ложно, то y → x, наоборот, истинно. Остаётся вспомнить таблицу истинности импликации и выписать все пары x и y, при которых она возвращает истину.
Наша таблица истинности готова, теперь давайте искать соответствия с предложенной в условии таблицей.
Для переменной w сразу находится нужное место — четвёртый столбец. Только в нём не содержится единиц и может быть 3 нуля.
Единственный оставшийся столбец без нулей отводим под переменную z.
Во втором и третьем столбцах таблицы из условия рассмотрим последнюю строку. Снова здесь ситуация с импликацией: такое положение нуля и единицы говорит нам о том, что второму столбцу соответствует y, а третьему — x.
В итоге имеем такую таблицу.
Переписываем буквы из заголовков в ответ: zyxw.
Решение перебором
Ручное решение надёжное, но может занимать довольно много времени, если дана сложная логическая функция, для которой вы не хотите самостоятельно строить таблицу истинности.
Всё, что мы делали раньше — это пытались подобрать подходящие значения для переменных из таблицы в условии. А что, если заставить программу самостоятельно перебирать все возможные значения и выдавать только те, подставив которые в логическую функцию, она будет удовлетворять условию?
В этом и заключается решение перебором 2 задания на языке Python. Это решение максимально простое и требует от вас лишь правильно записать логическое выражение, учитывая приоритет операций в языке Python.
Общий алгоритм можно расписать так:
Выводим буквы из условия для удобства print('x y z w')
В цикле перебираем все возможные значения переменных (0 и 1)
for x in 0, 1: for y in 0, 1: for z in 0, 1: for w in 0, 1:
Переписываем логическую функцию и подставляем её в условие
В зависимости от того, нужны истинные значения функции или ложные, выводим на экран значения переменных x, y, z, w.
Важно: конструкция if f: выводит только строки, где F = 1. Если в условии нужны строки с F = 0, используйте if not f: или явно проверяйте if f == 0:.
Давайте проверим этот алгоритм на задании с такой формулировкой:
Миша заполнял таблицу истинности логической функции F = (x ∨ y) ∧ ¬ (y ≡ z) ∧ ¬ w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w,x,y,z.
F
1
1
1
0
1
0
1
1
1
0
1
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Начнём с записи логической функции, она будет записываться так:
f = (x or y) and not (y == z) and not w
В целом, здесь нет никаких сложностей, все операции выполняются в стандартном порядке.
Теперь выше неё напишем четыре цикла for для перебора значений каждой переменной, а перед этим выведем сами названия переменных для удобства:
print('x y z w')
for x in 0, 1:
for y in 0, 1:
for z in 0, 1:
for w in 0, 1:
f = (x or y) and not (y == z) and not w
Не забывайте про отступы внутри циклов! А нам осталось лишь дописать условие, по которому, если функция возвращает истину, будут выводиться значения переменных x, y, z, w:
print('x y z w')
for x in 0, 1:
for y in 0, 1:
for z in 0, 1:
for w in 0, 1:
f = (x or y) and not (y == z) and not w
if f:
print(x, y, z, w)
Запускаем наш код и видим на экране следующее:
x y z w
0 1 0 0
1 0 1 0
1 1 0 0
И что же это? Да это буквально та же самая таблица истинности, которую мы составляли вручную, только теперь за нас всё сделала программа! Для наглядности оформим её как прошлые таблицы:
Осталось лишь сопоставить значения этой таблицы с той, что дана в условии. Как обычно, сразу находим столбец с одними нулями — четвёртый.
Но дальше всё не так очевидно. Единственное, что можно сказать наверняка — в последней строке исходной таблицы во втором и третьем столбце расположены единицы. А одновременно принимать истинные значения могут только x с y. Значит, один из них находится во втором столбце, а другой — в третьем.
Тогда первый столбец смело отдаём переменной z.
Ну а теперь определимся с оставшимися. Проще всего будет сопоставить в первой строке исходной таблицы: и там, и там расположены единицы. Такую же картину можем наблюдать во второй строке нашей таблицы — у переменных x и z.
В таком случае третий столбец займёт переменная x, а оставшийся второй достаётся y. Получаем такую таблицу.
Теперь мы готовы дать ответ на это задание: zyxw.
Перед ответом обязательно проверьте три вещи: все строки таблицы различны, логическая функция принимает нужное значение, а буквы выписаны именно в порядке столбцов из условия.
На этом мы закончим с ручным решением и перебором в Python. В следующей статье уже приступим к написанию универсального кода, который сразу будет выдавать подходящую комбинацию букв.
Разберём эту тему на бесплатном пробном занятии
Преподаватель покажет, как решать такие задачи, и подскажет, с чего начать подготовку. Группы до 8 человек, очно в Калининграде и онлайн.
Мы используем файлы cookie. Необходимые обеспечивают работу сайта: корзину и вход в личный кабинет. С вашего согласия мы также используем сервис Яндекс Метрика, чтобы анализировать посещаемость и улучшать сайт.
Подробнее — в политике конфиденциальности.
