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

Т а б л и ц а 4.36 Булева функция, заданная таблично XI х2 *3 / (хи хь хг) 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 1 Как видим, Уо = / в = f n = 0, остальные полиномиальные коэф­ фициенты равны 1. Нули можно не выписывать, а отсутствие сла­ гаемого (конъюнкции) вида х хх2...хк будет означать, что f n к - 0. Таким образом, предпоследнее выражение тоже является поли­ номом Жегалкина. Итак, с помощью конъюкции и М2 любую логическую функ­ цию можно единственным образом представить в виде многочлена. Иногда можно представить функцию в виде полинома Жегалкина более простым способом. Например, функцию ху будем искать в виде многочлена с неопределенными коэффициентами: х у = а ® Ф Ьх ф с у © dxy. При х = 0, у = 0 будет 0 = а; при х = 0, у = 1 имеем 0 = 0 Ф с, откуда с = 0; при х = 1, у = 0 имеем 1 = b Ф 0, т.е^Ь = 1. Наконец, при х = у = 1 получим 0 = 1 Ф < / и < / = 1 . В итоге х у = х Ф ху . 4.8.2. Функциональная замкнутость Обозначим через Р2 множество всех функций алгебры логики. Класс функций R с Р2 называется функционально замкнутым, если любая суперпозиция функций этого класса R принадлежит этому же классу. Это означает, что вместе с каждой функцией f(X]X 2 . . . x m) е R классу R принадлежит и функция / (у \у2.-.ут), где у, — необяза­ тельно различные функции или аргументы и f ( f f 2 .. f m) е R, если f { x xx 2 . . . xm) е R и для всех i = 1, 2, ..., п либо fj{xhx h...xir) е R, либо fj[Xi,Xk...Xu) ш xk. Рассмотрим наиболее важные функционально замкнутые классы функций алгебры логики. 193