Логика в информатике: таблицы истинности и запросы
Логика один из первых разделов информатики, и она встречается и в ОГЭ, и в ЕГЭ. При этом это просто аккуратное описание того, как мы рассуждаем: «и», «или», «не», «если… то». Разбираем логические операции на жизненных примерах, таблицы истинности и задачи, которые на них строятся.
Для 8–11 классов.
Пять операций
В логике высказывание либо истинно (1), либо ложно (0). Из простых высказываний складывают сложные с помощью операций.
| Операция | Обозначение | Когда истинна |
|---|---|---|
| отрицание, НЕ | ¬A | когда A ложно |
| конъюнкция, И | A ∧ B | только когда оба истинны |
| дизъюнкция, ИЛИ | A ∨ B | когда хотя бы одно истинно |
| импликация, ЕСЛИ… ТО | A → B | всегда, кроме случая A = 1, B = 0 |
| эквивалентность | A ≡ B | когда значения одинаковые |
Пример из жизни. «Я пойду гулять, если будет солнечно И я сделаю уроки»: нужны оба условия. «Возьму с собой яблоко ИЛИ банан»: хватит одного, а можно и оба. Логическое ИЛИ включающее, в отличие от бытового «или… или».
Импликация: самая странная операция
Импликация A → B читается «если A, то B». Её таблица удивляет: она ложна только в одном случае, когда A истинно, а B ложно.
Представьте обещание: «Если ты получишь пятёрку, я куплю тебе мороженое». Когда обещание нарушено? Только если пятёрка есть, а мороженого нет. Если пятёрки нет, обещание не нарушено, купят мороженое или нет. Отсюда знаменитое «из лжи следует что угодно»: при ложном A импликация всегда истинна.
Полезная замена, которая упрощает почти все задачи:
A → B = ¬A ∨ B
Таблица истинности
Таблица истинности перечисляет все наборы значений переменных и значение функции на каждом. Для одной переменной 2 строки, для двух 4, для трёх 8, для n переменных 2ⁿ.
Задача
Сколько наборов значений x, y, z делают функцию F = (x ∧ ¬y) ∨ z истинной?
Всего наборов 2³ = 8.
Если z = 1, F = 1 при любых x и y: это 4 набора.
Если z = 0, нужно x ∧ ¬y = 1, то есть x = 1 и y = 0: это 1 набор.
4 + 1 = 5.
Ответ: 5 наборов.
Приём «зафиксировать одну переменную и рассмотреть случаи» экономит время: не нужно выписывать всю таблицу. А на компьютерном ЕГЭ такие подсчёты удобно проверять перебором на Python, как в статье о решении задач перебором.
Законы, которые упрощают выражения
- Двойное отрицание: ¬¬A = A.
- Законы де Моргана: ¬(A ∧ B) = ¬A ∨ ¬B и ¬(A ∨ B) = ¬A ∧ ¬B. По-русски: «неверно, что и то и другое» значит «хотя бы одно неверно».
- Поглощение: A ∨ (A ∧ B) = A и A ∧ (A ∨ B) = A.
- Исключённое третье: A ∨ ¬A = 1, а A ∧ ¬A = 0.
Законы де Моргана встречаются в жизни постоянно. «Неверно, что сегодня холодно и идёт дождь» по логике значит «сегодня не холодно или нет дождя»: достаточно, чтобы не выполнялось хотя бы одно. А «неверно, что я возьму зонт или плащ» значит «не возьму ни зонт, ни плащ». При отрицании И превращается в ИЛИ, а ИЛИ в И.
Эти законы пригодятся и при программировании. Условие not (a > 0 and b > 0) можно переписать как a <= 0 or b <= 0, и иногда так код становится понятнее. А на ЕГЭ законы помогают упростить длинное выражение до такого, которое легко проверить в уме.
Задачи про поисковые запросы
В ОГЭ по информатике есть задачи, где в поисковой системе символ | означает ИЛИ, а & означает И. Нужно по количеству найденных страниц для одних запросов найти количество для другого. Решаются они через круги Эйлера и одну формулу:
|A ∪ B| = |A| + |B| − |A ∩ B|
Задача
По запросу «Крейсер | Линкор» найдено 7000 страниц, по запросу «Крейсер» 4800, по запросу «Крейсер & Линкор» 500. Сколько страниц найдётся по запросу «Линкор»?
Обозначим: |К ∪ Л| = 7000, |К| = 4800, |К ∩ Л| = 500.
Подставляем в формулу: 7000 = 4800 + |Л| − 500.
|Л| = 7000 − 4800 + 500 = 2700.
Ответ: 2700.
Почему вычитаем пересечение? Страницы, где есть оба слова, при сложении |К| + |Л| посчитались дважды. Нарисуйте два пересекающихся круга, и формула станет очевидной. В задачах с тремя словами кругов три, и удобнее подписать количество страниц в каждой из семи частей рисунка.
Где логика нужна за пределами экзамена
Каждая микросхема процессора собрана из миллиардов логических элементов И, ИЛИ, НЕ. Любое условие в программе, if x > 0 and y > 0, это логическое выражение. Фильтры в интернет-магазинах, расширенный поиск, настройки уведомлений: везде работают те же операции.
Алгебру логики придумал английский математик Джордж Буль в 1847 году. Тогда она казалась чистой философией, а через сто лет американский инженер Клод Шеннон показал, что по её законам можно проектировать электрические схемы. С этого началась цифровая техника.
Разберём на занятии
Занимаемся по всем школьным предметам с 4 по 11 класс: живые занятия, общая доска и домашка, которую проверяет тот же преподаватель.
Первое занятие бесплатное: можно посмотреть формат вместе с ребёнком и решить, подходит ли он.
Частые вопросы
Логика в ОГЭ и ЕГЭ одинаковая?
Основа одна, но в ОГЭ задачи проще: определить истинность высказывания для числа или посчитать страницы по запросам. В ЕГЭ функции длиннее, в них четыре-пять переменных и импликации, и их удобно разбирать перебором на компьютере.
Какой приоритет у операций?
Сначала отрицание, потом И, потом ИЛИ, потом импликация и эквивалентность. Как и в арифметике, скобки меняют порядок. В сомнительных местах лучше ставить скобки явно.
Почему в Python импликацию пишут как x <= y?
На значениях 0 и 1 сравнение x <= y ложно только при x = 1 и y = 0, ровно как импликация. Это удобный приём, но он работает только для логических значений.