СДНФ и СКНФ

Теорема (о СДНФ):

Всякая тождественно не равная 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 СКНФ единственна.


Оставить комментарий





Статистика

Рейтинг@Mail.ru