Операции над функциями выбора

Над функциями выбора определены следующие операции.

1. Объединением функций выбора  и  называется функция , определяемая формулой: , .

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

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

4. Произведением функций выбора  и  называется функция , определяемая формулой: , .

Теорема 1. Пусть 1) ; 2) ; 3) . Тогда для любого  справедливо:

1) ; 2) ; 3) .

Теорема 2. Пусть . Тогда

.

 

Классы функций выбора

В основу классификации функции выбора положены следующие условия.

1. Условие наследования (Н).

Функция выбора С удовлетворяет условию наследования, если из того, что , следует: .

2. Условие независимости от отвергнутых альтернатив (О).

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

3. Условие согласия (С).

Функция выбора С удовлетворяет условию согласия, если .

4. Условие Плотта (квазисумматорность) (КС).

Функция выбора С удовлетворяет условию квазисумматорности, если , .

5. Условие сумматорности (СМ).

Функция выбора С удовлетворяет условию сумматорности, если

, .

6. Условие мультипликаторности (МП).

Функция выбора С удовлетворяет условию мультипликаторности, если

, .

7. Условие монотонности (М).

Функция выбора С удовлетворяет условию монотонности, если

.

Функция выбора называется:

1. Рефлексивной, если =Æ, .

2. Антирефлексивной, если = , .

3. Полной, если Æ для всех , Æ.

4. Транзитивной, если из того, что

                                   Æ,

                                   Æ следует, что .

Легко проверить, что функция выбора из задачи №10 (см. упражнения к § 3) является антирефлексивной, полной, транзитивной.

 

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

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

Будем считать, что подмножества X множества W предъявляются для выбора последовательно: . Упорядоченность подмножеств связана с моментом предъявления данного множества.

Пусть  - результаты выборов, .

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

Динамическая функция выбора представляет собой конечный автомат, задаваемый множеством S состояний, множеством O входов и функцией переходов  : , ; - начальное состояние.

  Конечным автоматом, порожденным выбором, называется автомат, у которого множество состояний S есть множество всех возможных выборов из всех подмножеств , а множество входов – множество всех подмножеств  (т.е. ). Функция переходов F определяется выбором из X при условии, что предыдущим выбором было некоторое Y.

Способы задания динамической функции выбора

1. Таблица переходов.

o s	Æ	…
…

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

2. Диаграмма переходов.

Диаграмма переходов представляет собой граф, вершинами которого являются состояния. Вершины i, j связаны дугой, если возможен переход из состояния i в состояние j. Над дугой помечается, под действием каких входов данный переход возможен.

 

Упражнения к § 3

I. Основные упражнения

1. Пусть  - сужение отношения R, заданного на , на множество ;   - отношение двойственное к ;  - отношение двойственное к ;  - отношение двойственное к R;  - сужение  на X. Доказать, что .

2. Доказать, что функции выбора  и  связаны соотношениями: 1) ; 2) .

 3. Верно ли, что из того, что , следует, что ?

 4. Доказать, что произвольная функция выбора не обязательно является нормальной.

5. Рассмотрим . Для перечисленных ниже функций выбора C, заданных на , построить отношения ,  такие, что  или доказать, что таких ,  не существует:

1) , , ;

2) , =Æ, ;

3) ,   =Æ, .

6. Пусть  и задана функция выбора: Æ, , , , , , . Построить ЛФВ (С).

  7. Пусть  и задано семейство булевых функций: = ; , . Найти функцию выбора С.

  8. Для функции выбора  из задачи 6 и функции  из задачи 7 построить функции выбора:

1) ; 2) ; 3) ; 4) . Найти ЛФВ построенных функций.

  9. Пусть ,  - нормальные функции выбора. Доказать, что  - нормальная функция выбора.

10. Пусть . Для функции выбора С: , ,  проверить выполнение условий Н, О, С, КС, СМ, МП, М.

11. Пусть . Функция выбора описывается следующим образом:

если предъявляется x и предыдущий выбор не содержал x, то выбирается x, в противном случае выбор пуст; если предъявляется y и предыдущий выбор содержал y, то выбирается y, в противном случае выбор пуст; если предъявляется  и предыдущий выбор не был пуст, то выбирается y, в противном случае выбирается x. Задать функцию выбора: 1) таблицей;                                       2) диаграммой перехода.