ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ

А

аксиома объёмности................................................. 150

аксиома (неупорядоченной) пары.............................. 151

аксиома бесконечности.............................................. 154

аксиома выбора........................................................... 157

аксиома выделения...................................................... 150

аксиома объединения.................................................. 151

аксиома равенства...................................................... 150

аксиома регулярности................................................ 152

аксиома существования булеана............................... 151

аксиома существования области значений.............. 153

аксиоматика Цермело-Френкеля теории множеств 149

аксиомы Пеано........................................................... 171

аксиомы исчисления высказываний............................. 97

аксиомы логических связок.......................................... 12

аксиомы специальной теории.................................... 103

аксиомы формального исчисления предикатов....... 100

аксиомы формальной арифметики.......................... 105

алгоритм приписывания истинностных значений высказываниям 6

алфавит специальной теории.................................... 102

алфавит формальной арифметики.......................... 104

алфавит язык исчисления высказываний..................... 9

алфавит языка исчисления предикатов..................... 70

антисимметричность............................................... 159

арифметическое выражение..................................... 104

ассоциативность дизъюнкции.............................. 19, 22

ассоциативность конъюнкции.................................... 18

Б

бесконечное множество............................................. 155

бинарное отношение................................................... 158

булеан множества...................................................... 147

булеан множества (множество всех подмножеств) 151

булева функция.............................................................. 33

В

верхняя грань множества.......................................... 159

вполне упорядоченное множество............................ 159

выводимость формул в специальной теории........... 107

выделение множества в другом множестве с помощью характеристического свойства его элементов 146

выполнимая формула, истинная на всех конечных моделях 121

высказывание................................................................... 5

Д

декартов квадрат множества................................. 148

дизъюнктивная нормальная форма........................... 27

доказательство теоремы........................................... 90

доказательство формулы в формальном исчислении предикатов 101

доказательство формулы в специальной теории... 104

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

доказательство формулы в формальном исчислении высказываний 98

доказательство эквивалентности нескольких условий 94

доказуемая формула специальной теории............... 104

доказуемая формула формального исчисления высказываний 99

доказуемая формула формального исчисления предикатов 101

доказуемая формула формальной арифметики..... 106

достаточное условие.................................................... 89

З

закон ассоциативности............................................. 137

закон выражения импликации................................... 139

закон двойного отрицания..................................... 19, 22

закон дистрибутивности.......................................... 137

закон идемпотентности........................................... 137

закон коммутативности........................................... 137

закон контрапозиции............................................. 19, 22

закон логики................................................................... 18

закон ограничения................................................... 19, 22

закон перестановки посылок................................. 19, 22

закон поглощения.................................................... 19, 22

закон противоположности................................... 19, 22

закон разбора случаев................................................... 19

закон рассуждений от противного...................... 19, 22

закон резолюций............................................................ 19

закон силлогизма........................................................... 19

закон тождества......................................................... 18

законы введения дизъюнкции....................................... 19

законы де Моргана......................................... 19, 22, 139

законы действий с тавтологиями и противоречиями 20, 23

законы дистрибутивности.................................... 19, 22

законы удаления конъюнкции...................................... 19

законы, выражающие одни логические связки через другие 19, 22

замкнутое относительно резолюций множество формул 52

замыкание относительно резолюций......................... 52

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

значение функции........................................................ 153

И

идемпотентность дизъюнкции............................ 18, 22

идемпотентность конъюнкции............................ 18, 22

импликативная форма записи теоремы.................. 86

интегральная схема...................................................... 56

интерпретация множества формул исчисления предикатов 72

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

исключающее или.......................................................... 34

истинностное значение формулы исчисления высказываний 12

К

квантор всеобщности "............................................ 63

квантор существования $.......................................... 63

кванторы....................................................................... 63

коммутативность дизъюнкции............................ 18, 22

коммутативность конъюнкции........................... 18, 22

конечное множество.................................................. 155

константы (выделенные символы) в специальной теории 102

континуум-гипотеза.......................................... 166, 176

контрапозиционное утверждение.............................. 87

конъюнктивная нормальная форма........................... 27

конъюнкция, дизъюнкциея, импликация и эквивалентность предикатов 61

Л

лемма о значениях выражений x^e............................... 26

лемма о разложении булевой функции по k переменным 34

лемма о свойствах отношения равносильности формул 21

лемма об областях истинности.................................. 62

линейно упорядоченное множество.......................... 159

