ПО ДИСЦИПЛИНЕ Математическая логика и теория алгоритмов Самара-2011 2 УДК 621.391 Блатов И.А., Сергиевская И.М. <...> Учебное пособие включает программу экзамена по математической логике и теории алгоритмов, вопросы для самопроверки разной степени сложности по разделам математической логики и теории алгоритмов и ответы к ним, рекомендации к выполнению контрольной работы. <...> 7 Рекомендации к выполнению контрольной работы……………32 Ответы на вопросы для самопроверки…………………………. <...> Тестовые задания затрагивают такие разделы курса как исчисление высказываний и исчисление предикатов, методы доказательств, машины Тьюринга, рекурсивные функции. <...> Теорема о связи отношений логического следствия и логической эквивалентности. <...> Примеры теорий первого порядка с собственными аксиомами. <...> При фиксированном интерпретацией называется функция I :… <...> К символам алфавита в исчислении высказываний не относятся … (выберите не менее двух символов) 8 A. <...> 2) По теореме, обратной теореме дедукции, ├ A B C 2. <...> 66. n -местным предикатом на множестве X называется n -местная функция :f 67. x A i 68. <...> Пусть A x x ,., xn) – n -местный предикат, ix – переменная в предикате. <...> Пусть A x x ,., xn) – n -местный предикат, ix – переменная в предикате. <...> Предикатная формула находится в приведенной форме, если в ней… <...> Предикатная формула находится в предваренной нормальной форме, если она имеет вид… <...> Укажите не менее двух формул, при приведении которых к предваренной нормальной форме нужно вводить новые переменные… <...> 1) 1) Предикатная буква ( )n Ak . функция 2) Функциональная буква fk . <...> 2) ( )n 3) Предметная константа ia . n -местная на множестве X . предикат множестве X . <...> Формула теории первого порядка называется логически общезначимой, если она… <...> Чистое исчисление предикатов (исчисление предикатов без собственных аксиом) - …теория. <...> Чистое исчисление предикатов (исчисление предикатов без собственных аксиом) – в общем случае …теория. <...> Теория первого порядка с собственными аксиомами - … теория… <...> При преобразовании <...>
Математическая_логика_и_теория_алгоритмов_Учебное_пособие_для_студентов_заочного_факультета.pdf
УДК 621.391
Блатов И.А., Сергиевская И.М. Математическая логика и теория
алгоритмов. Учебное пособие для студентов заочного факультета. -
Самара: ГОУВПО ПГУТИ, 2011. - 55 с.
Учебное пособие включает программу экзамена по математической логике и
теории алгоритмов, вопросы для самопроверки разной степени сложности по
разделам математической логики и теории алгоритмов и ответы к ним,
рекомендации к выполнению контрольной работы.
Учебное пособие может быть использовано для самостоятельной работы и
подготовки к тестированию.
Редактор:
Старожилова О.В. – к.т.н., доц., доцент кафедры высшей математики ПГУТИ
Рецензент:
Головкина М.В. – к.ф.-м.н., доц., доцент кафедры физики ПГУТИ
Государственное образовательное учреждение высшего
профессионального образования
Поволжский государственный университет телекоммуникаций и информатики
Блатов И.А., Сергиевская И.М., 2011
3
Стр.3
Содержание
Введение……………………………………………………………4
Программа экзамена по математической логике и теории
алгоритмов………………………………………………………….5
Литература………………………………………………………….6
Вопросы для самопроверки………………………………………..7
Рекомендации к выполнению контрольной работы……………32
Ответы на вопросы для самопроверки…………………………..40
Введение
Курс «Математическая логика и теория алгоритмов» является одним из
базовых курсов при подготовке программистов.
В настоящее время активно применяются формы контроля знаний
студентов в виде тестов. Данное пособие содержит рекомендации по
выполнению контрольной работы студентов-заочников, а также может помочь
организовать тестовый контроль знаний студентов специальностей 230100
«Программное обеспечение средств вычислительной техники и
автоматизированных систем», 230400 «Информационные системы и
технологии», поскольку написано в соответствии с Государственным
образовательным стандартом высшего профессионального образования по
названным специальностям. Пособие может быть использовано и студентами
других специальностей в курсе дискретной математики.
Тестовые задания затрагивают такие разделы курса как исчисление
высказываний и исчисление предикатов, методы доказательств, машины
Тьюринга, рекурсивные функции.
4
Стр.4