Обратите внимание на следующие факты:
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ть: (К,Н,С,О => НТ,АЦ)
Возьмем произвольные 3 варианта, которые обозначим как x, y, z . Для предъявлений, составленных из этих вариантов, рассмотрим таблицы всех различных функций выбора, удовлетворяющих свойствам Н,С,О,К.
Рассмотрим произвольное предъявление. Отношение между вариантами этого предъявления сохраняет свойства НТ и АЦ, то есть остается слабым порядком.
Слабый порядок (свойства НТ+АЦ) характеризуется графом, в котором к каждому лучшему варианту идет дуга от каждого промежуточного и худшего варианта (т.е. от всех вариантов нижних слоев).
Поэтому переход к частичному предъявлению, содержащему хотя бы один вариант верхнего слоя, не приведет к перемещению вариантов на более высокий слой, и свойство К оказывается выполненным.
Для того, чтобы механизм блокировки обеспечивал одноэлементный выбор, необходимо и достаточно ацикличности и слабосвязности отношения R.
Одноэлементный выбор, свойства Н=О=К <=> Строгий порядок
Необходимоcть: (Одноэлементный выбор [Н=О=К,С] => СП,АЦ)
Рассмотрим только все попарные предъявления. Так как при этом всегда выбирается один вариант, то к выбранному варианту идет дуга от невыбранного. Поэтому отношение является слабосвязным.
Одноэлементность выбора вытекает из того, что каждый слой (в т.ч. и слой лучших вариантов) содержит ровно один элемент.
Выполнение свойств Н, О, К вытекает из предыдущего рассмотрения.
Их равенство является свойством функций одноэлементного выбора.
Свойства наследования и согласия выполняются.
Используется двойственность механизмов блокировок и предпочтений.
