Теория для 18 задания ЕГЭ по информатике
Основная тема задания №18 — алгебра логики. С неё и начнём. Для успешного решения номера вам важно знать 3 теоретических момента:
- Основные логические операции
- Порядок логических операций
- Законы логики
Основные логические операции
1. Инверсия «НЕ»
Логическое отрицание
Обозначения: ¬А, Ā
Меняет значение на противоположное
2. Конъюнкция «И»
Логическое умножение
Обозначения: А∧В, А & В, А и В, AB
Принимает значение «истина», когда все значения единицы.
Хотя бы один 0 обнуляет всё.
3. Дизъюнкция «ИЛИ»
Логическое сложение
Обозначения: А∨В, А | В, А или В
Принимает значение «истина», когда хотя бы одна единица. «Ложь», когда все нули.
4. Импликация "Если, то"
Следование
Обозначения: А→В, А => В
Из истины следует истина, из лжи что угодно
5. Эквивалентность «Равны»
Тождество
Обозначения: А≡В, А <=> В
Иcтина, когда значения одинаковы. Ложь, когда различны
Порядок логических операций
- Действия в скобках
- Инверсия
- Конъюнкция
- Дизъюнкция
- Импликация
- Эквивалентность
Законы логики
Законов логики существует огромное количество, но именно для ЕГЭ достаточно знать 10 законов из данной таблицы. Некоторые из них очевидные, некоторые придётся выучить.
Практика
В различных источниках и базах задач ЕГЭ по информатике вы можете встретить множество разных типов задания №18. Но важно понимать, что последние 3 года на ЕГЭ был ровно 1 тип, и он же представлен в Демо-версии 2020 года: алгебра логики и математические неравенства. Поэтому в данной статье разберём задания именно этого типа.
Подтип №1. Переменные x и y возможно рассмотреть отдельно
Пример задания:
Для какого наименьшего целого числа A выражение
((x · x < A)∨(x ≥ 8)) ∧ ((y · y < A) → (y < 8))
тождественно истинно (то есть принимает значение 1 при любых целых неотрицательных значениях переменных x и y)?
Решение:
Выражение состоит из двух больших скобок, между которыми стоит знак конъюнкции. Выражение должно быть тождественно истинно. Вспоминаем из теории, что конъюнкция истинна только тогда, когда обе скобки равны 1. Вывод:
(x · x < A) ∨ (x ≥ 8) ≡ 1
(y · y < A)→(y < 8) ≡ 1
Поскольку в первом выражении остались только иксы, а во втором только игреки, x и y можно рассматривать отдельно друг от друга.
Решим первое выражение. Оно должно быть истинным при любых иксах.(x · x < A) ∨ (x ≥ 8) ≡ 1
Заметим, что при x ≥ 8 (вторая скобка), выражение будет истинным, независимо от первой скобки, поскольку между ними стоит дизъюнкция. Нам необходимо покрыть все целые неотрицательные значения x, поэтому осталось покрыть значения x ⩽ 7 или x · x ⩽ 49.
Выражение x · x < A должно полностью покрыть все значения x·x ⩽ 49. Такое возможно, только если А будет > 49. Поскольку А целое, ответ на первое выражение: A ≥ 50.
Решим второе выражение. Оно должно быть истинным при любых игреках.
(y · y < A) → (y < 8) ≡ 1
Упростим его по закону преобразования импликации:
¬(y · y < A) ∨ (y < 8) ≡ 1
или
(y · y ≥ A) ∨ (y < 8) ≡ 1
Заметим, что при y < 8 (вторая скобка), выражение будет истинным, независимо от первой скобки, поскольку между ними стоит дизъюнкция. Нам необходимо покрыть все целые неотрицательные значения y, поэтому осталось покрыть значения y ≥ 8 или y · y ≥ 64.
Выражение y · y ≥ A должно полностью покрыть все значения y·y≥ 64. Такое возможно, только если А будет меньше либо равно 64. Ответ на второе выражение: А ⩽ 64.
Пересекаем решения A ≥ 50 и А ⩽ 64, ищем наименьшее А (по условию). Получаем ответ:
А = 50
Подтип №2. Переменные x и y необходимо рассматривать совместно
Пример задания:
Для какого наименьшего целого неотрицательно числа A выражение
(x + 2 · y ≤ A) ∨ (x > 25) ∨ (y > 12)
тождественно истинно (то есть принимает значение 1 при любых целых неотрицательных значениях переменных x и y)?
Заметим, что при x > 25 или при y > 12 наше выражение уже принимает значение истина, т.к. 3 скобки соединяет дизъюнкция, которая истинна, когда хотя бы одна скобка истинна.
Следовательно, первая скобка должна покрывать область, когда x ⩽ 25 и y ⩽ 12.
Подставим граничные значения x = 25 и y = 12 в первую скобку. Получим:
25 + 2 · 12 ≤ A
49 ≤ A
А ≥ 49
Нас интересует наименьшее целое А. Получаем ответ:
А = 49