Преобразование Мёбиуса

Пусть у нас есть некоторая
Нужно построить полином Жегалкина по таблице истинности (очевидно это , сделаем вид что мы не знаем какой у неё П.Ж.):

Полном Жегалкина выражается в виде:
Довольно легко сделать вывод, что , когда (вектор аргументов - доминирует над вектором участника ксора - : )

Следовательно, можно упростить до

Кортеж аргументов функции -
Полином Жегалкина -
🥳

( описана ниже)

Теорема

3. 
   
   

Схемы из функциональных элементов (Boolean circuits)

Типы вершин в графе

• - входные вершины (аргументы)
• - функциональная вершина (в неё входит рёбер, где - арность функции)
• - выходная вершина (значение)

Пример:

Теорема

- базис Функцию - можно записать формулой в базисе можно записать в схеме в
- минимальное число ф. эл. в схеме для над
- максимальная длина пути для в

Теорема

- базисы


Можно асимптотически оценивать схему без базиса