Логические задачи на поиск количества решений: ЕГЭ по информатике

Тема посвящена решению логических уравнений и систем уравнений с подсчётом количества различных решений. В ЕГЭ по информатике это задание повышенной сложности (обычно №23), где требуется найти число наборов переменных, при которых логическое выражение истинно. Ключевые приёмы: приведение к ДНФ/КНФ…

Что нужно знать

• Логическое уравнение — равенство двух логических выражений; решением является набор значений переменных, при котором уравнение обращается в истину.
• Система логических уравнений — несколько уравнений, решением которой является набор, удовлетворяющий всем уравнениям одновременно.
• Основные логические операции: НЕ (¬), И (∧), ИЛИ (∨), импликация (→), эквивалентность (↔).
• Таблицы истинности для базовых операций: ¬A, A∧B, A∨B, A→B (ложна только при 1→0), A↔B (истинна при совпадении значений).
• Законы алгебры логики: де Моргана, дистрибутивности, поглощения, исключения импликации (A→B = ¬A∨B), исключения эквивалентности (A↔B = (A∧B)∨(¬A∧¬B)).
• Метод замены переменных: введение новых переменных для упрощения системы, особенно при цепочках импликаций.

Термины и понятия

• Логическая переменная: переменная, принимающая значения 0 (ложь) или 1 (истина).
• Логическое выражение: формула, составленная из переменных и логических операций.
• Тавтология: логическое выражение, истинное при любых значениях переменных.
• Противоречие: логическое выражение, ложное при любых значениях переменных.
• ДНФ (дизъюнктивная нормальная форма): дизъюнкция конъюнктов.
• КНФ (конъюнктивная нормальная форма): конъюнкция дизъюнктов.
• Импликация: логическая операция A→B, ложная только когда A истинно, а B ложно.
• Эквивалентность: логическая операция A↔B, истинная при совпадении значений A и B.

Частые ошибки

• Путаница в таблице истинности импликации: считают, что 1→0 истинно, или наоборот.
• Ошибки при раскрытии эквивалентности: забывают, что A↔B истинно и при (0,0), и при (1,1).
• Неправильное применение законов де Моргана: ¬(A∧B) ≠ ¬A∧¬B, а ¬A∨¬B.
• При построении дерева решений теряют ветви или не учитывают зависимости между переменными.

Как пройти тему

В курсе «Информатика» тема «Логические задачи на поиск количества решений» занимает 2 занятия по 40 минут: репетитор объясняет материал, задаёт вопросы как на экзамене, разбирает ваши ответы и в конце ставит оценку. Это обзор темы, полный разбор — в занятии. ИИ может ошибаться: проверяйте важное по учебнику. Занятия не заменяют живого репетитора и не гарантируют результат на экзамене.

Другие темы раздела

• Высказывания. Логические операции: НЕ, И, ИЛИ, импликация, эквивалентность
• Таблицы истинности. Построение и анализ
• Законы алгебры логики. Упрощение логических выражений
• Решение логических уравнений и систем уравнений

← Предыдущая тема: Решение логических уравнений и систем уравнений
Следующая тема: Понятие алгоритма. Свойства алгоритмов. Способы записи

Все темы: ЕГЭ по информатике