Рассмотрено и утверждено

на заседании кафедры математики, ТиМОМ

протокол от 01.01.2001 г.

зав. кафедрой _________________

Вопросы к экзамену по дисциплине «Математическая логика»

4 курс, направление подготовки 050200.62 «Физико-математическое образование»

профиль «Информатика»

8 семестр, уч. г., ОДО

Составитель: к. ф.-м. н., доц.

1.  Понятие высказывания. Основные логические операции над высказываниями. Примеры. Язык исчисления высказываний.

2.  Формулы алгебры высказываний. Таблицы истинности. Тождественно истинные, тождественно ложные и выполнимые формулы. Примеры.

3.  Равносильные формулы. Равносильные преобразования формул. Упрощение формул. Примеры.

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

5.  Конъюнктивная и дизъюнктивная нормальные формы. Примеры. Теорема о СДНФ и СКНФ.

6.  Применение исчисления высказываний к разработке РКС и СБИС. Примеры.

7.  Логическое следование. Критерий логического следования. Теорема о дедукции. Примеры.

8.  Строение математических теорий. Виды теорем: прямая, обратная, противоположная, контрапозиционная. Методы доказательства теорем. Условия необходимые, достаточные, необходимые и достаточные.

9.  Предикаты. Области истинности и ложности предикатов. Примеры.

10.  Основные логические операции над предикатами. Лемма об областях истинности. Примеры.

11.  Кванторы. Истинные и ложные высказывания с кванторами. Примеры.

12.  Равносильные предикаты. Основные равносильности с кванторами. Примеры.

13.  Язык исчисления предикатов и формулы исчисления предикатов. Примеры.

14.  Интерпретации формул исчисления предикатов. Тождественно истинные (общезначимые), тождественно ложные (противоречия) и выполнимые формулы. Примеры.

15.  Приведённая предваренная нормальная форма (ППНФ). Теорема о приведении формулы исчисления предикатов к ППНФ.

16.  Содержательный и формальный аксиоматический методы. Построение формальных теорий исчисления высказываний (ИВ) и исчисления предикатов (ИП). Примеры доказательств теорем в ИВ и ИП.

17.  Проблемы непротиворечивости, полноты и разрешимости для ИВ и ИП.

ТРЕБОВАНИЯ К ОТВЕТУ

Для получения оценки “удовлетворительно” необходимо знать основные определения и формулировки теорем (по всему курсу), уметь приводить примеры и решать стандартные задачи.

Для получения оценки “хорошо” нужно, в дополнение к вышеизложенному, уметь доказывать основные результаты билета. Для получения оценки “отлично” нужно, кроме прочего, доказать все теоретические результаты билета.

ЛИТЕРАТУРА

1.  Лекции И ПРАКТИКА

2.  е-ЛЕКЦИИ

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

4.  Игошин логика и теория алгоритмов. – М.: Издательский центр “Академия”, 2004.