alexey_rom (alexey_rom) wrote,
alexey_rom
alexey_rom

Categories:
  • Mood:

Учебник логики

Учебников по математической логике много. Зачем нужен ещё один?
1) Семантические деревья не описаны ни в одном русскоязычном учебнике. Даже такая классика, как "Логика первого порядка" Смальяна, не переведена на русский.
2) Доказательства теорем должны иметь чёткую логическую структуру. Чем она ближе к описанной в учебнике системе вывода, тем лучше. Поэтому естественный вывод в учебнике тоже должен быть, и в максимально удобном для реального использования виде.
3) Логика первого порядка не должна представляться как вершина достижений мат.логики.
4) Достойное место должны занимать приложения.
5) Такой учебник -- идеальное место, чтобы напомнить о базовых понятиях (множество, функция, и т.д.).

Ближе всего к этим требованиям подходит "Прикладная логика" Н.Н.Непейводы, но у неё, с моей точки зрения, есть свои недостатки:
1) вместо деревьев там представлены менее удобные семантические таблицы;
2) представлены не самые удобные формальные описания и доказательства полноты обеих главных систем вывода;
3) много философских и политических утверждений.

Примерное содержание:

0. Язык математики
0.0 Мотивация
0.1 Высказывания
0.2 Предикаты
0.3 Логические связки
0.4 Кванторы
0.5 Равенство
0.6? Определённые описания
1. Основные понятия
1.0 Типы
1.1 Множества
1.2 Функции
1.3 Кортежи
1.4 Списки, последовательности
1.5 Отношения
1.6 Фактор-множества
1.7? Графы
1.8 Формальные языки
(О представлениях этих понятий в теории множеств в главе не говорится)
2. Предварительные сведения
2.0 Индукция и рекурсия (в том числе на деревьях)
2.1-... Столько теории множеств, сколько нужно для следующих глав
3. Логика высказываний
3.0 Синтаксис
3.1 Семантика
3.2 Естественный вывод
3.3 Допустимые правила, правило подстановки
3.4 Корректность и полнота естественного вывода
3.5 Семантические деревья по Смальяну
3.6 Корректность и полнота семантических деревьев
3.7 Улучшенные варианты семантических деревьев
4. Логика предикатов
4.0 Синтаксис
4.1 Семантика
4.2 Естественный вывод
4.3 Корректность и полнота естественного вывода
4.4 Семантические деревья
4.5 Корректность и полнота семантических деревьев
4.6 Предварённая нормальная форма и семантические деревья для неё
4.7 Выше первого порядка (возможно, в отдельную главу?)
5. Аксиоматические теории
5.0 Определения
5.1 Компактность, теоремы Лёвенгейма-Сколема
5.2 Полнота, разрешимость, категоричность теорий
5.3 Арифметика (первого и второго порядка)
5.4 Действительные числа
5.5 Нестандартный анализ
6. Неполнота
6.0 Теорема Тарского
6.1 Первая теорема Гёделя о неполноте
6.2 Вторая теорема Гёделя о неполноте (всё это в теориях строк, а не в арифметике)
6.3 Арифметизация синтаксиса (и перенос предшествующих теорем на арифметику)
7 Вычислимость
7.0 Определение вычислимой функции (не через машины Тьюринга; что-нибудь вроде FLooP Хофштадтера)
7.1 Разрешимые и перечислимые множества
7.2 Массовые задачи
7.3 Неразрешимость задачи об остановке
7.4? Классы сложности
8? Интуиционистская логика и изоморфизм Карри-Ховарда
9? Применения логики в программировании (логика Хоара, equational reasoning и т.д.)

Как вариант, перегруппировать главы 3-4 в "Синтаксис и семантика классической логики", "Семантические деревья" и "Естественный вывод".
Tags: логика, математика
Subscribe

  • Post a new comment

    Error

    Comments allowed for friends only

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 9 comments