Теорема 2. Любая функция k - значной логики может быть представлена в виде СДНФ:
f(x1,..., xn) = v js1(x1) & js2(x2) &... jsn(xn) & f (s1, s2,..., sn)
или в виде s-p формы:
f(x1,..., xn) = Å Ys1 (x1) & Ys2 (x2)... & Ysn (xn) Ä f (s1,...,sn).
Пример. Для функции, заданной таблицей истинности
x1 | x2 | f |
0дд 0 | ||
составить СДНФ и s-p форму.
Решение. Заметим, что значения xi в таблице соответствуют индексам si при функциях ji и Yi. И в соответствии с выше обозначенными формулами можно записать:
f(x1, x 2) = j0(x1) & j1(x2) & 1 v j0(x1) & j2(x2) & 2
v j2(x1) & j1(x2) & 1.
f(x1, x 2) = Y0(x1) & Y1(x2) Ä 1 Å Y0(x1) & Y2(x2) Ä 2
Å Y2(x1) & Y1(x2) Ä 1.