Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Контрольная работа: Полурешетки m-степеней

Название: Полурешетки m-степеней
Раздел: Рефераты по математике
Тип: контрольная работа Добавлен 07:58:48 04 мая 2009 Похожие работы
Просмотров: 39 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Содержание

Введение

Теоретическая часть

§1 Основные определения

§2 Простейшие свойства m – степеней

§3 Минимальные элементы верхней полурешетки m-степеней

2. Практическая часть

§1. Идеалы полурешетки m-степеней частично рекурсивных функций

Литература


Введение

Сейчас много внимания уделяется вопросам сводимости функций. Данная работа посвящена одной из разновидностей сводимости частично рекурсивной функции, а именно m-сводимости.

Для дальнейшего рассмотрения этого вопроса будем пользоваться общепринятыми понятиями и теоретико-множественными обозначениями.

Символы логических операций: отрицания, конъюнкции, дизъюнкции, импликации, и эквивалентности будем обозначать: , соответственно.

Кванторы общности и существования обозначают соответственно.

Совокупность всех целых неотрицательных чисел обозначим через N.

Под множеством будем понимать подмножество N.

Латинскими буквами A,B,C,… будем обозначать множества.

Объединение множества A и B обозначим через пересечения этих множеств - а разность , дополнение - .

Пусть 1 *2 *…*n 1 ,2 ,…,n 1 1 , 2 2 ,…,nn -декартово произведение множеств 1 ,2 ,…,n .

Определение: Функции называется арифметической, если ее аргументы пробегают натуральный ряд N, и сама функция принимает лишь натуральные значения.

Под n-местной частичной арифметической функцией будем понимать функцию, отображающую некоторое множество в N ,где -n-ая декартовая степень множества N.

Греческими строчными буквами будем обозначать частично рекурсивные функции (ЧРФ) : .

Всякий раз, когда число аргументов явно не указывается, речь идет об одноместных функциях. Обозначим через множество всех одноместных ЧРФ.

Запись означает, что функция для этой n-ки не определена, а запись означает, что функция для этой n-ки определена.

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

Определение: Частичную n-местную функцию назовем всюду определенной, если .

Всюду определенная функция будет обозначаться латинскими буквами: f,g,h,… . [5,6]


Теоретическая часть

§1 Основные определения

Определение 1: (интуитивное).

Арифметическая функция называется частично рекурсивной, если существует алгоритм для нахождения ее значений.

Определение 2:

Под начальными функциями будем понимать следующие функции:

1.функция следования S;

2.функции выбора

,

3.

4.нулевая функция .

Определение 3: (оператор суперпозиции (подстановка)).

Говорят, что функция получена суперпозицией из функций и , если для всех значений выполняется равенство:

Определение 4: (оператор примитивной рекурсии ).

Говорят, что функция получена из двух функций и с помощью оператора примитивной рекурсии, если имеют место следующие равенства:


.

Это определение применимо и при n=0. Говорят, что функция получена из одноместной функции константы равной и функции , если при всех :

Определение 5: (-оператор или оператор минимизации).

Определим -оператор сначала для одноместных функций.

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

.

В этом случае -оператор называется оператором обращения и -наименьшее .

Теперь определим -оператор в общем виде:

Определение 6:

Функция называется частично рекурсивной функцией (ЧРФ) ,если она может быть получена из начальных функций с помощью конечного числа применений трех операторов: суперпозиции, примитивной рекурсии, -оператора.

Определение 7:

Если - ЧРФ и всюду определена, то она называется рекурсивной функцией.

Определение 8:

Множество - рекурсивно перечислимо (РП), в интуитивном смысле, если существует эффективная процедура, которая выписывает элементы этого множества. Каждый элемент на некотором шаге будет выписан.

Определение 9:

Характеристической функцией множества называется функция

Определение 10:

Множество называется рекурсивным, если характеристическая функция является рекурсивной.

Определение 11:

Функция m-сводима к функции (), в точности тогда, когда существует рекурсивная функция , такая, что

Функция называется сводящей функцией.

Введем отношение m-эквивалентности на множестве .

Определение 12:

Введем понятие m-степени функции .

Определение 13:

Введем понятие m-сводимости множеств.

Определение 14:

Множество m-сводимо к множеству (обозначение ), если существует рекурсивная функция такая, что В этом случае говорят, чтоm-сводимо к посредством .

Аналогично вводится понятие m-степени множества .

Определение 15:

Частичная характеристическая функция для множества -функция

Определение 16:

ЧРФ – универсальная для множества , если (-рекурсивная функция ) где - ЧРФ с геделевым номером .

Определение 17:

Если на множестве определено бинарное отношение , удовлетворяющее условиям:

1. (рефлексивность);

2. (антисимметричность);

3. (транзитивность),

то множество называется частично упорядоченным, а отношение называется частичным порядком на . Отношение , удовлетворяющее только свойствам 1,3, называется предпорядком на . Если частичный порядок на удовлетворяет условию

4. то называется линейным порядком (или просто порядком), а -линейно упорядоченным множеством или цепью.

Определение 18:

Верхней (нижней) гранью подмножества называется такой элемент что () для любого . Элемент называется max (min) элементом , если () для всех

Если же () для любых ? ,то элемент называется наибольшим (наименьшим).

Определение 19.

Наименьшая (наибольшая) из верхних (нижних) граней множества называется точной верхней (нижней) гранью этого множества.

Определение 20.

Полурешеткой (точнее, верхней полурешеткой) назовем пару где - непустое множество, а -бинарная операция на , удовлетворяющая условиям: для любого

1.

2.

3.

Если - полурешетка, то зададим на частичный порядок следующим соотношением: для

Проверка того, что это частичный порядок, очевидна. Операция является для этого порядка операцией взятия точной верхней грани.

Определение 21:

Множество называется продуктивным, если существует рекурсивная функция , называемая продуктивной функцией для , такая, что

Ясно, что продуктивное множество не может быть р.п. Если бы то Ø, что невозможно.

Определение 22:

Множество называется креативным, если оно р.п. и продуктивно.

Заметим, что креативные множества по теореме Поста не могут быть рекурсивными. Примером креативного множества будет

Действительно

откуда рекурсивная функция является продуктивной функцией для .

Имеет место следующее утверждение: если В - р.п. множество, А -креативно, то - креативно.[1,5]

§2 Простейшие свойства m – степеней

Ведем отношение частного порядка на множестве m – степеней:


Обозначим через L частично упорядоченное множество m – степеней.

Утверждение 2.1: множество L является верхней полурешеткой.

Доказательство:

Рассмотрим , где

.

Докажем, что эта функция является точной верхней гранью для произвольных ЧРФ α и β.

Рассмотрим γ :

для рекурсивных функций g, f.

Определим функцию .

Проверим следующие равенства: .

Пусть x=2t, тогда и .

Пусть x=2t+1, тогда и .

Таким образом, равенство справедливо.

Следовательно, функция является точной верхней гранью для произвольных ЧРФ α и β, ч.т.д.

Утверждение 2.2: .

Доказательство:

: Пусть , тогда посредством рекурсивной функции f, которая множество А m – сводит к В.

: Аналогично , ч.т.д.

Следствие: существует изоморфное вложение полурешетки m-степеней рекурсивно перечисляемых множеств в полурешетку m-степеней частичных характеристических функций: .

Утверждение 2.3: .

Доказательство:

Если Ø, то утверждение справедливо.

Пусть Ø. Возьмем , откуда для некоторого ; а так как для некоторой рекурсивной функции f, то и .

Таким образом, , ч.т.д.

Следствие: функции, принадлежащие одной и той же m-степени, имеют одинаковую область значений.

Утверждение 2.4: Пусть f, g – рекурсивные функции, тогда .

Доказательство:

: Следует из следствия к 2.3.

: Пусть : покажем, что , то есть .

Строим таким образом: допустим , начинаем последовательно вычислять g(0), g(1), …, пока не получим, что g(n)=i, а такое n обязательно появится, так как .

Полагаем, что , тогда очевидно, что .

Аналогично строим функцию , такую, что . Отсюда получим, что .

Таким образом, так как и , ч.т.д. [1]


§3 Минимальные элементы верхней полурешетки m -степеней

Утверждение 3.1: Наименьшего элемента в L нет.

Доказательство:

Допустим противное, то есть пусть - наименьший в L элемент. Тогда Ø ), где сØ – нигде неопределенная функция.

