Полная версия

Главная arrow Математика, химия, физика arrow Дискретная математика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

ТЕОРИЯ МНОЖЕСТВ И БИНАРНЫХ ОТНОШЕНИЙ

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

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

Такой подход называется аксиоматическим [1].

При изучении всех разделов дискретной математики, в том числе и элементов теории множеств и бинарных отношений, мы также используем аксиоматический подход [1—6, 11].

Основные понятия теории множеств

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

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

Во множество можно объединять самые разные объекты. Например, множество натуральных чисел А, множество целых чисел Z, множество действительных чисел /?, множество предметов в вашей комнате IV и т.д.

Элементами множества могут выступать другие множества, например /) = [1]. Такое множество V называется классом или семейством [2].

Количество элементов во множестве называется мощностью или кардинальным числом. Например, мощность множества М= {а, Ь, с} равна 3, М — 3. В зависимости от мощности множества могут быть конечные и бесконечные. Множество, в состав которого не входит ни одного элемента, называется пустым и обозначается как 0. Мощность пустого множества равна нулю. Но мощность множества С, элементом которого является пустое множество, равна единице, С = {0},С = 1.

Множества равномощны, если их мощности равны. Например, множества /) = [1] и К={а, Ъ} равномощны.

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

Если каждому элементу бесконечного множества можно поставить в соответствие натуральное число я, е N, причем только одно без пропусков и повторений, то это множество называется счетнобесконечным и его мощность равна |А| = А0 (алеф-нуль), первому трансфинитному числу. Второе трансфинитное число А, алеф, равно мощности множества Я действительных чисел. Известно и третье

трансфинитное число А = 2А = 22 °, алеф-один, равное множеству точек в пространстве, заданных координатами (х,у, г). Трансфинитные числа обозначают буквами еврейского алфавита.

Кантор создал шкалу трансфинитных чисел: алеф-ноль, алеф, алеф-один,... .

Считаем, что множество счетное, если выполняется один из двух случаев:

  • • множество состоит из конечного числа элементов, т.е. его кардинальное число совпадает с одним из натуральных чисел;
  • • множество счетно-бесконечное, т.е. его мощность совпадает

с мощностью множества натуральных чисел.

Множество несчетное, если оно бесконечно и неравномощно множеству натуральных чисел.

Множество А называется подмножеством В, если каждый элемент аI из А, я, е А, принадлежит одновременно и множеству В, а1 е В, А В. В предельном случае множества Аи В могут состоять из одних и тех же элементов.

Если во множестве В найдется хотя бы один элемент х,-, который не принадлежит А, Зх/, х,- <е В, х,- й А, то А — собственное подмножество В, А с В. Пустое множество 0 всегда является подмножеством любого множества В.

Между понятиями «подмножество» и «собственное подмножество» существует значительная разница. Так, подмножество А может совпадать с самим множеством В, т.е. А < |2?|, но собственное подмножество С всегда состоит из меньшего количества элементов, чем В, т.е. |С| < В.

Например, рассмотрим два множества Л/, = {а, Ъ, с} и М2 = {а, Ь, с, с!}. Множество М, является собственным подмножеством М2, так как в М2 имеется элемент б, не принадлежащий множеству Мх.

Множество В в приведенных выше определениях часто называют надмножеством (собственным надмножеством) множества А

Множества Л и В равны, если являются подмножествами (надмножествами) друг друга.

Для каждого множества М можно построить новое множество, элементами которого являются все подмножества М и только они. Тогда множество М называется универсумом и обозначается как /, а множество всех его подмножеств — буяеаном В(1).

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

Например, возьмем в качестве универсума / множество натуральных чисел на отрезке [1, 3], 1= {1, 2, 3}, тогда булеан В(1) = {0, {1}, {2}, {3}, {1,2}, {1,3}, {2, 3}, {1,2, 3}}. Если мощность универсума равна

ш, то мощность его булеана всегдаВ(1) = 2т.

Теорема 1.1. Основная теорема о конечных множествах

Любое конечное множество не может быть эквивалентно никакому своему собственному подмножеству.

При определении множеств и подмножеств можно столкнуться с парадоксом Рассела, который заключается в следующем. Рассмотрим множество А всех множеств В, не содержащих себя в качестве элементов, А = {В/В Если множество Л существует, то содержит ли А в качестве элемента самого себя, т.е. А е А? При ответе на этот вопрос мы сталкиваемся с логическим противоречием: если А е А, то по определению элементов множества А ? А. Если А то А е А.

Для задания множеств необходимо указать элементы, которые ему принадлежат. Это можно сделать следующим образом [3]:

  • • перечислить элементы множества, например М- {1, 2, 3, 4, 5};
  • • использовать характеристический предикат, задающий свойства

элементов, например М = {х/х е N и х < 6};

• с помощью производящей функции, которая помогает вычислить

каждый элемент рассматриваемого множества, например М =

= {х / й)г / := 1 Ю 5 бо х := /}.

Во всех трех случаях мы задаем множество М, содержащее пять натуральных чисел от 1 до 5.

  • [1] синий, красный, зеленый}, {шар, куб, цилиндр, пирамида
  • [2] синий, красный, зеленый}, {шар, куб, цилиндр, пирамида
 
<<   СОДЕРЖАНИЕ   >>