Математическая логика (стр. 3 )

Алгебра высказываний.

Логика высказывания. Логические операции над высказываниями. Язык логики высказываний, формулы. Истинностные значения формул. Равносильность. Равносильные преобразования формул. Представление истинностных функций формулами. Тавтологии – законы логики.

Нормальные формы. Совершенные нормальные формы. Теорема существования и единственности совершенных нормальных форма.

Логическое следствие. Прямая и обратная теоремы, противоположная и обратная теоремы; закон контрапозиции. Методы математических доказательств.

Применение алгебры высказываний к описанию релейно-контактных схем. Исчисление высказываний.

Формулы исчисления высказываний. Аксиомы исчисления высказывания и правила вывода. Теорема дедукции и ее применение. Исследования системы аксиом исчисления высказываний; их непротиворечивость и полнота.

Принципы построения исчислений высказываний (гильбертовского или генценовского типа). Классическое и конструктивное (интуиционистское) исчисления. Аксиомы, правила вывода. Доказуемость формул. Выводимость из гипотез. Производные правила. Теорема дедукции. Характеристики исчислений высказываний – непротиворечивость, полнота, разрешимость и связанные с ними теоремы. Независимость аксиом, правил вывода. Законы исключенного третьего и снятия двойного отрицания – законы классической логики. Эффективные и неэффективные доказательства.

Логика предикатов. Формулы логики предикатов и их классификация.

Предикаты и кванторы. Язык логики предикатов. Термы и формулы. Языки первого порядка. Интерпретации. Значение формулы в интерпретации. Равносильность. Общезначимость и выполнимость формул. Проблема общезначимости, неразрешимость ее в общем случае. Применение языка логики предикатов для записи математических предложений, построение отрицаний предложений.

Приведенная форма для формул логики предикатов.

Предваренная нормальная форма.

Проблема разрешения в логике предикатов. Применение логики предикатов. Строение математических теорем. Методы доказательства теорем.

Проблемы оснований математики. Парадоксы теории множеств. Проблема непротиворечивости математики. Программа Гильберта. Метод формализации. Конструктивное направление в математике.

Исчисление предикатов. Непротиворечивость исчисления предикатов. Теорема Геделя о полноте исчисления предикатов.

Формализованные математические теории. Теории первого порядка. Аксиомы теории, правила вывода. Доказательства в теории. Характеристики теорий: непротиворечивость, полнота, разрешимость. Непротиворечивость исчисления предикатов. Модели теорий. Теорема о полноте для теорий. Формальная арифметика. Теоремы Геделя о неполноте. Формализация теории множеств. Обзор результатов о непротиворечивости и независимости в основаниях теории множеств.

7.  Список основной и дополнительной литературы.

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

1.  Игошин логика и теория алгоритмов.- М.: Издательский центр «Академия»; 2004.

2.  Игошин -практикум по математической логике.- М.: Просвещение, 1986.

3.  Введение в математическую логику. – М.: Наука, 1976.

4.  Новиков математической логики.- М.: Наука, 1973.

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

1.  Математическая логика.- М.: Мир, 1973.

2.  , Максимова по теории множеств, математической логике и теории алгоритмов.- М.: Наука, 1975.

3.  Стол . Логика. Аксиоматические теории: Пер. с анг.-М.,1968.

4.  Введение в математическую логику.- М.: Наука,1960.

8. Требования к уровню освоения программы:

В результате изучения данной дисциплины студент должен

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

-знать основные понятия алгебры высказываний (высказывания, определение операций над высказываниями, формулы, логическая равносильность формул, СДНФ, логическое следование); применение алгебры высказываний, виды теорем и методы их доказательств; понятие вывода, свойства выводимости из гипотез, теорему о дедукции, её применение, производные правила вывода, свойства формализованного исчисления высказываний; определение булевых функций, их свойства и применение; основные понятия логики предикатов(предикаты, определения логических и кванторных операций, понятие равносильных предикатов, следование предикатов, понятие интерпретации); понятие формализованного исчисления предикатов, определение разрешимых и перечислимых множеств, теорему Гёделя о неполноте.

-уметь находить значение истинности высказываний, логическое значение формул алгебры высказываний, определить вид формулы, упрощать формулу алгебры высказываний с помощью равносильных преобразований, приводить данную формулу к СКН - форме и СДН- форме; находить следствия формул для данных посылок и наоборот; строить обратное, противоположное и обратное к противоположному утверждение; применять различные методы доказательства теорем; строить выводы в формализованном исчислении высказываний; применять теорему о дедукции; применять булевы функции к релейно-контактным схемам; определять вид предиката; устанавливать равносильность предикатов;

