Алгебра логики: таблицы истинности, законы, преобразования выражений
Ты научишься строить таблицы истинности, применять законы логики и упрощать логические выражения.
Зачем на экзамене
Алгебра логики помогает определить, при каких значениях условий выражение истинно. Для заданий 2 и 15 тебе понадобятся таблицы истинности, эквивалентные преобразования и аккуратная работа с отрицанием. Эти навыки позволяют заменить перебор коротким рассуждением или проверить найденный ответ.
Что нужно уметь
- вычислять значения основных логических операций;
- учитывать приоритет операций и правильно расставлять скобки;
- строить таблицу истинности для выражения;
- заменять импликацию и эквиваленцию через NOT, AND и OR;
- применять законы де Моргана и другие эквивалентности;
- упрощать выражение и проверять результат таблицей истинности.
База
Логические значения и операции
Логическая переменная принимает два значения: 0 означает ложь, 1 означает истину. Результат любой логической операции тоже равен 0 или 1.
- NOT, отрицание: ¬A меняет значение A на противоположное.
- AND, конъюнкция: A ∧ B истинно, только если истинны оба высказывания.
- OR, дизъюнкция: A ∨ B истинно, если истинно хотя бы одно высказывание. Это включающее "или": при A = 1 и B = 1 результат тоже равен 1.
- Импликация: A → B ложна только в случае A = 1 и B = 0.
- Эквиваленция: A ↔ B истинна, когда A и B имеют одинаковые значения.
| A | B | ¬A | A ∧ B | A ∨ B | A → B | A ↔ B |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 |
Приоритет операций
Сначала вычисляй выражения в скобках. Затем выполняй отрицание, конъюнкцию, дизъюнкцию, импликацию и эквиваленцию. Получается порядок: скобки, NOT, AND, OR, →, ↔. Если запись допускает разные толкования, поставь скобки явно. Например, ¬A ∧ B означает (¬A) ∧ B, а не ¬(A ∧ B).
Таблица истинности
Если в выражении n разных переменных, таблица содержит 2^{n} наборов их значений. Для двух переменных это 4 строки, для трех: 8, для четырех: 16. Перебирай наборы в одном порядке и добавляй отдельный столбец для каждой промежуточной операции. Так легче найти ошибку.
Основные эквивалентности
Эквивалентные выражения принимают одинаковые значения при всех наборах переменных. Знак ≡ показывает такую равносильность.
| Правило | Эквивалентность |
|---|---|
| Двойное отрицание | ¬¬A ≡ A |
| Законы де Моргана | ¬(A ∧ B) ≡ ¬A ∨ ¬B; ¬(A ∨ B) ≡ ¬A ∧ ¬B |
| Импликация | A → B ≡ ¬A ∨ B |
| Противоречие и исключенное третье | A ∧ ¬A ≡ 0; A ∨ ¬A ≡ 1 |
| Константы | A ∧ 1 ≡ A; A ∨ 0 ≡ A; A ∧ 0 ≡ 0; A ∨ 1 ≡ 1 |
| Поглощение | A ∨ (A ∧ B) ≡ A; A ∧ (A ∨ B) ≡ A |
| Распределение | A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C) |
Для эквиваленции полезны две формы:
A \leftrightarrow B \equiv (A \land B) \lor (\neg A \land \neg B) \equiv (A \to B) \land (B \to A)Операции AND и OR можно переставлять и группировать: A ∧ B ≡ B ∧ A, A ∨ B ≡ B ∨ A. Это помогает вынести общий множитель или поставить рядом выражение и его отрицание.
Как решать
Если нужна таблица истинности
- Выпиши все разные переменные.
- Создай 2^{n} строк и перебери все наборы нулей и единиц.
- Раздели выражение на операции по скобкам и приоритету.
- Посчитай промежуточные столбцы слева направо.
- Проверь итоговый столбец по смыслу операций: импликация имеет единственный ложный случай, эквиваленция истинна при равных значениях.
Если нужно преобразовать выражение
- Убери импликации по правилу A → B ≡ ¬A ∨ B.
- Раскрой эквиваленции, если они мешают упрощению.
- Перенеси отрицания внутрь скобок по законам де Моргана.
- Убери двойные отрицания.
- Примени распределение, поглощение и правила для 0 и 1.
- Проверь равносильность на нескольких наборах, а при сомнении построй полную таблицу.
Не раскрывай все скобки автоматически. Сначала ищи короткие конструкции: A ∧ ¬A, A ∨ ¬A, A ∨ (A ∧ B). Они часто сокращают выражение за один шаг.
Частые ошибки
- Ошибка: считать импликацию аналогом AND. Как избежать: запомни ее единственный ложный набор: 1 → 0.
- Ошибка: понимать OR как выбор ровно одного варианта. Как избежать: проверь строку 1 ∨ 1. Результат равен 1.
- Ошибка: при отрицании скобки поменять операции, но не отрицать переменные. Как избежать: в законе де Моргана сделай два действия: замени ∧ на ∨ или наоборот и поставь отрицание перед каждым элементом.
- Ошибка: пропустить набор значений в таблице. Как избежать: заранее посчитай число строк как 2^{n}.
- Ошибка: вычислять длинное выражение одним столбцом. Как избежать: выдели отдельный столбец для каждого действия.
- Ошибка: принять совпадение на одном наборе за эквивалентность. Как избежать: сравни выражения на всех наборах переменных.
Проверь себя
- Сколько строк нужно в таблице истинности для четырех переменных?
- Чему равна импликация A → B при A = 1 и B = 0?
- Замени выражение ¬(A ∧ B) по закону де Моргана.
- Когда эквиваленция A ↔ B равна 1?
- Упрости выражение A ∨ (A ∧ B).
Ответы: 1) 16; 2) 0; 3) ¬A ∨ ¬B; 4) когда A и B равны; 5) A.
Связь с заданиями
Для задания 2 тренируй точное чтение таблиц истинности, порядок вычислений и сравнение столбцов. Для задания 15 особенно полезны замена импликации, законы де Моргана и упрощение условий. В обоих случаях проверяй преобразование на допустимых наборах значений и не опирайся только на внешнее сходство формул.