Таблица истинности показывает значение логической функции на каждом наборе значений переменных. Калькулятор строит её по выражению — с промежуточным столбцом для каждой операции, как это делают вручную, — и по таблице находит нормальные формы: совершенные (СДНФ, СКНФ) и минимальные (ДНФ, КНФ). Функцию можно задать и вектором значений: строкой из 2ⁿ нулей и единиц в порядке наборов.
Как вводить выражение
Переменные — латинские буквы, можно с номером: a, B, x1. Буквы, написанные подряд, — это конъюнкция: AB + C означает A ∧ B ∨ C, а x1x2 — x1 ∧ x2. Операции можно писать по-разному:
| Операция | Знаки | Значения на наборах 00, 01, 10, 11 |
|---|---|---|
| Отрицание (НЕ) | ¬a, !a, ~a, a', not a, не a | — (¬0 = 1, ¬1 = 0) |
| Конъюнкция (И) | a ∧ b, a & b, a && b, a * b, a · b, ab, a and b, a и b | 0, 0, 0, 1 |
| Дизъюнкция (ИЛИ) | a ∨ b, a | b, a || b, a + b, a or b, a или b | 0, 1, 1, 1 |
| Исключающее ИЛИ | a ⊕ b, a ^ b, a xor b | 0, 1, 1, 0 |
| Импликация | a → b, a -> b, a => b | 1, 1, 0, 1 |
| Эквивалентность | a ≡ b, a == b, a <-> b, a ↔ b | 1, 0, 0, 1 |
Приоритеты — от высшего к низшему: отрицание, конъюнкция, исключающее ИЛИ, дизъюнкция, импликация, эквивалентность. Операции одного уровня выполняются слева направо, кроме импликации: a → b → c читается как a → (b → c). Если сомневаетесь в порядке — ставьте скобки, калькулятор покажет, как понял выражение, в заголовке последнего столбца.
Нормальные формы
- СДНФ — дизъюнкция полных конъюнкций (минтермов) по наборам, где функция равна 1. Для a ⊕ b это ¬a ∧ b ∨ a ∧ ¬b.
- СКНФ — конъюнкция полных дизъюнкций (макстермов) по наборам, где функция равна 0: для a ⊕ b — (a ∨ b) ∧ (¬a ∨ ¬b).
- Минимальная ДНФ и КНФ — формы с наименьшим числом слагаемых (сомножителей), а при равном числе — с наименьшим числом букв. Калькулятор находит их методом Куайна — Мак-Класки: склеивает наборы в простые импликанты, берёт обязательные и перебором подбирает наименьшее покрытие остальных. Если минимальных форм несколько, показывается одна из них.
Безразличные наборы (x в векторе значений) — те, где значение функции не задано: например, коды, которые никогда не поступают на вход схемы. Минимизация использует их, когда это сокращает форму. Нагляднее всего склеивание видно на карте Карно.
Пример
Для выражения (a ∨ b) ∧ ¬c калькулятор строит промежуточные столбцы a ∨ b и ¬c и итоговый; вектор значений — 00101010, СДНФ — ¬a ∧ b ∧ ¬c ∨ a ∧ ¬b ∧ ¬c ∨ a ∧ b ∧ ¬c, а минимальные формы — a ∧ ¬c ∨ b ∧ ¬c и (a ∨ b) ∧ ¬c.
Частые вопросы
Как построить таблицу истинности?
Выпишите все наборы значений переменных — для n переменных их 2ⁿ, по порядку двоичных чисел от 00…0 до 11…1. Затем по шагам вычислите каждую операцию выражения, начиная с самых приоритетных: отрицание, затем конъюнкция, дизъюнкция, импликация и эквивалентность, — каждому шагу отводится свой столбец. Последний столбец — значение всей функции. Калькулятор делает то же и показывает промежуточные столбцы.
Чем СДНФ отличается от минимальной ДНФ?
СДНФ — совершенная дизъюнктивная нормальная форма: дизъюнкция конъюнкций, в каждой из которых есть все переменные, по одной на каждый набор, где функция равна 1. Она единственна, но длинна. Минимальная ДНФ равна той же функции, но состоит из наименьшего числа конъюнкций с наименьшим числом букв — её получают склеиванием наборов, например методом Куайна — Мак-Класки или по карте Карно.
Как записывается импликация и какая у неё таблица?
Импликация a → b ложна только в одном случае: a = 1, b = 0; на наборах 00, 01, 10, 11 её значения — 1, 1, 0, 1. Она равна ¬a ∨ b. В калькуляторе её пишут знаком → или ->; в Python на значениях 0 и 1 её заменяет сравнение a <= b.
Можно ли проверить ответ задачи ЕГЭ по информатике?
Да: введите выражение из условия, и калькулятор покажет его таблицу. Для проверки в Python выберите запись «Python» — калькулятор запишет выражение с операциями not, and, or, а импликацию и эквивалентность — сравнениями <= и ==, которые на значениях 0 и 1 дают тот же результат.
Источники
- W. V. Quine. The problem of simplifying truth functions. The American Mathematical Monthly, 1952, vol. 59, no. 8 — простые импликанты и сокращение нормальных форм
- E. J. McCluskey. Minimization of Boolean functions. The Bell System Technical Journal, 1956, vol. 35, no. 6 — табличный метод поиска простых импликантов и покрытия — им считаются минимальные ДНФ и КНФ
- Википедия. Quine–McCluskey algorithm; Karnaugh map — разобранные примеры f = Σm(4, 8, 10, 11, 12, 15) + d(9, 14) и f = Σm(6, 8, 9, 10, 11, 12, 13, 14) — эталоны тестов калькулятора
Встроить калькулятор на свой сайт
Скопируйте код и вставьте его в HTML страницы, статьи или вики. Виджет бесплатный, без рекламы, счётчиков и cookie. Условие одно — ссылка на GAW под рамкой остаётся на месте. Подробнее о виджетах
<iframe src="https://gaw.ru/embed/truth-table/" title="Таблица истинности онлайн" width="100%" height="640" style="border:1px solid #e3e5e9;border-radius:8px" loading="lazy" allow="clipboard-write"></iframe>
<p style="margin:6px 0 0;font-size:14px">Калькулятор: <a href="https://gaw.ru/tools/truth-table/">Таблица истинности онлайн</a> — GAW.ru</p>Автоподстройка высоты рамки
Если сайт разрешает скрипты, добавьте этот код один раз в любом месте страницы: рамка будет менять высоту вместе с результатом расчёта.
<script>window.addEventListener("message",function(e){if(e.origin!=="https://gaw.ru"||!e.data||e.data.type!=="gaw:embed-height")return;var f=document.querySelectorAll('iframe[src^="https://gaw.ru/embed/"]');for(var i=0;i<f.length;i++)if(f[i].contentWindow===e.source)f[i].style.height=e.data.height+"px"})</script>Обновлено .
Нашли ошибку в расчёте?