О задании
Поскольку в прошлой статье мы уже разобрались с операциями алгебры логики и научились их записывать на языке 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.
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.»
Здесь в выражении мы видим похожую ситуацию, что и в примере выше. Разделим все выражение на три части:
- ¬ (x → z)
- y≡ w
- y
И, поскольку у нас тут снова дизъюнкция и выражение должно быть ложным, то все эти три части так же должны принимать только ложные значения. С переменной y все понятно. Давайте для наглядности составим свою таблицу истинности, куда будем записывать возможные значения для каждой переменной.
Во второй части имеем эквивалентность y ≡ w, которая должна быть ложной. Значения для y мы уже знаем, следовательно, w должна принимать противоположные значения, то есть истинные.
Дальше чуть сложнее. Отрицание импликации ¬ (x → z), которое должно быть ложным, говорит нам о том, что сама импликация должна возвращать истину. Вспоминаем, что импликация возвращает истину во всех случаях, кроме одного: когда первое утверждение истинно, а второе утверждение ложно.
То есть переменная x может принимать значения 0, 0, 1, в то время как y будет принимать значения 0, 1, 1. Иначе говоря, значения x должны быть меньше или равны значениям z. Так и запишем в таблицу.
Переходим к сопоставлению нашей таблицы истинности и той, которую не дописал Миша из условия этой задачи. Сверху разместим таблицу из условия, а снизу — нашу. Сразу видим, что нули отсутствуют только в одном столбце — четвёртом. Его и отведём под истинные значения переменной w.
По аналогии найдём столбец и для переменной y — это третий столбец, ведь только в нём нет единиц.
Осталось лишь сопоставить две переменные: x и z. Обратите внимание на первую строку таблицы истинности из условия. Мы ранее уже выяснили, что значения x должны быть меньше или равны значениям z. Тогда получается, что первый столбец следует соотнести с переменной z, а второй — с x.
В итоге получаем заполненную таблицу истинности из условия.
Чтобы дать ответ на это задание, достаточно просто переписать буквы из заголовка этой таблицы в том же порядке — zxyw.
Пример 1
Для закрепления решим еще одно задание:
«Миша заполнял таблицу истинности логической функции F = (z → ¬ (y → x)) ∨ w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.»
И снова нам предстоит работать с дизъюнкцией. Правда, теперь выражение делится всего на две части:
- z → ¬ (y → x)
- w
Повторяться не будем, как и в прошлом примере здесь переменная w будет принимать только ложные значения.
Переходим к выражению z → ¬ (y → x), оно ложное только тогда, когда z принимает истинные значения. Записываем это в таблицу.
Ну а по таблице истинности для импликации мы знаем, что выражение ¬ (y → x) должно быть ложным. Убираем здесь отрицание и получаем, что y → x, наоборот, должно быть истинным. Значит, просто вспомним таблицу истинности для импликации и перепишем все возможные значения x и y, при которых импликация будет возвращать истину.
Наша таблица истинности готова, теперь давайте искать соответствия с предложенной в условии таблицей.
Для переменной w сразу находится нужное место — четвёртый столбец. Только в нём не содержится единиц и может быть 3 нуля.
Единственный оставшийся столбец без нулей отводим под переменную z.
Во втором и третьем столбцах таблицы из условия рассмотрим последнюю строку. Снова здесь ситуация с импликацией: такое положение нуля и единицы говорит нам о том, что второму столбцу соответствует y, а третьему — x.
В итоге имеем такую таблицу.
Переписываем буквы из заголовков в ответ: zyxw.
Решение перебором
Ручное решение надёжное, но может занимать довольно долго времени, если дана сложная логическая функция, для которой вы не хотите самостоятельно строить таблицу истинности.
Все, что мы делали раньше — это пытались подобрать подходящие значения для переменных из таблицы в условии. А что, если заставить программу самостоятельно перебирать все возможные значения и выдавать только те, подставив которые в логическую функцию, она будет удовлетворять условию?
В этом и заключается решение перебором 2 задания на языке Python. Это решение максимально простое и требует от вас лишь правильно записать логическое выражение, учитывая приоритет операций в языке Python.
Общий алгоритм можно расписать так:
1. Выводим буквы из условия для удобства print(‘x y z w’)
2. В цикле перебираем все возможные значения переменных (0 и 1)
3. Переписываем логическую функцию и подставляем её в условие
4. В зависимости от того, нужны истинные значения функции или ложные, выводим на экран значения переменных x, y, z, w.
Давайте проверим этот алгоритм на задании с такой формулировкой:
«Миша заполнял таблицу истинности логической функции F = (x ∨ y) ∧ ¬ (y ≡ z) ∧ ¬ w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w,x,y,z.
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.»
Начнем с записи логической функции, она будет записываться так:
В целом, здесь нет никаких сложностей, все операции выполняются в стандартном порядке.
Теперь выше неё напишем четыре цикла for для перебора значений каждой переменной, а перед этим выведем сами названия переменных для удобства:
Не забывайте про отступы внутри циклов! А нам осталось лишь дописать условие, по которому, если функция возвращает истину, будут выводиться значения переменных x, y, z, w:
Запускаем наш код и видим на экране следующее:
И что же это? Да это буквально та же самая таблица истинности, которую мы составляли вручную, только теперь за нас все сделала программа! Для наглядности оформим её как прошлые таблицы:
Осталось лишь сопоставить значения этой таблицы с той, что дана в условии. Как обычно, сразу находим столбец с одними нулями — четвёртый.
Но дальше все не так очевидно. Единственное, что можно сказать наверняка — в последней строке исходной таблицы во втором и третьем столбце расположены единицы. А одновременно принимать истинные значения могут только x с y. Значит, один из них находится во втором столбце, а другой — в третьем.
Тогда первый столбец смело отдаём переменной z.
Ну а теперь определимся с оставшимися. Проще всего будет сопоставить в первой строке исходной таблицы: и там, и там расположены единицы. Такую же картину можем наблюдать во второй строке нашей таблицы — у переменных x и z.
В таком случае третий столбец займёт переменная x, а оставшийся второй достаётся y. Получаем такую таблицу.
Теперь мы готовы дать ответ на это задание: zyxw.
На этом мы закончим с ручным решением и перебором в Python. В следующей статье уже приступим к написанию универсального кода, который сразу будет выдавать подходящую комбинацию букв.