Q- обычное отношение эквивалентности

35. Проблемы ИП (непротиворечивости, полнота в узком смысле, полнота в широком смысле).

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

Логика называется полной(в широком смысле), если в ней выводимо все, что истинно. Теорема о полноте исчислений предикатов полна.

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

Теорема Гёделя о неполноте. Во всякой достаточно богатой теории существует такая истинная формула, что ни она, ни её отрицание не выводимо в этой теории.

36. Логические основы ЭВМ. Простейшие преобразователи информации. Структурная формула. Функциональная схема.

Для описания логики функционирования аппаратных и программных средств ЭВМ используется алгебра логики(булева).

Булева алгебра оперирует логическими переменными, которые могут принимать только два значения: истина или ложь (true или false), обозначаемые соответственно 1и 0.

Основной СС ЭВМ является двоичная СС, в которой используются только 2 цифры –1 и 0.

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

1. Инвертор (Логический элемент НЕ).

. 2. Конъюнктор (логический элемент И). Физически последовательное соединение переключателей

Дизъюнктор (логический элемент ИЛИ).

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

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

37. Нечеткая логика. Основные понятия (нечеткое множество, лингвистические переменные). Основные свойства нечетких множеств.

Пусть  - универсальное множество, т.е. полное множество, охватывающее всю проблемную область. Нечеткое множество  представляет собой набор пар , где  и  - функция принадлежности, которая представляет собой некоторую субъективную меру соответствия элемента  нечеткому множеству .

Свойства нечетких множеств

а) нечеткое множество  пустое, т.е. , если , .

б) нечеткие множества  и эквивалентны, т.е. , если

---

, .

в) нечеткое множество  является подмножеством нечеткого множества , т.е. , если , .

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

38. Интуитивное определение алгоритма. Возможные случаи протекания алгоритмического процесса. Определение алгоритма, применимого к исходному набору данных. Характерные черты алгоритма. Область применимости алгоритма.

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

Алгоритм — это упорядоченный набор однозначных выполнимых шагов.

Пусть алгоритм A имеет исходный набор данных P . Возможны следующие три случая протекания алгоритмического процесса.

1.На некотором шаге возникает состояние, опознаваемое как заключительное. При этом происходит остановка вычислений и выдается результат Q.

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

3.При некотором состоянии возникает ситуация, когда процесс вычислений обрывается без выдачи результата (например, не срабатывает инструкция для определения результата вычислений). Тем самым нет перехода к следующему шагу и нет результата вычислений. В этом случае говорим, что произошла безрезультатная остановка.

Свойства:

1. Массовость.

Начальная система величин может выбираться из некоторого потенциально бесконечного множества. 

2. Понятность.

Чтобы алгоритм можно было выполнить, он должен быть понятен исполнителю

3. Дискретность.

Алгоритм представляется в виде конечной последовательности шагов (алгоритм имеет дискретную структуру) и его исполнение расчленяется на выполнение отдельных шагов (выполнение очередного шага начинается после завершения предыдущего).

4. Конечность.

Выполнение алгоритма заканчивается после выполнения конечного числа шагов. При выполнении алгоритма некоторые его шаги могут повторяться многократно.

5. Определенность.

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

6. Эффективность.

Каждый шаг алгоритма должен быть выполнен точно и за конечное время.

Областью применимости алгоритма наз. совокупность тех объектов, к к-рым он применим

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

Особенности:

1)Конечность – любой алгоритм должен приводить к цели за конечное число шагов (т.е. исключается бесконечные циклы).

2)Определенность- каждый шаг алгоритма должен быть точно и недвусмысленно определен

---

3)Алгоритм имеет некоторое количество входных данных

4)Алгоритм обязательно имеет от 1 до нескольких выходных данных

5)Эффективность – все входящие в алгоритм операции можно выполнить точно и за конечный отрезок времени

Типы моделей:

• Рекурсивные функции

