Узагальнено булеві решітки

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Федеральне агентство з освіти

Державна освітня установа
вищої професійної освіти
Вятский державний гуманітарний університет

Математичний факультет

Кафедра алгебри та геометрії

Випускна кваліфікаційна робота

Узагальнено булеві решітки


Виконав:

студент V курсу математичного факультету

Онучин Андрій Володимирович

Науковий керівник:

к.ф.-м.н., доцент кафедри алгебри та геометрії ВятГГУ
Чермний Василь Володимирович

Рецензент:

д.ф.-м.н., професор, зав. кафедрою алгебри і геометрії ВятГГУ

Вечтомов Євген Михайлович

Робота допущена до захисту в державної атестаційної комісії

«___» __________2005 Р. Зав. кафедрою Є.М. Вечтомов

«___»__________ 2005 Декан факультету В.І. Варанкіна

Кіров

2005

Зміст

Вступ 3

Глава 1 Квітня

1.1. Впорядковані множини 4

1.2. Грати 5

1.3. Дистрибутивні решітки 7

1.4. Узагальнені булеві решітки, булеві грати 8

1.5. Ідеали 9

Глава 11 лютого

2.1. Конгруенції 11

2.2. Основна теорема 17

Бібліографічний список 27

Введення

Булева грати є класичний математичний об'єкт, який почав інтенсивно вивчатися в роботах М. Стоуна 30-ті роки 20-го століття, розширенням цього поняття до узагальнено булевих решіток займалися Г. Гретцер і Е. Шмідт у своїх працях кінця 50-х років.

Мета даної роботи: встановлення взаємно однозначної відповідності між конгруенції та ідеалами в узагальнено булевих гратах. (Для булевих решіток це положення доведено в книзі [2], крім того, сформульовано в книзі [3] в якості вправ). А також - встановлення зв'язку між узагальнено булевими гратами і булевими кільцями.

Дана дипломна робота складається з двох глав: в першому розділі дано основні поняття, а так само містяться базові відомості з теорії грат. Крім того, в першому розділі розглянуто кілька найпростіших теорем.

Другий розділ представляє собою основну частину даної дипломної роботи. Спираючись на роботи Гретцера Г., але більш докладно, розглянуті властивості конгруенції і зв'язок конгруенції та ідеалів в узагальнено булевих гратах (Теореми 2.1, 2.2, 2.3.). Крім того реалізована основна мета даної дипломної роботи: встановлено зв'язок між булевими кільцями і узагальнено булевими гратами (Основна теорема).

Глава 1

1.1. Впорядковані множини

Впорядкованим безліччю P називається непорожня безліч, на якому визначено бінарне відношення , Що задовольнить для всіх таким умовам:

1. Рефлексивність: .

2. Антисиметричність. Якщо і , То .

3. Транзитивність. Якщо і , То .

Якщо і , То говорять, що менше або більше , І пишуть або .

Приклади впорядкованих множин:

  1. Безліч цілих позитивних чисел, а означає, що ділить .

  2. Безліч всіх дійсних функцій на відрізку і означає, що для .

Ланцюгом називається упорядкований безліч, на якому для будь-яких має місце або .

Використовуючи відношення порядку, можна отримати графічне представлення будь-якого кінцевого упорядкованої множини P. Зобразимо кожен елемент множини P у вигляді невеликого гуртка, розташовуючи x вище y, якщо . З'єднаємо x і y відрізком. Отримана фігура називається діаграмою упорядкованої множини P.


Приклади діаграм упорядкованої множини:

1.2. Грати

Верхньої гранню підмножини Х в упорядкованому безлічі Р називається елемент a з Р, більший або рівний всіх x з X.

Точна верхня грань підмножини X впорядкованої безлічі P - це така його верхня грань, яка менше будь-який інший його верхній межі. Позначається символом sup   X і читається «Супремум X».

Згідно аксіомі антисиметричність упорядкованої множини, якщо точна верхня грань існує, то вона єдина.

Поняття нижньої межі і точної нижньої межі (яка позначається inf   X і читається «інфінум») визначаються двояко. Також, згідно аксіомі антисиметричність упорядкованої множини, якщо точна нижня грань X існує, то вона єдина.








Гратами називається упорядкований безліч L, в якому будь-які два елементи x і y мають точну нижню грань, що позначається , І точну верхню грань, що позначається .

Приклади решіток:

Примітка. Будь ланцюг є гратами, тому що збігається з меншим, а з великим з елементів .

Найбільший елемент, тобто елемент, більший або рівний кожного елемента упорядкованої множини, позначають 1, а найменший елемент, тобто менший або рівний кожного елемента упорядкованої множини, позначають 0.

