↔ Таблица истинности онлайн

СКНФ и СДНФ онлайн

Введите формулу — калькулятор построит таблицу истинности и сразу найдёт СДНФ (совершенную дизъюнктивную нормальную форму), СКНФ (совершенную конъюнктивную нормальную форму) и полином Жегалкина. Ниже показано, как свернуть совершенные формы до обычных ДНФ и КНФ, найти минимальную ДНФ (МДНФ) и как связаны СДНФ и СКНФ. Удобно для заданий по дискретной математике.

Введите формулу — таблица построится сразу.

Примеры: A ∧ B, A ∨ ¬B, (A → B) ∧ (B → C), закон де Моргана, A ⊕ B ⊕ C

Какие знаки можно вводить

ОперацияЗнаки вводаОписание
НЕ (отрицание)¬ ! ~ NOTменяет значение на противоположное
И (конъюнкция)∧ & * ANDистинно, когда истинны оба
ИЛИ (дизъюнкция)∨ | + ORложно, когда ложны оба
XOR (исключающее ИЛИ)⊕ ^ XORистинно, когда операнды различны
Штрих Шеффера (И-НЕ)↑ NANDложно только когда истинны оба
Стрелка Пирса (ИЛИ-НЕ)↓ NORистинно только когда ложны оба
Импликация→ ->ложно только при 1 → 0
Эквивалентность↔ ≡ <->истинно, когда операнды равны
Переменные / константыA B C D … 1 0буквы — переменные, 1 — истина, 0 — ложь

Приоритет: НЕ → И / И-НЕ → XOR → ИЛИ / ИЛИ-НЕ → импликация → эквивалентность. Меняйте порядок скобками. Регистр и пробелы не важны.

Таблица истинности логических операций

Базовая таблица истинности всех логических операций для двух переменных A и B — отрицание, конъюнкция, дизъюнкция, исключающее ИЛИ, импликация и эквивалентность. Это готовый справочник: по нему удобно проверять значения связок при разборе любой формулы.

AB ¬A A ∧ B A ∨ B A ⊕ B A → B A ↔ B
00100011
01101110
10001100
11011011

Как читать: И (∧) истинно только в последней строке, где истинны оба операнда; ИЛИ (∨) ложно только в первой строке; XOR (⊕) истинно, когда A и B различны; импликация (→) ложна единственный раз — при 1 → 0; эквивалентность (↔) истинна, когда значения совпадают.

Пример: построение СДНФ и СКНФ по таблице истинности

Разберём формулу F = (A ∧ B) ∨ ¬C из примера выше. Переменных три, поэтому в таблице 2³ = 8 наборов. Столбцами показаны подформулы A ∧ B и ¬C, а в последнем столбце — значение всей формулы.

№ABCA ∧ B¬CF
0000011
1001000
2010011
3011000
4100011
5101000
6110111
7111101

СДНФ — по единичным наборам

Функция равна 1 на наборах 0, 2, 4, 6, 7. Для каждого пишем конъюнкцию всех переменных: переменную берём без отрицания, если она равна 1, и с отрицанием, если 0 (минтерм). Минтермы соединяем знаком ИЛИ:

СДНФ = (¬A ∧ ¬B ∧ ¬C) ∨ (¬A ∧ B ∧ ¬C) ∨ (A ∧ ¬B ∧ ¬C) ∨ (A ∧ B ∧ ¬C) ∨ (A ∧ B ∧ C)

СКНФ — по нулевым наборам

Функция равна 0 на наборах 1, 3, 5. Для каждого пишем дизъюнкцию всех переменных: переменную берём с отрицанием, если она равна 1, и без отрицания, если 0 (макстерм). Макстермы соединяем знаком И:

СКНФ = (A ∨ B ∨ ¬C) ∧ (A ∨ ¬B ∨ ¬C) ∧ (¬A ∨ B ∨ ¬C)

Проверка: всего наборов 8, из них 5 единичных (столько минтермов в СДНФ) и 3 нулевых (столько макстермов в СКНФ) — 5 + 3 = 8. Знаки переменных в СДНФ и СКНФ берутся по противоположным правилам. Введите свою формулу в поле выше — обе формы построятся автоматически.

ДНФ и КНФ: чем отличаются от совершенных форм

ДНФ (дизъюнктивная нормальная форма) — это любая дизъюнкция конъюнкций переменных и их отрицаний, например (A ∧ B) ∨ ¬C. КНФ (конъюнктивная нормальная форма) — наоборот, конъюнкция дизъюнкций, например (A ∨ ¬C) ∧ (B ∨ ¬C). В отличие от совершенных форм, в обычные ДНФ и КНФ не обязаны входить все переменные в каждом терме, поэтому они короче. Совершенная форма — это частный случай: СДНФ всегда является ДНФ, а СКНФ — КНФ.

Чтобы получить ДНФ, совершенную дизъюнктивную форму упрощают, склеивая соседние минтермы (по правилу X ∧ Y ∨ X ∧ ¬Y = X). Для нашей функции F = (A ∧ B) ∨ ¬C пять минтермов СДНФ сворачиваются до короткой ДНФ:

