Переключательные функции, сохраняющие единицу.

Переключательные функции, сохраняющие нуль.

Пять классов переключательных функций. Теорема о функциональной полноте

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

К пяти замечательным классам переключательных функций относятся:

· линейные переключательные функции;

· переключательные функции, сохраняющие нуль;

· переключательные функции, сохраняющие еди­ницу;

· монотонные переключательные функции;

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

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

Линейные переключательные функции. В соответствии с теоремой Жегалкина любая переключательная функ­ция может быть представлена в виде многочлена (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) равна нулю, то говорят, что эта функция сохраняет нуль.

Для переключательных функций, сохраняющих нуль, выполняется следующее условие:

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, а для любой пары сравнимых наборов условие монотонности выполняется.

Самодвойственные переключательные функции. Для определения самодвойственных функций введем поня­тие противоположных наборов.

Определение 1.4.6. Два набора аргументов называются противоположными если все значения аргументов одного набора противоположны значениям аргументов другого набора.

Чтобы получить противоположный набор, достаточно заменить в данном наборе нули единицами, а едини­цы—нулями. Приведем примеры противоположных на­боров: 101100 и 010011; 1111 и 0000; 10101 и 01010.

В общем случае два противоположных набора можно записать следующим образом: х1, х2, х3, ..., xn и

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

или, что то же самое

.

Найдем самодвойственные переключательные функ­ции двух аргументов в табл. 1.4. Эта таблица содержит две пары противоположных наборов: 0,0 и 1,1; 0,1 и 1,0. Следовательно, самодвойственные функции должны иметь противоположные значения в первом-четвертом и втором-третьем столбцах значений аргументов.

В табл. 1.6 принадлежность функции тому или иному классу помечена звездочкой в соответствующем столбце.