Совершенная конъюнктивная нормальная форма
Совершенная конъюнктивная нормальная форма (СКНФ) — это представление булевой функции как нормальной формы, то есть конъюнкции элементарных дизъюнкций, в каждую из которых входят все переменные ровно по одному разу.
Формула
Если функция \(F(x_1, x_2, \ldots, x_n)\) равна нулю в строках с номерами \(i_1, i_2, \ldots, i_k\), то её СКНФ записывают как конъюнкцию соответствующих макстермов:
Правило записи макстерма: переменная берётся без отрицания, если в выбранной строке она равна 0, и с отрицанием, если она равна 1. Тогда весь макстерм становится равным 0 именно в этой строке.
Пусть функция \(F(A,B)\) равна 0 при наборах \((0,1)\) и \((1,1)\). Для набора \((0,1)\) получаем макстерм \(A \lor \neg B\): он равен 0 при \(A=0\), \(B=1\). Для набора \((1,1)\) получаем \(\neg A \lor \neg B\). Поэтому СКНФ имеет вид \(F=(A \lor \neg B) \cdot (\neg A \lor \neg B)\). Алгоритм построения СКНФ сводится к выбору нулевых строк и жазбалар таких макстермов.
В СКНФ выбирают строки, где функция равна 0, и соединяют макстермы конъюнкцией. В СДНФ, наоборот, выбирают единичные строки и соединяют минтермы дизъюнкцией. Внутри макстерма правило знаков также противоположно правилу для минтерма.
Какой макстерм соответствует набору \((A,B,C)=(1,0,1)\)?
Главное
- СКНФ — конъюнкция элементарных дизъюнкций, содержащих все переменные.
- Для построения СКНФ берут нулевые строки таблицы истинности.
- В макстерме переменная без отрицания соответствует нулю, а с отрицанием — единице.