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

Московский государственный технический университет
имени Н.Э. Баумана
Т.Е. Бояринцева, Н.В. Золотова,
Р.С. Исмагилов
МАТЕМАТИЧЕСКАЯ ЛОГИКА
И ТЕОРИЯ АЛГОРИТМОВ
Методические указания
к выполнению типового расчета
Москва
Издательство МГТУ им. Н.Э. Баумана
2011

УДК 517.11
ББК 22.12
Б86
Рецензент А.И. Белоусов
Б86
Бояринцева Т.Е.
Математическая логика и теория алгоритмов : метод. указания к выполнению типового расчета / Т.Е. Бояринцева, Н.В. Золотова, Р.С. Исмагилов. – М.: Изд-во МГТУ им. Н.Э. Баумана,
2011. – 43, [5] с. : ил.
Приведены основные понятия и факты, относящиеся к языку
высказываний, языку предикатов, теории алгоритмов, теории нечетких множеств и нечеткой логике. Наряду с традиционными разделами математической логики изложен метод резолюций, полезный для
приложений. Рассмотрены типовые задачи.
Для студентов, изучающих математическую логику, а также для
преподавателей.
Рекомендовано Учебно-методической комиссией НУК ФН МГТУ
им. Н.Э. Баумана.
УДК 517.11
ББК 22.12
c
⃝МГТУ им. Н.Э. Баумана, 2011

ВВЕДЕНИЕ
Формальные языки (в дальнейшем опускаем эпитет «формальный») используются как инструмент для описания и исследования
понятий, методов (алгоритмов и пр.), связанных с той или иной
областью математики либо ее приложений. Мы будем иметь дело
с двумя примерами — языком высказываний и языком предикатов. Прежде чем обратиться к ним, рассмотрим некоторые общие
понятия, связанные с языками.
Язык складывается из cинтаксиса и семантики. С синтаксисом
связаны следующие понятия.
1) алфавит — конечная совокупность символов, называемых
буквами;
2) слово — любая конечная цепочка букв алфавита;
3) формулы — «правильно составленные» слова, выделяемые из
множества слов с помощью некоторого набора правил. В некоторых случаях предварительно вводят (также с помощью некоторого
набора правил) набор слов, называемых термами. Это материал,
из которого строятся формулы.
Синтаксис построен. Переходим к семантике.
Семантика заключается в указании интерпретации (термов,
формул). Это понятие трудно описать, не прибегая к конкретным
примерам языков. Можно лишь сказать, что интерпретация ставит
в соответствие буквам, термам, формулам либо математические
объекты (числа, элементы множеств, знаки неравенств, равенств и
пр.), либо предметы и понятия, связанные с окружающим миром.
Далее приводятся правила, выделяющие из совокупности формул
те, которые считаются истинными в данной интерпретации.
Обычно указывается целый класс интерпретаций. Формула, истинная в каждой из них, называется тождественно истинной; ее
также называют тавтологией или законом языка.
3

Важный элемент языка — исчисление. Так называется набор
правил, позволяющих выводить законы языка, не прибегая к конкретным интерпретациям, а используя лишь формальные манипуляции, предписанные правилами.
Опишем построение языка более подробно. Построим синтаксис:
а) алфавит состоит из символов: | (палочка), ′ (штрих), Δ (треугольник), ( , ) (скобки) (разумеется, расставленные в этом предложении запятые не входят в алфавит).
б) введем термы по следующим правилам. Во-первых, | есть
терм (по определению). Далее, если слова α, β — термы, то слова
(α)(β) и (α)′ — тоже термы. Термы описаны. Для сокращения записи будем опускать некоторые скобки и писать ||| вместо ((|)(|))(|),
а также α
′′ вместо ((α)
′)
′ и т. п.
в) назовем формулой любое слово вида αΔβ, где α, β — термы.
Синтаксис готов.
Перейдем к семантике. Зафиксируем целое число m > 0 и
зададим следующую интерпретацию. Во-первых, интерпретируем
термы. Для этого поставим в соответствие каждому терму α число
Im(α) по следующим правилам: Im(|) = m, Im(α
′) = Im(α) +
+1, Im((α)(β)) = Im(α)+Im(β) (таким образом, штрих интерпретирован как прибавление единицы, а приписывание одного терма
к другому — как сложение). Наконец, формулу αΔβ интерпретируем как равенство Im(α) = Im(β) (таким образом, треугольник
интерпретирован как равенство). Мы получили семейство интерпретаций Im.
Формулу αΔβ назовем истинной в интерпретации Im, если
Im(α) = Im(β). Формула, истинная в каждой из интерпретаций
Im, есть закон нашего языка. Вот пример закона: (||)
′ Δ(|)(|
′) (проверьте!)
Наконец, обратимся к исчислению. Данный язык весьма прост,
а потому легко непосредственно описать все его законы. Однако
мы опишем его по образцу, который обычно применяется в более
сложных языках. Во-первых, назовем законом формулу |Δ|. Далее,
если формулы αΔβ и γΔθ — законы, то законами объявляются
также формулы (α)(γ)Δ(β)(θ). Наконец, законами объявляют те и
только те формулы, которые можно получить применением этих
правил.
4

Упражнение. Интерпретируйте Δ как < и выпишите какойлибо закон полученного языка.
Переходим к языку высказываний. Начнем со вспомогательного инструмента — булевых функций.