Вопросы по ДискМат - 2023-24-1
.pdfВопросы для подготовки к экзамену по дисциплине «Дискретная математика и математическая логика»
Раздел 1. Теория булевых функций.
1.Определение булевой функции (БФ). Количество БФ от n переменных. Таблица истинности БФ.
2.Булевы функции одной и двух переменных (их таблицы, названия). Логические связки и х таблицы истинности.
3.Формулы логики высказываний. Представление БФ формулами.
4.Тождественно истинные (ложные) и выполнимые БФ.
5.Эквивалентные формулы. Основные эквивалентности теории булевых функций.
6.Двойственные булевы функции. Двойственные формулы. Принцип двойственности.
7.ДНФ и КНФ, алгоритмы приведения.
8.СДНФ и СКНФ, теоремы существования и единственности, алгоритмы приведения.
9.Минимальная ДНФ. Алгоритмы минимизации (карты Карно).
10.Полином Жегалкина, его существование и единственность. Алгоритм построения.
11.Суперпозиция булевых функций. Замкнутые классы булевых функций.
12.Полные системы булевых функций, базисы.
13.Классы T0, T1 (функции, сохраняющие 0 и 1).
14.Класс S самодвойственных функций, определение двойственной БФ.
15.Класс монотонных функций.
16.Класс линейных функций.
17.Леммы о несамодвойственной, немонотонной, нелинейной функциях.
18.Теорема Поста о полноте системы булевых функций.
19.Релейно-контактные схемы: определение, примеры, функция проводимости. Анализ и синтез РКС (умение решать задачи).
Раздел 2. Логика высказываний.
1.Парадоксы в математике. Парадоксы Г. Кантора и Б. Рассела.
2.Логическое следование в логике высказываний. Проверка логического следования с помощью таблиц истинности и эквивалентных преобразований.
3.Понятия прямой теоремы, а также противоположной, обратной и обратной к противоположной теорем.
4.Понятия необходимых и достаточных условий.
5.Формальные системы. Выводы в формальных системах. Свойства выводов.
6.Исчисление высказываний (ИВ) Гильберта. Примеры выводов.
7.Теорема о дедукции для ИВ.
8.Теорема о полноте и непротиворечивости ИВ.
9.Метод резолюций для логики высказываний.
Раздел 3. Логика предикатов.
1.Понятие предиката и операции, их представления, примеры.
2.Сигнатура, интерпретация сигнатуры на множестве, алгебраические системы.
3.Язык логики предикатов, термы, формулы логики предикатов.
4.Свободные и связанные переменные. Замкнутые формулы.
5.Истинность формул на алгебраической системе
6.Выразимость свойств в логике предикатов. Умение записать формулой различные свойства систем и элементов систем.
7.Тождественно истинные (ложные) и выполнимые формулы.
8.Эквивалентность формул логики предикатов.
9.Основные эквивалентности логики предикатов.
10.Пренексный вид формулы.
11.Классы формул n, n, n. Теорема о связях между этими классами.
12.Нормальная форма Сколема, ее построение (на примерах).
13.Изоморфизм алгебраических систем. Теорема о сохранении значений термов и формул в изоморфных системах. Автоморфизм.
14.Элементарная теория алгебраической системы. Элементарная эквивалентность систем. Связь понятий изоморфизма и элементарной эквивалентности.
15.Логическое следование в логике предикатов.
16.Теория. Модель теории.
17.Исчисление предикатов (ИП) Гильберта. Свойства выводов.
18.Непротиворечивая теория.
19.Теорема о существовании модели (без доказательства).
20.Теорема о связи выводимости и противоречивости.
21.Теоремы о корректности и полноте ИП.
22.Теорема компактности.
23.Обоснование нестандартного анализа (построение алгебраической системы, элементарно эквивалентной полю вещественных чисел, содержащей бесконечно малые элементы).
24.Метод резолюций для логики предикатов (без доказательства корректности).
Литература
1.Хороший конспект.
2.М.Г. Лопатков. Дискретная математика, математическая логика и теория алгоритмов: теория булевых функций. Учебное пособие. – Омск: ОмГУ, 2006.
3.И.В. Ашаев, Ю.М. Ашаева, Дискретная математика и математическая логика в задачах государственных экзаменов по математике в ОмГУ. Учебное пособие. — Омск: ОмГУ, 2016.
4.С.В. Яблонский. Введение в дискретную математику.
5.Н.К. Верещагин, А. Шень. Языки и исчисления.
6.А.В. Гладкий. Математическая логика.
7.А.И. Мальцев. Алгебраические системы.
8.Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем.