Белоусов И.Н., Белоусова В.И. Дискретная математика и математическая логика

Учебник. — Екатеринбург: Уральский университет, 2024. — 178 с. — ISBN 978-5-7996-3858-0.В учебнике рассмотрены следующие темы: бинарные отношения, бинарные операции, алгебраические структуры, конечные поля, алгебраические коды, теория графов, логика высказываний. Для успешного освоения представленных материалов в учебник включены также базовые общеалгебраические сведения. В конце каждой главы приведены упражнения для проверки полученных знаний.Издание предназначено для студентов направлений 09.03.01 «Информатика и вычислительная техника», 09.03.03 «Прикладная информатика», 09.03.04 «Программная инженерия» и может быть полезно студентам всех направлений бакалавриата и специалитета ИРИТ — RTF УрФУ.ПредисловиеБинарные отношения
Множества. Операции над множествами.
Определение и способы задания бинарного отношения.
Операции над бинарными отношениями.
Основные свойства бинарных отношений.
Классы эквивалентности.
Частичный порядок.
Полурешетки и решетки.
Рефлексивное, симметричное и транзитивное замыкание бинарного отношения.
Бинарные отношения из множества в множество.
Упражнения для самостоятельной работы.Элементы общей алгебры
Группоиды и полугруппы.
Алгоритм Лайта.
Группы.
Подгруппы. Смежные классы.
Циклические группы.
Группы подстановок.
Матричные группы.
Нормальные подгруппы. Фактор-группы.
Изоморфизмы и гомоморфизмы.
Кольца и поля.
Линейное пространство над произвольным полем F.
Идеалы и гомоморфизмы ассоциативных колец.
Упражнения для самостоятельной работы.Теория чисел
Элементарная теория чисел.
Взаимно простые числа.
Теория сравнений.
Китайская теорема об остатках.
Теория сравнений в криптографии.
Упражнения для самостоятельной работы.Многочлены над конечными полями
Обзор общей теории многочленов.
Теория сравнений для многочленов и примеры построения полей небольшого составного порядка.
Основные теоремы о многочленах над конечными полями.
Упражнения для самостоятельной работы.Коды, исправляющие ошибки
Блоковые коды.
Примеры блоковых кодов.
Линейные коды. Порождающая матрица линейного кода.
Проверочная матрица линейного кода.
Дуальные коды.
Минимальное расстояние линейного кода.
Декодирование линейных кодов с помощью смежных классов.
Декодирование с помощью синдромов.
Код Хэмминга и расширенный код Хэмминга.
Циклические коды.
Нахождение систематической порождающей матрицы циклического кода.
Специальный вид проверочной матрицы циклического кода.
Коды, порожденные элементами из расширения основного поля.
Коды БЧХ.
Примеры кодов БЧХ.
Декодирование кодов БЧХ.
Упражнения для самостоятельной работы.Элементы теории графов
Основные понятия теории графов.
Алгоритмы на графах.
Упражнения для самостоятельной работы.Элементы математической логики
Высказывания и операции над ними.
Формулы логики высказываний.
Классификация формул. Равносильные формулы.
Нормальные формы.
Упражнения для самостоятельной работы.Ответы к упражнениям для самостоятельной работы
Библиографический список