На решітці можна розглядати дві бінарні операції:

- Складання і

- Твір

Ці операції мають такі властивості:

1. , ідемпотентность;

2. , комутативність;

3. , асоціативність;

4. , закони поглинання.

ТЕОРЕМА 1.1. Нехай L - множина з двома бінарними операціями , Що володіють властивостями (1) - (4). Тоді відношення (Або ) Є порядком на L, а виникає впорядковане безліч виявляється гратами, причому: і .

Доказ. Рефлексивність відносини випливає з властивості (1). Зауважимо, що воно є наслідком властивості (4):

Якщо і , Тобто і , То в силу властивості (2), отримаємо . Це означає, що відношення антисиметричною.

Якщо і , То застосовуючи властивість (3), отримаємо: , Що доводить транзитивність відносини .

Застосовуючи властивості (3), (1), (2), отримаємо:

,

.

Отже, і .

Якщо і , То використовуючи властивості (1) - (3), маємо:

, Тобто .

За визначенням точніше верхньої межі переконаємося, що .

З властивостей (2), (4) випливає, що і .

Якщо і , То за властивостями (3), (4) отримаємо:

.

Звідси за властивостями (2) і (4) випливає, що

.

Таким чином, .

Нехай L решітка, тоді її найбільший елемент 1 характеризується одним з властивостей:

1. .

2. .

Аналогічно характеризується найменший елемент :

1.

2. .

1.3. Дистрибутивні решітки

Решітка L називається дистрибутивної, якщо для будь-яких виконується:

D 1. .

D 2. .

У будь решітці тотожності D 1 і D 2 рівносильні. Доказ цього факту міститься в книзі [2], стор 24.

Приклади дистрибутивних решіток:

  1. Безліч цілих позитивних чисел, означає, що ділить . Це решітка з операціями НОД і НОК.

  2. Будь ланцюг є дистрибутивної гратами.


ТЕОРЕМА 1.2. Решітка L з 0 і 1 є дистрибутивної тоді і тільки тоді, коли вона не містить підграток виду

Доказ цієї теореми можна знайти у книзі [1].

1.4. Узагальнено булеві решітки, булеві решітки

Усюди далі під словом «грати» розуміється довільна дистрибутивная решітка з 0.

Решітка L називається узагальненої булевой, якщо для будь-яких елементів і d з L, таких що існує відносне доповнення на інтервалі , Тобто такий елемент з L, що і .

(Для , , Інтервал | ; Для , можна так само визначити напіввідкритий інтервал | ).

ТЕОРЕМА 1.3. (О єдиності відносного додатки узагальнено булевой решітці). Кожен елемент узагальнено булевой решітки L має тільки одне відносне доповнення на проміжку.

Доказ. Нехай для елемента існує два відносних додатки і на інтервалі . Покажемо, що . Так як відносне доповнення елемента на проміжку , То і , Так само відносне доповнення елемента на проміжку , То і .

Звідси

,

таким чином , Тобто будь-який елемент узагальненої булевой решітки має на проміжку тільки одне відносне доповнення.

Решітка L називається булевой, якщо для будь-якого елементу з L існує доповнення, тобто такий елемент з L, що і

ТЕОРЕМА 1.4. (О єдиності додатки булевой решітці). Кожен елемент булевой решітки L має тільки одне доповнення.

Доказ аналогічно доведенню теореми 1.3.

