А
аксиома объёмности................................................. 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
Л
лемма о значениях выражений xe............................... 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