Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Скачиваний:
126
Добавлен:
20.04.2015
Размер:
2.35 Mб
Скачать

66

Целью данного учебно-методического пособия является развитие навыков самостоятельной работы студентов.

По курсу “Дискретная математика” учебной программой предусмотрено 46 часов самостоятельного обучения. Автор включил в учебно-методическое пособие перечисленные ниже вопросы в связи с тем, что они тесно связаны с вопросами курса, предусмотренными Государственным стандартом.

На основании понятия взаимно однозначного соответствия проводится доказательство многих теорем первой части курса – “Математическая логика”. Понятие отношения тесно связано с понятиями графов и предикатов. Знание об изоморфизмах алгебр помогут студенту перенести выводы о доказанных свойствах некоторых алгебраических структур на более сложные объекты.

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

Вопросы для самостоятельного изучения (по курсу «Дискретная математика», первый семестр)

1. Множества: определения, примеры.

2. Способы задания множеств: порождающая процедура, разрешающая процедура.

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

4. Векторы и прямые произведения, определения, примеры.

5. Теорема о мощности прямого произведения множеств.

6. Проекции векторов и векторных множеств на оси.

7. Элементы комбинаторики: правило произведения, размещения без повторений, размещения с повторениями.

8. Элементы комбинаторики: перестановки без повторений, перестановки с повторениями.

9. Элементы комбинаторики: сочетания без повторений, правило суммы.

10. Соответствия: определения, свойства.

11. Взаимно однозначные соответствия и мощность множеств: утверждение о взаимно однозначном соответствии равномощных множеств, теорема о числе подмножеств конечного множества.

12. Взаимно однозначные соответствия и мощность множеств: семь утверждений о счетных множествах.

13. Взаимно однозначные соответствия и мощность множеств: теорема Кантора, теорема о числе подмножеств счетного множества.

14. Бинарные отношения и их свойства.

15. Отношения эквивалентности, отношения порядка. Лексико-графический порядок.

16. Понятие операции. Основные свойства бинарных операций.

17. Алгебры: определения и примеры.

18. Гомоморфизм и изоморфизм алгебр.

19. Булева алгебра и теория множеств: теорема 1 об изоморфизме булевых алгебр.

20. Булева алгебра и теория множеств: теорема 2 об изоморфизме булевых алгебр.

1. Множества и операции над ними

1.1. Множества. Определения, примеры. Способы задания множеств

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

Множество, которое подчиняется лишь такому ограничению, может содержать объекты почти любой природы.

Например:

- множество всех станций Московского метро;

- множество левых ботинок;

- множество натуральных чисел: 1, 2, 3, 4 и т. д.;

- множество символов, доступных специальному печатающему устройству;

- множество кодов операций конкретного компьютера.

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

Множества обычно обозначают прописными буквами, например, А. Если число принадлежит множеству, то будем говорить, что “оно является элементом множества”. Например, если а является элементом множества А, то это утверждение может быть записано следующим образом:

”.

Утверждение “b не является элементом А” будем обозначать

”.

Символ происходит от греческой буквы.

Пример:

- множество всех натуральных чисел: 1, 2, 3, . . . Обозначим N. Часто 0 считают натуральным числом. Множество N с добавлением 0 обозначается .

- множество всех натуральных чисел, не превосходящих 100.

- множество всех решений уравнения (элементы множества- числа, являющиеся решением).

- множество всех чисел вида , где.

Определение: Множество А называется подмножеством множества В (обозначается ), если всякий элемент А является элементом В.

Говорят: В содержит А или покрывает А.

Определение1: Множества А и В равны, если их элементы совпадают или если это два множества, имеющие одинаковые элементы.

Определение2: Множества А и В равны, если и. Определение 2 указывает на наиболее типичный метод доказательства (сначала доказывается, затем обратное.

Пример:

Тригонометрическая теорема: :

а) всякое решение уравнения имеет вид;

б) всякое число вида является решением уравнения sin x = 1.

Определение: Если и, то А называетсястрогим подмножеством множества В (обозначается ,- строгое включение).

Соседние файлы в папке Методичка