Привет, меня зовут Елена и на канале TeachYou мы разбираемся, как решать задачи из ЕГЭ по информатике. Цель канала я вижу в том, чтобы собрать в одном месте теорию по заданиям базового и продвинутого уровня, а также разобрать типовые задания.
Если вы дочитываете мои публикации до конца, то знаете, что я делаю подборки задач с разными формулировками, которые обязательно нужно прорешать до экзамена.
Логические выражения
Сегодня мы разберем мою любимую тему - алгебру логики (опять передаю привет преподавателю по дискретной математике. Павел Александрович, не ругайте за неакадемическое изложение материала 🙈).
Введение. Высказывания
Высказыванием в алгебре логики называется выражение, относительно которого можно сказать, истинно оно или ложно. Говорят, что высказывание принимает значение "истина" (еще обозначается 1) или "ложь" (обозначается 0).
"На улице идет дождь" - высказывание. Можно выглянуть в окно и проверить, капает там или нет. Высказывания обычно обозначаются заглавными латинскими буквами (A, B, C, X, Y, Z...).
Некоторые логические операции. Таблица истинности
Часто требуется составить комбинацию высказываний. К примеру, в разговоре с другом вы можете сказать, что "если не будет дождя и я найду мяч, то пойдем играть в волейбол". От чего зависит, пойдете ли вы играть? От значения двух высказываний: "если не будет дождя" и "если я найду мяч". Если оба высказывания будут истинными - отличной вам игры!
Для составления комбинации высказываний используются логические операции, результат которых может принимать бинарные значения - 0 или 1, ложь или истина.
Основные логические операции:
- отрицание (инверсия, читается "не А"). Обозначается ¬А или чертой над А (как вектор, но без стрелочки. Когда пойму, как вставить этот символ в Дзен, поправлю)). Если высказывание А истинно, то ¬А ложно, и наоборот.
- логическое сложение (дизъюнкция, читается "А или В"). Обозначается A ∨ B. Результат логического сложения будет истинным, когда хотя бы одно из входящих в него высказываний истинно, и ложно, когда все входящие в него высказывания ложны.
- логическое умножение (конъюнкция, читается "А и В"). Обозначается A ∧ B. Результат логического умножения будет истинным, когда все входящие в него высказывания истинны, и ложным в остальных случаях.
- равнозначность (эквиваленция, "А эквивалентно В", "А то же самое, что и В"). Обозначается А≡В. Результат эквиваленции будет истинным, если значения А и В одинаковы, и ложным, если они различны.
- следование (импликация, читается "из А следует В"). Обозначается А⇒В. Результат импликации будет ложным только тогда, когда А равно истине, а В ложно, в остальных случаях результат принимает значение истины.
Для значений логических операций можно построить таблицу истинности. Чтобы ее построить, переберем возможные комбинации высказываний А и В и запишем соответствующие им значения операций.
Значения логических функций хорошо бы запомнить. Я знаю, у вас есть режим программиста в калькуляторе и вы можете посчитать конкретное значение в питоне или чем там планируете пользоваться. Но произведение 7*8 тоже можно не помнить, а вычислять каждый раз через сумму. Только зачем, если на это тратится время?
Если обычно у школьников со значениями операций конъюнкции-дизъюнкции возникает лишь легкая путаница, то таблицу истинности для импликации запомнить сложнее - она какая-то на первый взгляд неочевидная.
Попытаюсь кинуть вам якорь для запоминания: фразу, перечисляющую значения А и В, для которых импликация истинна. "Из правды может следовать только правда, а из лжи - все, что угодно". Проговариваем эту фразу, смотря на таблицу истинности:
- когда А=1 и В=1 (из правды следует правда), результат импликации равен истине;
- если А=0, то чему бы не было равно В, результат импликации будет истинным (из лжи следует все, что угодно).
Когда я сдавала ЕГЭ, эта фраза существенно облегчила мне запоминание, при каких значениях А и В импликация принимает значение 1.
И еще один якорек) Представьте, что вы решаете какую-то задачу и получаете ответ. Вы можете:
- ошибиться или решать все правильно;
- получить верный или неверный ответ.
Рассмотрим варианты:
- Если вы ошибетесь, то получите неправильный ответ . Может такое быть? Чаще, чем хотелось бы. Значит, 0⇒0 = 1.
- Если вы ошибетесь, то получите правильный ответ. Такое случается, но реже. Получается, 0⇒1 = 1.
- Если вы будете решать правильно, то получите неправильный ответ. Давайте представим, что мы живем в мире без опечаток на заветных последних страничках задачника. Такого быть не может. Значит, 1⇒0 = 0.
- Если вы будете решать правильно, то получите правильный ответ. Это возможно, и желаю, чтобы на всех экзаменах с вами так и произошло. 1⇒1 = 1.
Нужны ли вам такие фишечки для запоминания или они кажутся странными и лишними?
Есть и другие логические функции, но на данный момент они не встречаются в егэшных задачах. Если вам попадется что-то необычное, напишите в комментариях, обсудим и добавим в статью.
Логические функции. Пример с РешуЕГЭ
Давайте посмотрим, как выглядят задачи 2 типа на ЕГЭ по информатике.
Что тут происходит?
Видим логическую функцию, заданную длинным выражением с инверсиями, дизъюнкциями и конъюнкциями. Так как это функция, у нее есть переменные x, y и z. Для каждого набора значений переменных известно значение логической функции F (в таблице приведены наборы переменных, для которых F истинна, следовательно, для остальных наборов F ложна).
Что нужно понимать на этом этапе?
- Сколько наборов аргументов существует для функции F(x,y,z)? Давайте ответ (предположение/сомнения/непонимания) вы напишете в комментариях. Кстати, на понимание этого момента несколько лет назад предлагались к решению задачи на РешуЕГЭ (пройдите по ссылочке, там две задачи. Их не будет в ЕГЭ-2023, и если вам нужно "натаскивание" на экзамен, ни в коем случае не заглядывайте туда! Задания только для тех, кто хочет понимания того, с чем он работает).
- В каком порядке выполняются логические действия в выражении для функции F? Вспоминаем, что конъюнкция это логическое умножение, дизъюнкция - логическое сложение; инверсия действует на аргумент, стоящий после нее, или на выражение в скобках, если после символа отрицания сразу идет скобка. Остальное все, как в математике - сначала вычисляются значения в скобках, потом выполняется умножение и в самом конце сложение.
Решение задач "ручками"
ЕГЭ по информатике уже два года сдается на компьютерах, и многие задачи, изначально предлагаемые к решению на листочке, теперь можно решить с использованием ЭВМ (так еще говорят вообще?))
Несмотря на это, я за то, чтобы уметь решать задачи по-старинке ручками на листочке. Зачем?
Во-первых, если вы сразу лезете программировать, скорее всего, вы не "чувствуете" задачу и не можете определить, насколько адекватен ответ, полученный программно.
Во-вторых, на экзамене случается всякое. Ваша ЭВМ (простите 😂) может зависнуть, и вы будете сидеть и ждать ее возвращения в строй, тратя драгоценное время, в то время как могли бы решить за это время задачу ручками.
Поэтому - решим эту задачку ручками! Сразу оговорюсь - она простая, точно не уровня ЕГЭ-2023, но подходит для того, чтобы разобраться с темой.
Дублирую условие:
Решение:
Смотрим на вопрос - нужно определить, при каких значениях аргументов функция истинна. Смотрим на выражение. Последнее действие (два последних действия) - дизъюнкция. То есть, у нас есть логическая сумма трех скобок, которая должна быть равна 1. По правде говоря, когда мы дошли до этого утверждения, мы уже почти решили задачу.
Когда логическая сумма (т.е. результат логического сложения) будет истинной? Когда хотя бы одно слагаемое равно 1. У нас таких слагаемых три - три скобки. Выходит, нужно посмотреть, при каком наборе аргументов значение каждой скобки получается истинным.
Итак, ¬x ∧ y ∧ z = 1. Что это за выражение? Это логическое произведение трех аргументов. Когда результат конъюнкции будет истинным? Когда каждый логический множитель равен 1. Получается, ¬x=1 (то есть x=0), y=1, z=1. Нашли первый набор аргументов: x=0, y=1, z=1.
Аналогичным образом находим еще два набора аргументов: x=0, y=0, z=1 и x=0, y=0, z=0.
Теперь нужно сопоставить наши решения (наборы аргументов, при которых функция истинна) приведенным в таблице. Смотрим на картинку:
Еще раз пропишу алгоритм действий:
- Выясняем, какое действие выполняется последним (как в математике, читаем выражение по типу "сумма/произведение синуса и косинуса").
- Отвечаем на вопрос - когда это выражение будет истинно/ложно (Когда сумма будет равна 0? - Когда все слагаемые равны 0. Когда произведение равно 0? - Когда хотя бы один множитель равен 0. И т.п.)
- Смотрим, при каком наборе аргументов наши скобки будут принимать значение, которое мы определили в п.2.
- Выписываем наборы аргументов, определенные в п.3, в табличку. Сопоставляем нашу табличку таблице из условия.
Формулировки заданий и выражения для логических функций могут быть разными, алгоритм решения, в общем-то, одинаков.
Для тех, кто не хочет решать ручками, даю ссылку на это задание на сайте РешуЕГЭ, там в решении есть пример написания программы для поиска удовлетворяющих заданию аргументов на Python (обратите внимание, как заботливо я проставляю для вас все ссылочки: знаю, что многие поленятся сразу искать сами и оставят это на никогда не наступящее "потом"). Оговорюсь, что на экзамене я рекомендую искать наборы аргументов именно таким, программным, образом. Но мне нужно, чтобы, если программа выдала четыре решения вместо трех, ученик сразу понял, что допустил в коде опечатку, а не продолжил решать задачу дальше.
Несколько примеров ("на И", дерево решений, лишние строки)
Продолжим решать задачи второго типа ручками. Задачу "на или" (мое название) мы рассмотрели выше. Дальнейшие названия задач тоже будут "авторскими", они нужны для понимания специфики решения конкретного задания.
Задача "на И"
Рассмотрим задачу №1620 с сайта Полякова:
Такие задачи я называю "задачами на И", так как конъюнкция - последнее действие в выражении, задающем логическую функцию F.
Нам нужно определить, при каких наборах аргументов функция F будет ложна. Вспоминаем, когда результат логического умножения будет ложным - когда хотя бы один из множителей равен 0 (как и в обычной математике).
Наше выражение представляет собой логическое произведение двух скобок. Приравняем к нулю каждую из них.
Первая скобка ¬x ∨ y ∨ z = 0. Перед нами логическая сумма трех слагаемых. Когда результат дизъюнкции будет ложным? Тогда, когда все слагаемые будут равны 0. Находим набор аргументов, обращающих первую скобку в 0: x=1, y=0, z=0.
Вторая скобка ¬x ∨ ¬z = 0. Это логическая сумма трех слагаемых. Определяем, при каком наборе значений переменных она будет ложной: x=1, z=1. А чему должен быть равен y? Так как y не входит в эту скобку, то значение выражения в ней не зависит от значения y, и оно может быть любым: и 0, и 1. Получается, из второй скобки мы получили два набора аргументов: x=1, y=0, z=1 и x=1, y=1, z=1.
Теперь выписываем полученные наборы значений аргументов (их еще можно называть решениями уравнения F=0) в табличку и сопоставляем их с приведенными в условии. Получаем ответ yzx.
Задача с лишними строками. Дерево решений
Мы все еще абстрагируемся от возможности находить наборы значений переменных программно) На примере следующей задачи покажу, как еще можно решать задачи второго типа.
Смотрим на выражение. Это логическое произведение двух множителей. Чтобы результат конъюнкции был истинным, нужно, чтобы каждый множитель был равен 1. Пока все, как обычно. Дальше нужно смотреть на скобки.
В первой скобке стоит импликация. Таблица истинности для импликации содержит три набора значений аргументов, при которых ее результат будет истинным. Их, конечно, можно перечислить. Но одновременно с этим должна быть равна 1 вторая скобка.
Во второй скобке - отрицание конъюнкции. Чтобы оно было равно 1, результат конъюнкции z ∧ x должен быть равен 0. Вспоминаем, что конъюнкция равна 0 тоже при трех наборах аргументов.
Наборы аргументов, обращающие первую и вторую скобки в 1, нужно как-то пересечь.
Как это можно делать?
- В лоб. Выписать три набора y и z, при которых первая скобка обращается в 1. Вспомнить, что каждое из этих решений порождает два (х в скобку не входит, так что он может быть любым). Получим шесть наборов значений переменных из первой скобки и аналогичным образом шесть наборов из второй. Некоторые наборы будут повторяться. Так как нам нужно, чтобы скобки одновременно были истинными, в таблицу решений включаем те наборы переменных, которые являются одинаковыми. И ищем соответствие между таблицей из условия и нашими решениями.
- Построить дерево решений. Строго говоря, мы делаем то же самое, что и при решении "в лоб", просто неподходящие варианты будем отбрасывать сразу. Решение приведено в галерее.
Домашнее задание
Я буду приучать вас использовать для подготовки к экзамену сайт К. Полякова. Да, там бывают задачи, близкие к олимпиадным, которые никогда никому не попадутся на ЕГЭ. Зато банк заданий на этом сайте своевременно пополняется новыми задачами и вы не встретите там устаревших формулировок заданий (по крайней мере, не в таком количестве, как на РешуЕГЭ).
Переходим по ссылочке, заботливо ведущей в раздел с задачами второго типа (хотя бы кто мне сердечко за это поставил, для вас же стараюсь) и решаем задачи №№ 5361, 5362, 5293, 5109, 5020, 4441, 3647.
Понимаете, что вам нужна помощь с подготовкой к экзамену?
У меня ещё есть окна для офлайн занятий. Я провожу уроки с использованием графического планшета, записи с занятия высылаю в виде pdf-файла. Пишите в личку или отметьтесь в комментариях, договоримся о первом занятии.
Нравится вам такой формат - теория, разбор задач? В каком виде удобнее читать решение - текстовом или на картинках в галерее? Напишите в комментариях, чтобы я могла делать материал удобным для изучения. И подписывайтесь на мой канал - при подготовке к экзамену все источники будут полезны.