Краткие ответы на экзаменационные вопросы по дисциплине "Дискретная математика" (Предмет дискретной математики. Метод Блейка-Порецкого)

1.  Предмет ДМ

В курсе изучаются фундаментальные понятия, лежащие в основе математической кибернетики и таких разделов математики как алгебра, теория графов, математическая логика. Хотя данные разделы и являются отдельными математическими теориями, они не только используют методы друг друга, но и тесно связаны между собой. Все их можно объединить условным названием ``дискретная математика''. Этот термин характеризует конструктивный характер теории, алгоритмические, комбинаторные методы. Задачи дискретной математики, как правило, тесно связаны с компьютерными проблемами, естественно выражаются в виде различных алгоритмов.

Историческая справка

Дискретная математика, по-существу, стала активно развиваться с начала XX века, когда стали изучаться возможности формализации математики и были получены фундаментальные результаты в области математической логики. Это результаты Поста, Клини и, особенно, Гёделя. Теорема неполноты Гёделя имеет мировоззренческое значение – она показывает ограниченность формальных методов построения математической теории.

Тесно связаны с математической логикой исследования в области теории алгоритмов Тьюринга, Поста, Чёрча (также в начале XX века).

Информатизация и компьютеризация общества во второй половине XX века в значительной степени стимулировала развитие дискретной математики.

2. Основные задачи (ДМ).

Непрерывная мат-ка развивалась в сот-и с запросами естествознания. Развитие ДМ обусловлено изучением законов и правил человеческого мышления. Она применяется в тех областях техники, к-е связаны с моделированием мышления (ВТ, прогр-е).

Мышление реализует себя прежде всего в языке. Ядром ДМ явл-ся теория языков (формальных).  Слово «формальные» подчеркивает, что в этой теории изучаются искуственные языки, спец-но созданные для каких-либо целей: 1. языки программир-я, 2. языки математики и т.д. Теория ФЯ явл-ся базой теории кодирования, криптологии, изучающие методы защиты инфор-и, теории алгоритмов и мат-й логики.

В прикладном аспекте эта теория (ФЯ) служит основой разработки математического обеспечения ВТ.

3. Основные обозначения ТМ.

a Î A; a Ï A

{ a, b, c} – множество, сост-е из элв…

A={ x: x… } – Мн-во А, сост-е из эл-в х, обладающих св-м..

Æ - пустое мн-во

U – универсальное мн-во

АÌ В - мн-во А явл-ся подмножеством мн-ва В

AÈB – объединение мн-в А и В

AÇB – пересечение мн-в А и В

 - дополнение множ-ва А до  U

А\В – разность мн-в А и В

 - объед-е мн-в А (от I до k)

v – дизъюнкция; ^ - конъюнкция

=> импликация

<=> эквиваленция

¬A,  - отрицание высказывания А

 - квантер всеобщности

 - квантер сущ-я

A - число размещений из m эл-в по k (без повторений)

C - число сочетаний из n эл-в по m

P - число перестановок из n эл-в

D(f) - Область опр-я отображения f

D(p) - обл. опр-я соот-я p

sup B(int B) - точка верхнее (нижнее) грань множ-ва В

|A| - мощ-сть множ-ва А

A~B - множ-во А эквивалентно множ-ву В

N - мощ-сть счетного множ-ва

4. Основные понятия ТМ. Объединение.

«Множество» - неопределяемое базовое понятие.

Кантор: «Под множеством я понимаю вообще все многое, к-е возможно мыслить как единое, т.е. такую совокупность определенных элементов, которые посредством одного закона м.б. соединена в одно целое.»

Способы задания множеств:

1. перечисление эл-в: { a₁, …,a_k } k элементное множество

2. указание св-ва, к-м должны обладать все эл-ты множ-ва: A={ x: x… }

Множества называются равными, если любой эл-т одного мн-ва явл-ся эл-м другого и наоборот объединение AÈB={ x: xÎA или xÎB}

Универсальным множеством наз-ся мн-во, содержащее все эл-ты, находящиеся в рассмотрении.

5. Основные понятия ТМ. Пересечение

«Множество» - неопределяемое базовое понятие.

Кантор: «Под множеством я понимаю вообще все многое, к-е возможно мыслить как единое, т.е. такую совокупность определенных элементов, которые посредством одного закона м.б. соединена в одно целое.»

Способы задания множеств:

1. перечисление эл-в: { a₁, …,a_k } k элементное множество

2. указание св-ва, к-м должны обладать все эл-ты множ-ва: A={ x: x… }

Множества называются равными, если любой эл-т одного мн-ва явл-ся эл-м другого и наоборот пересечение  AÇB={ x: xÎA и xÎB}

Универсальным множеством наз-ся мн-во, содержащее все эл-ты, находящиеся в рассмотрении.

6. Основные понятия ТМ. Разность

«Множество» - неопределяемое базовое понятие.

Кантор: «Под множеством я понимаю вообще все многое, к-е возможно мыслить как единое, т.е. такую совокупность определенных элементов, которые посредством одного закона м.б. соединена в одно целое.»

Способы задания множеств:

1. перечисление эл-в: { a₁, …,a_k } k элементное множество