Упрощение логических выражений
Введите логическое выражение в привычной записи, например AB + A'C + BC, и получите его простейшую дизъюнктивную (ДНФ) и конъюнктивную (КНФ) нормальную форму. Для двух–четырёх переменных строится и карта Карно.
Работает в браузере: всё, что вы вводите, никуда не отправляется.
Как пользоваться
- Введите выражение. Если переменные — одиночные буквы, пишите как в учебнике:
A'B + AB', (A + B)(A + C). Имена переменных — латиницей.
- При необходимости перечислите безразличные наборы (номера минтермов).
- Посмотрите минимальную ДНФ и КНФ и сверьтесь с картой Карно.
Как это работает
Программа строит таблицу истинности, расставив переменные по алфавиту (первая — старший разряд номера минтерма). Метод Куайна — Мак-Класки склеивает минтермы, отличающиеся одной переменной, пока склеивать больше нечего; оставшиеся термы — простые импликанты. Затем перебор с отсечениями выбирает самый дешёвый набор импликант, покрывающий все минтермы: сначала по числу термов, затем по числу литералов. Для КНФ то же делается с нулями функции, и каждый терм инвертируется.
Разобранный пример
AB + A’C + BC равно 1 на минтермах 1, 3, 6 и 7. Простые импликанты: A’C (1, 3), BC (3, 7) и AB (6, 7). Минтерм 1 покрывает только A’C, минтерм 6 — только AB; вместе они покрывают и 3 с 7, поэтому BC лишний: минимальная форма — AB + A’C (теорема о консенсусе). Нули 0, 2, 4, 5 дают КНФ (A + C)(A’ + B).
Советы
- Ставьте скобки, когда смешиваете И и ИЛИ: сильнее всего связывает НЕ, затем И, затем XOR, затем ИЛИ.
- Выражение, которое упрощается до 1, — тавтология; упрощающееся до 0 никогда не бывает истинным.
- Чтобы увидеть все строки, вставьте выражение в генератор таблиц истинности.
Частые вопросы
Как программа находит минимальную форму?
Она вычисляет выражение на всех наборах входов, затем методом Куайна — Мак-Класки находит все простые импликанты и выбирает наименьший набор, покрывающий все единицы: сначала по числу термов, затем по числу литералов. КНФ находится так же по нулям функции и переворачивается по закону де Моргана.
Что означают A' и AB?
A' — это НЕ A (отрицание), а буквы, записанные подряд, соединены через И: AB'C — это A И НЕ B И C. A + B — это ИЛИ. Если имена переменных длиннее одной буквы, выберите «Слова» и пишите И явно, например speed and not brake. Имена переменных и слова and, or, not пишутся латиницей.
Что такое безразличные наборы?
Комбинации входов, которые никогда не встречаются или значение на которых не важно, например коды 10–15 в двоично-десятичной цифре. Если их указать, программа сама решит, считать каждый набор нулём или единицей, — как выйдет короче.
Минимальная форма единственна?
Не всегда. У некоторых функций несколько покрытий с одинаковым числом термов и литералов; программа показывает одно из них. Они одинаково просты и дают одну и ту же таблицу истинности.
Сколько переменных можно использовать?
До 8. Карта Карно строится для 2, 3 или 4 переменных; при большем числе смотрите список минтермов или генератор таблиц истинности.