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

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

Логика и интуиция. Истинное и ложное высказывания. Логические операции: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность. Союзы языка и логические операции. Сложные высказывания. Понятие формулы алгебры высказываний. Логическое значение составного высказывания.

Таблица истинности и методика ее построения. Классификация формул алгебры высказываний.

Законы алгебры логики. Основные правила получения тавтологий. Логическая равносильность формул. Примеры равносильных формул. Равносильные преобразования формул. Равносильность в логике и тождества в алгебре.

Понятие нормальной формы. Понятие совершенных дизъюнктивной и конъюнктивной нормальных форм. Основные способы представления формул в совершенных нормальных формах.

Логическое следование формул. Понятие логического следствия. Признаки и свойства логического следствия. Следование и равносильность формул. Правила логических умозаключений. Нахождение следствий из данных посылок. Нахождение посылок для данного следствия.

Приложения алгебры высказываний к логико-матема­тической практике. Прямая и обратная теоремы. Необходимое и достаточное условия. Противоположная и обратная противоположной теоремы. Закон контрапозиции. Методы доказательства математических теорем. Дедуктивные и индуктивные умозаключения. Решение «логических задач».

Тема 2. Булевы функции

Понятие множества. Включение и равенство множеств. Операции над множествами: объединение, пересечение, дополнение (разность). Абсолютное дополнение. Бинарные отношения и функции.

Понятие n-арного отношения. Понятие булевой функции одного аргумента. Булевы функции от двух аргументов. Выражение одних булевых функций через другие. Булевы функции от n аргументов. Число булевых функций. Выражение булевых функций через конъюнкцию, дизъюнкцию, отрицание.

Булевы функции и формулы алгебры высказываний. Нормальные формы булевых функций. Системы булевых функций. Теорема Поста о полноте системы булевых функций. Применение булевых функций к релейно-контактным схемам. Двоичный полусумматор. Одноразрядный двоичный сумматор. Шифратор и дешифратор.

Тема 3. Формализованное исчисление высказываний

Система аксиом и теория формального вывода. Теорема о дедукции и ее следствия. Применение теоремы о дедукции. Производные правила вывода.

Доказуемость формулы и ее тождественная истинность (синтаксис и семантика). Лемма о выводимости. Полнота и непротиворечивость формализованного исчисления высказываний.

Тема 4. Логика предикатов

Понятие предиката. Классификация предикатов. Множество истинности предиката. Равносильность и следование предикатов. Логические операции над предикатами. Кванторные операции над предикатами. Численные кванторы. Ограниченные кванторы. Логический квадрат.

Понятие формулы логики предикатов. Классификация фор­мул логики предикатов. Тавтологии логики предикатов.

Применение логики предикатов к логико-математи­ческой практике. Сравнение логики предикатов и логики высказываний. Строение математических теорем.

Тема 5. Неформальные аксиоматические теории

Понятие аксиоматической теории. Примеры аксиоматических теорий. Интерпретации и модели аксиоматической теории. Свойства аксиоматических теорий.

Тема 6. Формальные аксиоматические теории

История идеи формальной аксиоматической теории. Понятие формальной аксиоматической теории.

Язык и метаязык, теоремы и метатеоремы формальной теории. Интерпретации и модели формальной теории. Семантическая выводимость. Свойства формальных аксиоматических теорий.

Формализованное исчисление высказываний как формальная аксиоматическая теория. Теорема Гёделя о существовании модели. Полнота и адекватность формализованного исчисления предикатов.

.

4. МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

4.1. Планы семинарских занятий

Не предусмотрены.

4.2. Практические занятия

Математическая логика [Текст] : методические указания и задания к практическим занятиям для студентов направления 230700.62 Прикладная информатика профиль «Прикладная информатика в информационной сфере». – Чита : ЗИП СибУПК, 201 .

4.3. Лабораторные занятия

Математическая логика [Текст] : методические указания и задания к лабораторным работам для студентов направления 230700.62 Прикладная информатика профиль «Прикладная информатика в информационной сфере». – Чита : ЗИП СибУПК, 201 .

4.4. Задания контрольной работы

для студентов заочной формы обучения

Математическая логика [Текст] : методические указания и задания к выполнению контрольных работ для студентов направления 230700.62 Прикладная информатика профиль «Прикладная информатика в информационной сфере». – Чита : ЗИП СибУПК, 201 .

4.5. Курсовая работа (проект)

Не предусмотрена.

4.6. Тематика рефератов

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. Формальные теории числовых систем.

5. СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ

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

1. Гринченков, Д. В. Математическая логика и теория алгоритмов для программистов [Текст] : учебник для вузов / , . – М. : КноРус, 2010. – 208 с.

2. Ершов, Ю. Л. Математическая логика [Текст] : учебное пособие / , . – М. : ФИЗМАТЛИТ, 2010. – 356 с.

3. Игошин, В. И. Математическая логика [Текст] : учебник для вузов / – М. : Инфра-М, 2012. – 400 с.

5.2. Нормативные документы

Нет.

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

4. Аляев, Ю. А. Дискретная математика и математическая логика [Текст] : учебное пособие / , – М. : Финансы и статистика, 2008. – 368 с.

5. Колмогоров, А. Н. Математическая логика [Текст] : учебное пособие / А. Н Колмогоров, – М. : КомКнига, 2009. –240 с.

6. Триумфгородских, М. В. Дискретная математика и математическая логика для информатиков, экономистов и менеджеров, [Текст] : учебное пособие / . – М. : Диалог-МИФИ, 2011. – 184 с.

7. Хаггард, Г. Дискретная математика для программистов [Текст] : учебное пособие / Г. Хаггард, Дж. Шлипф, С. Уайтсайдс. – М. : Бином. Лаборатория знаний, 2010. – 632 с.

