Перечень вопросов, которые выносятся на экзамен в 1 семестре

1. Математический язык. Имена, именные формы, высказывания, высказывательные формы. Логические знаки. Таблицы истинности для отрицания, конъюнкции, дизъюнкции, импликации, эквивалентности.

2. Логика Аристотеля. Понятие класса и множества. Отличия. Принадлежность элемента множеству. Диаграммы Венна. Подмножества. Равенство множеств.

3. Операции над множествами: превращение элемента в множество, объединение и пересечение множеств, свойства.

4. Операции над множествами: разность, дополнение, симметрическая разность множеств, свойства. Законы де Моргана.

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

6. Интерпретации переменных. Таблицы истинности. Интерпретации формул. Построение таблицы истинности для формул.

7. Тавтологии, выполнимые и невыполнимые формулы. Важнейшие тавтологии (идемпотентность, закон исключенного третьего, закон силлогизма, modus tollens, ассоциативные законы).

8. Важнейшие тавтологии (коммутативные и дистрибутивные законы, закон двойного отрицания, законы де Моргана, противоречие, контрапозиция, поглощение и др.).

9. Теорема о тавтологии и невыполнимой формуле. Доказательство. Операция подстановки в формулу. Получение новых тавтологий.

10. Выполнимое множество формул. Выполнение набора формул. Логическое следование и эквивалентность формул. Теоремы о выводимости и тавтологиях.

11. Второе правило подстановки. Правила логического вывода (модус поненс, силлогизм, модус толлендо поненс, двойное отрицание, контрапозиция, доказательство от противного, законы де Моргана, доказательство разбором случаев).

12. Нормальные формы. Построение формулы по таблице. Литерал. Конъюнкт. ДНФ. СДНФ. Теорема о выполнимой формуле и СДНФ.

13. Дизъюнкт. КНФ. СКНФ. Построение по таблице истинности. Теорема о представлении произвольной формулы с помощью ограниченного набора логических связок.

14. Понятие булевой функции. Множество булевых функций. Несущественные переменные. Суперпозиция функций. Понятие замкнутого класса. Примеры замкнутых классов. Замыкание множества функций.

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

16. Класс T₁. Теорема о замкнутости класса T₁. Двойственные функции. Примеры. Класс самодвойственных функций. Доказательство замкнутости. Лемма о несамодвойственной функции.

17. Предполный класс M. Примеры. Доказательство замкнутости. Лемма о немонотонной функции. Пример применения.

18. Предполный класс L. Примеры. Доказательство замкнутости. Лемма о нелинейной функции. Пример применения.

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. Упорядоченные множества. Минимум, максимум, минимальный и максимальный элементы. Примеры.

49. Грани. Цепи. Постулат Куратовского – Цорна.

50. Понятие функции. Область определения, область значений. Всюду определенная функция. Образы, прообразы. Графики функций.

51. Частичные и всюду определенные функции. Сужения функций.

52. Инъективные, сюръективные, биективные функции. Пример: шифр Цезаря.

53. Монотонные функции. Неубывающая, строго возрастающая, невозрастающая и строго убывающая функции.

54. Композиция функций. Обратные функции.

55. Последовательности и подпоследовательности как функции специального вида.

56. Функции k в 1. Принцип Дирихле, обобщенный принцип Дирихле. Доказательство.

57. Теорема Эрдёша и Секереша о возрастающей (убывающей) подпоследовательности.

58. Понятие мощности для бесконечных множеств. Определение Г.Кантора. Свойства мощностей. Счетные (À₀) множества. Доказательства счетности множества четных чисел и множества целых чисел.

59. Доказательство счетности множества рациональных чисел. Первая диагональная процедура Г.Кантора.

60. Несчетные множества. Несчетность множества вещественных чисел. Вторая диагональная процедура Г.Кантора. Иррациональные числа. Алгебраические числа. Трансцендентные числа. Мощность булеана бесконечного множества. Кардинальные числа. Континуум-гипотеза.