Дискретная математика

72 f(xj, X2, X,i)^ & fx}'"' vx\ V... vx], "" ) ("i.a-, a „). й» ^=0 называется совершенной конъюнктивной нормальной формой (с.к.н.ф.) для/. Очевидно, что совершенная к.н.ф. (с.к.н.ф.) определяются в терминах, двойственных к с.д.н.ф. С.к.н.ф. функции/Сл:;Д2,.,..д:^, очевидно, является к.н.ф. этой функции, удовлетворяющая следующим условиям; -нет одинаковых множителей; -в каждый множитель входят все переменные Х;,Х2, ••Дп оД^н и только один раз (и только они) с отрицанием, либо без отрицания. С.к.н.ф. для функции / можно построить по таблице истинности этой функции. Для этого выбираем строки, где /=0. Для каждой строки, где /=0, строим конституенту нуля к!' следующим образом. Если в выбранной строке переменная Xj принимает значение I, то в А она входит с отрицанием, если xj=Q, то Xj входит в iv" без отрицания. Конъюнкция построенных конституант нуля и будет с.к.н.ф. Пример. Для функции f(x,y,z) предыдущего примера найдем с.к.н.ф. Нужно выбрать строки, где/=0. Это строки с номерами: 4 , 6 и 7. В результате получим с.к.н.ф.; (xvlyvlz)&(lx vyvlz) &(1х vjyvz). Второй метод построения с.к.н.ф. - метод равносильных ареоиразованнй, который применяется, когда булева функция задана в виде формулы и состоит в следующем; находим к.н.ф., затем добиваемся выполнения требуе.мых условий, вводя недостаюшие переменные согласно равносильности B~(B\o:)&(Bvlх/. При этом может оказаться, что исходная формула А тавтология и с.к.н.ф. не существует. 12. Полином Жегалкина Теорема 3.16 (Жегалкина). Любую булеву функцию/(С\-;, x2,...,xj можно ! единственным образом представить в виде: f(xi, Х2, •••, + ai&X] +а^с&Л2+...+ап £ &А'„ + On+i&xjc&x I а„ .;d:xic&xs+ ...+an&x)&x „+a„i, j&Xj&x2&x_:i+...+ar&x„.2&x„.i&Xf,+ ...+ I ai&Xi&X;&...&X„, j где £ 3/ fO < i<k) являются постоянными, равными нулю или единице. Правая 1 часть записанного равенства называется полиномом Жегалкта. Доказательство, Если функция тождественно равна нулю, то, очевидно, f(xi, xj,..., x,J=ao, an = 0. Пусть /(х-;,xj,..., x^J не тождественно равна нулю. Рассмотрим сумму всех собственных KOHCTHTyeifT единицы функции: