Программа дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направления подготовки» ] подготовки бакалавра/ магистра/ специалиста [Оставьте этот титульный лист для дисциплины,

8Образовательные технологии

8.1Методические рекомендации преподавателю

8.2Методические указания студентам

9Оценочные средства для текущего контроля и аттестации студента

9.1Тематика заданий текущего контроля

1. 
   Какое отображение называется взаимно однозначным соответствием между множествами? Привести примеры отображений, которые являются и которые не являются взаимно однозначными соответствиями. Установить взамно однозначное соответствие между множеством всех целых четных чисел и множеством всех целых нечетных чисел.
   

2. 
   Какие множествами называются равномощными? Доказать, что множество всех бесконечных последовательностей чисел 0 и 1 равномощно множеству всех подмножеств множества {1, 2, 3,…}.
   

3. 
   Какие множества называются счетными? Привести пример счетного множества. Доказать, что всякое бесконечное подмножество счетного множества само счетно. Доказать, что всякое бесконечное множество содержит счетное подмножество.
   

4. 
   Доказать, что объединение конечного или счетного числа конечных или счетных множеств конечно или счетно. Вывести отсюда, что множество всех наборов (a₁,…,a_d), где d фиксировано, а a₁,…a_d –целые неотрицательные числа, счетно.
   

5. 
   Доказать, что множество всех рациональных чисел счетно. Доказать, что множество всех конечных последовательностей натуральных числе счетно.
   

6. 
   Что такое алгебраическое число? Доказать, что множество всех алгебраических чисел счетно.
   

7. 
   Доказать, что если A – бесконечное множество, а B – конечное или счетное множество, то A равномощно объединению A с B. Вывести отсюда, отрезок [a, b] равномощен интервалу (a, b) для любых чисел a < b.
   

8. 
   Доказать, что отрезок [0,1] равномощен множеству всех бесконечных последовательностей из 0 и 1. Вывести отсюда, что квадрат равномощен отрезку.
   

9. 
   Что означает утверждение «мощность множества A не меньше мощности множества B»? Верно ли, что |A|≥|A|? Верно ли, что если |A|≥|B| и |B|≥|C|, то |A|≥|C|? Ответ обосновать.
   

10. 
    Доказать теорему Кантора--Бернштейна. Доказать с ее помощью, что шар и куб равномощны.
    

11. 
    Доказать теорему Кантора. Вывести из нее, что множество всех бесконечных последовательностей из 0 и 1 несчетно.
    

12. 
    Рассказать об известных вам парадоксах теории множеств.
    

13. 
    Описать как работает МНР (машина с неограниченными регистрами). Какие в ней используются команды? Что такое программа для МНР? Привести пример.
    

14. 
    Что такое МНР-вычислимая фанкция? Доказать, пользуясь только определением, что f(x,y)=x+y является такой функцией.
    

15. 
    Что такое разрешимый предикат? Привести пример.
    

16. 
    Доказать, если f(x₁,…x_n), g₁(y₁,…,y_m),…, g_n(y₁,…,y_m) –- МНР-вычислимые функции, то и f(g₁(y₁,…,y_m),…,g_n(y₁,…,y_m)) ---тоже МНР-вычислимая функция.
    

17. 
    Что такое неформальный алгоритм? Привести пример. Сформулировать тезис Черча. Привести пример его применения.
    

18. 
    Доказать, что существуют МНР-невычислимые функции.
    

19. 
    Рассказать как нумеруются МНР-команды и МНР-программы. Выписать МНР-программу, имеющею номер 8. Какую функцию от одного переменного она вычисляет?
    

20. 
    Используя нумерацию программ, указать явно МНР-невычислимую функцию.
    

21. 
    Что такое универсальная функция для заданного множества МНР-вычислимых функций? Доказать, что для множества всех МНР-вычислимых функций одного переменного универсальная функция существует.
    

22. 
    Что такое тотальная МНР-вычислимая функция одного пременного? Приведите пример. Доказать, что для множества всех таких функций универсальной функции не существует.
    

23. 
    Какое подмножество в N^s называется разрешимым? А какое называется перечислимым? Привести примеры. Доказать, что не существует общего алгоритма, позволяющего по паре чисел (n, m) узнать останавливается ли вычисление по программе с номером n при начальной конфигурации регистров R₁=m, R₂=0, R₃=0,…
    

24. 
    Доказать, что не существует общего алгоритма, который для любой МНР-вычислимой функции одного переменного позволял бы установить тотальна она или нет.
    

25. 
    Доказать, что всякое разрешимое подмножество в N^s перечислимо.
    

26. 
    Доказать, что в N^s существуют перечислимые подмножества, не являющиеся разрешимыми, например, таковым является при s=1 множество всех таких n, что вычисление по МНР-программе с номером n сходится при начальной конфигурации R₁=n, R₂=0, R₃=0,…
    

27. 
    Доказать, что перечислимые подмножества в N --- это в точности проекции на первую координату разрешимых подмножеств в N².
    

28. 
    Что такое алгебраическое подмножество в N^s? Привести пример. Доказать, что всякое алгебраическое подмножество разрешимо.
    

29. 
    Какие подмножества в N называются диофантовыми? Сформулировать теорему Матиясевича.
    

30. 
    Сформулировать 10-ю проблему Гильберта. Используя теорему Матиясевича, доказать, что 10-я проблема Гильберта имеет отрицательное решение.
    

31. 
    Доказать, что всякое перечислимое подмножество в N является множеством значений некоторой тотальной МНР-вычислимой функции одного переменного.
    

32. 
    Доказать, что подмножество E в N перечислимо тогда и только тогда, когда E есть множество неотрицательных значений некоторого многочлена от нескольких переменных с целыми коэффициентами. Вывести отсюда, что существует «формула простых чисел», т.е. такой многочлен от нескольких переменных с целыми неотрицательными значениями, что множеством его положительных значений при целых значениях переменных является в точности множество всех простых чисел.
    

33. 
    Дать определение булевой функции (функции алгебры логики) от n переменных. Дать определения конъюнкции, дизъюнкции, импликации, отрицания и эквивалентности.
    

34. 
    Сколько всего имеется булевых функций от n переменных? Ответ обосновать. Что такое таблица истинности булевой функции? Привести пример.
    

35. 
    Что такое n-мерный единичный куб, его вершины и грани? Как нумеруются его вершины с помощью двоичного разложения чисел? Проиллюстрировать эти понятия на примере n=1, 2, 3.
    

36. 
    Что такое формула? Как булевы функции задаются с помощью формул? Единственно ли такое задание? Привести примеры.
    

37. 
    Указать важнейшие равносильности формул алгебры логики. Проиллюстрировать на примере одной из них принцип их доказательства.
    

38. 
    Что такое носитель булевой функции? Доказать, что носитель конъюнкции (дизъюнкции) булевых функции f и g от n переменных равен пересечению (объединению) носителей функций f и g.
    

39. 
    Что такое элементарная конъюнкция? Когда она называется правильной? Доказать, что носителем элементарной конъюнкции от n переменных является грань n-мерного куба. Привести примеры.
    

40. 
    Что такое дизъюнктивная нормальная форма булевой функции? Что такое ее совершенная дизъюнктивная нормальная форма (СДНФ)? Привести примеры. Доказать, что всякая ненулевая булева функция обладает единственной СДНФ.
    

41. 
    Описать практический способ нахождения СДНФ. Привести пример.
    

42. 
    Что такое полином Жегалкина? Сколько всего имеется различных полиномов Жегалкина от n переменных? Ответ обосновать. Доказать, что всякая булева функция может быть реализована полиномом Жегалкина и притом единственным. Привести пример.
    

43. 
    Что такое сокращенная дизъюнктивная нормальная форма булевой функции? Привести пример. Сформулировать и обосновать правила обобщенного склеивания и поглощения.
    

44. 
    Сформулировать алгоритм Блейка нахождения сокращенной дизъюнктивной нормальной формы. Привести пример его применения.
    

45. 
    Что такое тупиковая дизъюнктивная нормальная форма. Описать способ ее нахождения. Привести пример.
    

46. 
    Что такое двойственная и что такое самодвойственная булева функция? Привести примеры. Доказать, что если F(x₁,…x_n)=f(g₁(x₁,…,x_n),…f_d(x₁,…,x_n)), то F*(x₁,…x_n)=f*(g*₁(x₁,…,x_n),…f*_d(x₁,…,x_n)).
    

47. 
    Что такое монотонная булева функция? Привести примеры. Доказать, что если f(y₁,…,y_d), g₁(x₁,…,x_n),…, g₁(x₁,…,x_n) монотонны, то и f(g₁(x₁,…,x_n),…f_d(x₁,…,x_n)) монотонна.
    

48. 
    Что такое функциональное замыкание совокупности булевых функций? Какая совокупность называется функционально замкнутой? Какая совокупность называется полной? Привести примеры. Описать классы S, L, M, T₀, T₁ и доказать, что они функционально замкнуты и неполны.
    

49. 
    Сформулировать теорему Поста о полноте. Привести пример ее применения для доказательства полноты какой-либо совокупности булевых функций.
    

50. 
    Что такое контактная схема и булева функция, реализуемая контактной схемой? Привести пример. Как по данной схеме записать формулой реализуемую этой схемой булеву функцию? Привести пример.
    

51. 
    Доказать, что любая булева функция может быть реализована контактной схемой. Описать метод каскадов. Привести пример.
    

52. 
    В чем состоит проблема минимизации контактных схем? Доказать, что для функции Шеннона L(n) имеет место неравенство L(n) ≤ n2ⁿ. Сформулировать теоремы Шеннона и Лупанова.
    

53. 
    Описать компоненты, из которых состоит любое формальное исчисление, -- язык, аксиомы, правила выводаю Что такое вывод? Привести пример формального исчисления.
    

54. 
    Описать язык, аксиомы и правила вывода исчисления высказываний. Привести примеры.
    

55. 
    Описать алгоритм, распознающий, является ли конечная последовательность формул в исчислении высказываний выводом или нет.
    

56. 
    Объяснить почему ни одно из правил вывода в исчислении высказываний не является лишним.
    

57. 
    Какая формула в исчислении высказываний называется тавтологией? Привести примеры.