≡× МЕНЮ

• Грамматика
• География
• СМИ
• Моя жизнь
• Книги

Множества и операции над множествами. Понятие подмножества

Сравнительный анализ возможностей человека и машины

Показатели превосходства человека	Показатели превосходства машины
Обнаружение полезных сигналов с низким энергетическим уровнем (световых, звуковых)	Выполнение однообразных точных работ длительное время.
Опознание образов и их обобщение	Быстрая реакция на сигналы управления
Обнаружение сигналов на фоне высоких уровней шумов	Плавное и точное приложение больших усилий.
Хранение большого объема информации длительное время и использование требуемой информации в нужное время	Хранение больших объемов информации и быстродействие при их вводе
Способность к восприятию и использованию неполной информации	Выполнение сложных вычислений с большой точностью и скоростью
Нахождение и использование эвристических методов решения	Одновременное выполнение нескольких разнообразных действий
Реагирование на непредвиденные обстоятельства	Использование дедуктивных методов в процессе принятия решения
Оригинальность в решении задач	Нечувствительность ко многим посторонним факторам
Способность учитывать прошлый опыт и изменять способ действий	Работоспособность в условиях, где человек не может работать
Способность выполнять операции в непредвиденных ситуациях	Чувствительность к стимулам превосходящим человеческие
Способность работать в условиях перегрузок	Время стабильной работы больше, чем у человека
Чувствительность к широкому диапазону стимулов

В системе «человек-машина» к человеку предъявляются ряд требований.

Человек должен:

Уметь четко формулировать задачи;

Знать компоненты СОУ и ее возможности;

Уметь составлять программу решения задачи;

Уметь сравнивать полученный результат с предполагаемым и изменять несоответствие изменением способа решения задачи.

Множество - это объединение в одно целое объектов, связанных между собой неким свойством. Термин «множество» в математике не всегда обозначает большое количество предметов, оно может состоять из одного элемента и вообще не содержать элементов, тогда его называют пустым и обозначают .

Множество B называется подмножеством множества A , если любой элемент множества B является элементом множества A . Обозначение: .

Пример. . Запишем все подмножества множества M: {-14}, {11}, {17}, {-14;11}, {-14;17}, {11;17}, {-14;11;11}, .

Свойства включения множеств:

1. Пустое множество является подмножеством любого множества: Æ Ì А .

2. Любое множество является подмножеством самого себя, т. е. для любого множества А справедливо включение А Ì А .

3. Если А – подмножество множества В , а В – подмножество множества С , то А – подмножество множества С .

Универсальное множество – это самое большее множество, содержащее в себе все множества, рассматриваемые в данной задаче.

На диаграмме Эйлера – Венна универсальное множество обозначают в виде прямоугольника и буквы U .

Два множества A и B равны, если они состоят из одних и тех же элементов.

Из этого принципа следует, что для любых двух различных множеств всегда найдется некоторый объект, являющийся элементом одного из них и не являющийся элементом другого. Так как пустые совокупности не содержат элементов, то они не различимы и поэтому пустое множество – единственно.

Подмножества. Определение равенства множеств можно сформулировать иначе, используя понятие подмножества.

Определение. Множество A называется подмножеством множества B , если каждый элемент A является элементом B.

Следствие 1. Очевидно,
для любого множества A, т.к. каждый элемент из A есть элемент из A.

Следствие 2. Для любого множества A,
, ибо если бы пустое множество не являлось подмножеством A, то в пустом подмножестве существовали бы элементы, не принадлежащие A. Однако пустое множество не содержит вообще ни одного элемента.

Если
, то пишут
, и если
, то A – собственное подмножество B.

Понятие подмножества множеств позволяет легко формализовать понятие равенства двух множеств.

Утверждение. Для любых A и B

Логическую эквивалентность, определяемую выражением (1.1) используют как основной способ доказательства равенства двух множеств.

Замечание . Отношение включения  обладает рядом очевидных свойств:

(рефлексивность);

(транзитивность).

Для любого множества X можно определить специальное множество всех подмножеств множества X, которое называется булеаном ℬ
, которое включает в себя само множество X, все его подмножества и пустое множество
.

Пример. Пусть
– это множество, состоящее из трех элементов. Тогда булеанℬ (X) это множество:

Собственными подмножествами ℬ (X) являются следующие множества:

{a},{b},{c},{a,b},{b,c},{a,c}.

В общем случае, если множество X содержит n элементов, то множество его подмножеств ℬ (X) состоит из элементов.

Операции на множествах.

Пусть U – универсальное множество,
. Тогда для множеств X,Y можно определить операции
.

Определение . Объединением множеств X и Y называется множество
, состоящее из элементов, входящих хотя бы в одно из множеств (X или Y):

Рис. 1.1 – Объединение множеств Рис. 1.2 – Пересечение множеств

Определение . Пересечением множеств X и Y называется множество
, состоящее из элементов, входящих в X и в Y одновременно:

Определение . Разностью множеств X и Y называется множество
, состоящее из элементов, входящих в множество X, но не входящих в Y:

Рис. 1.3 – Разность множеств
Рис. 1.4 – Симметрическая

разность множеств

Определение . Симметрической разностью двух множеств X и Y называется множество
, состоящее из элементов множества X и элементов множества Y, за исключением элементов, являющихся общими для обоих множеств:

Определение . Для любого множества
дополнением множествадо U называется такое множество, что:

Рис. 1.5 – Дополнение множества X до U

На рис. 1.1  1.5 представлены диаграммы Венна, наглядно демонстрирующие результаты операций
.

Дополнение множества иногда обозначается
. Операции
связаны между собой законами де Моргана:

, (1.7)

. (1.8)

В справедливости законов де Моргана легко убедиться самостоятельно.

В таблице 1.1 представлены основные свойства операций над множествами.

Таблица 1.1

	Свойства операций	Объединение, пересечение, дополнение
	коммутативность	,
	ассоциативность
	дистрибутивность
	идемпотентность	, , , , ,
	теоремы де Моргана	,
	инволюция

Операции объединения и пересечения можно обобщить. Пусть
– множество индексов,
– семейство подмножеств множества X.

Определение. Семейство подмножеств
множества X, для которых
, называетсяразбиением множества X, если выполняются следующие два условия:

,

Определение. Семейство подмножеств
множества X называетсяпокрытием множества X, если:
.

Определение. Класс K подмножеств из U называется алгеброй, если:

1.
;

2. из того, что
следует, что
;

3. из того, что
следует, что
.

Пример. Пусть
, тогда класс
образует алгебру.

Определение. Класс F подмножеств из U образует -алгебру, если:

1.
;

2. из того, что
следует
;

3. из того, что
,
следует, что
.

Пример. Множество всех подмножеств U образует -алгебру, т.е.ℬ (U) – -алгебра.

Множество А называют подмножеством множества S (или в множестве 5), если каждый элемент множества А является элементом множества S. Обозначение: Ис5.

Выражение AqS также читают: «А включено в 5», «А содержится в 5», «S содержит А», «А часть S». Знак с называют символом включения.

Запишем данное определение символически:

Из определения вытекает: множество А является подмножеством в S тогда и только тогда, когда из предложения (хеА ) следует предложение (xeS).

Построим отрицание к тому, что AczS. По законам логики имеем:

Итак, предложение «Множество А не включено в S » равносильно предложению «Существует элемент множества А , который не лежит в S».

Два множества А и В формально можно соединить знаками включения двумя способами: A(z.B и ВсА. Каждое из этих выражений определяет предложение, которое может быть истинным или ложным. Второе включение В (также пишут А^В) по отношению к первому называют обратным. Не всегда из справедливости одного из включений следует истинность другого включения.

Пример 6.2.1. Имеет место включение {-2;2} с {-2;0; 1 ;2}, так как оба числа (-2) и 2 являются элементами множества {-2;0; 1 ;2}. Однако {-2;0; 1 ;2} не включено в {-2;2}, так как, например, 0г {-2;2}.

Пример 6.2.2. Пусть А - множество всех ромбов, В - множество всех квадратов.

А ? В, так как существует ромб, не являющийся квадратом.

В с: А, так как любой квадрат является ромбом (что вытекает из определений данных фигур).

Друг ими словами, множество всех квадратов является подмножеством множества всех ромбов.

Пример 6.2.3. {х | *:12}с{* | дг:3}, так как *:12=>*:3 (обоснуйте самостоятельно). Однако обратное включение неверно, гак как х:3фх":2 (приведите контрпример).

Из определения вытекает, что то есть каждое множество является подмножеством самою себя.

Возьмем вместо А пустое множество. Тогда утверждение 0qS равносильно V* (хе0 xeS). Так как посылка импликации всегда ложна, то для любого объекта д; импликация принимает истинное значение. Значит, утверждение 0qS верно. Итак, пустое множество является подмножеством любого множества.

Вывод: у любого непустого множества всегда есть два подмножества - само множество и пустое. Их называют тривиальными подмножествами. Само множество также называют несобственным подмножеством.

Подмножество в S называется собственным, если оно не совпадает с S. Запись AaS означает, что А является собственным подмножеством в S:

Знак символом строгого включении.

Мы имеем два отношения: отношение принадлежности элемента множеству (обозначаемое знаком е) и отношение включения множеств (обозначаемое знаком с). В общем случае это разные знаки. Например, {2}с{2,3}, но {2} *г{2,3}. Однако иногда между множествами можно поставить оба знака.

Пример 6.2.4. Множество А = {2} является элементом множества В = {1,2,{2}}. При этом А есть подмножество множества В , так вес элементы множества А лежат в В (в А есть только один элемент - число 2, который лежит в В).

Итак, {2}е{1,2,{2» и {2}с{ 1,2,{2}}.

Пример 6.2.5. Рассмотрим плоскость а и прямую /, лежащую на этой плоскости. Если рассматривать прямую как элемент плоскости, то принято писать lea. Если же понимать прямую как множество точек, принадлежащих данной прямой, то это множество будет подмножеством множества всех точек плоскости. Тогда можно записать /са.

Пусть верны прямое и обратное включения AqB и B В этом случае для всех х выполняются импликации хеЛ ->хеВ и xgB->xеЛ, что равносильно тому, что для всех.v хеЛ тогда и только тогда, когда хеВ. Это означает, что множества А и В совпадают:

Эю простое соображение лежит в основе метода доказательства равенства множеств, называемого методом двойного включения : для того чтобы доказать, что множества А и В равны, надо доказать прямое и обратное включения множ еств.

По сути, эта идея была продемонстрирована в примере 6.1.3, так как прямое включение A означает, что из предиката Р{х), задающего множество А , следует предикат Q{x ), задающий множество В , а обратное включение означает, что из Q(x) следует Р(х). Рассмотрим еще один пример.

Пример 6.2.6. Возьмем множества:

А = {2п | neZ) - множество всех четных чисел,

В - {хх=а+Ь, где а и b - нечетные числа} - множество всех чисел, каждое из которых является суммой некоторых нечетных чисел.

Докажем, что А=В.

Покажем справедливость включения А^В. Пусть хеА, тогда имеем х = 2w = (2/f-l)+1, то есть х представим в виде суммы двух нечетных чисел. Значит, хеВ.

Верно также обратное включение ВсА. В самом деле, пусть хеВ. Тогда х = (2/7+1)+(2А+1) = 2(/;+А"+1) = 2т. Значит х - четное число, поэтому хеА.

Оба включения доказаны. Значит, множества А и В равны.

Упражнение. Докажите, что множества {2/7-1 пе Z} и {2/7+1 | не Z} равны, то есть оба определяют множество нечетных чисел.

Пример 6.2.7. Заметим, что множества А= {2я-1 | //eN} и В - {2/7+1 | /7 € N} нс равны, так как IgA, но 1 &В. Поэтому множество всех нечетных положительных чисел задаст только множество Л. При этом включение Л^В верно.

Пусть дано множество S. Семейство всех подмножеств множества S называется булеаном множества S (или степенью множества S) и обозначается В(5) или 2 s .

По определению В(5) = {X | AfcS}.

Ясно, что 0еВ(5) и SeB(S) для любого множества S.

Пример 6.2.8. Пусть S = {1,2,3}. Найдем булсан этого множества.

Заметим, что элементами булеана являются множества.

Термин «степень множества» и соответствующее обозначение мотивируются тем, что если мы имеем конечное //-элементное множество, то число элементов его булеана будет равно степени 2". Рассмотренный выше пример иллюстрирует эту зависимость. Доказательство данного факта будет дано в главе 3. Там же будет рассмотрена формула, позволяющая находить у //-элементного множества число подмножеств, содержащих фиксированное число элементов.

• В некоторой литературе знаком с обозначают произвольное подмножество.

Определение:

Множество – это любая совокупность объектов, которые называются его элементами.

Если х- элемент множества М, то обозначают: х М { х – принадлежит М}, если не принадлежит, то х ∉ М; Множество не содержащее элементов называется пустым и обозначается ∅

Множество, в котором содержатся все элементы, находящиеся в рассмотрении, называется универсальным или универсумом и обозначается –

Ư. Множества, состоящие из одних и тех же элементов, называются равными и обозначаются А = В.

Если любой элемент множества В является элементом множества А, то множество В называется подмножеством множества А (частью множества А) и обозначается В ⊂ А; Отсюда следует, что любое множество является частью самого себя.

По определению пустое множество ∅ является подмножеством любого множества. Т.о. у любого множества А есть два подмножества:

Они называются несобственными подмножествами множества А. Любое множество В множества А, которое не является несобственными подмножествами А, (т.е. они отличны от А и ∅) и называются собственными подмножествами подмножества А. Множество из одного элемента а обозначается {а}.

Пример: А = {1;2;3} тогда пустое множество ∅ и само множество А является несобственными подмножествами А.

Множества:{1},{2},{3},{1;2},{1;3},{2;3} называются собственными подмножествами множества А. Совокупность всех множеств А называется его булеаном и обозначается – 2 А; В А, означает, что В А, В ≠ А. В этом случае говорят, что В строго включено в А или В является собственным подмножеством А;

В случае В ⊆ А, В = А говорят, что В нестрогое включение в А, т.е. В является несобственным подмножеством А.

Основные логические символы

ХР(х) – квантор общности (означает “для любого х выполняется

ХР(х) – квантор существования (означает “существует х, для которого выполняется Р (х)”.)

Р ⇒ Q – импликация (“из Р следует Q ”)

⟺ - эквивалентность (“тогда и только тогда”)

Р ∧ Q – конъюнкция (“Р и Q”)

Р ∨ Q – дизъюнкция (“Р или Q”)

Не Р или - отрицание Р

: = - символы присвоения (“положим”)

def – (“положим по определению”)

Используя эти символы можно записать:

1) (А = В) ⟺(( х ∈ А ⇒ х ∈ В) ∧ ( х ∈ В ⇒ х ∈ А)

2) (А ⊆ В) ⟺ ( х/х ∈А ⇒ х ∈ В)

3) (А = В) ⟺ (В ⊂ А ∧ А⊂ В)

Задание множеств

Перечислением элементов: М: = { а 1 ; а 2 ; а 3 ; …; а n }

или характеристическим свойством Р(х)

(предикатом): М: = { х | Р(х) }

Например:

1) В = { х ∈ N | х < 3} означает, что В= { 1; 2}

2) А ={ х ∈ N | х +1=5} означает, что А = {4}

3) В = { х ∈ N | х M5} или {5;10;15…}

т.е. { х | Р(х) }означает, что множество элементов х множества обладает свойством Р(х)

4) М = { х ∈ N | х ­3< 5}={1;2;3;4;5;6;7}

Операции над множествами

Рассматриваются следующие операции над множествами:

1 0 . Объединение множеств А и В.

U

А ∪ В = { х/х ∈ А или х ∈ В} – т.е. состоит из элементов, принадлежащих хотя б одному из множеств А или В.

2 0 . Пересечение множеств А и В.

A∩B = {x/x ∈ A и x ∈ B} – т.е. состоят из элементов, принадлежащих одновременно А и В.

3º. Разность множеств А и В.

A/B = {x/x ∈ A и x ∉ B} – т.е. состоит из элементов А, не принадлежащих В.

4º. Симметрическая разность А и В (или кольцевая сумма А и В)

А Ө B = {x/x ∈ A и x ∉ B} ∪ {x/x ∈ В и x ∉ А} или {А\В ∪ В\А}

5º. Дополнение А до универсума

= U\A = {x|x ∈ Uux и x ∉ А}

Произведение множеств

Прямым (декартовым) произведением двух множеств А и В называется множество всех упорядоченных пар, в которой I элемент из множества А, II элемент – из множества В, т.е. А×В = {(а, в)/а Є А ̂в Є В}

Пример: А={2;5;7;9} и В ={2;4;7},

Тогда А×В = {(2,2) ; (2,4) ; (2,7) ; (5,2) ; (5,4) ; (5,7) ; (7,2) ; (7,4) ; (7,7) ; (9,2) ; (9,4); (9,7)}

А∩В={2,7}; А∪В={2,4,5,7,9}; А/В={5,9}; В/А={4}; А Ө В={4,5,9}

Элементы множества А×В называются точками; В паре (х, у) абсцисса – х и ордината – у точки, соответствующей этой паре.

Множество точек плоскости является прямым произведением вида R×R=R 2 , где R–множество действительных чисел.

R 2 называется декартовым квадратом на R.

Элементы теории графов

«Под множеством мы понимаем объединение в одно целое определенных, вполне различимых объектов нашей интуиции или нашей мысли» - так описал понятие «множество» Георг Кантор, основатель теории множеств.
Основные предпосылки канторовской теории множеств сводятся к следующему:
1° Множество может состоять из любых различимых объектов.
2° Множество однозначно определяется набором составляющих его объектов.
3° Любое свойство определяет множество объектов, которые этим свойством обладают.

Если х - объект, Р - свойство, Р(х) - обозначение того, что х обладает свойством Р, то через {х|Р(х)} обозначают весь класс объектов, обладающих свойством Р. Объекты, составляющие класс или множество, называют элементами класса или множества.

Термин «множество » употребляется как синоним понятий совокупность, собрание, коллекция некоторых элементов. Так, можно говорить о:
а) множестве пчёл в улье,
б) множестве точек отрезка,
в) множестве вершин квадрата или о множествах его сторон и диагоналей,
г) множестве студентов в аудитории и т.д.
В приведённых примерах в случаях а), в)-г) соответствующие множества состоят из определённого конечного числа предметов, такие множества называются конечными . Множество точек отрезка (пример б)) пересчитать невозможно, поэтому такие множества называются бесконечными . Множество, не содержащее ни одного элемента, называется пустым множеством.

Наиболее простая форма задания множества — перечисление его элементов, например А={4, 7, 13} (множество А состоит из трёх элементов — целых чисел 4, 7, 13). Другая часто применяемая форма задания — указание свойств элементов множества, например A = {x| x^2 ≤ 4} — множество чисел х, удовлетворяющих указанному условию.

Множества обычно обозначаются большими буквами А, В, С,…., а их элементы — малыми: а, в, с,… Запись а ∈ А (читается: а принадлежит А) или A ∋ a (читается: А содержит а) означает, что а есть элемент множества А. Пустое множество обозначается значком Ø.

Если каждый элемент множества В является также элементом множества А, множество В называется подмножеством множества А (обозначение — B ⊆ A или A ⊇ B).

Каждое множество является своим подмножеством (это самое «широкое» подмножество множества). Пустое множество является подмножеством любого множества (это самое «узкое» подмножество). Любое другое подмножество множества А содержит хотя бы один элемент множества А, но не все его элементы. Такие подмножества называются истинными, или собственными подмножествами. Для истинных подмножеств множества А применяется обозначение B ⊂ A или A ⊃ B. Если одновременно B ⊆ A и A ⊆ B, т.е каждый элемент множества В принадлежит А, и в то же время каждый элемент А принадлежит В, то А и В, очевидно, состоят из одних и тех же элементов и, следовательно, совпадают. В этом случае применяется знак равенства множеств: A = B. (Символы ∈, ∋, ⊂, ⊃, ⊆, ⊇ называются символами включения).

Геометрически множества обычно изображаются как некоторые множества точек плоскости. В любой имеющей смысл задаче обычно рассматриваются подмножества некоторого «наибольшего» множества U, которое называют универсальным множеством. Так, на рис. 1 изображено универсальное множество U и два его подмножества — множества А и В, B ⊂ A. Сами картинки типа рис. 1 называются диаграммами Эйлера-Венна .