Логические выражения и таблицы истинности: как строить, читать и считать наборы
С логическими выражениями проще всего справиться, если не угадывать ответ, а построить таблицу истинности: перебрать все наборы значений и вычислить выражение по шагам. Ниже мы повторим основные операции и порядок их выполнения, построим таблицу для трёх переменных и научимся по нескольким строкам таблицы находить нужную функцию.
Пять операций, которые нужно знать наизусть
В задачах используются отрицание ¬ (НЕ), конъюнкция ∧ (И), дизъюнкция ∨ (ИЛИ), импликация → («если A, то B») и эквиваленция ↔ («A тогда и только тогда, когда B»). Значения операций над двумя переменными удобно держать в одной таблице.
| A | B | A ∧ B | A ∨ B | A → B | A ↔ B |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 |
Запомнить проще через «особые случаи»: конъюнкция истинна лишь при двух единицах, дизъюнкция ложна лишь при двух нулях, импликация ложна только при A = 1, B = 0, эквиваленция истинна, когда значения совпадают.
В каком порядке вычислять
Операции выполняются в таком порядке: сначала скобки, затем ¬, потом ∧, затем ∨ и в последнюю очередь → и ↔. Поэтому запись A ∨ B ∧ C означает A ∨ (B ∧ C), а не (A ∨ B) ∧ C.
Строим таблицу для трёх переменных по шагам
Задача. Построй таблицу истинности для F = (A ∨ B) ∧ ¬(B ∧ C) и скажи, на скольких наборах F истинно.
Решение. У трёх переменных 23 = 8 наборов. Добавим столбцы для промежуточных значений: A ∨ B, затем B ∧ C, затем ¬(B ∧ C), и в конце F.
| A | B | C | A ∨ B | B ∧ C | ¬(B ∧ C) | F |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 | 0 |
Единицы в последнем столбце стоят в четырёх строках.
Ответ: F истинно на 4 наборах.
Наборы всегда перечисляй в порядке возрастания двоичного числа (000, 001, 010, …): так ты не пропустишь ни одного набора.
Угадываем функцию по строкам таблицы
В экзамене часто дают лишь несколько строк таблицы и просят выбрать подходящее выражение. Лучший способ - подставлять строки в варианты и вычёркивать те, что не совпали.
Задача. Фрагмент таблицы истинности функции F(x, y, z): строка (1, 0, 0) даёт F = 1, строка (0, 1, 0) даёт F = 0, строка (1, 1, 1) даёт F = 0. Какое выражение подходит: (x ∨ y) ∧ ¬z; x ∧ (y → z); x → y; x ∧ ¬y?
Решение. Проверим каждое выражение по строкам. Для (x ∨ y) ∧ ¬z строка (0, 1, 0) даёт (0 ∨ 1) ∧ 1 = 1, но нужно 0, вариант не подходит. Для x ∧ (y → z) строка (1, 1, 1) даёт 1 ∧ 1 = 1, а нужно 0. Для x → y строка (1, 0, 0) даёт 0, а нужно 1. Остаётся x ∧ ¬y: на строках получаем 1 ∧ 1 = 1, 0 ∧ 0 = 0 и 1 ∧ 0 = 0, все три совпадают.
Ответ: x ∧ ¬y.
Обрати внимание: мы не доказывали, что выбранная формула верна для всех восьми наборов. Нам достаточно того, что три остальных варианта точно не подходят.
Сколько наборов делают выражение истинным
Иногда достаточно знать, сколько единиц в столбце результата. Для этого не обязательно строить всю таблицу: полезно разбирать выражение по смыслу.
Задача. Сколько существует наборов (x, y, z), для которых (x ∧ y) ∨ (¬x ∧ z) = 1?
Решение. Разберём два случая. При x = 1 второе слагаемое обращается в нуль, остаётся y: выражение истинно при y = 1, а z любое, то есть 2 набора. При x = 0 первое слагаемое равно нулю, остаётся z: истинно при z = 1, а y любое, и это ещё 2 набора. Всего 2 + 2 = 4.
Ответ: 4.
Такой приём называется разбором по значению одной переменной. Он быстрее полной таблицы, когда переменных больше трёх. Тренироваться на подобных подсчётах можно в тесте по логике.
Упрощаем выражение по законам де Моргана
Отрицание вносится в скобки с заменой операции: ¬(A ∨ B) = ¬A ∧ ¬B и ¬(A ∧ B) = ¬A ∨ ¬B. Двойное отрицание сокращается: ¬¬A = A. Импликацию можно заменить на A → B = ¬A ∨ B.
Например, ¬(A ∨ ¬B) = ¬A ∧ ¬¬B = ¬A ∧ B. Убедимся с помощью таблицы: при A = 0, B = 1 исходное выражение равно ¬(0 ∨ 0) = 1, и ¬A ∧ B = 1 ∧ 1 = 1. Во всех остальных наборах оба выражения равны нулю.
Если сомневаешься в преобразовании, не доверяй памяти: проверь его на таблице истинности. Для двух переменных это всего четыре строки, и ошибка сразу станет заметна.
Проверь себя
Для скольких наборов значений (A, B) истинно выражение A ∨ ¬B?
Какое выражение равносильно ¬(A ∨ ¬B)?
Для какого набора значений (x, y, z) ложно выражение x → (y ∧ z)?
Частые вопросы
Как запомнить, когда импликация ложна?
Сколько строк в таблице для пяти переменных?
Чем отличаются обозначения ∧, &, И?
Читай дальше
Материалы подготовлены с помощью ИИ и проверены автоматически: все вычисления пересчитаны программой, а ответы сверены независимым решением. Если нашёл ошибку или неточность, напиши на vortexlearn.offical@gmail.com - исправим.