Построение СДНФ
Совершенная дизъюнктивная нормальная форма, или СДНФ, позволяет записать логическую функцию непосредственно по её таблице истинности. Для этого выбирают строки, в которых функция равна 1, составляют для них минтермы и соединяют полученные конъюнкции дизъюнкцией.
Что такое СДНФ
Перед построением СДНФ полезно повторить, как устроена таблица истинности. В ней перечислены все наборы значений входных переменных и значение логической функции на каждом наборе. Если переменных \(n\), таблица содержит \(2^n\) строк с наборами.
Совершенная дизъюнктивная нормальная форма — это дизъюнкция элементарных конъюнкций, каждая из которых содержит все переменные функции ровно по одному разу: либо саму переменную, либо её отрицание. Такая элементарная конъюнкция называется минтермом.
Дизъюнкция обозначается знаком \(\lor\), конъюнкция — знаком \(\land\), отрицание переменной \(A\) — выражением \(\neg A\). Поэтому общий вид СДНФ функции от переменных \(A\), \(B\), \(C\) выглядит так:
Внутри каждой скобки находятся все переменные, соединённые конъюнкцией. Скобки соединяются дизъюнкцией. В СДНФ включаются только те минтермы, которые соответствуют строкам таблицы со значением функции 1.
В строке таблицы истинности переменной со значением 1 в минтерм записывают без отрицания, а переменную со значением 0 — с отрицанием. Например, набор \(A=1\), \(B=0\), \(C=1\) соответствует минтерму \(A\land\neg B\land C\).
Алгоритм построения по таблице истинности
Алгоритм состоит из нескольких последовательных действий. Важно не смешивать правила для СДНФ и построения СКНФ: в СДНФ рассматривают строки с единицами, а в СКНФ — строки с нулями.
- Определите переменные функции и убедитесь, что в таблице есть все \(2^n\) наборов.
- Найдите все строки, в которых результат функции равен 1.
- Для каждой выбранной строки составьте минтерм: значение 1 оставьте без отрицания, значение 0 замените отрицанием.
- Проверьте, что в каждом минтерме присутствуют все переменные ровно по одному разу.
- Соедините все минтермы знаком дизъюнкции \(\lor\).
- При необходимости уберите внешние скобки, если это не ухудшает читаемость.
Формула (2) означает: СДНФ функции \(F\) — дизъюнкция всех минтермов \(m_i\), соответствующих строкам, где \(F=1\). Порядок слагаемых обычно не важен: перестановка минтермов не меняет значение функции.
Сначала выписывайте выбранную строку в отдельной черновой записи, например \(1\ 0\ 1\ 1\). Только затем переводите её в минтерм \(A\land\neg B\land C\land D\). Это снижает риск перепутать отрицания.
Почему алгоритм работает
Каждый минтерм равен 1 только на одном наборе значений переменных. Например, \(A\land\neg B\land C\) истинно только при \(A=1\), \(B=0\), \(C=1\). На любом другом наборе хотя бы один множитель равен 0, поэтому весь минтерм равен 0.
Дизъюнкция минтермов, соответствующих всем строкам таблицы, где функция равна 1, задаёт ту же логическую функцию. Каждый выбранный минтерм даёт единицу на своей строке, а дизъюнкция делает результат равным 1 ровно на объединении этих строк.
Иначе говоря, минтермы работают как точные «метки» строк. Они не пересекаются: один набор входов не может одновременно соответствовать двум различным минтермам. Поэтому при объединении всех нужных минтермов получается исходная функция.
Какой минтерм соответствует набору \(A=0\), \(B=1\), \(C=0\)?
Разобранный пример
Построим СДНФ функции \(F(A,B,C)\) по таблице истинности. Для наглядности добавим столбец результата.
| \(A\) | \(B\) | \(C\) | \(F\) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
Единицы в последнем столбце стоят в строках \(001\), \(011\), \(100\) и \(111\). Для каждой такой строки составим отдельный минтерм.
Полученная запись и есть СДНФ функции. Каждый минтерм содержит \(A\), \(B\) и \(C\), а число минтермов равно числу единиц в столбце результата: четырём.
Проверка выполняется по выбранным строкам. Например, при \(A=1\), \(B=0\), \(C=0\) третий минтерм равен 1, поэтому вся дизъюнкция равна 1. На строке \(A=1\), \(B=0\), \(C=1\) ни один из записанных минтермов не равен 1, поэтому значение функции равно 0.
Связь с минтермами и нормальными формами
СДНФ является частным случаем нормальной формы. Её особенность — в полноте каждого минтерма: нельзя пропустить переменную или записать её и без отрицания, и с отрицанием. Подробное понятие минтерма удобно повторить на странице «Минтерм».
Если функция тождественно равна 1, её СДНФ содержит все \(2^n\) минтермов. Если функция тождественно равна 0, строк с единицей нет, поэтому обычная СДНФ не содержит ни одного минтерма; функцию записывают как константу лжи \(0\). Это связано со свойствами константы лжи и константы истины.
<ul><li>Выбирать строки с результатом 0 вместо строк с результатом 1. Это правило относится к СКНФ, а не к СДНФ.</li><li>Записывать отрицание не для нулевой, а для единичной переменной.</li><li>Пропускать переменную в минтерме. В СДНФ каждая переменная должна встретиться ровно один раз.</li><li>Соединять минтермы знаком \(\land\) вместо \(\lor\).</li><li>Путать порядок столбцов. Перед составлением минтермов проверьте, какая позиция относится к каждой переменной.</li><li>Считать количество строк с единицами неправильно: число минтермов должно совпадать с числом единиц в столбце функции.</li></ul>
Для СДНФ: берём строки с 1, внутри строки используем конъюнкцию, нулевые значения превращаем в отрицания, готовые минтермы соединяем дизъюнкцией.
Как быстро проверять ответ
Есть три быстрые проверки. Во-первых, в каждом слагаемом должно быть одинаковое число переменных — столько же, сколько входных переменных у функции. Во-вторых, число слагаемых должно совпадать с количеством единиц в столбце функции. В-третьих, можно проверить одну выбранную строку: соответствующий минтерм обязан стать 1, а на любой другой строке — 0.
Если в задании требуется только построить СДНФ, не нужно дополнительно упрощать выражение. После сокращения отдельных переменных или объединения слагаемых запись может перестать быть совершенной, хотя останется эквивалентной исходной функции. Поэтому сначала оформите полную СДНФ, а преобразования выполняйте только по условию.
Проверь себя
Главное
- СДНФ — дизъюнкция минтермов, каждый из которых содержит все переменные ровно по одному разу.
- Для построения выбирают строки таблицы, где результат функции равен 1.
- Значение 1 записывают без отрицания, значение 0 — с отрицанием.
- Внутри минтерма используется конъюнкция, между минтермами — дизъюнкция.
- Число минтермов равно числу единиц в столбце функции; после построения ответ полезно проверить по таблице.