СДНФ и СКНФ
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, x2,…,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 СКНФ единственна.
- Дизъюнктивная и Конъюнктивная нормальные формы. Разложение функции по компонентам
- Класс линейных функций и его замкнутость относительно суперпозиции
- Суперпозиция функций. Функционально замкнутые классы
- Теорема Форда-Фалкерсона о максимальном потоке
- Функции и отношения, их свойства
- Графы, мультиграфы, псевдографы, орграфы. Изоморфизм графов
- Рекуррентные уравнения, порядок уравнения, частное и общее решение
- Решетки
- Класс самодвойственных функций и его замкнутость относительно суперпозиции. Критерий самодвойственности. Лемма о несамодвойственной функции.
- Графы и группы подстановок, орбита группы подстановок
- Двойственные функции. Теорема о суперпозиции двойственных функций. Принцип двойственности
- Производящая функция для сочетаний без повторений и с повторениями с ограничением на число повторений
- Линейные рекуррентные уравнения(ЛРУ) однородные и неоднородные с переменными коэффициентами
- Булевы решетки и булевы алгебры
- Линейные рекуррентные уравнения однородные и неоднородные с постоянными коэффициентами
- Лемма о немонотонной функции. Критерий монотонности по сокращенной ДНФ
- Плотность распределения функции распределения вероятностей
Рубрика: Математика