Свойства понятия выводимости:

Пусть Г – призвольное множество формул и A, B, C – формулы. Рассмотрим множество свойств:

1) Г, A |= A

2) Г, А, В |= С, то Г,В, А |= C

3) Если из Г выводится В, А – призводная формула, то из Г, А тоже выводится В

Г |= B, A

Г, А |= B

4) Если из Г вывоится А, из Г выводится В, из формул А, В выводится С, то из Г выводится С

Г |= А; Г |= B; А, В |= C, то Г |= C

5) Г, А |= B, Г |= A, то Г |= B

6) Г |= A->B ʌ Г |= A, то Г |= B

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

Теория Т называется противоречивой, если она содержит такое высказывае S, что S и ˥S одновременно являются теоремами. В противном случае теория Т называется непротиворечивой.

Моделью теории называется интерпретация языка этой теории.

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

Теория Т называется абсолютно полной или полной в широком смысле, если для любого высказывания S этой теории или S, или ˥S есть теорема.

Т. 1. Исчисление высказываний полно в узком и широком смысле.

Т. 2. Выское исчисление предикатов 1-ого порядка Т непротиворечивого.

Теория алгоритмов. Интуитивное понятие алгоритма.

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

Классификация алгоритмов: 1) технологические; 2) управляющие; 3) информационно-вычислительные.

Алгоритм (в интуитивном смысле) – правило, сформулированное на некотором языке и определяющее процесс переработки допустимых данных в искомые результаты.

Машина Тьюринга (МТ) – это четверка вида T = (A, Q, P, q₀), где А – конечный алфавит ленточных символов, Q – конечное непустое множество состояний головки МТ, Р – конечное множество команд, q₀ – начальное состояние головки МТ.

Под конфигурацией МТ принято понимать слово Vq_is_jF, где V и F – слова в алфавите МТ, s_j – символ, обозреваемый головкой МТ, q_i – текущее состояние головки МТ.

Функция F(x₁, x₂, …, x_n) называется вычислимой по Тьюрингу, если существует МТ, вычисляющая эту функцию.

Тезис Тьюринга.

Изучая МТ, обнаружили, что это мощное вычислительное устройство.

Неразрешимые проблемы.

1) проблемы, которые алгоритмически неразрешимы;

2) проблемы, которые алгоритмически разрешимы, но не разрешимы в реальном времени.

Теорема 1.

Проблема самоприменимости нерарешима, т. е. не существует алгоритма, отличного по номеру самопримен-е машины от несамоприменимых (смотри стр. 149 у С. Яблокова).

Теорема 2.

Проблема останова неразрешима, т. е. не существует алгоритма, определяющего для МТ Т и входной ленты L, остан-ся ли Т, получив на вход ленту L.

Полиномиальным алгоритмом или алгоритмом полиномиальной врем-й сложности называют алгоритм, у которого временная сложность равна O(P(n)), P(n) – некоторая полиномиальная функция от входной длины n.

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

ФОРМАЛЬНЫЕ ЯЗЫКИ И ГРАММАТИКИ

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

Цепочка длины K над алфавитом V – произвольная последовательность k символов из алфавита V, не обязательно различных.

Ԑ - пустая цепочка, не содержит ни одного символа.

Формально понятие цепочки над алфавитом V определяется следующим образом:

1) Ԑ - цепочка над алфавитом V;

2) если x – цепочка над алфавитом V и символ V_i принадлежит V, то xV_i – тоже цепочка над V;

3) других цепочек нет.

V^k - множество всех цепочек длины k над алфавитом V.

V_k = { w | |w| = k}

V⁰ = E = {Ԑ}

V^* = . Его элементами являются все цепочки над алфавитом V, в том числе и Ԑ.

V⁺ = V^*\{Ԑ}

Конкатенация цепочек w и  - это последовательность символов, получившаяся приписыванием справа символов цепочки w символов цепочки . Обозначается умножением “*”.

Если цепочка w = *, то цепочка  - префикс цепочки w. Если цепочка  не пуста, то  - собственный префикс. Аналогично,  - суффикс w. Если  не пуста, то  - собственный суффикс.

Свойства конкатенации:

1) V^* замкнуто относительно конкатенации, т. е. любое ,  ϵ V^*;

2) конкатенация ассоциативна w, , (w*)* = w*(*), * ϵ V^*;

3) пустая цепочка – единица конкатенации w Ԑw = wԐ = w;

4) если V содержит более одного символа, то операция конкатенации некоммутативна:

существуют такие w,  ϵ V^* => w* != *w;

5) w,  ϵ V^* |w*| = |w| + ||.

w^k – конкатенация k цепочек w, т. е.

w^k = w * w * … w

k раз

Будем считать, что w⁰ = Ԑ.

Обращением цепочки w = v₁v₂ … V_n назовем цепочку w^R = v_n v_n-1 … v₁. Ԑ^R = Ԑ.

Теорема

Если V != , то множество всех цепочек над алфавитом V счетно.

Формальный язык над алфавитом V – произв-е множество цепочек над алфавитом V. Т. о., любой язык L над алфавитом V является подмножеством V^* => язык L – не более чем счетное множество.

Класс всех языков над V – множество всех подмножеств V*. Поскольку V* счетно, если V != , то класс всех языков над V имеет мощность континуума.

Конкатенация языков A и B – множество всех цепочек, получающихся в результате приписания к цепочке языка А цепочки языка B.

A*B = {w*| w ϵ A,  ϵ B}

E = {Ԑ} - единица конкатенации языка.

AE = { a Ԑ = a, abԐ = ab} = A

A = {w  | w ϵ A,  ϵ } = , т. к. в языке нет цепочек. и E - два различных языка!

Основные свойства конкатенации языков:

1) операция конкатенации языков ассоциативна:

• L₁, L₂, L₃ c V^*: (L₁*L₂)*L₃ = L₁*(L₂*L₃)

2) язык E = {Ԑ} является единицей конкатенации языков L c V^*, LE = EL = L

3) пустой язык является нулем конкатенации языков L c V^*, L = L =

4) конкатенация над алфавитом из более чем одного символа некоммутативна: L₁ c V^*, L₂ c V^*, |V| > 1,

L₁L₂ != L₂L₁

5) операция конкатенации языков дистрибутивно относительно объединения: L1,L2,L3 c V^*,

L₁(L₂ ᴗ L₃) = L₁L₂ ᴗ L₁L₃

6) но не дистрибутивно относительно пересечения.

L^* = также является подмножеством V^* множества всех цепочек над алфавитом. L^* - замыкание Клини или итерация.

L⁺ = L^*\ E

Обращение языка L состоит из всех цепочек, являющиеся обращениями языка L: L^R = {w^R| w ϵ L}