8. Эвнин, А. Ю. Задачник по дискретной математике, [Текст] : учебное пособие / . – М. : Либроком, 2011. – 264 с.

6. ИНФОРМАЦИОННОЕ И ПРОГРАММНОЕ

ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

6.1. Перечень обучающих, контролирующих

и расчетных компьютерных программ

− контролирующая компьютерная программа VinEx306b.

6.2. Перечень кино-, видео-, телефильмов

Нет.

6.3. Перечень интернет-ресурсов

− http://matembook.chat.ru;

− http://mech.math.msu.su;

− ­http://computer-science.hotmail.ru;

− ­http://mathnet. *****;

− ­http://www. mapler. *****;

− ­http://www. helen. .

7. МАТЕРИАЛЬНОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

Для изучения дисциплины используются лекционная аудитория, оснащенная мультимедийным оборудованием и компьютерные классы.

8. САМОСТОЯТЕЛЬНАЯ РАБОТА

№ п/п	Темы дисциплины	Источники, рекомендуемые для самостоятельной работы
1.	Тема 1. Алгебра высказываний	1 – 8
2.	Тема 2. Булевы функции	1 – 8
3.	Тема 3. Формализованное исчисление высказываний	1 – 8
4.	Тема 4. Логика предикатов	1 – 8
5.	Тема 5. Неформальные аксиоматические теории	1 – 8
6.	Тема 6. Формальные аксиоматические теории	1 – 8

9. ПРИМЕРНЫЙ ПЕРЕЧЕНЬ ЗАДАНИЙ

ПО ВИДАМ КОНТРОЛЯ

9.1. Итоговый контроль

Итоговый контроль осуществляется в форме экзамена.

Вопросы к экзамену

1. Бинарные отношения и функции.

2. Булевы функции от n аргументов. Число булевых функций.

3. Булевы функции от двух аргументов.

4. Двоичный полусумматор.

5. Доказуемость формулы и ее тождественная истинность (синтаксис и семантика).

6. Закон контрапозиции.

7. Законы алгебры логики.

8. Интерпретации и модели формальной теории.

9. Истинное и ложное высказывания.

10. Кванторные операции над предикатами.

11. Классификация формул алгебры высказываний.

12. Лемма о выводимости.

13. Логические операции над высказываниями: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность.

14. Логические операции над предикатами.

15. Методы доказательства математических теорем. Дедуктивные и индуктивные умозаключения.

16. Одноразрядный двоичный сумматор.

17. Операции над множествами: объединение, пересечение, дополнение (разность). Абсолютное дополнение.

18. Полнота и непротиворечивость формализованного исчисления высказываний.

19. Понятие n-арного отношения.

20. Понятие аксиоматической теории. Примеры аксиоматических теорий.

21. Понятие булевой функции одного аргумента.

22. Понятие логического следствия.

23. Понятие множества. Включение и равенство множеств.

24. Понятие нормальной формы.

25. Понятие предиката. Классификация предикатов.

26. Понятие совершенных дизъюнктивной и конъюнктивной нормальных форм.

27. Понятие формулы логики предикатов. Классификация формул логики предикатов.

28. Приложения алгебры высказываний к логико-математической практике. Прямая и обратная теоремы. Необходимое и достаточное условия.

29. Применение булевых функций к релейно-контактным схемам.

30. Применение логики предикатов к логико-математической практике.

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

32. Система аксиом и теория формального вывода

33. Сложные высказывания. Понятие формулы алгебры высказываний.

34. Сравнение логики предикатов и логики высказываний.

35. Тавтологии логики предикатов.

36. Теорема о дедукции и ее следствия. Применение теоремы о дедукции.

37. Теорема Поста о полноте системы булевых функций.

38. Шифратор и дешифратор.

9.2. Промежуточный контроль

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

ТЕСТ

1. Высказыванием называется:

а) любое математическое выражение;

б) предложение, о котором можно сказать истинно оно или ложно;

в) любой набор слов;

г) любая символьная запись.

2. Х и У – высказывания, тогда запись означает:

а) ассоциативность дизъюнкции;

б) идемпотентность конъюнкции;

в) закон де Моргана;

г) коммутативность дизъюнкции.

3. Элементарные дизъюнктивные одночлены в совершенной конъюнктивной нормальной форме функции связаны в виде:

а) дизъюнкции;

б) конъюнкции;

в) импликации;

г) эквивалентности.

4. Элементарной дизъюнкцией называется дизъюнкция любого числа булевых переменных, взятых с отрицанием или без него, в которой каждая переменная встречается …

а) точно один раз;

б) не более одного раза;

в) не менее одного раза;

г) n раз.

5. Операция объединение множеств определяется как …

а) ;

б) ;

в) ;

г) .

6. Основоположником математической теории множеств является …

а) Андрей Колмогоров;

б) Георг Кантор;

в) Джон Венн;

г) Леонард Эйлер.

7. Символ включения имеет вид….

а) ;

б) ;

в) ;

г) .

8. Множество, не содержащее ни одного элемента, называется …

а) свободным;

б) пустым;

в) каре;

г) порожним.

9. Дана таблица истинности для булевой функции:

Х	У	F
0	0	0
0	1	1
1	0	1
1	1	0

Это функция называется …

а) стрелкой Пирса;

б) штрихом Шеффера;

в) суммой по модулю два;

г) тавтологией.

10. Количество всех возможных булевых функций четырех переменных равно …

а) 8;

б) 16;

в) 32;

г) 64.

СОГЛАСОВАНО

Начальник учебно-методического отдела

___________________________

«____» _____________________ 2012 г.

И. о. зав. кафедрой прикладной информатики

___________________________

«____» _______________________ 2012 г.