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

85 Функция l(x:=iy) не является монотонной, так как на наборе (1,0) равна единице, а на большом наборе (1,1) - нулю. Нетрудно убедиться, что имеет место приведенная далее теорема и следствие из этой теоремы. Теорема 3.22. При суперпозиции монотонных функций получается монотонная функция. Следствие 3.8. В полной системе функций должна содержаться хотя бы одна немонотонная функция. 4. Линейные функции. Функция f(xi,x2, называется линейной, если f(X,,X2, =Co+C/cfex/+C2cfeX2+...+C „(b:„ где С; - константы (единица или нуль), 0<i<n. Примеры линейных функций. Линейными являются следующие двухаргументные функции: тождественно равная нулю (f(x,y)=Q), тождественно равная единице а также f(x,y)=x, f(x,y)=\+x, f(x,y)=y, f(^-y)~'^+y, f(x,y)=x+ у, f(x,y)=\^ x+ y. Других двухаргументных линейных функций нет. Например, функция f(x,y)=x&y является нелинейной. Легко доказать следующую теорему. Теорема 3.23. Суперпозиция линейных функций является линейной функцией. j Следствие 3.9. В полной системе булевых функций должна содержаться хотя бы одна нелинейная булева функция. Действительно, в противном случае нельзя получить нелинейную функцию, например, х&у. Пусть Ро- класс функций, сохраняющих нуль, Р г класс функций, сохраняющих единицу, S - класс самодвойственных функций, М - класс монотонных функций, L - класс линейных функций. Теорема 3.24. (Теорема Поста). Для полноты системы функций 0={cpi, \ (Рп} необходимо и достаточно, чтобы для каждого из классов Ро, Pi, S, М,Ь ь Ф нашлась функция <pi, ему (классу) не принадлежащая. | Необходимость условий теоремы вытекает из следствий 3.5-3.9. Доказательство достаточности не приводим.