<<
>>

2.2.3.2. Линейные функции

Определение. Арифметические функции в алгебре логики это сложение по модулю два и умножение (конъюнкция).

Определение. Многочленом Жегалкина называется многочлен, являющийся суммой константы 0 или 1 и различных одночленов, в которые все переменные входят не выше, чем в первой степени: , причем на каждом наборе все аij (j = 1, …, k) различны, aj Î {0, 1}.

Теорема. Всякую булеву функцию можно представить единственным полиномом Жегалкина.

Многочлен Жегалкина можно получить различными способами. Остановимся на рассмотрении построения многочлена Жегалкина с помощью треугольника Паскаля. Рассмотрим алгоритм на примере.

Пример 46.

Построить многочлен Жегалкина для функции f=10011110.

Решение.

Алгоритм построения многочлена Жегалкина:

Шаг 1. Строим таблицу (табл. 57). Первый столбец содержит возможные слагаемые полинома Жегалкина. Нулевому набору всегда соответствует слагаемое 1. Остальным наборам соответствует слагаемое, представляющее собой конъюнкцию переменных, которые на данном наборе принимают значение 1. Следующие n столбцов – всевозможные наборы из 0 и 1, соответствующие переменным. Далее столбец значений функции f. Функция g является вспомогательной, поэтому изначально этот столбец не заполнен.

Таблица 57

Слагаемые полинома Жегалкина x1 x2 x3 f g Треугольник Паскаля
1 0 0 0 1
x3 0 0 1 0
x2 0 1 0 0
x2x3 0 1 1 1
x1 1 0 0 1
x1 x3 1 0 1 1
x1 x2 1 1 0 1
x1 x2 x3 1 1 1 0

Шаг 2. Построение треугольника Паскаля. Верхняя сторона треугольника есть функция f. Любой другой элемент треугольника есть сумма по модулю два двух соседних элементов предыдущей строки. Левая сторона треугольника представляет собой значение вспомогательной функции g (табл. 58).

Таблица 58

Слагаемые полинома Жегалкина x1 x2 x3 f g Треугольник Паскаля
1 0 0 0 1 1 f = 1 0 0 1 1 1 1 0
x3 0 0 1 0 1 1 0 1 0 0 0 1
x2 0 1 0 0 1 1 1 1 0 0 1
x2x3 0 1 1 1 0 0 0 1 0 1
x1 1 0 0 1 0 0 1 1 1
x1 x3 1 0 1 1 1 1 0 0
x1 x2 1 1 0 1 1 1 0
x1 x2 x3 1 1 1 0 1 1

Шаг 3. Построение полинома Жегалкина. В полином войдут только те слагаемые, которым соответствует единица во вспомогательной функции g.

Для данной функции многочлен Жегалкина имеет вид:

f = 1 + x3 + x2 + x1 x3 + x1 x2 + x1 x2 x3.

Определение. Функция f(x1, x2, …, xn) называется линейной, если многочлен Жегалкина для нее имеет следующий линейный относительно переменных вид:

f(x1, x2, …, xn) = a1x1 + … + anxn + an+1, где каждое ai равно 0 или 1.

Булева функция из рассмотренного выше примера не является линейной.

Теорема. Класс L = {f | f = a0+a1x1+…+anxn, aiÎ{0, 1}} линейных функций замкнут относительно суперпозиций.

<< | >>
Источник: Лекции - Дискретная математика. 2016

Еще по теме 2.2.3.2. Линейные функции:

  1. Линейная регрессия
  2. 7.1. Задачи линейного программирования
  3. 7.2. Построение экономико- математических моделей задач линейного программирования
  4. 7.3. Графическое решение задачи линейного программирования
  5. § 54. Построение эмпирической линейной функции методом наименьших квадратов
  6. СПЛАЙН-ФУНКЦИИ
  7. Возможна ли линейная функция спроса?
  8. Линейная регрессия.
  9. Линейная корреляция.
  10. 2.3. Элементарные функции и конформные отображения
  11. Тема 10. Множества. Числовые множества. Функция.
  12. 1.1. Линейная функция
  13. §2. Линейная и постоянная функции
  14. §3. Степенные функции
  15. § 5. Элементарные функции
  16. Приложение 3В. Линейное программирование
  17. Функции рыночного спроса