2014-02-09
1046
Рассмотрим на примерах.
1 способ. Определение неизвестных коэффициентов (если функция задана таблицей). Записываем полином в общем виде
.
Находим неизвестные коэффициенты, используя значения функции на всех наборах.
Следовательно,
.
2 способ. Использование алгебраических преобразований (если функция задана формулой).
.
3 способ. С помощью треугольника Паскаля по единицам его левой стороны (табл. 9.4).
f = (10011110).
Таблица 9.4
Построение многочлена Жегалкина для функции f
| Слагаемые многочлена | x 1 | x 2 | x 3 | f | Треугольник Паскаля |
| x 3 | |||||
| x 2 | |||||
| x 2 x 3 | |||||
| x 1 | |||||
| x 1 x 3 | |||||
| x 1 x 2 | |||||
| x 1 x 2 x 3 |
Верхняя сторона треугольника это функция f. Остальные элементы определяются как сумма по модулю двух соседних элементов предыдущей строки. В первом столбце таблицы показаны слагаемые многочлена Жегалкина, соответствующие всем наборам. В полиноме Жегалкина для данной функции будет содержаться столько слагаемых, сколько единиц в левой стороне треугольника.
Следовательно,
.
Определение. Пусть M – некоторое подмножество функций из P 2. Замыканием M называется множество всех булевых функций, представимых в виде формул через функции множества M. Обозначается [ M ].
Замечание. Замыкание инвариантно относительно операций введения и удаления фиктивных переменных.
Примеры.
1) M = P 2, [ M ]= P 2.
2) M ={1, x 1Å x 2}, [ M ] – множество L всех линейных функций вида
, (ci =0,1).
Свойства замыкания:
1) [ M ]= M;
2) [[ M ]]=[ M ];
3) M 1Í M 2 Þ [ M 1]Í[ M 2];
4) [ M 1È M 2] Í [ M 1]È[ M 1].
Определение. Класс (множество) M называется (функционально) замкнутым, если [ M ]= M, т.е. любая суперпозиция функций из M снова принадлежит M.
Примеры.
1) Класс M = P 2 функционально замкнут;
2) Класс {1, x 1Å x 2} не замкнут;
3) Класс L замкнут (линейное выражение, составленное из линейных выражений линейно).
Новое определение полноты. M – полная система, если [ M ]= P 2.
