В статье обсуждается методика использования пакета математических символьных вычислений Maple при изучении вузовского курса «Математическая логика и теория алгоритмов». Рассматриваются особенности синтаксиса подпакета with(Logic). Показана методика компьютерного нахождения конъюнктивной, дизъюнктивной и полиномиальной форм булевой функции. Отмечено, что при машинном нахождении полиномиальной нормальной формы для функции необходимо использовать, кроме команд логического подпакета, команды для работы с многочленами. На конкретном примере детально разобран алгоритм проверки функциональной полноты системы булевых функций.
В пособии излагаются основные вопросы теории булевых функций, прежде всего связанные с доказательством фундаментальной теоремы Э. Поста о функциональной полноте. Рассмотрен вопрос о применении булевых функций для проектирования схем из функциональных элементов и анализу их сложности. Особое внимание уделено доказательству NP-полноты и coNP-полноты ряда проблем распознавания для булевых функций. Рассмотрены некоторые вопросы, связанные с построением схем из функциональных элементов. В пособие включен основной материал по теории k-значных функций (функций k-значной логики), включая теорему А. В. Кузнецова о функциональной полноте. Пособие предназначено для студентов, обучающихся по специальности “Компьютерная безопасность’’ и по направлению “Информационная безопасность’’. Оно может быть использовано при изучении дисциплин “Дискретная математика’’, “Математическая логика и теория алгоритмов’’, “Теория алгоритмов’’, “Сложность вычислений’’, “Криптографические методы защиты информации’’, “Модели безопасности компьютерных систем’’ и “Криптографические протоколы’’, а также специальных дисциплин.
В пособии излагаются основные вопросы теории булевых функций, прежде всего связанные с доказательством фундаментальной теоремы Э. Поста о функциональной полноте. Рассмотрен вопрос о применении булевых функций для проектирования схем из функциональных элементов и анализу их сложности. Особое внимание уделено доказательству NP-полноты и coNP-полноты ряда проблем распознавания для булевых функций. Рассмотрены некоторые вопросы, связанные с построением схем из функциональных элементов. В пособие включен основной материал по теории k-значных функций (функций k-значной логики), включая теорему А. В. Кузнецова о функциональной полноте. Пособие предназначено для студентов, обучающихся по специальности “Компьютерная безопасность’’ и по направлению “Информационная безопасность’’. Оно может быть использовано при изучении дисциплин “Дискретная математика’’, “Математическая логика и теория алгоритмов’’, “Теория алгоритмов’’, “Сложность вычислений’’, “Криптографические методы защиты информации’’, “Модели безопасности компьютерных систем’’ и “Криптографические протоколы’’, а также специальных дисциплин.