МОНОТОННЫЕ ФУНКЦИИ

На множестве двоичных наборов длины n определим отношение предшествования наборов.

Пусть и . Тогда набор предшествует набору , если .

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

Например, наборы (0, 1, 0, 0, 1, 0) и (0, 1, 1, 0, 1, 1) находятся в отношении предшествования, а наборы
(1, 1, 0, 0, 1, 0) и (1, 0, 1, 0, 1, 1) оказываются несравнимыми в отношении .

 

Упражнение. Проверить, что отношение предшествования наборов является отношением частичного порядка.

Рассмотрим представление отношения на множестве с помощью диаграммы для этого отношения, представленной на рис 4.6. Пусть n = 3.

1 1 1

 
 

 

 


0 1 1 1 0 1 1 1 0

 

 

1 0 0 0 1 0 0 0 1

 

 

0 0 0

Рис. 4.6

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

Все наборы единичного n-мерного куба, имеющие равное число единиц, несравнимы между собой и образуют слой в таком кубе. В случае произвольного значения n в диаграмме для отношения содержится n +1 слоев.

 

Упражнение. Нарисовать диаграмму отношения для
n = 4.








Дата добавления: 2015-09-18; просмотров: 583;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.003 сек.