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

Элементы теории множеств

§1. Множества и их спецификация (способы задания)

Понятие множества - одно из основных понятий математики. Вообще говоря, это неопределяемое понятие, такое как точка или прямая в геометрии, как число в арифметике.

Ввел это понятие немецкий математик Георг Кантор(1849-1918). Он определил его так: множество есть многое мыслимое как единое целое.

Множество — это совокупность определенных различаемых объектов, собранных по какому-либо общему признаку. Объекты, из которых составлено множество, называются элементами множества.

Утверждения типа ”объект а есть элемент множества А” и “объект а принадлежит множеству А”, которые имеют один и тот же смысл, записывают а_А, а если объект а не является элементом множества А, то пишут а_А.

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

Множество, которое подчиняется лишь такому требованию, может содержать элементы любой природы:

· множество зарезервированных слов языка Паскаль;

· множество натуральных чисел;

· множество символов, доступных данному компьютеру;

· множество левых ботинок.

Множества будем обозначать прописными буквами А, В, С,..., а элементы строчными а, b, с,...

Есть и некоторые специальные, часто встречающиеся, множества, для которых мы будем использовать специальные обозначения: R- множество действительных чисел; Q- множество рациональных чисел; Z- множество целых чисел; N- множество натуральных чисел.

Одно и то же множество можно описать по-разному, например:

1) множество всех четных натуральных чисел;

2) множество всех чисел вида 2n, где n - натуральное.

Как видим, эти два описания определяют одно и то же множество.

Поэтому нужно ответить на вопрос: когда два описания определяют одно и то же множество?

Под спецификацией множества будем понимать символический способ его задания. Существует два основных способа спецификации множеств:

1. перечислить все его элементы: А={1,2,3,4,5}, B={begin, end, if, then, do, for, while, repeat, until,...}

2. записать признак, определяющий его элементы в виде высказывательной формы, то есть в виде {x| P(x) истинно}, где Р(х)— высказывательная форма или проще {x| P(x)} читается: множество состоит из таких элементов х, что истинно Р(х)( то есть множество определяется как множество истинности некоторой высказывательной формы).

Пример: А={a| a_N)a<6}, B={x| x-зарезервированное слово языка Паскаль}.

Выбор той или иной спецификации зависит от конкретной задачи, однако в любом случае она должна удовлетворять требованию различимости объектов.

Приведем некоторые примеры.

Учитывая определение равенства множеств: {7,8,9} = {8,9,7} = {9,8,7} = ={7,8,9,8,9}, поскольку элемент каждого из выписанных здесь множеств является элементом другого. Однако если три первые спецификации можно как-то объяснить (например, требование какой-то задачи), то последнюю спецификацию следует считать неудачной, поскольку не все элементы можно отличить друг от друга.

Рассмотрим множество X={“Введение в Паскаль”, ”Основы структурных данных”, ”Введение в Паскаль”}. Что это: множество, состоящее из двух книг, записанных по невнимательности дважды, или это три книги, две из которых имеют одинаковое название? В последнем случае две книги “Введение в Паскаль” надо как-то разделить. Из данной информации нельзя извлечь правильный ответ. Поэтому со спецификациями надо быть осторожнее.

Элементами множества могут быть опять же множества:

А={1, {2,3}} — множество, состоящее из двух элементов, а множество В={1,2,3} — из трех. C={{3,5}, {5,7}, {7,9}} — оно состоит из трех элементов. D={3, 5, 7, 9} — из четырех. Конечно, С_D и A_B.

Задача 1: Описать словами рекурсивно заданное множество

X={x|x_Z)(x=1*(x-2) _X)}.

Определение 1: Два множества А и В называют равнымии пишут А=В, если А и В содержат одни и те же элементы.

Формально: два множества А и В равны, если "x (x_A + x_B).

Определение 2: Множество А называется подмножеством множества В, если каждый элемент множества А принадлежит множеству В ("х(х_А.х_В)).

Это записывают так: А_В, читаем: А содержится в В. Например: 3_{3,5,7}, {3}_{3,5,7}, аналогично {3,7}_{3,5,7}. А вот для множества {1;{2,3}} можно записать: {2,3}_{1;{2,3}}; 2_{1;{2,3}}. Чтобы заработал знак включения надо записать элемент {2,3} как множество, то есть {{2,3}}_{1;{2,3}}.

Другие примеры: 1. Q_R. 2. Z_Q, 3. N_R, 4. A={x|0_x<4 ) x_R}, B={y|1_y<3 ) y_R}, тогда B_A.

Определение 3: Множество А называется собственным подмножествоммножества В, если А_В и А_В. В случае, если надо подчеркнуть, что А_В или А=В будем писать А_ В.

Например, можно записать А_А, на самом деле будем использовать символ _,то есть А_А — почему?

