Конспект лекций по дискретной математике. Учебное издание

СОДЕРЖАНИЕ: Предисловие (6). Часть 1. Элементы математической логики (7). 1. Составные высказывания (7). 2. Простейшие связки (8). 3. Другие связки (10). 4. Логические отношения (11). 5. Варианты импликации (12). 6. Основные законы, определяющие свойства введенных логических операций (13). - Первое практическое занятие по теме «Логические операции» (15). 7. Булевы функции (21). 8. Свойства элементарных булевых функций (23). 9. Дизъюнктивные и конъюнктивные нормальные формы алгебры высказываний (24). 10. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы (25). 11. Многочлены Жегалкина (27). - Второе практическое занятие по теме «Булевы функции. Многочлены Жегалкина» (29). - Контрольные вопросы (38). Часть 2. Множества и отображения (39). 1. Понятие множества (39). 2. Способы задания множеств (39). 3. Подмножества (40). 4. Операции над множествами (40). 5. Соотношение между множествами и составными высказываниями (42). 6. Соотношения между высказываниями и соответствующими им множествами истинности (43). 7. Выводы (45). 8. Абстрактные законы операций над множествами (45). - Третье практическое занятие по теме «Операции над множествами» (46). 9. Кортежи и декартово произведение множеств (50). 10. Бинарные отношения (51). 11. Отображение множеств (52). 12. Функции (53). - Четвертое практическое занятие по теме «Отношения. Отображения. Функции» (54). - Контрольные вопросы (59). Часть 3. Элементы комбинаторного анализа (60). 1. Основные правила комбинаторики (60). 2. Перечислительная комбинаторика или теория перечислений (61). 3. Комбинации элементов с повторениями (63). 4. Бином Ньютона (64). - Пятое практическое занятие по теме «Комбинаторные формулы. Бином Ньютона» (64). - Контрольные вопросы (67). Часть 4. Логика предикатов или логика первого порядка (68). 1. Предикаты (68). 2. Применение предикатов в алгебре (70). 3. Булева алгебра предикатов (71). 4. Кванторы (71). 5. Формулы логики предикатов (72). 6. Равносильные формулы логики предикатов (73). 7. Приведенные и нормальные формы в логике предикатов (74). 8. Исчисление предикатов (76). - Шестое практическое занятие по теме «Предикаты» (77). - Контрольные вопросы (80). Часть 5. Элементы теории графов (81). 1. Некоторые основные понятия (81). 2. Степень вершины (82). 3. Маршруты, цепи, циклы (82). 4. Связность графа (83). 5. Ориентированные графы (83). 6. Изоморфизм графов (84). 7. Плоские графы (85). 8. Операции над графами (85). 9. Способы задания графов (86). 10. Некоторые типы графов (88). - Седьмое практическое занятие по теме «Графы» (90). - Контрольные вопросы (99). Часть 6. Элементы теории кодирования (100). 1. Кодирование как способ представления информации (100). 2. Кодирование и декодирование (101). 3. Помехоустойчивое кодирование (101). 4. Канал связи (101). 5. Криптология (102). 6. Алфавитное кодирование (102). 7. Математическое изучение алфавитного кодирования (103). 8. Проблема взаимной однозначности (104). 9. Достаточный признак взаимной однозначности алфавитного кодирования (104). 10. Общий критерий взаимной однозначности (106). - Восьмое практическое занятие по теме «Алфавитное кодирование» (107). 11. Двоичный алфавит (113). 12. Самокорректирующиеся коды (114). 13. Коды Хемминга (114). 14. Алгоритм построения кода Хемминга (115). 15. Обнаружение ошибки в кодах Хемминга (116). 16. Декодирование (получение исходного сообщения) (118). - Девятое практическое занятие по теме «Коды Хемминга» (118). - Контрольные вопросы (120). Часть 7. Элементы теории автоматов (121). 1. Понятие конечного автомата (121). 2. Определение конечного автомата (121). 3. Способы задания конечного автомата (122). 4. Примеры конечных автоматов (124). 5. Канонические уравнения автомата (131). - Десятое практическое занятие по теме «Конечные автоматы» (133). - Контрольные вопросы (135). Часть 8. Элементы теории алгоритмов (136). I. Вычислимые функции и алгоритмы (136). II. Теория рекурсивных функций (141). - Одиннадцатое практическое занятие по теме «Рекурсивные функции» (145). III. Нормальный алгоритм Маркова (149). - Двенадцатое практическое занятие по теме «Нормальные алгоритмы» (155). IV. Машины Тьюринга (156). - Тринадцатое практическое занятие по теме «Машина Тьюринга» (160). - Контрольные вопросы (162). Часть 9. Задачи для контрольных и самостоятельных работ (163). Рекомендуемая литература (174). Аннотация издательства: В книге в доступной форме изложены разделы, традиционно изучаемые в курсе дискретной математики. Книга рассчитана на студентов нематематических вузов, желающих ознакомиться с методами дискретной математики. Математическая подготовка, необходимая для чтения этой книги, ограничивается программой математики средней школы. Содержание разделов книги взаимно связано друг с другом и включает: элементы математической логики, теории множеств, предикатов, графов, элементы комбинаторики, кодирования и теории конечных автоматов, а также введение в теории алгоритмов. Все разделы снабжены большим количеством примеров и решенных задач, помогающих усвоить и закрепить изучаемый материал. Книга может быть также полезна преподавателям, которые начинают читать курс дискретной математики.