Булева алгебра для ЕГЭ: вся теория и практика решения задач

Что такое булева алгебра и зачем она нужна на ЕГЭ?

На экзамене выпускнику предлагают странную таблицу, заполненную нулями и единицами, и просят выбрать формулу, которая ей соответствует. Или дают громоздкое выражение с заданием упростить его. Чтобы не растеряться, требуется освоить три простые операции: И, ИЛИ и НЕ. Именно на них строится вся алгебра логики.

Алгебра логики оперирует величинами, которые принимают только два значения: истина (1) или ложь (0). Это идеальный математический аппарат для описания работы компьютеров, цифровых схем и логических условий. В ЕГЭ по информатике он встречается в заданиях №2 и №15.

Британский математик Джордж Буль ещё в 1847 году предложил записывать логические высказывания в виде формул и выполнять над ними действия, похожие на сложение и умножение. Долгое время это была чистая теория, но с появлением компьютеров его идеи стали фундаментом цифровой эпохи.

Логические переменные и двоичная система

Логическая величина — это переменная, которая может быть равна только 0 или 1. Такой выбор не случаен: это прямое отражение двоичной системы счисления, на которой построены все компьютеры. Каждый бит информации — это и есть логическая переменная.

В выражениях переменные могут встречаться в двух видах: прямом (A) и с отрицанием (¬A). Такую пару называют литералом.

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

Три кита булевой алгебры — это конъюнкция (И), дизъюнкция (ИЛИ) и отрицание (НЕ). Их таблицы истинности необходимо знать наизусть.

Конъюнкция (И, ∧) — логическое умножение

A ∧ B истинно (равно 1) только в одном случае: когда оба операнда истинны. Это как строгий фильтр: если хоть одно условие не выполнено — результат ложь.

Пример из ЕГЭ: «Доступ к файлу разрешён, если пользователь ввёл верный логин И правильный пароль». Одно несовпадение — и вход закрыт.

Дизъюнкция (ИЛИ, ∨) — логическое сложение

A ∨ B истинно, если **хотя бы один** операнд истинен. Ложно только в одном случае: когда оба ложны.

Важно: логическое «ИЛИ» — не исключающее. Оно допускает, что могут сработать оба условия одновременно.

Пример из ЕГЭ: «Аварийная сигнализация срабатывает, если температура выше нормы ИЛИ давление упало ниже критического». Если сработали оба датчика — сигнал всё равно идёт.

Отрицание (НЕ, ¬) — инверсия

Отрицание просто переворачивает значение: 0 → 1, 1 → 0.

Порядок действий в логических выражениях

В булевой алгебре, как и в обычной, есть строгий порядок:

1. Отрицание (¬) — сначала.

2. Конъюнкция (∧) — потом.

3. Дизъюнкция (∨) — в последнюю очередь.

Это правило работает так же, как в математике: сначала умножение, потом сложение.

Типичная ошибка на ЕГЭ: путают порядок в выражении A ∨ B ∧ C. Правильно: сначала вычисляется B ∧ C, потом результат складывается с A. При сомнениях рекомендуется ставить скобки.

Законы булевой алгебры (как упрощать выражения)

На ЕГЭ редко дают простые выражения. Их требуется упрощать. Вот список главных законов, которые это позволяют.

Самые важные — законы де Моргана:

— ¬(A ∧ B) = ¬A ∨ ¬B.

— ¬(A ∨ B) = ¬A ∧ ¬B.

Они позволяют «протащить» отрицание внутрь скобок, поменяв И на ИЛИ и наоборот.

Запоминалка: если «НЕ» заходит в скобки, оно меняет знак операции на противоположный.

Алгоритм упрощения

Чтобы упростить выражение, следует действовать так:

1. Убрать двойные отрицания (¬(¬A) = A).

2. Применить законы де Моргана, чтобы избавиться от отрицаний сложных выражений.

3. Раскрыть скобки (дистрибутивность).

4. Использовать поглощение (A ∨ (A ∧ B) = A).

5. Удалить противоположности (A ∧ ¬A = 0, A ∨ ¬A = 1).

Пример: упростим ¬(¬A ∨ B) ∨ (A ∧ C).

— По де Моргану: ¬(¬A ∨ B) = A ∧ ¬B.

— Получаем: (A ∧ ¬B) ∨ (A ∧ C).

