11. Операції над множинами
Закони операцій над множинами співпадають із законами логіки (2):
1) Комутативний p^q=q^p …
2) Асоціативний (р^q)^r=p^(q^r) …
3) Дистрибутивний (p^q)vr=(pvr)^(qvr) …
4) Закон де Моргана
5) Закон суперечності p^(не)р=0
6) Закон виключеного третього рv(не)р=1
7) Закон подвійного заперечення
8) Закон ідемпотентності р^q=p …
9) Закон поглинання (pvq)^p=p …
10) Співвідношення для сталих p^1=p p^0=0 p+1=1 p+0=p
12.Комп’ютерне подання множини.
У комп’ютері можна подавати мнж різними способами. Один з них - зберігати невпорядк елементи мнж.Проте в такому разі операції з мнж займатимуть багато часу, оскільки треба щоразу переглядати елементи. Одним із найпошир і найпрост способів є подання мнж за допомогою бітових рядків. Впорядкуємо універсальну множину U={U1, U2…Un}. Якщо елемент Us належить мнж А то на і-вому місці бітового рядка ставимо 1, якщо Us не належ А то ставимо 0. Довжина бітового рядка = кількості елементів в універсальній множині.
13.Відношення та їх властивості.
Найпростіший спосіб задати співвідношення між елементами – це задати пари цих елементів. Бінарним відношенням називається підмножина декартового добутка АхВ а належ А, в належ В, (а.в) належ R. Якщо А=В, відношення називається унарним. Властивості відношень: Властивості відношень на множині А.
Відношення
R
на множині А називають рефлексивним,
якщо для будь-якого
виконується
.
Відношення
R
на множині А називають антирефлексивним,
якщо з
виходить, що
.
Відношення
R
на множині А називають іррефлексивним,
якщо для будь-якого
виконується
.
Відношення
R
на множині А називають симетричним,
якщо для будь-яких
з того, що
,
випливає, що
.
Відношення
R
на множині А називають антисиметричним,
якщо для всіх
з того, що
і
,
випливає, що
.
Відношення
антисиметриче,
якщо в разі
воно водночас не містить пар
та
.
Існують відношення, які мають обидві
властивості: симетричності й
антисиметричності. Наприклад, відношення
на множині А = {а} водночас і симетричне,
й антисиметричне. Є також відношення,
які не мають жодної з цих двох властивостей.
Відношення
R
на множині А називають асиметричним,
якщо для всіх
з того, що
,
випливає, що
.
Будь-яке асиметричне відношення має
бути й антисиметричним. Обернене
твердження неправильне.
Відношення
R
на множині А називають транзитивним,
якщо для будь-яких
з того, що
,
випливає
.
Відношення
R
на множині А називають антитранзитивним,
якщо для будь-яких
з того, що
,
випливає
.
14.Відношення еквівалентності.
Відношення назив відношенням еквівалентності, якщо воно рефлексивне, симетричне і транзитивне. Елементи, які перебувають у відношенні еквівалентності називаються еквівалентнимию. Відношення еквівалентності розбиває будь – яку множину на класи еквівалентності, при чому всі вони не перетинаються. Відношення еквівалентності можна розглянути на прикладі конгруенції. Число а називається конгруентним числу в якщо їх при діленні на число М – рівні. Класи еквівалентності позначаються К(a)(m) де m – модуль, а – представник класу. Сумою класів К(a)(m) і К(в)(m) називається клас з представником а+в (К(a+в)(m) ). Добутком класів К(a)(m) і К(в)(m) називається клас з представником а*в (К(a*в)(m) ).
15.Відношення часткового порядку.
Відношення R на множині а називається відношенням часткового порядку, якщо воно рефлексивне, антисиметричне і транзитивне. Відношення строгого порядку: антирефлексивне, асиметричне, транзитивне. Відношення толерантності: рефлексивне, симетричне, антитранзитивне.
16.Операції над відношеннями.
1) Об’єднання- Якщо A та B - множини, то об'єднанням A та B є множина, яка включає всі елементи A і всі елементи B, і більш нічого.
2)Переріз
3)Різниця - Якщо A та B - множини, то різницею між B та А (порядок множин важливий), або відносним доповненням A до B, є множина з елементів B, які не належать A.
4)Композиція
17.Замикання відношень.
Замиканням відношення R відноносно властивості Р називається така множина R*, що: 1)R(належ) R* 2) R* володіє вдастивістю Р. 3) R* є підмножиною будь-якого іншого відношення, яке містить R і має властивість Р.
18.Алгебраїчні операції та іх властивості
n-арна операція f на А – це відображення прямого добутку n екземплярів множини на смаму множину f: An A . Найчастіше розглядають унарні і бінарні операції.
19. Поняття алгебраїчної структури
Алгебраїчною структурою називається множина разом із заданими операціями, визначеними і замкненими на цій множині. Ця множина називається носієм алгебраїчної структури.
На непорожній множині X може бути задано, взагалі кажучи, багато різних алгебраїчних операцій. Бажаючи виділити одну з них, використовують дужки:, і говорять, що операція визначає на X алгебраїчну структуру. Якщо операція асоціативна чи комутативна, то такі ж назви привласнюються і відповідній алгебраїчній структурі. Природа елементів основної множини X нас не цікавить, справжніми об’єктами вивчення є алгебраїчні операції. Ясно, що виділити можна не одну операцію, а декілька.
Непорожня множина X разом із заданою на ній сукупністю алгебраїчних операцій називається алгебраїчною структурою:.
Непорожня множина X разом із заданою на ній сукупністю алгебраїчних операцій і сукупністю відношень називається алгебраїчною системою:. Якщо алгебраїчна система не містить операцій, вона називається моделлю, якщо не містить відношень – алгеброю.
Множина F дійсних функцій однієї дійсної змінної, тобто функцій разом з унарною операцією диференціювання утворює алгебру.