Головна Головна -> Реферати українською -> Інформатика, комп'ютери, програмування -> Решітки

Решітки

Назва:
Решітки
Тип:
Реферат
Мова:
Українська
Розмiр:
12,42 KB
Завантажень:
15
Оцінка:
 
поточна оцінка 5.0


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2 
Серед частково впорядкованих множин винятково важливу роль відіграють так звані решітки або структури.

Точною верхньою гранню підмножини 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 < Rj, якщо кожен клас Ait, t=1,2,...,k розбиття Ri міститься в деякому класі Ajt розбиття Rj. Наприклад, для M ={1,2,3,4,5} розбиття R'={{1,2},{3},{4,5}} менше розбиття R''={{1,2,3},{4,5}} і менше розбиття R'''={{1,2},{3,4,5}}, а розбиття R'' і R''' непорівнювані.

Мінімальним елементом частково впорядкованої множини P є розбиття { {a} | aM}, а максимальним елементом - {M}. Тоді sup{Ri,Rj} = Rk, де Rk - розбиття, в якому елементи a,bM входять в один клас тоді і тільки тоді, коли існує такий cM, що кожна з пар елементів a і c та c і b належить одному класу або в Ri, або в Rj ; inf{Ri,Rj} = Rl, де Rl - розбиття, в якому елементи a,bM належать одному класу тоді і тільки тоді, коли вони належать одному класу і в Ri, і в Rj.

Наприклад,

sup{R'',R'''} = {{1,2,3,4,5}}, sup{R',R''} = {{1,2,3},{4, 5}},

inf{R'',R'''} = {{1,2},{3},{4,5}}, inf{R',R''} = {{1,2},{3},{4,5}}.

Оскільки за теоремою 1.10 існує взаємно одозначна відповідність між усіма розбиттями даної множини M і всіма відношеннями еквівалентності на M, то множина всіх відношень еквівалентності на M може бути перетворена в решітку.

Скінченну частково впорядковану множину M зручно зображати у вигляді діаграми або структурного графа, вершини якого відповідають елементам множини M. З вершини a проводимо стрілку у вершину b, якщо a  b і не існує такого c, що a  c і c  b. Стрілки (петлі), що відповідають діагональним парам (a,a) не проводимо.

Приклад 2. 1. На рис.1.6 зображено діаграми для чотирьох частково впорядкованих множин:

а) множини двійкових кортежів B3;

б) булеана  (M) множини M = {a,b,c} з відношенням включення ;

в) множини натуральних чисел C={2,5,7,10,28,70} з відношенням "ділить";

г) множини D={a,b,c,d} з відношенням часткового порядку R={(a,a),(b,b),(c,c), (d,d),(a,c),(b,c),(a,d), (b,d)}.

а) б) в) г)

Рис.1.

2. Діаграма будь-якої скінченної лінійно впорядкованої множини 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) для деякої пари елементів найменша верхня (або найбільша нижня) грань не існує.

Завантажити цю роботу безкоштовно
Пролистати роботу: 1  2 



Реферат на тему: Решітки

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок