Переключательные функции одного и двух аргументов (стр. 3 из 3)
где j1, …,jm – номера наборов, на которых функция равна единице;
m– число таких наборов.
Определение 3. Дизъюнкция конституент единицы, равных единице на тех же наборах, что и заданная функция, называется совершенной дизъюнктивной нормальной формой переключательной функции.
Любую переключательную функцию f(x1, . . . , xn) (кроме константы ноль) можно представить в совершенной дизъюнктивной нормальной форме. Заметим, что любая переключательная функция имеет единственную совершенную дизъюнктивную нормальную форм у: это непосредственно следует из выражения (3).
Совершенную дизъюнктивную нормальную форму переключательной функции удобно находить в такой последовательности:
· выписать ряд произведений всех аргументов и соединить их знаками дизъюнкции; количество произведений должно равняться числу наборов, на которых заданная функция обращается в единицу;
· записать под каждым произведением набор аргументов, на котором функция равна единице, и над аргументами, равными нулю, поставить знаки отрицания.
Это правило называют иногда правилом записи переключательной функции по единицам.
Пример 4. Представить в совершенной дизъюнктивной нормальной форме переключательную функцию четырех аргументов f23805(x1,x2,x3,x4) (см. табл. 2).
Решение. Из табл. 2 видно, что переключательная функция принимает значения, равные единице, на следующих наборах аргументов:
0001, 0011, 0100, 0101, 1000, 1001, 1010, 1011, 1100, 1101, 1111.
Таким образом, совершенная дизъюнктивная нормальная форма функции f23805(x1,x2,x3,x4) будет состоять из одиннадцати дизъюнкций, каждая из которых представляет собой конъюнкцию четырех элементов:
4. Совершенная конъюнктивная нормальная форма переключательной функции.
Если заданная переключательная функция равна единице на большинстве наборов аргументов, то представление функции в совершенной дизъюнктивной нормальной форме может оказаться достаточно громоздким. В этих случаях удобнее использовать другую форму представления функции – совершенную конъюнктивную нормальную форму. Для представления функций в этой форме используется функция конституенты нуля.
Рассмотрим выражение
, (4)где f(i) – значение переключательной функции на i-м наборе.
Ввиду справедливости соотношений 1Úx= 1 и 0Úх= х, при подстановке в выражение (4) значений функции f(i), сомножители, у которых f(i), == 1, можно опустить, а значения функции f(i)=0 не писать. Тогда
(5)где j1, j2, …,jm–номера наборов, на которых функция равна нулю;
т -число таких наборов.
Определение 4.Произведение конституент нуля, которые равны нулю на тех же наборах, что и заданная функция, называется совершенной конъюнктивной нормальной формой.
Любая переключательная функция f(x1, . . . , xn) (кроме константы единицы) может быть представлена в совершенной конъюнктивной нормальной форме. Любая переключательная функция имеет единственную совершенную конъюнктивную нормальную форму.
Сформулируем правило представления переключательной функции в совершенной конъюнктивной нормальной форме. Чтобы представить переключательную функцию п аргументов в совершенной конъюнктивной нормальной форме, достаточно:
· выписать произведение дизъюнкций всех аргументов с количеством сомножителей, равным числу наборов, на которых заданная функция обращается в нуль;
· выписать под каждым сомножителем набор аргументов, на котором функция равна нулю, и над аргументами, равными единице, поставить знаки отрицания;
Это правило иногда называют правилом записи переключательной функции по нулям.
Пример 5. Представить в совершенной конъюнктивной нормальной форме функцию f23805(x1,x2,x3,x4) (см. табл. 2).
Решение. Из табл. 2 видно, что переключательная функция принимает значения, равные нулю, на следующих наборах аргументов:
0000, 0010, 0110, 0111, 1110.
Таким образом, совершенная конъюнктивная нормальная форма функции f23805(x1,x2,x3,x4) будет состоять из пяти конъюнкций, каждая из которых представляет собой дизъюнкцию четырех элементов:
ЛИТЕРАТУРА
1. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учебник для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.– М.: изд-во МГТУ им. Н.Э. Баумана, 2001.– 744 с. (Сер. Математика в техническом университете; Вып XIX).
2. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика.– М.: Наука, Физматлит, 2000.– 544 с.– ISBN 5-02-015238-2.
3. Зарубин В.С. Математическое моделирование в технике: Учеб. для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.– М.: Изд-во МГТУ им. Н.Э. Баумана, 2001.– 496 с. (Сер. Математика в техническом университете; вып. XXI, заключительный).