Федеральне агентство з освіти
Державна освітня установа
вищої професійної освіти
Вятський державний гуманітарний університет
Математичний факультет
Кафедра алгебри і геометрії
Випускна кваліфікаційна робота
Узагальнено булеві решітки


Виконав:
студент V курсу математичного факультету
Онучін Андрій Володимирович
Науковий керівник:
к.ф.-м.н., доцент кафедри алгебри та геометрії ВятГГУ
Чермний Василь Володимирович
Рецензент:
д.ф.-м.н., професор, зав. кафедрою алгебри і геометрії ВятГГУ
Вечтомов Євген Михайлович
Робота допущена до захисту в державної атестаційної комісії
«___» __________2005 Р. Зав. кафедрою Є.М. Вечтомов
«___»__________ 2005 Декан факультету В.І. Варанкіна
Кіров
2005
Зміст
"1-2" Вступ ............................................ .................................................. ............ 3
Глава 1 ................................................ .................................................. ........... 4
1.1. Впорядковані множини ................................................ ................... 4
1.2. Грати ................................................. ................................................. 5
1.3. Дистрибутивні решітки ................................................ ..................... 7
1.4. Узагальнені булеві решітки, булеві решітки ................................. 8
1.5. Ідеали ................................................. .................................................. 9
Глава 2 ................................................ .................................................. ......... 11
2.1. Конгруенції ................................................. ...................................... 11
2.2. Основна теорема ................................................ ............................... 16
Бібліографічний список ................................................ .......................... 22

Введення

Булева грати є класичний математичний об'єкт, який почав інтенсивно вивчатися в роботах М. Стоуна 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 називається дистрибутивної, якщо для будь-яких виконується:
D1. .
D2. .
У будь-якій решітці тотожності D1 і D2 рівносильні. Доказ цього факту міститься в книзі [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.