Спирина, М.С. Дискретная математика

явные выражения для а и р, получим h(x ) -< h(y), т.е. монотонную функцию. Следует отметить свойство монотонных булевых функций одно­ го и двух аргументов. Поскольку на В и В2 сравнимы лишь 0 ч 1 и 00 -< 11 соответственно, а значения получаются 0 -< 1, то такие монотонные функции будут сохраняющими 0 и 1, т.е. пересече­ нием этих двух подклассов. Каждый из пяти рассмотренных классов функций обладает очень важным свойством: любая из функций алгебры логики, полученная с помощью операций суперпозиции и подстановки из функций одного юшсса, обязательно будет принадлежать тому же классу булевых функций. 4.8.3. Функционально полные системы функций Систему S функций / , , f 2, ..., f m алгебры логики называют ф у н к ц и о н а л ь н о п о л н о й , если любую функцию алгебры логики можно записать с помощью суперпозиции некоторого набора бу­ левых функций f f 2 Очевидно, что если S — функционально полная система, то добавление любого числа булевых функций не изменит статуса системы как функционально полной. Функционально полная система функций называется б а зи с ом в пространстве Р2, если удаление хотя бы одной из функций, входящих в нее, превращает эту систему в функционально не­ полную. Ранее было доказано, что через функции Х\ v х2, х х л х2, х можно выразить любые функции алгебры логики, приведя их к виду СКНФ или СДНФ. Следовательно, система этих трех функ­ ций полна. Так же мы представляли любую функцию в виде ком­ позиции суммы по модулю два, конъюнкции и константы 1 (уда­ ление всех 0 приводило к равной функции). Однако это не един­ ственные возможности для представления функций алгебры логики. Оказывается, существует довольно много функционально полных систем. _Например, булевы функции можно выразить только через jc , v х2 и х , воспользовавшись правилом Де Моргана и представив опе­ рацию конъюнкции через дизъюнкцию и отрицание, так как X, Л Х 2 = Х х VJC2. К ри т ерий функциональной полноты системы функций сфор­ мулирован в теореме Поста—Яблонского. Для того чтобы система S функций f f 2. . . fmалгебры логики была функционально полной, необходимо и достаточно, чтобы она содер­ жала функцию : не сохраняющую константу 0; не сохраняющую константу 1; 196