линейный порядок........................................................ 159

логические связки............................................................ 9

логическое следствие.................................................... 42

логическое следствие предиката................................. 89

логическое следствие формул исчисления предикатов 76

М

метод полного перебора возможных случаев............ 92

метод рассуждения от противного........................... 93

метод резолюций.......................................................... 51

минимальный и максимальный элементы множества 159

множества неравные.................................................. 146

множества равные..................................................... 146

множество.................................................................. 146

множество подмножеств......................................... 147

модель (интерпретация) формальной теории....... 112

Н

наименьший и наибольший элементы множества. 159

начальный отрезок множества................................ 159

независимая система аксиом.................................... 124

необходимое условие...................................................... 89

непротиворечивость специальной теории............... 108

неформальная аксиоматическая теория.................. 96

О

область значений функции........................................ 153

область истинности предиката................................ 60

область ложности предиката.................................... 60

область определения предиката................................. 60

область определения функции................................... 153

обратное утверждение................................................ 87

объединение множеств...................................... 147, 152

объектная (или предметная) область....................... 59

объектные переменные................................................. 70

одноразрядный сумматор............................................ 57

определение................................................................ 5, 83

ординальные числа...................................................... 154

основные равносильности исчисления высказываний 136

отношение принадлежности элемента множеству 146

отображение............................................................... 153

отрицание предиката................................................. 61

П

парадокс Берри........................................................... 176

парадокс Рассела........................................................ 149

первичные неопределяемые понятия........................... 83

первичные отношения.................................................. 83

первоотношение.............................................................. 5

первопонятие................................................................... 5

пересечение множеств............................... 147, 150, 152

перечисление элементов множества........................ 146

подмножество множества....................................... 146

полином Жегалкина...................................................... 40

полная формальная теория....................................... 114

полное множество булевых функций.......................... 36

полнота формальной теории в узком смысле......... 114

полнота формальной теории в широком смысле.... 113

полный порядок........................................................... 159

правила введения дизъюнкции.................................... 135

правила введения конъюнкции.................................... 135

правила вывода в формальной арифметики............ 106

правила вывода формального исчисления предикатов 100

правила дедукции........................................................... 45

правила объединения и разделения посылок............... 45

правила силлогизма....................................................... 45

правила удаления конъюнкции................................... 135

правило modus ponens.................................................. 44

правило modus tollens................................................. 135

правило modus tollens.................................................... 45

правило введения дизъюнкции...................................... 45

правило введения конъюнкции...................................... 45

правило восстановления скобок в формулах исчисления высказываний 11

правило вывода формального исчисления высказываний 98

правило контрапозиции........................................ 45, 136

правило объединения посылок.................................... 134

правило опровержения.......................................... 45, 136

правило перестановки посылок............................ 45, 133

правило разделения посылок....................................... 134

правило расширения посылок....................................... 45

правило резолюций........................................................ 45

правило силлогизма..................................................... 133

правило удаления конъюнкции..................................... 45

предварённая нормальная форма (ПНФ) формулы исчисления предикатов 79

предварённая приведённая нормальная форма (ППНФ) формулы исчисления предикатов 79

предикат от n переменных.................................. 59, 60

предикатные символы.................................................. 70

приведённая форма (ПФ) формулы исчисления предикатов 79

принцип трансфинитной индукции.......................... 165

проблема выполнимости формулы формальной теории 118

проблема доказуемости формулы формальной теории 118

проблема общезначимости формулы формальной теории 118

производные правила вывода исчисления высказываний..... 133

пропозициональные переменные.................................... 9

противоположное утверждение................................. 87

прямое (или декартово) произведение множеств... 148

прямое утверждение.................................................... 87

пустое множество............................................. 146, 150

Р

равномощные множества.......................................... 155

равносильные на множестве предикаты................... 65

равносильные формулы исчисления предикатов........ 75

разность множеств........................................... 147, 150

релейно-контактная схема (РКС)............................. 54

рефлексивность........................................................... 159

С

свободные и связанные вхождения объектных переменных 70

свободные и связанные объектные переменные......... 71

свойства выводимости формул исчисления высказываний 131

свойство упорядоченной пары................................... 151

связывание переменной с помощью кванторов......... 64

служебные символы......................................................... 9

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

совершенная конъюнктивная нормальная форма (СКНФ) 27

совершенная элементарная дизъюнкция.................... 27

