Булос Дж., Джеффри Р. — Вычислимость и логика :: Электронная библиотека попечительского совета мехмата МГУ

Главная Ex Libris Книги Журналы Статьи Серии Каталог Wanted Загрузка ХудЛит Справка Поиск по индексам Поиск Форум

Авторизация

Поиск по указателям

Булос Дж., Джеффри Р. — Вычислимость и логика

Обсудите книгу на научном форуме

Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

Название: Вычислимость и логика

Авторы: Булос Дж., Джеффри Р.

Аннотация:

Книга известных американских математиков, являющаяся в настоящее время одной из наиболее известных в США книг по математической логике, выдержавшая там три издания (1974, 1980, 1989 гг.). В ней содержатся начала и некоторые дополнительные главы математической логики, последовательно и строго излагаются классические теоремы о неразрешимости логики предикатов и разрешимости некоторых ее фрагментов, знаменитые теоремы Гёделя о полноте, нестандартные модели и многое другое. Материал дополнен упражнениями.
Для всех, кто интересуется математической логикой, а также информатикой, философией и лингвистикой.

Язык:

Рубрика: Математика/Алгебра/Математическая логика/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 1994

Количество страниц: 396

Добавлена в каталог: 09.05.2005

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID

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

$M^{*}$ (машина Тьюринга)      194
$\mathcal{M}$ стандартная интерпретация языка арифметики      135 214
EI (экзистенциальная конкретизация) (existential instantiation)      170
J (функция пересчета пар) (pairing function)      218
L (язык арифметики) (language of arithmetic)      133 214
q      145
UI (универсальная конкретизация) (universal instantiation)      170
Z (элементарная арифметика Пеано) (elementary Peano arithmetic)      242
Абак (abacus)      53
Аддисон      281
Адрес (address)      81
Аксиома зависимого выбора (axiom of dependent choice)      176 178 211 212
Аксиома конечности (axiom of finitude)      197
Аксиоматизируемая теория (axiomatizable theory)      237
Аксиомы индукции (induction axioms)      242
Аксиомы системы G (axioms of G)      351
Аксиомы теории Q (axioms of Q)      214
Аннотация (annotation)      170 174
Антидиагональная последовательность (antidiagonal sequence)      28
Антидиагональное множество (antidiagonal set)      28
Аргумент (argument)      13
Арифметика (arithmetic)      235
Арифметика без сложения (arithmetic without addition)      290
Арифметика умножения (arithmetic without multiplication)      290
Безбуквенное предложение (letterless sentence)      354
Бернайс      242 245
Бет      322
Булос      350 352
Буль      328
Бюхи      154
Взаимно простые числа (relatively prime numbers)      296
Всюду определенная функция (total function)      18
Вторая теорема Гёделя о неполноте (Goedel's second incompleteness theorem)      249
Вывод из множества $\Delta$ (derivation from $\Delta$ )      170
Вывод канонический (canonical derivation)      180
Вынуждение (forcing)      281
Выполнение (satisfaction)      141 143
Выполнимость (satisfiability)      141 144
Вычисление (computation)      36
Генерическое множество (generic set)      284
Гёделева нумерующая (godel numbering)      228
Гёдель      160 228 281 373
Гильберт      242 245
Голдфарб      358
Граф очистки (mop-up graph)      95-97
Граф переходов (flow graph)      40
График (graph)      121
де Йонг      353
Денотат имени (denotation, bearer, designation, reference)      134
Денотат, терма (denotation)      139
Диагонализация выражения (diagonalization of an expression)      230
Диагональная последовательность (diagonal sequence)      27
Диагональное множество (diagonal set)      27
Диаграмма (diagram)      196
Диадическое предложение (dyadic sentence)      300
Доказательство в Z (proof in Z)      243
Дребен      309
Единичечная запись (monadic notation)      79
Значение имени в интерпретации      134 (см. «Денотат имени»)
Значение терма в интерпретации (denotation)      139
Значение функции (value)      13
ИМЯ (NAME)      132
Интерполянт (interpolation sentence)      309
Интерполяционная лемма Крейга (Craig interpolation lemma)      309-318 319 326
Интерпретации изоморфные (isomorphic interpretations)      253
Интерпретации элементарно эквивалентные (elementarily equivalent interpretations)      203
Интерпретация (interpretation, structure)      134 135
Интерпретация имени      134 (см. «Денотат имени»)
Интерпретация множества предложений (interpretation of a set of sentences)      135
Интерпретация предложения (interpretation of a sentence)      135
Интерпретация соответствовуюшая множеству предложений (interpretation matching a set of sentences)      183
Интерпретация языка (interpretation of a language)      134
Интерпретация языка арифметики стандартная ( $\mathcal{N}$ ) (standard interpretation of the language of arithmetic)      135 214
Истинностное значение (truth value)      135
Истинность в интерпретации (truth in an interpretation)      141 264
Истинность в модели системы G (validity in a model for G)      356
Йенсен      330
Кантор      25
Категоричная теория (categorical theory)      254
Квантор (quantifier)      131
Квантор ограниченный (bounded quantifier)      119 217 218
Квантор фиктивный (vacuous quantifier)      173
Китайская теорема об остатках (Chinese remainder theorem)      297
Компактность (compactness)      261 271
Композиция (composition)      105
Конгруэнция (congruence)      295
Конечно аксиоматизируемая теория (finitely axiomatizable theory)      237
Конечно выполнимое предложение (finitely satisfiable sentence)      165
Конкретизирующий терм (instantial term)      170
Консервативное расширение (conservative extension)      320
Континуум-гипотеза (continuum hypothesis)      281
Конфигурация (configuration)      41
Корректность (soundness)      167
Кочен      10
Коэкстенсивные термы (coextensive terms)      291
Коэкстенсивные формулы (coextensive formulas)      291
Коэн      281
Крейг      240 308
Кринке      10 249 356
Ламбек      83 99
Лемма о $\beta$ -функции ( $\beta$ -function lemma)      220
Лемма о диагоналиэации (diagonal lemma)      231
Лёб      245
Лёвенгейм      202 205
Логика второго порядка (second-order logic)      261
Логика диадическая (dyadic logic)      300
Логика монадическая (monadic logic)      329-335
Логика первого порядка (first-order logic)      131
Логическая равносильность (logical equivalence)      146 147
Логическая эквивалентность (logical equivalence)      146 147
Логический символ (logical symbol)      132
Логическое следование (implication)      142 144 147
Локально выполнимое множество предложений (O.K. set of sentences)      185
Максимальное непротиворечивое множество (maximal consistent set)      358
Машина Тьюринга (Turing machine)      38
Машинная таблица (machine table)      40
Машины-путешественницы (touring machines)      57
Мелзак      99
Метод диагоналиэации (method of diagonalization)      25-29
Минимизация (minimization)      114 215 217
Множества рекурсивно неотделимые (recursively inseparable sets)      385
Множество n-генерическое (n-generic set)      287
Множество антидиагональное (аntidiagonal set)      28
Множество бесконечное по Дедекинду (Dedekind infinite set)      272
Множество генерическое (generic set)      284
Множество диагональное (diagonal set)      27
Множество значений (range)      18
Множество непротиворечивое (consistent set)      358
Множество непротиворечивое максимальное (maximal consistent set)      358
Множество определимое (definable set)      232
Множество относительно большое (relatively large set)      345
Множество предложений локально выполнимое (O.K. set of sentences)      185
Множество пустое (empty set)      12
Множество разрешимое (decidable set)      233
Множество рекурсивно перечислимое (recursively enumerable set)      384
Множество счетно бесконечное (enumerably infinite set)      12
Множество счетное (enumerable set)      12 19 208
Модель множества предложений (model of a set of sentences)      143
Модель предложения (model of a sentence)      143
Модель системы G (model for G)      356
Монадическая формула (monadic formula)      328
Монадическое предложение (monadic sentence)      200 328
Мостовский      215
Невычислимость (uncomputability)      47
Негативный тест (negative test)      152
Неподвижная точка (fixed point)      353
Непрерывность (continuity)      172
Непротиворечивая теория (consistent theory)      232
Непротиворечивое множество (consistent set)      358
Неравенство верхнее (upper inequality)      293

Неравенство нижнее (lower inequality)      293
Неразрешимое предложение (undecidable sentence)      371
Нестандартные модели арифметики (non-standard models of arithmetic)      256
Несущественность (dispensability)      301
Неявное определение (implicit definition)      322-325
Нормальная форма терма (normal form)      293
Нуль-функция (zero function)      104
Нумератор (enumerator)      208
Область интерпретации (domain of an interpretation)      134
Область определения (domain)      18
Общезначимое предложение (valid sentence)      141
Общезначимость (validity)      141
Описание времени s (description of time s)      158
Определение неявное (implicit definition)      322-325
Определение путем перебора случаев (definition by cases)      117
Определение равенства (definition of identity)      265
Определение явное (explicit definition)      323
Определимое множество (definable set)      232
Определимость в арифметике (definability in arithmetic)      274 280
Определимость в арифметике второго порядка (definability in second-order arithmetic)      273 275 281 289
Опровержение множества $\Delta$ (refutation of $\Delta$ )      168
Основное свойство правила EI (basic property of EI)      172
Отмеченное предложение (red sentence)      313
Относительно большое множество (relatively large set)      345
Отношение регулярное (regular relation)      217
Отношение рефлексивное (reflexive relation)      146 186
Отношение симметричное (symmetrical relation)      146 186
Отношение транзитивное (transitive relation)      146 186
Отношение эквивалентности (equivalence relation)      146 186
Падоа      322
Парадокс Берри (Berry's paradox)      377
Парадокс Сколема (Skolem's paradox)      207
Парис      348
Патнам      309
Пендлбери      97
Первая теорема Гсдслж о неполноте (Godel's first incompleteness theorem)      228 239
Подинтерпретапия (subinterpretation)      202
Подинтерпретапия элементарная (elementary subinterpretation)      211
Подобный элемент (similar element)      330
Подпредложение (subsentence)      331 351
Подстановка (substitution)      105
Подформула (subformula)      329
Позитивный тест (positive test)      152
Полная теория (complete theory)      236
Полное сходство (exact likeness)      331
Полнота (completeness)      167
Порядок O (order O)      208
Правила системы G (rules for G)      351
Правило необходимости (necessitation)      351
Предикат доказуемости (provability predicate)      246
Предикат истинности (truth-predicate)      250
Предикатный символ (predicate letter)      132
Предложение (sentence)      133 291
Предложение безбуквенное (letterless sentence)      354
Предложение диадическое (dyadic sentence)      300
Предложение истинное в интерпретации (sentence true in an interpretation)      141 264
Предложение истинное в модели системы G (sentence valid in a model for G)      356
Предложение конечно выполнимое (finitely satisfiable sentence)      165
Предложение модализованное относительно p (sentence modalized in p)      353
Предложение монадическое (monadic sentence)      200 328
Предложение неразрешимое (undecidable sentence)      371
Предложение общезначимое (valid sentence)      141 356
Предложение отмеченное (red sentence)      313
Предложение системы G (sentence of G)      350
Предложение чистое (pure sentence)      300
Предложение чистое диадическое (pure dyadic sentence)      328 335 339
Предложение чистое монадическое (pure monadic sentence)      333
Представимая функция (representable function)      214
Пренексная нормальная форма (prenex normal form)      148
Пресбургер      290
Примитивная рекурсия (primitive recursion)      106
Примитивно рекурсивная функция (primitive recursive function)      100 105
Проблема остановки (halting problem)      47 54 64 74
Проблема остановки для абаков (abacus halting problem)      96 97
Проблема распознавания (decision problem)      152
Проблема самоприменимости (self-halting problem)      48 53
Проблема усердного абака (busy abacus problem)      96 98
Проблема усердного бобра (busy beaver problem)      46 55-62
Продуктивность (productivity)      46 56
Проектирующие функции (identity fuctions, projection functions)      104
Пропозициональный символ (sentence letter)      132
Процедура распознавания выполнимости бескванторных предложений (decision procedure for quantifier-free satisfiability)      196
Пустое множество (empty set)      12
Равносильность логическая (logical equivalence)      146 147
Радо      56
Разрешимое множество (decidable set)      233
Рамсей      341 342 344
Ранг (rank)      357
Рассел      265 377
Расширение теории (extension of a theory)      232
Реализация имени в интерпретации      134 (см. «Денотат имени»)
Регистры (registers)      81
Регулярная функция (regular function)      115
Регулярное отношение (regular relation)      217
Рейдхаар-Олсон      353 362
Рекурсивная функция (recursive function)      100 114 130 216
Рекурсивно неотделимые множества (recursively inseparable sets)      385
Рекурсивно перечислимое множество (recursively enumerable set)      384
Рекурсия примитивная (primitive recursion)      106
Релятивизация кванторов (relativization of quantifiers)      290
Рефлексивное отношение (reflexive relation)      146 186
Робинсон, A.      321
Робинсон, Р.      215
Россер      371
Самбин      353 362
Сегерберг      356
Символ логический (logical symbol)      132
Символ предикатный (predicate letter)      132
Символ предложения (sentence symbol)      132
Символ пропозициональный (sentence symbol)      132
Символ функциональный (function symbol)      132
Симметричное отношение (symmetrical relation)      146 186
Система G      350
Сколем      202 205 290
Слово (word)      32
Соловэй      352 358
Состояние (state)      39
Стандартная интерпретация языка арифметики ( $\mathcal{N}$ ) (standard interpretation of the language of arithmetic)      135 214
Счетно бесконечное множество (enumerably infinite set)      12
Счетное множество (enumerable set)      12 19 208
Счетность (enumerability)      12 266
Тарский      215 228
Тезис Чёрча (Church's thesis)      37 78 80
Теорема А. Робинсона о непротиворечивости (Robinson's consistency theorem)      321
Теорема Аддисона (Addison's theorem)      281 288-289
Теорема Бета об определимости (Beth's definability theorem)      322-327
Теорема взаимности (reciprocation theorem)      355 367
Теорема Горского о неопределимости (Tarski's indefinability theorem)      228 236 272 327
Теорема Лёаенгейма — Сколема (Skolem-Lowenheim theorem)      180 193 200 204 262 267 328
Теорема Лёба (Lob's theorem)      248 350 352
Теорема о компактности (compactness theorem)      180 192 347
Теорема о корректности (soundness theorem)      173
Теорема о неподвижной точке (fixed point theorem)      353 360-363
Теорема о полноте (completeness theorem)      180
Теорема о семантической корректности (semantical soundness theorem)      357
Теорема о семантической полноте (semantical completeness theorem)      358
Теорема о строгой корректности (strong soundness theorem)      173
Теорема об арифметической корректности (arithmetical soundness theorem)      352
Теорема об полноте (arithmetical completeness theorem)      352
Теорема Рамсеж (Ramsey's theorem)      341
Теорема системы G (theorem of G)      351
Теорема теории (theorem of a theory)      145 213
Теорема Чёрча о неразрешимости (Church's undecidability theorem)      228 235
Теорема Шура (Schur's theorem)      348
Теоремы Гёделж о неполноте (Godel's incompleteness theorems)      228 239 249
Теория $\omega$ -непротиворечивая ( $\omega$ -consistent theory)      373
Теория $\omega$ -противоречивая ( $\omega$ -inconsistent theory)      373
Теория (theory)      145 213
Теория аксиоматизируемая (axiomatizable theory)      237
Теория категоричная (categorical theory)      254

1 2

О проекте