ТЕОРЕМА 1.5. (О зв'язку узагальнено булевих і булевих решіток).

Будь булева решітка є узагальнено булевой, зворотне твердження не вірно.

Доказ. Дійсно, розглянемо довільну булеву грати L. Візьмемо елементи a і d з L, такі що . Зауважимо, що відносним доповненням елемента a до елемента d є елемент , Де a '- доповнення елемента a в булевой решітці L. Дійсно, , Крім того . Звідси випливає, що грати L є узагальнено булевої.

1.5. Ідеали

Підгратки I решітки L називається ідеалом, якщо для будь-яких елементів і елемент лежить в I. Ідеал I називається власним, якщо . Власний ідеал решітки L називається простим, якщо з того, що і слід або .

Так як непорожнє перетин будь-якого числа ідеалів знову буде ідеалом, то ми можемо визначити ідеал, породжений безліччю H в решітці L, припускаючи, що H не збігається з порожнім безліччю. Ідеал, породжений безліччю H буде позначатися через (H]. Якщо , То замість писатимемо і називати головним ідеалом.

ТЕОРЕМА 1.5. Нехай L - грати, а H і I - Непорожні підмножини в L, тоді I є ідеалом тоді і тільки тоді, коли якщо , То , І якщо , То .

Доказ. Нехай I - ідеал, тоді тягне за собою , Так як I - Підгратки. Якщо , То Умови теореми перевірені.

Назад, нехай I задовольняє цим умовам і . Тоді і так як , То , Отже, I - підгратки. Нарешті, якщо і , То , Значить, і I є ідеалом.

Глава 2

2.1. Конгруенції

Відношення еквівалентності (тобто рефлексивне, симетричне і транзитивне бінарне відношення) на решітці L називається конгруенції на L, якщо і спільно тягнуть за собою і (Властивість стабільності). Найпростішими прикладами є ω, ι, визначені так:

(Ω) ; (Ι) для всіх .

Для позначимо через суміжний клас, що містить елемент , Тобто |

Нехай L - довільна грати і . Найменшу конгруенцію, таку, що для всіх , Позначимо через і назвемо конгруенції, породженою безліччю .

ЛЕММА 2.1. Конгруенція існує для будь-якого .

Доказ. Дійсно, нехай Ф = | для всіх . Так як перетин в решітці збігається з теоретико-множинним перетином, то для всіх . Отже, Ф = .

У двох випадках ми будемо використовувати спеціальні позначення: якщо або і - Ідеал, то замість ми пишемо або відповідно. Конгруенція виду називається головною, її значення пояснюється наступною лемою:

ЛЕММА 2.2. = | .

Доказ. Нехай , Тоді , Звідси . З іншого боку розглянемо , Але тоді . Тому і .

Зауважимо, що - Найменша конгруенція, щодо якої , Тоді як - Найменша конгруенція, така, що міститься в одному суміжному класі. Для довільних решіток про конгруенції майже нічого не відомо. Для дистрибутивних решіток важливим є наступний опис конгруенції :

ТЕОРЕМА 2.1. Нехай - Дистрибутивная решітка, і . Тоді і .

Доказ. Позначимо через Ф бінарне відношення, визначене наступним чином: і .

Покажемо, що Ф - відношення еквівалентності:

1) Ф - відношення рефлексивності: x · a = x · a; x + b = x + b;

2) Ф - відношення симетричності:

x · a = y · a і x + b = y + b y · a = x · a і y + b = x + b ;

3) Ф - відношення транзитивності.

Нехай x · a = y · a і x + b = y + b і нехай y · з = z · с і y + d = z + d. Помножимо обидві частини x · a = y · a на елемент с, отримаємо x · a · c = y · a · c. А обидві частини y · с = z · с помножимо на елемент a, отримаємо y · c · a = z · c · a. В силу симетричності x · a · c = y · a · c = z · a · c. Аналогічно отримуємо x + b + d = y + b + d = z + b + d. Таким чином .

З усього вище зазначеного випливає, що Ф - відношення еквівалентності.

Покажемо, що Ф зберігає операції. Якщо і z L, то (x + z) · a = (x · a) + (z · a) = (y · a) + (z · a) = (y + z) · a і (x + z) + b = z + (x + b) = z + (y + b), отже, . Аналогічно доводиться, що і, таким чином, Ф - конгруенція.

Нарешті, нехай - Довільна конгруенція, така, що , І нехай . Тоді x · a = y · a, x + b = y + b, і . Тому обчислюючи по модулю , Одержимо

, Тобто , І таким чином, .

СЛІДСТВО З ТЕОРЕМИ 2.1. Нехай I - довільний ідеал дистрибутивної решітки L. Тоді в тому і тільки тому випадку, коли для деякого . Зокрема, ідеал I є суміжним класом по модулю .

Доказ. Якщо , То і елементи x · y · i, i належать ідеалу I.

Дійсно .

Покажемо, що .

Скористаємося тим, що (*), Зауважимо, що і , Тому ми можемо додати до тотожності (*) або , І тотожність при цьому буде виконуватися.

Додамо : , Одержимо .

Додамо : , Одержимо .

Звідси . Таким чином, .

Зворотно згідно лемі 2, |

Однак і тому |

Якщо , То звідки

.

Дійсно, (**).

Розглянемо праву частину цієї тотожності:

Об'єднаймо перше і друге складові -

.

Об'єднаймо перше і третє складові -

,

таким чином (***)

Зауважимо, що , Тому додамо до обох частин висловлювання (***) y:

Але , Звідси .

Отже, умова наслідки з теореми 2.1. виконано для елемента . Нарешті, якщо і , То , Звідки і , Тобто є суміжним класом.