— Выносим A за скобки: A ∧ (¬B ∨ C).

Готово. Минимум.

СДНФ и СКНФ

Любую логическую функцию можно записать в стандартной форме.

СДНФ — сумма минтермов (конъюнкций, которые дают 1 только на одном наборе).

СКНФ — произведение макстермов (дизъюнкций, которые дают 0 только на одном наборе).

Пример: функция истинна на наборах (0,1) и (1,0).

СДНФ = (¬A ∧ B) ∨ (A ∧ ¬B)**

Карты Карно

Для функций от 2–4 переменных удобно использовать карты Карно. Это таблица, где соседние клетки отличаются значением ровно одной переменной.

Правило: объединяются соседние единицы в блоки (1, 2, 4, 8 клеток). Каждый блок даёт одну конъюнкцию, из которой уходят «меняющиеся» переменные. Это и есть минимальная форма.

Таблицы истинности: как строить

Алгоритм:

1. Определяется количество переменных n — строк будет 2ⁿ.

2. Перечисляются все наборы (для n=3: 000, 001, 010, 011, 100, 101, 110, 111).

3. Вычисляются промежуточные значения, соблюдая приоритет.

4. Записывается итог.

Пример: F = (A ∧ B) ∨ ¬C.

Решение заданий ЕГЭ

Задание №2: таблица → формула

Подход: подставляются известные наборы в каждый вариант ответа и отсекаются неверные. Достаточно найти одно противоречие.

Пример: дана строка (x=0, y=1, z=0) → F=1.

— Вариант F = x ∧ y → 0 ∧ 1 = 0 → не подходит.

— Вариант F = y ∧ ¬z → 1 ∧ 1 = 1 → кандидат.

Проверяется второй набор — и находится верный ответ.

Задание №15: упрощение

Пример: упростить ¬(A ∧ B) ∨ ¬(¬A ∨ ¬B).

1. По де Моргану: ¬(¬A ∨ ¬B) = A ∧ B.

2. Получаем: ¬(A ∧ B) ∨ (A ∧ B).

3. Это X ∨ ¬X = 1. Ответ: 1.

Логические схемы

Элементы И, ИЛИ, НЕ соединяются в схемы. Чтобы записать формулу по схеме, проходится путь от входов к выходу.

Пример: A → НЕ → ∧ (с B) → ∨ (с A).

Формула: (¬A ∧ B) ∨ A.

Как избежать ошибок на ЕГЭ

1. Скобки в черновике расставляются обязательно — они спасают от ошибок в приоритете.

2. Результат проверяется на крайних наборах (все 0, все 1).

3. Не следует путать импликацию и эквивалентность. Импликация **A → B** ложна только при **A=1, B=0**.

4. Полезно тренироваться на задачах из открытого банка ФИПИ.

Часто задаваемые вопросы

Что такое булева алгебра простыми словами?

Раздел математики, где всё — 0 или 1, а операции — И, ИЛИ, НЕ.

Как составить таблицу истинности для ЕГЭ?

Определяется число строк (2ⁿ), перебираются все наборы, вычисляются значения с соблюдением приоритета.

Законы де Моргана простыми словами?

Отрицание «И» становится «ИЛИ» с отрицаниями. Отрицание «ИЛИ» становится «И» с отрицаниями.

Как упростить логическое выражение?

Убираются двойные отрицания, применяются законы де Моргана, раскрываются скобки, используется поглощение.

Какие задания ЕГЭ по информатике связаны с булевой алгеброй?

№2 (таблицы истинности) и №15 (упрощение, равносильность, схемы).

Что такое СДНФ и СКНФ?

Способы стандартной записи логических функций. СДНФ — сумма произведений (по единицам), СКНФ — произведение сумм (по нулям).

Приоритет логических операций в ЕГЭ?

Сначала НЕ, потом И, потом ИЛИ. Скобки меняют порядок.

Понимание булевой алгебры — ключ к успешному решению заданий №2 и №15 на ЕГЭ по информатике. Это превращает механическое заучивание формул в уверенное владение логическим аппаратом.

В онлайн-школе ЕГЭLAND преподаватели информатики помогают освоить законы булевой алгебры, учат быстро строить таблицы истинности и упрощать логические выражения, а также разбирают типовые задачи из открытого банка ФИПИ. Записаться на пробное занятие можно на сайте школы.