СДНФ и СКНФ
19.07.2010 |Теорема (о СДНФ):
Всякая тождественно не равная 0 функция f(x1, x2,…,xn) допускает представление f(x1, x2,…,xn) = ∀f(C1,…,Cn)xC11…xCnn (1) , где дизъюнкция берется по всем наборам C=(C1,…,Cn) из 0 и 1, для которых f(c) = 1
Доказательство: Пусть функция f(x1, x2,…,xn)≠0. По лемме о разложении функции по компонентам при k=n получаем:
f(x1, x2,…,xn) = ∀f(C1,…,Cn)xC11…xCnn. Из правой части этого равенства выбросим все нулевые дизъюнктивные слагаемые, для которых f(C1,…,Cn)=0, останутся слагаемые, в которых f(C1,…,Cn)=1. Равенство принимает вид:
f(x1, x2,…,xn) = ∀f(C)=1 xC11…xCnn.
Определение: Правая часть представления (1) называется СДНФ функции f.
Замечание: Каждое слагаемое в СДНФ называется конституентой единицы. Конституента единицы xC11…xCnn =1 на единственном наборе x1=c1, x2=c2, xn=cn.
Замечание: Всякая ФАЛ допускает представление в виде СДНФ, которая построена из функций множества F={&, ∨, ¬} (2). Следовательно, множество F составляет полную систему. Система F3={x/y}, состоящая из единственной функции (штрих Шеффера), составляет полную систему
Замечание: Для всякой не равной тождественно нулю функции существует единственная СДНФ.
Теорема (о СКНФ): Всякая не равная тождественно 1 функция f(x1, x2,…,xn) допускает представление
f(x1, x2,…,xn) = &f(C1,…,Cn)(x¬C11∨…∨x¬Cnn) (3), где конъюнкция берется по всем наборам C = (C1, C1,…,Cn) из 0 и 1, для которых f(C) = 0.
Доказательство: заметим, что ¬(xc) = x¬c. Пусть функция f(x1, x2,…,xn)≠1. Тогда ¬f≠0 и потому функция ¬f допускает представление в виде СДНФ.
¬ f(x1, 2,…,xn) =∨¬f(C)=1(xC11…xCnn). Берем отрицание от обеих частей.
f(x1, x2,…,xn) = ¬∨f(C)=0(xC11…xCnn) = &f(C)=0¬(xC11…xCnn) = &f(C)=0(¬xC11…¬xCnn) = &f(C)=0(x¬C11…x¬Cnn)
Определение: Правая часть представления (3) называется СКНФ для функции f.
Замечание: для всякой функции f≠1 СКНФ единственна.
