Курсовая работа: Вивчення поняття відносин залежності
Приклад 6.
Розглянемо довільну множину і його непусту кінцеву підмножину
. Уведемо на множині А наступне відношення залежності
Z B (А)
.
Таким чином, залежними будуть всі надмножини множини .
Якщо , то
.
Якщо , то
.
Якщо , то
.
Одержуємо транзитивний простір залежності.
Приклад 7.
Підпростір простору залежності Z
. Розглянемо
, де діє те ж відношення залежності Z. Тоді одержимо індукований простір залежності
Z
B
. У цьому випадку залежними будуть тільки ті підмножини множини
, які були залежні в просторі
Z
. І якщо простір
Z
транзитивне, те транзитивним буде й підпростір
.
Приклад 8.
Нехай і Z =
. Такий простір залежності
Z
не транзитивне, тому що
й
. Простір А має два базиси
й
, які є і єдиними мінімальними множинами, що породжують
в.
Цей приклад показує, що існують не транзитивні простори залежності, у яких мінімальні множини, що породжують, незалежні, тобто є базисами.
Приклад 9.
Задамо на множині N натуральних чисел наступне відношення залежності:
Z .
Одержуємо нескінченну строго зростаючий ланцюжок оболонок в Z
. При
одержуємо
.
Таким чином, маємо .
Зауваження.
Поняття простору залежності можна й зручно визначати через базу залежності. Саме, множина B всіх мінімальних залежних множин простору залежності Z
назвемо його базою . Ясно, що множини з B не порожні, кінцеві й не втримуються друг у другу. Крім того, будь-яка незалежна множина містить деяка множина бази B . Простір
Z
має єдину базу й однозначно визначається їй. Тому простору залежності можна задавати базами.
Легко бачити, що вірно наступне твердження:
Непуста множина B підмножин множини задає на
відношення залежності тоді й тільки тоді, коли множини з B не порожні, кінцеві й не включений друг у друга.
У термінах бази B можна сформулювати умова транзитивності відповідного простору залежності.
2. Простір залежності
Теорема 1.