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

1 Введение

В результате изучения дисциплины «Математическая логика и теория алгоритмов» студенты должны:

• освоить формальный язык математической логики для математических утверждений;

• освоить базовые понятия теории множеств;

• изучить теорию и методы математической логики и теории алгоритмов;

• научиться решать задачи определенного вида, связанные с формальным языком, логикой высказываний, теорией множеств и теорией алгоритмов.

Данное пособие содержит практический материал, предназначенный

для обучения студентов умению решать задачи по математической логике

и теории алгоритмов. Из всей программы курса выбрано несколько тем,

усвоение которых, на наш взгляд, требует умения решать задачи определенного вида.

Что значит владение точными предметами? Это и есть умение решать задачи, причем не столько стандартные, но и требующие известной

независимости мышления, здравого смысла, оригинальности, изобретательности.

Неизвестны какие бы то ни было правила мышления, которые точно

предписывали бы мышлению наиболее целесообразные пути. Если бы подобные правила и были возможны, вряд ли они были бы очень полезны.

Наилучшие правила мышления нельзя получить как-то извне, их нужно

выработать так, чтобы они вошли в плоть и кровь и действовали с силой

инстинкта. Поэтому для развития мышления действительно полезным является только его упражнение.

5

Для практического освоения математической логики и теории алгоритмов предлагаемые для студентов задачи делятся на две неравноценные

группы: задачи по теме «Предикаты и интерпретации» должны помочь

студентам правильно ответить на тесты по указанной теме — такие тесты

включены в первую контрольную работу (тестовую). Остальные рассматриваемые задачи относятся к темам, включенным во вторую контрольную

работу (письменную). Рассматриваются решения типичных задач по темам:

1) «операции с множествами», 2) «отношения», 3) «отображения», 4) «эквивалентность и порядок», 5) «логика высказываний», 6) «язык логики предикатов», 7) «математическая индукция», 8) «сравнение скорости роста».

В последнем разделе приводятся варианты заданий для второй контрольной работы.