Сложность алгоритма помогает оценить затраты на его реализацию и определяется вычислительными мощностями, необходимыми для его выполнения. Она часто измеряется двумя параметрами: T(временная сложность) и S (пространственная сложность, или требования к памяти). И T и S обычно представляются в виде функций от n, где n – размер входных данных.

Пусть А – алгоритм для решения некоторого класса задач, а n – размерность отдельной задачи из этого класса. В общем случае n может быть длиной обрабатываемой последовательности данных. Определим f(n) как рабочую функцию, дающую верхнюю границу для максимального числа основных операций (сложения, сравнения и т.д.), которые должен выполнить алгоритм.

Продолжить читать "Оценка сложности алгоритма"

Содержание понятия “алгоритм“ можно определить следующим образом:

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

Основные свойства алгоритма:

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

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

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

4. Конечность. Алгоритм заканчивает работу после конечного числа шагов.

5. Результативность. В момент прекращения работы алгоритма известно, что является результатом.

6. Массовость. Алгоритм описывает некоторое множество процессов, применимых при различных входных данных.

Продолжить читать "Понятие алгоритма"

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

A1.      A → (A →B),

A2.      (A → (B → C)) → ((A → B) → (A → C)),

A3.      (ךA → ךB) → (B → A),

A4.      xF(x) →F(y),

A5.      F(y)→ xF(x).

Продолжить читать "Логика предикатов . Пример формальной теории первого порядка"

Рассмотрим два случая:

1). S не зависит от X

1. (x)P(x)V S = (x)[P(x)V S],

2. (x)P(x)V S = (x)[P(x)V S],

3. (x)P(x)&S = (x)[P(x)&S],

4. (x)P(x)&S = (x)[P(x)&S].

Эти свойства являются следствием свойств коммутативности и дистрибутивности дизъюнкции и конъюнкции.

2). S зависит от X

1. (x)P(x)V (x)S(x) = (x)[P(x)V S(x)],

2. (x)P(x)&( x)S(x) = (x)[P(x)&S(x)],

3. (x)[P(x)&S(x)]t(x)P(x)&( x)S(x),

4. (x)P(x)V (x)S(x) → (x)[P(x)V S(x)].

Продолжить читать "Логика предикатов . Расширение области действия кванторов"

Определение. Правильно построенные формулы логики предикатов – это комбинации атомных предикатов и констант с логическими связками. Они определяются рекурсивно над множеством атомных предикатов с помощью связок ך,→, скобок и одной дополнительной связки( Рекурсивное определение)

формулы:

1. Атомные предикат есть формула.

2. Если Р-формула, то ך(P) – тоже формула.

3. Если Р,Q-формулы, то (P→ Q) – тоже формула.

4. Если Р-формула, то (x)P – тоже формула.

5. Никаких других формул нет.

Продолжить читать "Логика предикатов . Формулы"

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

В разговорном языке встречаются более сложные повествовательные предложения, истинность которых может меняться при изменении объектов, о которых идет речь. В логике такие предложения, истинность которых зависит от параметров, обозначают с помощью предикатов. Таким образом, предикат - это высказывание-функция, значение (истина/ложь) которого зависит от параметров.

Продолжить читать "Логика предикатов. Основные понятия"

Определение формальной теории

Формальная теория T – это:

1. множество A символов, образующих алфавит A и множество слов A*;

2. множество F слов в алфавите A, F Ì A*, которые называются формулами;

3. подмножество B формул, B Ì F, которые называются аксиомами;

4. множество R отношений на множестве формул, которые называются правилами вывода.

Множество символов A, как правило, конечно. Обычно, для образования символов используют буквы, к которым приписывают в качестве индексов натуральные числа. Множество формул F обычно задается индуктивным определением, например, с помощью формальной грамматики. Как правило, это множество бесконечно. Множества A и F в совокупности определяют язык или сигнатуру формальной теории. Множество аксиом B может быть конечным или бесконечным. Если множество аксиом бесконечно, то оно задается с помощью конечного множества схем аксиом и правил порождения. Множество правил вывода R, как правило, конечно.

