Основные свойства декартова произведения.

1. Если , то . То есть декартово произведение множеств не обладает свойством коммутативности.

Действительно, по определению если то , а . Но так как , то . Отсюда .

2. Декартово произведение множеств не обладает свойством ассоциативности: для любых множеств .

3. Если хотя бы одно из множеств А или В пусто, то и декартово произведение этих множеств есть множество пустое:

Ø= Ø Ø Ø = Ø.

Это свойство следует из понятия декартова произведения и понятия пустого множества.

4. Для любых трех множеств справедливы следующие утверждения:

4.1.

4.2.

4.3.

Докажем, например, свойство 4.3.

Обозначим множество , а множество . Покажем, что .

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

Докажем, что .

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

Так как и , то , что и требовалось доказать.

Теорема: Число элементов в декартовом произведении двух конечных множеств А и В равно произведению чисел элементов в каждом из них:

.

Раздел II. Элементы комбинаторики

Лекция № 7. АЛГОРИТМЫ И МОДЕЛИ.

Контрольные вопросы:

1. Понятие алгоритма и его свойства.

2. Способы задания алгоритмов.

3. Классификация алгоритмов.

4. Понятия модели и моделирования.

5. Метод математического моделирования. Ос­новные виды математических моделей.

6. Аксиоматический метод и моделирование.

7. Связь с начальным курсом математики.

Литература:

Лекции №№ 8 - 9. ОСНОВЫ КОМБИНАТОРИКИ.

Контрольные вопросы:

1. Понятие о комбинаторной задаче.

2. Правила суммы и произведения.

3. Соединения без повторений и с повторениями.

4. Бином Ньютона и треугольник Паскаля. Число подмножеств конечного множества.

5. Комбинаторные задачи в начальном курсе математики.

Литература: (1) гл. I, § 2 пп. 8-11; (2) гл. I, § 6, с. 142-149; (3) гл. I, § 2 пп.6-8; (4) гл. V, с. 151-155; (5) гл. IV, §§ 4.1 – 4.7.

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

Как раздел математики комбинаторика возникла в 16 веке. Ее возникновение и развитие связано с именами ученых Н. Тарталья (1500-1557гг), Б. Паскаля (1623-1662гг), П. Ферма (1601-1665гг). Позднее крупный вклад в развитие комбинаторных методов был сделан Г. Лейбницем (1646-1716гг), я. Бернулли (1654-1705 гг), л. Эйлером (1707-1783гг).

Решение большинства комбинаторных задач основано на применении двух основных правил: правила суммы и правила произведения.

Задача 1: В вазе лежит 8 слив и 6 абрикосов. Сколькими способами можно выбрать из вазы один плод?

Переведем задачу на язык теории множеств. Имеются 2 множества: . Эти множества не имеют общих элементов: Ø. Требуется узнать, сколько существует способов выбора одного элемента, принадлежащего множеству А или множеству В, т.е. объединению этих множеств.

Элемент из множества А можно выбрать 8-ю способами, из множества В – 6-ю способами. А так как эти множества не имеют общих элементов, то выбрать один элемент, принадлежащий А или В можно 8+6 =14 способами.

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

Правило суммы: если элемент а можно выбрать n способами, а элемент b – m способами, причем ни один из способов выбора элемента а не совпадает со способом выбора элемента b, то выбор элемета «а либо b» можно осуществить (n+m) cпособами.

Задача 2: В столовой имеется 4 вида первых блюд и 6 видов вторых. Сколькими способами можно выбрать обед, состоящий из одного первого и одного второго блюда?

Решение такого вида задач сводится к подсчету числа упорядоченных пар, когда известно число способов выбрать первую компоненту и вторую компоненту.

Пусть . Множество всех упорядоченных пар элементов, состоящих из элементов множеств А и В, образует декартово произведение этих множеств. Известно, что . Тогда наша задача будет иметь решение: (способа).

Правило произведение: если элемент а можно выбрать n способами, а элемент b – m способами, то пару (а; b) можно выбрать способами.

Правило суммы и произведения легко распространяется на тот случай, когда множеств не два, а «n».

Пусть даны множества Ø . Тогда

Замечание: если множества А и В пересекаются, то