-владеть методами алгебры высказываний, логики предикатов, а также основными методами доказательств и вывода.

Примерный перечень вопросов к экзамену.

1.Высказывания. Операции над ними.

2. Тавтологии. Основные свойства.

3. Отношения логического следования. Свойства

4. . Равносильность формул. Основные равносильности

5. Полные и неполные системы логических связок.

6. Двойственные формулы. Приведенные формулы. Свойства.

7. Теорема двойственности

8. Алгебра Буля.

9. Булевы функции.

10. Классы и теорема Поста (без доказательства.)

11. Элементарная конъюнкция и элементарная дизъюнкция. Свойства

12. Конъюнктивная и дизъюнктивная нормальные формы

13. Полные элементарные конъюнкции и дизъюнкции.

14. Совершенные дизъюнктивные нормальные формы. Алгоритмы построения СДНФ

15. Совершенные конъюнктивные нормальные формы.

Алгоритмы построения СКНФ

16 Приложения совершенных форм.

17. Понятие предиката. Область истинности предиката

18. Язык логики предикатов

19. Связанные и свободные переменные в формулах

20. Интерпретация языка логики предикатов

21. Логически общезначимые формулы

22 Предваренные нормальные формы

23. Проблема разрешения

24. Пример формулы, выполнимой на бесконечном множестве и невыполнимой на конечном множестве

25. Понятие формальной теории._

26. Построение исчисления высказываний. Закон тождества

27. Производные правила вывода

28. Законы двойного отрицания

29. Первый и второй законы контрапозиции

30. Теорема дедукции

31. Законы противоречия

32. Непротиворечивость исчисления высказываний

33. Теорема о выводимости из специальной системы гипотез

34. Полнота исчислений высказываний. Теорема о полноте

35. Независимость аксиом исчисления высказываний. Независимость аксиом, построенных

по схеме А1

36. Независимость аксиом исчисления высказываний. Независимость аксиом,

построенных по схеме А2.

37. Независимость аксиом исчисления высказываний. Независимость аксиом,

построенных по схеме А3 .

38. Понятие о теории первого порядка

39. Модели теории первого порядка

40 Примеры теории первого порядка

41. Простейшие свойства теории первого порядка

42. О теореме дедукции в теориях первого порядка

43. Независимость формулы вывода от данной формулы

44. Теорема дедукции в теориях первого порядка.

45. Следствие теоремы дедукции

46. Теорема о непротиворечивости расширений теории.

47. Геделевская нумерация выражений теории первого порядка

48. Теорема Линденбаума.

9. Сведения о переутверждении программы на определенный учебный год и регистрации изменений по схеме:

Учебный год	Решение кафедры (№ протокола, дата, подпись зав. кафедрой)	Внесенные изменения	Номера листов (страниц)
замененных	новых	аннулированных

Учебная программа составлена на основании ГОС ВПО 2005 г. для специальности

050201 Математика с дополнительной специальностью

Программу составил(и):

1., канд. физ. мат. наук., доцент_________

Ф. И.О., ученая степень, ученое звание

2.____________________________________________________________________________

Ф. И.О., ученая степень, ученое звание

Настоящая программа не может быть воспроизведена ни в какой форме без предварительного письменного разрешения кафедры-разработчика программы.

Программа одобрена на заседании кафедры

алгебры 2 марта 2007_г., протокол ___________________________________­­­­­­­­­­­­­­­­­­­_________

наименование кафедры, дата заседания и номер протокола

Заведующий кафедрой

______________алгебры_______ _____________ ____ _________

наименование кафедры подпись Ф. И. О.

Программа одобрена учебно-методическим советом факультета

«____» _____________2007 г.

Председатель учебно-методического совета_______________ _____________

подпись Ф. И. О.

Программа одобрена учебно-методическим управлением университета

«____» _____________200 г.

Начальник учебно-методического управления _____________ ___________

подпись Ф. И. О.

ЛИСТ РЕГИСТРАЦИИ ИЗМЕНЕНИЙ

Изме-нение	Номера листов (стр.)	Всего листов (стр.) в документе	Номера распоря-дительного документа	Подпись	Дата	Срок введения изменений
заменен-ных	новых	аннули-рованных