Понятие множества относится к аксиоматическим понятиям математики.
Определение . Множество – такой набор, группа, коллекция элементов, которые обладают каким-либо общим для них всех свойством или признаком.
Обозначение: A , B .
Определение . Два множества A и B равны тогда и только тогда, когда они состоят из одних и тех же элементов. A = B .
Запись a ∈ A (a ∉ A) означает, что a является (не является) элементом множества A.
Определение . Множество, не содержащее элементов, называется пустым и обозначается ∅.
Обычно в конкретных случаях элементы всех рассматриваемых множеств берутся из одного, достаточно широкого множества U, которое называется уни- версальным множеством .
Мощность множества обозначается как |M| .
Замечание : для конечных множеств мощность множества – это число элементов.
Определение . Если |A| = |B| , то множества называются равномощными .
Для иллюстрации операций над множествами часто используются диаграммы Эйлера – Венна . Построение диаграммы заключается в изображении большого прямоугольника, представляющего универсальное множество U , а внутри его – кругов, представляющих множества.
Над множествами определены следующие операции:
Объединение А∪В: = {х/х∈А∨х∈В}
Пересечение А∩В: = {х/х∈А&х∈В}
Разность А\В: = {х/х∈А&х∈В}
Дополнение A U \ A: = {x / x U & x ∉ A}
Задача1.1. Дано: а)A,B⊆Z, A = {1;3;4;5;9}, B = {2;4;5;10}. б)A,B⊆R, A = [-3;3), B = (2;10].
Решение.
a) A∩B = {4;5}, A∪B = {1;2;3;4;5;9;10}, A \ B = {1;3;9}, B \ A = {2;10}, B = Z \ B ;
б) A∩B = (2;3), A∪B = [-3;10] , A\B = [-3,2], B\A = ,B Z\B = (-∞,2]∪(10,+∞).
1) Дано: а) A, B ⊆ Z, A = {1;2;5;7;9;11}, B = {1;4;6;7}.
б) A, B ⊆ R, A = [-3; 7), B = [-4; 4].
Найти: A∩B, A∪B, A\B, B\A, B .
2) Дано: а) A, B ⊆ Z, A = {3;6;7;10}, B = {2;3;10;12}.
б) A, B ⊆ R, A = .
Найти: A∩B, A∪B, A\B, B\A, B .
3) Дано: а) A, B ⊆ Z, A = {1;2;5;7;9;11}, B = {1;4;6;7}.
б) A, B ⊆ R, A = .
4) Дано: а) A, B ⊆ Z, A = {0;4;6;7}, B = {-3;3;7}.
б)A,B ⊆ R, A = [-15;0), B = [-2;1].
Найти: A∩B, A∪B, A\B, B\A, A .
5) Дано: а) A, B ⊆ Z, A = {0;9}, B = {-6;0;3;9}.
б) A, B ⊆ R, A = [-10; 5), B = [-1; 6].
Найти: A ∩ B, A ∪ B, A\B, B\A, B .
6) Дано: а)A, B ⊆ Z, A = {0;6;9}, B = {-6;0;3;7}.
б) A, B ⊆ R, A = [-8;3), B = .
Найти: A ∩ B, A ∪ B, A\B, B\A, B .
7) Дано: а)A, B ⊆ Z, A = {-1;0;2;10}, B = {-1;2;9;10}.
б)A, B ⊆ R, A = [-10;9), B = [-5;15].
Найти: A∩B, A∪B, A\B, B\A, B .
8) Дано: а) A,B ⊆ Z, A = {1;2;9;37}, B = {-1;1;9;11;15}.
б) A, B ⊆ R, A = [-8;1), B = [-5;7].
Найти: A ∩ B, A ∪ B, A\B, B\A, B .
9) Дано: а) A, B ⊆ Z, A = {-1;0;9;17}, B = {-1;1;9;10;25}.
б) A, B ⊆ R, A = [-4;9), B = [-5;7].
Найти: A∩B, A∪B, A\B, B\A, B .
10) Дано: а)A,B⊆Z, A = {1;7;9;17}, B = {-2;1;9;10;25}.
б) A,B⊆R, A = .
Найти: A ∩ B, A ∪ B, A\B, B\A, A .
Задача1.1. Используя диаграммы Эйлера-Венна доказать тождество:
A\ (B\C) = (A\B) ∪ (A ∩ C).
Решение.
Построим диаграммы Венна.
Левая часть равенства представлена на рисунке а), правая – на рисунке б). Из диаграмм очевидно равенство левой и правой частей данного соотношения.
Задачи для самостоятельного решения
Используя диаграммы Эйлера-Венна доказать тождества:
1) A\(B ∪ C) = (A\B) ∩ (A\C);
2) A ∪ (B\C) = (A ∩ B)\C;
3) A ∪ (B \ C) = (A ∩ B) \ (A ∩ C);
4) (A\B) \C = (A\B) \ (B\C);
5) (A\B) \C = (A\B) ∪ (A∩C);
6) A∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C);
7) (A ∩ B) \ (A ∩ C) = (A ∩ B) \C;
8) A∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C);
9) (A ∪ B) \C = (A\C) ∪ (B\C)
10) A∪ (A ∩ B) = A ∪ B
Задача 1.3. На уроке литературы учитель решил узнать, кто из 40 учеников класса читал книги A, B, C. Результаты опроса оказались таковы: книгу A читали 25 учеников; книгу B читали 22 ученика; книгу C читали 22 ученика; книги A или B читали 33 ученика; книги A или C читали 32 ученика; книги B или C читали 31 ученик; все книги читали 10 учеников. Определите: 1) Сколько учеников прочли только книгу A?
2) Сколько учеников прочли только книгу B?
3) Сколько учеников прочли только книгу C?
4) Сколько учеников прочли только по одной книге?
5) Сколько учеников прочли хотя бы одну книгу?
6) Сколько учеников не прочитали ни одной книги?
Решение.
Пусть U - множество учеников в классе. Тогда
|U| = 40, |A| = 25, |B| = 22, |C| = 22, |A ∪ B| = 33, |A ∪ C| = 32, |B ∪ C| = 31, |A ∩ B ∩ C| = 10
Попробуем проиллюстрировать задачу.
Разобьём множество учеников, прочитавших хотя бы одну книгу, на семь подмножеств k 1 , k 2 , k 3 , k 4 , k 5 , k 6 , k 7 , где
k 1 - множество учеников, прочитавших только книгу A;
k 3 - множество учеников, прочитавших только книгу B;
k 7 - множество учеников, прочитавших только книгу C;
k 2 - множество учеников, прочитавших книги A и B и не читавших книгу C;
k 4 - множество учеников, прочитавших книги A и C и не читавших книгу B;
k 6 - множество учеников, прочитавших книги B и C и не читавших книгу A;
k 5 - множество учеников, прочитавших книги A, B и C.
Вычислим мощность каждого из этих подмножеств.
|k 2 | = |A ∩ B|-|A ∩ B ∩ C|; |k 4 | = |A ∩ C|-|A ∩ B ∩ C|;
|k 6 | = |B ∩ C| - |A ∩ B ∩ C|; |k 5 | = |A ∩ B ∩ C|.
Тогда |k 1 | = |A| - |k 2 | - |k 4 | - |k 5 |, |k 3 | = |B| - |k 2 | - |k 6 | - |k 5 |, |k 7 | = |C| - |k 6 | - |k | - |k 5 |.
Найдём |A ∩ B|, |A ∩ C|, |B ∩ C|.
|A ∩ B| = | A| +| B| - |A ∩ B| = 25 + 22 - 33 = 14 ,
|A ∩ C| = |A| + |C| - |A ∩ C| = 25 + 22 - 32 = 15 ,
|B ∩ C| = |B| + |C| - |B ∩ C| = 22 + 22 - 31 = 13 .
Тогда k 1 = 25-4-5-10 = 6; k 3 = 22-4-3-10 = 5; k 7 = 22-5-3-10 = 4;
|A ∪ B ∪ C| = |A ∪ B| + |C| - |(A ∪ B) ∪ C| .
Из рисунка ясно, что |C| - |(A ∪ B) ∪ C| = |k 7 | = 4, тогда |A ∪ B ∪ C| = 33+4 = 37 – число учеников, прочитавших хотя бы одну книгу.
Так как в классе 40 учеников, то 3 ученика не прочитали ни одной книги.
Ответ:- 6 учеников прочли только книгу A.
- 5 учеников прочли только книгу B.
- 4 ученика прочли только книгу C.
- 15 учеников прочли только по одной книге.
- 37 учеников прочли хотя бы одну книгу из A, B, C.
- 3 ученика не прочитали ни одной книги.
Задачи для самостоятельного решения
1) В течение недели в кинотеатре шли фильмы A, B, C . Каждый из 40 школьни- ков видел либо все 3 фильма, либо один из трёх. Фильм A видели 13 школьников. Фильм B видели 16 школьников. Фильм C видели 19 школьников. Сколько школьников видели только по одному фильму?
2) В международной конференции участвовало 120 человек. Из них 60 владеют русским языком, 48 – английским, 32 – немецким, 21 – русским и английским, 19 – английским и немецким, 15 – русским и немецким, а 10 человек владеют всеми тремя языками. Сколько участников конференции не владеют ни одним из этих языков?
3) В спортивных соревнованиях участвует школьная команда из 20 человек, каждый из которых имеет спортивный разряд по одному или нескольким из трёх видов спорта: лёгкой атлетике, плаванию и гимнастике. Известно, что 12 из них имеют разряды по лёгкой атлетике, 10 – по гимнастике и 5 – по плаванию. Определите количество школьников из этой команды, имеющих разряды по всем видам спорта, если по лёгкой атлетике и плаванию разряды имеют 2 человека, по лёгкой атлетике и гимнастике – 4 человека, по плаванию и гимнастике – 2 человека.
4) Опрос 100 студентов дал следующие результаты о количестве студентов, изучающих различные иностранные языки: испанский – 28; немецкий – 30; французский – 42; испанский и немецкий – 8; испанскии и французский – 10; немецкий и французский – 5; все три языка – 3. Сколько студентов изучает немецкий язык в том и только том случае, если они изучают французский язык? 5) Опрос 100 студентов выявил следующие данные о числе студентов, изучающих различные иностранные языки: только немецкий – 18; немецкий, но не испанский – 23; немецкий и французский – 8; немецкий – 26; французский – 48; французский и испанский – 8; никакого языка – 24. Сколько студентов изучают немецкий и испанский язык?
6) В отчёте об опросе 100 студентов сообщалось, что количество студентов, изучающих различные языки, таково: все три языка – 5; немецкий и испанский – 10; французский и испанский – 8; немецкий и французский – 20; испанский – 30; немецкий – 23; французский – 50. Инспектор, представивший этот отчёт, был уволен. Почему?
7) В международной конференции участвовало 100 человек. Из них 42 владеют французским языком, 28 – английским, 30 – немецким, 10 – французским и английским, 8 – английским и немецким, 5 – французским и немецким, а 3 чело- века владеют всеми тремя языками. Сколько участников конференции не владеют ни одним из этих языков?
8) Студенты 1 курса, изучающие информатику в университете, могут посещать и дополнительные дисциплины. В этом году 25 из них предпочли изучать бухгалтерию, 27 выбрали бизнес, а 12 решили заниматься туризмом. Кроме того, было 20 студентов, слушающих курс бухгалтерии и бизнеса, 5 изучали бухгалтерию и туризм, а 3 – туризм и бизнес. Известно, что никто из студентов не отважился посещать сразу 3 дополнительных курса. Сколько студентов посещали, по крайней мере, 1 дополнительный курс?
9) В олимпиаде по математике для абитуриентов приняло участие 40 учащихся. Им было предложено решить одну задачу по алгебре, одну по геометрии и одну по тригонометрии. Задачу по алгебре решили 20 человек, по геометрии – 18, по тригонометрии – 18 человек. Задачи по алгебре и геометрии решили 7 человек, по алгебре и тригонометрии – 8 человек, по геометрии и тригонометрии – 9 человек. Ни одной задачи не решили 3 человека. Сколько учащихся решили толь- ко две задачи?
10) В классе 40 учеников. Из них по русскому языку имеют тройки 19 человек, по математике – 17 человек и по физике – 22 человека. 4 ученика имеют тройки только по одному русскому языку, 4 – только по математике и 11 – только по физике. По русскому, математике и физике имеют тройки 5 учащихся. 7 человек имеют тройки по математике и физике. Сколько учеников имеют тройки по двум из трёх предметов?
Основные понятия теории множеств
Понятие множества является фундаментальным понятием современной математики. Мы будем считать его первоначальным и теорию множеств строить интуитивно. Дадим описание этого первоначального понятия.
Множество – это совокупность объектов (предметов или понятий), которая мыслится как единое целое. Объекты, входящие в эту совокупность, называются элементами множества.
Можно говорить о множестве студентов первого курса математического факультета, о множестве рыб в океане и т.д. Математика обычно интересуется множеством математических объектов: множество рациональных чисел, множество прямоугольников и т.д.
Множества будем обозначать большими буквами латинского алфавита, а его элементы малыми.
Если – элемент множества M , то говорят « принадлежит M » и пишут: . Если некоторый объект не является элементом множества, то говорят « не принадлежит M » и пишут (иногда ).
Существует два основных способа задания множеств: перечисление
его элементов и указание характеристического свойства
его элементов. Первый из этих способов применяется, в основном, для конечных множеств. При перечислении элементов рассматриваемого множества его элементы обрамляются фигурными скобками. Например, 
обозначает множество, элементами которого являются числа 2, 4 , 7 и только они. Этот способ применим не всегда, так как, например, множество всех действительных чисел таким образом задать невозможно.
Характеристическое свойство элементов множества M – это такое свойство, что всякий элемент, обладающий этим свойством, принадлежит M , а всякий элемент, не обладающий этим свойством, не принадлежит M . Множество элементов, обладающих свойством , обозначается так:
или 
.
Наиболее часто встречающиеся множества имеют свои особые обозначения. В дальнейшем будем придерживаться следующих обозначений:
N = – множество всех натуральных чисел;
Z = – множество всех целых чисел;
– множество всех рациональных чисел;
R – множество всех действительных (вещественных) чисел, т.е. рациональных чисел (бесконечных десятичных периодических дробей) и иррациональных чисел (бесконечных десятичных непериодических дробей);
– множество всех комплексных чисел.
Приведем более специальные примеры задания множеств с помощью указания характеристического свойства.
Пример
1.
Множество всех натуральных делителей числа 48 можно записать так: 
(запись используется только для целых чисел , и означает, что делится на ).
Пример 2. Множество всех положительных рациональных чисел, меньших 7, записывается следующим образом: .
Пример 3. – интервал действительных чисел с концами 1 и 5; – отрезок действительных чисел с концами 2 и 7.
Слово «множество» наводит на мысль, что оно содержит много элементов. Но это не всегда так. В математике могут рассматриваться множества, содержащие только один элемент. Например, множество целых корней уравнения 
. Более того, удобно говорить о множестве, не содержащем ни одного элемента. Такое множество называется пустым
и обозначается через Ø. Например, пустым является множество действительных корней уравнения .
Определение 1. Множества и называются равными (обозначается А=В ), если эти множества состоят из одних и тех же элементов.
Определение 2. Если каждый элемент множества принадлежит множеству , то называют подмножеством множества .
Обозначения: (« включается в »); (« включает »).
Ясно, что Ø и само множество являются подмножествами множества . Всякое другое подмножество множества называется его правильной частью . Если и , то говорят, что « А – собственное подмножество »или что «А строго включается в » и пишут .
Очевидно следующее утверждение: множества и равны тогда и только тогда, когда и .
На этом утверждении основан универсальный метод доказательства равенства двух множеств : чтобы доказать, что множества и равны, достаточно показать, что , а является подмножеством множества .
Это наиболее употребительный способ, хотя и не единственный. Позже, познакомившись с операциями над множествами и их свойствами, мы укажем другой способ доказательства равенства двух множеств – с помощью преобразований .
В заключение заметим, что часто в той или иной математической теории имеют дело с подмножествами одного и того же множества U , которое называют универсальным в этой теории. Например, в школьной алгебре и математическом анализе универсальным является множество R действительных чисел, в геометрии – множество точек пространства.
Операции над множествами и их свойства
Над множествами можно выполнять действия (операции), напоминающие сложение, умножение и вычитание.
Определение 1. Объединением множеств и называется множество, обозначаемое через , каждый элемент которого принадлежит хотя бы одному из множеств или .
Сама операция , в результате которой получается такое множество, называется объединением.
Краткая запись определения 1:
Определение 2. Пересечением множеств и называется множество, обозначаемое через , содержащее все те и только те элементы, каждый из которых принадлежит и , и .
Сама операция , в результате которой получается множество , называется пересечением.
Краткая запись определения 2:
Например, если 
, 
, то 
, .
Множества можно изображать в виде геометрических фигур, что позволяет наглядно иллюстрировать операции над множествами. Такой метод был предложен Леонардом Эйлером (1707–1783) для анализа логических рассуждений, широко применялся и получил дальнейшее развитие в трудах английского математика Джона Венна (1834–1923). Поэтому такие рисунки называют диаграммами Эйлера-Венна .
Операции объединения и пересечения множеств можно проиллюстрировать диаграммами Эйлера–Венна следующим образом:
 |  |
– заштрихованная часть; – заштрихованная часть.
Можно определить объединение и пересечение любой совокупности множеств , где – некоторое множество индексов.
Определение . Объединением совокупности множеств называется множество , состоящее из всех тех и только тех элементов, каждый из которых принадлежит по крайней мере одному из множеств .
Определение . Пересечением совокупности множеств называется множество , состоящее из всех тех и только тех элементов, каждый из которых принадлежит любому из множеств .
В случае, когда множество индексов конечно, например, 
, то для обозначения объединения и пересечения совокупности множеств в этом случае обычно пользуются обозначениями:
и 
.
Например, если 
, 
, 
, то , .
С понятиями объединения и пересечения множеств неоднократно встречаются в школьном курсе математики.
Пример 1. Множество М решений системы неравенств
является пересечением множеств решений каждого из неравенств этой системы: .
Пример 2. Множество М решений системы
является пересечением множеств решений каждого из неравенств этой системы. Множество решений первого уравнения – множество точек прямой , т.е. . Множество . Множество состоит из одного элемента – точки пересечения прямых.
Пример 3. Множество решений уравнения
где 
, является объединением множеств решений каждого из уравнений , , т.е.
Определение 3. Разностью множеств и называется множество, обозначаемое через , и состоящее из всех тех и только тех элементов, которые принадлежат , но не принадлежат .– заштрихованная часть; . с операциями объединения, пересечения и дополнения. Полученную математическую структуру называют алгеброй множеств илиалгеброй Булямножеств (вчесть ирландского математика и логика Джорджа Буля (1816–1864)). Через будем обозначать множество всех подмножеств произвольного множества и называть его булеаном множества .
Перечисленные ниже равенства справедливы для любых подмножеств A, B, C универсального множества U. Поэтому их и называют законами алгебры множеств.
Множество a и содержащим его множеством A обозначается так (a есть элемент множества A ; или a принадлежит A , или A содержит a ). Если a A , то пишут (a не входит в A , A не содержит a a , b , c
Операции над множествами .
Универсальное множество
Универса́льное мно́жество
Диаграммы Венна. Тождества алгебры множеств и их доказательство.
Диаграмма Венна - схематичное изображение всех возможных пересечений нескольких множеств, показывают математические, теоретико-множественные или логические отношения между множествами.
Тождества и их доказательства.
Для произвольных множеств А, В, и С справедливы следующие соотношения:
1. Коммутативность:
2. Ассоциативность
3. Дистрибутивность объединения относительно пересечения
3’. Дистрибутивность пересечения относительно объединения
4. Законы действия с пустым и универсальным множествами
5. Закон идемпотентности
6. Закон де Моргана
7. Закон поглощения
, 
8. Закон склеивания
, 
9. Закон Порецкого
, 
10. Закон двойного дополнения
Доказать следующее тождество .
Докажем это тождество аналитическим способом (используя равносильности алгебры множеств)
Понятие формального языка
Формальный язык - язык, характеризующийся точными правилами построения выражений и их понимания. Он строится в соответствии с четкими правилами, обеспечивая непротиворечивое, точное и компактное отображение свойств и отношений изучаемой предметной области (моделируемых объектов).
Формальный язык – основа создания программного обеспечения.
ФЯ образуется с помощью исходного набора букв а1, а2, …., а100, с помощью букв образуются слава. Слово в формальном языке – упорядоченный набор букв (Ящерица – 30 букв)
Для операции * слов справедлив ассоциативный закон.
Теория полугрупп и полуколец – основа теории ФЯ
Тавтологии
Тавтология – тождественно-истинное высказывание, которое всегда истинно.
Простейшая тавтология - выражение (A или не A ), представляющее закон исключённого третьего, где вместо A может быть подставлено любое выражение,могущее быть ложным или истинным, например свет включен или не включен , дважды два равно или не равно пяти . Тавтологией являются и законы математической логики выраженные через оператор эквивалентности: и т. п.
Понятие высказывательной формы или предиката от одной переменной. Примеры предикатов.
Предикат – высказывание зависящее от какой-то меняющейся переменной величины.
Одноместный предикат – отображение, по которому каждому значению переменой указывается единственное значение 0 или 1 .примеры:
Конъюнкцией
двух предикатов А(х) и В(х) называется новый предикат 
, который принимает значение «истина» при тех и только тех значениях х Т, при которых каждый из предикатов принимает значение «истина», и принимает значение «ложь» во всех остальных случаях. Множеством истинности Т предиката А(х) В(х), х Х является пересечение множеств истинности предикатов А(х) – Т1 и В(х) – Т2, т.е. Т= Т1 ∩Т2. Например: А(х): «х – четное число», В(х): « х кратно 3». А(х) В(х) – «х – четное число и х кратно 3». Т.е. предикат «х делится на 6».
Отрицанием предиката А(х) называется новый предикат, который принимает значение «истина» при всех значениях х Т, при которых предикат А(х) принимает значение «ложь», и принимает значение «ложь», если А(х) принимает значение «истина». Множеством истинности предиката, х Х является дополнение Т" к множеству Т в множестве Х.
Возьмём высказывания: `` Сократ - человек "", `` Платон - человек "". Оба эти высказывания выражают свойство ``быть человеком"". Таким образом, мы можем рассматривать предикат `` быть человеком "" и говорить, что он выполняется для Сократа и Платона.
25 область определения и область истинности предиката
Множество М, на котором определен предикат P(х) , называется областью определения предиката.
Множество всех элементов х Î М, при которых предикат принимает значение «истина», называется множеством истинности предиката Р(х), то есть множество истинности предиката Р(х) - это множество 1р = {х| х Î М, Р(х) = 1}.
Р(х): «х 2 + 1> 0, xÎ R»; область определения предиката М = R и область истинности – тоже R, т.к. неравенство верно для всех действительных чисел. Таким образом, для данного предиката М = I p . Такие предикаты называются тождественно истинными.
В(х): «х 2 + 1< 0, xÎ R»; область истинности I p =Æ, т.к. не существует действительных чисел, для которых выполняется неравенство. Такие предикаты называются тождественно ложными.
Кванторы. Двухместные предикаты. Определения уравнения, тождества и неравенства.
Ква́нтор - общее название для логических операций, ограничивающих область истинности какого-либо предиката и создающих выcказывание. Чаще всего упоминают:
· Квантор всеобщности (обозначение: , читается: «для всех…», «для каждого…» или «каждый…», «любой…», «для любого…»).
· Квантор существования (обозначение: , читается: «существует…» или «найдётся…»).
Обозначим предикат «x делится на 5». Используя квантор общности, можно формально записать следующие высказывания (конечно, ложные):
1. любое натуральное число кратно 5;
2. каждое натуральное число кратно 5;
3. все натуральные числа кратны 5;
следующим образом:
.
Следующие (уже истинные) высказывания используют квантор существования:
1. существуют натуральные числа, кратные 5;
2. найдётся натуральное число, кратное 5;
3. хотя бы одно натуральное число кратно 5.
Их формальная запись:
.
· Высказывание означает, что область значений переменной включена в область истинности предиката .
(«При всех значениях (x) утверждение верно»).
· Высказывание означает, что область истинности предиката непуста.
(«Существует (x) при котором утверждение верно»).
Операции над кванторами
Правило отрицания кванторов - применяется для построения отрицаний высказываний, содержащих кванторы, и имеет вид:
Двухместный предикат – отображение, по которому каждой паре переменных указывается единственное значение 0 или 1.
Предикат является двухместным предикатом, предметной областью которого могут служить любые множества действительных чисел. Высказывание истинно, а высказывание ложно. Если вместо одной из переменных подставить число, то получится одноместный предикат.
Пересечение графов
Пусть G1(V1,E1) и G’2(V2’,E2’) – произвольные графы. Пересечением G1∩G’2 графов G1 и G’2 называется граф с множеством вершин V1∩V’2 с множеством ребер E = E1∩E’2
Свойства
· Пересечение множеств является бинарной операцией на произвольном булеане 2 X ;
коммутативна :
· Операция пересечения множеств транзитивна (ассоциативность) :
· Универсальное множество X является нейтральным элементом операции пересечения множеств:
· Таким образом булеан вместе с операцией пересечения множеств является абелевой группой;
· Операция пересечения множеств идемпотентна:
· Если - пустое множество, то
Остов и коостов графов.
Остов графа - такой его подграф, который является деревом.
Коостов – дополнение остова до графа.
Понятие множества. Операции над множествами. Универсальное множество.
Множество (N- натуральные,Z-целые,Q-рационал, R-действительные) – неопределяемое понятие, это совокупность объектов, рассматриваемая как одно целое. Понятие множества принимается за основное, т. е. не сводимое к другим понятиям. Объекты, составляющие данное множество, называются его элементами. Простое множество не имеет ни одного элемента. Основное отношение между элементом a и содержащим его множеством A обозначается так (a есть элемент множества A ; или a принадлежит A , или A содержит a ). Если a не является элементом множества A , то пишут (a не входит в A , A не содержит a ). Множество можно задать указанием всех его элементов, причем в этом случае употребляются фигурные скобки. Так {a , b , c } обозначает множество трех элементов. Аналогичная запись употребляется и в случае бесконечных множеств, причем невыписанные элементы заменяются многоточием. Так, множество натуральных чисел обозначается {1, 2, 3, ...}, а множество четных чисел {2, 4, 6, ...}, причем под многоточием в первом случае подразумеваются все натуральные числа, а во втором - только четные.
«пустое множество» - множество, не содержащее ни одного элемента, его обозначают
Способы задания: табличный, перечислением элементов, графический, рекуррентный, формулой.
Операции над множествами .
Пересечение множеств – множество, состоящее из элементов, которые принадлежат обоим множествам.
Для пересечения множеств справедливы:
· X∩Y=Y∩X - коммутативный закон
· (X∩Y)∩Z = X∩(Y∩Z) = X∩Y∩Z - ассоциативный закон
Объединение множеств – множество, состоящее из элементов, принадлежащих хотя бы одному из множеств.
Для объединенных множеств справедливы:
· XUY = YUX - коммутативный закон
· (XUY) UZ = XU (YUZ) = XUYUZ - ассоциативный закон,
Универсальное множество
Универса́льное мно́жество - множество, содержащее все мыслимые объекты. Универсальное множество единственно.
Универсальное множество – множество, которое содержит все элементы, из которых может состоять другое множество, т.е. полностью содержать все элементы универсального множества. .
Если при некотором рассмотрении участвуют только подмножества некоторого фиксированного множества, то это самое большое множество будем считать универсальным.
Универсальное множество обладает интересным свойством, которое не имеет аналогии в обычной алгебре, а именно, для любого множества X справедливо соотношение XU(объединение)I = I.
Универсальное множество обычно обозначают графически в виде множества точек прямоугольника, а отдельные множества в виде отдельных областей внутри этого прямоугольника. Изображение множеств в виде областей в прямоугольнике, представляющем универсальное множество, называется диаграммой Эйлера-Венна.
Что такое множество в математике? Математическое множество - это несколько отдельных элементов, рассматриваемых, как единое целое. Если обозначить такой элемент буквой a, а само множество - буквой А, то запись будет выглядеть следующим образом:
проговаривается эта запись так: a принадлежит А, или А содержит а, или а - элемент А.
Для перечисления элементов множества используются фигурные скобки - {}. То есть, например, множество, в котором а ∈ А, b ∈ A и c ∈ A, будет записываться в таком виде:
Виды множеств.
Пустые множества.
Пустое множество – это то множество, которое вообще не содержит никаких элементов. Обозначается оно цифрой 0 или специальным значком ∅.
Примером пустого множества может служить любое нелогичное понятие , противоречащее самому себе - «множество птиц, живущих на дне океана», или «множество деревьев на Луне». Поскольку оба множества лишены смысла и не отвечают реальности, то, следовательно, они являются пустыми. Скажем, количество деревьев на Луне – 0, поэтому «множество деревьев на Луне» будет пустым (не будет содержать ни одного элемента).
Равные множества.
Равные множества – это два или более множеств, состоящих из равных наборов элементов. Приведём пример. Скажем, все члены Вашей семьи находятся на кухне. Таким образом, Множество «Члены семьи на кухне» будет равно множеству «Члены семьи в квартире».
Если два множества - А и B - состоят из одинакового набора элементов, то они будут равны, то есть А = B. Элементы множеств могут перечисляться в любой последовательности, на результат это никак не влияет. Множество {a, b, c} можно с тем же успехом записать, как {a, c, b}, или {с, b, a}, или {b, c, a}.
Подмножества и надмножества.
Если множества А и B состоят из одинаковых элементов {a, b, c}, то А будет считаться подмножеством B, а B - надмножеством А. Записывается это следующим образом:
A ⊆ B, B ⊇ A.
Бывает так, что множество В содержит в себе каждый из элементов множества А, но в то же время в нем присутствуют и другие элементы, множеству А не принадлежащие. В этом случае множество В становится собственным надмножеством А, в то время как множество А становится собственным подмножеством В.
Иначе говоря, если А ⊆ В, но при этом А ≠ В, то А ⊂ В, В ⊃ А.
