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

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

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

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

так: Ki(x1, …, xn), где i – номер набора, на котором конституента равна единице. Например, запись K7(x1, x2, x3, x4) означает функцию четырех аргументов, равную единице на наборе (0111).

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

K7(x1, x2, x3, x4) = .

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

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

Решение. Пятиразрядное двоичное число, равное двенадцати, записывается в виде: 01100. Запишем произведение пяти аргументов, располагая их в порядке возрастания индексов: x1×x2×x3×x4×x5. Сопоставляя это произведение с двоичным числом 01100, определяем, что знаки отрицания необходимо поставить над первым, четвертым и пятым аргументами:

K12(x1, x2, x3, x4, x5) =.

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

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

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

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

Решение. Пятиразрядное двоичное число, равное двадцати пяти, записывается в виде: 11001. Запишем дизъюнкцию пяти аргументов, располагая их в порядке возрастания индексов: x1Úx2Úx3Úx4Úx5. Сопоставляя это произведение с двоичным числом 11001, определяем, что знаки отрицания необходимо поставить над первым, вторым и пятым аргументами:

M25(x1, x2, x3, x4, x5) =.

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

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

f(x1, . . . , xn) = ао Å a1x1 Å a2x2 Å …Å anxn Å an+1x1 x2Å … Å aNx1…xn ,

(1)

где a0, a1x1, … aN— константы, равные нулю или единице;

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

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

Для доказательства теоремы Жегалкина предположим, что задана произвольная переключатель­ная функция п аргументов f(x1, . . . , xn), равная еди­нице на некотором числе наборов с номерами m1, … mp.

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

f(x1, . . . , xn) = Km1 Å Km2 Å . . . Å Kmp. (2)

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

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

.

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

Ki= (1 Å x1)x2(1Åx3)x4x5.

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

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

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

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

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

Пример 3. Представить в виде полинома Жегалкина функцию f58(x1,x2,x3).

Функция f58(x1,x2,x3) равна единице на втором, третьем, четвертом и шестом наборах, и может быть записана в виде суммы соответствующих конституент единицы:

f58(x1,x2,x3) =K2Å K3Å K4Å K6 =.

Используя соотношение , получаем

f58(x1,x2,x3)=(1Åx1)x2(1Åx3)Å(1Åx1)x2x3Å x1(1Åx2)(1Åx3)Åx1x2(1Åx3).

Приводя подобные члены, окончательно находим

f58(x1,x2,x3)= x1Å x2Å x1x2Åx1x3.

3. Совершенная дизъюнктивная нормальная форма переключательной функции.

В общем виде пере­ключательная функция п аргументов может быть задана таблицей истинности. Обозначим через f(i) (i=0, … ,2n-1) значение функции на i-м наборе аргументов. Напомним, что каждая из величин f(i) принимает значение нуль или единица. В соот­ветствие i-му набору аргументов можно поставить конституенту единицы Ki, которая принимает значение, равное единице только на данном f(i) наборе. Умножим каждую конституенту единицы Ki на значение функ­ции f(i) и рассмотрим дизъюнкцию произведений fiKi:

 Скачать реферат