Читать онлайн «Математическая логика и теория алгоритмов: метод. указания к выполнению типового расчета»

Московский государственный технический университет имени Н. Э. Баумана Т. Е. Бояринцева, Н. В. Золотова, Р. С. Исмагилов МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ Методические указания к выполнению типового расчета Москва Издательство МГТУ им. Н. Э. Баумана 2011 УДК 517. 11 ББК 22. 12 Б86 Рецензент А. И. Белоусов Бояринцева Т. Е. Б86 Математическая логика и теория алгоритмов : метод. указа- ния к выполнению типового расчета / Т. Е. Бояринцева, Н. В. Зо- лотова, Р. С. Исмагилов. – М. : Изд-во МГТУ им. Н. Э. Баумана, 2011. – 43, [5] с. : ил. Приведены основные понятия и факты, относящиеся к языку высказываний, языку предикатов, теории алгоритмов, теории нечет- ких множеств и нечеткой логике. Наряду с традиционными раздела- ми математической логики изложен метод резолюций, полезный для приложений. Рассмотрены типовые задачи. Для студентов, изучающих математическую логику, а также для преподавателей. Рекомендовано Учебно-методической комиссией НУК ФН МГТУ им. Н. Э. Баумана. УДК 517. 11 ББК 22. 12 c МГТУ им. Н. Э. Баумана, 2011   ВВЕДЕНИЕ Формальные языки (в дальнейшем опускаем эпитет «формаль- ный») используются как инструмент для описания и исследования понятий, методов (алгоритмов и пр. ), связанных с той или иной областью математики либо ее приложений. Мы будем иметь дело с двумя примерами — языком высказываний и языком предика- тов. Прежде чем обратиться к ним, рассмотрим некоторые общие понятия, связанные с языками. Язык складывается из cинтаксиса и семантики. С синтаксисом связаны следующие понятия. 1) алфавит — конечная совокупность символов, называемых буквами; 2) слово — любая конечная цепочка букв алфавита; 3) формулы — «правильно составленные» слова, выделяемые из множества слов с помощью некоторого набора правил. В некото- рых случаях предварительно вводят (также с помощью некоторого набора правил) набор слов, называемых термами. Это материал, из которого строятся формулы. Синтаксис построен. Переходим к семантике. Семантика заключается в указании интерпретации (термов, формул). Это понятие трудно описать, не прибегая к конкретным примерам языков. Можно лишь сказать, что интерпретация ставит в соответствие буквам, термам, формулам либо математические объекты (числа, элементы множеств, знаки неравенств, равенств и пр. ), либо предметы и понятия, связанные с окружающим миром. Далее приводятся правила, выделяющие из совокупности формул те, которые считаются истинными в данной интерпретации. Обычно указывается целый класс интерпретаций. Формула, ис- тинная в каждой из них, называется тождественно истинной; ее также называют тавтологией или законом языка. 3  Важный элемент языка — исчисление.