Вивчення поняття відносин залежності
Курсова робота
Вивчення поняття відносин залежності
Зміст
Введення
1. Визначення й приклади
2. Простір залежності
3. Транзитивність
4. Зв'язок транзитивних відносин залежності з операторами замикання
5. Матроїди
Висновок
Список літератури
Введення
Метою курсової роботи є вивчення поняття відносини залежності, розгляд відносини залежності на різних множинах.
Поставлена мета припускає рішення наступних задач:
Вивчити й дати визначення поняттю відношення залежності.
Розглянути деякі приклади відносини залежності.
Сформулювати й довести властивості й теореми як для довільних, так і для транзитивних просторів залежності.
Розглянути теорему про зв'язок транзитивного відношення залежності й алгебраїчного оператора замикання.
Вивчити поняття матроїда, привести приклади матроїдів.
Розглянути жадібний алгоритм і його зв'язок з матроїдами.
На підставі поставлених цілей і задач кваліфікаційна робота розбивається на 5 параграфів.
У першому параграфі наведені основні визначення й розглянуті деякі приклади відносини залежності.
У другому - розглядаються довільні простори залежності, їхньої властивості й деяких теорем.
Третій – присвячений транзитивним і кінцеве мірним просторам залежності. Тут розглянуті властивості транзитивних просторів залежності й доведені теореми, які підтверджують існування базису й інваріантність розмірності в будь-якому кінцеве мірному транзитивному просторі залежності.
У четвертому параграфі формулюються основні визначення дотичного оператора замикання й розглянута теорема про подання транзитивного відношення залежності за допомогою алгебраїчного оператора замикання.
П'ятий параграф присвячений матроїдам, прикладам матроїдів і їхньому застосуванню при вивченні теоретичною основою аналізу «жадібних» алгоритмів.
Основною літературою при написанні кваліфікаційної роботи стали монографії: Кона П. «Універсальна алгебра» [2] і Куроша О. Г. «Курс вищої алгебри» [3].
1. Визначення й приклади
Визначення 1.
Множина Z підмножин множини A назвемо відношенням залежності на A, якщо виконуються наступні аксіоми:
Z1:
Z ;
Z2:
Z
Z ;
Z3:
Z
(
Z
-
звичайно).
Підмножина множини A називається залежною, якщо вона належить Z, і незалежною у противному випадку.
Легко переконатися в незалежності аксіом Z1 - Z3..
Модель 1:
.
Думаємо Z = B (А)
для будь-якої
множини
.
Модель 2:
.
Нехай Z =
при
.
Модель 3:
. Нехай Z =
для нескінченної
множини
.
Визначення 2.
Простором
залежності
назвемо пари
Z
, де Z – відношення
залежності
на A.
Визначення 3.
Елемент
називається
залежним
від множини
,
якщо а О
X або існує така
незалежна
підмножина
Y множини X, що
залежно, тобто
Z
Z ).
З визначення
1 випливає, що
якщо елемент
залежить від
множини
,
то він залежить
від деякої
кінцевої підмножини
.
Визначення 4.
Множина всіх
елементів, що
залежать від
X, називається
оболонкою
множини X і
позначається
через
.
Ясно, що
й включення
тягне включення
їхніх оболонок:
.
Визначення 5.
Якщо
= A, то X називається
множиною, що
породжує, множини
A.
Визначення 6.
Незалежна підмножина, що породжує, множини A називається базисом множини A.
Визначення 7.
Множина
залежить
від
,
якщо будь-який
елемент із
залежить від
,
тобто
.
Визначення 8.
Відношення
залежності
Z на A будемо
називати транзитивним
відношенням
залежності,
якщо
.
Визначення 9.
Транзитивним простором залежності назвемо простір залежності, у якому відношення залежності має властивість транзитивності.
Як теоретико-множинний постулат будемо використовувати наступний принцип, еквівалентний відомій аксіомі вибору.
Лема Цорна.
Непуста впорядкована множина, у якому кожне лінійно впорядкована підмножина має верхню грань, має максимальний елемент.
Далі доцільно розглянути деякі приклади відносини залежності:
Приклад 1.
Поняття лінійної
залежності
у векторному
просторі V над
полем
.
Система векторів
векторного
простору V
називається
лінійно залежної,
якщо існує
кінцева лінійно
залежна її
підсистема,
у противному
випадку – лінійно
незалежної.
Поняття лінійної
залежності
в кінцеве мірних
векторних
просторах
дається в курсі
алгебри. Кінцева
система векторів
V
називається
лінійно залежної,
якщо існують
елементи поля
одночасно не
рівні нулю й
такі, що лінійна
комбінація
. Множина лінійних
комбінацій
множини
векторів векторного
простору V з
коефіцієнтами
з поля P називається
лінійною
оболонкою
цих векторів
і позначається
.
При цьому
- є підпростором
у просторі V,
породженим
.
Одержуємо
транзитивне
відношення
залежності.
Приклад 2.
Нехай поле
є розширенням
основного поля
Р, а
мінімальне
підкольце
утримуючі
елементи
й поле Р. Підкольце
складається
із всіх елементів
поля
,
які виражаються
через елементи
й елементи поля
Р за допомогою
додавання,
вирахування
й множення: це
будуть усілякі
багаточлени
від
з коефіцієнтами
з поля Р. Тоді,
якщо для всякого
елемента
існує єдиний
запис у вигляді
багаточлена
від
як невідомих
з коефіцієнтами
з поля Р, тобто
якщо різні
багаточлени
від
будуть різними
елементами
підкольца
,
те система
елементів
,
буде називатися
алгебраїчно
незалежної
над полем Р, у
противному
випадку алгебраїчно
залежної.
Довільна множина
елементів поля
Р називається
залежним,
якщо воно містить
кінцеву залежну
підмножину.
У першому випадку
кільце
ізоморфно
кільцю багаточленів
.
Відношення
алгебраїчної
залежності
над полем Р
є транзитивним
відношенням
залежності.
Приклад 3.
Нехай на множині
A задане рефлексивне
й симетричне
бінарне відношення
(називане відношенням
подібності).
Підмножина
X множини A
будемо вважати
залежним,
якщо воно містить
два різних
елементи, що
перебувають
у відношенні
.
Оболонкою
множини
служить множина
![]()
![]()
У цьому випадку
можна підсилити
аксіому
відносини
залежності
в такий спосіб:
Z
Z.
Тоді оболонкою
множини
буде множина
всіх елементів,
що перебувають
відносно подібності
хоча б з одним
елементом із
множини
.
Уведене відношення
залежності
буде транзитивним
тоді й тільки
тоді, коли відповідне
бінарне відношення
буде транзитивне,
тобто є відношенням
еквівалентності
на
.
У випадку, коли
- відношення
еквівалентності
буде незалежним
тоді й тільки
тоді, коли
множина
містить не
більше одного
елемента. Будь-яка
максимальна
незалежна
підмножина
буде містити
рівно по одному
елементі з
кожного класу
еквівалентності
.
Приклад 4.
Розглянемо
чотирьох елементну
множину
.
Назвемо підмножину
множини
залежним
тоді й тільки
тоді, коли
або
.
Z
.
Розглянемо
підмножину
множини
,
по уведеному
визначенню
воно буде незалежно.
Розглянемо
оболонку множини
й знайдемо
оболонку оболонки
нашої множини
.
Таким чином,
ми одержали
,
тобто розглянуте
нами відношення
залежності
не є транзитивним.
Приклад 5.
Розглянемо
довільну множину
й
.
Множина
будемо вважати
залежним,
якщо
B (А) B (В), тобто
,
але
.
Таким чином,
одержали наступний
транзитивний
простір залежності:
B (А) B (В.
Оболонкою
буде множина
.
Зокрема можна розглянути 2 випадки:
,
тобто всі множини
незалежні, тоді
.
B (А)![]()
, тобто всі
множини, крім
порожнього,
будуть залежними,
у цьому випадку
.
Приклад 6.
Розглянемо
довільну множину
і його непусту
кінцеву підмножину
.
Уведемо на
множині А
наступне відношення
залежності
Z
B (А)
.
Таким чином,
залежними
будуть всі
надмножини
множини
.
Якщо
,
то
.
Якщо
,
то
.
Якщо
,
то
.
Одержуємо транзитивний простір залежності.
Приклад 7.
Підпростір
простору залежності
Z
. Розглянемо
,
де діє те ж
відношення
залежності
Z. Тоді одержимо
індукований
простір залежності
Z
B
.
У цьому випадку
залежними
будуть тільки
ті підмножини
множини
,
які були залежні
в просторі
Z
. І якщо простір
Z
транзитивне,
те транзитивним
буде й підпростір
.
Приклад 8.
Нехай
і Z =
.
Такий простір
залежності
Z
не транзитивне,
тому що
й
.
Простір А має
два