Исчисления высказываний классической логики (курс лекций, С.И. Гуров)

Материал из MachineLearning.

Версия от 14:00, 31 августа 2011; Kropotov (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Содержание

Аннотация

Рассмотрены основные понятия пропозициональной логики. Даются методы характеризации формул алгебры логики, в частности, метод резолюций и метод семантических таблиц. Изучаются логические исчисления гильбертовского и генценовского типов и общие свойства формальных теорий. Рассматриваются свойства метатеории логических исчислений: корректность и непротиворечивость, семантическая полнота, полнота по Посту, разрешимость и независимость. Длительность курса 32 часа.

Автор курса: доц. каф. ММП, к.ф.-м.н. Гуров Сергей Исаевич.

Содержание курса

Классическая алгебра логики. Алгебра высказываний. Формальная логика. Высказывания и их оценки. Высказывания простые и сложные. Парадоксы материальной импликации. Двоичная алгебра высказываний. Оператор замыкания и его свойства. Язык функций и язык формул.

Бинарные отношения на множестве формул. Типы формул алгебры логики. Тавтологии. Примеры классических логических законов. Логическая эквивалентность (равносильность). Теорема о подстановке вместо пропозициональных переменных. Теорема о замене эквивалентных. Фактор-алгебра логических формул. Логическое следование. Семантическая противоречивость и выполнимость множества формул. Примеры логических правил.

Характеризация формул алгебры высказываний. Проблема характеризации формул. Метод истинностных таблиц. Метод приведения к нормальным формам. Метод редукции. Метод семантических таблиц. Метод резолюций.

Исчисление высказываний. Гильбертовские исчисления. Логические исчисления. Алфавит, выражения, формулы исчисления. Аксиомы и теоремы. Вывод в исчислениях. Синтаксис и семантика. Метаязык и метатеория. О теории доказательств.

Исчисление высказываний (ИВ) H . Гильбертовские исчисления. Исчисление высказываний H. Основные и производные свойства выводимости. Метатеорема о дедукции. Дедуктивная эквивалентность.

Метатеория ИВ H . Семантическая пригодность и непротиворечивость исчисления H. Семантическая полнота и полнота по Посту исчисления H. Алгебра Линденбаума-Тарского L*. Ультрафильтры L*. Независимость системы аксиом исчисления H.

Исчисление высказываний H^{\prime},\ H_1. Описание ИВ H^{\prime},\ H_1 и их свойства.

Типы логических исчислений и их представления. ИВ гильбертовского типа. Выводимость как оператор замыкания.

Генценовские исчисления высказываний. Исчисление N натурального типа. Исчисления секвенций (ИС) натурального типа. Доказательство в идее дерева. Допустимые правила. Основные свойства ИС N. Метатеория ИС N.

Исчисление S секвенциального типа. Определение ИС S. Свойство под-формульности правил вывода. Свойства ИС S и поиск доказательств. Допустимость сечения. Эквивалентность ИС S и ИВ H_1.

Литература

Основная литература

  1. Бет Э.В. Метод семантических таблиц // Математическая теория логиче-ского вывода / Сб. перев. под ред. А.В. Идельсона и Г.Е. Минца. М.: Наука. 1967. C. 191-199.
  2. Верещагин В.Н., Шень А. Лекции по математической логике и теории ал-горитмов. Часть II. Языки и исчисления. М.: МЦНМО. 2000.
  3. Гладкий А.В. Математическая логика. М.: РГГУ. 1998.
  4. Гуров С.И. Исчисления высказываний классической логики: Учебно-методическое пособие. М.: МАКС Пресс. 2007.
  5. Ершов Ю.Л., Палютин Е.А. Mатематическая логика: Учеб. пособие для ву-зов. М.: Наука. 1987 (и следующие издания).
  6. Клини С.К. Математическая логика. М.: Мир. 1973.
  7. Колмогоров А.Н., Драгалин А.Г. Введение в математическую логику. Ма-тематическая логика. Дополнительные главы. М.: МГУ. 2005.
  8. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: 1975.
  9. Мендельсон Э. Введение в математическую логику: Пер. с англ. /Под ред. С.И. Адяна. М.: Наука. 1984.
  10. Непейвода Н.Н. Прикладная логика: Учебное пособие. Новосибирск: Изд-во Новосибир. ун-та. 2000.
  11. Столл Р. Множества. Логика. Аксиоматические теории / Пер. с англ. Ю.А. Гастева и И.Х. Шмаина. Под. ред. Ю.А. Шихановича. М.: Просвещение. 1968.

Дополнительная литература

  1. Гуров С.И. Упорядоченные множества и универсальная алгебра (вводный курс). М.: ВМК МГУ. 2004.
  2. Карпенко А.С. Логика на рубеже тысячелетий // Логические исследования. Вып. 7. М.: Наука. 2000. С. 7-60.
  3. Математическая теория логического вывода / Сб. перев. под ред. А.В. Идельсона и Г.Е. Минца. М.: Наука. 1967.
  4. Чёрч А. Введение в математическую логику. Т. 1. М.: ИЛ. 1961.
  5. Судоплатов С.В., Овчинникова Е.В. Математическая логика и теория алго-ритмов: Учебник. М.: ИНФРА-М. Новосибирск: Изд-во НТГУ. 2004.
  6. Шенфилд Дж. Математическая логика. М.: Наука. 1975.
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%98%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F_%D0%B2%D1%8B%D1%81%D0%BA%D0%B0%D0%B7%D1%8B%D0%B2%D0%B0%D0%BD%D0%B8%D0%B9_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B9_%D0%BB%D0%BE%D0%B3%D0%B8%D0%BA%D0%B8_%28%D0%BA%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9%2C_%D0%A1.%D0%98._%D0%93%D1%83%D1%80%D0%BE%D0%B2%29»
Личные инструменты