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