совершенная элементарная конъюнкция.................... 27

специальная формальная теория.............................. 102

степень множества................................................... 148

стрелка Пирса ¯......................................................... 34

сумматор....................................................................... 57

схема правил логического следования.......................... 44

схема формальной индукции...................................... 106

Т

таблица истинности формулы исчисления высказываний 14

теорема.......................................................................... 85

теорема Банаха-Тарского......................................... 173

теорема Гёделя о неполноте................................... 111

теорема Гёделя о неполноте формальной арифметики 117

теорема – критерий логического следования............ 76

теорема – критерий логического следования............ 43

теорема – критерий независимости системы аксиом 125

теорема Линдебаума о пополнении теории............ 116

теорема Робинсона.................................................... 173

теорема Чёрча о неразрешимости формальной арифметики 124

теорема Чёрча о неразрешимости формальной теории исчисления предикатов 122

теорема компактности............................................ 108

теорема о взаимосвязях понятиий полноты........... 114

теорема о дедукции.............................................. 44, 132

теорема о дедукции...................................................... 77

теорема о дизъюнктивной и конъюнктивной нормальных формах формального исчисления высказываний 144

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

теорема о количестве наборов из нулей и единиц длины n 17

теорема о количестве неравносильных формул исчисления высказываний 32

теорема о количестве подмножеств n-элементного множества 17

теорема о независимости системы аксиом формального исчисления высказываний 125

теорема о независимости системы аксиом формального исчисления предикатов 130

теорема о неполноте в узком смысле формальных теорий исчислений высказываний и предикатов 116

теорема о непротиворечивости формального исчисления высказываний 109

теорема о непротиворечивости формального исчисления предикатов 110

теорема о полиномах Жегалкина............................... 40

теорема о полноте системы булевых функций......... 38

теорема о полных и неполных системах булевых функций 36

теорема о правиле перечисления интерпретаций..... 16

теорема о предварённой приведённой нормальной форме 80

теорема о приведённой форме.................................... 79

теорема о разрешимости формального исчисления высказываний 120

теорема о реализации булевых функций формулами исчисления высказываний 33

теорема о свойствах операций Ä, Å...................... 38

теорема о совершенных нормальных формах............ 29

теорема о существовании модели............................. 113

теорема о существовании неизмеримых по Лебегу множеств 175

теорема об n-разрешимости.................................... 120

теорема об общезначимых замкнутых $-формулах 123

теорема об основных законах логики......................... 18

теорема об основных правилах логического вывода.. 45

теорема об основных равносильностях...................... 22

теорема об эквивалентности проблем доказуемости, общезначимости и выполнимости 119

теорема об эквивалентных понятиях конечности (бесконечности) множеств 156

теорема об эквивалентных формулировках аксиомы выбора 160

теорема об эквивалентных формулировках аксиомы регулярности 164, 174

теорема об элиминации кванторов на конечном множестве 120

терм (функциональное выражение) в специальной теории 103

тождественно истинные, ложные и выполнимые формулы исчисления предикатов 75

тождественно истинный на множестве предикат 65

тождественно ложный на множестве предикат.... 65

транзитивность......................................................... 159

У

упорядоченная пара............................................ 148, 151

условие функциональности........................................ 153

Ф

ф-категоричная формальная теория...................... 114

формальная аксиоматическая теория...................... 96

формальная арифметика.......................................... 104

формальное исчисление высказываний....................... 97

формальное исчисление предикатов........................... 99

формула выполнимая.................................................... 18

формула замкнутая.................................................... 112

формула исчисления высказываний............................. 97

формула исчисления предикатов............................... 100

формула специальной теории.................................... 103

формула тождественно истинная............................. 18

формула тождественно ложная................................ 18

формула формальной арифметики.......................... 104

формула языка исчисления высказываний.................... 9

формула языка исчисления предикатов..................... 70

формула-противоречие................................................ 18

формула-тавтология................................................... 18

формулы равносильные................................................. 20

функциональные символы в специальной теории.... 102

функция........................................................................ 153

Ц

цепь............................................................................... 159

Ч

частично упорядоченное множество....................... 159

частичный порядок.................................................... 159

Ш

штрих Шеффера |....................................................... 34

Э

элемент множества................................................... 146

элементарная дизъюнкция........................................... 27

элементарная конъюнкция.......................................... 27

Я

язык исчисления высказываний.................................... 97

язык исчисления предикатов....................................... 99