Дизъюнктивная и Конъюнктивная нормальные формы. Разложение функции по компонентам
16.07.2010 | 
Автор: Определение: Элементарная конъюнкция, есть конъюнкция, составленная из попарно различных переменных или отрицаний переменных. (x,y,¬x&y&¬z)
Дизъюнктивная нормальная форма (ДНФ) – есть дизъюнкция, составленная из попарно различных элементарных конъюнкций. (xy?¬xy¬z?¬x¬y¬z)
Элементарная дизъюнкция есть дизъюнкция, составленная из попарно различных переменных или отрицаний переменных.
Конъюнктивная нормальная форма (КНФ) – есть конъюнкция попарно различных элементарных дизъюнкций.
Замечание: Введенные объекты могут допускать повторы своих элементов.
Введем обозначение xc = {x, если с=1, ¬x, если с=0}
&i=1..nAi = A1&A2&..&An
?i=1..nAi = A1?A2?..?An
заметим xc=1 ? x = c, ибо xc11&xc22&..&xcnn = 1 ? x1 = c1, x2 = c2,…, xn = cn
Лемма(о разложении ф-ции по компонентам).
Всякая ФАЛ допускает представление:
f(x1, x2,…, xn) = ?(c1,…,ck)f(c1,…,ck, xk+1,…, xn)xc11…xckk, где дизъюнкция берется по всем наборам из c1,..,ck из нулей и единиц.
Доказательство: Покажем, что равенство f(a1,…,an) = ?(c1,…,ck)f(c1,…,ck, ak+1,…,an) ac11…ackk – справедливо для любого (1) набора (a1,…,an) из 0 и 1.
Пусть правая часть =1, тогда найдется =1 дизъюнктивный член f(c1,…,ck, ak+1,…,an)ac11…ackk = 1 ? a1 = c1, a2 = c2, ak = ck и f(a1, a2,…,ak, ak+1,…,an) = 1 ? левая часть равенства (1) также =1.
Пусть теперь левая часть =1, тогда последовательно получаем следующее:
f(a1, a2,…,ak, ak+1,…,an) = 1
f(c1, c2,…,ck, ak+1,…,an)ac11…ackk = 1
?(c1,…,ck)f(c1,…,ck, ak+1,…,an ) ac11…ackk = 1 – правая часть (1)
Равенство (1) доказано, лемма установлена.
Замечание: Функция f(c1,…,ck, xk+1,…,xn) – называется компонентой функции f(x1, x2,…,xn). Переменные c1, c2,…,ck могут стоять на любых аргументных местах функции.
- Стандартизованные формы представления моделей
- Коронный разряд и формы коронного разряда
- Функции и отношения, их свойства
- Лемма о нелинейной функции
- Лемма о немонотонной функции. Критерий монотонности по сокращенной ДНФ
- Двойственные функции. Теорема о суперпозиции двойственных функций. Принцип двойственности
- Влияние формы воздействиующего напряжения на развитие разряда
- Лемма о немонотонной функции. Критерий монотонности по сокращенной ДНФ
- Производящие функции для комбинаторных конфигураций и их числа
- Функции алгебры логики
- Производящие функции для размещений с повторениями с ограничениями и без ограничений на число повторов
- Функции и процедуры, пакеты в VHDL
- СДНФ и СКНФ
- Геометрические свойства знакоопределенной функции Ляпунова
- Системы различных представителей, теорема Холла о совершенном паросочетании в двудольном графе
- Класс самодвойственных функций и его замкнутость относительно суперпозиции. Критерий самодвойственности. Лемма о несамодвойственной функции.
- Плотность распределения функции распределения вероятностей
Рубрика: Математика