Дизъюнктивная и Конъюнктивная нормальные формы. Разложение функции по компонентам
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 могут стоять на любых аргументных местах функции.
