Задачи к зачету по математической логике.
Вопросы к экзамену по математической логике 2012 ПГУ КМБ-ИТЕ
1. История математической логики. Аристотелевская силлогистика.
2. Формальная логика. Понятие. Суждение. Умозаключение.
3. Доказательство правильности силлогизмов с помощью диаграмм Эйлера.
4. Синтаксис логики высказываний. Формализация высказываний и формулы логики высказываний.
5. Алгебра высказываний. Законы алгебры логики.
6. Равносильные преобразования в логике высказываний.
7. Преобразование форм представления формул в логике высказываний.
8. Разложение Шеннона.
9. Определение свойств переключательных функций – ПФ (логических функций -ЛФ).
10. Теорема о функциональной полноте двоичных ПФ.
11. Основные понятия по минимизации переключательных (логических) функций. Минимизация методом неопределённых коэффициентов.
12. Минимизация переключательных (логических) функций методом Квайна – Мак Класки.
13. Минимизация переключательных (логических) функций методом карт Карно.
14. Минимизация переключательных (логических) функций методом поразрядного сравнения. Метод Л.Ф.Викентьева.
15. Особенности системной минимизации ЛФ (ПФ).
16. Минимизация переключательных (логических) функций в базисе «Сумма по модулю два, И, НЕ».
17. Понятие об автомате и его математическом описании. Синтез элементарного автомата памяти типа RS триггера.
18. Синтез логического преобразователя комбинационного автомата. Представление логического преобразователя в разных базисах. Метод каскадов.
19. Синтез логического преобразователя последовательностного автомата с детерминированной входной последовательностью. Эквивалентные такты.
20. Синтез логического преобразователя последовательностного автомата с недетерминированной входной последовательностью.
21. Получение контрольного теста логического преобразователя автомата.
22. Получение диагностического теста логического преобразователя автомата.
23. Полином Жегалкина-ПЖ..
24. Булева производная-БП. Использование БП для получения тестов логического преобразователя.
25. Закон контрапозиции. Необходимые и достаточные условия.
26. Условные силлогизмы. Аргументы.
27. Модус поненс и модус толленс.
28. Проверка правильности логических выводов.
29. Получение следствий из данных посылок.
30. Метод резолюций в логике высказываний.
31. Синтаксис логики предикатов первого порядка. Кванторы. Свободные и связанные переменные.
32. Тождественные преобразования формул логики предикатов.
33. Универсум Эрбрана. Семантическое дерево.
34. Подстановки и унификация. Резольвенция и факторизация.
35. Принцип резолюции в логике предикатов.
36. Принцип логического программирования. Язык ПРОЛОГ.
37. Понятие о формальных теориях и формальных системах. Теоремы Гёделя.
38. Исчисление высказываний
39. Исчисление предикатов.
40. Доказательство в смысле Гильберта и в смысле Генцена.
41. Понятие о математической лингвистике. Формальный язык. Кодирование цепочек.
42. Формальные грамматики и их свойства. Классификация формальных грамматик.
43. Алгоритм и его свойства. Схемы алгоритмов.
44. Понятие о рекурсивных функциях и нормальных алгорифмах Маркова.
45. Машина Тьюринга.
46. Машина Поста.
47. Универсальная абстрактная машина и проблема самоприменимости в теории алгоритмов.
48. Задачи теории алгоритмов. Сложность алгоритмов: P,NP,NP полнота.
49. Получение по схеме алгоритма графа эквивалентного автомата на «жёсткой» логике.
50. Получение по схеме алгоритма эквивалентного автомата на «гибкой» логике-ПЗУ
51. Получение по схеме алгоритма эквивалентного автомата на «гибкой» логике-ПЗУ+MS.
52. Получение по ГСА микропрограммы с двумя типами микрокоманд.
53. Современные модальные логики.
54. Понятие о нечеткой логике. Нечёткая логика в системе МАТЛАБ.
55. Функции К-значной логики и функциональная полнота многозначных ПФ.
56. Понятие о логическом программировании на языке Пролог.
57. Арифметизация булевых функций.
58. Псевдобулевы функции. Арифметизация ПБФ.
59. Представление булевой и псевдобулевой функции рядом Фурье.
60. Матрица Адамара. Спектральные коэффициенты БФ и ПБФ.
Задачи к зачету по математической логике.
1. Доказать или опровергнуть общезначимость формулы, используя законы алгебры логики и формулы равносильных преобразований, а также путем построения дерева доказательства.
2. Формализовать высказывание. Получить СДНФ, СКНФ, ДНФ, КНФ, ПЖ. Представить высказывание в виде суперпозиции только следующих операций 1) «Штрих Шеффера», 3) «Стрелка Пирса», 3)»Импликация» и «Отрицание», 4) «Импликация» и «Константа нуля»(«0»). Получить разложение Шеннона.
3. Проверить аргумент методом резолюций. Получить все следствия из данных посылок.
4. Определить свойства ПФ.
5. Выполнить минимизацию ПФ заданным методом.
6. Синтез ЛП комбинационного автомата.
7. Синтез ЛП последовательностного автомата-распознавателя.
8. Упростить заданную формулу по законам алгебры логики и формулам равносильных преобразований.
9. Написать программу на языке ПРОЛОГ-Д для определения отношения родства. Построить модифицированное дерево.
10. Получить булеву производную.
11. Получить полином Жегалкина.
12. Получить по ГСА эквивалентный автомат на «жёсткой» логике.
13. Получить по ГСА эквивалентный автомат на «гибкой» логике.
14. Получить цепочку формального языка по ее номеру, получить номер цепочки в заданном алфавите.
15. Проверить правильность умозаключения Аристотелевской силлогистики с помощью кругов Эйлера и в логике предикатов.
16. Получить машину Тьюринга для вычисления переключательной функции.
17. Получить машину Тьюринга для распознавания последовательности.
18. Получить машину Поста для вычисления переключательной функции.
19. Получить по ГСА микропрограмму с двумя типами микрокоманд.
20. Выполнить арифметизацию ПФ (ЛФ).
21. Представить ПФ (ЛФ) рядом Фурье.
Литература.
1.Аляев Ю.А. Тюрин С.Ф. Дискретная математика и математическая логика. – М.: Финансы и статистика, 2006. – 357 с.
2.С.Ф.Тюрин. Аляев Ю.А. Практическая дискретная математика и математическая логика – М.: Финансы и статистика, 2010. – 384 с.
3.Тюрин С.Ф. Дискретная математика и математическая логика. – Пермь, ПГТУ, 2009. – 52 с.