Московский государственный технический университет имени Н.Э. Баумана Т.Е. Бояринцева, Н.В. Золотова, Р.С. Исмагилов МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ Методические указания к выполнению типового расчета Москва Издательство МГТУ им. <...> Белоусов Б86 Бояринцева Т.Е. Математическаялогика и теорияалгоритмов : метод. указанияк выполнению типового расчета / Т.Е. Бояринцева, Н.В. Золотова, Р.С. Исмагилов. <...> Приведены основные понятия и факты, относящиеся к языку высказываний, языку предикатов, теории алгоритмов, теории нечетких множеств и нечеткой логике. <...> Наряду с традиционными разделами математической логики изложен метод резолюций, полезный для приложений. <...> 1) алфавит — конечнаясовокупность символов, называемых буквами; 2) слово — любаяконечнаяцепочка букв алфавита; 3) формулы — «правильно составленные» слова, выделяемые из множества слов с помощью некоторого набора правил. <...> В некоторых случаях предварительно вводят (также с помощью некоторого набора правил) набор слов, называемых термами. <...> Далее приводятся правила, выделяющие из совокупности формул те, которые считаютсяистинными в данной интерпретации. <...> Длясокращениязапивместо ((α) ) ит. п. угольник), ( , ) (скобки) (разумеется, расставленные в этом предложении запятые не входят в алфавит). б) введем термы по следующим правилам. <...> Во-первых, | есть си будем опускать некоторые скобки и писать ||| вместо ((|)(|))(|), атакже α в) назовем формулой любое слово вида α∆β,где α, β — термы. <...> Зафиксируем целое число m> 0 и +1,Im((α)(β)) = Im(α)+Im(β) (таким образом,штрих интерпретирован как прибавление единицы, а приписывание одного терма зададим следующую интерпретацию. <...> Дляэтого поставим в соответствие каждому терму α число Im(α) по следующим правилам: Im(|)= m,Im(α )= Im(α)+ к другому — как сложение). <...> Далее, если формулы α∆β и γ∆θ — законы, то законами объявляются также формулы (α)(γ)∆(β)(θ). <...> Булевы векторы и булевы функции жество всех векторов вида x =(x1 .xn),xi ∈{0, 1} (в записи векторов опускаем <...>
_Математическая_логика_и_теория_алгоритмов.pdf
УДК 517.11
ББК 22.12
Б86
Рецензент А.И. Белоусов
Б86
Бояринцева Т.Е.
Математическаялогика и теорияалгоритмов : метод. указанияк
выполнению типового расчета / Т.Е. Бояринцева, Н.В. Золотова,
Р.С. Исмагилов. – М.: Изд-во МГТУ им. Н.Э. Баумана,
2011. – 43, [5] с. : ил.
Приведены основные понятия и факты, относящиеся к языку
высказываний, языку предикатов, теории алгоритмов, теории нечетких
множеств и нечеткой логике. Наряду с традиционными разделами
математической логики изложен метод резолюций, полезный для
приложений. Рассмотрены типовые задачи.
Длястудентов, изучающих математическую логику, а также для
преподавателей.
Рекомендовано Учебно-методической комиссией НУК ФН МГТУ
им. Н.Э. Баумана.
УДК 517.11
ББК 22.12
МГТУ им. Н.Э. Баумана, 2011
c
Стр.2
ОГЛАВЛЕНИЕ
Введение ........................................................ 3
1. ЯЗЫК ВЫСКАЗЫВАНИЙ ................................... 6
1.1. Булевы векторы и булевы функции . . . . .................... 6
1.2. Язык высказываний ....................................... 8
1.3. Метод резолюций в языке высказываний................... 13
2. ЯЗЫК ПРЕДИКАТОВ........................................ 16
2.1. Синтаксис языка предикатов .............................. 16
2.2. Интерпретации. Семантика языка предикатов . . ............ 18
2.3. Метод резолюций в языке предикатов . . ................... 24
3. ТЕОРИЯ АЛГОРИТМОВ .................................... 30
3.1. Алгоритмы ............................................... 30
3.2. Машины с неограниченными регистрами. Тезис Ч¨
3.3. Задачи нумерации и перечислениямножеств . . . . ........... 35
3.4. Некоторые свойства разрешимых и перечислимых множеств 37
3.5. Алгоритмическаяразрешимость и неразрешимость ........ 39
4. НЕЧЕТКИЕ МНОЖЕСТВА И НЕЧЕТКАЯ ЛОГИКА ....... 40
4.1. Нечеткие множества . . .................................... 40
4.2. Нечеткаялогика высказываний . . .......................... 43
Литература ..................................................... 44
ерча ..... 32
Стр.45