Реферат: Переключательные функции одного и двух аргументов

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

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

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

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

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

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

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

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

Теорема Жегалкина . Любая переключательная функ­ция может быть представлена в виде полинома (много­члена), т. е. записана в форме

f(x₁ , . . . , x_n ) = а_о Å a₁ x₁ Å a₂ x₂ Å … Å a_n x_n Å a_n+1 x₁ x₂ Å … Å a_N x_1… x_n ,

(1)

где a₀ , a₁ x₁ , … a _N — константы, равные нулю или единице;

Å — операция сложения по модулю два.

При записи конкретной переключательной функции в виде многочлена коэффициенты a₀ , a₁ x₁ , … a _N выпа­дают, так как члены, при которых коэффициенты рав­ны нулю, можно опустить, а коэффициенты, равные еди­нице, не писать.

Для доказательства теоремы Жегалкина предположим, что задана произвольная переключатель­ная функция п аргументов f ( x ₁ , . . . , x_n ), равная еди­нице на некотором числе наборов с номерами m ₁ , … m_p .

Покажем, что переключательная функция f ( x ₁ , . . . , x_n ) равна сумме конституент единицы, ко­торые равны единице на тех же наборах, что и данная функция:

f(x₁ , . . . , x_n ) = K_m1 Å K_m2 Å . . . Å K_mp . (2)

Действительно, на каждом из наборов с номерами m ₁ , … m_p равна единице только одна конституента, стоящая в правой части выражения (2), а осталь­ные равны нулю. Следовательно, на этих наборах и только на них правая часть выражения (2) принимает значение, равное единице.

Для того чтобы перейти от выражения (2) к виду (1), достаточно представить конституенты едини­цы в виде произведений и, используя соотношение , заменить все переменные с отрицаниями (так как отрицания в выражение (3.1) не входят). Пусть на­пример, конституента единицы записана в виде

.

Тогда получим

K_i = (1 Å x ₁ ) x ₂ (1 Å x ₃ ) x ₄ x ₅ .

Раскрывая скобки и приводя подобные члены в соответствии со свойствами операции сложения по модулю два, получаем запись заданной функ­ции в форме (1), что и доказывает теорему.

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

Чтобы переключательную функцию, заданную таблицей истинности, представить в виде полинома Жегалкина, доста­точно записать функцию в виде суммы конституент еди­ницы, равных единице на тех же наборах, на которых равна единице заданная функция. Затем все аргументы, входящие в полученное выражение с отрицанием, заме­нить с помощью соотношения , раскрыть скобки и привести подобные члены с учетом тождества;

x , если п нечетно,

x Å x Å . . . Å x = 0, если п четно.

Пример 3. Представить в виде полинома Жегалкина функцию f ₅₈ ( x ₁ , x ₂ , x ₃ ) .

Функция f ₅₈ ( x ₁ , x ₂ , x ₃ ) равна единице на втором, третьем, четвертом и шестом наборах, и может быть записана в виде суммы соответствующих конституент единицы: