2) 
– число делителей числа 
(
);
3) 
– сумма делителей числа 
(
).
1) 
; 2) 
; 3) 
;
4) 
; 5) 
; 6) 
.
P | Q | P?Q |
И | И | Л |
И | Л | И |
Л | И | И |
Л | Л | И |
Докажите, что предикат (P?Q)(x) тоже примитивно рекурсивный.
Предикаты P(x) и Q(x) примитивно рекурсивны. Определим: (P?Q)(x)?P(x)?Q(x) для всех x?N, где логическая связка ? задана следующей таблицей истинности:P | Q | P?Q |
И | И | Л |
И | Л | И |
Л | И | И |
Л | Л | Л |
Докажите, что предикат (P?Q)(x) тоже примитивно рекурсивный.
Функция y=f(x) определена «с перебором случаев»:
Докажите, что функция y=f(x) примитивно рекурсивная.
Пусть f – примитивно рекурсивная n-местная функция, а n-местная функция g, такая, что ?x1,x2,…,xn?N g(x1,x2,x3,…,xn)=f(x2,x1,x3,…,xn). Докажите, что функция g примитивно рекурсивная (n?2). Пусть f – примитивно рекурсивная n-местная функция, а (n?1)-местная функция g, такая, что ?x1, x2,…, xn?1?N g(x1, x2,…, xn?1)=f(x1, x1, x2,…, xn-1). Докажите, что функция g примитивно рекурсивная. Пусть f – примитивно рекурсивная 3-местная функция, а 5-местная функция g, такая, что ?x1, x2, x3, x4, x5?N g(x1, x2, x3, x4, x5)=f(x2, x3, x4). Докажите, что функция g примитивно рекурсивная. Пусть f – примитивно рекурсивная 6-местная функция, а 3-местная функция g, такая, что ?x1, x2, x3?N g(x1, x2, x3)=f(x2, x3, x2, x3, x2, x3). Докажите, что функция g примитивно рекурсивная.Машина Тьюринга
Выяснить, применима ли машина Тьюринга Т, задаваемая программой П, к слову Р. Если применима, то найти результат применения машины Т к слову Р. Предполагается, что начальная и заключительные конфигурации имеют стандартную форму.
Тесты текущего контроля по дисциплине «Математическая логика и теория алгоритмов»
Дополнение к области определения некоторой вычислимой функции _________ рекурсивно перечислимым
A) может не быть;
B) разъединено с ;
не может быть;D) должно быть.
Множество ________ тогда и только тогда, когда оно является _______ некоторой вычислимой функцииA) перечислимо, множеством значений;
B) разрешимо, множеством значений;
разрешимо, областью определения;D) перечислимо, областью определения.
Если
и рекурсия проводится по 
, то функция 
равна
0;
; x+z; 
. Функция, полученная из вычислимой с помощью рекурсии, является Вычислимой; примитивно рекурсивной; дифференцируемой; частично рекурсивной. Геделевский номер, равный 
, имеет функция 
; 
; 
; 
. Показал возможность существования универсальной вычислительной машины, способной выполнить любую эффективную процедуру А. Тьюринг; Д. Гильберт; А. Марков; К. Гёдель. Машина Тьюринга есть совокупность компонент пяти; двух; четырех; трех. Множество натуральных чисел является только рекурсивным; только перечислимым; рекурсивным и перечислимым; простейшим. Формализованный язык для однозначной записи алгоритмов называется автоматным языком; регулярным языком; метаязыком языком; алгоритмическим языком. Если множество не является множеством значений никакой функции, то оно нерекурсивно, но рекурсивно перечислимо; рекурсивно, но не перечислимо; нерекурсивно и неперечислимо; рекурсивно, но не перечислимо. 11. Усеченная разность 
равна
12. Функция 
является
13. Формальная грамматика, позволяющая построить любую
правильную цепочку символов, называется грамматикой
нормальной; автоматной; регулярной; порождающей. Идея использования рекурсии для решения задач, связанных соснованиями математики, предложена
Гильбертом; Пеано; Аль Хорезми; Тьюрингом. Функция, определяемая как число шагов в вычислении машинойТьюринга, называется
характеристической; геделевским номером; временным ресурсом; длиной программы. Команда машины Тьюринга состоит из элементарных действий любого числа; конечного числа; трех; двух.4.4 Методические материалы, определяющие процедуры оценивания ЗУН
Экзаменационные вопросы по математической логике и теории алгоритмов
1. Высказывания. Алфавит и формулы алгебры высказываний.
2. Эффективность определения формулы. Скобки. Формализация букв алфавита.
3. Истинностные значения и истинностные таблицы.
4. Равносильность формул. Истинностные функции.
5. Совершенные нормальные формы истинностных функций. Алгоритм построения СДНФ.
6. Совершенные нормальные формы истинностных функций. Алгоритм построения СКНФ.
7. Полные системы истинностных функций.
8. Виды формул алгебры высказываний, их классификация.
9. Важнейшие свойства общезначимых формул.
10. Методы установления общезначимости формул. Равносильные преобразования формул.
11. Отношение логического следования и его связь с общезначимостью. Важнейшие правила следования.
12. Применение языка алгебры высказываний. Исчисление высказываний. Система аксиом.
13. Теорема дедукции. Полнота исчисления высказываний.
14. Независимость аксиом А1—А3.
15. Аксиоматики L1 и L2.
16. Теория первого порядка. Примеры теорий первого порядка. Свойства теорий первого порядка.
17. Интерпретации. Выполнимость и истинность. Модели. Обобщение теорий первого порядка.
18. Теоремы о полноте.
19. Предваренные нормальные формы. Примеры. Нормальная форма Сколема. Пример.
20. Алгоритмы. Основные требования к алгоритмам.
21. Вычислимые функции. Разрешимые и перечислимые множества. Пересечение и объединение перечислимых множеств.
22. График вычислимой функции. Диагональный метод. Пример перечислимого неразрешимого множества.
23. Примитивно рекурсивные функции. Операторы суперпозиции и примитивной рекурсии.
24. Частично рекурсивные и общерекурсивные функции. Оператор минимизации и ограниченный оператор минимизации.
25. Примитивно рекурсивные предикаты и множества. Ограниченные кванторы.
26. Задание машины Тьюринга. Принцип машины Тьюринга.
27. Представление машины Тьюринга графом. Вычислимые по Тьюрингу функции.
28. Операции над машинами Тьюринга. Основная гипотеза теории алгоритмов (тезис Черча)
29. Нормальные алгоритмы Маркова. Функции вычислимые по Маркову.
30. Замыкание, распространение нормального алгоритма. Операции над нормальными алгоритмами.
5. Учебно-методическое и информационное обеспечение дисциплины (модуля)
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 |
