Реферат на тему:
Решітки
Серед частково впорядкованих множин винятково важливу роль відіграють
так звані решітки або структури.
Точною верхньою гранню підмножини A частково впорядкованої множини M
(позначається supA) називають найменшу з верхніх граней підмножини A.
Відповідно, точною нижньою гранню підмножини A частково впорядкованої
множини M (позначається infA) називають найбільшу з нижніх граней
підмножини A.
Частково впорядкована множина M називається решіткою (структурою), якщо
для будь-якої пари елементів a,b(M (тобто для будь-якої двоелементної
підмножини множини M ) існують sup{a,b} і inf{a,b}.
Приклад 1. 1. Будь-яка лінійно впорядкована множина M (наприклад,
числові множини N, Z, Q і R з традиційними відношеннями порядку) є
решіткою. Якщо a,b(M, то sup{a,b} = max(a,b) і inf{a,b} = min(a,b).
2. Розглянемо множину N натуральних чисел з відношенням часткового
порядку “ділить”. Для a,b(N означимо sup{a,b} = НСК(a,b) і inf{a,b) =
НСД(a,b) (НСК – найменше спільне кратне, НСД – найбільший спільний
дільник). Тоді sup{12,32 }=96, inf{12,32}= 4, inf{16,27}=1.
3. Частково впорядкована за відношенням включення множина ((M) всіх
підмножин множини M є решіткою: sup{A,B}=A(B і inf{A,B}= A(B, A,B(M.
4. Розглянемо множину R кортежів дійсних чисел довжини n з відношенням
часткового порядку, означеним у прикладі 1.17(4), тобто
(a1,a2,…,an)((b1,b2,…,bn) тоді і тільки тоді, коли ai(bi,
i=1,2,…n. Частково впорядкована у такий спосіб множина R є решіткою:
sup{(a1,a2,…,an),(b1,b2,…,bn)}=(c1,c2,…,cn), де ci = max(ai,bi),
i=1,2,…n, а inf{(a1,a2,…,an),( b1,b2,…,bn)} = (d1,d2,…,dn), де
di = min(ai,bi), i=1,2,…,n.
Аналогічно можуть бути перетворені на решітки множини кортежів Nn, Zn,
Qn і Bn, де B = {0,1 } – множина двійкових цифр.
Множина P = {R1,R2,…,Rm} всіх можливих розбиттів деякої скінченної
множини M може бути перетворена в решітку в такий спосіб. Вважаємо, що
розбиття Ri={Ai1,Ai2,…, Aik} і Rj={Aj1,Aj2,…,Ajk} знаходиться у
відношенні Ri
а) б) в) г)
Рис.1.
Діаграма будь-якої скінченної лінійно впорядкованої множини
M={a1,a2,...,an}, ai ( ai+1, i=1,2,...,n-1 має вигляд
a1 a2 a3 an-1 an
Неважко переконатись, що a(b, a,b(M тоді і тільки тоді, коли в діаграмі
частково впорядкованої множини M існує складений зі стрілок шлях, що
веде з вершини a у вершину b. Верхня грань для {a,b} - це елемент, в
який ведуть шляхи з a і з b. Нижня грань {a,b} - це елемент, з якого
існують шляхи і в a, і в b.
Частково впорядкована множина не є решіткою тоді, коли
1) деяка пара елементів не має верхньої або нижньої грані;
2) для деякої пари елементів найменша верхня (або найбільша нижня) грань
не існує.
Наприклад, перші дві множини B і ((M) з прикладу 1. є решітками, тому що
для їхніх діаграм не виконується жодна з наведених умов. Множина C не є
решіткою, оскільки, наприклад, для пар {2,5}, {5,7}, {7,10} не існують
нижні грані, а пари {10, 28} і { 28,70} не мають верхніх граней. Пара
елементів {a,b} ({c,d}) множини D має дві верхні (дві нижні) грані c і d
(відповідно a і b), однак не має найменшої верхньої (найбільшої нижньої)
грані, оскільки елементи c і d (a і b) непорівнювані між собою.
Частково впорядкована множина M називається повною решіткою, якщо для
будь-якої непорожньої підмножини A(M в множині M існують найменша верхня
грань sup A і найбільша нижня грань inf A. Очевидно, що довільна повна
решітка є решіткою, але не будь-яка решітка є повною решіткою. Якщо M -
повна решітка, то найменша верхня грань усієї множини M (sup M)
називається одиницею даної решітки і позначається 1, а найбільша нижня
грань множини M (inf M) називається нулем решітки і позначається 0.
Вибір цих назв для sup M і inf M пояснюється такими властивостями
елементів 1 і 0.
Для довільного елемента a(M виконується
sup {1,a} = 1, sup {0,a} = a, a ( 1,
inf {1,a} = a, inf {0,a} = 0, a (0.
(1.)
Очевидно, що елементи 0 і 1 є відповідно найменшим і найбільшим
елементами повної решітки M.
Приклад 1.21. 1. Решітки B, ((M) і P з прикладу 1.19 є повними
решітками. Одиницями цих решіток будуть відповідно (1,1,1), M і {M}, а
нулями - (0,0,0), ( і { {a} | a(M }.
2. Множина N натуральних чисел не є повною решіткою, оскільки будь-яка
її нескінченна підмножина на має найменшої верхньої грані.
Множина всіх дільників натурального числа n, частково впорядкована за
відношенням "ділить", є повною решіткою. Одиницею в такій решітці є
число n, а нулем - число 1.
(0,0,0)
(0,1,0)
(0,0,1)
(1,0,0)
(1,1,0)
(1,0,1)
(0,1,1)
(1,1,1)
(
{b}
{c}
{a}
{a,b}
{a,c}
{b,c}
{a,b,c}
a
b
c
d
2
70
5
7
28
10
Нашли опечатку? Выделите и нажмите CTRL+Enter
