В число шестнадцати переключательных функций входят функции, рассмотренные в п.1:

f₀(x,y) = 0 -- константа нуль;

f₁₅(x,y) = 1 -- константа единица;

f₃(x,y) = x --переменная x;

f₅(x,y) = y --переменная y;

f₁₂(x,y) = --инверсия x;

f₁₀(x,y) = --инверсия y;

Таблица 2

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

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

Функция f₁(x,y) называется конъюнкцией, или логическим умножением. Таблица истинности этой функции совпадает с таблицей умножения двух одноразрядных двоичных чисел. Можно ввести функцию n аргументов, соответствующую произведению n одноразрядных двоичных чисел. Такая переключательная функция равна единице тогда и только тогда, когда все ее аргументы равны единице. Для конъюнкции справедливы следующие соотношения:

x 0 = 0;

x 1 = x;

x x = x;

x y = y x;

x = 0.

Функция f₇(x,y) называется дизъюнкцией или логическим сложением. Эта функция равна нулю только в том случае, когда все ее аргументы равны нулю. Можно ввести функцию n аргументов, соответствующую логическому сложению n одноразрядных двоичных чисел. Такая переключательная функция равна нулю тогда и только тогда, когда все ее аргументы равны нулю. Для конъюнкции справедливы следующие соотношения:

x 0 = x;

x 1 = 1;

x x = x;

x y = y x;

x = 1.

Таблица истинности функции f₆(x,y) совпадает с таблицей сложения двух одноразрядных двоичных чисел по модулю два. Можно ввести функцию n аргументов, соответствующую сумме по модулю два n одноразрядных двоичных чисел. Такая переключательная функция определяется следующим условием: она равна единице, если число аргументов, равных единице, нечетно, и равна нулю, если число таких аргументов четно. Приведем некоторые соотношения для суммы по модулю два:

x 0 = x;

x 1 = ;

x x = 0;

x x x = x;

x y = y x.

Рассмотренные шестнадцать функций двух аргументов (будем называть их элементарными) позволяют строить новые переключательные функции следующим образом:

путем перенумерации аргументов;

путем подстановки в функцию новых функций вместо аргументов.

Функцию, полученную из функций f₁, f₂, …, f_k путем применения (возможно многократного) этих двух правил, будем называть суперпозицией функций f₁, f₂, …, f_k. Например, имея элементарные функции инверсии, конъюнкции, дизъюнкции, импликации, запрета, сложения по модулю два, можно составить новую переключательную функцию:

f (x,y,z) = ((y)z)((yz)x).

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

Пример 1. Представить в виде таблицы функцию

f (x,y,z) = ((y)z)((yz)x).

Решение. Функцию f (x,y,z) будем представлять последовательно, записывая в столбцы табл. 1.5 промежуточные результаты, получаемые после выполнения каждой операции:

Таблица 3

Таблица истинности функции f (x,y,z) = ((y)z)((yz)x).

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

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

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

Определение 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, поставить знак отрицания.

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

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

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_nx_n a_n+1x₁ x₂ … a_Nx_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₂(1x₃)x₄x₅.

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

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

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

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

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

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

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

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

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

f₅₈(x₁,x₂,x₃)=(1x₁)x₂(1x₃)(1x₁)x₂x₃ x₁(1x₂)(1x₃)x₁x₂(1x₃).

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

f₅₈(x₁,x₂,x₃)= x₁ x₂ x₁x₂x₁x₃.

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

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

. (3)

Если подставить в выражение (3) значения f_(i), то получим дизъюнкцию конституент, которые равны еди-нице на тех же наборах, что и заданная функция. Дей-ствительно, ввиду того, что 0x=0 и 0х=х, члены вы-ражения (2), в которых коэффициенты f_(i)=0, можно опустить, а так как x1 = x, то коэффициенты f_(i)=1 можно не писать. Тогда

где j₁, …,j_m - номера наборов, на которых функция равна единице;

m - число таких наборов.

Определение 3. Дизъюнкция конституент единицы, равных единице на тех же наборах, что и заданная функция, называется совершенной дизъюнктивной нормальной формой переключательной функции.

Любую переключательную функцию f(x₁, . . . , x_n) (кроме константы ноль) можно представить в совершенной дизъюнктивной нормальной форме. Заметим, что любая переключательная функция имеет единственную совершенную дизъюнктивную нормальную форм у: это непосредственно следует из выражения (3).

Совершенную дизъюнктивную нормаль-ную форму переключательной функции удобно находить в такой последователь-ности:

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

записать под каждым произведением набор аргу-ментов, на котором функция равна единице, и над аргу-ментами, равными нулю, поставить знаки отрицания.

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

Пример 4. Представить в совершенной дизъюнктивной нормальной форме переключательную функцию четырех аргументов f₂₃₈₀₅(x₁,x₂,x₃,x₄) (см. табл. 2).

Решение. Из табл. 2 видно, что переключательная функция принимает значения, равные единице, на следующих наборах аргументов:

0001, 0011, 0100, 0101, 1000, 1001, 1010, 1011, 1100, 1101, 1111.

Таким образом, совершенная дизъюнктивная нормальная форма функции f₂₃₈₀₅(x₁,x₂,x₃,x₄) будет состоять из одиннадцати дизъюнкций, каждая из которых представляет собой конъюнкцию четырех элементов:

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

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

Рассмотрим выражение

, (4)

где f_(i) - значение переключательной функции на i-м наборе.

Ввиду справедливости соотношений 1 x = 1 и 0х= х, при подстановке в выражение (4) значений функ-ции f_(i), сомножители, у которых f_(i), == 1, можно опустить, а значения функции f_(i)=0 не писать. Тогда

(5)

где j₁, j₂, …,j_m -номера наборов, на которых функ-ция равна нулю;

т -число таких наборов.

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

Любая переключательная функция f(x₁, . . . , x_n) (кроме константы единицы) может быть пред-ставлена в совершенной конъюнктивной нормальной форме. Любая переключательная функ-ция имеет единственную совершенную конъюнктивную нормальную форму.

Сформулируем правило представления переключа-тельной функции в совершенной конъюнктивной нор-мальной форме. Чтобы представить переключательную функцию п аргументов в совершенной конъюнктивной нормальной форме, достаточно:

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

выписать под каждым сомножителем набор аргу-ментов, на котором функция равна нулю, и над аргу-ментами, равными единице, поставить знаки отрицания;

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

Пример 5. Представить в совершенной конъюнктив-ной нормальной форме функцию f₂₃₈₀₅(x₁,x₂,x₃,x₄) (см. табл. 2).

Решение. Из табл. 2 видно, что переключательная функция принимает значения, равные нулю, на следующих наборах аргументов:

0000, 0010, 0110, 0111, 1110.

Таким образом, совершенная конъюнктивная нормальная форма функции f₂₃₈₀₅(x₁,x₂,x₃,x₄) будет состоять из пяти конъюнкций, каждая из которых представляет собой дизъюнкцию четырех элементов:

ЛИТЕРАТУРА

1. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учебник для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.- М.: изд-во МГТУ им. Н.Э. Баумана, 2001.- 744 с. (Сер. Математика в техническом университете; Вып XIX).

2. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика.- М.: Наука, Физматлит, 2000.- 544 с.- ISBN 5-02-015238-2.

3. Зарубин В.С. Математическое моделирование в технике: Учеб. для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.- М.: Изд-во МГТУ им. Н.Э. Баумана, 2001.- 496 с. (Сер. Математика в техническом университете; вып. XXI, заключительный).