Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

Математика->Курсовая работа
В системах управления технологическими процессами существуют проблемы, связанные с решением задач оценки эффективности управления такими системами с у...полностью>>
Математика->Реферат
Соединение вала машины с валом электродвигателя напрямую возможно лишь в относительно редких случаях, когда частоты вращения этих валов совпадают, нап...полностью>>
Математика->Реферат
Под противопожарным понимается такое водоснабжение, которое кроме удовлетворения хозяйственно-питьевых и производственных нужд полностью обеспечивает ...полностью>>
Математика->Контрольная работа
При имеем механизм: изменяемую систему, при – статически определимую систему, при - статически неопределимую систему. n = 3D – Ш – С0 D=75 Ш=3 C0=3 n ...полностью>>

Главная > Учебное пособие >Математика

Сохрани ссылку в одной из сетей:

\bookfoldsheets0Федеральное агентство по образованию РФ

«ДИСКРЕТНАЯ МАТЕМАТИКА»

(КОНСПЕКТ ЛЕКЦИЙ)

Преподаватель: профессор,
Архипов Игорь Константинович
  1. МНОЖЕСТВА

Множество – совокупность элементов, обладающих каким-то одним общим свойством. (Это определение не является строгим, оно лишь показывает особенности построения множеств, т.е. для построения множества важно указать свойство, которым обладают все его элементы).

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

Если такого номера для каждого элемента не существует, то такое множество называется бесконечным.

Бесконечное множество часто называют континуумом (например: совокупность точек на плоскости).

Если можно пересчитать все число элементов в счетном множестве, то эта сумма называется мощностью множества.

Множества задаются различными способами:

  1. С помощью перечисления всех его элементов.

{0,1,2,3,4,5,6,7,8,9}

  1. Алгоритмическая форма (в виде последовательности или фомул).

а) конечное

М={2;4;6;8} <=> М={m|2n;n-целое;1<=n<=4}

б) бесконечное

А={х| |х-1|<3}

  1. СВОЙСТВА СЧЕТНЫХ МНОЖЕСТВ

  1. Всякое подмножество счетного множества конечно или счетно

