Дискретная математика

Рекомендуемая литература

Баврин И.И. Дискретная математика: учебник и задачник для прикладного бакалавриата.-

Введение

МАТЕМАТИКА

Непрерывная математика
Теория пределов и непрерывности

Дискретная математика
Прерывная.
Основа информатики

Являются основами для создания систем

Аналоговые

Разделы дискретной математики

Теория множеств.
Комбинаторика
Теория графов.
Алгебра логики.
Матрицы.
Разностные уравнения.
Дискретная вероятность.

Задачи курса

УМЕТЬ
Правильно употреблять математическую символику и оперировать математическим инструментарием.
Классифицировать задачу. Выбирать

Раздел 1. Элементы теории 1.1 Множества и операции над ними

Множество –

Примеры

Учебник –страницы.
Группа ВТ-115 – ФИО студентов.
Серия микросхем – состав серии.

Обозначения числовых множеств

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

Названия и обозначения числовых множеств

Множество действительных чисел удовлетворяющих условию:

Обозначение в теории

Названия и обозначения числовых множеств

Множество действительных чисел удовлетворяющих условию:

Альтернативное обозначение

Названия и обозначения числовых множеств

Множество действительных чисел удовлетворяющих условию:

Альтернативное обозначение

Названия и обозначения числовых множеств

Множество действительных чисел удовлетворяющих условию:

Альтернативное обозначение

Названия и обозначения числовых множеств

Множество всех действительных чисел обозначается:

ИЛИ

ИЛИ

R

Множество всех положительных

Множества конечные и бесконечные

Множество содержащее конечное число элементов называют конечным, в

Формы задания множества 1 способ

Например: А = {1,2,3} – означает, что множество

Формы задания множества 2 способ

Заключается в описании элементов определяющим свойством P (x),

C = {x: x – пациент больницы №4 г.Владимир}
D = {x:

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

Равенство множеств

Если множество А и множество В состоит из одних и

Подмножество множества

Если имеется два множества А и В и известно, что

Пример 1: Множество четных чисел, есть подмножество множества целых чисел.
Пример 2:

ТЕОРЕМА 1

Если

а

то

А=В

1.Любой элемент из множества В является
элементом множества А.

2.Любой

Определение - булеан

Элементами множества могут быть подмножества.
Множество всех подмножеств множества А

Универсальное множество

D

H

A

C

B

S

U

Множество U – универсальное множество, которое задает область
исследования

Пустое множество

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

ТЕОРЕМА 2

Пустое множество является подмножеством любого множества.

ДОКАЗАТЕЛЬСТВО

Из определения подмножества следует, что

Операции над множествами Объединение или сумма

ОПРЕДЕЛЕНИЕ: если даны два множества А и

Пример операции объединения

ПРИМЕР 1: {1,2,3} {2,3,4}= {1,2,3,4}

ПРИМЕР 2: А – множество

Следствие операции объединения

Объединение N множеств

Операция объединения может быть распространена на N множеств. Тогда

Задача

Операция пересечения или умножения

ОПРЕДЕЛЕНИЕ: если даны два множества А и В,

Пример операции пересечения

ПРИМЕР: {1,2,3} {2,3,4} ={2, 3}

А

В

С

СЛЕДСТВИЯ операции пересечения

Для некоторой пары множеств может оказаться, что их пересечение
равно

Непересекающиеся множества

Множества, пересечение которых, является пустым множеством называются непересекающимися.
ПРИМЕР 1: А

Пересечение N множеств

Операция пересечения может быть распространена на N множеств. Тогда

Вычитание множеств

ОПРЕДЕЛЕНИЕ: Разностью множеств А и В называется совокупность тех элементов

Варианты вычитания множеств

А

В

А

В

А

В

1

2

3

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

ОПРЕДЕЛЕНИЕ: Симметричной разностью множеств А и В

Дополнение

Дополнением множества А до универсального множества U, является частный случай разности:

A

Диаграммы Эйлера-Венна

Применяются для наглядного изображения соотношений между подмножествами какого либо универсального

Декартово произведение множества А на множество В

ОПРЕДЕЛЕНИЕ: это множество всех

Декартова степень

ЗАДАЧА; дано множество X={0,1,2} вычислить

Порядок выполнения операций над множествами

Дополнение – (пересечение- объединение) и разность -

Мощность множества

Это характеристика количества элементов множества. Используется как класс эквивалентности над

Законы алгебры множеств или алгебра Буля

1. ЗАКОН. Свойство двойного дополнения.

Двойное дополнение

Законы алгебры множеств или алгебра Буля

2 ЗАКОН. Свойство идемпотентности объединения или

Законы алгебры множеств или алгебра Буля

3 ЗАКОН. Дополнения.

Законы алгебры множеств или алгебра Буля

4. ЗАКОН. Свойство единицы.

Законы алгебры множеств или алгебра Буля

5 ЗАКОН. Свойство нуля.

Законы алгебры множеств или алгебра Буля

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

Законы алгебры множеств или алгебра Буля

7 ЗАКОН. Коммутативность пересечения или объединения

Законы алгебры множеств или алгебра Буля

8 ЗАКОН. Ассоциативности пересечения или объединения.

Законы алгебры множеств или алгебра Буля

9 ЗАКОН. Дистрибутивность объединения относительно пересечения

Проверка закона де Моргана

Пусть