Размещено на http://www.allbest.ru/

Теорія множин

Вступ

У повсякденному житті та практичній діяльності часто доводиться говорити про деякі сукупності різних об'єктів: предметів, понять, чисел, символів тощо. Наприклад, сукупність деталей механізму, аксіом геометрії, чисел натурального ряду, літер абетки. На основі інтуїтивних уявлень про подібні сукупності сформувалося математичне поняття множини. Значний внесок до теорії множин зробив Георг Кантор. Згодом завдяки його дослідженням теорія множин стала цілком визначеною та обґрунтованою галуззю математики, а на сьогодні вона набула фундаментального значення.

1. Основні поняття теорії множин. Алгебра множин

Множина є настільки загальним і водночас початковим поняттям, що її чітке визначення через більш прості поняття дати важко. Тому слідом за Г. Кантом ми приймаємо інтуїтивне уявлення про множину як сукупність деяких елементів, цілком визначених у випадку кожної конкретної множини.

Способи задання множин.

1. Простий перелік елементів А={a1, a2,…, an,}.

2. Опис елементів визначеною властивістю: X={x|P(x)}, де P(x) означає, що елемент х має властивість P(x).

Операції на множинах:

1) об'єднання (сума) AB;

2) перетин (добуток) AB;

3) різниця A\B;

4) доповнення (заперечення) .

Множина 2U всіх підмножин універсальної множини U із заданими на ній чотирма операціями складає алгебру множин.

2. Відношення та їх властивості

Відношення реалізують у математичних термінах на абстрактних множинах реальні зв'язки між реальними об'єктами. Відношення застосовуються при побудові комп'ютерних баз даних, які організовані у вигляді таблиць даних. Зв'язки між групами даних у таблицях описуються мовою відношень. Самі дані обробляються і перетворюються мовою відношень.

Під n-арним відношенням R на множині Х розуміється підмножина n-го ступеня цієї множини RXn. Якщо n=1, то відношення називається унарним, якщо n=2 - бінарним.

Способи задання бінарних відношень.

1. Будь-яке бінарне відношення може бути задане у вигляді списку, елементами якого є пари, з яких складається відношення.

2. Бінарне відношення R на множинах X і Y може бути задане за допомогою матриці (W=W(R)), рядки якої відповідають елементам множини X, стовпчики - елементам множини Y.

3. Бінарне відношення R на множинах X, Y може бути задане графічно.

Операції над відношеннями: обернене відношення, композиція відношень, степінь відношення, переріз відношення, фактор-множина.

Властивості бінарних відношень: рефлексивність, антирефлексивність, симетричність, асиметричність, антисиметричність, транзитивність, антитранзитивність.

Бінарні відношення підрозділяються на відношення еквівалентності, порядку та толерантності.

3. Відображення та функції

Відношення R між множинами X і Y (RXY) є функціональним, якщо всі його елементи (упорядковані пари) різні за першим елементом: кожному xX або відповідає тільки один елемент yY, такий, що xRy, або такого елемента y взагалі не існує.

Нехай F - функціональне відношення, FXY. Відповідність x y від першого до другого елемента кожної пари (x,y)F відношення F називається функцією f або відображення f множини Df в Y і позначається як f: DfY, або як DfY.

Види зображень.

1. Функція f: XY називається сюр'єктивним відображенням, якщо Rf=Y.

2. Функція f: XY називається ін'єктивним відображенням, якщо з x1x2 випливає f(x1) f(x2).

3. Функція f: XY називається бієктивним відображенням, якщо вона сюр'єктивна та ін'єктивна.

4. Булеві функції та алгебра логіки

Для зображення інформації в комп'ютерах використовується двійкова система числення. Таким чином, всі операції, які виконує комп'ютер, проводяться на множині {0,1}. Ці перетворення зручно формально зобразити за допомогою апарата двійкової логіки, який був розроблений Джорджем Булем у середині ХІХ століття.

