Історія
визначення 1
Леонарда Ейлера поставили запитання: чи можна, прогулюючись по Кенігсберга, оминути через всі мости міста, двічі не проходячи через жоден з них. План міста з сімома мостами додавався.
У листі знайомому італійському математику Ейлер дав коротке і красиве рішення проблеми кенігсберзькими мостів: при такому розташуванні завдання нерозв'язна. При цьому він вказав, що питання здалося йому цікавим, тому що «Для його вирішення недостатні ні геометрія, ні алгебра ...».
При вирішенні багатьох завдань Л. Ейлер зображував безлічі за допомогою кіл, тому вони і отримали назву «Кола Ейлера». Цим методом ще раніше користувався німецький філософ і математик Готфрід Лейбніц, який використовував їх для геометричного пояснення логічних зв'язків між поняттями, але при цьому частіше використовував лінійні схеми. Ейлер ж досить грунтовно розвинув метод. Особливо знаменитими графічні методи стали завдяки англійському логіку і філософу Джону Венну, який ввів діаграми Венна і подібні схеми часто називають діаграмами Ейлера-Венна. Використовуються вони в багатьох областях, наприклад, в теорії множин, теорії ймовірності, логіці, статистиці та інформатики.
Принцип побудови діаграм
До сих пір діаграми Ейлера-Венна широко використовують для схематичного зображення всіх можливих перетинів декількох множин. На діаграмах зображують все $ 2 ^ n $ комбінацій n властивостей. Наприклад, при $ n = 3 $ на діаграмі зображують три кола з центрами в вершинах рівностороннього трикутникаі однаковим радіусом, який наближено дорівнює довжині сторони трикутника.
Логічні операції задають таблиці істинності. На діаграмі зображується коло з назвою безлічі, яку він представляє, наприклад, $ A $. Область в середині кола $ A $ буде відображати істинність виразу $ A $, а область поза колом - брехня. Для відображення логічної операції заштриховують тільки ті області, в яких значення логічної операції при безлічі $ A $ і $ B $ істинні.
Наприклад, кон'юнкція двох множин $ A $ і $ B $ істинна тільки в тому випадку, коли обидва безлічі істинні. В такому випадку на діаграмі результатом кон'юнкції $ A $ і $ B $ буде область в середині кіл, яка одночасно належить множині $ A $ і безлічі $ B $ (перетину множин).
Малюнок 1. Кон'юнкція множин $ A $ і $ B $
Використання діаграм Ейлера-Венна для доказу логічних рівностей
Розглянемо, як застосовується метод побудови діаграм Ейлера-Венна для доказу логічних рівностей.
Доведемо закон де Моргана, який описується рівністю:
Доведення:
Малюнок 4. Інверсія $ A $
Малюнок 5. Інверсія $ B $
Малюнок 6. Кон'юнкція інверсій $ A $ і $ B $
Після порівняння області для відображення лівої і правої частини бачимо, що вони рівні. З цього випливає справедливість логічної рівності. Закон де Моргана доведений за допомогою діаграм Ейлера-Венна.
Рішення завдання пошуку інформації в Інтернет за допомогою діаграм Ейлера-Венна
Для здійснення пошуку інформації в Інтернет зручно використовувати пошукові запити з логічними зв'язками, аналогічними за змістом спілкам "і", "або" російської мови. Сенс логічних зв'язок стає більш зрозумілим, якщо проілюструвати їх за допомогою діаграм Ейлера-Венна.
приклад 1
У таблиці наведено приклади запитів до пошукового сервера. Кожен запит має свій код - буква від $ A $ до $ B $. Потрібно розташувати коди запитів в порядку зменшення кількості знайдених сторінок по кожному запиту.
Малюнок 7.
Рішення:
Побудуємо для кожного запиту діаграму Ейлера-Венна:
Малюнок 8.
відповідь:БВА.
Рішення логічного змістовної задачі за допомогою діаграм Ейлера-Венна
приклад 2
За зимові канікули з $ 36 $ учнів класу $ 2 $ не були ні в кіно, ні в театрі, ні в цирку. У кіно сходило $ 25 $ людина, в театр - $ 11 $, в цирк - $ 17 $ людина; і в кіно, і в театрі - $ 6 $; і в кіно і в цирк - $ 10 $; і в театр і в цирк - $ 4 $.
Скільки людей побувало і в кіно, і в театрі, і в цирку?
Рішення:
Позначимо кількість хлопців, які побували і в кіно, і в театрі, і в цирку - $ x $.
Побудуємо діаграму і дізнаємося кількість хлопців в кожній області:
Малюнок 9.
Чи не були ні в театрі, ні в кіно, ні в цирку - $ 2 $ чол.
Значить, $ 36 - 2 = 34 $ чол. побували на заходах.
У кіно і театр сходило $ 6 $ чол., Значить, тільки в кіно і театр ($ 6 - x) $ чол.
У кіно і цирк сходило $ 10 $ чол., Значить, тільки в кіно і цирк ($ 10 - x $) чол.
В театр і цирк сходило $ 4 $ чол., Значить, тільки в театрі і цирк ($ 4 - x $) чол.
У кіно сходило $ 25 $ чол., Значить, з них тільки в кіно сходило $ 25 - (10 - x) - (6 - x) - x = (9 + x) $.
Аналогічно, тільки в театр сходило ($ 1 + x $) чол.
Тільки в цирк сходило ($ 3 + x $) чол.
Отже, сходили в театр, кіно і цирк:
$ (9 + x) + (1 + x) + (3 + x) + (10-x) + (6-x) + (4-x) + x = 34 $;
Тобто тільки одна людина сходив і в театр, і в кіно, і в цирк.
подібні документи
Відновлення графів за заданим матрицями суміжності вершин. Побудова для кожного графа матриці суміжності ребер, инцидентности, досяжності, контрдостіжімості. Пошук композиції графів. Визначення локальних ступенів вершин графа. Пошук бази графів.
лабораторна робота, доданий 09.01.2009
Опис заданого графа множинами вершин V і дуг X, списками суміжності, матрицею інцидентності і суміжності. Матриця ваг відповідного неориентированного графа. Визначення дерева найкоротших шляхів за алгоритмом Дейкстри. Пошук дерев на графі.
курсова робота, доданий 30.09.2014
Поняття "граф" і його матричне уявлення. Властивості матриць суміжності і інцидентності. Властивості маршрутів, ланцюгів і циклів. Завдання знаходження центральних вершин графа, його метричні характеристики. Додаток теорії графів в областях науки і техніки.
курсова робота, доданий 09.05.2015
Алгоритм переходу до графічного поданням для неорієнтованого графа. Кількість вершин неорієнтованого графа. Читання з матриці смежностей. Зв'язки між вершинами в матриці. Завдання координат вершин в залежності від кількості секторів.
лабораторна робота, доданий 29.04.2011
Математичний опис системи автоматичного управлінняза допомогою графів. Складання графа і його перетворення, позбавлення від диференціалів. Оптимізації орієнтованих і неорієнтованих графів, складання матриць суміжності і інцидентності.
лабораторна робота, доданий 11.03.2012
Орієнтовані і неорієнтовані графи: Загальна характеристика, Спеціальні вершини і ребра, полустепені вершин, матриці суміжності, інцидентності, досяжності, зв'язності. Числові характеристики кожного графа, обхід в глибину і в ширину, базис циклів.
курсова робота, доданий 14.05.2012
Перевірка справедливості тотожностей або включень з використанням алгебри множин і діаграм Ейлера-Венна. Зображення графа і матриці відносини, що володіє властивостями рефлексивності, транзитивності і антісіммерічності. Вивчення неориентированного графа.
контрольна робота, доданий 05.05.2013
Безліччю іменується деяка сукупність елементів, об'єднаних за будь-якою ознакою. Над множинами визначають операції, багато в чому подібні з арифметичними. Операції над множинами інтерпретують геометрично за допомогою діаграм Ейлера-Венна.
реферат, доданий 03.02.2009
Побудова діаграми псевдографом, матриці інцидентності і матриці сусідства вершин. Відновлення дерева по вектору за допомогою алгоритму Прюфера. Побудова таблиці істинності для функції і досконалої кон'юнктівной і диз'юнктивній нормальної форм.
контрольна робота, доданий 25.09.2013
Способи вирішення завдань дискретної математики. Розрахунок найкоротшого шляху між парами всіх вершин в орієнтованому і неорієнтованому графах за допомогою використання алгоритму Флойда. Аналіз завдання і методів її вирішення. Розробка і характеристика програми.
Історія
визначення 1
Леонарда Ейлера поставили запитання: чи можна, прогулюючись по Кенігсберга, оминути через всі мости міста, двічі не проходячи через жоден з них. План міста з сімома мостами додавався.
У листі знайомому італійському математику Ейлер дав коротке і красиве рішення проблеми кенігсберзькими мостів: при такому розташуванні завдання нерозв'язна. При цьому він вказав, що питання здалося йому цікавим, тому що «Для його вирішення недостатні ні геометрія, ні алгебра ...».
При вирішенні багатьох завдань Л. Ейлер зображував безлічі за допомогою кіл, тому вони і отримали назву «Кола Ейлера». Цим методом ще раніше користувався німецький філософ і математик Готфрід Лейбніц, який використовував їх для геометричного пояснення логічних зв'язків між поняттями, але при цьому частіше використовував лінійні схеми. Ейлер ж досить грунтовно розвинув метод. Особливо знаменитими графічні методи стали завдяки англійському логіку і філософу Джону Венну, який ввів діаграми Венна і подібні схеми часто називають діаграмами Ейлера-Венна. Використовуються вони в багатьох областях, наприклад, в теорії множин, теорії ймовірності, логіці, статистиці та інформатики.
Принцип побудови діаграм
До сих пір діаграми Ейлера-Венна широко використовують для схематичного зображення всіх можливих перетинів декількох множин. На діаграмах зображують все $ 2 ^ n $ комбінацій n властивостей. Наприклад, при $ n = 3 $ на діаграмі зображують три кола з центрами в вершинах рівностороннього трикутника і однаковим радіусом, який наближено дорівнює довжині сторони трикутника.
Логічні операції задають таблиці істинності. На діаграмі зображується коло з назвою безлічі, яку він представляє, наприклад, $ A $. Область в середині кола $ A $ буде відображати істинність виразу $ A $, а область поза колом - брехня. Для відображення логічної операції заштриховують тільки ті області, в яких значення логічної операції при безлічі $ A $ і $ B $ істинні.
Наприклад, кон'юнкція двох множин $ A $ і $ B $ істинна тільки в тому випадку, коли обидва безлічі істинні. В такому випадку на діаграмі результатом кон'юнкції $ A $ і $ B $ буде область в середині кіл, яка одночасно належить множині $ A $ і безлічі $ B $ (перетину множин).
Малюнок 1. Кон'юнкція множин $ A $ і $ B $
Використання діаграм Ейлера-Венна для доказу логічних рівностей
Розглянемо, як застосовується метод побудови діаграм Ейлера-Венна для доказу логічних рівностей.
Доведемо закон де Моргана, який описується рівністю:
Доведення:
Малюнок 4. Інверсія $ A $
Малюнок 5. Інверсія $ B $
Малюнок 6. Кон'юнкція інверсій $ A $ і $ B $
Після порівняння області для відображення лівої і правої частини бачимо, що вони рівні. З цього випливає справедливість логічної рівності. Закон де Моргана доведений за допомогою діаграм Ейлера-Венна.
Рішення завдання пошуку інформації в Інтернет за допомогою діаграм Ейлера-Венна
Для здійснення пошуку інформації в Інтернет зручно використовувати пошукові запити з логічними зв'язками, аналогічними за змістом спілкам "і", "або" російської мови. Сенс логічних зв'язок стає більш зрозумілим, якщо проілюструвати їх за допомогою діаграм Ейлера-Венна.
приклад 1
У таблиці наведено приклади запитів до пошукового сервера. Кожен запит має свій код - буква від $ A $ до $ B $. Потрібно розташувати коди запитів в порядку зменшення кількості знайдених сторінок по кожному запиту.
Малюнок 7.
Рішення:
Побудуємо для кожного запиту діаграму Ейлера-Венна:
Малюнок 8.
відповідь:БВА.
Рішення логічного змістовної задачі за допомогою діаграм Ейлера-Венна
приклад 2
За зимові канікули з $ 36 $ учнів класу $ 2 $ не були ні в кіно, ні в театрі, ні в цирку. У кіно сходило $ 25 $ людина, в театр - $ 11 $, в цирк - $ 17 $ людина; і в кіно, і в театрі - $ 6 $; і в кіно і в цирк - $ 10 $; і в театр і в цирк - $ 4 $.
Скільки людей побувало і в кіно, і в театрі, і в цирку?
Рішення:
Позначимо кількість хлопців, які побували і в кіно, і в театрі, і в цирку - $ x $.
Побудуємо діаграму і дізнаємося кількість хлопців в кожній області:
Малюнок 9.
Чи не були ні в театрі, ні в кіно, ні в цирку - $ 2 $ чол.
Значить, $ 36 - 2 = 34 $ чол. побували на заходах.
У кіно і театр сходило $ 6 $ чол., Значить, тільки в кіно і театр ($ 6 - x) $ чол.
У кіно і цирк сходило $ 10 $ чол., Значить, тільки в кіно і цирк ($ 10 - x $) чол.
В театр і цирк сходило $ 4 $ чол., Значить, тільки в театрі і цирк ($ 4 - x $) чол.
У кіно сходило $ 25 $ чол., Значить, з них тільки в кіно сходило $ 25 - (10 - x) - (6 - x) - x = (9 + x) $.
Аналогічно, тільки в театр сходило ($ 1 + x $) чол.
Тільки в цирк сходило ($ 3 + x $) чол.
Отже, сходили в театр, кіно і цирк:
$ (9 + x) + (1 + x) + (3 + x) + (10-x) + (6-x) + (4-x) + x = 34 $;
Тобто тільки одна людина сходив і в театр, і в кіно, і в цирк.
Деякі завдання зручно і наочно вирішувати за допомогою діаграм Ейлера-Венна. Наприклад, завдання на безлічі. Якщо Ви не знаєте, що таке діаграми Ейлера-Венна і як їх будувати, то спочатку прочитайте.
Тепер розберемо типові завдання про множини.
Завдання 1.
У школі з поглибленим вивченняміноземних мов провели опитування серед 100 учнів. Учням поставили запитання: "Які іноземні мовиви вивчаєте? ". З'ясувалося, що 48 учнів вивчають англійську, 26 - французьку, 28 - німецьку. 8 школярів вивчають англійську та німецьку, 8 - англійська і французька, 13 - французьку та німецьку. 24 школяра не вивчають ні англійська, ні французька, ні німецький. Скільки школярів, які пройшли опитування, вивчають одночасно три мови: англійська, французька та німецька?
Відповідь: 3.
Рішення:
- безліч школярів, що вивчають англійську ( "А");
- безліч школярів, хто вивчає французьку ( "Ф");
- безліч школярів, які вивчають німецьку ( "Н").
Зобразимо за допомогою діаграми Ейлера-Венна те, що нам дано за умовою.
Позначимо шукану область А = 1, Ф = 1, Н = 1 як "х" (в таблиці нижче область №7). Висловимо інші області через х.
0) Область А = 0, Ф = 0, Н = 0: 24 школяра - дано за умовою задачі.
1) Область А = 0, Ф = 0, Н = 1: 28- (8-х + х + 13-х) = 7 + х школярів.
2) Область А = 0, Ф = 1, Н = 0: 26- (8-х + х + 13-х) = 5 + х школярів.
3) Область А = 0, Ф = 1, Н = 1: 13-х школярів.
4) Область А = 1, Ф = 0, Н = 0: 48- (8-х + х + 8-х) = 32 + х школярів.
5) Область А = 1, Ф = 0, Н = 1: 8-х школярів.
6) Область А = 1, Ф = 1, Н = 0: 8-х школярів.
| № області | А |
Ф |
Н |
кількість школярів |
|---|---|---|---|---|
| 0 | 0 |
0 |
0 |
24 |
| 1 | 0 |
0 |
1 |
7 + х |
| 2 | 0 |
1 |
0 |
5 + х |
| 3 | 0 |
1 |
1 |
13-х |
| 4 | 1 |
0 |
0 |
32 + х |
| 5 | 1 |
0 |
1 |
8-х |
| 6 | 1 |
1 |
0 |
8-х |
| 7 | 1 |
1 |
1 |
х |
Визначимо х:
24 + 7 + (х + 5) + х + (13-х) + (32 + х) + (8-х) + (8-х) + х = 100.
х = 100- (24 + 7 + 5 + 13 + 32 + 8 + 8) = 100-97 = 3.
Отримали, що 3 школяра вивчають одночасно три мови: англійська, французька та німецька.
Так буде виглядати діаграма Ейлера-Венна при відомому х:
Завдання 2.
На олімпіаді з математики школярам запропонували вирішити три завдання: одну з алгебри, одну з геометрії, одну з тригонометрії. В олімпіаді взяли участь 1000 школярів. Результати олімпіади були наступні: завдання з алгебри вирішили 800 учасників, з геометрії - 700, з тригонометрії - 600. 600 школярів вирішили завдання з алгебри і геометрії, 500 - з алгебри і тригонометрії, 400 - з геометрії і тригонометрії. 300 осіб вирішили завдання з алгебри, геометрії і тригонометрії. Скільки школярів не вирішило жодної задачі?
Відповідь: 100.
Рішення:
Спочатку визначимо безлічі і введемо позначення. Їх три:
- безліч завдань з алгебри ( "А");
- безліч завдань з геометрії ( "Г");
- безліч завдань з тригонометрії ( "Т").
Зобразимо те, що нам треба знайти:
Визначимо кількість школярів для всіх можливих областей.
Позначимо шукану область А = 0, Г = 0, Т = 0 як "х" (в таблиці нижче область №0).
Знайдемо інші області:
1) Область А = 0, Г = 0, Т = 1: школярів немає.
2) Область А = 0, Г = 1, Т = 0: школярів немає.
3) Область А = 0, Г = 1, Т = 1: 100 школярів.
4) Область А = 1, Г = 0, Т = 0: школярів немає.
5) Область А = 1, Г = 0, Т = 1: 200 школярів.
6) Область А = 1, Г = 1, Т = 0: 300 школярів.
7) Область А = 1, Г = 1, Т = 1: 300 школярів.
Запишемо значення областей в таблицю:
| № області | А |
Г |
Т |
кількість школярів |
|---|---|---|---|---|
| 0 | 0 |
0 |
0 |
х |
| 1 | 0 |
0 |
1 |
0 |
| 2 | 0 |
1 |
0 |
0 |
| 3 | 0 |
1 |
1 |
100 |
| 4 | 1 |
0 |
0 |
0 |
| 5 | 1 |
0 |
1 |
200 |
| 6 | 1 |
1 |
0 |
300 |
| 7 | 1 |
1 |
1 |
300 |
Зобразимо значення для всіх областей за допомогою діаграми:
Визначимо х:
х = U- (A V Г V Т), де U-універсум.
A V Г V Т = 0 + 0 + 0 + 300 + 300 + 200 + 100 = 900.
Отримали, що 100 школярів не вирішило жодної задачі.
Завдання 3.
На олімпіаді з фізики школярам запропонували вирішити три завдання: одну з кінематики, одну з термодинаміки, одну з оптики. Результати олімпіади були наступні: завдання з кінематики вирішили 400 учасників, з термодинаміки - 350, з оптики - 300. 300 школярів вирішили завдання з кінематики та термодинаміки, 200 - з кінематики та оптиці, 150 - з термодинаміки і оптиці. 100 чоловік вирішили завдання з кінематики, термодинаміки і оптиці. Скільки школярів вирішило два завдання?
Відповідь: 350.
Рішення:
Спочатку визначимо безлічі і введемо позначення. Їх три:
- безліч завдань з кінематики ( "К");
- безліч завдань з термодинаміки ( "Т");
- безліч завдань з оптики ( "О").
Зобразимо за допомогою діаграми Ейлера-Венна те, що нам дано за умовою:
Зобразимо те, що нам треба знайти:
Визначимо кількість школярів для всіх можливих областей:
0) Область К = 0, Т = 0, О = 0: не визначено.
1) Область К = 0, Т = 0, О = 1: 50 школярів.
2) Область К = 0, Т = 1, О = 0: школярів немає.
3) Область К = 0, Т = 1, О = 1: 50 школярів.
4) Область К = 1, Т = 0, О = 0: школярів немає.
5) Область К = 1, Т = 0, О = 1: 100 школярів.
6) Область К = 1, Т = 1, О = 0: 200 школярів.
7) Область К = 1, Т = 1, О = 1: 100 школярів.
Запишемо значення областей в таблицю:
| № області | До |
Т |
Про |
кількість школярів |
|---|---|---|---|---|
| 0 | 0 |
0 |
0 |
- |
| 1 | 0 |
0 |
1 |
50 |
| 2 | 0 |
1 |
0 |
0 |
| 3 | 0 |
1 |
1 |
50 |
| 4 | 1 |
0 |
0 |
0 |
| 5 | 1 |
0 |
1 |
100 |
| 6 | 1 |
1 |
0 |
200 |
| 7 | 1 |
1 |
1 |
100 |
Зобразимо значення для всіх областей за допомогою діаграми:
Визначимо х.
х = 200 + 100 + 50 = 350.
Отримали, 350 школярів вирішило два завдання.
Завдання 4.
Серед перехожих провели опитування. Було поставлено питання: "Яке домашня тварина у Вас є?". За результатами опитування з'ясувалося, що у 150 людина є кішка, у 130 - собака, у 50 - пташка. У 60 чоловік є кішка і собака, у 20 - кішка і пташка, у 30 - собака і пташка. У 70 чоловік взагалі немає домашньої тварини. У 10 чоловік є і кішка, і собака, і пташка. Скільки перехожих взяли участь в опитуванні?
Відповідь: 300.
Рішення:
Спочатку визначимо безлічі і введемо позначення. Їх три:
- безліч людей, у яких є кішка ( "К");
- безліч людей, у яких є собака ( "С");
- безліч людей, у яких є пташка ( "П").
Зобразимо за допомогою діаграми Ейлера-Венна те, що нам дано за умовою:
Зобразимо те, що нам треба знайти:
Визначимо кількість осіб для всіх можливих областей:
0) Область К = 0, С = 0, П = 0: 70 осіб.
1) Область К = 0, С = 0, П = 1: 10 осіб.
2) Область К = 0, С = 1, П = 0: 50 осіб.
3) Область К = 0, С = 1, П = 1: 20 осіб.
4) Область К = 1, С = 0, П = 0: 80 осіб.
5) Область К = 1, Т = 0, О = 1: 10 осіб.
6) Область К = 1, Т = 1, О = 0: 50 осіб.
7) Область К = 1, Т = 1, О = 1: 10 осіб.
Запишемо значення областей в таблицю:
| № області | До |
C |
П |
кількість людина |
|---|---|---|---|---|
| 0 | 0 |
0 |
0 |
70 |
| 1 | 0 |
0 |
1 |
10 |
| 2 | 0 |
1 |
0 |
50 |
| 3 | 0 |
1 |
1 |
20 |
| 4 | 1 |
0 |
0 |
80 |
| 5 | 1 |
0 |
1 |
10 |
| 6 | 1 |
1 |
0 |
50 |
| 7 | 1 |
1 |
1 |
10 |
Зобразимо значення для всіх областей за допомогою діаграми:
Визначимо х:
х = U (універсум)
U = 70 + 10 + 50 + 20 + 80 + 10 + 50 + 10 = 300.
Отримали, що 300 осіб взяли участь в опитуванні.
Завдання 5.
На одну спеціальність в одному з ВУЗів надходило 120 чоловік. Абітурієнти здавали три іспити: з математики, з інформатики та російській мові. Математику здали 60 чоловік, інформатику - 40. 30 абітурієнтів здали математику і інформатику, 30 - математику і російську мову, 25 - інформатику і російську мову. 20 чоловік здали всі три іспити, а 50 осіб - провалили. Скільки абітурієнтів здали російську мову?
Людське мислення влаштовано так, що світ представляється що складається з окремих «об'єктів». Філософам давно відомо, що світ - єдине нерозривне ціле, і виділення в ньому об'єктів - це не більше ніж довільний акт нашого мислення, що дозволяє сформувати доступну для раціонального аналізу картину. Але як би там не було, виділення об'єктів і їх сукупностей - природний спосіб організації нашого мислення, тому не дивно, що він лежить в основі головного інструменту опису точного знання - математики.
Поняття множини належить до числа фундаментальних невизначених понять математики. Про безлічі відомо як мінімум, що воно складається з елементів. Для визначеності приймемо такі формулювання.
визначення. під безліччю Sбудемо розуміти будь-які збори певних і помітних між собою об'єктів, мислиме як єдине ціле. Ці об'єкти називаються елементами безлічі S.
визначення. Під безліччю розуміють об'єднання в єдине ціле визначених цілком розрізняються предметів (об'єктів), які при цьому називаються елементами утвореного ними безлічі.
Зазвичай безлічі позначають прописними буквами латинського алфавіту: A, B, C, ...; а елементи множин - малими літерами: a, b, c, … .
якщо об'єкт хє елементом множини М, То говорять, що хналежить М: х М. В іншому випадку говорять, що хне належить М: х М.
У цьому інтуїтивному визначенні, що належить німецькому математику Г. Кантор, істотним є та обставина, що збори предметів саме розглядається як один предмет, мислиться як єдине ціле. Що стосується самих предметів, які можуть входити в безліч, то щодо них існує значна свобода.
приклад 1
Це може бути безліч студентів, що навчаються в університеті, безліч простих чиселі т.д.
визначення. безліч Аназивається підмножиною множини В, Якщо будь-який елемент з Ає елементом В(Позначають). якщо Ає підмножиною Ві Вне є підмножиною А, То говорять, що Ає строгим (власним) підмножиною В(Позначають).
визначення. Безліч, що не містить елементів, називається порожнім (позначають Æ), воно є підмножиною будь-якої множини. безліч Uназивається універсальним, тобто всі розглянуті безлічі є його підмножиною.
Розглянемо два визначення рівності множин.
визначення. безлічі Аі Ввважаються рівними, якщо вони складаються з одних і тих же елементів, пишуть А = В, в іншому випадку А¹ В.
визначення. безлічі Аі Ввважаються рівними, якщо 
існують наступні способи завдання множин :
1) перерахуванням елементів: М = (a 1 , a 2 , …, a k} , Т. Е. Списком своїх елементів;
2) характеристичним предикатом: М = (x | P(x)} (Описом характеристичних властивостей, якими повинні володіти його елементи);
породжує процедурою: M = { x | x= f} , Яка описує спосіб отримання елементів безлічі з уже отриманих елементів або інших об'єктів. В такому випадку елементами безлічі є всі об'єкти, які можуть бути
1) побудовані за допомогою такої процедури. Наприклад, безліч всіх цілих чисел, які є ступенями двійки.
зауваження. При завданні множин перерахуванням позначення елементів зазвичай укладають в фігурні дужки і розділяють комами. Перерахуванням можна задавати тільки кінцеві безлічі (число елементів множини звичайно, в іншому випадку безліч називається нескінченним). Характеристичний предикат - це деяка умова, виражене у формі логічного твердження або процедури, що повертає логічне значення. Якщо для даного елемента умова виконана, то він належить визначається безлічі, в іншому випадку - не належить. Породжує процедура - це процедура, яка, будучи запущеною, породжує деякі об'єкти, які є елементами визначається безлічі. Нескінченні безлічі задаються характеристичним предикатом або породжує процедурою.
приклад 2
1) М = (1, 2, 3, 4)- перерахування елементів множини.
2) - характеристичний предикат.
визначення. Потужність кінцевого безлічі А- це число його елементів.
Потужність безлічі позначають: | A|.
приклад 3
|| = 0; |{}| = 1.
визначення. Безлічі називаються рівнопотужними, якщо їх потужності збігаються.
визначення. Безліч всіх підмножин множини А називається булеані P (A).
Відомо, що якщо безліч Амістить nелементів, то безліч P(A) містить 2 nелементів. У зв'язку з цим використовується також позначення безлічі-ступеня безлічі Ау вигляді 2 А.
приклад 4
А = (0, 1, 2),P(A) = { , {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}} .
Геометрично безлічі можна уявити за допомогою діаграм Ейлера-Венна. Побудова діаграми полягає в зображенні великого прямокутника, що представляє універсальне безліч U, А всередині його - кіл (або якихось інших замкнутих фігур), що представляють безлічі. Фігури повинні перетинатися в найбільш загальному випадку, необхідному в завданню, і повинні бути відповідним чином позначені. Точки, що лежать всередині різних областей діаграми, можуть розглядатися як елементи відповідних множин. Маючи побудовану діаграму, можна заштрихувати певні області для позначення новостворених множин.
Операції над множинами розглядаються для отримання нових множин з уже існуючих.
визначення. об'єднанням множин Аі Вназивається множина, що складається з усіх тих елементів, які належать хоча б одній з множин А,В(Рис. 1.1):
Мал. 1.1. Діаграма Ейлера-Венна для об'єднання
визначення. перетином множин Аі Вназивається множина, що складається з усіх тих і тільки тих елементів, які належать одночасно як безлічі А, Так і безлічі В(Рис. 1.2):
Мал. 1.2. Діаграма Ейлера-Венна для перетину
визначення. різницею множин Аі Вназивається безліч всіх тих і тільки тих елементів А, Які не містяться в В(Рис. 1.3):
Мал. 1.3. Діаграма Ейлера-Венна для різниці
визначення. Симетричної різницею множин Аі Вназивається безліч елементів цих множин, які належать або тільки безлічі А, Або тільки безлічі В(Рис. 1.4):
Мал. 1.4. Діаграма Ейлера-Венна для симетричної різниці
визначення. Абсолютним доповненням множини Аназивається безліч всіх тих елементів, які не належать безлічі А(Рис. 1.5):
Мал. 1.5. Діаграма Ейлера-Венна для абсолютного доповнення
приклад 5
За допомогою діаграм Ейлера-Венна доведемо тотожність:
Розглянемо ліву частину співвідношення і виконаємо дії по порядку:
1) знайдемо перетин множин Ві З() (Рис. 1.6, а);
2) знайдемо об'єднання отриманого безлічі з безліччю А() (Рис. 1.6, б).
Розглянемо праву частинуспіввідношення 
:
1) знайдемо об'єднання множин Аі В(Рис. 1.6, в);
2) знайдемо об'єднання множин Аі З(Мал.
1.6, г);
3) знайдемо перетин двох останніх множин і ( ) (Рис. 6, д):
В обох випадках (рис. 1.6, б) і (рис. 1.6, д) отримуємо рівні безлічі. Отже, вихідне співвідношення справедливо.
Мал. 1.6. Доказ тотожності за допомогою діаграм Ейлера-Венна
Розглянемо основні тотожності алгебри множин. Для довільних множин А,В, і Зсправедливі наступні співвідношення (табл. 1.11):
Таблиця 1.11 Основні тотожності алгебри множин
|
об'єднання |
перетин |
|
1. Комутативність об'єднання |
1 '. комутативність перетину |
|
2. Асоціативність об'єднання |
2 '. асоціативність перетину |
|
3. Дистрибутивність об'єднання щодо перетину |
3 '. Дистрибутивність перетину щодо об'єднання |
|
4. Закони дії з порожнім і універсальним множинами |
4 '. Закони дії з порожнім і універсальним множинами |
|
5. Закон ідемпотентності об'єднання |
5 '. Закон ідемпотентності перетину |
|
6. Закон де Моргана |
6 '. Закон де Моргана |
|
7. Закон поглинання
|
7 '. закон поглинання
|
|
8. Закон склеювання
|
8 '. закон склеювання
|
|
9. Закон Порецкого
|
9 '. закон Порецкого
|
|
10. Закон подвійного доповнення |
|
