Лекции Просолупов

b) Пусть ( 1, ..., ) 0 и ( 1, ..., ) 0 и

( 1, ..., −1, +1, ..., , 1, ..., ) =

= ( 1, ..., −1, ( 1, ..., ), +1, ..., ).

Тогда

(0, ..., 0) = (0, ..., 0, (0, ..., 0), 0, ..., 0) = (0, ..., 0, 0, 0, ..., 0) = 0.

Получаем, что ( 1, ..., −1, +1, ..., , 1, ..., ) 0. Таким образом, [ 0] = 0.

Замечание 41.3 . Тождественная функция ( ) = лежит в классе 0. Функция отрицания ( ) = не лежит в 0. Таким образом, 0 ̸= ? и 0 ̸= 2.

§42. Функции, сохраняющие единицу

Замечание 42.1 . Рассуждения этого пункта повторяют содержание предыдущего с точностью до замены 0 на 1

Определение 42.2 . Пусть ( 1, ..., ) 2. называют функцией, сохраняющей единицу, если (1, ..., 1) = 1.

Множество всех функций сохраняющих 1 обозначим 1:

1 = { ( 1, ..., ) | 2, (1, ..., 1) = 1}.

Утверждение 42.3 . Класс функций 1 замкнут.

Доказательство. Доказательство полностью эквивалентно доказательству утверждения 41.2.

Замечание 42.4 . Тождественная функция ( ) = лежит в классе 1. Функция отрицания ( ) = не лежит в 1. Таким образом, 1 ̸= ? и 1 ̸= 2.

91

Лекция 14. Самодвойственные и монотонные функции

§43. Двойственность

Определение 43.1 . Пусть ( 1, ..., ) 2. Двойственной функцией к функцииназывается *( 1, ..., ) = ( 1, ..., ).

Пример 43.2 . Пусть ( , , ) = . Тогда *( , , ) = · = · .

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

Обозначим за множество всех самодвойственных функций:

= { | ( 1, ..., ) 2, *( 1, ..., ) = ( 1, ..., )}.

Пример 43.5 . Пусть = , * = = . ̸= * и, следовательно, * не является самодвойственной.

Пример 43.6 . Пусть — функция голосования:

( , , ) = .

*( , , ) = · · · = · · · · · =

=( )( )( ) = ( )( ) =

= =

= = ( , , ).

Функция голосования — самодвойственная.

92

Рассмотрим табличный вид функции голосования:

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

Тогда, по определению двойственной функции

*( 1, ..., ) = ( 1( 1 , ..., 1 ), ..., ( 1 , ..., )) =

= ( 1( 1 , ..., 1 ), ..., ( 1 , ..., )) =

= ( *1( 1 , ..., 1 ), ..., * ( 1 , ..., )) = = *( *1( 1 , ..., 1 ), ..., * ( 1 , ..., )).

С другой стороны, формула *( 1*, ..., *) реализует функцию

Таким образом, один из способов задать функцию *( 1, ..., ) формулой имеет вид * = *( 1*, ..., *).

Пример 43.8 . Пусть,

( , , ) = ( ≡ ) ( | ) = ( 1( , ), 2( , )).

93

*( , ) =( )* = = = .1*( , ) =( ≡ )* = ≡ = ≡ = .

2*( , ) =( | )* = | = = = ↓ .

Тогда по утверждению 43.7 *( , , ) будет иметь вид

*( , , ) = *( 1*( , ), 2*( , )) = ( ) ( ↓ ).

Действительно,

*( , , ) = ¬(( ≡ ) ( | )) = ¬(( ≡ ) ( )) =

=( ≡ ) ( ) = ( ) ( ↓ ).

Доказательство. Пусть = ¬ 1. Это значит, что = 0( 1), где 0( ) = . Тогда

0* = = = 0. Следовательно

* = 0*( 1*) = 0( 1*) = ¬ 1*.

Пусть = 1 2. Другими словами, = 0( 1, 2), 0( , ) = . Тогда

0* = = и

* = 0*( 1*, 2*) = 1* 2*.

Пусть = 1 2. Другими словами, = 0( 1, 2), 0( , ) = . Тогда

0* = = и

* = 0*( 1*, 2*) = 1* 2*.

Пусть = 0. Тогда * = 1. Пусть = 1. Тогда * = 0.

Пусть = . Тогда * = = = .

Пример 43.10 . Пусть, ( , , ) = 0 1 . Тогда,

*( , , ) = ( , , ) = ¬(0 1 ) =

=(0 ) (1 ) = (1 ) (0 ).

Пример подтверждает утверждение 43.9.

94

Пример 43.11 . Пусть, ( , , ) = (0 )( ). Тогда

*( , , ) = ¬((0 )( )) = ¬(1 )( )) =

=(1 ) ( )) = (1 ) ( ( ))).

Пример подтверждает утверждение 43.9.

Утверждение 43.12 . Класс функций замкнут.

Доказательство. Рассмотрим суперпозицию ранга 1 от функций из . a) Пусть

( 1, ..., ) и( 1, ..., −1, +1, ..., , ) = ( 1, ..., −1, , +1, ..., ).

Тогда

( 1, ..., −1, +1, ..., , ) = ( 1, ..., −1, , +1, ..., ) = = *( 1, ..., −1, , +1, ..., ) = ( 1, ..., −1, , +1, ..., ) = = ( 1, ..., −1, +1, ..., , ).

Следовательно ( 1, ..., −1, +1, ..., , ) . b) Пусть ( 1, ..., ) и ( 1, ..., ) и

( 1, ..., −1, +1, ..., , 1, ..., ) =

= ( 1, ..., −1, ( 1, ..., ), +1, ..., ).

Тогда

( 1, ..., −1, +1, ..., , 1, ..., ) =

=( 1, ..., −1, ( 1, ..., ), +1, ..., ) =

=( 1, ..., −1, ( 1, ..., ), +1, ..., ) =

=( 1, ..., −1, *( 1, ..., ), +1, ..., ) =

=*( 1, ..., −1, *( 1, ..., ), +1, ..., ) =

=( 1, ..., −1, ( 1, ..., ), +1, ..., ) =

=( 1, ..., −1, +1, ..., , 1, ..., )

Получаем, что ( 1, ..., −1, +1, ..., , 1, ..., ) . Таким образом, [ ] = .

Замечание 43.13 . Тождественная функция ( ) = лежит в классе . Конъюнкция ( ) = не лежит в . Таким образом, ̸= ? и ̸= 2.

Лемма 43.14 (О несамодвойственной функции). Пусть ( 1, ..., ) / . Тогда, подставляя в вместо аргументов и можно получить константу.

95

Доказательство. Пусть ( 1, ..., ), {0, 1}, такой набор, что ( 1, ..., ) =( 1, ..., ). Такой набор обязан существовать в силу несамодвойственности функции .

Рассмотрим функцию ( ) = ( 1 , ..., ). Тогда

(0) = (0 1 , ..., 0 ) = ( 10, ..., 0) = ( 1, ..., ) =

= ( 1, ..., ) = (1 1 , ..., 1 ) = (1).

Следовательно ( ) — константа.

Пример 43.15 (получение константы из несамодвойственной функции).

Пусть ( , , ) = ( ). Это несамодвойственная функция, поскольку

(0, 1, 0) = 0 (1 0) = 1 = 1 (0 1) = (1, 0, 1).

Тогда ( ) = ( , , ) — константа. Действительно,

( ) = ( ) = 1 = 1.

Будем говорить, что ̃ непосредственно предшествует ̃ и обозначать ̃ ′̃ , если ̃ ̃ и не существует набора ̃ такого, что ̃ ̃ ̃ .

Замечание 44.2 . , — отношения частичного порядка.

функций будем обозначать .

Пример 44.4 . Функция является монотонной. Функция — не монотонна.

Утверждение 44.5 . Класс функций замкнут.

96

Доказательство. Рассмотрим суперпозицию ранга 1 от функций из . a) Пусть

( 1, ..., ) и

( 1, ..., −1, +1, ..., , ) = ( 1, ..., −1, , +1, ..., ).

Тогда монотонность непосредственно следует из монотонности функции . b) Пусть ( 1, ..., ) и ( 1, ..., ) и

( 1, ..., −1, +1, ..., , 1, ..., ) =

= ( 1, ..., −1, ( 1, ..., ), +1, ..., ).

Пусть ̃ + −1 ̃ + −1. Тогда, в частности,

( , ..., + −1) ( , ..., + −1).

Поскольку монотонна, то

( , ..., + −1) ≤ ( , ..., + −1)

и, следовательно,

( 1, ..., −1, ( , ..., + −1), , ..., −1)

( 1, ..., −1, ( , ..., + −1), , ..., −1).

Таким образом, из монотонности следует, что

(̃ + −1) = ( 1, ..., −1, ( , ..., + −1), , ..., −1) ≤

≤ ( 1, ..., −1, ( , ..., + −1), , ..., −1) = (̃ + −1).

Получаем, что ( 1, ..., −1, +1, ..., , 1, ..., ) . Таким образом, [ ] = .

Замечание 44.6 . Тождественная функция ( ) = лежит в классе . Функция отрицания ( ) = не лежит в . Таким образом, ̸= ? и ̸= 2.

97

и

̃ = ( 1, ..., −1, 1, +1, ..., ).

Определим функцию ( ) следующим образом:

( ) = ( 1, ..., −1, , +1, ..., ).

Тогда:

(0) = ( 1, ..., −1, 0, +1, ..., ) = 1(1) = ( 1, ..., −1, 1, +1, ..., ) = 0.

То есть ( ) = , что и требовалось доказать.

b) Пусть теперь > 1. В этом случае построим последовательность наборов

̃ = ̃ (0) ̃ (1) ... ̃ ( − 1) ̃ ( ) = ̃ ,

где каждая пара наборов ̃ ( −1) и ̃ ( ) отличаются только в одной позиции, = 1, .

Это не трудно сделать, последовательно заменяя каждую позицию, в которой наборы̃ и ̃ различаются с нуля на единицу. Поскольку (̃ ) = 1 и (̃ ) = 0, найдется

такое , что ̃ ( − 1) = 1 и ̃ ( ) = 0. Такая ситуация возвращает нас к пункту )

доказательства.

Пример 44.8 . (Построение с помощью немонотонной функции) Пусть

( , , ) = ( ). Эта функция немонотонна, так как

(0, 0, 0) = 0 (0 0) = 1 > 0 = 1 (1 1) = (1, 1, 1).

Рассмотрим последовательность наборов

(0, 0, 0) (0, 0, 1) (0, 1, 1) (1, 1, 1)

и значения функции на этих наборах

1 = (0, 0, 0) = (0, 0, 1) = (0, 1, 1) > (1, 1, 1) = 0.

Тогда ( ) = ( , 1, 1) = . Действительно,

( ) = (1 1) = 0 = .

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

Пример 44.9 . Пусть ( , , ) = ( )| . На рисунке 13 представлена схема

отношения предшествования с указанием значения функции для каждого набора. Из рисунка видно, что в качестве соседних наборов, на которых нарушается монотонность можно выбрать, например, (1, 0, 0) и (1, 0, 1). Тогда, согласно лемме о немонотонной функции нужно выбрать функцию

( ) = (1, 0, ) = (0 0)| = 1| = .

98

(1,1,1)

(0,0,0)

Рисунок 12: Схема бинарного отношения предшествования наборов для = 3

f(0,0,0)=1

Рисунок 13: Отображение значений функции на схеме отношения предшествования наборов

99

Лекция 15. Линейные функции, критерий полноты

§45. Линейность

Определение 45.1 . Пусть ( 1, ..., ) 2. Функция — линейная, если ее

полином Жегалкина имеет вид

( 1, ..., ) = 0 1 1 2 2 ... .

Обозначим — класс всех линейных функций.

Пример 45.2 . — линейная функция. Функция не является линейной.

Утверждение 45.3 . Класс функций замкнут.

Доказательство. Рассмотрим суперпозицию ранга 1 от функций из . a) Пусть

( 1, ..., ) и

( 1, ..., −1, +1, ..., , ) = ( 1, ..., −1, , +1, ..., ).

Если

( 1, ..., ) = 0 1 1 2 2 ... ,

то

( 1, ..., −1, +1, ..., , ) = = 0 1 1 ... −1 −1 +1 +1 ... .

Следовательно ( 1, ..., −1, +1, ..., , ) . b) Пусть ( 1, ..., ) и ( 1, ..., ) и

( 1, ..., −1, +1, ..., , 1, ..., ) =

= ( 1, ..., −1, ( 1, ..., ), +1, ..., ).

Пусть

( 1, ..., ) = 0 1 1 2 2 ...

и

( 1, ..., ) = 0 1 1 2 2 ... .

Тогда

( 1, ..., −1, +1, ..., , 1, ..., ) = 0 1 1 ... −1 −1

( 0 1 1 ... ) +1 +1 ... =

=( 0 0) 1 1 ... −1 −1 +1 +1 ...

100