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

Вступ

Лекція 1

Основні способи подання інформації є дискретними: слова і інші конструкції мов і граматик, табличні дані, дані статистичні, тощо. Переклад слова дискрет – частка, тобто, дискретна інформація – це інформація у вигляді виділених часток. Математичні методи обробки, аналізу та перетворень і є предметом дискретної математики (іноді вживаються назви «скінчена математика», або навіть «конкретна математика»).

Список позначок:

N – множина натуральних чисел;

Z – множина цілих чисел;

N_ч - множина парних чисел;

R – множина дійсних чисел;

Q – множина раціональних чисел;

R₊ – множина додатних чисел;

| M | - потужність множини М;

U – універсальна множина;

Æ - пуста множина;

A Í B – нестроге включення;

A Ì B – строге включення;

x ÎA – елемент належить множині;

x ÏA – …не належить…;

"х – будь-який елемент;

$ х – існує певний елемент;

A ÇB – перетин множин;

AÈB – об’єднання множин

1 Множини.

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

Теорія множин разом з іншими розділами дискретної математики має безліч корисних застосувань у програмуванні. Вона використовується для побудови СУБД, під час побудови та організації роботи комп’ютерних мереж, зокрема мережі Internet.

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

Множини позначають великими латинськими літерами, а елементи множин – малими. Наприклад запис A={a, b, d, h} означає, що множина A складається з 4-х елементів a, b, d, h. В загальному вигляді твердження, що скінченна множина А складається з n елементів, записується так: A={a₁, а₂, а₃, …,а_n}. Належність елемента множині позначається символом Î: x ÎA (читають: елемент х належить множині А). в противному випадку позначають x ÏA (читають: елемент х не належить множині А).

Далі використовують такі загальноприйняті позначення основних числових множин:

N – множина натуральних чисел, N={1, 2, 3, …};

Z – множина цілих чисел, Z={…-2, -1, 0, 1, 2 …};;

R – множина дійсних чисел, будь-яке раціональне число можна зобразити у вигляді нескінченного десяткового дробу a,b₁b₂b₃…b_n…, де aÎZ, b_kÎ{0, 1, …9}.;

Q – множина раціональних чисел, будь-яке раціональне число можна зобразити у вигляді звичайного дробу a/b, де aÎ Z, bÎN;

Елементами множини можуть бути інші множини, тоді ці елементи позначають великими літерами.

Приклад. A={D, C}, D={a, b}, C={c, d, e}. При цьому DÎA, CÎA, але a Ï A, dÏА.

Прикдад. E={{1, 2}, 3}. Цей запис означає, що множина Е містить два елементи: множину {1, 2} і елемент 3.

Множина називається скінченною, якщо вона містить скінченне число елементів, і нескінченною, якщо вона містить необмежене число елементів.

Приклад. Множина A={1, 2, 3, 4, 5, 6, 7, 8, 9, 0}} цифр в десятковій системі числення скінченна, а множина точок кола нескінченна.

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

Наприклад. C=<1, 2, 3>.

A=<a₁, a₂, …, a_n>, nÎN.

В=(c, d, e).

Приклад. Розглянемо упорядковану множину А=(х, у) географічних координат довготи х і широти у. Якщо довготу і широту поміняти місцями, можна потрапити в іншу точку світу.

Приклад. Розглянемо множину A=<a₁, a₂, …, a_n>, nÎN, де a_k – середній бал студента групи, номер якого по журналу k. Якщо переставити місцями два елементи множини, якомусь студенту це піде на користь, але другий, отримавши чужий нижчий бал буде проти таких змін.

Вказати порядковий номер для всякого дійсного числа неможливо і порядок у R задається за допомогою порівнянь < i ≤.

1. Множину можна задати простим переліком елементів A={a₁, а₂, а₃, …,а_n}.

Приклад. Множину відмінників в групі позначимо F={Агеєв, Бурков, Суслов, Кукушкін}.

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

Приклад. N₁₀={x | xÎN, x<10} – множина натуральних чисел, менших за 10.

Властивості елементів можуть бути задані не формально, а за допомогою опису на природній мові.

Приклад. Множина S студентів групи К-1-09, які отримують стипендію.

Приклад. Коло – геометричне місце точок площини, рівновіддалених від центра даної точки цієї площини.

3. Множина може бути задана рекурсивно(породжуючою процедурою)- вказівкою способу послідовного породження її елементів.

Приклад. Відома з шкільного курсу арифметична (геометрична) прогресія. а₁=3,7 а_k=a_k-1+2,4. Тобто кожен елемент знаходимо, додаючи до попереднього 2,4.

При заданні множин можуть виникати помилки та протиріччя. Множина задана коректно, якщо для будь-якого елемента можна визначити, належить він множині чи ні.

Приклад. Визначення множини А як множини, що містить будь-які п’ять натуральних чисел, не є коректним, оскільки неможливо визначити точно елементи А.

Приклад. Множина С всіх простих чисел визначена коректно. Для будь-якого натурального числа можна перевірити, чи є воно простим. Хоча іноді це зробити складно, наприклад, чи просте число 86958476923751?

Приклад. Множина всіх динозаврів, що жили на Землі, є множина, що задана правильно. Хоча практично неможливо визначити елементи цієї множини, але теоретично ясно, що якщо тварина, яка будь-коли жила на Землі, є динозавром, то вона належить до цієї множини.

Некоректність задання множини часто пов’язана з протиріччям при перевірці належності деякого елемента множині. Наведемо два класичні приклади.

Приклад. Визначимо множину М як множину всіх множин, які не є елементами самих себе. Але тоді не можна з’ясувати, чи є сама множина М елементом множини М. Якщо так, то приходимо до протиріччя, оскільки М містить як елементи тільки множини, які не є елементами мамих себе. Якщо множина М не є елементом самої себе, то тоді, за визначенням, вона повинна бути елементом множини М, що є протиріччям.

Приклад. Єдиний перукар у місті В визначає множину К – мешканців, яких він повинен голити, як сукупність всіх тих мешканців міста В, які не голяться самі. Але тоді для самого перукаря виходить протиріччя і при включенні його до множини К, і при віднесенні його до мешканців, які голяться самі.

Такі протиріччя називають парадоксами і вивчають в математичній логіці.

Дата добавления: 2015-05-10