Дипломная работа

от 20 дней
от 9999 рублей

Курсовая работа

от 10 дней
от 1999 рублей

Реферат

от 3 дней
от 699 рублей

Контрольная работа

от 3 дней
от 99 рублей
за задачу

Диссертация

Сроки и стоимость индивидуальные

Главная - Статистика и статистическое наблюдение - Математическая логика и теория алгоритмов - контрольная работа (11 заданий).

Математическая логика и теория алгоритмов - контрольная работа (11 заданий). Статистика и статистическое наблюдение . Контрольная

  • Тема: Математическая логика и теория алгоритмов - контрольная работа (11 заданий).
  • Автор: Ольга
  • Тип работы: Контрольная
  • Предмет: Статистика и статистическое наблюдение
  • Страниц: 10
  • Год сдачи: 2007
  • ВУЗ, город: Москва
  • Цена(руб.): 650 рублей

Заказать персональную работу

Выдержка

Решение Задания 1:
Функция g(x1,x2,,xn) является примитивно рекурсивной, так как получается из примитивно рекурсивных функций Ik(x1,x2,,xn) = xk (1  k  n) и f(x1,x2,,xn) с помощью операции суперпозиции (или подстановки):

g(x1,x2,,xn) = f(I2(x1,x2,,xn), I1(x1,x2,,xn), I3(x1,x2,,xn),, In(x1,x2,,xn))

Функция f(x1,x2,,xn) является примитивно рекурсивной по условию. Функции Ik(x1,x2,,xn) = xk (1  k  n) являются примитивно рекурсивными по определению.
Что и требовалось доказать.

Решение Задания 2:
Функция P(x,y) является общерекурсивной, так как получается из общерекурсивных функций o(x) = 0 и S(x,y) = x + y с помощью операции примитивной рекурсии:
P(x,0) = x0 = 0 = o(x)
P(x,y+1) = x(y+1) = xy + x = P(x,y) + x = S(P(x,y),x)

Функция S(x,y) = x + y является общерекурсивной, так как получается из общерекурсивных функций s(x) = x + 1 и I1(x) = x с помощью операции примитивной рекурсии:

S(x,0) = x + 0 = x = I1(x)
S(x,y+1) = x + (y+1) = (x + y) + 1 = S(x,y) + 1 = s(S(x,y))

Функции o(x) = 0, s(x) = x + 1 и I1(x) = x являются общерекурсивными по определению.
Что и требовалось доказать.

Содержание

Задание 1. Доказать, что если функция f(x1,x2,,xn) примитивно рекурсивна, то примитивно рекурсивна функция g(x1,x2,,xn) = f(x2,x1,,xn), т.е. перестановка аргументов.

Задание 2. Доказать, что следующая функция общерекурсивна. P(x,y)=xy

Задание 3. Доказать, что следующая функция общерекурсивна sgn(x), если
sgn(x)=1, если x0
sgn(x)=0, если x=0

Задание 4. Построить машину Тьюринга, которая применима ко всем словам в алфавите и {a0,a1,a2} делает следующее: любое слово x1x2xn, где xi=a1 или xi=a2 (i=1,2,,n), преобразует в слово x2x3xnx1.

Задание 5. Применяя правило подстановки, доказать, что доказуема формула
(AB)&BB
Задание 6. Применяя правило подстановки и правило заключения, доказать, что доказуема формула
AvAA

Литература

Задание 7. Применяя производные правила вывода, показать, что доказуема формула
(AB)(AAvB)
Задание 8. Доказать, что H = {AB, BC} |- AC

Задание 10. Опишите машину Тьюринга, выполняющую операцию:
К (копирование) q101x00x0 | q001x01x0.

Задание 11. Опишите машину Тьюринга, выполняющую операцию:
Умножение: q101x+101y+10 | q0 01xy+10.

Задание 11. Опишите машину Тьюринга, выполняющую операцию:
Л (стирающая машина): q101x0 | q000x0.

Задание 12. По таблицам истинности найдите формулы, определяющие функции , , , . Упростите их. Постройте их КНФ, СКНФ, ДНФ, СДНФ. Для упрощенных формул постройте РКС.

Форма заказа

Напрмер, Экономика

Похожие работы

Название Цена
Контрольная работа по статистике (8 заданий). 900
Контрольная работа по статистике. 800
Применение несплошного наблюдения на практике. Основные компоненты анализа. 5 задач. 650
14 задач по статистике. 1000
4 задания по статистике. 1000
Задания по статистике - 8 шт. 2000
Статистика 1100
Контрольная работа по статистике (ИССЛЕДОВАНИЕ) 1300
Социально-экономическая статистика (7 задач с пояснениями) 950
Статистика (8 задач) 500

© 2010-2017, Все права защищены. Принимаем заказы по всей России.