Связь свойств нормальных функций выбора со свойствами соответствующих бинарных отношений

Обратите внимание на следующие факты:
1. Для нормальных функций выбора выполняются свойства наследования и согласия.
2. Двойственность механизмов предпочтения и блокировки.
3. Механизм предпочтения обычно использует в качестве структуры рефлексивное отношение.
4. Механизм блокировки обычно использует в качестве структуры антирефлексивное отношение.

Свойства вариантов, связываемых ациклическими отношениями

1. Варианты можно разделить на 4 категории:
а) изолированные варианты;
б) лучшие варианты;
в) худшие варианты;
г) промежуточные варианты.
2. Из каждого варианта категорий в) и г) существует маршрут к какому либо из лучших вариантов.
3. Для качественного порядка: из каждого варианта категорий в) и г) обязательно существует дуга к какому либо из лучших вариантов.
4. Для слабого порядка: из каждого варианта нижних слоев обязательно существует дуга к каждому варианту любого вышележащего слоя.
5. Для строгого порядка: каждый слой содержит ровно один вариант.

Рекомендации для самостоятельной работы

В доказываемых далее утверждениях (п.2-5) предполагается следующее:
1. Применяется механизм попарных блокировок и используется антирефлексивное отношение.
2. Выполняются свойства наследования и согласия.

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

Условия непустого выбора

Для того, чтобы механизм блокировки при любом предъявлении обеспечивал непустой выбор, необходимо и достаточно ацикличности отношения R. (Непустой выбор <=> ациклическое отношение)

Необходимоcть: (непустой выбор => АЦ)

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

Достаточное условие непустого выбора

Достаточность: (АЦ => непустой выбор)

1. Для любого предъявления соответствующая часть отношения остается ациклической.
2. Для ациклического отношения: из каждого промежуточного варианта (и худшего тоже!) существует маршрут к какому-нибудь из лучших вариантов.
3. В графе без циклов любой маршрут имеет конечную точку, конечная точка является мажорантой, поэтому выбор не пуст.

Выполнение свойства отбрасывания

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

(Свойства Н, С, О, непустой выбор <=> R есть Качественый порядок)

Необходимоcть: (Н,С,О => Т,АЦ)

Возьмем произвольные 3 варианта, которые обозначим как x, y, z . Для предъявлений, составленных из этих вариантов, рассмотрим таблицы всех различных функций выбора, удовлетворяющих свойствам Н,С,О.

Доказательство необходимого условия выполнения свойства О для нормальных функций непустого выбора (Н,С,О => Т + АЦ)

(Функция в каждой строке определяется ее первой точкой и свойствами, которые не заключены в скобки. Тогда свойства, указанные в скобках, выполняются автоматически. Свойства отмеченные знаком "?" , выполняются, если вариант, указанный в круглых скобках выбирается лишь в одном предъявлении.)

Доказательство достаточного условия выполнения свойства О для нормальных функций непустого выбора (Т + АЦ => Н,С,О)

Рассмотрим произвольное предъявление. Отношение между вариантами этого предъявления сохраняет свойства Т и АЦ, то есть остается качественным порядком.

Качественный порядок (свойства Т+АЦ) характеризуется графом, в котором от каждого промежуточного (а также "худшего") варианта идет дуга к какому-нибудь "лучшему" варианту.

Поэтому отбрасывание каких-либо отвергнутых вариантов не может удалить подобных дуг из оставшихся неотвергнутых вариантов, а поэтому множество лучших вариантов остается неизменным.

Иллюстрация доказательства достаточного условия

Выполнение свойства константантности

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

Свойства (Н, С, О,) К, непустой выбор <=> Слабый порядок

Необходимоcть: (К,Н,С,О => НТ,АЦ)

Доказательство необходимого условия выполнения свойства К для нормальных функций непустого выбора (К,Н,С,О => НТ + АЦ)

Доказательство достаточного условия выполнения свойства К для нормальных функций непустого выбора (НТ + АЦ => Н,С,О,К)

Рассмотрим произвольное предъявление. Отношение между вариантами этого предъявления сохраняет свойства НТ и АЦ, то есть остается слабым порядком.

Слабый порядок (свойства НТ+АЦ) характеризуется графом, в котором к каждому лучшему варианту идет дуга от каждого промежуточного и худшего варианта (т.е. от всех вариантов нижних слоев).

Поэтому переход к частичному предъявлению, содержащему хотя бы один вариант верхнего слоя, не приведет к перемещению вариантов на более высокий слой, и свойство К оказывается выполненным.

Иллюстрация доказательства достаточного условия (НТ + АЦ => Н,С,О,К)

Условия одноэлементного выбора

Для того, чтобы механизм блокировки обеспечивал одноэлементный выбор, необходимо и достаточно ацикличности и слабосвязности отношения R.

Одноэлементный выбор, свойства Н=О=К <=> Строгий порядок

Необходимоcть: (Одноэлементный выбор [Н=О=К,С] => СП,АЦ)

Рассмотрим только все попарные предъявления. Так как при этом всегда выбирается один вариант, то к выбранному варианту идет дуга от невыбранного. Поэтому отношение является слабосвязным.

Доказательство достаточного условия одноэлементнго выбора (СП + АЦ => Н=О=К ,С)

Одноэлементность выбора вытекает из того, что каждый слой (в т.ч. и слой лучших вариантов) содержит ровно один элемент.

Выполнение свойств Н, О, К вытекает из предыдущего рассмотрения.

Их равенство является свойством функций одноэлементного выбора.

Выводы

"3.6. Модели итоговых характеристик ИО" - тут тоже много полезного для Вас.

Связь свойств механизма попарных блокировок со свойствами бинарных отношений

Свойства наследования и согласия выполняются.

Связь свойств механизма попарных предпочтений со свойствами бинарных отношений

Используется двойственность механизмов блокировок и предпочтений.

Поделитесь ссылкой:

Популярные услуги

Связь свойств нормальных функций выбора со свойствами соответствующих бинарных отношений

Рекомендуемые материалы

Рекомендуемые лекции