Предметный указатель

а

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

б

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

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

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

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

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

в

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

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

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

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

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

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

д

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

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

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

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

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

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

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

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

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

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

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

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

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

з

закон ассоциативности 138

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

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

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

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

закон коммутативности 138

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

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

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

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

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

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

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

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

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

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

закон тождества 19

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

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

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

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

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

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

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

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

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

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

и

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

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

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

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

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

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

исключающее или 35

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

к

квантор всеобщности ( 64

квантор существования ( 64

кванторы 64

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

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

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

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

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

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

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

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

л

лемма о значениях выражений x( 27

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

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

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

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

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

логическое следствие 43

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

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

м

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

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

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

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

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

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

множество 146

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

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

н

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

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

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

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

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

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

о

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

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

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

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

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

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

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

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

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

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

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

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

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

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

отрицание предиката 62

п

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

правило modus ponens 45

правило modus tollens 136

правило modus tollens 45

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

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

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

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

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

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

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

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

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

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

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

правило силлогизма 134

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

р

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

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

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

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

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

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

с

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

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

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

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

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

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

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

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

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

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

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

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

стрелка Пирса ( 35

сумматор 57

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

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

т

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

теорема 86

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

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

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

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

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

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

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

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

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

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

теорема компактности 109

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

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

теорема о дедукции 78

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

теорема о свойствах операций (, ( 39

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

у

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

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

ф

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

функция 153

ц

цепь 159

ч

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

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

ш

штрих Шеффера | 35

э

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

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

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

я

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

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