ТЕОРЕМА 2.2. Нехай L - булева решітка. Тоді відображення є взаємно однозначним відповідністю між конгруенції та ідеалами решітки L. (Під розуміємо клас нуля по конгруенції , Під розуміємо грати конгруенції.)





Доказ. В силу наслідки з теореми 2.1. це відображення на безліч ідеалів; таким чином ми повинні тільки довести, що воно взаємно однозначно, тобто що суміжний клас визначає конгруенцію . Це твердження, проте, очевидно. Дійсно тоді і тільки тоді, коли (*), Останнє порівняння в свою чергу рівносильне порівнянні , Де с - відносне доповнення елемента в інтервалі .

Дійсно, множитимемо вираз (*) на з:

, Але , А , Звідси .

Таким чином, в тому і тільки тому випадку, коли .

Примітка. Наведене доказ не повністю використовує умова, що L - Дистрибутивная решітка з доповненнями. Фактично, ми користувалися тільки тим, що L має нуль і є гратами з відносними доповненнями. Такі грати називається узагальненої булевой гратами.

ТЕОРЕМА 2.3 (Хасімото [1952]). Нехай L - довільна решітка. Для того, щоб існувало взаємно однозначна відповідність між ідеалами і конгруенції решітки L, при якому ідеал, відповідний конгруенції , Був би суміжних класом по , Необхідно і достатньо, щоб грати L була узагальненої булевої.







Доказ. Достатність випливає з доведення теореми 2.2. Перейдемо до доведення необхідності.

Ідеалом, відповідним конгруенції , Повинен бути (0]; отже, L має нуль 0.







Якщо L містить діамант , То ідеал (a] не може бути суміжним класом, тому що з слід і . Але , Отже, будь-суміжний клас, який містить , Містить і , І .

Аналогічно, якщо L містить пентагон і суміжний клас містить ідеал , То і , Звідки . Отже, цей суміжний клас повинен містити і .

Отже, грати L не містить підграток, ізоморфних ні діаманти, ні Пентагону. Тому, по теоремі 1.2., Вона дистрибутивна.

Нехай і . Згідно слідству з теореми 2.1., Для конгруенції ідеал так само є суміжним класом, отже, , Звідки . Знову застосовуючи наслідок з теореми 2.1. отримаємо, для деякого . Так як , То і . Отже, про підлозі орого ледствии 4 отримали, цііодержать, відповідним конгруенції чином ми повинні тільки довести, і , Тобто елемент є відносним доповненням елемента в інтервалі .

2.2. Основна теорема




  1. Нехай - Узагальнена булева решітка. Визначимо бінарні операції на B, вважаючи і позначаючи через відносне доповнення елемента в інтервалі . Тоді - Булево кільце, тобто (Асоціативне) кільце, яке задовольняє тотожність (А отже і тождествам , ).

  2. Нехай - Булево кільце. Визначимо бінарні операції і на , Вважаючи, що і . Тоді - Узагальнена булева решітка.

Доказ.

    1. Покажемо, що - Кільце.

Нагадаємо визначення. Кільце - Це непорожня множина із заданими на ньому двома бінарними операціями , Які задовольняють наступним аксіомам:

    1. Комутативність складання: виконується ;

    2. Асоціативність складання: виконується ;

    3. Існування нуля, тобто , ;

    4. Існування протилежного елемента, тобто , , ;

    5. Асоціативність множення: , ;

    6. Закон дистрибутивності.

Перевіримо, чи виконуються аксіоми кільця:

1. Відносним доповненням до елемента буде елемент , А відносним доповненням елемент . В силу того, що , А так само єдиності додатки маємо .

2. Покажемо, що .








Розглянемо всі можливі групи варіантів:

1) Нехай , Тоді (Далі скрізь під елементом x будемо розуміти суму ).

Аналогічно отримуємо у випадках , , , і . Зауважимо, що коли один з елементів дорівнює нулю (наприклад, c), то отримуємо тривіальні варіанти (a + b = a + b).

2) Нехай , А елемент c не можна порівняти з ними. Можливі такі варіанти:

























Неважко помітити, що у всіх цих випадках , Крім того:

якщо c = a + b, то (A + b) + c = 0 = a + (b + c);

якщо c = 0, то отримуємо тривіальний варіант.

Варіант, коли c дорівнює найбільшому елементу решітки d, ми вже розглядали.

Якщо c = b, то (A + b) + c = (a + b) + b = a і a + (b + c) = a + (b + b) = a.

Якщо c = a, то (A + b) + c = (a + b) + a = b і a + (b + c) = a + (b + a) = b.