Следовательно, Ø и Ø ).

Возьмем всюду определенную функцию h. Ясно, что сØm h.

С одной стороны, Ø ) – наименьший элемент, то есть сØm h; с другой стороны сØm h.

Получили противоречие, то есть в L наименьшего элемента нет. Ч.т.д.

Утверждение 3.2: m-степень, содержащая универсальную функцию, является наибольшей в L.

Доказательство:

Пусть Ψ – универсальная функция, а α – произвольная ЧРФ. Так как α – ЧРФ, то найдется такое число х0 , что α=φ0 .

Покажем, что . В качестве сводящей возмем функцию f(x0 ,y). Тогда из определения Ψ вытекает, что , где , то есть .

Таким образом, - наибольшая в L. Ч.т.д.

Введем обозначение: .

Ясно, что .

Утверждение 3.3: сØ и множество всех функций вида cn (x) и только они образуют множество минимальных в L элементов.

Доказательство.

Из утверждения 3.1. следует, что сØ – минимальный в L элемент.

Возьмем произвольную функцию cn (x).

Пусть .

Ясно, что {}, кроме того α – всюду определенная функция, так как иначе , следовательно, .

Пусть теперь минимальный в L элемент, отличный от сØ и от всех сn , тогда определена в некоторой точке х0 ; пусть , имеем , где , то есть, . Получили противоречие. Ч.т.д. [1,2]


2. Практическая часть.

§1. Идеалы полурешетки m-степеней частично рекурсивных функций

Определение:

Идеалом полурешетки L назовем всякое подмножество I отличное от Ø, удовлетворяющее следующим условиям:

1. ;

2. .

Идеал называется главным, если он содержит наибольший элемент.

Рассмотрим множество всех m-степеней частичных характеристических функций, то есть:

Н={}.

Предположение 4.1:

Множество Н является главным идеалом полурешетки L.

Доказательство:

1. Берем две степени для некоторых р.п. множеств А и В. точной верхней гранью будет степень, содержащая функцию .

Определим множество АВ:

{}.


Докажем, что .

Будем пользоваться определением 15 для доказательства данного равенства.

Рассмотрим 4 случая.

1) если x=2t,

И если x=2t,

2) Если x=2t,

И если x=2t,

3) Если x=2t+1,

И если x=2t+1,

4) Если x=2t+1,

И если x=2t+1,

Следовательно, равенство справедливо во всех четырех случаях, т.к. обе его части равносильны в рассмотренных случаях.

.

2. Пусть . По определению m-сводимости из следует, что существует рекурсивная функция f такая, что: , откуда . Из утверждения 2.2 и того, что всякое р.п. множество m-сводимо к креативному следует, что: - наибольший элемент в Н, где k – креативно.

Тогда Н – главный идеал полурешетки L. Ч.т.д.

Рассмотрим множество всех m-степеней рекурсивных функций, то есть:

М={}.

Предположение 4.2: Данное множество М является главным идеалом полурешетки L.

Доказательство:

1. Берем две степени рекурсивных функций, их точной верхней гранью будет , где также рекурсивная функция.

2. Если , откуда существует рекурсивная функция h, такая, что , где также рекурсивная функция. Далее, посредством f(x) для любой рекурсивной функции f(x), отсюда - наибольший элемент в М.

М – главный идеал полурешетки L. Ч.т.д.


Литература

1. Дегтев А.Н. Сводимость частично-рекурсивных функций. – Сибирский математический журнал, 1975 т. 16, №5, с. 970-988.

2. Ершов Ю.Л. Теория нумераций. – М.: Наука, 1977.

3. Кагленд Н. Вычислимость. Введение в теорию рекурсивных функций. – М.: Мир, 1983.

4. Мальцев А.И. Алгоритмы и рекурсивные функции. – М.: Наука, 1965.

5. Поляков Е.А., Розинас М.Г. Теория алгоритмов. – Иваново: ИвГУ, 1976.

6. Поляков Е.А., Маринина Н.В. Теория алгоритмов. – Шуя: ШГПУ, 2004.

7. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. – М.: Мир, 1972.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений07:22:44 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
16:50:00 25 ноября 2015

Работы, похожие на Контрольная работа: Полурешетки m-степеней

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(150696)
Комментарии (1839)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru