Множества (преговор)
Множество е основополагащо понятие — за него няма дефиниция. Описваме го чрез друго основополагащо понятие — елемент. Елемент може да е всеки реален или абстрактен обект; за нас — стойности на числовите типове, низове и другите обекти от програмирането.
Всяко множество се определя от елементите си. Най-просто е да ги изпишем между къдрави скоби: двоичните цифри B = {0,1}, десетичните цифри D = {0,1,2,3,4,5,6,7,8,9}.
a ∈ M— елементът a принадлежи на M;a ∉ M— не принадлежи. Трета възможност няма.M ⊆ N— M е подмножество на N: всеки елемент на M е и елемент на N.- Ако
M ⊆ NиN ⊆ M— множествата съвпадат:M = N. - Елементите не се повтарят и не са подредени:
{0,0,0,1},{0,1},{1,0}са едно и също множество.
Операции между множества
| Операция | Означение | Резултат | Пример |
|---|---|---|---|
| Обединение | A ∪ B | елементите на A ИЛИ на B (вкл. и на двете) | {0,1,3,5,7} ∪ {0,3,4,5} = {0,1,3,4,5,7} |
| Сечение | A ∩ B | елементите, принадлежащи И на A, И на B | {0,1,3,5,7} ∩ {0,3,4,5} = {0,3,5} |
| Разлика | A − B | елементите на A, които НЕ са в B | {0,1,3,5,7} − {0,3,4,5} = {1,7} |
| Допълнение | Ā | елементите на универсалното U, които не са в A | Ē = {1,3,5,7,9} при U = D |
Декартово произведение
Операцията с най-голям интерес за нас носи името на френския математик и философ Рьоне Декарт. Множество от два елемента, в което единият е избран за първи, наричаме наредена двойка — (a, b).
Декартово произведение A × B
Множеството от всички наредени двойки (a, b), където a ∈ A и b ∈ B.
Познат пример е ортогоналната координатна система: всяка точка в равнината е наредена двойка (x, y). Друг: шахматната дъска — колони C = {a,b,c,d,e,f,g,h} и редове R = {1,…,8}; 64-те клетки са двойките на C × R.
Обобщение: декартовото произведение A₁ × A₂ × … × Aₙ е множеството от всички наредени n-торки (a₁, a₂, …, aₙ), където aᵢ ∈ Aᵢ. Ако множествата са крайни, броят на елементите е произведението на броевете: |A₁ × … × Aₙ| = |A₁|·|A₂|·…·|Aₙ|.
Бележка
Образуващите множества не е задължително да са от един и същ вид — при шахматната дъска едното е от букви, другото от цифри.
Релации
Релация
Всяко подмножество R на декартовото произведение A₁ × A₂ × … × Aₙ наричаме n-мерна (n-местна) релация. Всяко от множествата в произведението наричаме домейн на релацията.
За информатиката домейните са множества от стойности от някой тип. Наредената n-торка от типовете на домейните T_R = (type₁, type₂, …, typeₙ) наричаме сигнатура на релацията.
Примери за 2-местни релации от математиката: правата x = y, окръжността x² + y² = 1 — всяко множество от точки в равнината е релация. Такива са и релациите за сравняване: при T = {0,1,2} релацията R< = {(0,1), (0,2), (1,2)}.
Мостът към базите от данни
Нека N са естествените числа, I — българските собствени имена, F — фамилиите, B — възможните дати на раждане, P — населените места, S — двата пола. Тогава списъкът на учениците в класа (номер, име, фамилия, дата и място на раждане, пол) е 6-местна релация над N × I × F × B × P × S. Точно такива релации са таблиците в релационната БД!
Какво трябва да запомниш
- Множеството няма повтарящи се елементи и няма ред на елементите.
- Операции: обединение ∪, сечение ∩, разлика −, допълнение до универсалното.
- Декартово произведение = всички наредени n-торки; броят е произведение на броевете.
- Релация = подмножество на декартово произведение; множествата са ѝ домейни.
- Сигнатура = наредената n-торка от типовете на домейните.
- Таблицата „ученици в класа“ е 6-местна релация — оттам идва „релационен модел“.