@blackhawkjkee

Здравствуйте.
Мне нужна помощь с поиском теоретического материала по экзаменационным вопросам, которые трактуются следующим образом:

1. Выводимость из посылок.
Теорема о совпадении понятий синтаксической выводимости и семантического следования.
Корректность и полнота при выводимости из посылок.
2. Функциональная сложность.
Оптимальные по порядку сложности алгоритмы

Оранжевым выделил то, что еще немного нагуглил, но информации как-то мало и подана она очень неудобно для восприятия. Красным - те вопросы, по которым фактически нет никакой информации(либо она сильно завуалирована/скрыта)
Может в свободном доступе есть какие-либо учебники где данные вопросы в более подробной форме разбираются?

0

@Ellipsoid

Посмотрите:
1) Гладкий, Математическая логика;
2) Верещагин, Шень, Лекции по математической логике (название точно не помню).
Не знаю, есть ли там, но гляньте на всякий случай.

0

@BananaG

Если теория Т корректна и полна, то (Т ├ φ) ↔ (Т ╞ φ), где Т ├ φ означает синтаксическую выводимость.

0

@3D Homer

По первой части вам нужны теоремы о корректности и полноте исчисления высказываний или предикатов (второе сложнее). Посмотрите сам источник и литературу в http://lpcs.math.msu.su/~pentus/vmlw.htm, особенно

Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления
Успенский В. А., Верещагин Н. К., Плиско В. Е. Вводный курс математической логики.
Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов.

Нужно сказать, что исчислений (аксиом и правил вывода) для пропозициональной логики много, и рассматриваемые в этих источниках исчисление Гильберта является хотя и популярным, но далеко не единственным вариантом. В Лавров, Максимова описывается также наруральный вывод в виде исчисления секвенций. Вам нужно бы узнать, какое исчисление рассматривалось у вас в курсе.

0