С.Н. Селезнева - Основы дискретной математики, страница 7

В этом случае один элемент частично-упорядоченного множества всегда образует цепь длины 0.Определение 3.17. Длиной конечного частично упорядоченного множества называется длина максимальной цепи в нем.Определение 3.18. Множество элементов D частично упорядоченногомножества (A; ≤) назовем антицепью, если все они попарно не сравнимы.10Гельмут Хассе (Hasse) – немецкий математик XX века.39Определение 3.19.

Шириной конечной антицепи в частично-упорядоченном множестве называется число, равное ее мощности. Один элементчастично упорядоченного множества всегда образует антицепь ширины 1.Определение 3.20. Шириной конечного частично упорядоченного множества называется ширина максимальной антицепи в нем.Теорема 3.4 (Дилуорс11 ).

Ширина конечного частично упорядоченного множества равна минимальному числу цепей, на которое можноразбить это множество.3.6УпражненияЗадача 3.16. Пусть A – множество студентов некоторой группы. Является ли бинарное отношение R на множестве A частичным порядком?Если да“, является ли этот порядок линейным?”1) R – множество пар студентов, фамилия первого из которых располагается по алфавиту не позже фамилии второго;2) R – множество пар студентов, сумма вступительных баллов первого из которых не меньше суммы вступительных баллов второго.Задача 3.17.

Пусть A – множество месяцев года. Является ли бинарноеотношение R на множестве A частичным порядком? Если да“, является”ли этот порядок линейным?1) R – множество пар месяцев, первый из которых идет в календарене позже второго;2) R – множество пар месяцев одного времени года.Задача 3.18. Определяется ли отношением частичного порядка1)2)3)4)турнирная таблица участников соревнований;список студентов группы по алфавиту;распределение станций метрополитена по веткам;распределение местности на зоны пригородного сообщения?Задача 3.19.

Пусть A – множество точек на прямой с заданным направлением. Является ли бинарное отношение R на множестве A частичнымпорядком? Если да“, является ли этот порядок линейным?”11Роберт Палмер Дилуорс (Dilworth) – американский математик XX века.401) R – множество пар точек, вторая из которых расположена на прямой правее первой или совпадает с ней;2) R – множество пар точек, расстояние между которыми равно единичному отрезку.Задача 3.20. Является ли бинарное отношение R на множестве A частичным порядком? Если да“, является ли этот порядок линейным?”1) A – множество натуральных чисел, R – множество пар натуральныхчисел, первое из которых является делителем второго;2) A – множество целых чисел, R – множество пар целых чисел, разность которых делится на m, где m ≥ 1 – заданное натуральное число.Задача 3.21.

Пусть A = {1, 2, 3} – подмножество множества натуральных чисел. Является ли бинарное отношение R на множестве A2 частичным порядком? Если да“, является ли этот порядок линейным?”1) R = {((x1 , y1 ), (x2 , y2 )) ∈ (A2 )2 | x1 ≤ x2 , y1 ≤ y2 };2) R = {((x1 , y1 ), (x2 , y2 )) ∈ (A2 )2 | x1 + y1 ≤ x2 + y2 };3) R = {((x1 , y1 ), (x2 , y2 )) ∈ (A2 )2 | (x1 , y1 ) = (x2 , y2 )или x1 + y1 < x2 + y2 };4) R = {((x1 , y1 ), (x2 , y2 )) ∈ (A2 )2 | (x1 , y1 ) = (x2 , y2 )или |y1 − x1 | < |y2 − x2 |}.Для частичных порядков построить диаграмму Хассе, найти минимальные, максимальные, наименьший и наибольший (если они есть) элементы.Задача 3.22.

Пусть A – конечное множество. Доказать, что множествовсех его подмножеств P (A) является частично упорядоченным множеством относительно отношения ⊆. Найти его наименьший и наибольшийэлементы.Задача 3.23. 1. Доказать, что если в частично упорядоченном множестве есть наименьший (наибольший) элемент, то он единственный.2. Доказать, что если в частично упорядоченном множестве есть наименьший (наибольший) элемент, то он является единственным минимальным (максимальным) элементом этого частично упорядоченногомножества.41Задача 3.24. Доказать, что если R(2) ⊆ A2 – иррефлексивное и транзитивное отношение на множестве A, то отношениеR0 = R ∪ {(x, x) | x ∈ A}является частичным порядком на множестве A.Задача 3.25.

Пусть R(2) ⊆ A2 – бинарное отношение на множестве A.Доказать, что отношение R является одновременно и отношением эквивалентности, и отношением частичного порядка на множестве A, если итолько еслиR = {(x, x) | x ∈ A}.3.7Булев кубОпределение 3.21. Булевым12 множеством назовем множество B ={0, 1}.На множестве B введем линейный порядок ≤: 0 < 1.Определение 3.22.

n-мерным булевым кубом ( где n ≥ 1 – натуральноечисло) назовем множество B n с частичным порядком ≤n .Обозначение:B n = {(a1 , . . . , an ) | ai ∈ B, i = 1, . . . , n} – n-мерный булев куб.(B n ; ≤) – n-мерный куб B n – частично упорядоченное множество.Если α = (a1 , . . . , an ), β = (b1 , .

. . , bn ) ∈ B n , то α ≤ β, если ai ≤ bi привсех i = 1, . . . , n.В частично упорядоченном множестве (B n ; ≤) есть наименьший элемент: (0, . . . , 0) ∈ B n , и наибольший элемент: (1, . . . , 1) ∈ B n .Определение 3.23. Наборы из B n будем называть точками n-мерногобулева куба.Определение 3.24. Весом набора α = (a1 , . . . , an ) ∈ B n назовем числоединиц в нем.Обозначение:nP|α| =ai – вес набора α ∈ B n .i=112Джорж Буль (Boole) – английский математик и логик XIX века.42Определение 3.25. k-м слоем куба B n (0 ≤ k ≤ n) назовем подмножество всех его наборов веса k.Обозначение:Bkn = {α ∈ B n | |α| = k} – k-й слой куба B n .Теорема 3.5.

Мощность k-го слоя (0 ≤ k ≤ n) куба B n равна Cnk , тоесть |Bkn | = Cnk .Определение 3.26. Номером набора α = (a1 , . . . , an ) ∈ B n назовем число, которое в двоичной системе счисления записывается как a1 a2 . . . an .Обозначение:nPν(α) =ai · 2n−i – номер набора α ∈ B n .i=1Определение 3.27. Расстоянием (по Хэммингу13 ) между наборами α =(a1 , . . . , an ) и β = (b1 , . . .

, bn ) куба B n назовем число координат, в которых они различаются.Обозначение:nPd(α, β) =|ai − bi | – расстояние между наборами α и β из куба B n .i=1Определение 3.28. Соседними (по i-й координате) назовем наборы, которые отличаются только в одной (i-й) координате.α, β ∈ B n – соседние наборы, если d(α, β) = 1.Соседние наборы всегда сравнимы. Если α, β ∈ B n – соседние наборыи α ≤ β, то α l β.Определение 3.29. Противоположными назовем наборы, которые отличаются во всех координатах.α, β ∈ B n – противоположные наборы, если d(α, β) = n.Теорема 3.6.

Длина куба B n равна (n + 1).bncТеорема 3.7. Ширина куба B n равна Cn 2 .Теорема 3.8. Ширина куба B n достигается1) при четных n только на множестве всех наборов среднего слоя B nn ;22) при нечетных n только на каждом из множеств всех наборовдвух средних слоев B nn−1 и B nn+1 .2132Ричард Уэсли Хэмминг (Hamming) – американский математик XX века.433.8УпражненияЗадача 3.26.

1. Найти веса следующих наборов α ∈ B n :1) α = (110) ∈ B 3 ;2) α = (111) ∈ B 3 ;3) α = (0101) ∈ B 4 ;4) α = (10111) ∈ B 5 .2. Перечислить все наборы, принадлежащие слою1) B03 ;2) B23 ;3) B24 ;4) B45 .Задача 3.27. 1. Найти номера следующих наборов α ∈ B n :1) α = (010) ∈ B 3 ;2) α = (111) ∈ B 3 ;3) α = (1001) ∈ B 4 ;4) α = (10110) ∈ B 5 .2. Найти наборы α ∈ B n по их номерам ν(α):1) α ∈ B 3 , ν(α) = 5;2) α ∈ B 4 , ν(α) = 5;3) α ∈ B 4 , ν(α) = 12;4) α ∈ B 5 , ν(α) = 21.Задача 3.28. 1.

Найти все соседние и противоположные наборы к следующим наборам α ∈ B n :1) α = (000) ∈ B 3 ;2) α = (010) ∈ B 3 ;3) α = (1110) ∈ B 4 ;4) α = (00110) ∈ B 5 .2. Найти все наборы, отстоящие на расстояние d от следующих наборов α ∈ B n :1) α = (100) ∈ B 3 , d = 1;2) α = (111) ∈ B 3 , d = 2;3) α = (0101) ∈ B 4 , d = 2;4) α = (10011) ∈ B 5 , d = 5.Задача 3.29. 1.

Найти количество наборов из B n , соседних с заданнымнабором α ∈ B n .2. Найти количество наборов из B n , отстоящих от заданного набораα ∈ B n на расстояние d, 0 ≤ d ≤ n.Задача 3.30. 1. Доказать, что количество максимальных цепей куба B nравно n!2. Доказать, что количество максимальных цепей куба B n , содержащих набор α ∈ Bkn , равно k! · (n − k)!bnc3. Доказать, что ширина куба B n не меньше, чем Cn 2 .4. Доказать, опираясь на п.п.

1-2 и теорему 3.4, что ширина куба B nbncне больше, чем Cn 2 .44Задача 3.31. Доказать, что у куба B n1) при четных n есть только одна максимальная антицепь – среднийслой B nn ;22) при нечетных n есть только две максимальные антицепи – два средних слоя B nn−1 и B nn+1 .22Задача 3.32. Разбить на минимальное число цепей куб1) B 1 ;2) B 2 ;3) B 3 ;4) B 4 .Задача 3.33. Построим по индукции следующее разбиение куба B nна цепи.Базис индукции.

Куб B 1 разобьем на одну цепь C1 = {(0), (1)}.Индуктивный переход. Пусть куб B n уже разбит на цепи. Разбиениекуба B n+1 устроим следующим образом. Пусть C – произвольная цепьразбиения куба B n и α = (a1 , . . . , an ) – ее максимальный элемент. Включим две цепи C 0 и C 00 в разбиение куба B n+1 :C 0 = {β ∈ B n+1 | β = (0, b1 , . . . , bn ), где (b1 , . . . , bn ) ∈ C илиβ = (1, a1 , . . . , an )};C 00 = {β ∈ B n+1 | β = (1, b1 , . .