Алгебра логики: таблицы истинности и законы
Операции, эквивалентности и чеклист преобразования логических выражений.
На экзамене
Задания 2 и 15. Нужны таблицы истинности, точный порядок операций и равносильные преобразования.
Формулы и факты
| Операция | Когда результат равен 1 |
|---|---|
| ¬A | A = 0 |
| A ∧ B | A = 1 и B = 1 |
| A ∨ B | Хотя бы один операнд равен 1 |
| A → B | Всегда, кроме A = 1 и B = 0 |
| A ↔ B | A и B равны |
Приоритет: скобки, ¬, ∧, ∨, →, ↔. Для n переменных таблица содержит 2^n строк.
| Закон | Эквивалентность |
|---|---|
| Импликация | A → B ≡ ¬A ∨ B |
| Де Морган | ¬(A ∧ B) ≡ ¬A ∨ ¬B; ¬(A ∨ B) ≡ ¬A ∧ ¬B |
| Двойное отрицание | ¬¬A ≡ A |
| Противоречие | A ∧ ¬A ≡ 0 |
| Исключенное третье | A ∨ ¬A ≡ 1 |
| Поглощение | A ∨ (A ∧ B) ≡ A; A ∧ (A ∨ B) ≡ A |
| Константы | A ∧ 1 ≡ A; A ∨ 0 ≡ A; A ∧ 0 ≡ 0; A ∨ 1 ≡ 1 |
Алгоритм
- Расставь скобки по приоритету операций.
- Если нужна таблица, выпиши все 2^n наборов переменных.
- Создай отдельный столбец для каждой промежуточной операции.
- Если нужно упростить выражение, сначала замени импликации и эквиваленции.
- Перенеси отрицания внутрь скобок по законам де Моргана и убери двойные отрицания.
- Примени правила для 0 и 1, поглощение и конструкции A ∧ ¬A, A ∨ ¬A.
- Проверь равносильность полной таблицей истинности.
Ловушки
- Путают: включающее OR и выбор ровно одного варианта. Сверь: 1 ∨ 1 = 1.
- Путают: импликацию и AND. Сверь: единственный ложный случай импликации: 1 → 0.
- Путают: ¬A ∧ B и ¬(A ∧ B). Сверь: восстанови скобки по приоритету.
- Путают: совпадение на одном наборе и эквивалентность. Сверь: сравни все наборы.