Вопросы по курсу "Дискретная математика" для студентов групп АП-61, 62 1999.
1. Дайте определение взаимно однозначного соответствия между двумя множествами, приведите примеры. Дайте определение счётного множества. Докажите счётность множеств всех целых и всех рациональных чисел.
2. Дайте определение счётного множества. Докажите счётность множества всех слов в конечном алфавите и всех конечных подмножеств счётного множества.
3. Докажите, что всякое бесконечное множество содержит счётное подмножество, а также счётность объединения любых двух /или счётного семейства/ счётных множеств.
4. Дайте определение несчётного множества. Докажите, что множество всех бесконечных последовательностей из нулей и единиц несчётно.
5. Дайте определение несчётного множества. Докажите несчетность множества всех подмножеств натурального ряда и множества всех последовательностей натуральных чисел.
6. Объясните, что значит, что мощность одного множества превосходит мощность другого. Докажите, что мощность множества всех подмножеств любого множества имеет мощность большую, чем данное множество.
7. Дайте определение конечного автомата, приведите пример. Дайте определение множества, представимого /распознаваемого/ данным автоматом. Докажите, что существуют множества, не представимые никаким конечным автоматом.
8. Дайте определение регулярного множества /события/, приведите примеры. Докажите какие-либо тождества в алгебре регулярных событий. Сформулируйте основную теорему о связи регулярных выражений с конечными автоматами.
9. Изложите алгоритм анализа для события, представимого в данном конечном автомате.
10. Изложите алгоритм синтеза автомата, распознающего данное регулярное выражение.
11. Дайте определение машины Тьюринга, приведите пример. Дайте определение функции, вычисляемой данной машиной Тьюринга. Постройте МТ, вычисляющую функцию f(n)=2n.
12. Дайте определение функции, универсальной для данного класса функций. Докажите, что класс функций обладает универсальной функцией тогда и только тогда, когда он счетен.
13. Изложите тезис Чёрча. Изложите аргументы, делающие его убедительным.
14. Докажите существование вычислимой функции, универсальной класса всех вычислимых функций одного переменного.
15. Докажите, что универсальная вычислимая функция не может быть продолжена до всюду определённой вычислимой. Докажите, что её область определения - перечислимое неразрешимое множество.
16. Дайте определение нормального алгорифма Маркова, приведите пример. Дайте определение функции, вычислимой нормальным алгорифмом. Постройте нормальный алгорифм, вычисляющий функцию f(n)=2n.
17. Дайте определение разрешимого множества, приведите примеры. Докажите теорему о свойствах замкнутости класса разрешимых множеств.
18. Дайте определение перечислимого множества, приведите примеры. Докажите теорему о свойствах замкнутости класса перечислимых множеств.
19. Дайте определения разрешимого и перечислимого множеств, приведите примеры. Докажите теорему о связи этих понятий.
20. Докажите, что множество перечислимо тогда и только тогда, когда оно есть область определения вычислимой функции. Докажите существование перечислимого неразрешимого множества.
21. Сформулировать теорему Раиса.
22. Дать определения формального исчисления и формального вывода в нём. Привести примеры.
23. Дать определение исчисления высказываний. Привести пример вывода в нём.
24. Дать определение вывода из гипотез, привести примеры, сформулировать теорему дедукции. Привести примеры её применения.
25. Дать определение формулы, выводимой в ИВ. Сформулировать критерий выводимости для ИВ. Доказать тавтологичность выводимых в ИВ формул. Привести примеры применения критерия выводимости.
26. Дать определения разрешимого и непротиворечивого исчислений. Сформулировать критерий выводимости для ИВ. Доказать, что исчисление высказываний разрешимо и непротиворечиво.
27. Дать определение предиката, привести примеры. Дать определение множества истинности предиката. Доказать теорему о преобразовании множества истинности под действием булевых связок и кванторов.
28. Дать определение истинности предиката вида "сущ" х Р и "любое" х Р. Доказать теорему о вынесении кванторов из-под отрицания.
29. Дать определение общезначимой формулы логики предикатов. Доказать, что результат "предикатной подстановки" в тавтологию логики высказываний есть общезначимая формула. Привести пример общезначимой формулы, не получающейся таким образом.
30. Дайте определения транспортной сети, потока в ней, его величины и максимального потока. Изложите алгоритм построения максимального потока для данной сети.
31. Дайте определение транспортной сети, разреза в ней и его пропускной способности. Докажите теорему Форда-Фолкерсона.
Пусть А и В – множества. Взаимно однозначным соответствием (ВОС) А на В называется всякая функция f:А®В, удовлетворяющая условиям:
1. f определена на всем множестве А
2. множество ее значений совпадает с В
3. f инъективна, т.е. "a1,a2 ÎA[a1¹a2 Þ f(a1)¹f(a2)]
Множества А и В называют эквивалентными (А~В), если существует ВОС f:А®В.
Множество А называется счетным, если А~N. N – все натуральные числа. Иными словами счетность множества А означает, что все его элементы можно занумеровать (без повторений) натуральными числами.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.