Математическая логика и теория алгоритмов

Математическая логика и алгоритмы в инженерном деле. Предмет математической логики.

Логические функции. Однородные функции. Табличное задание функций. Двузначные однородные функции. Булевы функции. Табличное задание булевых функций. Булевы функции одной переменной. Булевы функции двух переменных. Элементарные булевы функции и их свойства. Булева алгебра. Свойство функций дизъюнкции, конъюнкции и инверсии. Тождественные преобразования. Геометрическое задание булевых функций. Булев куб. Носитель булевой функции и его свойства. Специальные булевы функции. Элементарная конъюнкция. Дизъюнктивно-нормальная форма (ДНФ). Элементарная дизъюнкция. Конъюнктивно-нормальная форма (КНФ). Первая теорема Гилберта — Акермана. Двойственные булевы функции. Вторая теорема Гилберта — Акермана. Релейно — контактные схемы. Полиномиальная нормальная форма. Полиномы Жегалкина. Теорема Жегалкина. Линейные функции.

Разложение Шеннона. Монотонно возрастающие булевы функции. Классы Поста. Критерий Поста.

Минимизация булевых функций в классе ДНФ. Импликанты булевых функций и их свойства. Сокращенные и минимальные ДНФ и их свойства. Первый этап минимизации. Алгоритм Блейка. Алгоритм Квайна — Мак-Класки. Алгоритм Нельсона. Второй этап минимизации. Критерий Журавлева. Имппликантные таблицы. Карты Карно. Минимизация в классе КНФ.

Понятие алгоритма. Численные алгоритмы. Логические алгоритмы. Свойства алгоритмов. Ассоциативное исчисление. Эквивалентность слов. Нормальный алгоритм Маркова. Машина Поста. Машина Тьюринга. Алгоритмическая разрешимость. Прикладная теория алгоритмов.

Комментирование запрещено