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

Конституенты.

В п. 1.2 был рассмотрен один из возможных способов представления переключательной функции – задание ее в виде таблицы истинности. В этом разделе будем решать обратную задачу, а именно представление переключательной функции, заданной таблицей истинности, через элементарные функции, образующие базис.

Рассмотрим переключательные функции, называемые конституентами.

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

Из определения следует, что число различных конституент единицы среди функций 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 аргументов, которая принимает значение, равное нулю, на одном единственном наборе аргументов.

Из определения следует, что число различных конституент нуля среди функций n аргументов равно 2ⁿ. Конституенты нуля обозначаются так: M_i(x₁, …, x_n), где i – номер набора, на котором конституента равна нулю. Конституента нуля может быть выражена через дизъюнкцию всех аргументов, каждый из которых входит в произведение со знаком отрицания или без него.

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

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

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

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