Cтраница 2
Операции отрицания и сложения ( по модулю два) являются линейными операциями, поскольку каноническими полиномами представляющих их булевых функций будут линейные формулы х 1 и х - f - у. В то же время функции ху и хУу, а значит, и определяемые ими операции умножения и дизъюнкции нелинейны. Первая из них имеет в качестве своего канонического полинома формулу ху, а вторая - формулу х у ху. [16]
После указанной подстановки получим булеву функцию двух переменных ф ( л -, /), канонический полином которой имеет вид XiXj - - axt & х / Y. Если эта функция равна - или / / х / xiXj xt х /, то теорема доказана. В противном случае, будучи нелинейной, эта функция, в силу теоремы 3, будет обязательно немонотонной. [17]
Программы 3.3 тестируются с помощью табл. 3.2, результаты должны совпадать с данными, полученными при вычислении канонического полинома и полинома Лагранжа. [18]
В алгебре Жегалкина роль совершенных форм булевой алгебры играют полиномы специального вида, которые мы будем называть каноническими полиномами. [19]
Любая булева функция может быть представлена в алгебре Жегалкина в виде одного и ( с точностью до порядка членов) только одного канонического полинома. [20]
Располагая функциями Xi, х -, Xi 1, Xj 1, можем в функции ф произвести замену Xi на xt Р, a Xj - на х / а, после чего получим функцию § ( Xi, Xj) с каноническим полиномом ( xt р) ( / - f -) - f - a ( t Р) Р ( - а) Y Ъ Xj axi Р / Р ах, ар Р / ар Y / 6, гДе буквой б обозначена булева константа ар - f - у. Если 6 0, то ty ( xi, xf) xf KJ, и теорема доказана. [21]
Точно таким же способом, какой был применен при доказательстве теоремы 5.3, можно показать, что описанный прием проведения преобразований выражений алгебры Жегалкина заканчивается через конечное число шагов. Поскольку он приводит к построению канонического полинома, мы можем сформулировать следующий результат. [22]
В отличие от канонического интерполяционного полинома для вычисления значений полинома Лагранжа не требуется предварительного определения коэффициентов полинома путем решения системы уравнений. Однако для - каждого значения аргумента х полином (3.5) приходится пересчитывать вновь, коэффициенты же канонического полинома вычисляются только один раз. С известными коэффициентами для вычисления значений канонического полинома требуется значительно меньшее количество арифметических операций по сравнению с полиномом Лагранжа. Важное место занимает полином Лагранжа в теории численных методов. [23]
В отличие от канонического интерполяционного полинома для вычисления значений полинома Лагранжа не требуется предварительного определения коэффициентов полинома путем решения системы уравнений. Однако для - каждого значения аргумента х полином (3.5) приходится пересчитывать вновь, коэффициенты же канонического полинома вычисляются только один раз. С известными коэффициентами для вычисления значений канонического полинома требуется значительно меньшее количество арифметических операций по сравнению с полиномом Лагранжа. Важное место занимает полином Лагранжа в теории численных методов. [24]
Операции отрицания и сложения ( по модулю два) являются линейными операциями, поскольку каноническими полиномами представляющих их булевых функций будут линейные формулы х 1 и х - f - у. В то же время функции ху и хУу, а значит, и определяемые ими операции умножения и дизъюнкции нелинейны. Первая из них имеет в качестве своего канонического полинома формулу ху, а вторая - формулу х у ху. [25]