• Машины Тьюринга

• Алгоритмы Маркова

Первый тип связывает понятие алгоритма с вычислениями и числовыми функциями. Наиболее развитая и изученная модель этого типа – рекурсивные функции – первый способ формализации понятия алгоритма.

Второй тип основан на представлении об алгоритме как о некотором детерминированном устройстве, способном выполнять в каждый отдельный момент лишь примитивные операции (машина Тьюринга).

Третий тип алгоритмических моделей – это преобразование слов в произвольных алфавитах, в которых элементарными операциями являются подстановки, т.е. замена куска слова (подслова) другим словом (Нормальный алгоритм Маркова, каноническая система Поста).

40. Конструктивные объекты. Счетные множества. Основные свойства счетных множеств. Алгоритмы и функции. Определение алгоритма, предложенное Черчем и Клини.

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

Множество A счетно, тогда и только тогда, когда его элементы можно представить в виде бесконечной последовательности без повторений Подмножество счетного множества конечно или счетно.

1. Объединение конечного или счетного числа конечных или счетных множеств конечно или счетно.

2. Множество действительных чисел не является счетным множеством.

3. Множество M, состоящее из всех строк (x1, x2,...,xn) произвольной длины n>=0, где xi принадлежит N, является счетным множеством.

4. Пусть α — конечный алфавит и X — множество всех слов в алфавите A. Тогда множество X является счетным множеств.

С точки зрения А.Черча и С. Клини, в алгоритмическом процессе вычисляется значение некоторой функции f(Q) (x1 , x2 , . . . , xn) Q, определенной на множестве натуральных чисел. Строгое определение алгоритма, предложенное Черчем и Клини, основано на понятии частично рекурсивной функции. Они предложили отождествить интуитивное понятие «алгоритм» со строгим математическим понятием «частично рекурсивная функция».

41. Рекурсивные функции. Исходные функции. Операторы суперпозиции, примитивной рекурсии. Определение примитивно рекурсивной функции.

Рекурси́вная фу́нкция — это числовая функция {\displaystyle f(n)} числового аргумента, которая в своей записи содержит себя же. Такая запись позволяет вычислять значения {\displaystyle f(n)}FАААААААF F(n) на основе значений {\displaystyle f(n-1),f(n-2),\ldots }F(n-1),F(n-2),…

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

---

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

42. Доказательство примитивной рекурсивности некоторых функций.

43. Оператор минимизации. Определение частично рекурсивных и общерекурсивных функций. Теорема о вычислимости всякой частично рекурсивной функции f. Тезис Черча.

Теорема. Всякая частично рекурсивная функция f является вычислимой функцией.

Тезис ЧЕРЧА: Числовая функция тогда и только тогда алгоритмически вычислима, когда она частично рекурсивна.

44. Определение алфавита, слова в теории нормальных алгоритмов Маркова. Понятия пустого слова и подслова. Определение марковской подстановки. Результат марковской подстановки. Соединение слов. Понятие расширения алфавита.

Алфавитом (как и прежде) называется любое непустое множество. Его элементы называются буквами, а любые последовательности букв — словами в данном алфавите. Для удобства рассуждений допускаются пустые слова (они не имеют в своем составе ни одной буквы). Если A и B — два алфавита, причем AєB, то алфавит B называется расширением алфавита A.

Слова будем обозначать латинскими буквами: P,Q,R (или этими же буквами с индексами). Одно слово может быть составной частью другого слова. Тогда первое называется подсловом второго или вхождением во второе.

Марковской подстановкой называется операция над словами, задаваемая с помощью упорядоченной пары слов (P,Q), состоящая в следующем. В заданном слове R находят первое вхождение слова P (если таковое имеется) и, не изменяя остальных частей слова R, заменяют в нем это вхождение словом Q. Полученное слово называется результатом применения марковской подстановки (P,Q) к слову R. Если же первого вхождения P в слово R нет (и, следовательно, вообще нет ни одного вхождения P в R), то считается, что марковская подстановка (P,Q) неприменима к слову R.

45. Определение алгоритма применимого к слову. Определение алгоритма над алфавитом. Простая и заключительная подстановки в теории нормальных алгоритмов Маркова. Схема алгоритма.

Пусть Р есть слово в алфавите А; говорят, что алгоритм α применим к слову Р, если Р содержится в области определения α.

Если алфавит В является расширением алфавита А, то всякий алгоритм в алфавите В называется алгоритмом над алфавитом А.

Для обозначения марковской подстановки (Р, Q) используется запись Р —> Q. Она называется формулой подстановки (Р, Q). Некоторые подстановки (Р, Q) будем называть заключительными. Для обозначения таких подстановок будем использовать запись Р —>. Q, называя ее формулой заключительной подстановки.

Слово Р называется левой частью, a Q — правой частью в формуле подстановки.

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

---

46. Определение нормального алгоритма Маркова в алфавите А.

Упорядоченный конечный список формул подстановок в алфавите называется схемой (или записью) нормального алгоритма в .

Данная схема определяет (детерминирует) алгоритм преобразования слов, называемый нормальным алгоритмом Маркова. Дадим его точное определение.

47. Описание работы нормального алгоритма Маркова со словами. Определение нормально вычислимой функции, заданной на некотором множестве слов некоторого алфавита. Примеры нормально вычислимых функций.

Пример МТ: вычисляющей функцию x+1;

48. Пример построения нормального алгоритма для функции.

49. Теорема о частичной вычислимости по Маркову всякой частично рекурсивная функции и следствие к ней. Принцип нормализации. Совпадение класса всех нормально вычислимых функций с классом всех функций, вычислимых по Тьюрингу. Эквивалентность различных теорий алгоритмов.

Теорема 1: Всякая частично рекурсивная функция (общерекурсивная) является частично вычислимой (вычислимой) по Маркову функцией.

Теорема 2: Всякая частичная функция, частично вычислимая (вычислимая) по Маркову, является частично рекурсивной (общерекурсивной) функцией.

"Принцип нормализации Маркова": Для нахождения значений функции, заданной в некотором алфавите, тогда и только тогда существует какой-нибудь алгоритм, когда функция нормально вычислима.

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

а) класс всех функций, вычислимых по Тьюрингу;

б) класс всех частично рекурсивных функций;

в) класс всех нормально вычислимых функций.

Алгоритмы H1 и H2 эквивалентны относительно алфавита A, если области применимости H1 и H2 относительно алфавита A совпадают и для любого слова P из этой области выполняется равенство H1(P) = H2(P).

50. Машина Тьюринга (МТ). Основные узлы, функционирование. Разновидности МТ. Данные МТ. Элементарные шаги МТ. Применение МТ к словам. Определение заключительного слова по заданному начальному слову и системе команд. Конструирование МТ: задание внешнего алфавита, множества состояний и системы команд. Композиция МТ.

Машина Тьюринга (МТ) состоит из двух частей – ленты и автомата.

Лента используется для хранения информации. Она бесконечна в обе стороны и разбита на клетки. В каждой клетке может быть записан один символ или ничего не записано. Автомат – это активная часть МТ. В каждый момент он размещается под одной из клеток ленты и видит её содержимое. Кроме того, в каждый момент автомат находится в одном из состояний. Находясь в некотором состоянии, автомат выполняет какую-то определённую операцию

МТ работает тактами (по шагам), которые выполняются один за другим. На каждом такте автомат МТ выполняет три следующих действия, причем обязательно в указанном порядке:

---

Смотрите также файлы

• Экзаменационные вопросы.docx

• Алгебра высказываний.doc

• Исчисление высказываний.doc

• история билеты(все).docx

• Текст 10000 символов (транспорт Британии).docx