Репетиторы по математике. Доска объявлений Авита. Предложение и спрос на обучение дискретной математике.

Подготовка к ЕГЭ, ГИА по математике

Решение курсовых работ и задач по дискретной математике

Репетиторы по математике в Москве

Арепетитор.рф поможет найти репетитора по математике! Бесплатный подбор!

Репетитор ГИА по математике

Отличные результаты! Опыт более 26 лет!
репетитор-по-математике.рф

Пример решения курсовой работы по дискретной математике

1. Верно ли утверждение, что если функция записана в расширенном базисе Клини с использованием оператора минимизации, она в любом случае не может являться примитивно-рекурсивной.
Обоснуйте ответ, сославшись на конкретные теоремы.
Если не верно – приведите контрпример.
Не верно согласно теореме о мажорируемых неявных функциях.
Подберем такие функции g(x,у) и a(x), чтобы они являлись ПРФ, например,

g(x,y) = (x+4)∸у,
a(x) = x+10,

т.е. они вычислимы и везде определены.
Используем слабую минимизацию, при этом имеет место соотношение

μy[g(x,y)=0] ≤ a(x)

для любых х.
Тогда по указанной теореме функция f(x) = μy[(x+4)∸у=0] будет являться примитивно-рекурсивной.

2. Как с точки зрения счётности, конечности и эффективной перечислимости можно охарактеризовать множество функций, являющихся частично-рекурсивными, но не принадлежащих к множеству примитивно-рекурсивных функций? Ответ обоснуйте.

Решение:
Из Тезиса Чёрча: любая арифметическая функция, вычислимая в обычном смысле (ВАФ), есть общерекурсивная функция (ОРФ), а всякая частичная арифметическая функция, вычислимая в обычном смысле (ВЧАФ), есть ЧРФ.
Множество частично-рекурсивных функций счетно, следовательно, любое его подмножество тоже счетно.
бесконечно, эффективно неперечислимо ?

3. Чем похожи и чем отличаются доказательство несчетности АФ и эффективной неперечислимости ВАФ? Почему нельзя копию доказательства несчетности АФ применить к ВАФ и тем самым доказать несчетность этого множества.

4. Чему равна мощность множества всех вычислимых функций одной действительной переменной? Ответ обоснуйте.
Решение:
Если функция вычислима, то значит, что ей можно сопоставить машину Тьюринга, её вычисляющую.
Мощность множества всех машин Тьюринга - алеф-ноль, значит, мощность множества всех вычислимых функций одной переменной ограничена сверху альф-нулём.
При этом среди таких функций также будут функции вида f(x) = a,
где а - вычислимое действительное число.
Мощность вычислимых действительных чисел - алеф-ноль, поэтому мощность искомого множества ограничена снизу алеф-нулем.
Из двух условий получаем, что мощность множества всех вычислимых функций одной переменной - алеф-ноль.

Зачем нужен репетитор.

Как научиться самому решать задачи по математике, физике, экономике.

5. Как с точки зрения счётности, конечности и эффективной перечислимости можно охарактеризовать множество элементов, которые возможно представить с помощью конечного числа счетно-бесконечной системы знаков?
Ответ обоснуйте.

Решение:
Обозначим это конечное число за n (натуральное число).
Тогда можно составить n последовательностей из одного знака, n² последовательностей из двух знаков, n³ из трех и т.д. (все получаемые значения будут натуральными числами).
Множество таких последовательностей будет счетно-бесконечно, т.е. мощность множества равна алеф-ноль.
Оно эффективно неперечислимо, но доказывать долго.

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

Класс частичных арифметических функций шире класса арифметических функций, т.к. любая арифметическая функция является всюду определенной частичной арифметической функцией и, кроме того, существуют не всюду определенные арифметические функции.
Диаграмма вхождения рассмотренных множеств друг в друга представлена на рисунке.

Отрывок из учебника - методички по дискретной математике

Для любого множества А найдется множество В, мощность которого больше А.

Доказательство онлайн репетитора по дискретной математике Алексея Учителя.

Автор учебника - преподаватель МФТИ А.Э. Султанов.
Скачать бесплатно можно на онлайн уроке.
Рассмотрим множество В всех функций, заданных на множестве А и принимающих значения 0 и 1.
Каждой точке а множества А поставим в соответствие функцию f^a(x), принимающую в этой точке а значение 1, а в остальных точках значение 0.
Ясно, что разным точкам соответствуют разные функции.
Отсюда следует, что мощность множества В не меньше мощности множества А (|B|≥|A|).
Предположим, что мощности множеств А и В равны друг другу. 
В этом случае существует взаимно-однозначное соответствие между элементами множеств А и В.
Обозначим функцию, соответствующую элементу а из множества А, через f_a(x).
Все функции семейства f_a(x) принимают значение или 0 или 1.
Построим новую функцию φ(x) = 1 - f_х(x).
Таким образом, чтобы найти значение функции φ(x)  в некоторой точке а, принадлежащей множеству А, надо сначала найти соответствующую функцию f_а(а) и затем вычесть из единицы значение этой функции в точке а.
Из построения видно, что функция φ(x) также задана на множестве А и принимает значения 0 и 1.
Следовательно, φ(x) является элементом множества В.
Тогда существует такое число b в множестве А, такое что φ(x) = f_b(x).

С учетом ранее введенного определения функции φ(x) = 1 - f_х(x), получим что для всех х, принадлежащих множеству А, верно 1 - f_х(x)= f_b(x).
Пусть х = b. Тогда 1 - f_b(b) = f_b(b) и значит f_b(b)=1/2.
Данный результат явным образом противоречит тому, что значения функции f_b(х) равны нулю или единице.
Следовательно, принятое предположение неверно, а значит не существует взаимно-однозначного соответствия между элементами множеств А и В (пишем |A| ≠ |B|).
Поскольку |A| ≠ |B| и при этом |B| ≥ |A|, значит |B| > |A|.
Это означает, что для любого множества А можно построить множество В большей мощности.
Отсюда можно сделать вывод, что множества самой большой мощности не существует.