Понятие функции выбора. Функции выбора, порожденные бинарными отношениями

Пусть задано множество , X – произвольное подмножество данного множества . Рассмотрим множество всех подмножеств  W: .

Функцией выбора называется отображение , ставящее в соответствие каждому  его подмножество .

C(Æ)=Æ, ситуация C(X)= Æ означает «отказ от выбора».

Предположим, что на множестве W задано бинарное отношение . Бинарное отношение порождает две наиболее важные в теории выбора функции: блокировку и предпочтение.

Функция выбора, определяемая на каждом подмножестве X множества W следующим образом:

,                          (1)

 называется блокировкой.

Функция выбора:

                            (2)

называется предпочтением.

Пусть R – бинарное отношение на W;  - его сужение на . Тогда  состоит из всех мажорант , а  - из всех максимумов, т.е. , .

В силу задачи №2 (см. упражнения к § 3) из двух функций выбора, порожденных бинарным отношением R, достаточно рассматривать только одну, так как блокировка по отношению R совпадает с предпочтением по отношению  и наоборот.

Функция выбора C называется нормальной, если существует бинарное отношение  такое, что  или .

Отметим, что если существует R: , то в силу задачи №2 существует такое, что  и наоборот.

Функция выбора   вложена в функцию выбора  (), если , .

Если  и неверно, что , то  строго вложена в ().

Пусть   - цепочка строго вложенных функций выбора.

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

Ближайшей к С сверху (снизу) называется функция выбора  () такая, что  () и не существует   () такой, что  ().

 

Примеры

1. В задаче №5 (см. упражнения): .

2.   В задаче № 5: - ближайшая сверху для ;

                                   - ближайшая снизу для ;

                                   не является ближайшей сверху для , так как .

Логические формы функций выбора

Рассмотрим конечное множество  : ;    – произвольное подмножество. Каждому подмножеству  () поставим в соотвестствие n-мерный вектор с компонентами 0 и 1 по формулам:                   

       , (3)

где      .

Отметим, что  (Æ)= (0,…,0); =(1,…,1).

 Логической формой функции выбора (ЛФВ (С)) называется упорядоченный набор булевых функций  от n-1 переменных:  , , построенных по следующему правилу:

           ,                 (4)

где ,

; .

Задание ЛФВ (С) эквивалентно заданию функции выбора С.

Замечание 1. Формула (4) означает, что .

То есть: если , что эквивалентно тому, что , то                         

        ;

         если , что эквивалентно тому, что  и,  

         следовательно, , то (4) верна для любого значения .

Алгоритм 1 (формирование ЛФВ (С)).

0. Задано множество ;  - множество всех подмножеств W, С- функция выбора, заданная на .

1. Для каждого подмножества  формируется n-мерный вектор  по формулам (3).

2. Для каждого подмножества  формируется n-мерный вектор , где

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

		…			…
0	0	…	0	0	…	0
…	…	…	…	…	…	…
1	1	…	1	1	…	1

Для определения значений  по формуле (4) в силу замечания 1 рассматриваем набор . Тогда =1 .

4. Формирование совершенных дизъюнктивных нормальных форм функций , :

.

5. ЛФВ (С), представляющая семейство функций , построена.