Аналогічно для випадків , , , і .

3) Під елементами нижнього рівня будемо розуміти елементи , , , , , , , , Тобто ті елементи 4-х мірного куба, які утворюють нижній тривимірний куб.

Під елементами верхнього рівня будемо розуміти елементи , , , , , , , , Тобто ті елементи 4-х мірного куба, які утворюють верхній тривимірний куб.

Під фразою «елемент верхнього рівня, отриманий з елемента нижнього рівня зрушенням за відповідним ребру »будемо розуміти елемент верхнього рівня.

Нехай a, b, c непорівнянні. Розглянемо наступні варіанти: і .








Нехай . Зауважимо, що це можливо тільки у випадках, коли належать нижнього рівня, причому лежать на позиціях елементів (Рис. 1). Або a, b залишаються на своїх позиціях, елемент c зсувається на верхній рівень по відповідному ребру (рис. 2). Або елемент a залишається на своїй позиції, елементи b, c зсуваються на верхній рівень по відповідному ребру (рис 3).

Неважко помітити, що у всіх цих випадках .

Нехай , Тут так само .

Таким чином ми розглянули всі основні групи варіантів розташування елементів a, b, c і у всіх цих випадках асоціативність складання виконується.

3. Розглянемо в решітці елемент , До нього існує відносне доповнення до елемента , Тобто і . Враховуючи, що в решітці і , Маємо наступне: і . Звідси .

4. Розглянемо відносне доповнення елемента до , Це елемент . Таким чином: і . Враховуючи, що в решітці виконуються тотожності і маємо наступне: і . Звідси .

5. Так як в решітці виконується асоціативність , А так само маючи , То .

6. Доведемо дистрибутивність або що те ж саме

(*).

Доведемо, що доповнення лівої і правої частин виразу (*) до верхньої межі збігаються.

Неважко помітити, що доповненням правій частині виразу (*) до елемента буде елемент .

Покажемо це:

, За визначенням відносного додатки елемента ( ), Де за взяли елемент , А елемент за .

, За визначенням відносного додатки елемента ( ), Де за взяли елемент , А елемент за .

Покажемо, що і для лівої частини (*) елемент буде відносним доповненням до верхньої межі :

, Тому що .

Ми показали, що доповнення елементів і до верхньої межі збігаються, отже, в силу єдиності додатки . А значить і , Тобто дистрибутивність доведена.

Таким чином, для всі аксіоми кільця виконуються.

Зауважимо, що виконується в силу того, що , А в гратах .

Також виконується , Тому що .

Таким чином, - Булево кільце.

Доказ (2). Часткову впорядкованість маємо виходячи з того, що вихідне булево кільце - Частково упорядкований безліч. Крім того - Грати, тому що існують sup (x, y) і inf (x, y), задані відповідними правилами: і .

Покажемо, що грати дистрибутивно, тобто що виконується тотожність (*)

Розглянемо ліву частину виразу (*):

.

Розглянемо праву частину виразу (*):

,

т.ч. тотожність вірно, тобто решітка є дистрибутивної.

Покажемо, що у кожного елемента в дистрибутивної решітці є відносне доповнення. Для цього розглянемо довільні елементи , Але вони так само повинні бути елементами решітки , Отже, в ній повинні лежати і , Яким в кільці відповідають .

Розглянемо елемент булева кільця (В решітці лежить відповідний йому елемент), зауважимо, що

і .

Тому елемент буде в дистрибутивної решітці відносним доповненням до верхньої межі .

Таким чином, буде дистрибутивної гратами з відносними доповненнями (узагальненої булевої).

Бібліографічний список

  1. Гретцер, Г. Загальна теорія решіток [Текст] / Г. Гретцер. - М.: Мир, 1982.

  2. Біркгоф, Г. Теорія решіток [Текст] / Г. Біркгоф. - М.: Наука, 1984.

  3. Кушнірів, Л.А. Елементи алгебри [Текст] / Л.А. Кушнірів. - М.: Наука, 1989.

Додати в блог або на сайт

Цей текст може містити помилки.

Математика | Диплом
184.4кб. | скачати


Схожі роботи:
Обобщ нно булеві решітки
Класифікація груп з перестановки узагальнено максимальними підгрупами
Класи кінцевих груп F замкнуті про взаємно простих індексів щодо твору узагальнено
Решітки
Коливання кристалічної решітки
Підсилювач приймальні антеною решітки
Структурні дефекти кристалічної решітки
Конструювання вібраторних антеною решітки
Побудова лінійної решітки вібраторних антен
© Усі права захищені
написати до нас