Функція виду y=f(x1,x2,…,xn), аргументи xi і значення y якої належить множині В, називається n-місною булевою функцією. Такі функції також називають логічними або перемикальними функціями.

Таблиці, в яких кожній інтерпретації (тобто набору аргументів) функції поставлено у відповідність її значення, називаються таблицями істинності булевої функції.

Булева алгебра - це алгебраїчна структура (А, , +, ,0,1) з бінарними операціями , +: А2А, унарною операцією « »: АА і виділеними елементами 0,1 в носії А.

5. Двоїстість булевих функцій

Функція f*(x1,…,xn) називається двоїстою до функції f(x1,…,xn), якщо f*(x1,…,xn)=.

Функція, двоїста сама собі, тобто f=f*, називається самодвоїстою.

Нехай функція F задана як суперпозиція функцій f0 і функцій f1,…,fn: F=f0 (f1,…,fn). Функцію F*, що двоїста F, можна одержати, замінивши у формулі F функції f0; f1,…,fn на двоїсті до них f*0; f*1,…,f*n.

Зазначимо функції, що двоїсті до „елементарних” функцій логіки ,, , константа 0, константа 1:

f(x,y)=xy; f*(x,y)==xy;

f(x)=; f*(x)==f(x);

f(x)=0; f*(x)==1=.

6. Нормальні форми

Серед множин еквівалентних формул, що зображують обрану функцію f, виділяється одна формула, яка називається досконалою нормальною формою функції f. Вона має регламентовану логічну структуру і однозначно визначається за функцією f, а її побудова заснована на рекурентному застосуванні теореми про спеціальні розкладання булевої функції за змінними.

Теорема 1. Про диз'юнктивне розкладання булевої функції f(x1,x2,…,xn) за k змінними.

Будь-яку булеву функцію f(x1,x2,…,xn) можна зобразити в такій формі:

f(x1,…,xk, xk+1,…,xn)=.

Досконалою диз'юнктивною нормальною формою (ДДНФ) булевої функції називається формула, зображена у вигляді диз'юнції конституент одиниці даної функції.

Теорема 2. Про кон'юнктивне розкладання булевої функції f(x1,x2,…,xn) за k змінними.

Будь-яку булеву функцію f(x1,x2,…,xn) можна зобразити у такій формі:

f(x1,…,xk, xk+1,…,xn)=.

Досконалою кон'юнктивною нормальною формою (ДКНФ) функції називається формула, зображена у вигляді кон'юнкції конституент нуля даної функції.

Для кожної інтерпретації функції існують єдині відповідні їй конституента одиниці та конституента нуля. Тому різних конституент одиниці та нуля для функції n змінних f(x1,x2,…,xn) існує стільки ж, скільки й інтерпретацій цієї функції - 2n.

Кількість різних булевих функцій від n змінних також становить . Отже, для кожної булевої функції існує єдина ДДНФ. Аналогічно доводиться, що різних ДКНФ функції від n змінних існує і, отже, кожній булевій функції відповідає єдина ДКНФ.

7. Алгебра Жегалкіна

