Теория алгоритмов и вычисляемые функции. Математическая логика

В пособии содержатся тестовые задания и упражнения по основным разделам, изучаемым в курсе «Логика». Для облегчения их решения и запоминания материала при подготовке к экзаменам и зачетам прилагается справочный материал в виде таблиц и схем, образцы выполнения итоговой контрольной работы и практикума.

Учебное пособие соответствует государственному образовательному стандарту дисциплин «Дискретная математика», «Математическая логика и теория алгоритмов». Пособие содержит краткий курс дискретной математики и математической логики. В каждом разделе приведены подробно разобранные примеры.

Пособие посвящено основам математической логики и теории алгоритмов. При этом исчисление высказываний представлено достаточно полно, для исчисления предикатов рассмотрены вопросы интерпретации, непротиворечивости и неразрешимости, теория алгоритмов представлена материалами по вычислимым функциям, разрешимым и перечислимым множествам, рассмотрены неразрешимые алгоритмические проблемы. Раздел формальной арифметики включает теорему Гёделя о неполноте.