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

83 Из теоремы 3.7 следует, что других полных систем функций, состоящих только из одной двуместной функции, нет. Из теорем 3.14 и 3.4 следует полнота каждой из систем функций: / 7 х , х&у} ; {]х, х\/у} ; {]х, х^у}. Можно показать, что, кроме перечисленных полных систем функций, существуют различные другие полные системы, например, является полной система функций {х&у, Кхщ/), xvlx}. Система булевых фунщий {(pj, (р2,..., (pj называется базисом, если она является полной системой функций, но никакая; ее собственная часть не образует полную систему функций. Примерами базиса будут системы {1, &}, {/}, но {1, &, vj -яе базис, ибо ее подсистема {], &} - полна. Естественно выяснить, есть ли критерии полноты системы функций, т.е. можно ли выяснить, когда (при каких условиях) та или иная система функций полна. И если есть такие критерии, то в чем они состоят. Ответом является теорема Поста. Но прежде чем ее сформулировать, введем некоторые новые понятия. 1. Функции, сохраняющие нуль (единицу). Булеваф у н к ц и я . . . . x j называется сохраняющей нуль (единицу), если/(13,0,...,0j=0 " Например, функция х&у, очевидно, сохраняет О, а функция Ixvlyvz сохраняет 1, Функция х^ у не сохраняет О, а х^1 у не сохраняет единицу. Таким образом, есть функции, сохраняющие О, функции, сохраняющие 1, а также есть функции, не сохраняющие О и функции, не сохраняющие 1. Теорема 3.20. Суперпозиция булевых функций, сохраняющих нуль (единицу), есть снова булева функция, сохраняющая нуль (единицу). Доказательство. Пусть даны булевы функции, сохраняющие нуль: f(Xj ,X2, (pi(yn<yi2,--.yi(mlj)> <Р2 (У21>У22,---,У2 (т2)):"-< (Рп(Уп1,Уп2 УпОт) Подставляя функции (pi,(p2,...,% вместо аргументов получаем новую функцию F(yn ,yi2, •••,yi(mO:---> Уп1,уп2, •••,Уп(тп))~f(Ph (Рп)- Найдем значение функции F на нулевом наборе, полагая все Так как каждая из функций cpi сохраняет нуль и, следовательно, равна нулю при нулевых значениях аргументов y j , а также /f'0,0,..,,0j=0, то получим, что i^(0,0,...,0; ;0,0,...,0J=0. Для функций, сохраняющих единицу, доказательство проводится аналогично. Следствие 3.5. В полной системе функций должна содержаться хотя бы одна функция, не сохраняющая нуль, т.е. равная единице на нулевом наборе.