М. С. Спирина - Учебно-методическое пособие по дисциплине «Математическая логика и теория алгоритмов» для студентов технических направлений и специальностей

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СЕРВИСА (ПВГУС)»
Кафедра «Высшая математика»

СОГЛАСОВАНО

УТВЕРЖДАЮ

Протокол УМС №__________

Проректор по УР и КО

от «

_______________ О.Н. Наумова

»_______________2010

Проректор по УМР
________________ С.П. Ермишин

УЧЕБНО-МЕТОДИЧЕСКОЕ ПОСОБИЕ
по дисциплине «Математическая логика и теория алгоритмов» для студентов технических
направлений и специальностей

Составитель: М.С. Спирина

Тольятти 2010

1

Утверждено на заседании кафедры «Высшая математика»
Протокол № 7 от 22.04.10
Зав. кафедрой «ВМ», к.ф.- м.н., доцент _____________ Т.В. Никитенко
Утверждено Научно-методическим Советом по естественно-научным и
математическим дисциплинам
Протокол № ____ от «____» ____________2010
Доцент, к.ф.-м.н ______________________________________ Т.В. Никитенко

2

Введение
Учебно-методическое пособие по дисциплине «Математическая логика и теория
алгоритмов» является логическим продолжением пособия «Конспект лекций по курсу
«Математическая логика и теория алгоритмов» для студентов технических
специальностей и направлений. Составитель: М.С. Спирина. Тольятти, 2010». Пособие
призвано осуществить практическую поддержку теоретического курса по этой
дисциплине. Пособие содержит типичные задания и наиболее важные задачи,
необходимые для приобретения опыта практической деятельности по этой дисциплине.
Пособие написано в соответствии с действующей программой по дисциплине
«Математическая логика и теория алгоритмов», раздел «Общие математические и
естественнонаучные дисциплины» для студентов технических специальностей и
направлений. Основной задачей изучения этой дисциплины при подготовке студентов
технических специальностей и направлений является обеспечение условий для
формирования профессиональной компетентности в области информационных систем
различного назначения. Благодаря изучению математической логики будущий выпускник
будет подготовлен к решению профессиональных задач в проектно-конструкторской и
производственно-технологической деятельности.
«Математическая логика и теория алгоритмов» тесно связана с дисциплиной
«Дискретная математика» и является ее логическим продолжением. В свою очередь
знания математической логики будут востребованы при изучении таких спецдисциплин
как «Программирование на языке высокого уровня», «Основы теории управления»,
«Организация ЭВМ и систем», «Базы данных», «Методы и средства защиты
компьютерной информации» и других.
Целью пособия является оказание методической помощи студентам при выполнении
практических заданий по этой дисциплине. Поэтому каждое занятие начинается с кратких
теоретических сведений, необходимых для выполнения практических заданий. Широко
представлена система упражнений: для каждого учебного элемента в пособии имеется
практическое задание, а для каждого вида заданий в пособии имеется соответствующий
образец решения с подробными комментариями.
«Математическая логика и теория алгоритмов» является глубоко абстрактной и
поэтому весьма сложно усваиваемой студентами наукой, по которой недостаточно
доступной учебно-методической литературы. В связи с этим издание данного пособия
приобретает особую актуальность для студентов заочной формы обучения. Однако
структура данного пособия не позволяет включить в него в полном объеме весь
теоретический материал, необходимый для осмысленного выполнения практических
заданий. Так как в этой дисциплине много новых терминов и математических символов,
то для их применения важно знать точное определение понятий и смысл символов.
Поэтому для выполнения практических заданий студентам как дневной, так и заочной
форм обучения рекомендуется предварительно внимательно ознакомиться с содержанием
соответствующих лекций по пособию [14]. Вместе с тем, основные сокращения, символы
и обозначения приведены в конце пособия. В пособии принят следующий способ
нумерации: номер каждого задания состоит из двух чисел: первое число соответствует
номеру занятия, второе – есть порядковый номер конкретного задания на этом занятии.

3

Содержание
Введение
Раздел 1. Построение логических исчислений
Занятие №1. Логика --">