🔥

Алексеев В. Б. - Дискретная математика - Полиномы Жегалкина. Замкнутые классы. Часть 1

Прежде всего стоит отметить, что некоторая часть информации о полиномах Жегалкина была пройдена на прошлой лекции:

Полиномы Жегалкина

Монотонная конъюнкция 1:17:22

Монотонной конъюнкцией над переменными называют либо , либо произведение из различных переменных без отрицания
Для ФАЛ из переменных существует ровно монотонных конъюнкций

Полином Жегалкина 1:18:47

Полиномом Жегалкина над переменными называется либо , либо сумма по модулю 2 () из различных монотонных конъюнкций над переменными

Существование и единственность полинома Жегалкина 1:22:20

может быть представлена полиномом Жегалкина, причем единственным образом

Положим как монотонную конъюнкцию всех , чей индекс совпадает с единицами в двоичном представлении . Например, 20:00

При

  1. : мы можем положить как , так и
Лемма 1 33:50

Пусть имеется ФАЛ и ее подфункции:


Тогда , где

Быстрый алгоритм построения полинома Жегалкина

Пусть ФАЛ представлена своим вектором: . Тогда ,
Пусть — соответствующий полином Жегалкина. Положим
Тогда, согласно лемме 1, если и , то

Так, рекурсивно мы делим наши функции на половинки по переменной, пока не упремся в просто суммы по модулю 2:
. Тогда

Пара иллюстраций для понимания работы алгоритма. Для большей конкретики я взял в скобочки те подфункции из 2-х элементов, на которые мы разбиваем полином:

Замкнутые классы

Замыкания множества ФАЛ 55:56

Пусть — любое подмножество ФАЛ (, — множество всех ФАЛ)
Тогда замыканием называется множество всех ФАЛ , которые можно выразить формулой над

То есть, — полная

Свойства замыкания:


  3. 1:01:04
Interactive Graph
Table Of Contents
🔥Алексеев В. Б. - Дискретная математика - Полиномы Жегалкина. Замкнутые классы. Часть 1
Полиномы Жегалкина
Замкнутые классы