- •1.Понятие множества. Конечные и бесконечные множества. Операции над
- •Основная теорема:
- •4. Обобщённое равенство. Абстракция. Примеры.
- •6. Отношение порядка. Частичный порядок. Линейный порядок.
- •Оператор суперпозиции
- •9.Оператор примитивной рекурсии, алгоритм его вычисления
- •10. Определение класса примитивно-рекурсивных функций. Примитивная рекурсивность функций сложения и умножения
- •11.. Доказательство существования вычислимых не примитивно
- •12.. Оператор минимизации, алгоритм его вычисления. Определение
- •13.. Представление и реализация алгоритма. Непроцедурность
- •Стратегии:
- •21.. Понятие протокола. Поведение процесса. Примеры.
- •25.. Определение np-полной задачи. Теорема Кука.
- •Теорема Кука:
Основная теорема:
Пусть - есть отношение эквивалентности на Х, тогда система классов эквивалентности представляет собой разбиение множества Х. Обратно, если Ф(х) – некоторое разбиение множества Х, а отношение определяется так, что элемент <а,в>є, если существует Ає(х):<а,в>єА, тогда отношение не эквивалентности. Каждое отношение эквивалентности задает разбиение множества Х.
4. Обобщённое равенство. Абстракция. Примеры.
Два элемента равны в обобщённом смысле, если они принадлежат одному классу эквивалентности. Одно из применений отношения эквивалентности – формулировка определений через абстракцию. Суть этой процедуры состоит в том, что понятие определяется, как множество всех предметов, обладающих каким-либо свойством, характеризующим по предположению это понятие. На первый взгляд этот метод может показаться противоестественным, но на практике он оказывается весьма удобным. Рассмотрим, например, такую проблему: как определить положительные рациональные числа в терминах положительных целых чисел. Мы введем понятия пар целых чисел, имеющих равные отношения посредством определения: <x,y>~<u,v>, если xv=uy (перемножаются между собой крайние члены и средние между собой); Это отношение эквивалентности и мы можем определить рациональные числа, как класс эквивалентности.
2/3=4/6 истинно, 2*6=3*4. 2\3 и 4\6 – различные имена для одного и того же рационального числа.
5. Понятие функции. График функции. Суперпозиция функций. Примеры.
Отношение f называется функцией «из А в В», если
А и В
(x,y) и (x,z) => y=z
Отношение f называется функцией «из А на В», если
А и В
(x,y) и (x,z) => y=z
ждественная функция : A A определяется (х)=х
Функция f называется «1-1 функцией», если
z= (x) и z= (y) => x=y
Если f - «1-1 функцией» и функция «из А на В» => f – взаимно-однозначное отображение
Ф-я, полученная из f1,…,fn некоторой подстановкой их друг в друга и переименованием аргументом, называется суперпозицией f1,…,fn.
Графиком функции у=f(х) называется множество всех точек плоскости, координаты которых удовлетворяют данному уравнению.
Функция f называется инъекцией, если для всех x1, x2 из того, что x1 x2, следует f(x1) f(x2).
Функция f называется сюръекцией, если (f) =B.
Функция f называется биекцией (взаимно однозначным соответствием между множествами A и B), если она инъективна и сюръективна. Функция называется взаимно-однозначной, если она переводит различные элементы в различные.
Пусть даны ф-ии f: A–>B и g: B–>C. Функция h: A–>C называется композицией функций f и g (f◦g), если имеет место равенство h(x)=g(f(x)), где хєА.
6. Отношение порядка. Частичный порядок. Линейный порядок.
Минимальный/максимальный элемент. Наименьший/наибольший элемент.
Примеры
Отношение строгого порядка - иррефлексивное, транзитивное, антисимметричное отношение. <
Пример:
А - Множество геометрических фигур
P={(x,y) | фигура х имеет площадь меньше, чем фигура у}
Отношение частичного порядка – рефлексивное, транзитивное, антисимметричное отношение. ≤
Пример:
Числовое отношение х ≤ y
Отношение линейного порядка – отношение частичного порядка, удовлетворяющее условию дихотомии (любые два элемента из множества сравнимы в этом отношении).
Пример:
Отношение "старше" на множестве людей является линейным порядком.
Отношение делимости на множестве М={1,2,4,8} (???)
Пусть – отношение порядка на множестве A , тогда:
минимальный элемент x множества A – это элемент для
которого y y x ,
максимальный элемент x множества A – это элемент для
которого y x y ,
наименьший элемент x множества A – это элемент для которого
y x y ,
наибольший элемент x множества A – это элемент для которого
y y x .
Если, как обычно, в случае x < y проводить стрелку от x к y, то в графе отношения минимальный элемент - это тот, в который не входят стрелки, а максимальный - из которого не выходят стрелки.
Подмножества {x, y, z}, упорядоченные отношением включения.
7. Аксиоматические теории. Непротиворечивость, полнота и независимость системы аксиом.
Чтобы задать формальную аксиоматическую теорию, необходимо определить:
некоторое счетное множество символов (алфавит) – символов теории Т(конечные последовательности символов в теории Т называются выражениями теории Т);
Подмножество выражений теории Т, называемых формулами;
Подмножество формул теории Т, называемых аксиомами.
Конечное множество R1, R2, …, Rm отношений между формулами, называемых правилами вывода.
Если А и формулы А1,А2,…,Аi находятся в некотором отношении Rk,то А называется непосредственным следствием из формул А1,А2,…,Ai, полученным по правилу Rk.
Выводом в теории Т называется всякая последовательность 1, 2,…, n формул такая, что для любого i формула i есть либо аксиома теории Т, либо непосредственное следствие каких-либо предыдущих формул. Формула А называется теоремой теории Т, если в ней существует вывод, в котором последней формулой является А. Формула А называется следствием множества формул Г тогда и только тогда, когда существует такая последовательность формул 1, 2,…, n, что n есть А, и для любогоi, 1<=i<=n, I есть либо аксиома, либо формула из Г, либо непосредственное следствие некоторых предыдущих формул. Эта последовательность называется выводом из А в Г. элементы называются посылками вывода или гипотезами. Сокращено можно записать Г├А. Если множество Г состоит из формул В1,В2,…,Вk, то пишут В1,В2,…,Вk├А, и говорят, что формула А выводима из формул В1,В2,…,Вk. Если Г – пустое множество, то Г├А тогда и только тогда, когда А есть теорема. В этом случае принято писать ├А и говорить, что формула А доказуема, а сам вывод (последовательность формул) называют доказательством.
1) Формальная аксиоматическая теория называется полной, если в ней доказуема любая тавтология (тождественно истинная формула). Если в теории сформулировано высказывание S, то в этой теории можно доказать либо S, либо не S.
2) Формальная аксиоматическая теория называется непротиворечивой, если в ней не существует вывода формулы А такой, что одновременно доказуемы формулы А и ¬А.
3) Формальная аксиоматическая теория называется независимой, если удаление любой из аксиом приводит к потере полноты.
Формальную аксиоматическую теорию называют полной в узком смысле, если добавление любой невыводимой формулы в качестве схемы и аксиом приводит к противоречивой системе.
За пределами любой теории есть неизмеримый остаток.
8.Неформальные свойства понятия алгоритма, понятия алфавита, слова, терма. Простейшие вычислимые функции. Оператор суперпозиции
Алгоритм:
Дискретность – процесс последовательного построения величин, при котором каждая след вычисляется из предшествующей системы величин.
Детерминированность — система величин полученных в некоторый момент времени, однозначно определяемый системой величин, полученных на предшествующих действиях.
Элементарность шагов — закон получение след из предыдущих должен быть простым
Направленность — если на каком-то этапе способ, получения след величин, не дает результатов, то должно быть указано что считать результатом алгоритма
Массовость — алгоритм должен быть применим к разным наборам исходных данных.
Алфавит – конечное множество символов A={a,b,c...}
Слово - конечное последовательность символов в алфавите
Термы – это слова особого вида, записанные в функциональном алфавите.
Алгоритм- множество функциональных термов. Интерпретация – множество аксиом, которые можно вывести.
Модель- интерпретированная теория.
Функциональный алфавит состоит из 3 частей:
символы предметных переменных (x,y,...z)
функциональные символы (f,g,...h)
специальные символы (, ),
Аксиомы – возьмем функции, которые назовем вычислимыми (простейшие вычислимые функции).
S(x)=x+1; функция следования
O(x)=0; функция нуля
выбор
Эти простейшие функции всюду определены и из них с помощью конечного числа применений операторов, введенных ниже, можно конструировать более сложные функции.
Тогда алгоритм можно определить как множество функциональных термов, задающее вычисление функции f.