Элементы комбинаторики

Цель:приобретение базовых знаний в области фундаментальных разделов математики. Повторить и систематизировать знания по данной теме.

Задачи:

• развитие творческого профессионального мышления;

• познавательная мотивация;

• овладение языком науки, навыки оперирования понятиями;

• овладение умениями и навыками постановки и решения задач;

• углубление теоретической и практической подготовки;

• развитие инициативы и самостоятельности студентов.

Теоретические сведения:

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

1. Логические символы

Квантор  - заменяет выражение "для любого", "для произвольного", "для какого бы ни было".

Квантор - заменяет выражение "существует", "найдется".

Запись  (импликация) означает, что из справедливости высказывания A вытекает справедливость высказывания B. Если, кроме того, из справедливости высказывания B вытекает справедливость A, то записываем . Если  , то высказывание B является необходимым и достаточным условием для того, чтобы выполнялось высказывание A.

Если предложения A и B справедливы одновременно, то записываем  . Если же справедливо хотя бы одно из предложений A или B, то записываем  .

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

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

Множество обозначают символом A = {x}, где x - общее наименование элементов множества A. Часто множество записывают в виде A = {a, b, c, ...}, где в фигурных скобках указаны элементы множества A. Будем пользоваться обозначениями:

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

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

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

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

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

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

Запись   означает, что элемент a принадлежит множеству A.

Запись   означает, что элемент a не принадлежит множеству A. Множество B, все элементы которого принадлежат множеству A, называется подмножеством множества A, и при этом записывают

(см. рис. 1).

Всегда , так как каждый элемент множества, естественно, принадлежит A. Пустое множество, т. е. множество, не содержащее ни одного элемента, обозначим символом  . Любое множество содержит пустое множество в качестве своего подмножества.

Если  , то A и B называются равными множествами, при этом записывают A = B.

Если  , то множество ℐ элементов множества А , не принадлежащих A, называется дополнением множества A к множеству (см. рис. 2).

Дополнение множества A к множеству ℐ обозначают символом ; или просто CA, если известно, к какому множеству берется дополнение. Таким образом,С А=

Если А⊂ℐ , то иногда дополнение множества B к множеству A называют разностью множеств A и B и обозначают A\B (см. рис. 3), т. е.

Пусть A и B - подмножества множества ℐ.

Объединением множеств A и B называется множество А⋂В(см. рис. 4)

Аналогично, если  подмножества множества ℐ, то их объединением будет множество

Пересечением подмножеств A и B называется множество (см. рис. 5)

Рисунки 1-6 называются диаграммы Эйлера-Венна.

Аналогично, символом  обозначают пересечение подмножеств     множества ℐ,т.е.

Два элемента a и b называются упорядоченной парой, если указано, какой из этих элементов первый, какой второй, при этом

Упорядоченную пару элементов a и b обозначают символом (a, b).

Аналогично определяется упорядоченная система из n элементов a₁, a₂, ..., a_n, которую обозначают символом (a₁, a₂, ..., a_n). Элементы a₁, a₂, ..., a_n называются координатами упорядоченной системы (a₁, a₂, ..., a_n).

Совокупность всевозможных упорядоченных пар (a, b), где, называется произведением множеств A и B и обозначается символом .

Аналогично, символом обозначают произведение множеств , т. е. совокупность всевозможных упорядоченных систем (a₁, a₂, ..., a_n),

где .