В тетради восемь строк, столбцы переменных слева, столбики со скобками справа, и где-то посередине всё поплыло. Я это видел не раз: человек умеет считать каждую операцию, но не знает, в каком порядке заполнять клетки. Таблица не подвиг, а конвейер. Пять шагов, всегда одних и тех же.
Чему научишься. После урока сможешь: выписать все наборы значений для 3–4 переменных в правильном порядке; разбить выражение на столбцы-шаги Ш1, Ш2… по приоритету; заполнить таблицу до итогового столбца F; проверить, равны ли два выражения, сравнив их столбцы.
Вспомни. Сколько строк в таблице и таблицы НЕ, И, ИЛИ: урок «Таблицы истинности». Импликация, эквиваленция и лестница приоритетов разобраны в предыдущем уроке этой главы.
Конвейер из пяти шагов
КАК СТРОИТЬ ТАБЛИЦУ ЛЮБОГО ВЫРАЖЕНИЯ
шаг 1 Сосчитай переменные: n штук → строк будет 2ⁿ
(2 переменные → 4 строки, 3 → 8, 4 → 16)
шаг 2 Выпиши ВСЕ наборы значений по порядку (двоичный счёт)
шаг 3 Разбей выражение на столбцы по приоритету:
отрицания ¬x, ¬y — по столбцу на каждое, без номера;
каждая скобка — один столбец: Ш1, Ш2, Ш3 (шаг 1, 2, 3);
цепочка одинаковых ∧ внутри скобки — тоже один столбец
шаг 4 Заполняй столбцы слева направо, строку за строкой
шаг 5 Последний столбец — F, значение всего выражения
Как это в твоей тетради. Преподаватель подписывает столбцы П1, П2, П3 — это «Пер. 1, 2, 3», то есть переменные, а результаты скобок выносит правее и подписывает формулой. Чтобы не путать с тетрадью, столбцы-скобки здесь называю Ш1, Ш2 (шаг 1, шаг 2). Порядок переменных в тетради свой (z y x): это не ошибка, столбец F просто получится с переставленными строками, а число единиц и нулей в нём не изменится.
Шаг 2: наборы в порядке двоичного счёта
Самая частая ошибка: пропустить набор или записать один дважды. Лекарство простое: наборы совпадают с числами от 0 до 2ⁿ−1, записанными в двоичной системе (если помнишь двоичный счёт — это он; если нет, ниже правило без него). Для трёх переменных считаем от 000 до 111. Правая переменная меняется каждую строку, средняя через одну, левая через две.
ВСЕ НАБОРЫ ДЛЯ ТРЁХ ПЕРЕМЕННЫХ x y z (8 строк) № │ x │ y │ z │ ────┼───┼───┼───┤ 0 │ 0 │ 0 │ 0 │ z: 0 1 0 1 0 1 0 1 меняется каждую строку 1 │ 0 │ 0 │ 1 │ y: 0 0 1 1 0 0 1 1 через одну 2 │ 0 │ 1 │ 0 │ x: 0 0 0 0 1 1 1 1 через две 3 │ 0 │ 1 │ 1 │ 4 │ 1 │ 0 │ 0 │ 5 │ 1 │ 0 │ 1 │ 6 │ 1 │ 1 │ 0 │ 7 │ 1 │ 1 │ 1 │ Для четырёх переменных — 16 строк, левая меняется через четыре.
Если переменных пять–семь (в тетради есть таблица на x1…x7), полную таблицу не строят: 128 строк никто не пишет. Преподаватель даёт несколько готовых строк, и F считают только для них тем же конвейером, шаг 2 пропускается.
Разбор: выражение из тетради
Возьмём (¬x ∧ z) ∨ (¬x ∧ ¬y ∧ ¬z). Три переменные, значит восемь строк. Шаг 3: отрицания ¬x, ¬y, ¬z дают три вспомогательных столбца. Первая скобка ¬x ∧ z идёт в столбец Ш1. Вторая скобка ¬x ∧ ¬y ∧ ¬z в столбец Ш2. Последняя операция, дизъюнкция Ш1 ∨ Ш2, это и есть F.
F = (¬x ∧ z) ∨ (¬x ∧ ¬y ∧ ¬z) x y z │ ¬x ¬y ¬z │ Ш1=¬x∧z │ Ш2=¬x∧¬y∧¬z │ F=Ш1∨Ш2 ───────┼──────────┼─────────┼─────────────┼──────── 0 0 0 │ 1 1 1 │ 0 │ 1 │ 1 0 0 1 │ 1 1 0 │ 1 │ 0 │ 1 0 1 0 │ 1 0 1 │ 0 │ 0 │ 0 0 1 1 │ 1 0 0 │ 1 │ 0 │ 1 1 0 0 │ 0 1 1 │ 0 │ 0 │ 0 1 0 1 │ 0 1 0 │ 0 │ 0 │ 0 1 1 0 │ 0 0 1 │ 0 │ 0 │ 0 1 1 1 │ 0 0 0 │ 0 │ 0 │ 0 Читаем строку 0 1 1: ¬x=1, z=1 → Ш1 = 1∧1 = 1; ¬y=0 → Ш2 = 1∧0∧0 = 0; F = 1∨0 = 1.
Обрати внимание на четыре нижние строки: там x = 1, значит ¬x = 0, и обе скобки гаснут сразу, считать дальше не нужно. Такие «выключатели» экономят половину работы: если в конъюнкции хоть один ноль, вся конъюнкция ноль; если в дизъюнкции хоть одна единица, вся дизъюнкция единица.
Проверка равенства двух выражений
В первой странице конспекта записано: ¬A ∧ ¬B = ¬(A ∨ B), и рядом «значения в последних столбцах совпадают». Это способ доказать, что два выражения равны: построить обе таблицы и сравнить столбцы F. Совпали во всех строках: выражения равны, одно можно заменять другим. Разошлись хоть в одной: не равны.
ЗАКОН ДЕ МОРГАНА ТАБЛИЦЕЙ: ¬A ∧ ¬B против ¬(A ∨ B)
A B │ ¬A ¬B │ ¬A∧¬B │ A∨B │ ¬(A∨B)
─────┼───────┼───────┼─────┼───────
0 0 │ 1 1 │ 1 │ 0 │ 1
0 1 │ 1 0 │ 0 │ 1 │ 0
1 0 │ 0 1 │ 0 │ 1 │ 0
1 1 │ 0 0 │ 0 │ 1 │ 0
^ совпадают ^
Столбцы ¬A∧¬B и ¬(A∨B) одинаковы во всех 4 строках → выражения равны.
Так же проверяют второй закон де Моргана ¬(A ∧ B) = ¬A ∨ ¬B и любую формулу, в которой сомневаешься. На экзамене это законный способ: не помнишь закон, построй таблицу.
Контрольный вопрос. Сколько строк в таблице истинности выражения с тремя переменными? Впиши число.
Подсказка: Два в степени числа переменных.
Онлайн-проверка ответа появится позже
Контрольный вопрос. В конспекте есть выражение (x ∧ y) ∨ (y ≡ z) ∨ w. Сколько строк будет в его таблице истинности? Впиши число.
Подсказка: Сначала пересчитай разные переменные в выражении, потом возведи двойку в эту степень.
Онлайн-проверка ответа появится позже
Контрольный вопрос. Наборы для двух переменных A B выписаны в порядке двоичного счёта. Какой набор стоит третьим?
Подсказка: Считай в двоичной системе от нуля: 00, 01, … Какое число третье по счёту?
Онлайн-проверка ответа появится позже
Контрольный вопрос. Чему равен столбец-шаг Ш1 = ¬x ∧ z в строке, где x = 0, z = 1? Впиши 1 или 0.
Подсказка: Сначала найди ¬x, потом посмотри, оба ли множителя конъюнкции равны единице.
Онлайн-проверка ответа появится позже
Контрольный вопрос. В выражении (¬x ∧ z) ∨ (¬x ∧ ¬y ∧ ¬z) какая операция выполняется последней и даёт столбец F? Впиши её название одним словом.
Подсказка: Обе скобки уже посчитаны в Ш1 и Ш2. Какой значок стоит между скобками?
Онлайн-проверка ответа появится позже
Контрольный вопрос. Два логических выражения считаются равными, если…
Подсказка: Вспомни запись в тетради про де Моргана: что именно там сравнивали?
Онлайн-проверка ответа появится позже
Контрольный вопрос. Построй таблицу для выражения из конспекта F = (¬x ∧ y ∧ z) ∨ (¬x ∧ ¬y ∧ z) ∨ (¬x ∧ ¬y ∧ ¬z). В скольких строках из восьми F = 1? Впиши число.
Подсказка: Во всех трёх скобках есть ¬x: при x = 1 выражение сразу 0. Остаются четыре строки с x = 0 — заполни их по конвейеру.
Онлайн-проверка ответа появится позже
Контрольный вопрос. Выражение из конспекта на четыре переменные: F = (x ∧ y) ∨ (y ≡ z) ∨ w. Построй его таблицу (16 строк) и впиши, в скольких строках F = 0.
Подсказка: Дизъюнкция равна 0, только когда все три слагаемых равны 0 одновременно. Выпиши, при каких наборах гаснет каждое, и найди общие строки.
Онлайн-проверка ответа появится позже
Задание. Одногруппник заполнил таблицу импликации A → B, но в одной строке ошибся. Найди её и впиши набор значений A и B этой строки двумя цифрами подряд без пробела, например 01.
A B │ A → B ─────┼─────── 0 0 │ 1 0 1 │ 1 1 0 │ 1 1 1 │ 1Подсказка: Импликация ложна ровно в одной строке. Проверь каждую строку по правилу «обещание нарушено».
✅ Готово, если: ты ввёл(а) верный ответ, и онлайн-проверка его приняла.
Онлайн-проверка ответа появится позже
Задание. Построй на бумаге полную таблицу истинности выражения из конспекта: 8 строк в порядке двоичного счёта, столбцы Ш1, Ш2, Ш3 и F. Впиши, сколько нулей получилось в столбце F (число).
Принято, если: (1) число нулей совпало; (2) наборы выписаны в порядке 000…111 без пропусков; (3) в таблице есть все три столбца-шага Ш1, Ш2, Ш3 и итоговый F.F = (x ≡ y) ∨ ((y ∨ z) → x) Столбцы: x y z │ Ш1 = x≡y │ Ш2 = y∨z │ Ш3 = Ш2→x │ F = Ш1∨Ш3Подсказка: Эквиваленция даёт 1 при одинаковых x и y. Импликация Ш2 → x даёт 0 только когда Ш2 = 1, а x = 0. F = 0 лишь там, где и Ш1 = 0, и Ш3 = 0.
✅ Готово, если: ответ раскрывает то, что просит критерий приёмки в задании выше.
Онлайн-проверка ответа появится позже
Итог. Таблица строится конвейером: сосчитать переменные (строк 2ⁿ) → выписать наборы двоичным счётом → разбить выражение на столбцы-шаги Ш1, Ш2… по приоритету (в тетради П1, П2, П3 — переменные, не путай) → заполнить слева направо → последний столбец F. Два выражения равны, если их столбцы F совпадают во всех строках; так проверяют законы де Моргана.
Что дальше
Законы алгебры логики, включая оба закона де Моргана, собраны в уроке «Преобразование логических выражений»: пройди его дома. Это урок 10 класса, для тебя он новый: там законы записаны словами (НЕ = ¬, И = ∧, ИЛИ = ∨), а формулы в значках для остальных законов — ниже. Потом переходим ко второй главе: алгоритмы и блок-схемы.
ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ В ЗНАЧКАХ (для сверки с уроком) переместительный A ∧ B = B ∧ A A ∨ B = B ∨ A сочетательный (A ∧ B) ∧ C = A ∧ (B ∧ C) распределительный A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C) двойное отрицание ¬¬A = A идемпотентность A ∧ A = A A ∨ A = A поглощение A ∨ (A ∧ B) = A A ∧ (A ∨ B) = A де Морган ¬(A ∧ B) = ¬A ∨ ¬B ¬(A ∨ B) = ¬A ∧ ¬B Знак = между выражениями: столбцы F совпадают во всех строках.
