Задание 18. Алгебра логики. Преобразование и анализ логических выражений. ЕГЭ 2021 по информатике

За это задание ты можешь получить 1 балл. На решение дается около 3 минут. Уровень сложности: повышенный.
Средний процент выполнения: 32.2%
Ответом к заданию 18 по информатике может быть цифра (число) или слово.

Теория к 18 заданию: читать

Задачи для практики

Показать еще

Теория для 18 задания ЕГЭ по информатике


Основная тема задания №18 — алгебра логики. С неё и начнём. Для успешного решения номера вам важно знать 3 теоретических момента:

  1. Основные логические операции
  2. Порядок логических операций
  3. Законы логики

Основные логические операции

1. Инверсия «НЕ»
Логическое отрицание
Обозначения: ¬А, Ā
Меняет значение на противоположное

Таблица истинности для инверсии
Таблица истинности для инверсии

2. Конъюнкция «И»
Логическое умножение
Обозначения: А∧В, А & В, А и В, AB
Принимает значение «истина», когда все значения единицы.
Хотя бы один 0 обнуляет всё.

Таблица истинности для конъюнкции
Таблица истинности для конъюнкции

3. Дизъюнкция «ИЛИ»
Логическое сложение
Обозначения: А∨В, А | В, А или В
Принимает значение «истина», когда хотя бы одна единица. «Ложь», когда все нули.

Таблица истинности для дизъюнкции
Таблица истинности для дизъюнкции

4. Импликация "Если, то"
Следование
Обозначения: А→В, А => В
Из истины следует истина, из лжи что угодно

Таблица истинности для импликации
Таблица истинности для импликации

5. Эквивалентность «Равны»
Тождество
Обозначения: А≡В, А <=> В
Иcтина, когда значения одинаковы. Ложь, когда различны

Таблица истинности для эквивалентности
Таблица истинности для эквивалентности

Порядок логических операций

  1. Действия в скобках
  2. Инверсия
  3. Конъюнкция
  4. Дизъюнкция
  5. Импликация
  6. Эквивалентность

Законы логики

Законов логики существует огромное количество, но именно для ЕГЭ достаточно знать 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

Готовим к ЕГЭ на 85+ баллов и побеждаем лень

Каждый месяц 12 онлайн-занятий в дружелюбной атмосфере + 16 домашних работ с жесткими сроками.
Не готовишься — вылетаешь.

Подробнее о курсе