Пит6
1. Множини і дії над ними.
Множиною називають сукупність об’єктів довільної природи(з певними обмеженнями). Множини прийнято позначати великими літерами А, В, …
Множина задається переліком елементів, в разі їх скінченності або ознакою,якою володіють всі елементи і тільки вони.
Числові множини мають стандартне позначення N-натуральні числа, Z-цілі числа, R-дійсні,Q – раціональні, C-комплексні. Множина без елементів називається порожньою і позначається
Кількість елементів множини називається її потужністю і позначається |A|. Якщо множина А містить об’єкт х, то його називаємо елементом А, і пишемо х є А, а інакше x А.
Якщо всі елементи множини А належать множині В, то А називають підмножиною В і пишемо .
Дії над множинами:
Для довільних двох множин А і В, визначають наступні дії:
Дії над множинами зручно позначати діаграмами Ейлера-Венна.
1) -об’єднання множин.
Об’єднанням 2-ох множин називається множина всіх елементів, які належать хоча б одній з множин А і В.
2) А- перетин множин.
Пертином 2-ох множин А і В називають множину елементів спільних для А і В.
3) A \ B – різниця множин.
Різницею 2-ох множин А і В називають множину елементів А, які не належать до В.
4) = (А \ В)(В \ А) - симетрична різниця.
Симетричною різницею називають множину елементів, які належать рівно одній з А і В.
Н-ад: А={1,2,3,4}, В={3,4,5}, тоді ={1,2,3,4,5}, А={3,4}, A \ B={1,2}, ={1,2,5}.
Дії над множинами мають очевидні властивості:
,
- комутативний закон.
,
- асоціативний закон.
,
- розподільні або дистрибутивні закони.
,
- іденпотентність.
=А – інволютивність.
закони Деморгана:
=, =
2. Відношення та їх властивості.
Означ.: Відношенням між елементами множин А1,А2,…,Аn називаємо довільну підмножину R декартового добутку A1A2…Аn.
Оскільки декартів добуток складається з усіх можливих наборів (а1,а2,…,аn), в яких а1 є А1, а2 є А2,…,аn є Аn, то відношення складається з усіх або деяких таких наборів, як правило відібраних за деякою ознакою.
Над в-ня. виконують операції обєднання,переріз,різниця,композиція.
Композицією R до 2ох в-нь R1A*B, R2B*C наз. в-ня RA*C.
Оберненим до в-ня R={(a,b):aєA,bєB} наз. в-ня R-1={(b,a):aєA,bєB}.
Якщо набір (а1,…,аn) потрапляє до , то кажемо що елементи а1,а2,…,аn перебувають у відношенні R.
Якщо відношення пов’язує елементи N-множин, то його називають n-арним (1-множину-унарне,2-ві-бінарне, 3-тернарне).
Пр.: - R-бінарне відношення між елементами множин А={1,2} і В={x,y}, тоді (1,х) є R-перебувають у відношенні, (1,у) R-не перебувають.
Як правило, для бінарних в-нь замість (х,у) є R пишуть простіше хRу.
Бінарне відношення на множині А може мати такі властивості:
рефлективність
-кожен елемент а з множини А перебуває у відношенні R сам із собою.
антирефлексивність
-ніякий елемент множини А не перебуває у множині R сам з собою.
симетричність
-якщо а перебуває у відношенні R з b, то й b перебуває у відношенні R з а.
асиметричність
-одночасне виконання аRb і bRa – неможливе.
антисиметричність
^ bRa
a=b)-одночасне виконання aRb i bRa –неможливе, або можливе при умові їх рівності.
транзитивність
(aRb^bRcaRc)-якщо у в-ні R перебувають а з b та b з с, то а перебуває у в-ні з с.
Якщо для деякого відношення мають місце наведені 3 властивості одночасно(рефлексивність, симетричність, транзитивність), то таке відношення називають відн. еквівалентності.
Транзитивним замиканням в-ня наз. найменше з відношень по включенню , яке містить дане в-ня і має властивість транзитивності. Можна побудувати за формулою тр=2..., де і=оо...о (і разів).
3.Відношення часткового порядку.
Означ.: Бінарне відношення на множині Х називається відношенням не строгого порядку, якщо воно рефлексивне, антисиметричне і транзитивне:
, то
; 2)
, то х=у ; 3)х
,
Відношення нестрогого порядку зображається графом, у якому :
1) в кожній вершині є петля; 2) між різними елементами не існує одночасно 2-ох протилежних стрілок;3) якщо існують дуги з х в у і з у в z , то існує і дуга з х в z.
Твердження: 1) Якщо існує -відношення строгого порядку, то - - відношення нестрогого порядку. 2)- відношення нестрогого порядку, то -відношення строгого порядку.
Означ.: Частковий порядок, для якого всі пари елементів є порівняльними називають лінійним порядком. Множину з частковим (лінійним) порядком називають частково (лінійно) впорядкованою.
Пр: Нехай A={3,7,8}, тоді 1,2,3 – нижні грані А, 8,9,10-верхні грані.
Означ.: Елемент х множини називають її найменшими елементом, якщо , інакше кажучи х – нижня грань всієї множини Х, у-найбільша, , , тоді у –верхня грань множини Х.
Означ.: Елемент х називається мінімальним min в множині , якщо не існує (тобто від нього не існує менших), аналогічно у-максимум max, якщо не існує .
Якщо у множині існує найменший елемент, то він єдиний і одночасно є min, але не навпаки, але не навпаки. Аналогічно, найбільший елемент є максимальний. Найменший і найбільший елементи множини А позначаються min A та max A.
Нехай А-підмножина ЧВМ (частково впорядкована множина).
Означ.: Найбільша серед нижніх граней множини А (якщо вона існує) називається точною нижньою гранню і позначається inf A(інфімум). Аналогічно – найменше з верхніх граней називається точною гранню і позначається sup A(супремум)- точна верхня грань.
Означ.: ЧВМ, в якій для кожних 2-ох елементів a i b існує іх точна нижня грань inf {a,b}=a^b – найбільша серед елементів, що передує а і b називається нижньою напівграткою . Аналогічно верхня напівгратка - це ЧВМ, така, що а і b існує точна верхня грань: sup{a,b}=ab( -cупремум).
Твердження: В лінійно впорядкованій множині (ЛВМ) -.
Теорема: Для кожної операції “ * ” : з властивостями
1) x*y=y*x; 2) x*(y*z)=(x*y)*z; 3) х*х=х.
Існує єдиний частковий порядок на х, для якого х*у – це точно нижня грань - .
4 Основні поняття та твердження про графи та орграфи.
Графом називаємо пару G=(V,E) з