Подмножеством множества А называется множество А` все элементы которого принадлежат множеству А

Пример:

  1. Сумма конечного или счетного числа конечных или счетных множеств есть конечное или счетное множество.

  2. Множество всех рациональных чисел счетно.

  3. Алфавитом называется любое непустое множество.

Пустое множество – множество, которое не содержит ни одного элемента.

Элементы множества под названием АЛФАВИТ называют буквами (символами).

Символом в данном алфавите любая конечная последова­тель­ность букв.

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

Такое подмножество называют семейством множеств А или булеаном. (обозначается В(А))

Будем называть вектором (кортежем) упорядоченный набор элементов и обозначать его , заметим, что в отличие от множества, элементы в векторе могут повторяться. Эти элементы называются координатами или проекциями.

Количество элементов в векторе называется его длиной, если в векторе 2 элемента, то двойка, если n элементов, то n-ка.

Теория множеств строится на основе систем аксиом.

  1. Аксиома существования: Существует по крайней мере одно множество.

  2. Аксиома объемности: Если множества А и В составлены из одних и тех же элементов, то они совпадают.

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

  4. Аксиома разности: Для произвольных множеств А и В существует множество, элементами которого являются те и только те элементы множества А, которые не содержатся в множестве В.

  5. Аксиома существования пустого множества: Существует множество не содержащее ни одного элемента.

  1. ОСНОВНЫЕ ОПЕРАЦИИ НАД МНОЖЕСТВАМИ

  1. Включение (объединение)

Множество А входит (включено) в множество В, или А является подмножеством В.

Если всякий объект, обладающий свойством , также обладает свойством , то говорят, что свойство включает свойство , т.е.

  1. Сумма

Сумма множеств А и В есть множество С, включающее в себя все элементы множество А и В.

Объект входит во множество если он входит во множество А или во множество В.

  1. Пересечение (произведение)

Пересечением множество А и В называется новое множество С. Элементы множества С принадлежат множеству А (обладают его свойствами) и множеству В (обладают его свойствами).

  1. Вычитание (разность)

Разность множеств А и В есть множество С, элементы которого обладают свойствами множества А и не обладают свойствами множества В или принадлежат множеству А и не принадлежат множеству В.

  1. Дополнение

Если имеется некоторое универсальное множество (универсум) U и все рассматриваемые множества есть его подмножества, то дополнением называется такое множество, элементы которого не входят в А, но принадлежат U.

ГРАФИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ

(Диаграммы Эймера, Венна)

1.

2.

3

В

А

.

4

U

.

4. ПРЯМОЕ ПРОИЗВЕДЕНИЕ А х В

Прямым произведением множеств А и В называется множество М всех пар (), таких, что

Если А=В, то такое произведение называется

Аналогично можно вывести операцию прямого произведения большего числа множеств.

Если в частности одинаковы то получаем

(Например, множество точек на плоскости являются прямым произведением двух множеств).

Если множества конечные, мощность произведений равна мощности произведений

5. ОСНОВНЫЕ ТОЖДЕСТВА АЛГЕБРЫ МНОЖЕСТВ

Независимость расположения:

(1)

(2)

Ассоциативность:

(3)

(4)

Дистрибутивность:

(7)

(8)

(9)

(10)

(11)

(12)

ЗАКОНЫ де Моргана

  1. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ И ИХ ПРИМЕНЕНИЕ В ТЕОРИИ МНОЖЕСТВ

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

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

  2. Если необходимо выделить все элементы множества, об­ладающие заданными свойствами, то это задача перечисления.

Рассмотрим следующие элементы комбинаторики, позволяющие решать вышеупомянутые задачи. К таким объектам относятся:

    • перестановки (с повторением и без них);

    • размещения (с повторением и без них);

    • сочетания (с повторением и без них);

Перестановками называют комбинации, состоящие из одних и тех же элементов и отличающиеся только порядком их расположения. Число всех возможных перестановок обозначается (без повторений).

Перестановки с повторениями вычисляются по формуле:

, где - число повторений элементов каждого вида.

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

(без повторения)

(с повторением)

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

(без повторения)

(с повторением)



Загрузить файл

Похожие страницы:

  1. Дискретная математика (5)

    Реферат >> Математика
    ... чисел) является дискретной. Дискретная математика – область математики, занимающаяся изучением свойств дискретных структур, ... в вычислительной технике и программировании). Традиционно к дискретной математике относят такие области математического значения ...
  2. Дискретная математика. Теория вероятностей и математическая статистика

    Книга >> Математика
    ... упражнения по двум разделам дисциплины: дискретная математика, теория вероятностей и математическая статистика ... «Психология» Социально – психологического факультета. СОДЕРЖАНИЕ ДИСКРЕТНАЯ МАТЕМАТИКА 3.1. Элементы теории множеств ………..……….………………………....... 4 ...
  3. Дискретная математика. Курс лекций

    Конспект >> Математика
    Теория множеств § 1.1. Множество Любое понятие дискретной математики можно определить с помощью понятия множества. ... натуральных чисел …,-2,-1,0,1,2,…n, то говорят о функции с дискретным временем. х(t) -1 0 1 2 3 n t Если вместо множества Х ввести ...
  4. Избранные главы дискретной математики

    Реферат >> Математика
    ... , узелки «на память» и др.); 2 — двоичная (в дискретной математике, информатике, программировании); 3 — троичная; 4 — четверичная; 8 — восьмеричная ... . §6 Теория графов Теория графов — раздел дискретной математики, изучающий свойства графов. Первая работа ...
  5. Основные положения дискретной математики

    Лекция >> Математика
    ... понятия. ЛИТЕРАТУРА Кузнкцов О.П., Адельсон – Вельский Г.М. Дискретная математика для инженера – 2-е иэдание переработанное и доплненное ... управления» Контрольная работа по дисциплине «Дискретная математика» специальность 071900 «Информационные системы» ...

Хочу больше похожих работ...

Generated in 0.0015838146209717