Представление переключательной функции в виде многочленов.

Из определения следует, что число различных конституент единицы среди функций n аргументов равно 2ⁿ. Конституенты единицы обозначаются так: K_i(x₁, …, x_n), где i – номер набора, на котором конституента равна единице. Например, запись K₇(x₁, x₂, x₃, x₄) означает функцию четырех аргументов, равную единице на наборе (0111).

Конституента единицы может быть выражена через конъюнкцию всех аргументов, каждый из которых входит в произведение со знаком отрицания или без него. Приведенную выше конституенту единицы можно представить через конъюнкцию аргументов следующим образом:

K₇(x₁, x₂, x₃, x₄) = .

Чтобы записать в виде произведения конституенту K_i(x₁, …, x_n), можно воспользоваться следующим правилом: записать n -разрядное двоичное число (n – число аргументов), равное i, и конъюнкцию n переменных; над переменными, места которых совпадают с позициями нулей в двоичном числе i, поставить знак отрицания.

Пример 3.1. Записать конституенту, равную единице на двенадцатом наборе для функции пяти переменных.

Решение. Пятиразрядное двоичное число, равное двенадцати, записывается в виде: 01100. Запишем произведение пяти аргументов, располагая их в порядке возрастания индексов: x₁×x₂×x₃×x₄×x₅. Сопоставляя это произведение с двоичным числом 01100, определяем, что знаки отрицания необходимо поставить над первым, четвертым и пятым аргументами:

K₁₂(x₁, x₂, x₃, x₄, x₅) = .

Определение 1.3.2. Конституентой нуля называют переключательную функцию n аргументов, которая принимает значение, равное нулю, на одном единственном наборе аргументов.