Файл: 1. Основные понятия теории множеств. Способы задания множеств. Операции над множествами. Теоретикомножественные тождества.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 03.12.2023
Просмотров: 352
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Разбиением множества называется всякое представление этого множества в виде суммы непересекающихся подмножеств:, .Здесь – множество индексов, которое может быть конечным, счетным или несчетным. Множества называют слоями разбиения.Имеет место следующая теорема. Теорема 2. Для того чтобы отношение позволяло разбить множество на классы, необходимо и достаточно, чтобы было отношением эквивалентности.Приведем примеры использования отношения эквивалентности для образования математических понятий.
( ).Точной верхней (нижней) гранью подмножества называется наименьшая верхняя (наибольшая нижняя) грань для . Точная верхняя и точная нижняя грани обозначаются соответственно и .Линейный порядок на множестве называется полным, если каждое непустое подмножество множества имеет наименьший элемент. В этом случае множество называется вполне упорядоченным.Частично упорядоченное множество называется решёткой, или структурой, если для любых двух элементов существует точная нижняя и точная верхняя грани. Пример 6. Примеры решёток:– множество всех подмножеств данного множества, упорядоченное по включению;– всякое линейно упорядоченное множество; причем, если , то .4. Общие правила комбинаторики: правила суммы, произведения и биекции. Булеан конечного множества. Примеры.Правило суммыЭто правило позволяет найти число элементов в объединении двух конечных множеств и :. (1)Если множества и не пересекаются ( ), то . (2)Иногда правило суммы формулируют следующим образом: если объект можно выбрать способами, а объект – способами, то выбор «либо , либо » можно осуществить способами.Пример 1. Сколько имеется путей из вершины в вершину на решетке, показанной на рис. 1?Рис.1. Решетка размером [4 5]Обозначим множество всех путей из в через и разобьем его на два непересекающиеся подмножества: – множество путей, проходящих через вершину , – множество путей, проходящих через вершину . Тогда .Очевидно, что искомое количество путей зависит только от размеров решетки. Обозначим через количество путей в решетке размером [ ], где , – соответственно количество горизонтальных и вертикальных путей. Тогда причем . Пользуясь этим соотношением для данного примера , , получим:.Правило произведенияЭто правило позволяет подсчитать число кортежей, которые можно составить из элементов данных конечных множеств. Для двух множеств и (3)Из равенства (3) следует, что число упорядоченных пар, которые можно составить из элементов множеств и равно произведению числа элементов в этих множествах.Это правило можно сформулировать иначе:если объект можно выбрать способами и после каждого из таких выборов другой объект можно выбрать способами, то выбор «
и » можно осуществить способами.По индукции правило умножения можно распространить на любое число сомножителей в декартовом произведении:. (4)Наиболее часто последнее равенство применяется, когда :. (5)В этом случае множество называют алфавитом, его элементы – буквами, а элементы декартова произведения – словами в алфавите . Слова записывают как в обычном языке, то есть без разделения букв запятыми и без внешних скобок: . Число называют длиной слова.Пусть . Тогда правило (5) можно сформулировать следующим образом:число слов длины в алфавите из букв равно .Пример.2. Из 80 студентов 40 играют в футбол, а 50 – в волейбол, причем 27 студентов играют и в футбол и в волейбол. Сколько студентов играют хотя бы в одну из этих игр? Сколько студентов играют лишь в одну из этих игр? Сколько студентов не играют ни в одну из этих игр? Пусть – множество студентов, играющих в футбол, – множество студентов, играющих в волейбол. Тогда , , . Число студентов, играющих хотя бы в одну из этих игр, согласно формуле (2.1): . Число студентов, играющих только в футбол: , а только в волейбол: . Число студентов, играющих только в одну из этих игр: . Число студентов, не играющих ни в одну из этих игр: .Пример 3. Сколько существует 6-значных телефонных номеров? Алфавит состоит из 10 цифр, номер – слово длины 6 в этом алфавите. Поэтому количество номеров равно .Пример 4. Найти число слов, содержащих 4 буквы, в которых любые две соседние буквы различны (число букв в алфавите равно 33). Первую букву можно выбрать 33-мя способами, вторую, третью и четвертую – 32 способами. Число слов равно 33∙323=1081344.
Правило биекцииЭто правило, которое называется также принципом взаимно однозначного соответствия, формулируется следующим образом:если между множествами и можно установить взаимно однозначное соответствие (биекцию), то .В качестве примера применения этого принципа найдем мощность множества всех подмножеств данного множества . Такое множество называют булеаном множества и обозначают символом .Пусть – -множество. Так как мощность множества не зависит от природы его элементов, то можно принять .Поставим в соответствие произвольному подмножеству двоичное слово по следующему правилу:Это соответствие взаимно однозначное. Отсюда следует, что число всех подмножеств -множества равно числу двоичных слов длины , то есть .5. Метод включений и исключений. Пример.Поставим задачу подсчитать количество элементов в объединении конечных множеств , которые могут иметь непустые пересечения между собой, т. е. это объединение в общем случае не является разбиением. Для двух множеств имеем формулу (1). Обозначим и применим эту формулу для трех множеств, используя дистрибутивность операций объединения и пересечения множеств:(6)В результате по индукции получаем формулу включений и исключений:(7)Подсчитаем теперь число элементов , обладающих ровно свойствами. Покажем, что в этом случае имеет место следующая формула включений и исключений:. (9)Действительно, элемент, обладающий ровно , , свойствами, не будет учитываться в формуле (9), а элемент, обладающий ровно свойствами, будет учитываться только один раз, так как При из формулы (9), как частный случай, имеем формулу обращения (8). Использование формулы (9) в комбинаторике называют методом включений и исключений. Пример 6. Найти число перестановок -множества, оставляющих на месте ровно элементов.Решение. Перестановки элементов данного -множества будем считать элементами -множества. Обозначим и свойство перестановки, состоящее в том, что элемент с номером в результате данной перестановки остается на месте. Тогда, .По формуле (9). (10)6. Понятие выборки. Размещения и формулы для их подсчета с повторениями и без повторений элементов. Примеры.7. Понятие выборки. Перестановки и формулы для их подсчета с повторениями и без
повторений элементов. Примеры.8. Понятие выборки. Сочетания и формулы для их подсчета с повторениями и без повторений элементов. Примеры.Понятие выборкиНабор элементов из множества называется выборкой объема из элементов или -выборкой. Выборка называется упорядоченной, если порядок следования элементов в ней задан. Две упорядоченные выборки, различающиеся лишь порядком следования элементов, считаются различными. Если порядок следования элементов не является существенным, то выборка называется неупорядоченной. В выборках могут допускаться или не допускаться повторения элементов. В зависимости от способа формирования все выборки в комбинаторике классифицируют как размещения, перестановки и сочетания с повторениями и без повторений элементов.Размещения-размещением с повторениями из элементов называется упорядоченная -выборка, в которой элементы могут повторяться. Число всех таких выборок, которые отличаются друг от друга составом элементов или их порядком, равно числу векторов в декартовом произведении . Это число обозначают . По правилу произведения получаем. (1)Пример 1. Для запирания сейфа используется диск, на который нанесены 12 символов, а секретное слово состоит из 5 символов. Сколько неудачных попыток может быть сделано человеком, не знающим секретного слова?Общее число комбинаций равно . Значит, неудачных попыток может быть 248831.-размещением без повторений из элементов называется упорядоченная -выборка, в которой элементы не повторяются. Число всех упорядоченных -множеств с различными элементами, которые можно составить из элементов -множества , обозначают .Для вычисления необходимо сделать выборов. 1-й элемент можно выбрать способами, 2-й – ( ) способами и т. д. Последний -й элемент можно выбрать способами. По правилу произведения. (2)Здесь – « -факториал» (0!=1!=1).Пример 2. Научное общество состоит из 25 человек. Надо выбрать президента общества, вице-президента, ученого секретаря и казначея. Сколькими способами может быть сделан этот выбор, если каждый член общества может занимать лишь один пост?Ответ: .ПерестановкиРешим следующую комбинаторную задачу.Сколькими способами можно упорядочить -множество ?Перестановками без повторений
-
Понятие вектора. Сначала вводится понятие направленного отрезка, как пары точек . Два отрезка и объявляются эквивалентными, если середины отрезков и совпадают. Далее проверяется, что это отношение между направленными отрезками рефлексивно, симметрично и транзитивно. Класс эквивалентных отрезков и есть вектор. -
Построение рациональных чисел из целых. Рассмотрим всевозможные пары из целых чисел такие, что . Пары и объявляются эквивалентными, если . Далее проверяется рефлексивность, симметричность и транзитивность. Класс эквивалентных пар – рациональное число.
( ).Точной верхней (нижней) гранью подмножества называется наименьшая верхняя (наибольшая нижняя) грань для . Точная верхняя и точная нижняя грани обозначаются соответственно и .Линейный порядок на множестве называется полным, если каждое непустое подмножество множества имеет наименьший элемент. В этом случае множество называется вполне упорядоченным.Частично упорядоченное множество называется решёткой, или структурой, если для любых двух элементов существует точная нижняя и точная верхняя грани. Пример 6. Примеры решёток:– множество всех подмножеств данного множества, упорядоченное по включению;– всякое линейно упорядоченное множество; причем, если , то .4. Общие правила комбинаторики: правила суммы, произведения и биекции. Булеан конечного множества. Примеры.Правило суммыЭто правило позволяет найти число элементов в объединении двух конечных множеств и :. (1)Если множества и не пересекаются ( ), то . (2)Иногда правило суммы формулируют следующим образом: если объект можно выбрать способами, а объект – способами, то выбор «либо , либо » можно осуществить способами.Пример 1. Сколько имеется путей из вершины в вершину на решетке, показанной на рис. 1?Рис.1. Решетка размером [4 5]Обозначим множество всех путей из в через и разобьем его на два непересекающиеся подмножества: – множество путей, проходящих через вершину , – множество путей, проходящих через вершину . Тогда .Очевидно, что искомое количество путей зависит только от размеров решетки. Обозначим через количество путей в решетке размером [ ], где , – соответственно количество горизонтальных и вертикальных путей. Тогда причем . Пользуясь этим соотношением для данного примера , , получим:.Правило произведенияЭто правило позволяет подсчитать число кортежей, которые можно составить из элементов данных конечных множеств. Для двух множеств и (3)Из равенства (3) следует, что число упорядоченных пар, которые можно составить из элементов множеств и равно произведению числа элементов в этих множествах.Это правило можно сформулировать иначе:если объект можно выбрать способами и после каждого из таких выборов другой объект можно выбрать способами, то выбор «
и » можно осуществить способами.По индукции правило умножения можно распространить на любое число сомножителей в декартовом произведении:. (4)Наиболее часто последнее равенство применяется, когда :. (5)В этом случае множество называют алфавитом, его элементы – буквами, а элементы декартова произведения – словами в алфавите . Слова записывают как в обычном языке, то есть без разделения букв запятыми и без внешних скобок: . Число называют длиной слова.Пусть . Тогда правило (5) можно сформулировать следующим образом:число слов длины в алфавите из букв равно .Пример.2. Из 80 студентов 40 играют в футбол, а 50 – в волейбол, причем 27 студентов играют и в футбол и в волейбол. Сколько студентов играют хотя бы в одну из этих игр? Сколько студентов играют лишь в одну из этих игр? Сколько студентов не играют ни в одну из этих игр? Пусть – множество студентов, играющих в футбол, – множество студентов, играющих в волейбол. Тогда , , . Число студентов, играющих хотя бы в одну из этих игр, согласно формуле (2.1): . Число студентов, играющих только в футбол: , а только в волейбол: . Число студентов, играющих только в одну из этих игр: . Число студентов, не играющих ни в одну из этих игр: .Пример 3. Сколько существует 6-значных телефонных номеров? Алфавит состоит из 10 цифр, номер – слово длины 6 в этом алфавите. Поэтому количество номеров равно .Пример 4. Найти число слов, содержащих 4 буквы, в которых любые две соседние буквы различны (число букв в алфавите равно 33). Первую букву можно выбрать 33-мя способами, вторую, третью и четвертую – 32 способами. Число слов равно 33∙323=1081344.
Правило биекцииЭто правило, которое называется также принципом взаимно однозначного соответствия, формулируется следующим образом:если между множествами и можно установить взаимно однозначное соответствие (биекцию), то .В качестве примера применения этого принципа найдем мощность множества всех подмножеств данного множества . Такое множество называют булеаном множества и обозначают символом .Пусть – -множество. Так как мощность множества не зависит от природы его элементов, то можно принять .Поставим в соответствие произвольному подмножеству двоичное слово по следующему правилу:Это соответствие взаимно однозначное. Отсюда следует, что число всех подмножеств -множества равно числу двоичных слов длины , то есть .5. Метод включений и исключений. Пример.Поставим задачу подсчитать количество элементов в объединении конечных множеств , которые могут иметь непустые пересечения между собой, т. е. это объединение в общем случае не является разбиением. Для двух множеств имеем формулу (1). Обозначим и применим эту формулу для трех множеств, используя дистрибутивность операций объединения и пересечения множеств:(6)В результате по индукции получаем формулу включений и исключений:(7)Подсчитаем теперь число элементов , обладающих ровно свойствами. Покажем, что в этом случае имеет место следующая формула включений и исключений:. (9)Действительно, элемент, обладающий ровно , , свойствами, не будет учитываться в формуле (9), а элемент, обладающий ровно свойствами, будет учитываться только один раз, так как При из формулы (9), как частный случай, имеем формулу обращения (8). Использование формулы (9) в комбинаторике называют методом включений и исключений. Пример 6. Найти число перестановок -множества, оставляющих на месте ровно элементов.Решение. Перестановки элементов данного -множества будем считать элементами -множества. Обозначим и свойство перестановки, состоящее в том, что элемент с номером в результате данной перестановки остается на месте. Тогда, .По формуле (9). (10)6. Понятие выборки. Размещения и формулы для их подсчета с повторениями и без повторений элементов. Примеры.7. Понятие выборки. Перестановки и формулы для их подсчета с повторениями и без
повторений элементов. Примеры.8. Понятие выборки. Сочетания и формулы для их подсчета с повторениями и без повторений элементов. Примеры.Понятие выборкиНабор элементов из множества называется выборкой объема из элементов или -выборкой. Выборка называется упорядоченной, если порядок следования элементов в ней задан. Две упорядоченные выборки, различающиеся лишь порядком следования элементов, считаются различными. Если порядок следования элементов не является существенным, то выборка называется неупорядоченной. В выборках могут допускаться или не допускаться повторения элементов. В зависимости от способа формирования все выборки в комбинаторике классифицируют как размещения, перестановки и сочетания с повторениями и без повторений элементов.Размещения-размещением с повторениями из элементов называется упорядоченная -выборка, в которой элементы могут повторяться. Число всех таких выборок, которые отличаются друг от друга составом элементов или их порядком, равно числу векторов в декартовом произведении . Это число обозначают . По правилу произведения получаем. (1)Пример 1. Для запирания сейфа используется диск, на который нанесены 12 символов, а секретное слово состоит из 5 символов. Сколько неудачных попыток может быть сделано человеком, не знающим секретного слова?Общее число комбинаций равно . Значит, неудачных попыток может быть 248831.-размещением без повторений из элементов называется упорядоченная -выборка, в которой элементы не повторяются. Число всех упорядоченных -множеств с различными элементами, которые можно составить из элементов -множества , обозначают .Для вычисления необходимо сделать выборов. 1-й элемент можно выбрать способами, 2-й – ( ) способами и т. д. Последний -й элемент можно выбрать способами. По правилу произведения. (2)Здесь – « -факториал» (0!=1!=1).Пример 2. Научное общество состоит из 25 человек. Надо выбрать президента общества, вице-президента, ученого секретаря и казначея. Сколькими способами может быть сделан этот выбор, если каждый член общества может занимать лишь один пост?Ответ: .ПерестановкиРешим следующую комбинаторную задачу.Сколькими способами можно упорядочить -множество ?Перестановками без повторений