Задача 2: Доказать, что если А_В и В_С, то А_С.

По определению подмножества, если А_В и В_А, то А=В (объясните, почему ).

Таким образом, чтобы доказать равенство двух множеств А и В надо доказать, что 1) А_В и 2) В_А. Фактически это означает, что любой элемент множества А является элементом множества В и любой элемент множества В является элементом множества А, что соответствует определению равенства двух множеств.

И в заключение введем еще два важных понятия.

Определение 4: Множество, не содержащее ни одного элемента, называется пустым множеством. Пустое множество обозначается символом Æ.

Формализуя: множество А пусто, если "x (x_A)— истинно.

Утверждение 1: Пустое множество единственно.

Доказательство:

Пусть C и D— пустые множества, тогда высказывание "x (x_С+x_D) истинно, поскольку x_С и x_D оба ложны. А по определению 1 это и означает, что С = D. Что и требовалось доказать.

Утверждение 2: Пустое множество является подмножеством любого множества.

Доказательство:

Действительно, для каждого x импликация x__.x_A истинна, так как посылка x__ ложна. Что и требовалось доказать.

Определение 5: Множество всех подмножеств множества X назовем степенью множества Хи будем обозначать Р(X).

Например, если X={1,2,3}, то P(X)={ _, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, X}.

Числовые множества

С дошкольного возраста ребенок оперирует натуральными числами, то производя счет предметов, то пересчитывая множество пальцев на руках. Основным понятием при введении понятия множества натуральных чисел N является отношение «непосредственно следовать за», которое определяется следующими аксиомами Пеано.

Аксиома 1. В множестве N существует элемент, непосредственно не следующий ни за каким элементом этого множества, который называется единицей и обозначается символом 1.

Аксиома 2. Для каждого элемента п множества N, существует единственный элемент (п+1), непосредственно следующий за п.

Аксиома 3. Для каждого элемента п из N существует не более одного элемента (п-1), за которым непосредственно следует п.

Аксиома 4. Любое подмножество Р множества N совпадает с N, если для него выполняются свойства: 1) 1 содержится в Р; 2) из того, что п содержится в Р, следует, что и (п+1) содержится в Р.

На основании аксиом Пеано сформулируем определение множества натуральных чисел.

Определение. Множество N, элементы которого удовлетворяют аксиомам 1-4, т.е. находятся в отношении «непосредственно следовать за», называется множеством натуральных чисел, а его элементы – натуральными числами.

Расширением множества натуральных чисел N является множество целых чисел Z, которое является объединением натуральных чисел, числа нуль и чисел противоположных натуральным числам.

Расширением множества целых чисел является множество рациональных чисел Q, представляющее собой объединение целых и дробных чисел. Множество всех чисел представимых в виде несократимой дроби m/n, где m может быть любым целым числом, (не исключая нуля), т.е. m Î Z, а n – натуральное число, т.е. nÎ N, составляют множество рациональных чисел. Любое рациональное число можно записать в виде бесконечной десятичной периодической дроби, и наоборот, любая бесконечная десятичная периодическая дробь представляет собой рациональное число.

Существуют числа, которые нельзя представить в виде несократимой дроби, т.е. не принадлежат множеству рациональных чисел. Такие числа составляют множество иррациональных чисел I, их можно представить в виде бесконечной десятичной непериодической дроби. Например, длина диагонали квадрата со стороной 1 должна выражаться некоторым положительным числом r²=1²+1²(по теореме Пифагора), т.е. таким, что r²=2. Число r не может быть целым, 1² = 1, 2 ² = 4 и т.д. Число r не может быть и дробным: если r = m/n - несократимая дробь, где n¹1, то r²=m²/n² тоже будет несократимой дробью, где n² ¹ 1; значит, m²/n² не является целым числом, а потому не может равняться 2. Поэтому длина диагонали квадрата выражается иррациональным числом, оно обозначается . Аналогично, не существует рационального числа, квадрат которого равен 5, 7, 10. Соответствующие иррациональные числа обозначаются , , . Противоположные им числа также иррациональны, они обозначаются - ,- ,- .

Множество иррациональных чисел бесконечно. Например, число p, выражающее отношение длины окружности к диаметру, нельзя представить в виде обыкновенной дроби – это иррациональное число.

Множество, элементами которого являются рациональные и иррациональные числа называется множеством действительных чисел и обозначается буквой R. Каждому действительному числу соответствует единственная точка координатной прямой. Каждая точка координатной прямой соответствует единственному действительному числу. Множество действительных чисел называют также числовой прямой.

Нами рассмотрен процесс расширения понятия числа от натуральных к действительным, который был связан с потребностями практики и с нуждами самой математики. Необходимость выполнения деления привела от натуральных чисел к понятию дробных положительных чисел; затем операция вычитания привела к понятиям отрицательных чисел и нуля; далее, необходимость извлечения корней из положительных чисел – к понятию иррационального числа. Множество, на котором выполнимы все эти операции, есть множество действительных чисел, однако не все операции выполнимы на данном множестве. Например, нет возможности извлечь корень квадратный из отрицательного числа или решить квадратное уравнение х² + х + 1 = 0. Значит, есть потребность в расширении множества действительных чисел.

Введем число i, такое, что i² = - 1. Это число позволит извлекать корни из отрицательных чисел. Итак, расширением множества действительных чисел есть множество комплексных чисел, которое обозначается буквой С. Подробно, с множеством комплексных чисел, мы познакомимся позже.

Будем пользоваться обозначениями:

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

Z - множество целых чисел;

Q - множество рациональных чисел,

R - множество действительных чисел

С - множество комплексных чисел.

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

1. Объединение. Объединением множеств А и В называется множество, состоящее из тех и только тех элементов, которые принадлежат хотя бы одному из множеств А и В. Обозначается: АÈВ.

Формально: А_В={x| x_A * x_B}.

Примеры:1. {1;2} _ {2;3} = {1; 2; 3}

2. {x| 1<x<10} _ {y| 10_y<11} = {z| 1<z<11}

в математике (1;10) _[10;11) = (1; 11)

3.Легко доказать, что A_A_B и B_A_B.

2. Пересечение. Пересечением множеств А и В называется множество, состоящее из тех и только тех элементов, которые принадлежат как множеству А, так и множеству В.

Обозначается: А_В.

Формально: А _ В = {x| x_A ) x_B}.

Примеры: 1. {1; 2} _ {2; 3} = {2}

2. (1; 10) _ [10; 11) = _

3. Z _ {x| x_R ) x>0} = N

4. Легко доказать, что A _ В _ A и A _ В _ B.

3. Разность двух множеств. Разностью множеств А и В называется множество, элементами которого являются элементы множества А, не принадлежащие множеству В, и только они. Обозначается: А \ В.

Формально: A \ B = {x| x_A ) x_B}.

Примеры: 1. Если A={1; 2; 3} и B={2; 3; 4}, то A \ B={1}, а B\A={4}.

2.Легко доказать, что если A _ B=_ , то A \ B = A, а B \ A = B.

4. Симметрическая разность.Эта операция используется нечасто, однако бывает полезной в некоторых приложениях, например в машинной арифметике.Симметрической разностью двух множествназывается множество, которое определяется следующим образом: ADB= (A È B) \ (A _ B), то есть из объединения выбрасываются общие элементы.

А это значит, что A D B состоит из тех и только тех элементов, которые либо принадлежат А, но не принадлежат В, либо принадлежат В, но не принадлежат А.

Формально: A D B ={x| x_A\B * x_B\A}.

Примеры: 1. A={1, 2, 3}; B={2, 3, 4}, то A D B={1, 4}.

2. Доказать, что если A _ B =_, то A D B=A _ B.

Теорема 1: (свойства операций объединения и пересечения): Для любых множеств А, В и С выполняются следующие законы:

1) А _ А = А - идемпотентность объединения.

2) А _ А = А - идемпотентность пересечения.

3) А _ В = В _ А - коммутативность объединения.

4) А _ В = В _ А - коммутативность пересечения.

5) А _ ( В _ С ) = ( А _ В ) _ С - ассоциативность объединения.

6) А _ ( В _ С ) = ( А _ В ) _ С - ассоциативность пересечения.

7) А _ ( В _ С ) = ( А _ В ) _ ( А _ С ) - дистрибутивность объединения относительно пересечения.

8) А _ ( В _ С ) = ( А _ В )_ ( А _ С ) - дистрибутивность пересечения относительно объединения.

Доказательство:

Докажем, например, свойство 8: пусть x_ A_(B_C) . x_A и x_(B_C), но второе означает, что x_B или x_C; если x_B, то x_(A_B), а если x_C, то x_(A_C), но это означает что x_(A_B) или x_(A_C) . x_(A_C)_ (A_B). С другой стороны пусть

x_(A_C)_ (A_B) . x_(A_B) или x_(A_C). Запишем логически x_(A_B)*x_(A_C), по определению пересечения истинно высказывание x_A)x_B*x_A)x_C T x_A)(x_B*x_C) º x_A_(B_C).Что и требовалось доказать.

Пример: Предположим, что мы имеем две программы P и Q и что А- множество всех значений данных, доступных P, а В- множество всех данных, доступных Q. Тогда А_В- множество всех данных, доступных P и Q; А_В- множество всех данных, доступных хотя бы одной из программ; А\В- множество данных, доступных P и недоступных Q; В\А- множество данных, доступных Q и недоступных P; АDВ- множество всех данных, доступных только одной из программ.

Не нашли, что искали? Воспользуйтесь поиском по сайту: