Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Топ:
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Интересное:
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Дисциплины:
2022-10-04 | 223 |
5.00
из
|
Заказать работу |
|
|
Пусть задано множество , 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. ЛФВ (С), представляющая семейство функций , построена.
|
|
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!