Лекции
по математической логике
МИЭМ, ФЭ, 2 курс, 3 семестр
Осенний семестр 2009/2010 учебного года
Группы К-31, 32
Лектор – доцент, к. ф.-м. н.
Вопросы к теоретическому зачёту
Глава 1. Булевы функции
§ 1.1. Основные понятия
1.1.1. Декартово произведение
Дать определения декартова произведения двух множеств, декартова квадрата произвольного множества. Привести примеры. Записать формулы, выражающие число элементов декартова произведения и декартова квадрата.
1.1.2. Декартова степень
Дать определение декартовой степени произвольного множества. Привести пример. Записать формулу, выражающую число элементов декартовой степени.
1.1.4. Определение булевой функции
Дать определение булевой функции от n переменных; привести примеры.
Выписать таблицы истинности для следующих булевых функций: отрицание, дизъюнкция, конъюнкция, импликация, сложение modulo 2, эквивалентность.
§ 1.2. Свойства булевых функций
Сформулировать основные тождества, выполняющиеся для булевых функций. Доказать какие-нибудь два из них.
§ 1.3. Дизъюнктивные нормальные формы (ДНФ)
1.3.1. Экспоненциальные обозначения в конъюнкциях
Дать определение элементарной конъюнкции от данных переменных. Рассказать об экспоненциальных обозначениях в конъюнкциях.
1.3.2. Лемма о равенстве двух булевых функций
Доказать лемму о равенстве двух булевых функций.
1.3.3. Теорема о совершенной ДНФ
Доказать теорему о совершенной ДНФ (в предположении, что лемма уже доказана). Сформулировать и объяснить следствие из этой теоремы.
1.3.4. Определение ДНФ
Дать определения дизъюнктивной нормальной формы (ДНФ) и её длины. Доказать, что любая ненулевая булева функция обладает разложением в ДНФ.
Глава 2. Логические исчисления
§ 2.1. Определение исчисления высказываний (ИВ)
2.1.1. Язык ИВ
Изложить определение языка исчисления высказываний (ИВ): определения алфавита, слова, формативной последовательности, формулы.
2.1.2. Аксиомы ИВ
Привести список 11 аксиом исчисления высказываний. Показать (на примере одной из них), что все они являются формулами ИВ.
2.1.3. Правила вывода
Дать определение подстановки в слово. Привести пример. Сформулировать предложение о подстановке в формулу. Дать определения правил вывода ИВ (правил подстановки и правила modus ponens).
§ 2.2. Формальные выводы
2.2.1. Определение формального вывода в ИВ
Дать определения формального вывода в исчислении высказываний и выводимой формулы. Сформулировать правило одновременной подстановки.
2.2.2. Пример формального вывода в ИВ
Привести (с обоснованием) пример формального вывода в ИВ (доказать выводимость формулы (A ® A)).
2.2.3. Формальный вывод из гипотез
Дать определение формального вывода из гипотез (в ИВ). Дать определение формулы, выводимой из данного списка гипотез.
2.2.4. Пример формального вывода из гипотез
Привести пример формального вывода из гипотез.
§ 2.3. Теорема дедукции
2.3.1. Лемма к теореме дедукции
Сформулировать и доказать лемму к теореме дедукции.
2.3.2. Формулировка теоремы дедукции
Сформулировать теорему дедукции. Доказать теорему, обратную к теореме дедукции.
2.3.3. Доказательство теоремы дедукции в частных случаях
Доказать теорему дедукции в трёх частных случаях.
2.3.4. Доказательство теоремы в общем случае
Доказать теорему дедукции в общем случае (в предположении, что она уже доказана в трёх частных случаях).
§ 2.4. Критерий выводимости
2.4.1. Понятие интерпретации формулы
Дать определение интерпретации формулы ИВ (во множестве булевых функций).
2.4.2. Формулировка критерия выводимости
Сформулировать критерий выводимости в ИВ.
2.4.3. Доказательство теоремы в одну сторону
Сформулировать и частично доказать критерий выводимости в ИВ.
§ 2.5. Непротиворечивость ИВ
2.5.1. Определение противоречивости
Объяснить, как может быть определено понятие противоречивости ИВ (три варианта определения).
2.5.2. Доказательство непротиворечивости ИВ
Доказать, что ИВ является непротиворечивым по любому из трёх вариантов определения противоречивости.
§ 2.6. Исчисление предикатов
2.6.1. Определение предиката
Дать определение n-местного предиката. Привести примеры.
2.6.2. Кванторы
Объяснить понятие квантора. Привести примеры.
2.6.2. Свободные и связанные переменные в математике
Объяснить (на примерах) различие между свободными и связанными переменными в математике.
2.6.4. Язык исчисления предикатов (первого порядка)
Рассказать о языке (исчисления предикатов) первого порядка.
2.6.5. Примеры сигнатур в математике
Привести примеры сигнатур.
Сформулировать аксиомы арифметики G. Peano.
2.6.6. Понятия терма и формулы
Дать определения терма и формулы для языков первого порядка.
2.6.7. Пронесение отрицания через кванторы
Записать формулы пронесения отрицания через кванторы.
2.6.8. Пример из математического анализа
Объяснить (на примере из математического анализа) невозможность перестановки кванторов в общем случае.
Глава 3. Теория алгорифмов (07.11.09)
§ 3.1. Понятие вычислимой функции
3.1.1. Машина с неограниченными регистрами (МНР)
Дать определение машины с неограниченными регистрами (МНР), определение программы для такой машины.
3.1.2. Вычисление функций на МНР
Рассказать о реализации функций натурального аргумента на МНР.
Дать определение (частичной) вычислимой функции натурального аргумента. Объ - яснить связь с понятием последовательности натуральных чисел (возможно, лакунарной).
3.1.3. Пример невычислимой функции
Привести (с обоснованием) пример невычислимой функции.
§ 3.2. Счётные и несчётные множества (14.11.09)
3.2.1. Определение счётного множества
Дать определение счётного множества. Привести примеры счётных множеств. Доказать, что подмножество счётного множества не более чем счётно.
3.2.2. Пример несчётного множества
Доказать, что множество всевозможных бесконечных последовательностей нату-ральных чисел несчётно (теорема G. Cantor’а).
3.2.3. Несчётность множества всех действительных чисел
Доказать, что множество всех действительных чисел несчётно (теорема G. Cantor’а).
3.2.4. Счётность множества всех вычислимых функций (21.11.09)
Доказать, что множество всех вычислимых функций счётно.
3.2.5. Существование невычислимой функции
Доказать существование невычислимой функции.
§ 3.3. Нумерация программ
3.3.1. Нумерация N2 и N3
Рассказать о нумерации N2 и N3.
3.3.2. Нумерация команд
Рассказать о нумерации команд для МНР.
3.3.3. Нумерация программ
Рассказать о нумерации программ для МНР. Объяснить, почему её можно рассмат - ривать как вычислимую функцию.
§ 3.4. Универсальные функции (28.11.09)
Дать определение функции, универсальной для данного класса (множества) функций (натурального аргумента). Доказать, что универсальная функция существует тогда и только тогда, когда данный класс счётен. Доказать существование универсальной вычислимой функции.
Доказать, что функция, универсальная в классе всех вычислимых всюду определённых функций, не является вычислимой.
Доказать, что универсальная вычислимая функция не может быть продолжена до всюду определённой вычислимой функции. (05.12.09.)
§ 3.5. Определение алгорифма
3.5.1. Понятие алгорифма
Сформулировать понятие алгорифма.
Сформулировать тезис Church’а.
3.5.2. Невозможность некоторых алгорифмов
Доказать, что не существует алгорифма, который определял бы по произвольной паре натуральных чисел, входит ли она в область определения универсальной вычислимой функции или нет.
Доказать, что не существует алгорифма проверки корректности программы.
Рассказать о проверке программы на наличие вируса.
