Основные понятия теории множеств. Дневной и сокращенной формы обучения

ЛЕКЦИЯ № 1

Воронеж

Дневной и сокращенной формы обучения

КУРС ЛЕКЦИЙ ПО ДИСЦИПЛИНЕ

Моделирования и управления

Кафедра информационных технологий,

Ю.В. БУГАЕВ, И.Ю. ШУРУПОВА

‘”ДИСКРЕТНАЯ МАТЕМАТИКА”

Для студентов, обучающихся по направлениям

230400 –"Информационные системы и технологии",

230700 – "Прикладная информацика"

Для множества не существует строгого определения, поэтому введем описательные понятия множества и его элементов.

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

Пусть имеется множество А, элементом которого является предмет а, это записывается как А={а}. Например, В={1, 2, 3}.

Если какой-то элемент а принадлежит множеству А, то это обозначается аÎА, а если b не принадлежит А, то - bÏА. Например, пусть А - множество четных натуральных чисел, тогда 6ÎА, а 3ÏА.

Пусть имеется два множества А и В, причем все элементы множества А принадлежат множеству В, т.е. если хÎА, то хÎB. В этом случае говорят, что множество А включено в множество В. Обозначается: АÍВ (Í - символ нестрогого включения, т.е. возможно совпадение множеств). Множество А совпадает с множеством В (А = В), если все элементы множества В являются элементами множества В и все элементы множества В являются элементами множества А. Это можно записать в виде

(АÍВ и ВÍА) <=> (А = В).

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

Пример: А = { 1, 2, 3 }, В = { 0, 1, 2, 3 }, АÌВ.

Возможны два способа задания множества.

1. Перечислением элементов, т.е. в фигурных скобках дается полное перечисление элементов данного множества. Например: N = {1,2,...,n,...} - множество натуральных чисел.

2. С помощью указания характерного свойства (указание свойства, которым обладают только элементы данного множества). Символически это записывается в виде A={x | P(x)} и читается - A есть множество всех элементов х, обладающих свойством P(x).

При задании множества вторым способом возможны различные противоречия и парадоксы. Рассмотрим примеры таких парадоксов.

1) Парадокс парикмахера: в городе жил парикмахер, который брил всех, кто не брился сам. Кто же брил парикмахера?

2) Пусть имеем натуральное число 11218321 - одиннадцать миллионов двести восемнадцать тысяч триста двадцать один. Это число можно описать с помощью восьми слов. Пусть А - множество натуральных чисел, которые нельзя определить с помощью фразы, имеющей меньше 20 русских слов. Обозначим а_min - наименьшее число из множества А, причем а_minÎA. Число а_min можно определить следующим образом: наименьшее натуральное число, которое нельзя определить с помощью фразы, имеющей менее двадцати слов. В этой фразе 14 слов. Значит, а_min можно определить с помощью фразы, содержащей менее 20 слов.

Тогда получается, что а_minÏ А.

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

В теории множеств имеется специальное множество, называемое пустым множеством (Æ), которое не содержит ни одного элемента. Пустое множество по определению содержится в любом множестве А (ÆÎА). Это понятие вводится из следующих соображений. Задавая множество вторым способом не всегда заранее можно быть уверенным, существуют ли элементы, ему принадлежащие. Например, можно говорить о множестве четырехугольников на плоскости, у которых все углы прямые, а диагонали не равны. Только знания основ геометрии позволяют убедиться, что таких четырехугольников не существует и, следовательно, это множество пусто.

Большинство утверждений теории множеств связано с равенством двух множеств и включением одного множества в другое. Поэтому надо детально разобраться в методах доказательства этих фактов.

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

(x Î А) => (x Î В).

2. Доказательство равенства А = В.

Оно сводится к доказательству двух включений АÍВ и ВÍА.

Пример 1. Докажем следующую теорему. Для любых множеств А, В и С выполняется закон транзитивности нестрогого включения, т.е. если АÍВ и ВÍС, то из этого следует, что АÍС.

Доказательство. Пусть x - любой элемент множества А, (xÎА), тогда в силу условия АÍВ, по определению нестрогого включения, элемент х принадлежит множеству В (хÎB). После доказательства этого факта, аналогично, используя условие ВÍС можно доказать, что х принадлежит С (хÎС).

В качестве исходного допущения мы приняли, что x – любой элемент из А. Из этого допущения при выполнении условий а) и б) получено следствие хÎС. По определению нестрогого включения это означает АÍС, что и требовалось доказать.

Пример 2. Пусть А={1,6}, В ={х | х²-7х+6=0}. Последнее читается как, В является множеством элементов х, для которых выполняется условие х² - 7х + 6 = 0. Включение АÍВ доказывается подстановкой элементов множества А в это условие. Для доказательства обратного включения ВÍА нужно найти все корни уравнения и убедиться, что они равны 1 и 6, т.е. принадлежат А. Выполнение обоих нестрогих включений означает равенство множеств А и В.