2015-06-26
956
На множестве двоичных наборов длины 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.