Интерпретация формальной теории

Интерпретацией формальной теории T в область интерпретации называется функция I, которая каждой формуле формальной теории однозначно сопоставляет некоторое содержательное высказывание относительно объектов множества. Это высказывание может быть истинным или ложным. Если высказывание является истинным, то говорят, что формула выполняется в данной интерпретации. Интерпретация I называется моделью множества формул, если все формулы этого множества выполняются в интерпретации I. Интерпретация I называется моделью формальной теории T , если все формулы этой теории выполняются в интерпретации I (то есть все выводимые формулы оказываются истинными в данной интерпретации).

Общезначимость и непротиворечивость

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

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

Модель для формальной теории T существует тогда и только тогда, когда T семантически непротиворечива. Формальная теория T называется формально непротиворечивой, если в ней не являются выводимыми одновременно формулы FךF. Теория T формально непротиворечива тогда и только тогда, когда она семантически непротиворечива.

Пусть F1, F2, . . . , Fm,G – формулы теории T , то есть F1, F2, . . . , Fm,G Ì F. Если существует такое правило вывода R,R Ì R, что (F1, F2, . . . Fm,G) Ì R, то говорят, что формула G непосредственно выводима из формул F1, F2, . . . , Fm по правилу вывода R. Символически это записывается следующим

образом:

F1, F2, . . . , Fm

G

R

или

F1, F2, . . . , Fm ` G

где формулы F1, F2, . . . , Fm называются посылками, а G – заключением.

Иными словами, правило вывода должно давать возможность по данному набору формул F1, F2 . . . Fm и формуле G установить, являются ли эти m+1 формул в определенном отношении (связи) между собой. Если факт отношения установлен, то G считается непосредственно выводимой из F1, F2 . . . Fm. Можно рассматривать аксиомы, как частные случаи правил вывода, у которых m = 0, то есть аксиома – непосредственно выводимая формула из пустого множества посылок. При содержательной интерпретации формальной теории формулы соответствуют утверждениям, аксиомы – исходным утверждениям, которые могут быть признаны содержательно истинными, правила вывода – схемам рассуждений, позволяющим из одних истинных утверждений получать другие истинные утверждения.

Продолжить читать "Формальные теории. Выводимость"

Формальные теории, не пользуясь естественным (разговорным) языком, нуждаются в собственном формальном языке, на котором записываются встречающиеся в нем выражения. Опишем используемые для этого средства:

Алфавит – конечное множество A = {a1, a2, …, an}, элементы которого называются буквами или символами.

Любая конечная последовательность букв b1…bk, где bi 2 A для i = 1, …k называется словом в алфавите . Слово может состоять только из одной буквы, а может вообще не содержать букв, тогда оно называется пустым и обозначается . Число букв в слове ‘ называется его длиной и обозначается | λ |. В частности, | λ |= 0. Над словами определена операция сцепления. Результатом сцепления слов ‘ = b1..bk и   = c1…cm является слово ‘  = b1..bkc1..cm. Очевидно, что | λ  |=| λ1 | + | λ2 |. Ассоциативность операции сцепления позволяет записывать результат двух и более сцеплений без скобок.

Продолжить читать "Формальные теории. Алфавиты, слова, языки"

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

Так, в цепочке преобразований (a + b)(a – b) = a(a – b) + b(a – b) = a² – ab + ba – b² = a² – b² использовано:

Во-первых, целый набор равенств, выражающих свойства чисел и операций над ними:

(x + y) · z = x · z + y · z,                               (x + y) + z = x + (y + z);

x – y = x + (-1) · y,                                          x + y = y + x;

x = 1 · x;                                                        n + (-n) = 0;

x · y = y · x;                                                   x · 0 = 0;

x · x = x²;                                                      x + 0 = x,

где вместо x, y, z могут подразумеваться любые выражения, а вместо n – любое число.

Продолжить читать "Формальные теории. Понятие формализации"