СКНФ — это совершенная конъюнктивная нормальная форма представления функции.
Введение
Любая логическая формула должна определять некую булеву функцию. Однако, с другой стороны, для любой булевой функции может быть записано бесконечное множество формул, которые её представляют. Одной из главных задач булевой алгебры, то есть, алгебры логики, является нахождение канонических форматов (то есть формул, которые построены по определенному правилу, канону), а также самых простых формул, которые представляют булевы функции.
Когда логические функции выражаются через дизъюнкцию, конъюнкцию и отрицание переменных, то такой формат представления называется нормальным. Среди нормальных форматов следует выделить такие, в которых функции могут быть записаны только единственным образом. Они называются совершенными.
Особая роль в алгебре логики отведена классам дизъюнктивной и конъюнктивной совершенным нормальным формам. В их базе заложены понятия элементарных дизъюнкций и элементарных конъюнкций.
Формула может называться элементарной конъюнкцией, в случае, если она выступает как конъюнкция одной или нескольких переменных, которые взяты с наличием отрицания или без него. Одна переменная или её отрицание может считаться одночленной элементарной конъюнкцией.
Формула носит название элементарной дизъюнкции в случае, когда она выступает как дизъюнкция (возможно даже одночленная) переменных, а также отрицаний переменных.
Нормальная форма логической формулы может характеризоваться тем, что для нее не свойственны эквивалентность, отрицание формул неэлементарного типа и знаки импликации. Известны следующие формы нормального типа:
- Тип конъюнктивной нормальной формы (КНФ).
- Тип дизъюнктивной нормальной формы (ДНФ).
СДНФ, то есть, совершенная дизъюнктивная нормальная форма формулы, является способом написания функции алгебры логики в качестве логического выражения. СДНФ формулой является равнозначная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций, при которых функция достигает показателя единица. У СДНФ могут быть выделены следующие основные свойства:
- Она имеет в своём составе разные элементарные конъюнкции
- Весь набор логических слагаемых формулы содержит все переменные, входящие в функцию F.
К СДНФ может быть приведена любая формула алгебры логики. Исключением является только тождественно ложная формула. СДНФ может быть получена при помощи таблицы истинности или через равносильные преобразования.
Простой дизъюнкцией (от английского inclusive disjunction) или дизъюнктом (от английского disjunct) именуется дизъюнкция одной или нескольких переменных, или их отрицаний, причём каждая переменная должна встречаться не более одного раза. Простая дизъюнкция делится на следующие типы:
- Тип полной дизъюнкции, если в неё каждая переменная или её отрицание входит ровно один раз.
- Тип монотонной дизъюнкции, если она не содержит отрицаний переменных.
Представление таблично заданных функций в форме СКНФ
Конъюнктивной нормальной формой (КНФ) является нормальная форма, в которой булева функция имеет вид конъюнкции нескольких простых дизъюнктов.
В качестве примера КНФ можно привести следующую функцию:
f(x,y)=(x∨y)∧(y∨¬z)f(x,y)=(x∨y)∧(y∨¬z)
Совершенной конъюнктивной нормальной формой (СКНФ от английского perfect conjunctive normal form) является такая КНФ, которая удовлетворяет следующим условиям:
- В ней отсутствуют одинаковые простые дизъюнкции.
- Каждая простая дизъюнкция является полной.
- Все дизъюнкции должны содержать каждую переменную из входящих в конъюнктивную нормальную функцию такого типа.
В качестве примера СКНФ можно привести следующую функцию:
f(x,y,z)=(x∨¬y∨z)∧(x∨y∨¬z)f(x,y,z)=(x∨¬y∨z)∧(x∨y∨¬z)
Для любой булевой функции f(x⃗ )f(x→), которая не равна тождественно единице, существует СКНФ, ее задающая.
Поскольку инверсия функции ¬f(x⃗ )¬f(x→) равняется единице на тех наборах, на которых f(x⃗ )f(x→) равняется нулю, то СДНФ для ¬f(x⃗ )¬f(x→) может быть записана следующим образом:
¬f(x⃗ )=⋁f(xσ1,xσ2,...,xσn)=0(xσ11∧xσ22∧...∧xσnn)¬f(x→)=⋁f(xσ1,xσ2,...,xσn)=0(x1σ1∧x2σ2∧...∧xnσn),
где σi σi обозначает наличие или отсутствие отрицание при xi xi.
Определим инверсию левой и правой части выражения:
f(x⃗ )=¬(⋁f(xσ1,xσ2,...,xσn)=0(xσ11∧xσ22∧...∧xσnn))f(x→)=¬(⋁f(xσ1,xσ2,...,xσn)=0(x1σ1∧x2σ2∧...∧xnσn))
Используя дважды к сформированному в правой части выражению правило де Моргана, можно получить:
f(x⃗ )=⋀f(xσ1,xσ2,…,xσn)=0f(x→)=⋀f(xσ1,xσ2,…,xσn)=0 (¬xσ11∨¬xσ22∨⋯∨¬xσnn)(¬x1σ1∨¬x2σ2∨⋯∨¬xnσn)
Последнее выражение представляет собой именно СКНФ.
Алгоритм формирования СКНФ по таблице истинности состоит из следующих действий:
- В таблице истинности следует отметить те наборы переменных, на которых значение функции равняется нулю.
- Для всех отмеченных наборов необходимо записать дизъюнкцию всех переменных по определённому правилу, а именно, если значение какой-либо переменной равняется нулю, то в дизъюнкцию следует включить саму переменную, в противном случае следует включить в дизъюнкцию её отрицание.
- Все сформированные дизъюнкции следует связать операциями конъюнкции.
Рассмотрим конкретный пример построения СКНФ для медианы:
Первое. В таблице истинности необходимо отметить те наборы переменных, на которых значение функции равняется нулю.
Рисунок 1. Таблица. Автор24 — интернет-биржа студенческих работ
Второе. Для всех отмеченных наборов следует записать конъюнкцию всех переменных по определённому правилу, а именно, если значение некоторой переменной равняется нулю, то в дизъюнкцию следует включить саму переменную, в противном случае в дизъюнкцию следует включить её отрицание.
Рисунок 2. Таблица. Автор24 — интернет-биржа студенческих работ
Третье. Все сформированные дизъюнкции следует связать операциями конъюнкции, чтобы получить итоговую формулу.
