Пит6
1. Множини і дії над ними.
Множиною називають сукупність об’єктів довільної природи(з певними обмеженнями). Множини прийнято позначати великими літерами А, В, …
Числові множини мають стандартне позначення N-натуральні числа, Z-цілі числа, R-дійсні,Q – раціональні, C-комплексні. Множина без елементів називається порожньою і позначається
Множину можна задати, перелічивши всі її елементи: А={1,3,5}; N={1,2,3,…}. Інший спосіб – вказати ознаку, за якою відбираються елементи множини. {x | x-парне додатнє }={2,4,6,…}, якщо ж відбираємо тільки елементи з деякої множини, то пишемо так: {у є R|<3}=(-,).
Кількість елементів множини називається її потужністю і позначається |A|. Якщо множина А містить об’єкт х, то його називаємо елементом А, і пишемо
х є А, а інакше x А.
Якщо всі елементи множини А належать множині В, то А називають підмножиною В і пишемо .
Н-ад:.Порожня множина є елементом кожної множини.
Дії над множинами:
Для довільних двох множин А і В, визначають наступні дії:
Дії над множинами зручно позначати діаграмами Ейлера-Венна.
1) -об’єднання множин.
Об’єднанням 2-ох множин називається множина всіх елементів, які належать хоча б одній з множин А і В.
2) А- перетин множин.
Пертином 2-ох множин А і В називають множину елементів спільних для А і В.
3) A \ B – різниця множин.
Різницею 2-ох множин А і В називають множину елементів А, які не належать до В.
4) = (А \ В)(В \ А) - симетрична різниця.
Симетричною різницею називають множину елементів, які належать рівно одній з А і В.
Якщо в деякій задачі розглядаємо тільки елементи деякої множини, то цю множину називають універсумом. Якщо U – універсум, то для довільної множини А, різниця U \ A складається з усіх елементів, що не належать множині А, вона називається доповненням до А (позначають ).
Н-ад: U=N, А={2,4,6,…}, ={1,3,5,…}.
Дії над множинами мають очевидні властивості:
,
- комутативний закон.
,
- асоціативний закон.
,
- розподільні або дистрибутивні закони.
,
- іденпотентність.
=А – інволютивність.
Корисними є так звані закони Деморгана: =, =
Дії об’єднання і перетину можливі для довільної кіл-ті мн-н, при цьому можна використовувати скорочення або
2. Відношення та їх властивості.
Відношенням між елементами множин А1,А2,…,Аn наз-мо довільну підмножину R декартового добутку A1A2…Аn.
Оск-ки декартів добуток склад-ся з усіх можливих наборів (а1,а2,…,аn), в яких а1є А1, а2 є А2,…,аn є Аn, то відн-ня складається з усіх або деяких таких наборів, як правило відібраних за деякою ознакою.
Якщо набір (а1,…,аn) потрапляє до , то кажемо що елементи а1,а2,…,аn перебувають у відношенні R.
Якщо відношення пов’язує елементи N-множин, то його називають n-арним (1-множину-унарне,2-ві-бінарне, 3-тернарне).
Як правило, для бінарних відн-нь замість (х,у) є R пишуть простіше хRу.
Бінарним відношенням між елементами скінчених множин зображають також бітовими матрицями (таблицями). Якщо | A|=m, |B|=n, то кожному відношенню відповідає відношення m рядків з n стовпців. Якщо і-тий елемент з А перебуває у відношенні R з j-им елементом множини В, то в і-му рядку на j-му місці ставимо одиничку.
Бінарне відношення на множині А може мати такі властивості:
рефлексивність
-кожен ел-т а з множини А перебуває у відношенні R сам із собою.
антирефлексивність
-ніякий ел-т множини А не перебуває у множині R сам з собою.
симетричність
-якщо а – у від-ні R з b, то й b–у в-ні R з а.
асиметричність.
-одночасне вик-ня аRb і bRa – неможл.
антисиметричність
^ bRa
a=b)-одночасне виконання aRb i bRa –неможливе, або можливе при умові їх рівності.
транзитивність
(aRb^bRcaRc)-якщо у відношенні R перебувають а з b та b з с, то а перебуває у відношенні з с.
Бінарне відношення R є :
1.рефлекивне, якщо у його матриці по головній діагоналі розташовані одинички.
2.антирефлексивне, якщо у його матриці по головній діагоналі розташовані нулі
3.симетричне, якщо його матриця теж симетрична відносно головної діагоналі.
4.антисиметричне, якщо у матриці елемент, симетричний до кожної одиниці поза діагоналлю є нулем.
5 асиметричне, якщо у матриці немає 2-ох одиниць симетричних відносно однієї діагоналі, зокрема на самій діагоналі всі елементи є нулями.
3.Відношення часткового порядку.
Означ.: Бінарне відношення на множині х називається відношенням не строгого порядку, якщо воно рефлексивне, антисиметричне і транзитивне:
^,то х=у ^
Відношення не строгого порядку на множині R- зображається графом, у якому: в кожній вершині є петля, між різними елементами не існує одночасно 2-ох протилежних стрілок, якщо існують дуги з х в у і з у в z, то існує і дуга з x в z.
Бінарне відношення на множині Х називається відношенням не строгого порядку, якщо воно рефлексивне, антисиметричне і транзитивне:
, то
; 2)
, то х=у ; 3)х
,
Відношення нестрогого порядку зображається графом, у якому :
1) в кожній вершині є петля; 2) між різними елементами не існує одночасно 2-ох протилежних стрілок;3) якщо існують дуги з х в у і з у в z , то існує і дуга з х в z.
Твердження: 1) Якщо існує -відношення строгого порядку, то - - відношення нестрогого порядку. 2)- відношення нестрогого порядку, то -відношення строгого порядку.
Якщо для відношення порядку і для елементів х та у виконано або то х та у – порівняльні, інакше – не порівняльні.
Частковий порядок, для якого всі пари елем-в є порівняльними – лін-ий порядок. Мн-ну з частковим(лін-м) порядком наз-ть частково(лін-но) впорядкованою.
Нехай А-підмножина частково впорядкованої множини ; елемент b називають нижньою гранню А, якщо . Аналогічно елемент с є X, с- верхня грань множини то, для всіх а є А.
Означ.: Елемент х множини називають її найменшими елементом, якщо , інакше кажучи х – нижня грань всієї множини