Алгебра (В,,,0,1), що утворена множиною В={0,1} разом з операціями (кон'юнкції), (XOR - от eXclusiva OR, сума за модулем 2) і константами 0,1, називається алгеброю Жегалкіна.

Серед усіх еквівалентних зображень функції в алгебрі Жегалкіна виділяється особливий вид формул, що називаються поліном Жегалкіна.

Поліномом Жегалкіна називається скінченна сума за модулем 2 попарно різних елементів кон'юнкцій над множиною змінних {x1,x2,…,xn}. Кількість змінних, що входять до елементарної кон'юнкції, називається рангом елементарної кон'юнкції.

Кількість попарно різних елементарних кон'юнкцій у поліномі називається довжиною полінома.

Булева функція називається лінійною, якщо її поліном Жегалкіна не містить кон'юнкцій змінних.

8. Функціональна повнота наборів булевих функцій

Замкненням множин булевих функцій називається множина [], що складається з функцій, які можна одержати суперпозицією функцій з . Якщо =[], то множина булевих функцій називається замкненим класом. Іншими словами можна сказати, що множина називається замкненим класом, якщо будь-яка суперпозиція функцій з також належить .

Система булевих функцій ={f1,f2,…,fn} називається функціонально повною, якщо []=Р2.

Булева функція f(x1,x2,…,xn) називається функцією, що зберігає 0, якщо на нульовому наборі вона дорівнює 0: f(0,0,…,0)=0.

Булева функція f(x1,x2,…,xn) називається функцією, що зберігає 1, якщо на одиничному наборі вона дорівнює 1: f(1,1,…,1)=1.

Булева функція f називається монотонною, якщо для будь-яких пар наборів значень змінних (a1,…,an) і (b1,…,bn), для яких виконується відношення (a1,…,an) (b1,…,bn), правильна і нерівність f(a1,…,an) f(b1,…,bn).

Система булевих функцій повна, якщо і тільки якщо вона містить хоча б одну функцію, що не зберігає нуль, хоча б одну функцію, що не зберігає одиницю, хоча б одну несамодвоїсту функцію, хоча б одну немонотонну функцію і хоча б одну нелінійну функцію.

9. Методи мінімізації булевих функцій

Пошук найбільш простої логічної формули булевої функції має велике значення при формуванні запитів до баз даних, у логічному програмуванні, в інтелектуальних системах.

Задача мінімізації складається з пошуку найпростішої, згідно з обраним критерієм мінімізації, формули. Критерії можуть бути різними, наприклад: кількість змінних у формулі, кількість знаків кон'юнкції та диз'юнкції або комбінація подібних критеріїв.

Карта Карно для ДНФ (діаграма Вейча - для КНФ) є аналогом таблиці істинності, зображеній у спеціальній формі. Значення змінних розташовані у заголовках рядків і стовпчиків карти.

Для конкретної булевої функції карта Карно заповнюється так. У клітинках, відповідних інтерпретаціям, на яких функція дорівнює одиниці, записують одиниці. Ці клітинки відповідають конституентам одиниці, що присутні у ДДНФ функції. В інші клітинки записують нулі.

теорія множина алгебра функція

10. Основи математичної логіки

Як наука логіка виникла у IV ст. до н.е. у працях давньогрецького філософа Аристотеля, основоположника формальної логіки.

Ідею математизації логіки висловив ще у XVII ст. великий німецький вчений Лейбниць. Він сформулював задачу створення нової логіки, яка була б „мистецтвом обчислення”.

Тільки у середині XIX ст. ірландський математик Дж. Буль частково втілив у життя ідею Лейбниця.

Математична логіка займається формалізацією деякої області людського мислення, у тому числі з метою надання можливості написання програми для обчислювальної машини, яка в цьому розумінні отримає здатність міркувати.

11. Логіка висловлювань

Висловлення - це оповідальне речення, про яке можна сказати, істинне воно чи хибне, але не те й інше водночас.

Істина або хибність, яка приписана деякому висловленню, називається істиннісним значенням цього висловлення. Позначається: „Істина” - І, Т (True) або 1, „Хибність” - Х, F (False) або 0.

Атомами (елементарними висловлюваннями) називаються висловлення, які відповідають простим оповідальним реченням, тобто не мають складових частин.

Логіка висловлювань - це алгебраїчна структура ({X,I},,, ,,~,X,I) з носієм - війковою множиною {X: ”Хибність”, I: ”Істина”}, операціями - логічними зв'язками ( - кон'юнкція , - диз'юнкція, - заперечення, - імплікація, ~ - еквівалентність) і константами: Х - хибність і І - істина.

У логіці висловлювань правильно побудована формула визначається рекурсивно так:

1. Атом є формула.

2. Якщо А і В - формули, то (АВ), (АВ), (АВ), (А~В) і А - також формули.

3. Ніяких формул, крім породжених вказаними вище правилами, не існує.

12. Логіка першого порядку (ЛПП)

У деяких задачах постає необхідність удосконалити логіку висловлень з тим, щоб вона повніше пояснювала здібності людини робити логічні висновки. Для цього до логіки предикатів введено додаткові, нові порівняно з логікою висловлювань логічні поняття, а саме: терм, предикат і квантор.

Визначено деякий предикат, якщо:

а) задана деяка (довільна) множина М, що називається областю визначення предиката (предметна область);

б) фіксована множина {0,1}, що називається областю значень;

в) вказане правило, за допомогою якого кожному елементу, що взятий з предметної області, ставиться у відповідність один з двох елементів з області значень.

Предикат Р, що має n аргументів, називається n-місним предикатом, позначається P(x1,x2,…,xn).

Кількість аргументів предиката P(x1,x2,…,xn) називається його порядком.

Аргументи предиката називаються термами. Терм визначається рекурсивно так:

1. Константа є терм.

2. Змінна є терм.

3. Якщо f є n-місним функціональним символом, а t1,t2,…,tn - терм, то f(t1,t2,…,tn) є терм.

4. Ніяких термів, крім породжених за допомогою вказаних вище правил, не існує.

Нехай Р(х) - предикат, визначений на М. Висловлення „для всіх хМ, Р(х) істинне” позначається хР(х). Знак називається квантором загальності.

Висловлення „існує таке хМ, що Р(х) істинне” позначається хР(х), де знак називається квантором існування.

Всі закони і тотожності, справедливі у логіці висловлень, залишаються справедливими і у логіці предикатів. Крім того, у логіці предикатів існують додаткові закони, призначені для еквівалентного перетворення формул, що містять квантори та змінні.

Правильно побудованими формулами логіки предикатів називаються формули, які можна рекурсивно визначити так:

1. Атом є формулою.

2. Якщо F і G - формули, то (F), (FG), (FG), (FG), (F~G) також є формулами.

3. Якщо F - формула, а x - вільна змінна, то (x)F і (x)F теж формули.

4. Ніяких формул, крім породжених вказаними вище правилами, не існує.

Частина формули, на яку поширюється дія квантора, називається областю дії квантора.

Формула F в логіці предикатів знаходиться у випередженій нормальній формі (ВНФ) тоді і тільки тоді, коли вона може бути зображена у вигляді (Q1x1)…(Qnxn)(M), де кожне (Q1x1), i=1,…,n, є або (x), або (x), а M - формула, що не містить кванторів. Причому (Q1x1)…(Qnxn) називається префіксом, а М - матрицею формули F.

13. Основні поняття теорії графів

Граф - це упорядкована пара множин {V,E}, де V - множина вершин,
E - множина ребер. Графи підрозділяються на орієнтовані й неорієнтовані.

Виділяють такі види графів: порожній, повний, тотожний, симетричний, регулярний (однорідний), дуальний, нуль-граф, псевдограф, мультиграф.

Графи можна задати:

- графічно;

- переліком елементів;

- матрицею суміжності;

- матрицею інциденцій.

14. Ейлерові та гамільтонові ланцюги і цикли

Прийнято пов'язувати зародження теорії графів як математичної дисципліни з роботою Леонарда Ейлера 1736 р., у якій знайдено умову існування у зв'язному графі циклу, що містить всі ребра графа (без повторень). Такий цикл тепер називається ейлеровим. Як показує простий приклад, є графи, що не містять ейлерові цикли.

Гамільтоновим циклом у графі G=(X,Y) називається простий цикл Q=(X,Y0), який містить всі вершини графа, незалежно від того, чи є G орієнтованим. Вимога простоти циклу є принциповою: за гамільтоновим циклом Q можна обійти всі вершини х графа G, відвідуючи кожну проміжну (тобто не початкову і не кінцеву) вершину тільки один раз. Сам граф G, в якому існує гамільтонів цикл, називається гамільтоновим графом.

15. Планарність графів

Граф G=(X,Y) називається повним, якщо він не містить петель і кратних ребер, а також кожна пара вершин суміжна. Повний граф позначається Kn, де n - кількість вершин.

Дводольним графом називається граф, у якого множину вершин можна розбити на дві непересічні підмножини так, що ребра з'єднують вершини з різних підмножин. Повний дводольний граф - це граф, у якого будь-які дві вершини, що входять у різні множини вершин, суміжні. Повний дводольний граф позначається Km,n, де m та n - кількість вершин у кожній з долів.

Граф G є плоским, якщо його ребра перетинаються лише у вершинах.

Граф G1 є планарним, якщо існує ізоморфний до нього граф G, який є плоским.

Графи К5 і К3,3 відіграють фундаментальну роль у теорії планарності. Їх називають графами Понтрягіна-Курантовського. Граф G1 є планарним лише тоді, коли він не містить підграфів Понтрягіна-Курантовського.

16. Відстані на графах

Найменша довжина ланцюга, що з'єднує вершини a і b графа G, називається відстанню між ними. Позначається d(a,b).

Відстань має властивості, що задовольняють аксіомам метрики.

1. Якщо між вершинами a і b існує відстань, то вона більше нуля, причому відстань від однієї вершини до цієї ж вершини дорівнює нулю.

d(a,b)0;

d(a,a)=0.

2. Відстань між вершинами a і b дорівнює відстані між вершинами b і a.

d(a,b)=d(b,a).

3. Якщо існує три вершини a, b і c, причому c знаходиться між вершинами a і b, то відстань між вершинами a і b буде менше чи дорівнюватиме сумі відстаней між вершинами a і c та вершинами c і b.

d(a,c)+ d(c,b) d(a,b).

У деяких графах ребрам приписані числові характеристики (пропускна здатність, ціна, вага, довжина). У цих випадках довжиною ланцюга є сума числових характеристик ребер, що входять у ланцюг. Відстанню між a і b буде довжина найкоротшого ланцюга. Задачі відшукання найкоротших відстаней між вершинами графа (мережі) із заданими вагами ребер часто зустрічаються на практиці і мають очевидний економічний зміст. Це саме можна сказати і про задачі пошуку оптимальних шляхів в орієнтованих мережах. Один з ефективних алгоритмів розв'язку таких задач - алгоритм Дейкстри.

17. Дерева

Зв'язний граф Т без циклів називається деревом. Орієнтація може не враховуватися, і тоді говорять про ребра дерева yi. Якщо орієнтація враховується, то говорять про дуги дерева, а саме дерево називається орієнтованим, наприклад, дерево логічних можливостей, генеалогічне дерево. Формула А. Келі (1897 р.). Число n позначених дерев з n вершинами дорівнює nn-2.

Основними операціями над деревами є кодування та декодування. Ці операції використовуються для відображення дерев у пам'яті комп'ютера.

Існує три способи обходу дерев:

- „у глибину”;

- „у шир”;

- кінцевий порядок обходу.

18. Транспортні мережі

Такий граф є зручною моделлю при дослідженні цілого ряду задач у транспорті, зв'язку та інших областях, пов'язаних з дійсним або уявним рухом товарів, інформації або людей. Введемо визначення і позначення, типові для цього кола питань.

Транспортна мережа - це зв'язний орієнтований граф без петель і паралельних ребер, у якому:

1. Є тільки одна вершина, в яку не заходить жодна дуга, яка називається витоком xs.

2. Є тільки одна вершина, з якої не виходить жодна дуга, яка називається стоком xt.

3. Кожній дузі присвоєна числова характеристика , яка називається пропускною здатністю дуги u.

Зазначимо, що потоки у неорієнтованих графах можна зобразити у вигляді потоків у відповідних орієнтованих; потоки у незв'язних графах можуть вивчатися покомпонентно; потік у петлі не впливає на розподіл потоку між вершинами.

Размещено на Allbest.ru