Список сокращений. ТИФ – тождественно истинная формула;

ТИФ – тождественно истинная формула;

ТЛФ – тождественно ложная формула;

ФПСО – функционально полная система операций;

КЕ – конституента единицы;

КН – конституента нуля;

ФАЛ – функции алгебры логики;

НДФ – нормальная дизъюнктивная форма;

НКФ – нормальная конъюнктивная форма;

СНД(К)Ф – совершенная нормальная дизъюнктивная (конъюнктив-

ная) форма;

сНД(К)Ф – сокращенная нормальная дизъюнктивная (конъюнктив-

ная) форма;

ТНД(К)Ф – тупиковая нормальная дизъюнктивная (конъюнктивная)

форма;

МНД(К)Ф – минимальная нормальная дизъюнктивная (конъюнктив-

ная) форма;

МФ – минимальная форма;

КК – карта Карно;

РКС – релейно-коммутационная схема;

ПЗ – правило заключения;

ПОП – правило одновременной подстановки;

ПСЗ – правило сложного заключения;

ПСДО – правило снятия двойного отрицания;

ТД – теорема дедукции;

ОТД – обобщенная теорема дедукции;

ПНФ – предварённая нормальная форма;

СПР – схема примитивной рекурсии;

МТ – машина Тьюринга;

ДМТ – детерминированная машина Тьюринга;

НДМТ – недетерминированная машина Тьюринга;

ВСА – временная сложность алгоритма;

ПСА – пространственная сложность алгоритма;

ДВУ – детерминированное вычислительное устройство;

НДВУ – недетерминированное вычислительное устройство.

Содержание

Введение....................................................................................................................3

1.Алгебра логики ………………………………………………………………….5

1.1.Понятие о простом и сложном высказывании……………………………......5

1.2.Логческие операции над высказываниями ………………………………….. 7

1.3.Формулы алгебры логики …………………………………………………….13

1.4.Аксиомы и законы алгебры логики ………………………………………….17

1.4.1.Правила склеивания для элементарных конъюнкций и дизъюнкций …...24

1.4.2.Правила поглощения для элементарных конъюнкций и дизъюнкций......25

1.4.3.Правило развертывания ………………………………………………….....25

1.5.Функции алгебры логики. Нормальные формы логических функций …….28

1.6.Минимизация логических функций ……………………………………........33

1.6.1.Рачетный метод минимизации ……………………………………………..34

1.6.2.Табличный метод минимизации …………………………………………...36

1.6.3.Расчетно-табличный метод минимизации (метод Квайна) …………........40

1.7.Некоторые применения алгебры логики …………………………………….46

2.Исчисление высказываний …………………………………………………..55

2.1.Понятие формулы исчисления высказываний ……………………………...56

2.2.Аксиомы и простейшие правила вывода ……………………………………58

2.3.Определение доказуемой формулы ……………………………....................61

2.4.Производные правила вывода …………………………………………….....63

2.5.Определение формулы, выводимой из совокупности формул H ………....67

2.6.Понятие вывода……..…………………………………………………………69

2.7.Основные правила выводимости …………………………………................71

2.8.Доказательство некоторых законов логики ………………………………….74

2.9.Проблемы аксиоматического исчисления высказываний …………………77

3.Логика предикатов …………………………………………………………….83

3.1.Понятие предиката ………………………………………………....................83

3.2.Логические операции над предикатами ……………………………………..87

3.3.Кванторные операции ………………………………………………………...90

3.4.Определение формулы логики предикатов... ……………………………….96

3.5.Равносильные формулы логики предикатов ……………………………......98

3.6.Предваренная нормальная форма …………………………………………..105

3.7.Выполнимость и общезначимость формул ………………………..............106

3.8.Применение языка логики предикатов в математике и технике ………....111

4.Основные положения теории алгоритмов ………………………………...116

4.1.Интуитивное понятие алгоритма …………………………………………...116

4.2.Уточнение понятия алгоритма ……………………………………………...118

4.3.Частично рекурсивные и общерекурсивные функции ……………………..121

4.4.МашиныТьюринга …………………………………………………………...128

4.5.Понятие о нормальных алгоритмах Маркова ……………………………..137

4.6.Алгоритмически неразрешимые проблемы ………………………………..138

4.7.Сложность алгоритмов ……………………………………………………...140

Ответы и решения ……………………………………………………………..151

Раздел 1…………………………………………………………………………...151

Подраздел 1.1……………………………………………………………………..151

Подраздел 1.2……………………………………………………………………..151

Подраздел 1.3……………………………………………………………………..153

Подраздел 1.4……………………………………………………………………..154

Подраздел 1.5……………………………………………………………………..155

Подраздел 1.6……………………………………………………………………..156

Подраздел 1.7……………………………………………………………………..158

Раздел 2 ………………………………………………………………………….. 161

Подраздел 2.1…………………………………………………………………….161

Подраздел 2.4…………………………………………………………………….161

Подраздел 2.8…………………………………………………………………….164

Раздел 3 …………………………………………………………………………..166

Подраздел 3.2…………………………………………………………………….166

Подраздел 3.3…………………………………………………………………….168

Подраздел 3.5…………………………………………………………………….170

Подраздел 3.7…………………………………………………………………….173

Раздел 4 …………………………………………………………………………..176

Подраздел 4.3…………………………………………………………………….176

Подраздел 4.4…………………………………………………………………….179

Библиографический список ………………………………………………….186

Список сокращений............................................................................................188

Содержание …………………………………………………….........................190