Ах, ЕГЭ по информатике — тот самый экзамен, где логика и программирование встречаются в смертельном танце под названием «Задание 2». Если вы думали, что алгебра логики — это скучная история про нули и единицы, то приготовьтесь: сейчас мы превратим её в комедию ошибок и забавных открытий!
Итак, представьте себе Мишу.
Миша решил заняться заполнением таблицы истинности для функции F = ¬(x → z) ∨ (y ≡ w) ∨ y. Взялся он за дело с энтузиазмом студента на первом курсе, но успел заполнить лишь три строки и… потерялся, как кот в новой коробке.
Не указал ни один столбец переменной! Вот вам классика: вроде всё просто, а голова кругом.
На самом деле задание 2 ЕГЭ — это как раз тот случай, когда надо уметь быстро ориентироваться в логических функциях и их таблицах истинности.
И не переживайте — времени даётся всего около трёх минут. Три минуты! За это время можно сварить кофе, проверить соцсети и решить пару логических задачек.
Главное — знать алгоритм действий.
Первое правило Мишиных приключений: если функция задана через дизъюнкцию (∨), чтобы вся функция была ложной, все части должны быть ложными. Это как если бы вы пытались уговорить трёх друзей пойти на вечеринку, но каждый из них говорит «нет» — значит вечеринка не состоится. Логично?
Логично!
В нашем случае функция разбивается на три части: ¬(x → z), (y ≡ w) и y. Чтобы функция была ложной, каждая из этих частей должна быть ложной сама по себе.
Например, если y должно быть ложным (ну или нулём), то тут уже можно прикинуть: если y равно нулю, а (y ≡ w) ложно — значит w должен быть равен единице. А дальше начинается веселье: x → z — это условное высказывание; оно ложно только тогда, когда x истинно (1), а z ложно (0). Разве не забавно?
Как будто x пытается сказать «если я буду правдой», а z отвечает «нет уж!» и всё рушится.
Кстати говоря, про условные высказывания напоминает анекдот: «Если завтра будет дождь — я останусь дома». Но сегодня нет дождя… Значит я могу пойти гулять! Вот так работает импликация в логике.
Вернёмся к таблице истинности. Вы же знаете эту загадочную штуку с кучей единичек и ноликов?
Иногда кажется, что она создана специально для того, чтобы свести с ума даже самых стойких студентов и программистов-новичков.
Но есть два пути решения: можно взять карандаш и начать дописывать недостающие значения вручную (да-да, как в старые добрые времена), а можно написать программу на Python! Ведь Python — этакий волшебник среди языков программирования: пару строк кода — и задача решена без усилий.
Однако пока оставим кодировщиков в покое и попробуем разобраться вручную. Сначала разделяем функцию на части по дизъюнкции — это как делить пиццу между друзьями: каждый кусок должен быть понятен и отделён от другого.
Далее смотрим на каждую часть отдельно.
Если нам нужно получить ложь для всей функции F при определённых входах переменных — значит все эти части тоже должны быть ложными одновременно. Это правило проще запомнить чем список покупок перед походом в супермаркет.
После этого идёт самое интересное: сопоставляем столбцы таблицы с переменными w,x,y,z так, чтобы все условия выполнялись одновременно.
Тут пригодится чутьё детектива Шерлока Холмса или хотя бы чувство юмора программиста после пятой чашки кофе.
Вспомните шутку про программиста:
— Почему программисты путают Хэллоуин и Рождество?
— Потому что Oct 31 == Dec 25!