ДНФ = ¬C ∨ (A ∧ B)

Проверка по таблице: ¬C = 1 на всех наборах, где C = 0 (это 000, 010, 100, 110), а оставшийся единичный набор 111 покрывает конъюнкция A ∧ B. Вместе они дают ровно те пять строк, где F = 1.

Аналогично из СКНФ получают КНФ. По дистрибутивному закону ¬C ∨ (A ∧ B) = (¬C ∨ A) ∧ (¬C ∨ B), то есть три макстерма нашей функции сворачиваются в две скобки:

КНФ = (A ∨ ¬C) ∧ (B ∨ ¬C)

Обе короткие формы равносильны исходной F — их таблицы истинности совпадают строка в строку. Проверить это можно на странице проверки равносильности формул. Введите свою формулу выше, чтобы получить совершенные СДНФ и СКНФ, а затем сверните их по законам логики.

Как преобразовать СДНФ в СКНФ и обратно

СДНФ и СКНФ одной функции строятся по одной и той же таблице, но по дополняющим друг друга строкам: СДНФ — по наборам, где F = 1, а СКНФ — по наборам, где F = 0. Поэтому переходить от одной формы к другой проще всего через таблицу, а не преобразованием отдельных термов.

Практическое правило на нашем примере: в СДНФ вошли минтермы наборов 0, 2, 4, 6, 7 — значит «пропущенные» наборы 1, 3, 5 как раз дают макстермы СКНФ. Достаточно выписать номера строк, которых нет в СДНФ, и по каждому построить макстерм (переменную берут с отрицанием, если в наборе она равна 1, и без отрицания, если 0). Обратный переход из СКНФ в СДНФ — тот же приём: берут наборы, не вошедшие в СКНФ, и строят по ним минтермы. Инструмент выводит номера наборов рядом с обеими формами, так что перевод сводится к выбору дополнительных строк.

МДНФ — минимальная дизъюнктивная нормальная форма

Минимальная ДНФ (МДНФ) — это ДНФ с наименьшим числом букв (вхождений переменных) среди всех равносильных ДНФ. Её получают из СДНФ минимизацией: сначала склеивают соседние минтермы по правилу X ∧ Y ∨ X ∧ ¬Y = X (два набора, различающиеся ровно в одной переменной, объединяются, а эта переменная исчезает), находят все простые (первичные) импликанты, а затем выбирают из них минимальное покрытие всех единичных наборов. Наглядно это делает карта Карно: единицы, стоящие рядом, объединяют в прямоугольники-двойки, четвёрки, восьмёрки, и каждый прямоугольник даёт один короткий терм.

Для нашей функции F = (A ∧ B) ∨ ¬C единицы стоят на наборах 0, 2, 4, 6, 7. Четыре набора с C = 0 (это 000, 010, 100, 110) объединяются в один прямоугольник — остаётся терм ¬C; оставшийся набор 111 склеивается с 110 по переменной C, давая терм A ∧ B. Больше склеек нет, оба импликанта необходимы, поэтому минимальная ДНФ:

МДНФ = ¬C ∨ (A ∧ B)

В ней всего 3 буквы против 13 в СДНФ из пяти полных минтермов — это и есть выигрыш минимизации. Здесь МДНФ совпала с найденной выше короткой ДНФ, но в общем случае у функции может быть несколько тупиковых ДНФ, и минимальной считается самая короткая из них. Ту же идею применяют к СКНФ, получая минимальную КНФ (МКНФ).

Полином Жегалкина

Полином Жегалкина (алгебраическая нормальная форма, АНФ) — ещё одна каноническая запись логической функции, но уже через операции исключающего ИЛИ ⊕ (сложение по модулю 2) и конъюнкции ∧, плюс константа 1. Любая функция представима единственным таким полиномом: f = c₀ ⊕ c₁A ⊕ c₂B ⊕ c₃(A ∧ B) ⊕ …, где каждый коэффициент c равен 0 или 1. В отличие от СДНФ, здесь нет отрицаний — вместо ¬A подставляют 1 ⊕ A.

Коэффициенты удобно находить методом треугольника (преобразованием Мёбиуса): берут столбец значений функции по всем наборам и последовательно заменяют соседние пары их суммой по модулю 2. Для F = (A ∧ B) ∨ ¬C столбец значений (по наборам 0…7) равен 1, 0, 1, 0, 1, 0, 1, 1, и после свёртки остаются единичные коэффициенты при константе, при C и при A ∧ B ∧ C:

Полином Жегалкина: F = 1 ⊕ C ⊕ (A ∧ B ∧ C)

Проверка: на наборах с C = 0 полином равен 1 ⊕ 0 ⊕ 0 = 1 (совпадает с F на 000, 010, 100, 110); на 111 получаем 1 ⊕ 1 ⊕ 1 = 1, а на 001, 011, 101 — 1 ⊕ 1 = 0. Все восемь значений сходятся с таблицей. Инструмент выше строит полином Жегалкина автоматически для любой введённой формулы — рядом со СДНФ и СКНФ.

Теория и пояснения

СДНФ и СКНФ — это канонические записи логической функции, восстановленные прямо из таблицы истинности. Совершенная дизъюнктивная нормальная форма (СДНФ) собирается по строкам, где функция равна единице: для каждой такой строки записывают конъюнкцию всех переменных, причём переменную берут «как есть», если в строке она равна 1, и с отрицанием, если равна 0; полученные конъюнкции (минтермы) соединяют знаком ИЛИ. Совершенная конъюнктивная нормальная форма (СКНФ) собирается по строкам, где функция равна нулю: для каждой такой строки записывают дизъюнкцию всех переменных, причём переменную берут с отрицанием, если в строке она равна 1, и без отрицания, если равна 0; полученные дизъюнкции (макстермы) соединяют знаком И. Правило знаков в СДНФ и СКНФ противоположно — это удобно запомнить. Если формула тождественно истинна, у неё нет нулевых строк, поэтому СКНФ не существует (её заменяет константа 1), а если формула тождественно ложна, у неё нет единичных строк, и тогда не существует СДНФ (её заменяет константа 0). Инструмент показывает обе формы под таблицей и подписывает номера наборов, по которым они построены.

Частые вопросы

Как найти СКНФ онлайн?

Введите формулу в поле выше — калькулятор построит таблицу истинности и по всем нулевым наборам сразу составит СКНФ (совершенную конъюнктивную нормальную форму). Рядом выводятся СДНФ, ДНФ, КНФ, МДНФ и полином Жегалкина, а ниже разобран пример нахождения СКНФ по таблице вручную.

Есть ли калькулятор ДНФ, КНФ, СДНФ и СКНФ?

Да, этот инструмент работает как калькулятор всех нормальных форм: по введённой формуле он находит совершенные СДНФ и СКНФ, сворачивает их до обычных ДНФ и КНФ, выводит минимальную ДНФ (МДНФ) и полином Жегалкина — всё считается в браузере, бесплатно и без регистрации.

Чем СДНФ отличается от СКНФ?

СДНФ строится по строкам, где функция равна 1 (дизъюнкция конъюнкций — минтермов), а СКНФ — по строкам, где функция равна 0 (конъюнкция дизъюнкций — макстермов). В СДНФ и СКНФ знаки переменных берутся по противоположным правилам.

Как составить СДНФ по таблице истинности?

Возьмите все строки с результатом 1. В каждой запишите конъюнкцию переменных: переменную без отрицания, если она равна 1, и с отрицанием, если 0. Соедините конъюнкции знаком ИЛИ.

Как составить СКНФ по таблице истинности?

Возьмите все строки с результатом 0. В каждой запишите дизъюнкцию переменных: переменную с отрицанием, если она равна 1, и без отрицания, если 0. Соедините дизъюнкции знаком И.

Что если СДНФ или СКНФ не существует?

У тождественно ложной формулы нет единичных строк, поэтому нет СДНФ (формула равна 0). У тождественно истинной формулы нет нулевых строк, поэтому нет СКНФ (формула равна 1).

Чем ДНФ отличается от СДНФ (и КНФ от СКНФ)?

СДНФ и СКНФ — совершенные формы: в каждый терм входят все переменные. Обычная ДНФ (дизъюнкция конъюнкций) и КНФ (конъюнкция дизъюнкций) могут быть короче — их получают из совершенных форм, склеивая соседние термы по законам логики. Например, СДНФ из пяти минтермов может свернуться до ДНФ ¬C ∨ (A ∧ B).

Как преобразовать СДНФ в СКНФ?

Проще всего через таблицу: СДНФ строится по строкам, где функция равна 1, а СКНФ — по строкам, где она равна 0. Выпишите наборы, которых нет среди минтермов СДНФ, — это и есть нулевые наборы, по каждому постройте макстерм (переменная с отрицанием, если в наборе она равна 1). Обратный переход из СКНФ в СДНФ выполняется так же по дополнительным строкам.

Что такое МДНФ и как её найти?

МДНФ — минимальная дизъюнктивная нормальная форма, то есть ДНФ с наименьшим числом букв. Её получают из СДНФ: склеивают соседние минтермы (X ∧ Y ∨ X ∧ ¬Y = X), находят простые импликанты и выбирают минимальное покрытие всех единичных наборов. Удобно пользоваться картой Карно. Например, СДНФ функции (A ∧ B) ∨ ¬C из пяти минтермов сворачивается в МДНФ ¬C ∨ (A ∧ B).

Что такое полином Жегалкина?

Это запись логической функции через сложение по модулю 2 (⊕) и конъюнкцию (∧) с константой 1, без отрицаний: f = c₀ ⊕ c₁A ⊕ … ⊕ (A ∧ B). Полином единственный для каждой функции; коэффициенты находят методом треугольника (преобразованием Мёбиуса) по столбцу значений. Инструмент строит полином Жегалкина автоматически рядом со СДНФ и СКНФ.