Определение 1.3.4. Произведение конституент нуля, которые рав-
ны нулю на тех же наборах, что и заданная функция, называется совершенной конъюнктивной нормальной формой.
Любая переключательная функция f(x1, . . . , xn) (кроме константы единицы) может быть представлена в совершенной конъюнктивной нормальной форме. Любая переключательная функция имеет единственную совершенную конъюнктивную нормальную форму.
Сформулируем правило представления переключательной функции в совершенной конъюнктивной нормальной форме. Чтобы представить переключательную функцию п аргументов в совершенной конъюнктивной нормальной форме, достаточно:
•выписать произведение дизъюнкций всех аргументов с количеством сомножителей, равным числу наборов, на которых заданная функция обращается в нуль;
•выписать под каждым сомножителем набор аргументов, на котором функция равна нулю, и над аргументами, равными единице, поставить знаки отрицания;
Это правило иногда называют правилом записи переключательной функции по нулям.
Пример 3.5. Представить в совершенной конъюнктивной нормальной
форме функцию f23805(x1,x2,x3,x4) (см. табл. 1.2).
Решение. Из табл. 1.2 видно, что переключательная функция принимает значения, равные нулю, на следующих наборах аргументов:
0000, 0010, 0110, 0111, 1110.
Таким образом, совершенная конъюнктивная нормальная форма
функции f23805(x1,x2,x3,x4) будет состоять из пяти конъюнкций, каждая из которых представляет собой дизъюнкцию четырех элементов:
f23805 (x1, x2 , x3 , x4 ) = (x1 x2 x3 x4 )(x1 x2 x3 x4 )(x1 x2 x3 x4 )(x1 x2 x3 x4 )(x1 x2 x3 x4 ).
1.4. Пять классов переключательных функций. Теорема о функциональной полноте
Существует пять замечательных классов переключательных функций, обладающих следующим свойством: любая переключательная функция, полученная с помощью операций суперпозиции и подстановки из функций данного класса, обязательно будет принадлежать к тому же классу.
К пяти замечательным классам переключательных функций относят-
ся:
• линейные переключательные функции;
12
•переключательные функции, сохраняющие нуль;
•переключательные функции, сохраняющие единицу;
•монотонные переключательные функции;
•самодвойственные переключательные функции. Рассмотрим эти классы переключательных функций.
Линейные переключательные функции. В соответствии с теоре-
мой Жегалкина любая переключательная функция может быть представлена в виде многочлена (3.1).
Определение 1.4.1. Переключательная функция называется линей-
ной, если она может быть представлена полиномом степени не выше первой , т. е. записана в виде
f(x1, . . . , xn) = ао a1x1 a2x2 … anxn , |
(4.1) |
где ао, a1, ..., an — коэффициенты, равные нулю или единице.
Нетрудно найти число различных линейных функций п аргументов. Каждому набору коэффициентов ао, a1, ..., an (число которых равно n+1) можно поставить в соответствие (n+1)-разрядное двоичное число. Количество различных (n+1)-разрядных чисел, а следовательно, и количество линейных функций равно 2n+1.
Среди переключательных функций одного аргумента имеются четыре линейные функции, а так как общее число переключательных функций одного аргумента также равно четырем, все они линейны. Среди переключательных функций двух аргументов имеется восемь линейных. Для того чтобы найти эти функции в табл. 1.4, можно, пользуясь сформулированным в п. 1.3 правилом, представить все переключательные функции двух аргументов в виде полиномов и выбрать среди них линейные. Проще, однако, выписать все возможные линейные полиномы и найти соответствующие им функции в табл. 1.4:
f0(x,y) = 0,
f15(x,y)=1, f3(x,y)=x,
f5(x,y)=y,
f12(x,y)=1 x, f10(x,y)=1 y, f6(x,y)=x y,
f9(x,y)=1 x y.
Переключательные функции, сохраняющие нуль.
Определение 1.4.2.Если переключательная функция на нулевом
наборе аргументов (т.е. на наборе 0,0, …,0) равна нулю, то говорят, что эта функция сохраняет нуль.
Для переключательных функций, сохраняющих нуль, выполняется следующее условие:
13
f(0, …,0)=0.
Переключательные функции, сохраняющие единицу.
Определение 1.4.3. Если переключательная функция на единич-
ном наборе аргументов (т. е. на наборе 1,1, ..., 1) равна единице, то говорят, что эта функция сохраняет единицу.
Другими словами, если переключательная функция сохраняет единицу, то выполняется условие
f(1, …,1)=1.
Монотонные переключательные функции. Для того чтобы опре-
делить монотонную переключательную функцию, введем критерий сравнения двух наборов аргументов.
Определение 1.4.4. Если значение каждого аргумента одного набора
больше или равно значению того же аргумента второго набора, то говорят, что первый набор не меньше второго.
Подчеркнем, что это определение требует выполнения условия «больше или равно» для всех значений аргументов. Если же некоторые из значений аргументов первого набора больше или равны, а другие меньше значений тех же аргументов второго набора, то такие наборы называются несравнимыми. Например, набор 1101 (х1=1,x2=1,x3 =0, x4=1) больше набора 1100 (х1=1,x2=1,x3 =0, x4=0), так как на этих наборах значения аргументов х1, x2, x3 равны, а значение аргумента x4 на первом наборе больше, чем на втором. Аналогично можно проверить выполнение следующих не-
равенств: 01101 >01000; 1011> 1000.
Два набора аргументов х1, x2, x3, x4, имеющих значения 1010 и 0110, несравнимы, так как значение аргумента х1 больше на первом наборе, а аргумента x2— на втором. Приведем еще несколько примеров несрав-
нимых наборов: 01 и 10; 100 и 001; 1110 и 1001.
Определение 1.4.5. Переключательная функция называется моно-
тонной, если при любом возрастании набора значения этой функции не убывают.
Например, для функций двух аргументов (см. табл. 1.4), учитывая, что наборы 01 и 10 несравнимы, найдем, что функции fo(x, у), f1(x, у}, f3(x, у) монотонны.
Функция f2(x, у) немонотонна, так как на наборе 10 она равна единице, а на большем наборе 11—нулю; f4(x, у) имеет немонотонность при переходе от набора 01 к набору 11.
Функция f5(x, y)—монотонная функция, хотя на первый взгляд может показаться, что она немонотонна, так как в таблице ее значений есть переход от единицы к нулю. Однако этот переход существует на несравнимых наборах 01 и 10, а для любой пары сравнимых наборов условие монотонности выполняется.
14
Самодвойственные переключательные функции. Для определения самодвойственных функций введем понятие противоположных наборов.
Определение 1.4.6. Два набора аргументов называются противо-
положными если все значения аргументов одного набора противоположны значениям аргументов другого набора.
Чтобы получить противоположный набор, достаточно заменить в данном наборе нули единицами, а единицы—нулями. Приведем примеры противоположных наборов: 101100 и 010011; 1111 и 0000; 10101 и 01010.
В общем случае два противоположных набора можно записать следующим образом: х1, х2, х3, ..., xn и x1, x2 x3...xn
Определение 1.4.7. Переключательная функция называется само-
двойственной, если на каждой паре противоположных наборов она принимает противоположные значения, т. е. если выполняется условие
f (x1, x2 ,..., xn ) = f (x1, x2 ,..., xn )
или, что то же самое
f (x1, x2 ,..., xn ) = f (x1, x2 ,..., xn ).
Найдем самодвойственные переключательные функции двух аргументов в табл. 1.4. Эта таблица содержит две пары противоположных наборов: 0,0 и 1,1; 0,1 и 1,0. Следовательно, самодвойственные функции должны иметь противоположные значения в первом-четвертом и втором-третьем столбцах значений аргументов.
В табл. 1.6 принадлежность функции тому или иному классу помечена звездочкой в соответствующем столбце.
Теорема о функциональной полноте.
Определение 1.4.8. Система переключательных функций называ-
ется функционально полной, если с помощью функций, входящих в эту систему, применяя операции суперпозиции и подстановки, можно получить любую, сколь угодно сложную переключательную функцию.
Теорема о функциональной полноте. Для того чтобы система пе-
реключательных функций была функционально полной, необходимо и достаточно, чтобы эта система включала:
•хотя бы одну переключательную функцию, не сохраняющую нуль;
•хотя бы одну переключательную функцию, не сохраняющую единицу;
•хотя бы одну нелинейную переключательную функцию:
•хотя бы одну немонотонную переключательную функцию;
•хотя бы одну несамодвойственную переключательную функцию.
15