Математическая логика и теория алгоритмов: Учебное пособие

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Государственное образовательное учреждение высшего профессионального образования «ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

Кафедра информатики

В.А. СТЕНЮШКИНА

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ

Рекомендовано Ученым советом Государственного образовательного учреждения высшего профессионального образования «Оренбургский государственный университет»в качестве учебного пособия для студентов экономических и естественнонаучных специальностей

Оренбург 2004

ББК 22.12я7 С 79 УДК [510.5+510.6](075.8)

Рецензент кандидат технических наук, доцент Ю.Н.Пивоваров

C 79

Стенюшкина В.А. Математическая логика и теория алгоритмов: Учебное пособие.Оренбург: ГОУ ОГУ, 2004. – 106 с. ISBN

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

ББК 22.12я7 ISBN © Стенюшкина В.А., 2004 © ГОУ ОГУ, 2004

ЧАСТЬ 1 МАТЕМАТИЧЕСКАЯ ЛОГИКА Введение Математическая логика – естественнонаучная дисциплина, изучающая математические доказательства и вопросы оснований математики. Логика как искусство рассуждений зародилась в глубокой древности. Начало формальной логики как науки о структуре суждений и умозаключений связано с именем Аристотеля (IV в. до н. э.). Дедуктивные умозаключения, в которых из двух суждений следует новое суждение – силлогизмы – были проведены Аристотелем на категорических суждениях – суждениях типа: А – общеутвердительное суждение «Всякое S суть Р»; Е – общеотрицательное суждение «Никакое S не суть Р»; I – частноутвердительное суждение «Некоторые S суть Р»; О – частноотрицательное суждение «Некоторые S не суть Р». Пример «первой фигуры» силлогизма: «Все люди смертны. Кай – человек. Следовательно, Кай смертен.» Первый этап развития формальной логики – традиционная логика – длился два тысячелетия. Второй этап – современная логика - длится поныне. Другие имена этого этапа – символическая логика или математическая логика. Основы современной формальной логики заложили (середина XIX – начало XXв.в.) Дж. Буль, О. Морган, Г. Фреге, Дж. Пеано. Традиционная логика опиралась на естественный язык, который из-за многозначности и аморфности требований к построению выражений и придания им смысла приводит к парадоксам. В средние века был распространен парадокс: “Сказанное Платоном – ложно, - говорит Сократ. – Сказанное Сократом – истинно, - говорит Платон”. Современная логика использует формальные теории (ФТ), или исчисления. Формальные теории описывают любые множества с заданными на них отношениями с помощью аксиом и правил вывода. С логической точки зрения наиболее существенными свойствами формальных теорий являются непротиворечивость, полнота и разрешимость. Исчисление называется непротиворечивым, если в нем не выводимы одновременно какое-либо высказывание и его отрицание. Исчисление, формализующее некоторую теорию, называется полным относительно этой теории, если множество истинных утверждений теории совпадает с множеством высказываний, выводимых в данном исчислении. Исчисление называется разрешимым, если существует алгоритм, позволяющий для любого высказывания определить, выводимо оно в этом исчислении или нет. Формальные теории являются развитием аксиоматического метода, приобретшего известность благодаря «Началам» Евклида (около 330 – 320 гг. до н. э.). Предпринятое во второй половине XIX в. исследование аксиом евклидовой геометрии (ЕГ) показало, что система аксиом, данная в «началах» не полна. В 1899 г. Дж. Гильберт предложил первую достаточно строгую аксиоматику ЕГ. К 1922 г. у Гильберта сложился план обоснования всей математики путем ее полной формализации и последующим «метаматематическим» доказательством

непротиворечивости формализованной математики. А в 1931 году К. Геделем была доказана теорема о неполноте арифметики, из которой следовало, что для достаточно богатых по содержанию математических теорий не существует адекватных формализаций. Тем не менее, вся дальнейшая работа над логическими основаниями математики в большой мере идет по путям, намеченным Гильбертом. Дело в том, что на практике формальные теории, описывающие содержательные объекты, задаются с помощью собственных аксиом, которые наряду с собственно предикатами и функторами содержат предикаты и функторы, свойства которых аксиомами не описываются, а считаются известными в данной теории. Язык, который мы изучаем (в данном случае язык ФТ), называется языком–объектом, а язык, на котором мы формулируем и доказываем различные результаты об этом языке – объекте, называется метаязыком. (Этот метаязык сам мог бы быть формализован и стать предметом исследования, которое, в свою очередь, проводилось бы на некотором метаязыке, и т. д.). Различию между «выводом в языке–объекте» и «доказательством в метаязыке» соответствует различие между теоремой языка – объекта и метатеоремой языка. Слово «метаматематика» употребляется, в частности, как название исследований логических и математических языков–объектов. Предмет математической логики разнообразен. Раздел математической логики, включающий классическую логику высказываний (алгебру высказываний и исчисление высказываний) и классическую логику предикатов (алгебру предикатов и исчисление предикатов), называется классической логикой. Классическая логика придерживается принципа двузначности, в соответствии с которым любое высказывание является либо истинным, либо ложным. Существуют также разнообразные неклассические логики. Среди них многозначные логики, интуиционистская логика, логика причинности, логика времени, деонтическая логика. В целом задача неклассических логик – более полно описать те элементы логической формы рассуждений, которые упускаются классической логикой. В то же время классическая логика остается ядром современной логики, сохраняющим свою теоретическую и практическую значимость. Математическая логика – одна из дисциплин, составляющих теоретический фундамент информатики. Из логических исследований возникло понятие алгоритма, на котором базируется программирование, проектирование вычислительных машин и автоматизированных систем управления. В вычислительной технике и автоматике используются логические схемы – устройства, преобразующие двоичные сигналы. Логические методы применяются при построении баз данных. Важна роль логики в исследованиях по искусственному интеллекту и создании роботов. В настоящее время математическая логика внедряется в экономику и право, биологию и медицину, языкознание и психологию, статистику и комбинаторный анализ. Аппарат математической логики универсален. 1 Алгебра высказываний

Алгебра высказываний – раздел математической логики, занимающийся построением и преобразованием высказываний с помощью логических операций, а также изучающий свойства и отношения между ними. 1.1 Высказывания. Логические операции Под высказыванием понимается любое предложение (естественного или формализованного языка), содержание которого оценено либо как истинное, либо как ложное. Пример – Высказывание «Вода – продукт горения водорода» естественно считать истинным, а высказывание «Все числа вида 2n+1 – простые» - ложным. В логике высказываний каждое высказывание отождествляется с его истинностным значением: «истина» (1) или «ложь» (0). Само установление истинностного значения отдельно взятого высказывания в логике высказываний не производится. На множестве высказываний в логике высказываний задаются операции так, что истинностное значение результата однозначно определяется истинностными значениями операндов. Эти операции называются логическими операциями. Рассмотрим наиболее распространенные логические операции /1/. Отрицание – одноместная логическая операция  («не») – по высказыванию А определяет высказывание A («не А» или «неверно, что А»), которое считается истинным тогда и только тогда, когда А – ложно. Пример – А:=«Число 10 делится на 5», А:=«Неверно, что число 10 делится на 5». Отрицание обозначается также символом « ¬ » или надчёркиванием. Конъюнкция – двухместная логическая операция ∧ («и») – по высказываниям А, В определяет высказывание А ∧ В («А и В»), которое считается истинным тогда и только тогда, когда оба высказывания А, В истинны. Дизъюнкция – двухместная логическая операция ∨ («или») – по высказываниям A, B определяет высказывание A∨В («A или B»), которое считается истинным тогда и только тогда, когда хотя бы одно из высказываний A, B – истинно. Пример – A:= «Дождь кончился», B:= «Птицы запели», A ∨ B:= «Дождь кончился, или птицы запели». Импликация – двухместная логическая операция → («если…, то…») – по высказываниям А, В определяет высказывание А→В («если А, то В»), которое считается ложным тогда и только тогда, когда А - истинно, В – ложно. Пример – Пусть А:= «2*2=5» - ложно, В:= «Рим столица Италии» - истинно. Тогда A→Β:=”Если 2×2=5, то Рим – столица Италии” – истинно. В импликации А→В высказывание А называется посылкой, высказывание В – заключением. Из определения импликации следует, что в случае истинности обоих высказываний А, А→В высказывание В – истинно. Это соот-

ветствует основному из применяемых в математике правил вывода - Modus Ponens (Правило отделения). Эквиваленция – двухместная логическая операция ↔ («если и только если…, то…») определяет высказывание А ↔ В («если и только если А, то В»), которое считается истинным тогда и только тогда, когда А, В имеют одинаковые истинностные значения (оба истинны или оба ложны). Пример – «Квадратная матрица имеет обратную (А) если и только если определитель матрицы отличен от нуля (В)». Это высказывание истинно , если считать, что А, В истинны. Путем суперпозиции логических операций можно составлять все более сложные высказывания. Порядок выполнения операций устанавливается с помощью скобок и в соответствии с приоритетом операций:  , ∧, ∨, →, ↔ (в порядке убывания). Пример – Пусть А, В – ложны, тогда высказывание (А∨В)∧(А∨В) ложно. 1.2 Булевы функции. Истинностные таблицы Булева функция – n-местная функция из {0,1}n в {0,1}. Каждой nместной логической операции α взаимно однозначно соответствует n-местная булева функция yα=fα(x1,…,xn), x1,…,xn, y∈{0,1}, где двоичные переменные x1,…,xn, y соответствуют высказываниям (операндам и результанту) и называются пропозициональными переменными. Другие названия булевых функций: логические функции, функции истинности. Булеву функцию n переменных можно задать, таблицей истинности (таблица 1.1): Таблица 1.1 x1 0 0 … 1

… … … … …

xn 0 1 … 1

f (x1,…,xn) f (0,…,0) f (0,…,1) … f (1,…,1)

Каждый набор значений аргументов называется интерпретацией булевой функции, а ее соответствующее значение – истинностным значением. Если число переменных n, то число различных наборов значений аргументов равно 2n, а число различных булевых функций – 2 2 Булевы функции одной переменной: yi=fi(x), i=0..3 (таблица 1.2). Булевы функции двух переменных: yi=fi(x1,x2), i=0..15. Приведём таблицы некоторых двухместных булевых функций (таблица 1.3). n

Таблица 1.2 x1 0 1

y0=0 0 0

y1=x 0 1

y2= x 1 0

y3=1 1 1

Таблица 1.3 x1 x2 y0=0 y1=x1 ∧ x2 y6=x1+x2

0 0 0 0

0 1 0 0

1 0 0 0

0

1

1

y7=x1∨x2 y8=x1↓x2

0

1

1

1

0

0

y9=x1↔x2 y13=x1↔x2 y14=x1/x2

1 1

0 1

0 0

1

1

1

y15=1

1

1

1

1 Название фу1 нкции 0 Константа 0 Конъюнкция 1 Сложение по 0 модулю 2 Дизъюнкция 1 Стрелка Пир0 са Эквиваленция 1 Импликация 1 Штрих Шеф0 фера 1 Константа 1

При построении таблиц истинности более сложных высказываний нужно последовательно использовать таблицы истинности логических операций. Пример – Составить таблицу истинности для высказывания А ∨ В Решение даётся таблицей 1.4. Таблица 1.4 А 0 0 1 1

В 0 1 0 1

А 1 1 0 0

А∨В 1 1 0 1

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

Нормальная форма 2.1 Конъюнктивная нормальная форма

нормальная

форма.

Дизъюнктивная

 x, σ = 1, Пусть x – двоичная переменная. Введем обозначение x σ =   x, σ = 0. Тогда функции и x1σ ∧ ...∧ x n σ , x1σ ∨ ...∨ x n σ , где (σ1,…,σn) – двоичный набор, а x1,…, xn – двоичные переменные (не обязательно различные) называются соответственно элементарной конъюнкцией, элементарной дизъюнкцией. 1

Пример–Пусть Тогда

n

(σ1,

σ2,

1

n

σ3)=(0,1,1). x1 σ1 ∧ x 2 σ 2 ∧ x 3 σ 3 x1 ∧ x 2 ∧ x 3 -

элементарная конъюнкция. Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция элементарных конъюнкций. Пример - ( x1 ∧ x2 ) ∨ ( x1 ∧ x2 ) - дизъюнктивная нормальная форма. Конъюнктивной нормальной формой (КНФ) называется конъюнкция элементарных дизъюнкций. Путем тождественных преобразований любую булеву функцию можно привести к дизъюнктивной или конъюнктивной нормальным формам. Если исходная функция содержит только основные связки ( , ∧, ∨, →, ↔), то сначала нужно элиминировать связки с помощью равенств: x → y = x ∨ y, x ↔ y = ( x ∧ y ) ∨ ( x ∧ y ) = ( x ∨ y ) ∧ ( x ∧ y );

затем продвинуть знак отрицания к переменным с учетом равенств x ∧ y = x ∨ y , x ∨ y = x ∧ y;

устранить двойное отрицание, x = x. так как , Затем, используя одно из равенств: x∧(y∨z)=(x∧y)∨(x∧z), x∨(y∧z)=(x∨y)∧(x∨z) непосредственно получить дизъюнктивную или конъюнктивную нормальную форму. Пример – Дана булева функция: ( x1 → x 2 ) ↔ x3 . Выполним последовательно указанные преобразования: ( x1 → x 2 ) ↔ x 3 = (( x 1 ∨ x 2 ) ∨ x 3 ) ∧ (( x 1 ∨ x 2 ) ∨ x 3 ) = (( x1 ∧ x 2 ) ∨ x 3 ) ∧ (( x 1 ∨ x 2 ) ∨ x 3 ) = ( x 2 ∨ x 3 ) ∧ (( x 1 ∨ x 2 ) ∨ x 3 ) = ( x1 ∨ x 3 ) ∧ ( x 2 ∨ x 3 ) ∧ ( x 1 ∨ x 2 ∨ x 3 ). Получена конъюнктивная нормальная форма.

2.2 Совершенная нормальная форма. Теорема существования и единственности

Совершенной дизъюнктивной нормальной формой по переменным x1,…, xn называется дизъюнктивная нормальная форма, у которой все элементарные конъюнкции содержат каждую переменную ровно по одному разу (в прямом или инверсном виде), и все конъюнкции различны. Совершенной конъюнктивной нормальной формой по переменным x1,…, xn называется конъюнктивная нормальная форма, у которой все элементарные дизъюнкции содержат каждую переменную ровно по одному разу (в прямом или инверсном виде), и все дизъюнкции различны. Пример - (x1 ∧ x2 ) ∨ ( x1 ∧ x2 ) - совершенная конъюнктивная нормальная форма по x 1 , x2 .

Теорема (существования и единственности) Для любой n-местной булевой функции f(x1,…, xn)≢ 0 существует единственная совершенная дизъюнктивная нормальная форма, реализующая эту функцию, и существует единственная совершенная конъюнктивная нормальная форма, реализующая эту функцию. Доказательство Проверим выполнение следующего тождества по двоичным переменным x1,…, xn: δ1

δn

f ( x x ,..., x n ) ≡ ∨ (δ ,...,δ ) f (δ 1 ,..., δ n ) ∧ x1 ∧ ... ∧ x n , 1

(2.1)

n

где правая часть есть дизъюнкция (по всем двоичным наборам (δ1,… , δn)) функций δ δ F (δ 1 ,..., δ n ) = f (δ 1 ,..., δ n ) ∧ x1 1 ∧ ... ∧ xn n . Пусть (x1,…, xn)=(σ1,…, σn) ∈ ｛0,1｝n. Слева имеем f (σ1,…, σn). Замеσ 1 δ ∧ ... ∧ σ n δ = 1 тим, что для правой части будет выполняться равенство тогда и только тогда, когда (δ1,…,δn)=(σ1,…, σn). Это означает, что дизъюнктивные члены правой части, для которых (δ1,…,δn)≠(σ1,…, σn), можно опустить. Правая часть становится равной f(σ1,…, σn) ∧1=f(σ1,…, σn). Итак, слева и справа в (2.1) имеем f(σ1,…, σn). Если f(x1,…, xn) ≢ 0, то формула (2.1) эквивалентна формуле 1

f ( x1 ,..., x n ) ≡ ∨ (δ ,...,δ 1

δ1

n ) f ( δ 1 ,...,δ n ) =1

n

δn

( x1 ∧ ... ∧ x n ).

(2.2)

Выражение справа есть совершенная дизъюнктивная нормальная форма. Существование совершенной дизъюнктивной нормальной формы доказано. Единственность доказывается от противного. Для булевой функции f(x1,…,xn) по тождеству (1) имеем:

f(x 1,…,x n) = ∨ (δ 1,…,δ n ) (f(δ 1,…,δ n) ∧ (x 1δ 1,…,x nδ n)

(2.3)

Взяв отрицание от обеих частей (2.3) и проведя тождественные преобразования, получим: f(x1,…xn)= ∧ (δ1,…,δn) (f(δ1,…,δn)∨ x1δ1∨…xnδn)

(2.4)

Если f(x1,…, xn) ≢ 1, то справедливо тождество: δ

f ( x1 ,..., x n ) ≡ ∧ ( δ

1 ,...,δ n ) f(д1 ,...,дn ) = 0

( x1 1 ∨ ... ∨ x n

δn

)

(2.5)

Выражение в правой части (2.5) является совершенной конъюнктивной нормальной формой. Существование совершенной конъюнктивной нормальной формы доказано. Единственность также имеет место. Теорема дает способы построения совершенной нормальной формы. Пример –Пусть булева функция y=f(x1,x2,x3) задана таблицей 1.5. Таблица 1.5 x1 x2 x3 Y

0000 0011 0101 0110

1111 0011 0101 1001

Тогда СДНФ и СКНФ – имеют соответственно вид: ( x1 ∨ x2 ∨ x3 ) ∧ ( x1 ∨ x 2 ∨ x 3 ) ∧ ( x1 ∨ x2 ∨ x 3 ) ∧ ( x1 ∨ x 2 ∨ x3 ); ( x 1 ∧ x 2 ∧ x 3 ) ∨ ( x 1 ∧ x 2 ∧ x 3 ) ∨ ( x1 ∧ x 2 ∧ x 3 ) ∨ ( x1 ∧ x 2 ∧ x 3 ). Следствие Любая булева функция выразима через функции:  , ∧, ∨. Функциональная полнота

Система функций называется полной в некотором множестве, если любая функция этого множества может быть представлена суперпозицией функций из указанной системы. Примеры полных систем в множестве булевых функций: 1) , ∧, ∨; 2)  , ∧; 3) , ∨; 4)↓; 5) ⁄. Две последние системы содержат по одной функции, которые называются соответственно Стрелка Пирса и Штрих Шеффера. Имеют место равенства:

x1 ↓ x2 = x1 ∨ x2 = x1 ∧ x2 ,

которые можно x1 / x2 = x1 ∧ x2 = x1 ∨ x2 , функций.

принять за определение этих

2.3 Применение алгебры высказываний к описанию релейноконтактных схем (РКС)

Под релейно-контактными схемами понимают схематическое изображение какого-либо устройства, состоящего из соединенных между собой двухпозиционных переключателей. Двухпозиционные переключатели могут находиться в двух состояниях: в замкнутом (ток проходит) и в разомкнутом (ток не проходит). Такие схемы можно описать в терминах алгебры высказываний. Каждому переключателю ставиться в соответствие высказывание, истинное при замкнутом переключателе и ложное – при разомкнутом. При этом удобно переключатели обозначать теми же буквами, что и высказывания. Если два переключателя работают так, что один из них замкнут, когда другой разомкнут, и наоборот, то они обозначаются соответственно А и Ā. Параллельному соединению переключателей будет, очевидно, соответствовать дизъюнкция высказываний, последовательному – конъюнкция. Переключательной схеме – так еще называют релейно-контактную схему - будет соответствовать сложное высказывание, истинное тогда и только тогда, когда схема проводит ток. Если высказывание упростить, то и схему можно аналогично упростить. Из двух схем более простой считается схема с меньшим числом переключателей. Пример – Упростить схему (рисунок 2.1).

А1

А2

А3 А1

А2

А3

А1

А2

А3

Рисунок 2.1

Решение Составляем по схеме высказывание и упрощаем его: (( А1 ∨ А3 ) ∧ А2 ) ∨ ( А1 ∧ А2 ∧ А2 ) ∨ ( А1 ∧ А2 ∧ А3 ) = ( А1 ∧ А2 ) ∨ ( А3 ∧ А2 ) ∨ ( А1 ∨ А1 ) ∧ ( А2 ∧ А3 ) = ( А1 ∧ А2 ) ∨ А3 ∧ ( А2 ∨ А2 ) = ( А1 ∧ А2 ) ∨ А3

Упрощенная схема (рисунок 2.2) имеет три переключателя вместо девяти в исходной.

А1

А2 А3 Рисунок 2.2

Алгебра предикатов

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

N-местным предикатом на множестве M называется n-местная функция Р(x1,…, xn), аргументы которой принимают значение из множества M, а сама функция принимает значения из множества {0(«ложь»), 1(«истина»)}. При n=1 предикаты называются унарными, n=2 – бинарными, n=3 - тернарными и т.д. Нульместный предикат рассматривается как высказывание. Предикат задает отношение нам. Примеры 1 M={1,2,3,…} – множество натуральных чисел; а) Р(x):= «x делится на 2». Р(2)= «истина», Р(3)= «ложь»; б) Р(x1, x2): «x1≥ x2». Р(1,2)= «ложь», Р(3,2)= «истина». 2 M=R=(-∞,+∞) – множество действительных чисел : Р(x1, x2, x3)= «истина», x1+x2+x3=1, «ложь», в противном случае; Р(1,0,0)=«истина»,Р(0,0,0)=«ложь» и т.д. Предикат Р(x1,…, xn), определенный на M, называется тождественно истинным на M, если определяющая его функция Р(x1,…, xn)≡1; тождественно ложным, если Р(x1,…, xn)≡0, выполнимым, если Р(x1,…, xn)≢ 0. Пример – Предикат Р(x):= «|х|>0», определенный на R, тождественно истинен на R. Предикаты называются равносильными, если они тождественно равны между собой как функции. Определенные элементы a1, a2,… из M называются предметными постоянными, а неопределенные элементы x1,…, xn из M – предметными переменны-

ми. При замещении предметной переменной хк, к∈1..n, предметной постоянной а∈M n-местный предикат Р(x1,…, xn) превращается в (n-1) местный предикат Р(х1,…,хк-1,a,хк+1,…,хn) и от хк уже не зависит. Если заместить все переменные постоянными, то получится высказывание, или нульместный предикат. Пример - Р(x1, x2, x3):= «x1+x2=x3» - трехместный предикат; Р(x1, x2, 5):= «x1+x2=5» - двухместный предикат; Р(2,3,5):= «2+3=5» - высказывание. N-местным функтором на множестве M называется n-местная функция f(x1,…, xu), принимающая, как и аргументы, значения из множества M (то есть n-местный функтор задает n-местную операцию на M). 3.2 Операции над предикатами. Кванторы

Пусть Р(х), Q(x), х∈М, для которых предикат Р(х) ложен. Отрицанием предиката Р(х) на множестве M называется предикат  Р(х) на том же множестве, истинный для тех и только тех значений х∈М, для которых предикат Р(х) ложен. Конъюнкцией предикатов Р(х), Q(x) на множестве M называется предикат Р(х)∧Q(x) на том же множестве, истинный для тех и только тех значений х∈М, для которых оба предиката Р(х), Q(x) истинны. Дизъюнкцией предикатов Р(х), Q(x) на множестве M называется предикат Р(х)∨Q(x) на том же множестве, истинный для тех и только тех значений х∈М, для которых истинен хотя бы один из предикатов Р(х), Q(x). Подобным образом вводятся предикаты Р(х) →Q(x), Р(х)↔Q(x). Пример – Даны предикаты: Р(х):= «х<5», Q(x):= «х≥2», х∈{1,2,3,4,5} =М. Тогда Р(х):= «х≥5», Р(х)∧Q(x):=«2≤х<5»; Р(1)∧Q(1)=0, Р(2)∧Q(2)=1. Над многоместными предикатами операции определяются аналогичным образом. Так, отрицанием n-местного предиката на некотором множестве М называется n-местный предикат Р(x1,…, xn) на том же множестве М, истинный для тех и только тех наборов значений аргументов, для которых предикат Р(x1,…, xn) ложен. Для предикатов вводится также специфические логические операции, или кванторы, - ∀ («каждый» или «для всех») – квантор общности и ∃ («существует» или «для некоторых») – квантор единичности. Пусть Р(х), х∈М – одноместный предикат. Тогда запись ∀х Р(х) («для любого х Р(х)») означает высказывание, истинное, если Р(х) – тождественно истинен на М, и ложное, если Р(х) не является тождественно истинным на М; запись ∃х Р(х) («существует х такой, что Р(х)») означает высказывание, истинное, если Р(х) выполним на М, и ложное, если Р(х) невыполним на М. Пример – Если Р(х):= «х2=1», х∈М=(-∞,+∞), то ∀х Р(х)=0, ∃х Р(х)=1. Специфические равносильности:

∀ хР( х) = ∃х Р( х), ∃ хР( х) = ∀ х Р( х).

Дадим определение квантификации для многоместных предикатов.

Пусть Р(х, х1,…,хn) – (n+1) – местный предикат, определенный на множестве M (n≥0). Тогда запись ∀х Р(х, х1,…,хn) означает n – местный предикат на М, зависящий от х1,…,хn (и не зависящий от х) и принимающий значение «истина» для тех и только тех значений а1,…,аn∈М переменных х1,…,хn, для которых одноместный предикат Р(х, а1,…,аn) является тождественно истинным на М; запись ∃х Р(х, х1,…,хn) означает n-местный предикат на М, зависящий от х1,…,хn (и независящий от х) и принимающий значение «истина» для тех и только тех значений а1,…,аn∈М переменных х1,…,хn, для которых одноместный предикат Р(х, а1,…,аn) является выполнимым на М. Предикат Р в записях ∀х Р ∃х Р называется областью действия квантора. Пример – Пусть Р(х,у):= «х<у», х, у∈R – двухместный предикат на множестве действительных чисел. Тогда предикаты ∀х (x
Таблица 2.2

1

2

x

1

1

2

2

x f

2

1

у

1

2

1

2

Р

0

1

Q

1

1

0

1

(х) (х) Решение В результате подстановки значения константы получаем высказывание ∀х(Р(х) → Q(f (х), 1). Строим вспомогательную таблицу 2.3. Таблица 2.3 х Q(f(х),1)

1 0

2 1

Р(х)→Q(f(х)

1

1

,1) По последней строке заключаем, что исходное высказывание имеет значение 1 в заданных условиях. 3.3 Термы. Атомы

Константы, переменные или функторы называются термами. Предикат, аргументами которого являются термы, называется также атомом. 3.4 Свободные и связанные вхождения переменных

Вхождения переменных в атом называются свободными. Свободные вхождения переменных в предикаты Р и Q остаются свободными в предикатах Р, Р→Q. Вхождение переменой в предикат ∀хР и ∃хР называются связанными. Если вхождения переменных (отличных от х) были свободными в предикате Р, то они остаются свободными и в предикатах ∀хР и ∃хР. Одна и также переменная может иметь в одном и том же предикате как свободные, так и связанные вхождения. Вхождение х в цепочку ∀х, ∃х, считается связанным. 1 В предикате ∀х(Р(х,у)∨∃уQ(у)∨ R(х) первое и второе вхождения переменной х связаны, третье - свободно, переменная у связана. 2 Дан предикат ∀х(Р(х,у,z)→∃уQ(х,у)∨ Q(х,у)∧ S . Здесь Р(х,у,z) - трехместный, Q(х,у) - двухместный, S - нульместный предикаты. Требуется определить истинностное значение данного предиката при условиях: М={a, b}; S = 0; свободные вхождения переменных заменяются значениями -х=b, у=а, z=a; предикаты Р, Q заданы таблицей 2.4. Таблица 2.4 х

a

a

a

a

b

b

b

b

у

a

a

b

b

a

a

b

b

z

a

b

a

b

a

b

a

b

Р

0

1

1

0

0

1

0

1

Q

0

0

0

0

0

0

1

1

Решение Подставляя значение свободных предметных переменных и значение предиката S, получим высказывание ∀х(Р(х,а,а)→ ∃уQ(х,у)∨Q(b,а) ∧1, которое в силу Q(b, а)=0 заменяется на высказывание ∀х(Р(х,а,а→∃у Q(х,у).

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

P(х,а,а)

а b

0 0

→ у)

∃уQ(х,

0 1

4 Формальные теории 4.1 Определение формальной теории

Формальная теория (ФТ) - это четверка Т = (S, F, А, R) /2/, где S - алфавит - множество символов; F - множество формул - множество правильно построенных цепочек символов из S; А - множество аксиом подмножество множества F; R - множество правил вывода - множество отношений ρ на множестве F. Множество S может быть конечным или бесконечным. Множество F чаще всего бесконечно, задается синтаксическими правилами. S и F в совокупности определяют язык формальной теории. Множество А может быть конечным или бесконечным; если бесконечно, то задается схемами и правилами их конкретизации. Множество R обычно конечно; будет предполагаться, что ρ ⊂ F n+1 (при некотором n) , где Fn+1 - (n+1)-ая декартова степень множества F. 4.2 Выводимость. Разрешимость

Пусть F1, ..., Fn, G- формула формальной теории Т, то есть F1,..., Fn,G∈F и пусть имеется правило ρ ∈ R такое, что (F1, …, Fn, G) ∈ ρ . Тогда формула G называется непосредственно выводимой из формул F1, ..., Fn по правилу ρ. F ,..., Fn ρ , при этом формулы F1, ...., Fn называются посылками, Запись: 1 G а формула G - заключением. Формула G называется выводимой из формул F1, ..., Fn, в формальной теории Т, если существует последовательность формул Е1 , ...., Ek такая, что Еk= G, а любая из Еi, i = 1 ...(k - 1), есть либо аксиома, либо одна из исходных формул F1,...,Fn, либо непосредственно выводима из подмножества ранее полученных формул Ej1,…, Ej1, j1,...,jl < i. Последовательность Е1, ...., Еk называется при этом выводом формулы G из формул F1, ... , Fn в теории Т. Запись: F1, ...,Fn |−…G; формулы F1, ..., Fn, называются гипотезами, формула G - тезисом. Знак теории Т можно опускать. Формула, выводимая только из аксиом, называется теоремой теории Т. Запись: |− G (множество гипотез пусто). При добавлении гипотез выводимость сохраняется, то есть если Г («гамма») и ∆ («дельта») - множества формул, причем Г|− TG, то есть Г, ∆ |− T G. Примечание - По отношению к теоремам формальной теории теоремы о формальной теории называются метатеоремами. Формальная теория называется разрешимой, если существует алгоритм, который для любой формулы определяет, является или нет эта формула теоремой теории. Формальная теория называется полуразрешимой, если существует алгоритм, который для любой теоремы дает ответ «да», а для формулы, не являю-

щейся теоремой, либо лает ответ «нет», либо не дает никакого ответа (то есть алгоритм применим (может быть, не ко всем формулам). 4.3 Интерпретация формальных теорий

Интерпретацией I формальной теории Т в область интерпретации Ω называется отображение всех множеств и отношений на них формальной теории Т в множество объектов и связей между ними области Ω. Это отображение должно удовлетворять условию: каждой формуле в Т соответствует высказывание в Ω. Если соответствующее высказывание в Ω является истинным, то говорят, что формула теории Т истинна в данной интерпретации. Интерпретация I называется моделью формальной теории Т, если все теоремы этой теории выполняются в интерпретации I (то есть для всех выводимых из аксиом формул теории Т соответствующие высказывания в области Ω истинны). Формула формальной теории называется тождественно истинной, или тавтологией, если она истинна в любой интерпретации. Формула формальной теории называется тождественно ложной, или противоречием, если она ложна в любой интерпретации. Формула называется выполнимой, если она истинна в некоторой интерпретации. 4.4 Непротиворечивость. Полнота. Независимость

Формальная теория называется непротиворечивой, если в ней не являются одновременно выводимыми формула F и  F. Формальная теория называется полной, если каждому истинному высказыванию в Ω соответствует теорема теории Т. Система аксиом непротиворечивой теории Г называется независимой, ес ли никакая из аксиом не выводима из остальных по правилам вывода теории Т. 5 Исчисление высказываний

Задача исчисления высказываний (ИВ) - описание всех тождественно истинных формул. 5.1 Определение ИВ

Классическое ИВ - это формальная теория L, в которой: - алфавит есть множество символов: 1) а, b, ..., а1 , b1 , ...- (пропозициональные) переменные; 2) , → - связки; 3) ( , ) - служебные символы; - множество формул есть множество цепочек символов, задаваемых синтаксическими правилами:

1) переменные есть (пропозициональные) формулы; 2) если А,В - формулы, то ( А), (А →В) - формулы; - множество аксиом задается схемами (один из вариантов): А1: = (А→ (В → А); А2: = ((А → (В →С )) → ((А →В) → (А→С)): А3: = (( В→ А) → ((В →А→ В)); A, A → B MP (Modus Ponens), -множество правил задается схемой: B где А, В, … - любые формулы. Для получения конкретных правил и аксиом используются подстановки формул вместо метасимволов А, В, .... Знак подстановки: «/». В дальнейшем используются синтаксические сокращения: А∧В: =  (А→  В); А, ∨, В:=  А → В. 5.2 Выводимость. Производные правила вывода

Выводимость формул в L, как в ФT, доказывается путем построения соответствующего вывода. Формулы вывода будем записывать в столбец, а справа - указывать основание для включения этих формул в вывод. В качестве примера рассмотрим вывод из аксиом. Теорема 5.1 |−LА→ А. Доказательствo 1) (А → ((А →А) → А)); А1: {А → А/В}; 2) ((А → ((А→ А) →А)) → ((А → (АА))(A→A)); А2: {А → АВ, А/С}; 3) ((А → (А → А )) → (А → А)); МР: 1,2; 4) А → (А → А); А1: {A /В}; 5) А → А; МР: 4,3 Всякую доказанную выводимость можно использовать как новое, производное правило вывода. Теорема 5.2 A|−LB→ А. Доказательство: 1) А; гипотеза; 2) А → (В →В); A1; 3) В → А; МР: 1,2. A I mp ─ правило введения импликации. Доказана выводимость B→A 5.3 Теорема дедукции

Теорема Если Г, А |−L ...В1, то Г |−L... А → В и обратно. Здесь Г - некоторое множество формул. Доказательство прямой теоремы. Пусть Е1 ..., Еn – вывод - В из Г, А. При этом Еn =В. Применяя метод математической индукции по i (1 ≤ i ≤ n), то есть

покажем, что Г|−L А→Еi; тогда при i =n прямая теорема будет доказана. Итак, пусть i = 1 (база индукции). Рассмотрим вывод: 1) Е1; аксиома или посылка: 2) Е1 → (А → Е1); А1:{А/В, Е1 /А}; 3) А → Е1; МР: 1,2. То есть Г|−LА → Е1 Далее по методу предположим, что Г|−LА → Еi для всех i < k и рассмотрим Ek.. Здесь возможны случаи: либо Ek аксиома или посылка, тогда доказательство повторяет предыдущее, либо Еk получена по правилу МР из Ei, Ej; причем i, j < k, и Ej: = Еi → Еk. В последнем случае, так как i, j < k , то для Ei , Ej имеются выводы Г|−LА → Еi и Г|−LА → (Еi → Еk ). Объединим эти выводы в один и достроим его до требуемого вывода: α1) A → Ei; α2) A → (Ei → Ek); α3) (A → (Ei → Ek)) →((A → Ei) → (A → Ek)); A2: {Ej./В, Ek /Сj}; α4) (А → Еi) → (А →Аk); МР: α2 α3; α5) A → Ek МР: α1 α4. Итак, для Ek вывод построен. Тогда по методу математической индукции заключаем, что для любого n имеет место выводимость Г|−LА → Еn. Поскольку Еn:=В, то Г|−LА→B. Прямая теорема доказана. Доказательство обратной теоремы. Пусть имеем вывод Г|−LА → B, состоящий из β формул. Достроим его: β 1) А → В; β 2) А; гипотеза; β 3) В; МР: β 2, β 3. Таким образом, имеет место выводимость Г|−LА→B. Обратная теорема доказана. Теорема доказана. Cледствие Если А|−LВ, то |−L A → В и обратно. Доказательство Г: =∅. 5.4 Применение ТД

Теорема 5.3 Имеет место выводимость: А → В, В → С|−LА → С. Доказательство Сначала докажем выводимость А → В, В → С|−L → С: 1) А → В; гипотеза; 2) В → С; гипотеза; 3) А; гипотеза; 4) В; МР: 3,1; 5) С; МР: 4,2. Вывод для С построен. Теперь по теореме дедукции заключаем, что А → В, В → С|−LА → С. Теорема доказана. Эта теорема дает производное правило A → B, B → C Tr , называемое правилом транзитивности: A→C

Теорема 5.4 Имеет место выводимость: А → (В → С), В |−L А → С. Доказательство Сначала доказываем выводимость А→(В→С), В,А|−LС: 1) A → (В → С); гипотеза; 2) А; гипотеза; 3) В→ С; МР: 2,1; 4) В; гипотеза; 5) С; МР: 4,3. Вывод для С построен. Теперь по теореме дедукции заключаем, что имеет место выводимость А → (В → С), В|−L А → С. Теорема доказана. Теорема A → ( B → C ), B Sec ─ правило сечения. дает производное правило A→C

6 Интерпретация исчисления высказываний 6.1 Интерпретация высказываний

исчисления

высказываний

в

алгебру

Интерпретация ИВ в алгебру высказываний задается приписыванием в качестве значений: -каждой пропозициональной переменной конкретного высказывания (с его истинным значением); -каждой связке - соответствующей логической операции (с сохранением приоритета). В результате интерпретации формула ИВ становится высказыванием, истинностное значение которого вычисляется в соответствии со структурой формулы и определением логических операций. «Лишние» скобки можно опускать. Формула называется истинной в данной интерпретации, если соответствующее ей высказывание истинно; ложное - в противном случае. 6.2 Равносильные формулы

Две формулы ИВ называются равносильными, если они имеют одинаковые истинностные значения во всех интерпретациях. Запись: А=В («А равносильно В»). Имеют место следующие равносильности: 1 Коммутативность конъюнкции, дизъюнкции: А ∧ В = В ∧ А, А ∨ В= В ∨ А. 2 Ассоциативность конъюнкции, дизъюнкции: А ∧ (В ∧ С)= (А ∧ B) ∧ C, А ∨ (В ∨ С) = (А ∨ В) ∨ С. 3 Дистрибутивность конъюнкции относительно дизъюнкции, дизъюнкции относительно конъюнкции: А∧(В∨С) = (А∧В)∨(А∧C)=(A∨(В∧С)=(А∨D)∧(А∨С). 4 Законы де Моргана: A ∧ B = A ∨ B, A ∨ B= A ∧ B, 5 Закон двойного отрицания.

A = A.

6 Закон исключенного третьего, закон противоречия: А ∨ A =1, А ∧ A =0. 7 Закон идемпотентности: А ∧ А = А, А ∨ А = А. 8 Законы поглощения: А ∧ (А ∨ В) = А, А ∨ (А ∧ В)=А. 9 Элиминация импликации и эквивалентности:

A → B = A ∨ B, A ↔ B = (A → B) ∧ (B → A) = (A ∧ B) ∨ (A ∧ B) 10 Законы констант: А ∧ 1 =А, А ∨ 1= 1, 1 = 0 , А ∧ 0 = 0, A ∧ 1 = A, 0 = 1. Все равносильности можно проверить таблично. Заметим, что свойство 2 позволяет бесcкобочные записи А1 ∧…∧ An или А1 ∨ ...∨ Аn. Пример - В соответствии с определением основных логических операций ( и соответствующих им БФ) составим таблицу 6.1.Сравнивая столбцы для A ∨ B и A ∧ B , заключаем, что A ∨ B = A ∧ B , то есть выполнен один из законов де Моргана. Используя имеющиеся равносильности, можно преобразовать одни формулы в другие, равносильные им (путем соответствующей замены формул и подформул). Таблица 6.1 А

В

А

A

A

B

A

0 1 1 1

1 0 0 0

1 1 0 0

1 0 1 0

1 0 0 0

∨В

0 0 1 1

0 1 0 1

7 Классификация формул логики высказываний 7.1 Типы формул

Формула в ЛВ называется тождественно-истинной, или тавтологией, если она истинна в любой интерпретации Формула ЛВ называется тождественно-ложной, или противоречием, если она ложна в любой интерпретации. Очевидно, формула тождественно истинна тогда и только тогда, когда  А тождественно ложна. Формула ЛВ называется выполнимой если она истинна хотя бы в одной интерпретации. Пример – Формула Р → P выполнима, так как, например 0 → 1 = 1. Основные примеры тавтологий: Р → Р (закон тождества); P ∨ P (закон исключенного третьего); P ∧ P (закон противоречия); P ↔ P (закон двойного отрицания); P → (Q → Р) (истина из чего угодно); P → (P →Q) (из лжи что угодно); (Р →Q) ∧ Р → Q (Modus Ponens); (Р → Q) ∧ Q → P (Modus Tollens); (Р → Q) ∧ (Q →R) → (Р →R) (закон силлогизма); (Р → Q) → (Q → P ) (закон контрапозиции). Эти тавтологии называются законами АВ, поскольку они тождественно истинны (для любых высказываний Р, Q, R,..) в силу своей структуры, и их можно рассматривать как схемы правильных умозаключений. Пример - Составить таблицу истинности для следующего высказывания: (P → Q) ↔ (Q → P) . Решение даётся таблицей 7.1. 7.2 Логическое следствие. Логическая эквивалентность

Формула ЛВ называется логическим следствием формулы А, если В истинна во всех интерпретациях, в которых А истинна. Запись: А ⇒ В («из А логически следует В»). Пример - Имеет место логическое следование Р ⇒ (Q → Р) (Таблица 7.1). Доказательство. Если Р=1, то как известно, Q→Р=1 при любом Q (0→1=1,1→1=1).Тогда имеем очевидное следование 1 ⇒ 1. Теорема Для того, чтобы А ⇒ В необходимо и достаточно, чтобы формула А → В были тавтологией.

Доказательство Необходимость Пусть А ⇒ В. Тогда по определению логического следствия, если А = 1, то В = 1, то есть невозможен набор (А, В) = (1, 0). Это означает по определению импликации, что А → В - тавтология. Таблица 7.1 Р

Р

Q

Q

( P → Q) ↔ (Q

1 1 0 1

1 0 1 0

1 1 0 1

1 1 1 1

→Q 0 0

0 0

Достаточность Пусть А → В – тавтология. Это означает, что (А, В) ≠ (1, 0), то есть , если А = 1, то В = 1. Тогда по определению логического следствия А ⇒ В. Теорема доказана. Формула В называется логическим следствием формул А1, …Аn, если В является логическим следствием формулы А1 ∧…∧ Аn, то есть А1 ∧…∧ Аn⇒ В. Запись: А1, ..., Аn ⇒ В. Теорема Для того, чтобы А1 ∧…∧ Аn⇒ В, необходимо и достаточно, чтобы формула А1 ∧…∧ Аn ∧ В была противоречием. 7.3 Подстановка

Если А - некоторая формула, в которую входит подформула В, то применяется запись: А (...В...). Если С - некоторая формула, которую подставляют формулу А вместо всех вхождений В, то применяется запись: А (...В...) {С//В}. В случае подстановки необязательно всех вхождений символ «//» заменяется на «/». Теорема 7.1 Если А (...х...) – тавтология и С - любая формула, то А (...х...) {С//х } – тавтология. Здесь В: =х). Теорема 7.2 Если А (...В...) и С = В («равносильно»), то А (...В...) = А (...В...) {С/ В }. Доказательство проводится путем анализа интерпретаций формул. Две формулы логики высказываний называются логически эквивалентными, если каждая из них является логическим следствием другой. Запись: А ⇔ В («А логически эквивалентно В»). Теорема Для того, чтобы А ⇒ В необходимо и достаточно, чтобы формула А ↔ В была тавтологией. Доказательство. Если А = 1, то из А ⇒ В следует, что В = 1. Если В = 1, то из В ⇒ А следует, что А = 1 (по одной из двух предыдущих теорем). Это означает, что А = 1, тогда и только тогда, когда В = 1, то есть А = В во всех интерпретациях, и по определению эквиваленции А ↔ В = 1 во всех интерпретациях. Теорема доказана.

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

8 Применение алгебры высказываний к доказательству

теорем математики Многие теоремы математики имеют форму импликации, а допущениями служат аксиомы развиваемой теории. Схемно эту ситуацию представим в виде: А1,…, Аm ⇒ А → В,

(8.1)

где А1, …, Аm – аксиомы, А → В - теорема (не высказывание). 8.1 Теоремы прямая и обратная

Теоремы вида А → В и В → А называются взаимно-обратными. В конкретной ситуации одну из них называют прямой, другую – обратной. Очевидно, обратная обратной есть исходная теорема. Это означает, что если взять, например, за исходную теорему А → В, то обратная ей будет В → А, обратная к последней будет снова А → В. Для любой пары взаимно- обратных теорем может наблюдаться один из случаев: а) обе теоремы верны; б) прямая теорема верна, обратная неверна; в) прямая неверна, обратная верна; г) обе теоремы неверны. Примеры 1 Пусть А:=«Число делится на 4»; В:=«Число делится на 2». Тогда прямая теорема А → В верна, обратная В → А неверна. 2 Пусть А: = «Фигура есть квадрат», В: = «Фигура есть ромб». Тогда и прямая и обратная теоремы неверны. Если теорема А → В верна, то А называется достаточным условием для В, а В – необходимым условием для А. Если верны и прямая, и обратная теоремы, то каждое из А , В является необходимым и достаточным для другого. Пример - Если А:=«Число делится на 3», В:=«Сумма цифр числа делится на 3», то А есть необходимое и достаточное условие для В. Теоремы противоположная и обратная противоположной

Теоремы вида А → В и В → А называются взаимно противоположными. Пример - Если А → В:=«Если функция дифференцируема (А), то она непрерывна (В)», то А → В:=«Если функция не является дифференцируемой (А), то она не является непрерывной (В)». Как известно, в данном случае теорема А→В верна, теорема А→В неверна.

Закон контрапозиции

Пусть А → В – прямая теорема. Ей соответствуют теоремы: В → А – обратная теорема, А → В – противоположная, B → A обратная противоположной. Теорема Если прямая теорема верна, то верна обратная противоположной. Обратно, если теорема, обратная противоположной верна, то прямая верна. Доказательство Известна тавтология (А → В) → (В → А) – (закон контрапозиции, - то есть (А → В) ⇒ ( B → A ), и первая часть теоремы доказана. Для B , A эта часть теоремы принимает вид B → A → (А→В) – тавтология, и вторая часть, а вместе с ней теорема доказана. Примечание - Теорема о теоремах называется метатеоремой по отношению к этим теоремам. Методы математических доказательств

Обратимся к схеме (8.1). Обычный способ доказательства теоремы А → В состоит в том, что А принимают в качестве еще одного допущения, то есть приходят к схеме: А1, …, Аn , А ⇒ В (8.2) Основанием для такого перехода служат равносильности: А1 ∧ … ∧ Аn → (А → В)= A1 ∨ …∨ An ∨ A ∨ B = А1∧ … ∧ Аn ∧ А → В. По способу проведения доказательства в математике делятся на два вида: прямое доказательство (доказательство теоремы в предложенной формулировке, или прямой теоремы) и доказательство от противного (то есть доказательство теоремы, обратной противоположной).

9 Свойства исчисления высказываний 9.1 Полнота

Имеют место следующие метатеоремы. Теорема 9.1 Всякая теорема исчисления высказываний есть тавтология. Теорема 9.2 Всякая тавтология является теоремой исчисления высказываний . Таким образом, теоремами теории L являются тождества - истинные формулы и только они. А это означает, что формальная теория L, то есть классическое исчисления высказываний, является полной. 9.2 Непротиворечивость

Из теоремы 9.1 следует, что теория L непротиворечива. Действительно. Любая теорема в L есть тавтология. Отрицание тавтологии не есть тавтология, то есть в L нет одновременной выводимости теоремы и ее отрицания, что соответствует определению непротиворечивости формальной теории. 9.3 Разрешимость

Теория L разрешима как формальная теория. Алгоритм, который определяет для любой формулы теории, является ли эта формула теоремой теории, может состоять в вычислении истинностных значений формулы в каждой интерпретации. Принципиально это выполнимо за конечное время в силу конечности числа интерпретаций и числа операций, присутствующих в формуле. 9.4 Исследование системы аксиом ИВ. Независимость

Подмножество α множества всех аксиом данной ФТ называется независимым, если ни одна из формул α не может быть выведена с помощью правил вывода из аксиом, не входящих в α. Известно, что каждая из схем аксиом А1, А2, А3 независима. Эта система аксиом предложена П.С. Новиковым; она весьма проста, но существует много других систем, работающих тоже хорошо. Примеры 1 Гильберт, Аккерман, 1938: - связки: ∨,  ; - аксиомы: А∨А → А; А → А∨В; А∨В → В∨А, (В → С) → (А∨В → А∨С); -правило: Modus Ponens. 2 Россер, 1953: - связки:∨,  ; - аксиомы: А → А ∧ А; А → А ∧ В → А; (А → В) → ( ( В∧ С) → (С∧ А); -правило: Modus Ponens.

3 Клини, 1952: связки:  , ∧ , ∨ , → ; - аксиомы: А → (В→ А) ; А→ (В→С)) → ((А→В) → (А → С); А ∧ В → А; А ∧ В → А; А→ (В → (А∧В)); А→ (А∨ В) ; В → (А∨ В); А→ С) → ( (В→С) →( ( А∨ В) → С )); (А →В) → ( ( А→  В) →  А ) ; А→А; -правило: Modus Ponens.

10 Исчисление предикатов

Задача исчисления предикатов (ИП) – описание всех тождественно- истинных предикатных формул. 10.1 Определение исчисления предикатов

Классическое исчисление предикатов первого порядка- это формальная теория К, в которой: -алфавит есть множество символов: 1)a,b, …, a1,b1, …, и x,y,…,x1,y1,… - (предметные) константы и предметные переменные соответственно; 2)Ρn , Qn , …,Ρ1n, Q1n, … и fn, gn , …, f1n, g1n, …, n= 0, 1,2, …) – n – местные (предметные) предикатные переменные и (предметные) функциональные переменные соответственно; 3) , → - связки; 4) ∀ , ∃ - кванторы; 5)(,) , , - служебные символы; -множество формул есть множество цепочек символов, задаваемых синтаксическими правилами: 1)(предметные) константы и (предметные) переменные, как цепочки, суть термы; 2) если t1,…,tn – термы, fn- n –местная функциональная переменная, то цепочка fn (t1,…,tn) – терм; 3)если t1,…,tn – термы, Pn – n – местная предикатная переменная, то цепочка Pn(t1,…,tn) – атом; 4)атом есть формула; 5)если F, G - формула, x – ( предметная) переменная, то цепочки ( F), (∀x F), ( ∃ x F), (F→ G) – тоже формулы; -множество аксиом ( один из вариантов) задается схемами: 1)схемы вида А1, А2, А3 исчисления высказываний (но с предикатными формулами); 2) P1: = ∀ x F(F(→ F( t); P2: = F( t) → ∃ x ∃(x), где t-терм, свободный для переменной x в формуле F; -множество правил вывода задается схемами: F, F → G MP, G G → F ( x) 2) R∀, G → ∀xF ( x)

1)

3)

F ( x) → G ∃xF ( x) → G

R∃,

где формула F содержит свободные вхождения переменной x, а формула G их не содержит.

10.2 Вхождение переменных в формулы ИП

Определение свободного и связанного вхождения переменных в формулы ИП аналогично (по синтаксису) определению для предикатов и рассмотрено в алгебре предикатов. То же относится и к понятию области действия кванторов. Формула ИП, не содержащая свободных вхождений переменных, называется замкнутой. Пусть F – формула, t – терм. Если никакое свободное вхождение переменной x в формулу F не лежит в области действия никакого квантора по переменной Υ, входящей в терм t, то терм t называется свободным для переменной x в формуле F. Примеры 1 Пусть F: = ∀y Р(x)- формула; t: = y – терм. Тогда терм t является несвободным для переменной x в формуле F. 2 Терм f(x,z) свободен для переменной xв формуле ∀yР(x,y)→Q(x), но тот же терм f(x,z) не свободен для переменной x в формуле ∃z∀y Р(x, y)→ Q (x).

11 Интерпретация исчисления предикатов 11.1 Интерпретация высказываний

исчисления

предикатов

в

алгебру

Интерпретация ИП в алгебру высказываний определяется заданием множества M - области интерпретации и последующим приписыванием в качестве значений: ─ каждой предметной константе и каждой свободной переменной конкретного элемента из M; ─ каждой n – местной предикатной или функциональной переменной конкретного n – местного предиката или соответственно функтора на M; ─ каждой связке и каждому квантору – соответствующих логических операций ( с сохранением приоритета). В результате интерпретации формула становится высказыванием, истинностное значение которого вычисляется в соответствии со структурой формулы и определением логических операций. Формула называется истинной в данной интерпретации, если соответст вующее ей высказывание истинно; ложной – в противном случае. Заметим, что истинностное значение формулы зависит от выбора множества M. Так, формула (∃x1Р(x1)→∀x2Р(x2)) истинна во всех интерпретациях, где M - одноэлементное множество, и не во всех, в противном случае. 11.2 Равносильности

Две формулы ИП называются равносильными, если они имеют одинаковые истинностные значения во всех интерпретациях. Запись: F = G («F равносильно G»). Имеет место следующие равносильности: 1) ∀x F(x) = ∃ x  F(x) ,  ∀ x F(x)= ∀ x  F(x); 2) ∀x(F(x) ∧ G(x)) = ∀xF (x) ∧ ∀xG(x), ∃x(F(x) ∨ G(x))=∃F(x) ∨ ∃xG(x); 3)∀x ∀y F(x, y) =∀y ∀ x F(x, y), ∃ x ∃y F(x, y)= ∃y∃ x F(x, y); 4)∀x (F(x)∧С) = ∀x F(x) ∧ С, ∀x (F(x) ∨ С)= ∀x F(x) ∨ С; 5)∃x (F(x)∧С) = ∃ x F(x) ∧ С, ∃ x (F(x) ∨ С) = ∃ x F(x) ∨ С; 6)С → ∀x F(x) = ∀x ( С → F(x)), С→ ∃ x F(x) = ∃ x (С → F(x)). Эти равносильности называются также законами логики предикатов. Формула С не содержит вхождений переменной x. Применяются, как и прежде. синтаксические сокращения: F↔G: = (F→ G) ∧ (G→ F), F→ G: =  F∨ С. Раннее отмеченные законы F=F, (F∨С)=F∧G, (F∧G)= F∨G здесь тоже имеют место и используются. С помощью равносильностей можно преобразовывать формулы.

12 Классификация формул логики предикатов 12.1 Тавтология. Противоречие. Выполнимая формула

Формула ЛП называется тождественно истинной, или тавтологией, если она истинна в любой интерпретации. Пример - Формула (∃x1 Р(x1) →∀x2 Р(x2)) не является тавтологией. Формула ЛП называется тождественно ложной, или противоречием, если она ложна в любой интерпретации. Формула ЛП называется выполнимой, если она истинна хотя бы в одной интерпретации. 12.2 Логическое следствие. Логическая эквивалентность

Формула ЛП G называется логическим следствием формулы F, если G истинна во всех интерпретациях, в которых F истинна. Запись: F→ G. Имеют место логические следования: 7)∃x(F(x)∧G(x)) ∃xF(x)∧∃xG(x), ∀x F(x)∨∀ ∃xG(x)⇒∀x(F(x)∨G(x)) ; 8)∀ xF(x) → H ⇒ ∃ x(F(x) → H), ∃ xF(x) → H ⇒ ∀ x(F(x) → H), где формула Н не содержит вхождений переменной х. Формулы F и G называются логически эквивалентными, если они являются логическими следствиями друг друга. Запись: F⇔ G. 12.3 Подстановка

Пусть F(x) – формула, t – терм. Положим по определению F(t):= F(…x …)  t//xТогда имеют место следующие теоремы. Теорема 12.1 Формула ∀xF(x)→F(t),где t – терм, свободный для перемен ной x в формуле F, есть тавтология. Теорема 12.2 Формула F(t) →∃ x F(x), где t – терм, свободный для переменной x в формуле F, есть тавтология. 12.4 Предваренная нормальная форма

В логике высказываний были введены нормальные формы – конъюнктивная и дизъюнктивная. В логике предикатов первого порядка также имеется нормальная форма, называемая предваренной нормальной формой (ПНФ). Формула ЛП F называется находящейся в ПНФ, если она имеет вид: Q1 x1 … Qn xn F0 , где Qi, i,= 1..n – один из кванторов (∀,∃), x i≠ xj, если i≠j,

(12.1)

F0 – формула, не имеющая кванторов. Цепочка Q1 x1 … Qn xn называется предикатом, F0 – матрицей. Пример - Формула ∀x∀y∃z (Q(x,y) →R(z)) находится в ПНФ. Для любой формулы ЛП существует логически эквивалентная ей формула, находящаяся в ПНФ. Приведение данной формулы ЛП к ПНФ можно произвести с помощью равносильностей (1-6) и следований (7-8). Пример - Привести формулу ∀x Р(x) →∃ x Q(x) к ПНФ. Решение - ∀x Р(x) →∃ x Q(x)= ((∀x Р(x))∨ ∃ x Q(x)= ∃ x ((∀x Р(x)) ∨ ∃ x Q(x)= ∃ x((Р(x)) ∨ Q(x)). Следовательно, ПНФ для исходной формулы есть ∃ x(( Р(x)) ∨ Q(x)). 12.5 Скулемовская стандартная форма

Доказательство теорем сопутствует основной задаче логики предикатов – описание всех тождественно – истинных формул. Согласно методу резолюций вместо доказательства тавтологичности формулы доказывается, что отрицание формулы противоречиво. Для этого формула приводится к скулемовской стандартной форме, или стандартной форме. Ранее обсуждалось, как свести формулу ЛП к ПНФ. Дальнейшее преобразование касается матрицы и префикса. Техника сведения бескванторной формулы (здесь - матрицы) к конъюнктивной нормальной форме также показана ранее. Теперь займемся элиминацией (устранением) кванторов. Пусть формула F находится в предваренной нормальной форме Q1 x1 … Qn xn F0, где F0 есть конъюнктивная нормальная форма. Если Qr, 1≤ r ≤n, есть квантор единичности в префиксе Q1x1…Qn xn, рассмотрим случаи: 1) никакой квантор общности не стоит в префиксе левее Qr. Тогда выбираем новую ( не встречавшуюся в формуле) константу с и заменяем все xr в F0 на с; вычеркиваем Qr xr из префикса; 2) имеется непустой список Qr1, …, Qrm, 1≤ r1≤ …≤rm< r, всех кванторов общности, встречающихся в префиксе левее Qr. Тогда выбираем новый ( не встречавшийся в формуле функциональный символ f, заменяем все xr в F0 на f(xr1, …, xrm). Выполняем эту процедуру для всех кванторов существования в префиксе. Полученная в результате формула имеет, по определению, скулемовскую стандартную форму. Константы и функторы, используемые для замены переменных кванторов существования, называются скулемовскими функциями. Пример – Указать ССФ формулы ∃ x ∀y ∀ z ∃u∀v ∃w P(x,y,z,u,v, w). Ответ - ∀y ∀ z∀v P(x, y, z, f(y, z), v,g(y, z, v)). Введем термины: литерал (атом или отрицание атома), дизъюнкт (дизъюнкция литералов). Дизъюнкт, не содержащий литералов, назовем пустым дизъюнктом. Множеством дизъюнктов назовем конъюнкцию всех дизъюнктов из S , где каждая переменная в S управляется квантором общности. По этому соглашению стандартная форма может быть представлена множеством дизъюнктов.

Пример – Имеется формула ∀ x ∃ y ∃ z (( Р (x, y) ∧ Q (x, z))∨ R (x, y, z). Ее ССФ может выглядеть так: ∀ x (( Р(x, f(x) ) ∨ R (x), g(x))) ∧ Q (x, g(x)) ∨ R (x, f(x), g(x)))), которую можно представить множеством  Р (x, f(x)) ∨ R (x, f(x), g(x)), Q (x, g(x)) ∨ R (x, f(x), g(x)). Следующая теорема – основа метода. Теорема Пусть S – множество дизъюнктов, которые представляют стандартную форму формулы F. Тогда F противоречива тогда и только тогда , когда S противоречива.

13 Применения логики предикатов 13.1 Строение математических теорем

Рассмотрим следующую теорему: «Если точка лежит на биссектрисе угла, то она равноудалена от сторон этого угла». Предусловием этой теоремы является предложение «Точка лежит на биссектрисе угла», а постусловием – предложение «Точка равноудалена от сторон угла». Оба условия являются предикатами. Обозначим их соответственно А(x) и В (x), x∈Р, где Р –множество точек плоскости. Тогда рассматриваемая теорема состоит в том, что импликация предикатов А(x)→ В (x), то есть предикат «Если точка x лежит на биссектрисе угла, то она равноудалена от сторон этого угла», обращается в истинное высказывание при всех x из множества Р. При помощи квантора общности это можно записать так: ∀ x (А(x)→ В (x)), x∈Р (13.1) Заметим, что словесная формулировка теоремы содержат описание множества объектов, о которых идет речь в теореме. 13.2 Методы доказательства теорем

Приведем формулировку принципа математической индукции. Пусть А(n) – произвольный предикат, заданный на множестве всех натуральных чисел. Высказывание ∀ n А(n) истинно, если истинно высказывание А(1) ∧ (∀k) (А (k) → А(k+1)). (Этот принцип, заметим, является одной из аксиом, определяющих натуральный ряд чисел). Под методом математической индукции понимают следующий способ доказательства. Сначала проверяют истинность высказывания А(1). Затем, предположив истинность высказывания А(k), доказывают истинность высказывания А (k+1). Если доказательство верно для любого натурального k, то в соответствии с принципом математической индукции высказывание А(n) признается истинным для всех n.

14 Свойства исчисления предикатов 14.1 Теорема Геделя о полноте исчисления предикатов

Имеют место следующие метатеоремы. Теорема 14.1 Всякая теорема классического исчисления предикатов первого порядка есть тавтология. Теорема 14.2 Всякая тавтология является теоремой классического исчисления предикатов первого порядка. Вторая из этих теорем доказана К. Геделем (1930) и является утверждением о полноте классического исчисления предикатов первого порядка. 14.2 Непротиворечивость

Теория К непротиворечива. Доказательство следует из теоремы 14.1 и аналогично доказательству о теории L. 14.3 Проблема разрешения в логике предикатов

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

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

15 Автоматическое доказательство теорем 15.1 Постановка задачи

Алгоритм, проверяющий отношение Г T S,

(15.1)

называется автоматическим доказательством теорем (АДТ). Здесь Γ - множество посылок, S – заключение (формулы); T-формальная теория,  - знак выводимости В общем случае такого алгоритма не существует, то есть не существует алгоритма, который для любых S, Г, T выдавал бы ответ «Да», если выводимость (15.1) имеет место, и ответ «Нет», в противном случае. В некоторых случаях подобные алгоритмы существуют. Например, в случае исчисления высказываний. Поскольку в ИВ теоремами являются общезначимые формулы (и только они), то для проверки выводимости достаточно построить таблицы истинности. Частичным алгоритмом АДТ (из наиболее известных) является метод резолюций (МР). Для любого прикладного ИП первого порядка МР дает ответ «Да», если (15.1) имеет место, и дает ответ «Нет» или не дает никакого ответа («зависает»), в противном случае. (Напомним, прикладное ИП есть ИП, которое содержит предметные константы и или функторы, иили предикаты и связывающие их собственные аксиомы. ИП, не содержащее предметных констант, функторов, предикатов и собственных аксиом, называется чистым.) 15.2 Основа метода резолюций

Теорема Если Г,  S  F, где F – тождественно ложная формула (противоречие), то Г S. Эта теорема лежит в основе МР, то есть используется идея «доказательства от противного». В качестве противоречия принято использовать так называемую «пустую» формулу и обозначать «пустым» квадратом: . 15.3 Правило резолюции

Метод резолюций работает с предложениями. Напомним, предложение – бескванторная дизъюнкция литералов, а литералы – это формулы вида А,  А, где А – атом. Далее будет показана методика перехода от формулы ИП к множеству предложений. Правило резолюции для ИВ: пусть С1, С2 – предложения в ИВ, причем С1 = Р ∨С1′, С2 =  Р ∨С2′, где Р – пропозициональная переменная, С1′, С2′ - пред-

C1, C 2 Rназывается C1'∨C 2' правилом резолюции. Здесь С1, С2 – резольвируемые предложения; С1′∨С2′ резольвента; R – название правила; Р,  Р – контрарные литералы. Теорема Резольвента является логическим следствием резольвируемых предложений. Правило резолюции для ИП: пусть С1, С2 – предложения в ИП, причем С1 = Р ∨С1′, С2 =  Р ∨С2′, где P1, Р2 – литералы, имеющие наиболее общий унифи ложения (в том числе, пустые); тогда правило вывода

C1, C 2 R называется правилом резолюции. C1'∨C 2' σ Здесь резольвента (С1′∨С2′)σ получена из предложения (С1′∨С2′) применением унификатора σ. Напомним, формулы А (…, хi, …), В (…, хi, …) называются унифицируемыми, если существует набор подстановок  хi  хii =1 , в результате которых будет выполняться равенство А (…, хi, …) = В (…, хi, …). Указанный набор называется общим унификатором, наименьший набор из возможных называется наиболее общим унификатором (НОУ). В подстановках используются обозначения хi – для переменных, хi – для формул, i =1 …n. катор σ; тогда правило вывода

15.4 Метод резолюций

Пусть требуется установить выводимость S  G

(15.2)

Тогда предварительно формулы множества S и формула G независимо преобразуются в множества предложений. (Множество предложений есть конъюнкция предложений). В полученном множестве всех предложений С отыскивается резольвируемые предложения, к ним применяется правило резолюции, и резольвента добавляется в множество С. При повторных действиях возможны случаи: 1) В результате очередного применения правила резолюции получено пустое предложение. Это означает, что выводимость (15.2) установлена (теорема доказана); 2)Среди текущего множества предложений С нет резольвируемых. Это означает, что выводимости (2) нет ( теорема опровергнута); 3) Процесс продолжается, множество С пополняется, пустых предложений нет. Здесь не ясно. Пример – Доказать теорему:  L (((А→В) → А) →А) Решение: Проведем тождественные преобразования:  (((А→В) → А) → А) =  ( ( ( А∨ В) ∨А) ∨А)= (((А ∧  В) ∨ А) ∨  А) = (А ∨ А) ∧ ( В ∨ А ) ∧  А. Разбиваем на приложения и последовательно применяем правило резолюции:

1) А ∨ А 2)  В ∨ А 3)..А 4) А (1, 3) (3,4) Получена пустая формула. Теорема доказана. 5) 15.5 Сведение формулы к множеству предложений

Любая формула ИП может быть преобразована в множество предложений с помощью следующих замен (≈> - знак замены). Элиминация импликации: А→В ≈>  А ∨ В. 1) (Знак → устранен). Продвижение отрицания:  А ≈>А,  (А ∨ В) 2) ≈> А ∧  В,  (А ∧ В) ≈> А ∨  В;  ∀х А ≈>∃ х  А,  ∃ х А ≈> ∀х  А. (Теперь знаки  - только перед атомами.) 3) Разделение связанных переменных: Q1 х А (…Q2хВ (…х…) …) ≈> Q1 хА (…Q2 yВ(…y…)…), где Q1, Q2 – любые кванторы. (Теперь нет случайно совпадающих связанных переменных.) Распространение кванторов: Q х А∨ B ≈> Q х 4) (А∨ В), Q х А∧В≈> Q х ( А ∧ В). (Теперь, после замен 1-4, формула находится в так называемой предваренной форме.) 5) Элиминация кванторов существования: ∃ х1 Q2 х2 … Qn хn А (х1, х2, …, хn) ≈>Q2 х2… Qn хn А(а,х2,…, хn); ∀х1… ∀х i-1 Q i+1 х i+1… Qn хn А (х1,…,xi,…xn) ≈> ∀х1… ∀х i-1 Q i+1 х i+1… Qn хn А (х1,…,f (х1, …, хi-1,… хn), где а – новая предметная константа, f – новый функтор, Q1, Q2,…, Qn – любые кванторы. (После замен 1-5 формула содержит кванторы только вида ∀.) Элиминация кванторов всеобщности: ∀х 6) А(х) ≈> А(х). (Теперь нет и кванторов ∀.) 7) Приведение к КНФ: А∨ (В∧С) ≈>(А∨В) ∧ (А∨ С), (А∧В) ∨ С≈>(А∨ С) ∧ (В∨ С). (Имеем КНФ после 1-7.) Элиминация конъюнкции: А∧В≈> А,В. (Те8) перь, после замен 1-8, имеем множество предложений.) 15.6 Обоснование метода резолюций

Теорема Если Г – множество предложений, полученных из формулы S, то S является противоречием тогда и только тогда, когда множество Г невыполнимо. Напомним, невыполнимость множества формул означает, что не существует интерпретации, в которой все формулы множества имеют значение «истина».

Пример – Даны высказывания F, G. Доказать, что F G. F: = «Каждый, кто хранит деньги, получает проценты». G:= «Если нет процентов, то никто не хранит деньги». Решение Введем предикаты: М(х):= «х есть деньги»; I(х):= «х есть проценты»; S (х,y): = «х хранит y»; Е (х, y):= «х получает y». Перейдем к предложениям. При этом, очевидно, F=∀х (∃y (М(y) ∧ S(х, y)) → ∀z(I(z) ∧Е (х, z))); G = (∃х I(х)) → (∃y ∃ z(М(y) ∧ S(z, y)))= ∃х (I(х))∨  (∃y∃ z (М(y) ∧ S(z, y)));  G=∀х ( I(х)) ∧∃y ∃ z (М(y) ∧ S(z, y))= ∃y∃ z∀х ( I(х)) ∧ М(y) ∧ S(z, y)) ≈> ∀ z (I(z) ∧ М (а) ∧ S(b,а)), а/ y,b/ z. Множество предложений: 1 ¬М(у) ∨ ¬S (х,y) ∨ I (f(х)), {F} 2 М(у) ∨ ¬S (х,y) ∨ Е (х, f(х)) { F} 3 ¬I(z) {G} 4 М(а) {G} 5 S (b,а) {G} Вывод: 6 ¬S (х,а) ∨ I (f(х)), (1,4), а/ y 7 I (f(b)), (5,6), b/х 8 , (3,7)  f(b)/ z Получена пустая формула. Выводимость доказана. Пример – Даны высказывания: F1:= « Том не может быть хорошим студентом, если неверно, что он способный и отец помогает ему»; F2 =«Том хороший студент только если его отец помогает ему». Доказать что F1F2. Решение Пусть H(x) - «x-хороший студент» S(x)- «x-способный студент»;Р (х, y) – «y помогает х». Тогда F1: =  (S(а) ∧ Р (а,b)) →  (Н(а)); F2: = Р(аb) ← Н (а) Метод резолюций дает: 1 S(а) ∨ ¬Н (а) 2 Р (а, в) ∨ ¬Н (а) 3 ¬Р (а, в) 4 Н (а) 5 Выводимость доказана.

Задачи

1 Дать истинностную оценку высказываний: а) В каждом ромбе диагонали взаимно перпендикулярны; б) Число 3 есть делитель числа 19; в) Число 1+28 – простое; г) Картины Рериха загадочны; д) Найдется число х, удовлетворяющее уравнению х2+1=0. 2 Из высказываний А:= «Испытания проведены», В:= «Программа выполнена» составьте высказывания: а) А∨ В; б) А∧ В; в) А→В; г) А↔В. 3 Данные высказывания: х1:= «Идет дождь», х2:= «Очень жарко». Запишите символически составные высказывания: а) Неверно, что идет дождь и очень жарко; б) Если не идет дождь, то очень жарко. 4 Выделите из следующих составных высказываний простые, обозначьте их буквами и с их помощью запишите исходные составные высказывания как результаты соответствующих логических операций: а) Давление падает, и система не работает; б) Вычисления выполнены точно или конструкция несовершенна; в) Проект разработал Андрей или Петр, а эксперимент выполнил Иван; г) Если я поеду на автобусе, то опоздаю на работу, или я воспользуюсь такси; д) Программа будет выполнена если и только если материалы поступят своевременно; е) Андрей помогает Петру или Петр помогает Петру, или они помогают друг другу. 5 Даны высказывания: А:= «Все кошки серы» и В:= «Число 6-простое число». Определите истинное значение высказываний: а)¬A; б)A⋁В; в)¬А⋀В; г) А↔¬В; д) А→В; е) В. 6 Составить таблицу истинности для высказываний; а) ¬х1⋁х2; б)(х∧ у)∨ х; в) ¬(х∨ у); г)(х∧ у)∨ (y∧ z)∨ (x∧ z). 7 Проверьте с помощью таблицы тождества: а) x→y=¬x∨ y

б) x∧ (x∨ y)=x в) x∨¬x∧ y=x∨ y г)xyz∨ xy¬z∨ x¬y=x 8 Упростите следующее выражения: а)¬xyz∨ x¬y¬z∨ xy¬z; б)(x∨ y)( ¬(xy)∨ z)∨¬z∨ (x∨ y)(u∨ v). 9 Составить нормальные формы для булевых функций: а)y=x1→x2; б)y=x1/x2; в)y=x1↓x2; г) ¬(x→(¬x↔z))(y→¬z); д) ¬(x∨ y¬z)(x∨ y); е) (xy∨¬yz) ¬ (¬x u). 10 Выразить через , ∧, ∨ операции: а) →; б) ↔; с) ⁄ ; д) ↓ . 11 Постройте переключательные схемы по формулам: а) (х1∨ х2 ∧ ¬х3) ∧ (х1 ∧ х2 ∨ х3 ∧ х4); б) (¬х1 ∧ (х2 ∨ ¬х3) ∨¬ х4) ∧ х1. 12 Запишите формулу, соответствующую переключательной схеме рисунка 16.1. Упростите эту формулу и постройте более простую схему:

А

В

С В А Рисунок 16.1 13 Изобразите схематически множества истинности предикатов А(х), В(х) и покажите штриховкой множества истинности следующих предикатов: а)¬А(х)∧ ¬В(х); б)¬ (А(х) ∨ В(х)); в) ¬А(х) ∨¬В(х); г) ¬ (А(х) ∧ В(х)).

14 Контрольную работу, содержащую 3 задачи, выполняли 105 студентов. Первую задачу решили 70 человек, вторую – 59, третью – 62. 90 студентов решили первую или вторую задачу, вторую или третью – 89, а первую или третью решили 91 студент. Сколько студентов решили все три задачи, если 6 студентов не решили ни одной задачи. 15 Пусть Е = е  - множество европейцев. Рассматривается четыре предиката: А (е): = «Европеец – гражданин Швейцарии»; В (е): = «Европеец владеет немецким языком»; С (е): = «Европеец владеет французским языком»; Д (е): = «Европеец владеет итальянским языком»; Тогда что означает высказывание: ∀е (А (е) → В (е)∨ С (е) ∨ Д (е)). 16 Рассмотрим два определения легкой контрольной: 1) Контрольная называется легкой, если каждую задачу решил хотя бы один студент. 2) Контрольная называется легкой, если хотя бы один ученик решил все задачи. Ответим на вопросы: а) Может ли быть контрольная легкой в смысле первого определения и не легкой в смысле второго? б) Может ли работа быть легкой в смысле второго определения и не легкой в смысле первого. 17 Имеется два конечных числовых множества А и В и некоторые высказывания о них: 1) Любое число из А больше любого числа из В; 2) Самое большое число из А больше самого большего числа из В; 3) Для любого числа из А найдется число из В, меньшее этого числа; 4) Каждое число из В меньше хотя бы одного числа из А; 5) Среднее арифметическое чисел из А больше среднего арифметического чисел из В. Найдите среди этих высказываний эквивалентные. 18 Граф G = (V, E) определяется заданием непустого множества вершин V, множества ребер Е и трехместного предиката Р(х,е,у): = «Ребро е соединяет вершины х и у», который определен на всех упорядоченных тройках (х,е,у), причем х,у ∈ V, е ∈ Е. Для орграфа х считается начальный, а у – конечный вершинами дуги е. Запишите предикаты, задающие: а)подмножество дуг орграфа, исходящих из вершины а; б)подмножество дуг орграфа, входящих в вершину b; в)подмножество ребер графа, инцидентных вершине а; г)подмножество ребер графа, соединяющих вершины а и b. 19 В соответствии с определением графа в задаче 18 расшифруйте высказывания: а)∃х∃у ((х≠у) ∧ Р(х,е,у) ∧ Р (у,е,х)); б)∃х Р(х,е,х).

Покажите, что для любого е ∈ Е истинно одно и только одно из этих высказываний. Назовите подмножества Е, соответствующие каждому в отдельности высказыванию. 20 На множестве натуральных чисел определены предикаты: Р(х):= «Число х делится на 8» и Q(x): = «х – четное число» Прочитайте следующие высказывания и выясните, какие из них истинны: а) ∀х Р(х); б) ∃х Р(х); в) ∀х Q(x); г) ∃х ¬Q(x); д) ∀х ¬Q(x); е) ∀х (Р(х)→ Q(x)); з) ∃х (Q(x) → Р(х)). 21 Пусть х – множество прямых на плоскости. На этом множестве определены предикаты: R (х,у): = «Прямая х пересекается с прямой у», S(х,у):= «Прямая х параллельна прямой у», причем х,у ∈ Х. Прочитайте следующие высказывания и определите их истинность: а) ∀х ∃у R(х,у); б) ∃х∃у ¬S (х,у)); в) ∀х∀у (R (х,у)→ ¬S (х,у)); г) ∀х∀у (R (х,у)∨ S (х,у)). 22 На множестве натуральных чисел определены предикаты: Р(х):= «х – простое число», Q(x): = «х - четное число», R (х,у): = « х- не равно у». Переведите на русский язык высказывание: ∃х (Р(х) ∧ Q(x)) ∧ ¬∃х (Р(х) ∧ Q(x) ∧ ∃у (R (х,у) ∧ Р(у) ∧ Q(у))). 23 Запишите предикаты для высказываний: а) Каждый студент изучает (один язык) или английский, или немецкий, или французский язык; б) Некоторые устройства укомплектованы осциллографами; в) Не все телевизоры работают хорошо; г) Ни один прибор не оказался забракованным. 24 Установите истинностное значение предикатов: а) Если некоторые транзисторы негодные и все транзисторы проверяются, то среди проверенных транзисторов найдутся негодные; б) Никто из спортсменов не изучает иностранных языков, если все инженеры изучают иностранный язык и некоторые из них – спортсмены. 25 Дан предикат ∀х (Р(х,у,z) →∃у Q(x,у)) ∨ Q(x,у) ∧ ¬S. Здесь Р(х,у,z) – трехместный, Q(x,у) – двухместный, S – нульместный предикат. Требуется определить истинностное значение данного предиката при условиях: М = а, в, S = 0; х=b, у=а, z=а; предикаты Р, Q имеют таблицу 1:

xуz ааа ааb аbа аbb bаа bаb bbа bbb

Р (х, у, z) 0 1 1 0 0 1 0 1

Q(x, у) 0 0 0 1

в)  L¬А → (А→В); г)  L (¬В →¬А) →(А →В); д)  L(А→В) → (¬В →¬А); е)  LА→(¬В →¬(А→В)) 27 В теории L доказать выводимость: а) А→В, В→С, А  С; б) А→В, В →С  А →С; в) D, А→В, D →С, С ∨ В, А  С; г) Р∧Q → R, Q → P, Q  R. 28 Дано высказывание: «Для того, чтобы матрица имела обратную, необходимо чтобы ее определитель был отличен от нуля. Какие из приведенных ниже высказываний логически следует из данного? а) Для того, чтобы матрица имела обратную, достаточно, чтобы ее определить был равен нулю. б) Для того, чтобы определитель матрицы был отличен от нуля, достаточно, чтобы эта матрица имела обратную. в) Для того, чтобы определитель матрицы был равен нулю, необходимо, чтобы эта матрица не имела обратной. г) Матрица имеет обратную тогда и только тогда, когда её определитель не равен нулю. 29 Докажите логическое следствие (Р → Q) ∧ (R → S) ∧ (S ∧ Q → T) ∧ T ⇒¬ P ∨ R через соответствующую тавтологию; с помощью правил вывода; дедуктивным способом. 30 Докажите равносильность высказываний Х → (Х ∧¬ (Y∨ Z)) и ¬X ∨ ¬Y ∧ Z. Представьте эту равносильность в виде логических следствий. 31 Упростите следующую систему высказываний: А → (В ∨ С); В → ¬ (А ∧ С); С → (А ∨ В); А → (В ∨ С); ¬A∨¬C∨B;А ∨ В ∨ С. Приняв для А, В, С некоторые высказывания, сформулируйте сложное высказывание исходной и упрощенной систем. 32 Исследуйте каждую из приведенных ниже систем высказываний на противоречивость: а) А → ¬В ∧ ¬С; (D ∨ Е) → F; F→¬ (G ∨ H); ¬С ∧ Е ∧ F; б) (А ∨ В) → С ∧ D; D ∨ Е → F; А ∨ ¬F;

в) (А → В) ∧ (С → D); (В → D) ∧ (¬С → А); (Е → F) ∧ (F →¬ D); ¬ Е → Е;

→ Е);

г) (А → В ∧ С) ∧ (D → В ∧ Е); (F → А) ∧ G → Н; (G → Н) → F ∧ D; ¬(С

Решите задачу двумя способами: путем приписывания значений простым высказываниям (буквам) и с помощью логического вывода. 33 Запишите в символической форме и установите логичность следующих рассуждений: а) Если заменить лампу (А), телевизор будет работать (В) при условии, что напряжение подключено (С). Лампа заменена, а напряжение не подключено. Следовательно, телевизор не будет работать. б) Если поднять давление (А) или увеличить температуру (В), то реакция произойдет быстрее (С), но опасность повысится (Д). Если опасность повысится, то необходимо принять меры защиты (Е). Меры защиты не приняты. Следовательно, давление поднимать нельзя. в) Если упростить схему (А), стоимость снизится (В), и если применить новые элементы (С), надежность увеличится (Д). Можно или упростить схему, или применить новые элементы. Однако, если упростить схему, то надежность не увеличится, а если применить новые элементы, то стоимость не снизится. Итак, надежность увеличится тогда и только тогда, когда стоимость снизится. 34 Свободен ли терм f (х1,х2) для х1 в формулах А1 (х1,х2) → ∀х2 А2 (х2), ∀ х2А(х2,а1)) ∨ ∃ х2А(х1,х2)? 35 Указать свободные и связанные вхождения переменных в следующие формулы: 1) ∀х3 (∀х1А (х1,х2) → А (х3,х1)); ∀х2А (х3,х2) → ∀х3А(х3,х2); 2) 3) (∀х2∃ х1А1 (х1,х2, f1 (х1,х2))) ∨  ∀х1А2 (х2, f2(х1)). 36 Даны формулы: 1) А1^2 (f1^2 (x1,x2),a1); А1^2 (x1,x2) → А1^2 (x2,x1); 2) ∀х1 ∀х2 ∀х3 (А1^2 (x1,x2) → А1^2 (x2,x3) → А1^2 (x1,x3). 3) Для следующих интерпретаций и для каждой из записанных формул указать, при каких значениях свободных переменных эти формулы выполнены (если они имеют свободные переменные), или выяснить, являются ли они ложными или истинными высказываниями (если они не содержат свободных переменных): а) Область интерпретации – множество всех целых положительных чисел; 2 А1 (y,z), f12(x,z), a1 интерпретируется соответственно как y ≥ z, yz, 1. б) Область интерпретации – множество всех множеств целых чисел, А12 (y, z), f12(y, z), а1 интерпретируются соответственно как y⊃z, z ∪ y, ∅ (пустое множество). 37 Показать, что следующие формулы не являются общезначимыми: а) ((∀х1А11(х1) → ∀х 1А21(х1)) → ((∀х1(А11(х1) → А21(х1))); б) (∀х1(А11(х1) ∨ А21(х1))) → ((∀х1 А11(х1)) ∨ (∀х1 А21(х1))).

38 Показать, что следующие формулы логически общезначимы: а) ∃ хi ∃ хj F ↔ ∃ хj ∃ хi F; б) ∃ хi ∀ хj F → ∀ хj ∃ хi F; в) ∀ хi F → ∃ хi F; г) ∀ хi F ↔  ∃ хi  F. 39 Введя подходящие обозначения, записать предложения, участвующие в нижеследующих выводах, в виде формул и выяснить, в каких случаях конъюнкция посылок логически влечет заключение: а) Для любого множества х существует множество у такое, что мощность у больше мощности х. Если х включено в у, то мощность х не больше мощности у. Всякое множество включено в V. Следовательно, V – не множество. б) Если всякий предок предка данного индивидуума есть также предок того же индивидуума, и никакой индивидуум не есть предок самого себя, то должен существовать некто, не имеющий предков. 40 Даны высказывания: F: = «Каждый, кто хранит деньги, получает проценты»; G: = «Если нет процентов, то никто не хранит денег» Доказать: F  G. 41Записать в виде категорических высказываний: а) «Не все телевизоры работают хорошо»; б) «Ни один прибор не оказался забракованным». 42Имеются посылки: F1: = «Таможенные чиновники обыскивают каждого, кто въезжает в страну, кроме высокопоставленных лиц», F2: = «Некоторые люди, способствующие провозу наркотиков, въезжали в страну и были обысканы исключительно людьми, способствующими провозу наркотиков»; F3: = «Никто из высокопоставленных лиц не способствовал провозу наркотиков». Предполагаемое заключение G: = «Некоторые из таможенников способствовали провозу наркотиков. Доказать: F1, F2, F3  G. Указание - Применить метод резолюций. 43 Король думает, что королева думает, что она не в своем уме. В своем ли уме король? 44 Посылка: «Студенты – граждане». Заключение: «Голоса студентов – голоса граждан». Вывести методом резолюций. 45 Пусть F1 и F2 таковы: F1: ∀х (Р(х)→Q(x)), F2:  Q(a). Доказать, что  Р (а) есть логическое следствие F1 и F2. 46 Восстановить скобки в выражениях: а) ∀х2  А11(х1) →А23(х1,х2,х3) ∨ ∀х1 А21(х1); б)  ∀х1 А11(х1) →∃х2 А21(х2) →А12(х1,х2) ∨ А11 (х2). 47 Перевести следующие предложения на язык формул:

а) Все рыбы, кроме акул, добры к детям; б) Не все птицы могут летать; в) Ты можешь обманывать кое-кого все время, ты можешь обманывать всех некоторое время, но ты не можешь обманывать всех все время; г) Если кто- нибудь может сделать это, то и Джон может. 48 Рассматриваются цепи, содержащие только двухпозиционные переключатели. а) Пусть каждый из трех членов комитета голосует «за», нажимая кнопку. Построить по возможности простую электрическую цепь, через которую ток проходил бы тогда и только тогда, когда не менее двух членов комитета голосуют «за»; б) Требуется, чтобы включение света в комнате осуществлялось с помощью трех различных переключателей таким образом, чтобы нажатие на любой из них приводило к включению света, если он перед ним был выключен, и к его выключению, если он был включен. Построить простую цепь, удовлетворяющую такому заданию. 49 Выяснить, являются ли следующие рассуждения логически правильными. Для этого проверить, является ли заключение логическим следствием конъюнкции посылок. а) Если капиталовложения останутся постоянными, то возрастут правительственные расходы или возникнет безработица. Если правительственные расходы не возрастут, то налоги будут снижены. Если налоги будут снижены и капиталовложения останутся постоянными, то безработица не возникнет. Следовательно, правительственные расходы возрастут. б) Люди могут мыслить. Машины - не люди. Следовательно, машины не могут мыслить. 50 Проверить совместность каждого из множеств утверждений. Для этого представить предложения в виде пропозициональных форм и затем проверить, является ли их конъюнкция противоречием. а) Если вечер скучен, то или Алиса начинает плакать, или Анатоль рассказывает смешные истории. Если Сильвестр приходит на вечер, то или вечер скучен, или Алиса начинает плакать. Если Анатоль рассказывает смешные истории, то Алиса не начинает плакать. Сильвестр приходит на вечер тогда и только тогда, когда Анатоль не рассказывает смешные истории. Если Алиса начинает плакать, то Анатоль рассказывает смешные истории. б) Если курс ценных бумаг растет или процентная ставка снижается, то либо падает курс акций, либо налоги не повышаются. Курс акций понижается тогда и только тогда, когда растет курс ценных бумаг и налоги растут. Если процентная ставка снижается, то либо курс акций не понижается, либо курс ценных бумаг не растет. Либо повышаются налоги, либо курс акций понижается и снижается процентная ставка.

ЧАСТЬ 2 ТЕОРИЯ АЛГОРИТМОВ Введение

Понятие алгоритма занимает одно из центральных мест в современной математике. Алгоритм – предписание, однозначно задающее процесс преобразования исходной информации в виде последовательности элементарных дискретных шагов, приводящих за конечное число их к результату. Слово «алгоритм» происходит, по мнению многих, от имени узбекского математика ал – Хорезми, который в IX веке разработал правила четырех арифметических действий над числами в десятичной системе счисления. С другой стороны, вычислительные процессы, с помощью которых искомые величины определялись из известных величин по заданным правилам, стали возникать в математике на самых ранних ступенях ее развития (Древний Египет, Вавилон, Древняя Греция). В книге Евклида «Начала» (около 300 г до н. э.) имеется алгоритм нахождения наибольшего общего делителя двух чисел, который, не исключено, был известен и ранее. Представим его в виде рекурсивной процедуры. Вход: неотрицательные целые числа а, b (а>b). Выход: НОД (а,b). Евклид (а, b) 1 если b=0 2 то НОД ← а 3 иначе НОД ← Евклид (b, а mod b) Реализация: Евклид (30,21) = Евклид (21,9) = Евклид (9,3) = Евклид (3,0)=3; НОД (3,21)=3. Входными и выходными данными алгоритма могут служить самые разнообразные конструктивные объекты. Это открывает возможность широкого применения понятия алгоритма. Можно говорить об алгоритме перевода с одного языка на другой, об алгоритме работы авиадиспетчера (перерабатывающего информацию о движении самолетов в предписания летчикам) и других применениях алгоритмического описания. Отметим несколько общих свойств алгоритмов. 1) Всякий алгоритм применяется к входным данным и имеет результатом выходные данные. На элементарных шагах появляются промежуточные данные. Данные должны быть специфицированы, в частности, указан алфавит данных и способы построения сложных данных из простых. Примерами данных могут быть числа, массивы чисел, изображения на экране и т. д. 2) Единицы объема данных и памяти ЭВМ должны быть согласованы. В прикладных алгоритмических моделях объем данных можно измерять числом ячеек памяти, в которых данные размещены. При этом исходят из того, что память ЭВМ состоит из одинаковых ячеек, каждая из которых может содержать один или несколько символов алфавита данных. 3) Элементарные шаги алгоритма состоят из базовых операций, число которых конечно. В частности, под операциями можно подразумевать машин-

ные команды, входящие в состав системы команд ЭВМ. В языках программирования высокого уровня базовые операции могут быть представлены операторами, входящими в состав синтаксиса данного языка программирования. 4) Последовательность шагов алгоритма должна быть однозначной. Не допускается произвола при выборе очередного шага алгоритма. Должны быть зафиксированы начальный и конечный шаги алгоритма. Возможны циклы (замкнутые подпути). Все шаги, которые встречаются в алгоритме, можно разделить на условные и безусловные. После безусловного действия либо выполняется действие, расположенное вслед за ним в описании, либо однозначно указывается, какой шаг надо выполнять следующим. Условное действие связано с проверкой условия и указывает, какое действие должно следовать за ним в зависимости от результата проверки. 5) Если способ получения результата на каком-либо шаге неприменим, то должно быть указано, что считать результатом выполнения алгоритма. Говорят, что алгоритм применим к допустимому исходному данному, если с его помощью можно перейти от исходного данного к искомому результату. Если результата нет, алгоритм, говорят, неприменим. Понятие применимости отвлечено от реальной ограниченности времени и ресурсов, требуется лишь конечность числа шагов и принципиальная возможность их выполнения. При этом используется термин «потенциальной выполнимости» алгоритма. Невыполнимость может состоять, например, в невозможности деления на нуль. 6) Начальная система величин может выбираться из некоторого потенциально бесконечного множества, что должно являть массовость алгоритма. Для машинной реализации алгоритма необходимо записать его на языке программирования, то есть составить программу. Путь от описания алгоритма к результату его выполнения проходит через транслятор – специальную программу, которая перерабатывает запись алгоритма в последовательность машинных команд. Алгоритм является фундаментальным понятием информатики. Имеется три крупных класса алгоритмов: вычислительные (работают с числами, числовыми матрицами и другими числовыми структурами); информационные (работают с большими объемами данных – базами данных – решают задачи поиска, записи, сортировки записей); управляющие (формируют управленческие воздействия на внешние процессы в соответствии с поступающей от них информацией). Еще следует сказать о детерминированности и корректности алгоритма. Детерминированность означает, что при одних и тех же исходных данных получается один и тот же конечный результат, а корректность состоит в правильности полученных с помощью него результата; кроме того, алгоритм должен быть обоснован и согласован с фактами и положениями данной области науки или техники. Приведенное толкование понятия «алгоритм» называется интуитивным. Оно хотя и нестрогое, но практически не требовало уточнения до двадцатых годов ХХ века, когда возникли так называемые массовые проблемы. Массовая проблема – проблема, когда требуется найти единый метод для бесконечной серии однотипных задач. Пример: построить алгоритм для выяснения имеются

ли целые корни у уравнения Р(х1,…,хm)=0, где Р (х1,…,хm)- произвольный многочлен с целыми коэффициентами от любого числа m переменных. Задача точного определения алгоритма стала одной из центральных математических проблем. Возникла теория алгоритмов, изучаются общие свойства алгоритмов. В 1936 году А. Черч опубликовал первое уточнение вычислимой функции, а А. Тьюринг и Э. Пост дали первые уточнения понятия алгоритма в терминах идеализированных вычислительных машин. В дальнейшем А.А. Марков предложил ввести понятие «нормального алгоритма». В рамках этих уточнений упомянутая ранее алгоритмическая проблема, известная как 10-я проблема Гильберта, оказалась неразрешимой. Теорию алгоритмов можно разделить на дескриптивную (качественную) и метрическую (количественную). Первая исследует алгоритмы с точки зрения устанавливаемого ими соответствия между исходными данными и результатами. К ней относятся, в частности, проблемы построения алгоритма, обладающего теми или иными свойствами, - алгоритмические проблемы. Вторая исследует алгоритмы с точки зрения сложности как самих алгоритмов, так и задаваемых ими вычислений, то есть процессов последовательного преобразования конструктивных объектов. Приложения теории алгоритмов имеются во всех областях математики. Теория алгоритмов тесно связана с математической логикой через понятие исчисления (например, теорема Геделя о неполноте может быть выведена из теорем теории алгоритмов), с основаниями математики, в которых одно из центральных мест занимает проблема соотношения конструктивного и неконструктивного, с кибернетикой (алгоритмы управления), с теорией информации (в 1965 году А.Н. Колмогоров предложил использовать теорию алгоритмов для обоснования теории информации). 1 Вычислимые функции 1.1 Понятие вычислимой функции. График вычислимой функции

Вычислимые функции (ВФ) – одно из основных понятий теории алгоритмов. Функция f называется вычислимой, если существует алгоритм, перерабатывающий всякий объект х, для которого определена функция f, в объект f(х) и не приводящий к результату ни для какого х, для которого f не определена /3/. Графиком ВФ называется множество пар вида (х, f(х)). Примеры 1 х – любое натуральное число, f(х)=х2; 2 х – пара рациональных чисел х1, х2, f(х)=х1:х2 (эта функция определена лишь для тех х, у которых х2≠0); 3 X – пара матриц X1, X2 с целочисленными элементами, f(X)=X1*X2 (эта функция определена лишь для тех X, у которых число столбцов в X1 равно числу строк в X2)

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

Областью применимости алгоритма называется совокупность тех объектов, к которым он применим, то есть дает результат. Про алгоритм А говорят, что он: - «вычисляет функцию f», если его область применимости совпадает с областью определения f, и А перерабатывает любой х из своей области применимости в f(х); - «разрешает множество М относительно множества Х», если он применим к любому х из Х и перерабатывает любой х из Х∩М в слово «да», а любой х из Х\М – в слово «нет»; - «перечисляет множество М», если его область применимости есть натуральный ряд, а совокупность результатов есть М. Множество называется разрешимым относительно Х, если существует разрешающий его относительно Х алгоритм. Множество называется перечислимым, если либо оно пусто, либо существует перечисляющий его алгоритм. Обнаружены результаты (путем анализа понятия «алгоритм»): - область возможных исходных данных и область применимости любого алгоритма суть перечислимые множества; - для любой пары вложенных одно в другое перечислимых множеств можно подобрать алгоритм, у которого внешнее множество служит областью возможных исходных данных, а внутреннее – областью применимости. Кроме того, имеет место следующие теоремы. Теорема 1 Функция f вычислима тогда и только тогда, когда перечислим ее график. Теорема 2 Подмножество М перечислимого множества Х тогда и только тогда разрешимо относительно Х, когда М и Х\М перечислимы. Теорема 3 Если Р, Q перечислимы, то Р∪ Q, Р∩ Q также перечислимы. Теорема 4 В каждом бесконечном перечислимом множестве Х существует перечислимое подмножество с неперечислимым дополнением. (В силу теоремы 2 это перечислимое подмножество будет неразрешимым относительно Х).

Теорема 5 Для каждого бесконечного перечислимого множества Х существует вычислимая функция, определенная на подмножестве этого множества и не продолжаемая до вычислимой функции, определенной на всем Х. Теоремы 4, 5 в совокупности дают пример алгоритма с неразрешимой областью применимости. Разрешимые и перечислимые множества составляют простейшие и в то же время важнейшие примеры множеств, строение которых задается с помощью тех или иных алгоритмических процедур. Систематическое изучение множеств конструктивных объектов с точки зрения таких свойств этих множеств, которые связаны с наличием тех или иных алгоритмов, образует алгоритмическую теорию множеств (так называемую).

2 Формальная теория вычислимости 2.1 Рекурсивные функции

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

Здесь под числами понимаются натуральные числа или ноль. Обозначим эту совокупность через N={0, 1, 2, ...}. Пустое множество обозначается ∅. Частичные функции из N×…×N=N(k) в N называются k - местными числовыми функциями. Операции над числовыми функциями называются операторами. Определение Пусть f1,...,fn - частичные функции переменных x1,...,xm, определенные на множестве A со значениями в множестве B, f - частичная функция n переменных, определенная на множестве B, со значениями в множестве C. Тогда говорят, что частичная функция g m переменных, определенная на множестве A со значениями в множестве C равенством g(x1,...,xm) = f(f1(x1,...,xm),...,fn(x1,...,xm)), получается операцией суперпозиции из функций f, f1, …, fn. Обозначение операции суперпозиции: Sn+1 (индекс вверху означает число функций). Определение Числовые функции s1(x)=x+1, оn(x1,…,xn)=0, Inm(x1,…,xn)=xm (1≤m≤n, n=1,2,…) называются простейшими. (Индекс 1 иногда будем опускать). Пример - I23(I12, I13, I22) = I13. Определение Пусть заданы числовые частичные функции: g - n -местная, h - (n+2) - местная, f - (n+1) - местная, причем f(x1,…,xn,0)=g(x1,…,xn); f(x1,…,xn,y+1)=h(x1,…,xn,y, f(x1,…,xn,y))

(2.1)

Тогда говорят, что функция f возникает из g и h примитивной рекурсией. Для n=0 (2.1) принимает вид: f(0)=a - константа; f(x+1)=h(x, f(x)).

(2.2)

Равенства (2.1) или (2.2) позволяют последовательно вычислять значения функции в точках y=0, 1, 2,... по значениям функций g и h. Обозначение операции рекурсии: f = R(g, h) , (2.3)

где операция R - двуместная операция, определенная на множестве F всех частичных функций. Если g, h определены всюду, то f определена всюду. 2.1.2 Примитивно рекурсивные функции

Определение Функция f называется примитивно рекурсивной, если ее можно получить из простейших функций s,o, Imn конечным числом операций суперпозиции и примитивной рекурсии. Примечания 1 Операции суперпозиции и примитивной рекурсии, будучи примененными к всюду определенным функциям, дают в результате всюду определенные функции. Поэтому примитивно рекурсивные функции всюду определены, а примитивно рекурсивные относительно G определены всюду, если функции из G всюду определены. 2 Операции суперпозиции и примитивной рекурсии, примененные к частичным примитивно рекурсивным относительно G функциям дают в результате примитивно рекурсивные относительно G функции. Примеры 1 Функции s(x)=s1(x)=x+1, o(x)=o1(x)=0, Imn(x1,…,xn)=xm (m,n=1,2,…) примитивно рекурсивны по определению. 2 Функция on(x1,…,xn)=0 примитивно рекурсивна. 3 Произвольная n-местная постоянная функция допускает представление в виде терма s(s(…s(on(x1,…,xn))…))=a. 4Двуместные функции x+y, xy, xy являются примитивно рекурсивными, как удовлетворяющие схемам соответственно: 1) x+0=x=I'1(x), x+(y+1)=(x+y)+1=S(x+y) с начальными примитивно рекурсивными функциями g(x)=I'1(x), h(x, y, z)=z+1; 2) x0=0(x), x(y+1)=xy+x с функциями g(x)=o(x), h(x, y, z)=z+x; 3) x0=1, xy+1=xyx, т.е. g(x)=1, h(x, y, z)=zx; 1, x = 0, 0, x = 0, sg (x) =  ( sg x = 1 − sgx) удовлетво4) функции sg ( x) =  > 1 , > 0 , 0 , 0 . x x   ряют примитивно рекурсивным схемам sg 0 = 0, sg ( x + 1) = 1, и

sg 0 = 1, sg ( x + 1) = 0, т.е. примитивно рекурсивны.  x − y, x ≥ y, 5) Усеченная разность x −& y =  (всюду определенная) являет0, x < y ся примитивно рекурсивной. Действительно, функция x÷1 удовлетворяет при-

митивно рекурсивной схеме 0 ∸ 1 = 0 (x + 1) ∸1 = x с примитивно рекурсивными начальными функциями o1 и I12 . Кроме того, для любых x, y имеем схему x∸0 = x , x∸(y + 1) = (x∸ y) ∸1, т.е. x ∸ y возникает примитивной рекурсией из I11 и h(x, y, z)=z∸1, что требовалось.

6) Из примитивной рекурсивности функций “+” и “– “следует примитивная рекурсивность функции / x-y /=(x∸y)+(y∸x). 2.1.3 Нумерация n-ок чисел

Определение Канторовское расположение двоек (пар) (x,y) чисел из N имеет вид (0,0), (0,1), (1,0), (0,2), (1,1), (2,0), (0,3),... (2.4) 1 2 3 4 5 6 7 … (пары расположены по возрастанию суммы элементов, а в сумме - по возрастанию первого элемента). Функции n=c(x,y), x= l(n), y=r(n), где n-номер пары (x,y), называются канторовскими нумерационными функциями. Лемма 1 Канторовские нумерационные функции являются примитивно рекурсивными. Лемма 2 Функция Геделя /1/ Г(x,y)=rest(l(x),1+(y+1)r(x)) примитивно рекурсивна. Канторовское расположение n-ок чисел из N определяется равенствами: c 3 ( x1 , x2 , x3 ) = c(c( x1 , x2 ), x3 ); c n+1 ( x1 ,..., xn +1 ) = c n (c( x1 , x2 ), x3 ,..., xn +1 ). Число c n ( x1 ,..., x n ) называется канторовским номером n-ки ( x1 ,..., x n ) . 2.1.4 Операция минимизации. Частично рекурсивные функции

Пусть f - n-местная частичная числовая функция, и известен механизм ее вычисления (в интуитивном смысле), причем механизм работает бесконечно тогда и только тогда, когда значение функции не определено. Рассмотрим относительно y уравнение f(x1,...,xn-1,y)=xn Будем давать переменной y значения 0,1,2,... последовательно и вычислять значения функции f соответственно (при фиксированных x1,...,xn). Определим частичную функцию Mf аргументов x1,...,xn следующим образом. Положим ее значение y=a, если выполнены условия: 1) значение f(x1,...,xn-1 ,y) определено для y=0,1,...,a-1, и f(x1,...,xn-1 ,y)≠xn ; 2) f(x1,...,xn-1 ,a)=xn. Если для набора (x1,...,xn) числа a , удовлетворяющего указанным условиям, не существует, значение y будем считать неопределенным. Определение Оператор M, переводящий функцию f в функцию Mf, называется оператором минимизации. Если заданная функция f одноместна то функция Mf называется обратной функцией для f и обозначается f-1. Примеры 1 Для функций sg и s обратными будут функции  x − 1, x > 0  x, x = 0, 1 ; s −1 ( x) =  . sg −1 x =  не существует, x = 0 не существует, x > 1

2 Рассмотрим функцию y+z. Составим уравнение y+z=x и будем давать переменной z значение 0,1,... . Получим частичную функцию x-y, определенную для x>y; Определение Частичная функция f называется частично рекурсивной, если она может быть получена из простейших функций o, s, Imn конечным числом операций суперпозиции, примитивной рекурсии и минимизации. Примечание - Класс частично рекурсивных функций шире класса примитивно рекурсивных. (Хотя бы потому, что примитивно рекурсивные функции всюду определены, а среди частично рекурсивных встречаются неопределенные всюду). 2.1.5 Тезис Черча

Значение понятия частично рекурсивной функции состоит в следующем. С одной стороны, каждая частично рекурсивная функция вычислима путем процедуры, отвечающей интуитивному представлению об алгоритмах. С другой стороны, какие бы классы алгоритмов ни строились, вычисляемые ими числовые функции оказывались частично рекурсивными. Поэтому ныне общепринятой является следующая естественнонаучная гипотеза. ТЕЗИС ЧЕРЧА Класс алгоритмически (или машинно) вычислимых частичных числовых функций совпадает с классом всех частично рекурсивных функций. 2.1.6 Общерекурсивные функции

Определение Операция Ml , определяемая соотношением Mf , если Mf определена всюду, Ml f = не определена, в противном случае, называется слабой минимизацией функции f. Определение Функции, которые можно получить из простейших функций конечным числом операций суперпозиции, примитивной рекурсии и слабой минимизации, называются общерекурсивными. Примечание - Общерекурсивные функции всюду определены. Теорема Все общерекурсивные функции являются всюду определенными частично рекурсивными функциями. Доказательство следует из определения слабой минимизации. Теорема Каждая всюду определенная частично рекурсивная функция общерекурсивна. Доказательство этой теоремы очень тонкое и здесь не приводится. Лемма 1 Каждая примитивно рекурсивная функция является общерекурсивной. Доказательство следует из определения общерекурсивной функции. Лемма 2 Класс общерекурсивных функций шире класса примитивно рекурсивных функций.

Доказательство следует из построения общерекурсивных функций, не являющихся примитивно рекурсивными. Примером такой функции является функция Аккермана /3/. 2.2 Регистровые машины. Машина Тьюринга

Регистр – это типовой блок в ЭВМ, используемый для хранения одного машинного слова, а также для некоторых манипуляций с этим словом. Регистры всегда входят в состав арифметического устройства, устройства управления, памяти ЭВМ и многие другие блоки. Регистр состоит из линейной цепочки отдельных разрядов, каждый из которых может хранить один бит информации. В зависимости от того, как работают эти цепи, выделяются много типов регистров: адресный, буферный, индексный, регистр команды и другие. Наиболее важными моделями вычислительных устройств регистрового типа являются машина с произвольным доступом к памяти (РАМ – равнодоступная адресная машина) и машина Тьюринга (МТ). В ходе развития теории алгоритмов у А. Тьюринга (1936) возникла концепция точного эквивалента для интуитивного представления об алгоритме в виде абстрактной вычислительной машины. Дадим версию машины Тьюринга, восходящую к Э. Посту. Машина Тьюринга содержит следующие части (рисунок 2.1). 1 ) Внешняя память – конечная лента, разбитая на конечное число ячеек. aj1

aj2

…

ajk qi

…

…

ajr

Рисунок 2.1 В процессе работы машины к существующим ячейкам машина может пристраивать новые ячейки, так что лента может считаться потенциально неограниченной в обе стороны. Каждая ячейка ленты может находиться в одном из конечного множества состояний. Совокупность их называется внешним алфавитом А={а0,а1,…,аm}. Пустые состояния обозначаются а0. В процессе работы машины ячейки ленты могут изменять свои состояния. Просмотр ленты осуществляется слева направо. В каждый такт времени лента имеет некоторую длину r, то есть r ячеек. Состояние ленты описывается словом aj1 aj2 … ajk …ajr, где aj1 – состояние первой слева ячейки, aj2 – второй и т.д. Пустые символы слева и справа можно опускать. 2) Внутренняя память машины – устройство, о котором известно, что в каждый такт времени оно находится в некотором состоянии. Алфавит внутренних состояний, или внутренний алфавит Q = q0,q1,…,qn, где q0 – стоп-символ, или символ заключительного состояния, q1, как правило, - символ начального состояния. 3) Указатель – устройство, которое может перемещаться вдоль ленты так, что в каждый такт времени оно указывает на определенную ячейку ленты.

(Иногда считают указатель неподвижным, а ленту движущийся.) Говорят также, что машина в данный такт «обозревает» соответствующую ячейку. 4) Устройство управления – воображаемый механизм, который в зависимости от состояния воспринимаемой ячейки и состояния внутренней памяти может изменить состояние воспринимаемой ячейки и положение указателя, сдвинув его на соседнюю ячейку влево или вправо. При этом, если необходимо, пристраиваются новые ячейки. Если в некотором такте времени внутренняя память машины приходит в заключительное состояние q0, то дальнейших изменений в машине не происходит, и машина называется остановившейся. Состоянием машины Тьюринга, или конфигурацией, называется слово aj1 aj2 … qi ajk …ajr, образованное вставкой символа внутреннего состояния перед символом обозреваемой ячейки в слове состояния ленты. Это слово конфигурации называется машинным словом. Работа машины состоит в том, что из данного состояния по истечении такта времени она переходит в следующее состояние и так далее. При этом, если машина, имея внутреннее состояние qi и воспринимая ячейку в состоянии aj, переводит внутреннюю память в состояние qs, изменяет aj на аt и передвигает указатель, то говорят, что машина выполняет команду qiaj→ qsаt D, где D – один из символов: L – сдвиг влево, R – сдвиг вправо, Е – нет сдвига. Совокупность всех команд, которые может выполнять машина, называется ее программой. Предполагается, что для каждой пары qi aj имеется не более одной команды. Таким образом, машина Тьюринга считается заданной, если заданы ее внешний, внутренний алфавиты и программа. Пример - Пусть А = 0,1, Q = q0, q1, q2, программа Р =  q10 → q20 R, q20→ q01Е, q11→ q11 R, q21→ q21R, начальное слово µ0 = q111. Тогда, применяя символ перехода состояний =, имеем: q11= 1 q11= 11 q10= 110 q20= 110 q01. Обозначая заключительное слово через µ и символ перехода с произвольным числом тактов − , можно записать: µ0 −P µ. Если за конечное число шагов внутреннее состояние переходит в q0, то говорят, что машина Тьюринга применима к данному слову. В противном случае машина Тьюринга называется «работающей вечно», или неприменимой к данному слову. В частности, возможно зацикливание или отсутствие подходящей команды. Существует много модификаций машин Тьюринга, в том числе, многоленточные МТ, имеющие по одному или несколько указателей на каждой из лент. Есть основания считать, что уточнение общего представления об алгоритме в алфавите, произведенное с помощью МТ, является адекватным. В теории алгоритмов известно следующее соглашение. ТЕЗИС ТЬЮРИНГА Для всякого алгоритма А в каком- либо алфавите может построен тьюринговый алгоритм, дающий при одинаковых исходных данных те же результаты, что и алгоритм А. Согласно этому тезису, всякая вычислимая в интуитивном смысле функция вычислима с помощью некоторой МТ. Принятие тезиса Тьюринга равносильно принятию тезиса Черча для частично рекурсивных функций. 2.3 Нормальные алгоритмы

Наряду с рекурсивными функциями и машинами Тьюринга нормальные алгоритмы (НА) получили известность в качестве одного из наиболее удобных уточнений общего интуитивного представления об алгоритме. Понятие НА было выработано А.А. Марковым (1947). Нормальные алгоритмы оперируют со словами конечной длины, преобразуя их друг в друга с помощью подстановок, то есть замены одних частей слова на другие. Любой нормальный алгоритм в фиксированном алфавите А вполне определяется указанием его схемы – упорядоченного конечного списка подстановок типа U→V (U заменяется на V), где U, V – слова в алфавите А. Заключительная подстановка записывается в виде U→ • V. Нормальный алгоритм работает следующим образом. Пусть Р – заданное слово в фиксированном алфавите. Принимаем его за начальное слово Р0 и строим следующее слово Р1. Если слово Рi (i ≥ 0) построено и работа алгоритма не закончена, то просматриваются подстановки (слева направо) и первая подходящая применяется. Если эта подстановка заключительная, работа заканчивается успешно, если не заключительная, то построено слово Рi +1 и процесс продолжается. Если нет подходящей подстановки, алгоритм не применим к данному слову. Возможна также бесконечная работа алгоритма – неуспех. Пример - Дан алфавит русского языка и схема S = я→ у, л→ у, с→ м, в→ б, р→ m, m→•р, о→ х, н→ а. Тогда, имея слово «слон», можно получить слово «муха». (Проверьте!) В теории алгоритмов строго доказано, что по своим возможностям преобразования нормальных алгоритмов эквивалентны частичным рекурсивным функциям и машинам Тьюринга. Соглашение о том, что для всякого алгоритма А в каком – либо алфавите может быть построен нормальный алгоритм, носит название принципа нормализации. Этот принцип равносилен тезису Черча и тезису Тьюринга. 2.4 Алгоритмические проблемы

Алгоритмическая проблема (АП) – проблема, в которой требуется найти единый метод (алгоритм) для решения бесконечной серии однотипных единичных задач. Примеры 1 Найти алгоритм для выяснения, имеются ли целые корни у данного алгебраического уравнения а0 xn + a1 x n-1 +…+ a n = 0, где а0, a1 ,…, a n - целые числа. Искомый алгоритм существует и основан на факте, что, если такое уравнение имеет целый корень p, то p должно быть делителем числа a n , и для данного уравнения можно найти все делители числа a n , и все их по очереди проверить. Эта задача алгоритмически разрешима. 2 Аналогичная проблема для для уравнения P(x 1 ,…, x m) = 0, где P(x 1 ,…, x m ) – произвольный многочлен с целыми коэффициентами от любого числа m неизвестных (10 – я проблема Гильберта) неразрешима.

Задача называется алгоритмически неразрешимой, если не существует машины Тьюринга (или рекурсивной функции, или нормального алгоритма Маркова), который её решает. Неразрешимой является «проблема остановки»: по описанию алгоритма A и аргументу x выяснить, остановится ли алгоритм, если исходные данные – x. Как следствие этой неразрешимости – невозможность создания общего для любой программы алгоритма отладки программ. Неразрешимой является также проблема распознавания эквивалентности алгоритмов: нельзя построить алгоритм, который по любым двум алгоритмам (программам) выяснял бы, вычисляют они одну функцию или нет. Имеет место следующая теорема. Теорема Райса Никакое нетривиальное свойство вычислимых функций не является разрешимым. Смысл этой теоремы: какое бы свойство вычислимых функций ни взять (периодичность, ограниченность, равенство другой, наперёд заданной функции и т. д.), нельзя построить общий алгоритм, например, машину Тьюринга, который по произвольному алгоритму A определял бы, обладает вычисляемая им функция fA этим свойством или нет. Приведём ещё пример невычислимой функции. Пусть выбрано некоторое уточнение алгоритма. Тогда все алгоритмы, предназначенные для вычисления числовых функций, можно закодировать натуральными числами, Пусть Ai обозначает алгоритм с номером i, а ϕi - функцию, вычисляемую алгоритмом Ai. Требуется построить алгоритм, вычисляющий функцию f(n) = ϕn(n)+1, если алгоритм применим к числу n, и f(n)=0 в противном случае. Эта проблема неразрешима. Действительно, если такой алгоритм Ak существует, то должно быть f(k)=ϕk(k) и f(k)=ϕk(k)+1, что невозможно.

3 Сложность алгоритмов 3.1 Характеристики сложности вычислений

Сложность алгоритма (СА) – величина, характеризующая длину описания или громоздкость процессов его применения к исходным данным /8/. Сложность описания алгоритма зависит от выбора того или иного способа задания алгоритмов. Если такой способ зафиксирован, то СА обычно понимают как длину записи, количество встречающихся в ней выражений определенного типа и т. п. Например, под сложностью описания машины Тьюринга понимают общее число символов внешнего и внутреннего алфавитов, или число команд в программе данной машины. Сложность нормального алгоритма понимают как длину слова, полученного записыванием друг за другом всех формул подстановки в том порядке, как они встречаются в схеме данного алгоритма (между формулами помещается специальный символ). Сложность процесса применения алгоритма к исходным данным называется сложностью вычислений. Сложность вычислений данного алгоритма есть функция, которая каждому объекту из области применимости данного алгоритма сопоставляет число, характеризующее сложность процесса применения этого алгоритма к данному объекту. Сложность работы алгоритма характеризуется длительностью алгоритмического процесса во времени и объемом промежуточных результатов. Для машины Тьюринга – это соответственно число тактов работы машины от исходного слова до результата и количество ячеек ленты, в которых хотя бы раз побывал указатель при работе над словом. Для нормальных алгоритмов аналогичными характеристиками является число применений формул подстановки при работе над исходным словом и максимальная длина слов, появляющихся в процессе применения алгоритма к данному слову. В терминах сложности вычислений удается уточнить и исследовать многие проблемы нахождения оптимального алгоритма решения конкретных задач. Развивается аксиоматический подход к оценке сложности алгоритмов и вычислений. Оценивая сложность различных алгоритмов, следует исходить из некоторой модели исполнителя. Здесь используется модель 1RAM – однопроцессорная машина с равнодоступной памятью /4/. 3.2 Размер входа. Время работы

При исследовании сложности вычислений обычно изучают зависимость времени работ от размера входа /5/. Рассмотрим задачу сортировки. Вход: Последовательность n чисел (а1, …, а n). Выход: Последовательность n чисел (а1′, …, а′n), являющаяся перестановкой входной последовательности и удовлетворяющая условию: а1′≤ …≤ а′ n. Будем называть алгоритм правильным, если на любом допустимом входе он заканчивает работу и выдает результат, удовлетворяющий условиям задачи В этом случае будет говорить также, что алгоритм решает данную задачу.

Пример – Вход : (1,3,2, 4). Выход (1,2,3,4). Сортировка вставками для этого примера описывается последовательностью: (1, 3, 2,4) => (1, 3, 2, 4) => (1, 2, 3, 4) =>(1, 2, 3, 4). Запишем в псевдокоде процедуру Sort_Ins, соответствующую сортировке вставками Sort_Ins (А) 1 for j←2 to length (A) 2 do k ← A (j) 3 i ← j-1 4 while i > 0 and A (i) > k 5 do A(i+1) ← A (i) 6 i ← i-1 7 A (i+1) ← k End {Sort_Ins} Здесь n = length (A), j – очередной элемент вставки; А (1 .. (j –1)) – отсортированный участок, А ((j + 1) .. n) – осталось вставить; k – дублер элемента А (j). Процедура работает следующим образом. В цикле for индекс j пробегает массив слева направо. Извлекается элемент А(j) и вправо сдвигаются элементы, большие его. Освободившееся место этот элемент и занимает. Обратим внимание на то, что отступы соответствуют уровню вложенности операций. Под размером входа понимают либо общее число битов для его представления, либо числом стандартных параметров и т. д. В рассматриваемом примере размером входа будем считать размер сортируемого массива. Время работы можно определять числом элементарных шагов алгоритма, хотя само понятие элементарного шага может каждый раз уточняться. Здесь достаточно каждой строке псевдокода поставить в соответствие стоимость и кратность. Общее время исполнения процедуры найдем умножением и сложением. Еще время уходит на вызов процедуры, но пока его не анализируем. Имеем таблицу: Таблица 3.1 Номер строки

1

2

3

4

5

6

7

Стоимость

С1

С2

С3

С4

С5

С6

С7

Кратность

n

n-1

n-1

n

n

n

j=2

j=2

∑ tJ

∑ (tj-1)

∑ (tj-1) j=2

n-1

Общее время Т(n)=с1n+с2(n-1)+с3(n-1)+с4∑tj+с5∑(tj-1)+с6∑(tj-1)+с7 (n-1); tj– число раз исполнения строки 4, j =2..n. Если массив на входе уже отсортирован, то цикл в строке 4 завершается после первой проверки. Общее время минимально: Т(n)=с1n+с2(n-1)+с3(n-1)+с4

(n-1)+с7(n-1)=аn+b; а=с1+с2+с3+с4+с7, b=-(с2+с3+с4+с7) и является линейной функцией размера входа. Если массив на входе отсортирован в обратном порядке, то tj = j. Общее время максимально: Т(n) = с1n+ с2 (n-1)+с3 (n-1)+с4 (n(n-1)/2 – 1)+ с5 (n-1)/2 + с6(n-1)/2 +с7(n-1)=аn2+bn+c; а=с5/2+с6/2, в=с1+с2+с3+с4/2–с5/2–с6/2+с7, с=-(с2+с3+ с4 с7); учтено, что ∑j=2 n j = n(n=1)/2 – 1, ∑j=1 n (j–1)=n(n=1)/2. Сама функция Т(n) уже квадратичная. Итак, мы рассмотрели худший и лучший случаи. В промежуточном случае, если считать, что в среднем около половины элементов массива А (1..(j–1)) больше А(j), и в строке 4 взять tj = j/2, то окажется, что среднее время квадратично зависит от размера входа – как и в худшем случае (конечно, коэффициенты другие). Среднее время зависит от распределения вероятностей, которое может не быть равномерным. Худшее время – максимальное время по всем входам. Его нужно знать и как срок выполнения любого варианта вычислений и потому, что оно имеет тот же порядок, что и среднее время довольно часто. Функцию времени выполнения алгоритма оценивают по возможности полиномам; если существует полином, эквивалентный функции времени при n→∝, то порядок этого полинома называют порядком роста. Таким образом, порядок роста работы алгоритма (процедуры) Sort_Ins равен двум. Алгоритм с меньшим порядком считается более эффективным, для достаточно больших n, время его выполнения меньше. 3.3 Асимптотика роста функций

Определение 1 Если f(n), g(n), n∈N – некоторые функции, то запись f(n) =Θ(g(n)) означает, что существуют числа с1, с2 >0 и n0∈N такие, что 0≤с1g(n)≤ f(n)≤ с2g(n) для всех n≥n0 (здесь символ “=“ читается как “ есть “). Пример – Проверить, что (1/4)n2-3n=Θ(n2). Проверка – Требуемое неравенство имеет вид с1n2≤(1/4)n2-3n≤с2n2, n≥n0. Это неравенство эквивалентно следующему: с1≤1/4-3/n≤с2, n ≥ n0. Второе неравенство, очевидно, выполняется при с2=1/4 и любого n0∈N. Первое неравенство можно записать в виде n ≥3/(1/4-с1). Если с1=1/5, то достаточно взять n0 = 60. Если f(n)=Θ((n)), то g(n) называется асимптотически точной оценкой для f(n). Заметим, далее, что если f(n) = Θ (g(n)), то и g(n)= Θ(f(n)). Определение 2 Если f(n), g(n), n∈N – некоторые функции, то запись f(n) = О(g(n)) означает, что существуют числа с > 0 и n0 ∈ N такие, что 0 ≤ f(n) ≤ с g(n) для всех n ≥ n0. Определение 3 Если f(n), g(n), n∈N – некоторые функции, то запись f(n) = Ω (g(n)) означает, что существуют числа с > 0 и n0 ∈ N такие, что 0 ≤ сg(n) ≤ f(n) для всех n ≥ n0. Таким образом, Θ – обозначение используется для двусторонней оценки (снизу и сверху), а О- и Ω- обозначения используются для односторонних оценок. Для любых двух функций f(n), g(n), n∈N свойства f(n)= О(g(n)) и g(n)=Ω

(f(n)) равносильны. (Символ «О» читается как «О- большое», символ «Ω» - как «Ω» - большое».) Асимптотические обозначения Θ, О, Ω могут использоваться внутри формул. Например, если имеется запись Т(n) = 2Т(n/2) + Θ(n), то имеется в виду, что функция Θ(n) не меньше с1n и не больше с2n для некоторых констант с1, с2 и достаточно больших n. А цепочка равенств типа 2n2+3n+1 =n2+Θ(n)=Θ(n2) понимается как последовательная асимптотическая оценка функции. Определение 4 Если f(n) = О(f(n)) и lim n→∞(f(n)/g(n))=0, то применяется обозначение f(n)=о(g(n)) (« f от n есть о – малое от g от n»). При этом предполагается, что f(n) и g(n) неотрицательны для достаточно больших n. Определение 5 Если g (n)=o(f(n)), то говорят также, что f(n)= ω(g(n)) («f от n есть ω - малое от g от n»). При этом уже предположено, что f(n) и g (n) неотрицательны для достаточно больших n. Итак, запись f(n)=о(g(n)) означает, что для любого ε> 0 существует n0 ∈ N такое, что 0 ≤ f(n) < εg(n) для всех n ≥ n0, а запись f(n)= ω(g(n)) означает, что для любого с > 0 существует n0 ∈ N такое, что 0 ≤ сg(n) ≤ f(n) для всех n ≥ n0. Примеры 1 2n = о (n2), 2n2 ≠ о (n2) 2 n2/2=ω(n), n2/2 ≠ ω(n2) Введенные характеристики асимптотического поведения функций обладают некоторыми стандартными свойствами. Так, отношения Θ,O,Ω, о, ω транзитивны, Θ, О, Ω рефлексивны, Θ симметрично. Пары отношений О и Ω, а также о и ω взаимно обратимы. 3.4 Оценки роста стандартных функций 3.4.1 Полином от переменной n имеет вид р(n) = ∑i=0dаini. Будем предполагать, что d – степень полинома. Тогда полином р(n)=О(nd). Говорят, что функция f(n) полиномиально ограничена, если f(n) = n O(1), или f(n) = О(nk) для некоторой константы k. 3.4.2 Экспонента от переменной n определяется как функция n → а n, а ≠ 0. При а>1 экспонента растет быстрее любого полинома, то есть nb = o(an). Для вещественных х выполнено неравенство ех>1+х; если х≤1, то имеет место оценка 1+х≤ех≤1+х+х2. Кроме того, можно отметить, что ех=1+х+Θ(х2), х→0. Напомним, что е =2,71828…; ех = ∑k=0∞х k/ k!. 3.4.3 Логарифмы – это функции n→logbn, b>0.Используются обозначения: log(n)=log2(n), ln(n)=loge(n). Напомним, что при х<1 выполняется равенство ln(1+х)=х-х2/2+х3/3-… . Для х>-1 справедливо: х/(1+ х)≤ln(1+х)≤х. Говорят, что функция f(n) ограничена полилогарифмом, если f(n)=logO(1)n. Любой полином растет быстрее любого полилогарифма, то есть log bn=o (nс), с>0. 3.4.4 Факториалы – это функции n→n!= n(n–1)!, n=1, 2,… . Полагают 0!=1. Очевидно, n!≤nn. Более точно, n! = 2πn (n/е)n(1+Θ(1/n)), - формула Сти-

рлинга. Из этой формулы следует, что n!=o(nn), n!=ω(2n), log(n!)= Θ(n log n). Наконец, 2πn (n/е)n≤n!≤ 2πn (n/е) ne1/12n. 3.4.5 Пример - Числа Фибоначчи Ф(0)=0; Ф(1)=1; Ф(n+1)=Ф(n)+Ф(n-1) , n>=2, растут экспоненциально с ростом n. (Начало последовательности: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,…). 3.5 Рекуррентные соотношения

Соотношение, устанавливающее связь между значением функции для данного значения аргумента и значениями этой функции для меньших значений аргумента, называется рекуррентным. Например, время работы процедуры, выполняющей сортировку слиянием, удовлетворяет рекуррентному соотношению: Т(n)=2Т(n/2)+Θ(n), n>1. Решить рекуррентное соотношение – значит с его помощью найти функцию или установить ее асимптотическое поведение. Здесь n – размер входа; для простоты считаем, что n – степень числа 2. Рассмотрим некоторые приемы решения рекуррентных соотношений. 3.5.1 Метод подстановки

Пример – Т(n)=2Т(n/2)+n, где n – степень двойки. Зададимся видом Т(n)=О (n log n) (это нужно суметь), то есть предположим, что Т(n)≤сnlogn для некоторого с. Так как достаточно выполнения оценки, начиная с некоторого n, позаботимся, чтобы с обеспечивало требуемое неравенство при n=2. Предположим теперь, что оценка верна для n/2, то есть Т(n/2)≤с(n/2)log(n/2). Подставим ее в соотношение; получим Т(n)≤с(n/2)log(n/2)+n≤сnlog(n/2)+n=сnlog(n)сnlog(2)+n+с nlog(n)-сn+n≤сnlog(n) (последний переход – при условии с≥1). Итак, Т(n)≤сnlog(n), то есть метод индукции прошел. Делаем вывод: Т(n)=O(nlog(n)). 3.5.2 Метод итераций

Пример – Т(n)=3Т([n/4])+n, где [▪] - целая часть. Подставляя соотношение в себя, получим Т(n)=n+3Т([n/4])=n+3([n/4])+3Т([n/16])=n+3([n/4])+3([n/16])+ 3Т([n/64])))= … ≤n+3n/4+9n/16+27n/64+ … + 3log nΘ(1)≤n∑i=0∝(3/4)i+Θ(nlog43) =4n+o(n)=O(n). Здесь использовано равенство [ [ n/4 ]/4] = [ n/16 ] и подобные. Впрочем, округление здесь не влияет на результат. Поскольку после i -ой итерации справа будет содержаться Т([n/4i]) до Т(1) чтобы дойти, нужно [ n/4i] приравнять 1, то есть получить i>log4n. Но заметив, что [ n/4i] ≤ n/4i, можно оценить наш ряд геометрической прогрессией со знаменателем (3/4) плюс слагаемое 3 log4n, относящееся к задачам ограниченного размера, и заменить указанное слагаемое на nlog43, что есть o(n). 4

3.5.3 Основной результат

Имеет место теорема: Пусть а ≥ 1, b> 1 – константа, f(n) – функция и рекуррентное соотношение Т(n)=аТ(n/b)+f(n), где под n/b понимается одно из двух ближайших целых чисел. Тогда: -для f(n)=O(nlogbа-ε), ε>0 верно, что Т(n)=Θ(nlogbа); -для f(n)=Θ(nlogbа) верно, что Т(n)=Θ(nlogbа log(n)); -для f(n)=Ω( nlogbа+ε), ε>0, причем аf(n/b)≤сf(n) для некоторой константы с < 1 и достаточно больших n, верно, что Т(n)=Θ(f(n)). Суть теоремы – в сравнении функции f(n) с nlogbа , если одна из функций растет быстрее другой, то она и определяет порядок роста Т(n). Если функции одного порядка, появляется логарифмический множитель. 3.6 NР – полнота

Если время работы алгоритма на входе длины n составляет О(nк) при некотором к, не зависящем от n, то алгоритм называется полиномиальным. Задача называется полиномиально разрешимой, если для нее существует полиномиальный алгоритм. Для некоторых задач алгоритмы не полиномиальны. Есть также неразрешимые задачи. Классическая задача – выяснить, останавливается ли данная программа на данном входе, - не может быть решена никаким алгоритмом. Специалисты считают полиномиальные алгоритмы практически приемлемыми, а алгоритмы, требующие времени, «большего», чем полиномиальное, представляющими лишь теоретический интерес. К характеристике полиномиальных алгоритмов следует добавить их замкнутость: композиция (последовательное выполнение) полиномиальных алгоритмов есть полиномиальный алгоритм. Достаточно полное изложение вопросов сложности алгоритмов имеется в /5/. Здесь приводятся лишь некоторые сведения. 3.6.1 Задачи разрешения. Класс P

Рассмотрим абстрактную задачу – бинарное отношение β между элементами множества условий U и множества решений V. Например, в задаче обхода графа условиями являются матрицы смежностей, а решениями – последовательности вершин. Задачами разрешения называются задачи, в которых требуется ответить («да» или «нет») на поставленный вопрос, то есть построить функцию f с областью определения U и множеством значений V= 0,1. Если предполагать, что входные данные для алгоритма представлены последовательностью битов (или последовательностью символов другого алфавита мощности ≥2), то абстрактная задача переходит в так называемую строковую задачу. Строковая задача называется полиномиальной, если существует алгоритм, который решает ее при длине входа n за время О (nк) для некоторого к. Множество полиномиальных строковых задач разрешения называется сложностным классом Р. Функция f: 0,1*→0, 1 называется вычислимой за полиномиальное время, если существует полиномиальный алгоритм, перево-

дящий х∈0,1* в y∈0, 1. Если существуют две вычислимые за полиномиальное время функции f12, f21, переводящие два представления множества U друг в друга, то эти представления называются полиномиально связанными. Справедливо следующее утверждение. Основная лемма Пусть имеется абстрактная задача разрешения с множеством условий U. Тогда для любых двух полиномиально связанных представлений множества U соответствующие строковые задачи, при условии их полиномиальности, эквивалентны с точки зрения их принадлежности классу Р. В силу этой леммы можно, как правило, не различать абстрактную задачу и ее строковое представление. Для задач разрешения используются формальные языки и грамматики. 3.6.2 Допускающие и распознающие языки

Языком L над алфавитом А называется некоторое множество последовательностей символов (слов) алфавита А (построенных по определенным правилам) Пример –L = ∧, 0, 1, 0110, 11, 001, … A={0,1}. Символ ∧ означает пустое слово, символ Ф означает пустой язык. Язык, состоящий из всех возможных слов над заданным алфавитом А обозначается через А*. Таким образом L⊂ А* для любого языка L над алфавитом А. На примере языков L⊂0,1* введём ещё несколько понятий из теории формальных языков. Говорят, что алгоритм A допускает слово x∈{0, 1}*, если А (х) = 1; отвергает, - если А(х) = 0. Алгоритм называется допускающим язык L, если алгоритм допускает все слова L и только их. Если алгоритм допускает все слова из L и не допускает слова из СL, то говорят, что этот алгоритм распознает язык . Язык L допускается  распознается за полиномиальное время если каждое слово языка допускается  распознается за время не большее O(nк) (n – длина слова х, к не зависит от х, соответствующим допускающим  распознающим языком. На основании введенных понятий можно определить класс Р следующим образом: Р = L⊂0, 1 * существует алгоритм А, распознающий язык  за полиномиальное время  . Имеет место теорема: Р = L  L допускается за полиномиальное время . Таким образом, в рассмотренной ситуации допускающие и распознающие за полиномиальное время языки эквивалентны. 3.6 3 Проверяющие алгоритмы Рассмотрим задачу разрешения, связанную с задачей поиска кратчайшего пути в графе. Дан неориентированный граф G = (X, Y), X – множество вершин, Y – множество ребер. Требуется для двух вершин графа построить кратчайший путь между ними. Это задача о кратчайшем пути. Здесь условием u является тройка (G, x1, x2),x1, x2 ∈X, а решением v – последовательность (x1, …,x2) вершин графа, составляющих требуемый путь. Одна из задач разрешения: по двум вершинам графа и числу k определить, существует ли в графе путь, связывающий заданные вершины, длина которого ≤ k. Теперь условием u является (G, x1,

x2, k), а решение v ∈{0, 1}, причём`v =1, если такой путь есть; v = 0 в противном случае. Существует алгоритм поиска в ширину на графе, с помощью которого сформулированная задача решается за полиномиальное время. Рассмотрим теперь задачу о гамильтоновом цикле. Напомним, гамильтоновым циклом в неориентированном графе называется простой цикл, который проходит через все вершины графа. Задача о гамильтоновом цикле состоит в ответе на вопрос, имеет ли данный граф гамильтонов цикл. Если в качестве решения организовать перебор перестановок вершин и проверку этих перестановок на гамильтоновость, то, как и следует ожидать, время работы не будет полиномиальным; более точно, время работы такого алгоритма равно Ω (2 √ n), где n – длина представления графа. ( Напомним, что число перестановок из m элементов равно m!. («эм – факториал»). Имеет место теорема: задача о гамильтоновом цикле является NP – полной. К раскрытию понятия NP – полноты мы и переходим в следующих пунктах. Проверяющим алгоритмом называется алгоритм А, имеющий два параметра; первый – входная строка, второй – образец (или сертификат). Такой алгоритм считаем допускающим вход u, если существует образец v, для которого А (и, v) = 1. Языком, проверяемым алгоритмом А, называется язык L =u ∈0,1 *  ( ∃ v ∈0,1 * А (u, v) = 1) . Итак, алгоритм А проверяет язык L, если для любого слова u∈СL найдется образец v, с помощью которого А может проверить принадлежность слова и языку L, а для строки не принадлежащей языку такого образца нет. В задаче о гамильтоновом цикле образцами могут быть последовательности вершин, образующие гамильтонов цикл. Гамильтоновость цикла в графе можно проверить за полиномиальное время. 3.6.4 Класс NP

Множество языков, для которых имеются работающие полиномиальное время проверяющие алгоритмы ( с образцами, ограниченными по длине некоторыми многочленами) называется сложностным классом NP. Заметим, что проверка языка в данном контексте несколько отличается от проверки языка как таковой. А именно: для U∉ L могут существовать длинные образцы, которые в данном контексте отбрасываются (и потому остаются непроверенными в прежнем смысле). Очевидно, всякую задачу из Р можно считать входящей в NP: полиномиальный алгоритм, распознающий язык, в этом случае уже существует, и для этого языка строится проверяющий алгоритм, не учитывающий второй параметр. Итак, Р⊂ NP. Совпадают ли классы Р и NP?. Большинство специалистов полагают, что в NP есть задачи, не решаемые за полиномиальное время. 3.6.5 Сводимость языков. NP – полнота языков

Обычно мы полагаем, что одна задача сводится к другой, если (возможно) преобразованные входы первой задачи являются входами другой. Говорят, что

язык L1 сводится к языку L2, если существует такая функция f:  0,1 *→0,1*, что для любого x ∈0,1* свойства x ∈ L1 и f(х) ∈ L2 эквивалентны. Функция f называется сводящей функцией, а алгоритм, вычисляющий функцию f, – сводящим алгоритмом. Если функция f вычислима за полиномиальное время, то говорят, что язык L1 сводится к языку L2 за полиномиальное время и используют запись: L1 ≤ р L2. Сводящая функция переводит любое слово x ∈ L1 в слово f(х) ∈ L2, а слово х ∉ L1 – в слово f(х) ∉ L2. Поэтому по ответу на вопрос: «f(х) ∈ 2?» мы получаем ответ на вопрос «х ∈ L1?». Справедливо утверждение: Если языки L1, L2 ⊂  0,1*, и L1 ≤ р L2, то из L2 ∈ Р следует, что L1∈ Р. При этом запись L1 ≤ р L2 можно интерпретировать так, что сложность языка L1 не более чем полиномиально превосходит сложность языка L2. Основное определение Язык L1⊂ 0, 1* называется NP – полным, если выполняются условия: 1) L1∈ NP; 2) для любого L2 ∈ NP выполняется отношение L2 ≤ р L1. Язык L1⊂ 0,1* называется NP – трудным, если выполнено условие 2), а условие 1) может выполняться или не выполняться. Основная теорема Если некоторая NP – полная задача разрешима за полиномиальное время, то Р = NP. Иначе говоря, если в классе NP есть задача, не разрешимая за полиномиальное время, то все NP – полные задачи таковы. Доказательство Если некоторый язык L1 является NP – полным и в то же время разрешимым за полиномиальное время, то для любого языка L2 ∈ NP из свойства 2) основного определения следует, что L2 ≤р L1. Последнее означает, что L2∈Р. Утверждение в первой формулировке доказано. Вторая формулировка теоремы эквивалентна первой. В соответствии с этой теоремой предположение о том, что Р ≠ NP означает, что NP – полные задачи не могут быть решены за полиномиальное время. Пока никто не предъявил полиномиальный алгоритм для решения NP – полной задачи, и никто не доказал N ≠ NP. 3.6.6 Примеры NP – полных задач

Имеется множество NP – полных задач в различных разделах математики: логике, графах, алгебре и так далее. Рассмотрим несколько примеров. 1 Задача о выполнимости схемы Дана схема, состоящая из элементов «и», «или», «не». Требуется выяснить, является ли эта схема выполнимой. При этом схема из функциональных элементов с несколькими входами и одним выходом называется выполнимой, если существует входной булев вектор, для которого выходной скаляр есть единица. Как уже известно, эта задача сводится к задаче о выполнимости пропозициональной формулы ϕ ≡ ((х1→х2) ∨  ((х1 ↔ х3) ∨ х4 )) ∧  х2 имеет выполняющий набор (х1, х2, х3, х4) = (0, 0, 1, 1). (проверьте!) Выполнимость можно проверить, перебрав все наборы значений переменных (для формулы с n переменными их 2n). В данном случае достаточно проверку провести для представленного образца. Переборный алгоритм как видно, не является

полиномиальным . Имеет место теорема: задача о выполнимости формулы NР полна. Предупреждение: естественный способ построение формулы, которая вычисляет туже функцию, что и заданная схема, состоящий в последовательной записи подформул, отвечающих тому или иному элементу (например, для выхода элемента «и» формула имеет вид ϕ1∧ ϕ2, где ϕ1, ϕ2 – формулы, соответствующие входам элемента), не является полиномиальным. Общая идея составления формулы, которую строит «нужный» сводящий алгоритм – в том, что вводится дополнительная переменная для каждого провода в схеме (а не только ее входов). Например, схеме (рисунок 3.1) соответствует формула ϕ = х8 ∧ (х8 ↔(х7 ∨ х6)) ∧ (х7 ↔ (х4 ∨ х5)) ∧ (х6 ↔ (х2 ∨х3) ∧ (х5 ↔  х3) ∧ (х4 ↔ (х1 ∧х2)). Такое построение приводит к схеме полиномиального размера и выполняется за полиномиальное время. х1

Λ

х4

V

х2

х7

х5



V

х3 х6

х8

V

Рисунок 3.1 2 Задача о клике Дан граф. Найти максимальный размер клики в этом графе. Напомним, клика в неориентированном графе есть полный подграф данного графа. Размером клики называется число ее вершин. 3 Задача о суммах подмножеств Требуется выяснить, существует ли подмножество данного множества с заданной суммой элементов.

4 Разработка алгоритмов и программ 4.1 Основные технологии

Программа – это запись алгоритма на языке, понятном исполнителю. С массовым внедрением вычислительных машин процесс программирования для них превращается в промышленное изготовление программ. Для этой цели создаются разнообразные технологии программирования. Основные из них: нисходящее программирование и восходящее программирование. Нисходящее программирование (программирование «сверху – вниз») основывается на идее декомпозиции исходной задачи на ряд подзадач: строится программа, в которой эти подзадачи выступают как некоторые именованные процедуры и к ним организуется обращение. Те подзадачи, которые еще не обработаны. Временно заменяются «заглушками». Затем по отношению к подзадачам применяется такой же прием. Выходящее программирование (программирование «сверху – вниз») основано на противоположном процесс: сначала пишутся и отлаживаются программы самого нижнего уровня; затем они собираются в блоки, все более крупные. Наконец, идет сборка всей программы, и программа отлаживается. Есть еще одна технология - технология пакетов прикладных программ. В этом случая новая задача решается путем комбинации отлаженных автономных модулей. Здесь использован опыт библиотек стандартных программ. В программировании выделяют два направления: прикладное программирование и системное программирование. Цель первого – разработка средств подготовки задач к решению на ЭВМ, цель второго – создать программное обеспечение реализации вычислительного процесса на ЭВМ и обмена информацией ЭВМ с внешним миром. Основные задачи системного программирования – разработка и совершенствование языков программирования, а также трансляторов для перевода программ с этих языков на машинный уровень; создание операционных систем для новых типов ЭВМ, разработка сервисных программ. Развивается направление в системном программировании программных систем искусственного интеллекта, языков извлечения и представления знаний. Поскольку язык реальной ЭВМ достаточно беден, в программировании имеет дело с виртуальной вычислительной машиной, состоящей частично из аппаратуры и частично из программного обеспечения, то есть программа моделируется более мощной входной язык. Перевод входного языка в машинный выполняют программы трансляторы. Трансляция может быть одно- и многошаговой, в зависимости от числа уровней в иерархии виртуальных ЭВМ. Уже разработаны тысячи языков программирования, существуют различные их классификации. Одна из них делит языки программирования на языки низкого, высокого и сверхвысокого уровня. Все языки низкого уровня ориентированы на тип аппаратуры. Популярными считаются языки ассемблеров для систем команд IBM – PC и VAX.Языки высокого уровня ориентированы на систему операторов (присваивание, перехода, цикла, условные операторы, операторы ввода – вывода) и описаний данных. Используемых в программе. Языки высокого уровня – ФОРТРАН, АЛГОЛ, ПАСКАЛЬ, АДА. К языкам сверхвысокого уров-

ня относят Algol – 68 и APL; они обладают дополнительными средствами описания обработки данных. По другой классификации языки программирования делятся на вычислительные и языки символьной обработки. К последним относятся ЛИСП, ПРОЛОГ, РЕФАЛ. С прикладной точки зрения ФОРТРАН, АЛГОЛ- 60, ПАСКАЛЬ ориентированы на научные и инженерные расчеты, КОБОЛ – типичный язык обработки экономической информации, СИМУЛА – 67 – язык имитационного моделирования. 4.2 Сортировка

Пусть задан файл φ, состоящий из записей: φ (1),…,φ(n). Каждой записи поставим в соответствии ключ ki, i=1…n.Обычно ключ – это какое-либо отдельное поле или комбинация полей записи (некоторый признак записи). Будем предполагать, что на множестве ключей задано отношение линейного порядка (следования) с обычными свойствами. Задача сортировки файла ставится так: найти перестановку записей µ (1),…,µ (n) такую, чтобы их ключи располагались в неубывающем порядке: k µ(1) ≤ …≤ k µ(n). Во многих случаях не требуется реально иметь перестановку, а достаточно, например, составить список индексов (адресов) элементов перестановки в исходном файле. Составление списка индексного списка называют индексный сортировкой. Впрочем, имея индексный список. Нетрудно произвести собственно сортировку. Пример – Дан массив чисел (4, 5, 3, 8, 1, 9, 3, 2). Обычная сортировка: 1, 2, 3, 5, 4, 5, 8,9; индексная сортировка: 5, 8, 3, 7, 1, 2, 4, 6. Имеется много алгоритмов сортировок /6/. 4.2.1 «Пузырьковая сортировка»

Название ассоциирует перемещение «малых» элементов со «всплытием». Итак, пусть S – числовой массив а (1), …,а (n). Говорят, элементы а (i), а(j) образуют инверсию, если i < j и а (i) > а(j). Тогда алгоритм «пузырьковой сортировки» состоит в последовательных просмотрах от конца к началу массива S и обмена местами соседних элементов с инверсией. Вход: массив S(1), …, S(n). Вывод: массив S(1) ≤ S … < S(n). Процедура Рus(S,n) 1 for i ←2, to n do 2 for j ← n to I do 3 if a(j – 1) > a(j) then swap(A(j-1),A(j)) End {Pus} Трудоемкость этого алгоритма равна О(n2), то есть при любых S и n он решает задачу за сn2 операций сравнений и обменов, где с – константа, не зависящая от n. Пузырьковая сортировка не требует для реализации дополнительной памяти, но временные характеристики – низкие. На практике используется редко.

4.2.2 Сортировка с помощью двоичного (бинарного) дерева

Бинарное дерево – ациклический граф с выделенной вершиной (корнем), у которой нет предшественников. Адрес корня – 1.Любая другая вершина имеет

Уровень 0 Уровень 1 Уровень 2

Уровень 3

Рисунок 4.1 только одного предшественника и одного или двух преемников. (рисунок 4.1). Для каждой вершины k, k=1…n, могут быть вычислены адреса предшественников и преемников по формулам: - для родителей х(k) =k\2, k=1… n; - для потомков слева у(k)= 2k, k=1…(n\2), yk=0, k> (n\2), - для потомков справа z(k)= 2k+1, k=1…((n-1)\2), z(k)= 0, k > (n-1)\2. Нумерация вершин (адресация) идет по уровням (сверху–вниз, слева– направо). Сортировка с помощью бинарного дерева выполняется следующим образом. Элементы массива помещаем в вершины нижнего уровня (рисунок 4.2). Первый этап – построение дерева. На первом шаге попарным сравнением надстраиваем уровень дерева и помещаем в вершины – родители меньшие элементы пары потомков. На втором шаге надстраиваем очередной уровень дерева (по аналогичному правилу) и т.д. В результате построения дерева его корнем будет минимальный элемент. Второй этап – собственно сортировка. Объявляем число µ в корне дерева очередным элементом сортированного массива и спускаемся в дереве Д по обозначенному им пути. Если путей несколько, выбираем тот, который включает потомков слева. Заменяем в нижнем уровне µ на +∞ и выполняем пересчет верхних уровней с учетом замены. Результат пересчета показан на рисунке 4.3. После n-кратного выполнения этапа 2 дерево D будет состоять из значений +∞, и процесс сортировки закончится. Для однократного выполнения второго этапа требуется выполнить log n сравнений. Поэтому общая трудоемкость сортировки составляет O(n log n) операций.

1 1

1 1

4 1

9

9

14

8

1

4

1

5

3

9 4

9

12 3

1 17

1

3

Рисунок 4.2 4.2.3 Быстрая сортировка

Пусть S(k), k=1..n – одномерный массив и х ∈ S(k) Просматриваем S слева направо, пока не найдем а > х, и просматриваем S справа налево, пока не найдем b< х. Меняем местами а и b Продолжая этот процесс, придем к последовательности, разделенной на две части S1 и S2 такой, что элементы из S1 не превосходят х, а элементы из S2 не меньше х. Пример – Массив – 6; 23, 17, 8, 14 , 25, 6, 3, 30, 7

Последовательность: 6, 7, 3, 8, 6 25, 14, 17, 30, 23. Значение х для массива будем выбирать так: если количество элементов в S нечетно, то это будет средний элемент, если четно, то из двух средних выбирать элемент с меньшим индексом. Итак, мы рассмотрим процедуру разделения. Теперь опишем процедуру быстрой сортировки. Разобьем S на две части S1 и S2 как только что было описано. Теперь поступим также с каждой из частей S1 и S2 и так далее, пока каждая из частей не будет содержать ровно 1 элемент. В результате получится отсортированный массив. При реализации этой процедуры на ЭВМ надо предусмотреть хранение адресов раздваиваемых подмассивов. Если каждый раз продолжать работу с меньшей из полученных частей, отправляя адреса начала и конца второй части на хранение, то потребуется запоминание не более 2 log(n) адресов (чисел). Можно хранить эти адреса в виде наращиваемого стека, обрабатывается первым. С другой стороны. Следует иметь в виду, что для «быстрой сортировки» нет гарантированной трудоемкости типа 0 (n log n), где n – число элементов массива. В иных ситуациях трудое-

мкость достигает 0 (n^2) (например, для упорядоченных массивов). По образному выражению Н.Вирта, «быстрая сортировка напоминает азартную игру, где следует рассчитать, сколько можно позволить себе проиграть в случае невезения». 4.3 Поиск

Типичными примерами поиска служат работа со справочником, каталогом в библиотеке, таблицами. Пусть файл ϕ состоит из записей ϕ(1),…, ϕ(n) с ключами kµ(i) ,i=1..n, k – некоторое значение. Рассматривается четыре вида простейших задач поиска: 1) Требуется определить по крайней мере одну запись в µ имеющую k своим ключом; 2) Требуется определить все записи в µ, имеющие k своим ключом; 3) Если в µ нет записей с ключом k, то добавить в µ новую запись; 4)Включить в µ новую запись. Число k называют аргументом поиска, или запросом, задачи 1 и 2 – простым поиском, 3 и 4 – поиском со вставкой. Поиск в задачах 1 и 2 может быть безрезультатным. В задачах 1-3 поиск может быть организован по выполнению условия а ≤ kµ(i) ≤ b, где а и b – константы и других условий. Здесь, как и раннее, под файлом будем понимать одномерный или двумерный числовой или символьный массив, то есть вести поиск в одномерной или двумерной таблице. Эффективность алгоритмов поиска зависит от организации исходной информации. В частности полезным предварительным преобразованием µ может оказаться сортировка. 4.3.1 Просмотр всех подряд записей до получения решения задач 1-3 называется последовательным поиском. 4.3.2 Бинарный поиск упорядоченного массива состоит в следующем. Сначала К сравнивается со средним ключом в таблице. Результат сравнения или приводит к решению задачи, или позволяет определить, в какой части массива продолжить поиск. Применяя этот принцип к «половинному» массиву, через не более чем log n сравнений, получается положительный или отрицательный ответ. 4.3.3 Задача поиска в сети ставится следующим образом. Пусть задана ориентированная сеть S= (Р, R, d), где Р – множество вершин, R – множество дуг; d – функция, определенная на R со значениями в множестве действительных чисел. Иногда d(х, у) интерпретирует как длина дуги (х, у) ∈ R. Основными подзадачами в алгоритмах оптимизации на сетях являются: - определение всех дуг сети вида (х, у) для фиксированной вершины х ∈ Р, то есть определение всех выходов у для данного х; - определение всех дуг сети вида (у, х) для фиксированной вершины х ∈ Р, то есть определение всех входов у для данного х;

Рассмотрим способ ускорения поиска в сети. Пусть решается задача определения выходов (рисунок 4.3). Считаем, что S представлена в оперативной памяти в виде массива дуг µ (таблица 4.1). 4

3

4

3

5

2

1

2 5

5

1

6

2

1

1

3

2 9

8

7

3

Рисунок 4.3 Отсортируем файл y по ключу х. В этом случае среднее время нахождения всех дуг (х, у) даже при последовательном поиске сократится примерно вдвое. Таблица 4.1 Индекс х 1 7 2 3 3 5 4 9 5 4 6 8 7 3 8 7

Дуга у

d 8 4 9 5 5 9 6 6

3 4 1 3 2 1 1 1

Индекс 9 10 11 12 13 14 15

х 1 1 6 1 6 6 6

Дуга у 3 7 4 6 8 5 9

d 3 2 2 5 3 5 2

Пусть имеется некоторый вспомогательный массив А, в позициях x которого записан адрес А(х) расположения в µ начальной дуги вида (x, y). В этом случае проблема поиска всех дуг (x, y) сводится к выборам адреса А(х). Если, например, требуется найти в µ все дуги вида (х0, у), то получив А(х0) = у0 мы попадаем на подмассив выходов из х0. Этот способ решения задачи полагает, что х∈Р – это натуральные числа. Для минимизации объема дополнительной памяти, то есть величина t=maxx∈P(x), удобно иметь последовательную нумерацию вершин, начиная с 1. Теперь о второй задаче. Если отсортировать µ по у, то удастся построить аналогичный простой механизм поиска входов в конкретную вершину. Однако, чтобы не потерять возможность эффективно решать предыдущую задачу, поступим следующим образом. Введем два массива В(х) и С(х). Массив В(х) уст-

роим также как и А(х). В позиции х величина В(х) есть адрес α первый от начала строки в µ с дугой (у, х). Если перейти на этот адрес α в µ, то затем можно воспользоваться массивом С(х), в котором по адресу α хранится адрес следующей дуги с тем же х. Символ ∅ в В(х) используется для указания отсутствия входов в х, а в С(х) – для отсутствия очередного входа в х (то есть как метка завершения соответствующего подмассива входов). Итак, проблема поиска всех входов в х решается выборкой сначала адреса В(х) и затем последовательных адресов из С. Формирование массивов В и С приводит, можно сказать, к адресному кодированию µ, или осуществляется адресная сортировка µ по у. 4.4 Алгоритмы перебора 4.4.1 Полный перебор

Рассмотрим задачу генерации перестановок (ГП). Постановка задачи Дано множество n попарно различных действительных чисел: S = {a1, …, an}. Требуется перечислить все N = n! перестановок элементов ак, к = 1…n этого массива. Алгоритм ГП Шаг 1 Производится сортировка массива по убыванию его элементов. Полученная перестановка считается начальной и выводится. Далее идет работа с индексами элементов i ∈ {1… n}. Шаг 2 Находится наименьший индекс i∈{2… n}, для которого аi - 1 > аi. Шаг 3 Находится наименьший индекс j∈{1…(n - 1)}, для которого аj > аi. Шаг 4 Обмен значениями аi и аj. Шаг 5 Обмениваем значениями компоненты в парах: (а1,аi - 1),…,(ак,аi - к ), к = [(i - 1) / 2]. Шаг 6 Вывод полученной перестановки. Если число выведенных перестановок < N, переход на шаг 2, в противном случае задача решена. Алгоритм требует осторожности при работе с большими n, так как N = n! растет очень быстро. Например, 10! = 3628800. Пример – Для начальной перестановки (3, 2, 1) следующими выводами перестановками будут: (2,3,1), (3,1,2), (1,3,2), (2,1,3), (1,2,3). (Имеется множество других алгоритмов).

4.4.2 Метод ветвей и границ

Рассмотрим задачу о коммивояжере. Постановка задачи Дано множество пунктов S = {1 … n} и сеть сообщений между ними. Конкретный пример дан рисунком 4.4 (граф) и матрицей A. Элемент aij, i,j∈ {1…n}, матрицы А показывает некоторую характеристику дуги (стоимость проезда) из пункта i (номер строки) в пункт j (номер столбца). Тре-

буется составить замкнутый маршрут, соединяющий все пункты и проходящий через каждый пункт ровно один раз. Дополнительное условие: сумма характеристик дуг маршрута (суммарная стоимость проезда) – минимальна. Решение задачи для небольших n может быть проведено следующим образом. Строим последовательно перестановки из номеров пунктов и для допустимых перестановок запоминаем лучшие суммы. Таким образом, для n пунктов просматривается (n - 1)! маршрутов. При n = 5, (n - 1)! = 24. Для больших n (но не очень – факториал быстро растет) применяется метод ветвей и границ.

1

2

3

4

∞ 18 28 22 24 4 ∞ 12 ∞ 29 22 19 ∞ 8 9 A= 7 ∞ 18 ∞ 9

5

29 16 10 10

∞

Рисунок 4.4 Приведем алгоритм ветвей, дающий все допустимые маршруты коммивояжера. Пусть S – цепочка элементов. Полагаем S = ( ), i = 1. Шаг 1 Выбор базы. В матрице А выбираем элемент ai j ≠ ∞ (можно с меньшим j), если существует. (Если такого элемента нет, продвижение в этом направлении невозможно). Шаг 2 Ветвление. По матрице А строим матрицы А1, А2. Построение А1 Полагаем S = S + ai j. Берем матрицу А, полагаем элементы i – строки, j – столбца равными ∞. Сам элемент ai j не меняем. Предотвращаем циклы, полагая a j i = ∞ (в общем случае для цепочки (ai j , a j к , a lm) полагаем a m i = ∞). Построение А2 Полагаем ai j в матрице А (остальные элементы – без изменения). С каждой из матриц А1, А2 и соответствующими цепочками идем на выполнение шага 1. При этом поиск базы производим в общем случае цепочки (ai j , a j к , a lm) в m – строке. Шаги 1, 2 выполняются до достижения длины n цепочки (есть маршрут) или цепочка имеет меньшую длину, но очередной выбор базы невозможен (маршрута с таким подмаршрутом нет). По достижении длины n – 1 вместо предотвращения надо провести проверку: если ami ≠ ∞, то присоединяя ami к цепочке, получаем маршрут, если ami = ∞, маршрута с подмаршрутом, соответствующим имеющейся цепочке, нет. Конец алгоритма. Для выбора маршрута с наименьшей стоимостью надо каждой цепочке ставить в соответствие ее суммарную стоимость. С момента построения какоголибо допустимого маршрута коммивояжера надо удерживать лишь маршруты с

наименьшей на данный момент стоимостью и цепочки с наибольшей стоимостью, чем удержанный маршрут. Для приведённого примера оптимальный маршрут коммивояжера: (а12, а23, а35, а54, а41) имеет стоимость 56. Маршрут можно записать также в виде: 1→2→3→5→4→1. 4.5 Рекурсивные алгоритмы

Объект называется рекурсивным, если он прямо или косвенно обращается к себе. Рекурсия является обобщением итерации (повтора). Повтор в языках программирования организуется с помощью оператор цикла. Рекурсия формируется на основе подпрограммы, вызывающей себя. Первый вызов выполняется из внешней программной единицы. При этом особое внимание должно уделяться условиям выхода из рекурсии. Рассмотрим несколько задач с применением рекурсивных алгоритмов /7/. 1 Ханойские башни Существует легенда: «В храме Бендареса находится бронзовая плита с тремя алмазными стержнями. На один из стержней бог при сотворении мира нанизал 64 диска разного диаметра из чистого золота. Наибольший диск лежит на бронзовой плите и с остальными образует пирамиду, сужающуюся кверху. Это – башня Брамы. Работая день и ночь, жрецы переносят диски с одного стержня на другой, следуя законам Брамы: 1) диски можно перемещать с одного стержня на другой только по одному; 2) нельзя класть больший диск на меньший: 3)при переносе дисков с одного стержня на другой можно использовать промежуточный третий стержень, на котором диски тоже могут находиться тоже только в виде пирамиды. Когда все 64 диска будут перенесены с одного стержня на другой, наступит конец света». Рекурсивная программа на языке программирования Turbo Pascal перемещения дисков может выглядеть следующим образом. Здесь N – число дисков, X, Y, Z – переменные диски, A, B, C – их конкретные имена. PROGRAM HANOI; VAR N: INTEGER; X, Y, Z: CHAR; PROCEDURE HAN(N: INTEGER; VAR X, Y, Z: CHAR); BEGIN IF N>0 THEN BEGIN HAN(N-1, X, Z, Y,); WRITELN(X,’→’,Y,’ ’); HAN(N-1, Z, Y, X) END END; BEGIN WRITELN(‘ВВОД N, X, Y, Z’); READ(N, X, Y, Z); HAN(N, X, Y, Z); WRITELN END. В результате запуска программы может получиться: ВВОД N, X, Y, Z 4ABC A→C C→B A→C B→A B→C A→C A→B C→B C→A

B→A C→B A→C A→C A→B C→B (Стрелки означают перемещение диска со стержня с именем, указанным слева, на диск с именем, указанным справа.) Примечание – Ввод достаточно больших чисел требует модификации программы. 2 Задача Фибоначчи (1228) «Некто поместил пару кроликов в некоем месте. Природа кроликов такова, что каждый месяц пара кроликов производит на свет другую пару, а начинают рождать через 2 месяца после своего рождения. Сколько пар кроликов будет через 12 месяцев?» Эта задача сводится к последовательности чисел 1, 1, 2, 3, 5, 8, 13, 21, …, при этом каждое следующее число, начиная с третьего, равно сумме двух предыдущих. Программу можно составить с применением рекурсивной функции FIB. PROGRAM CROL; VAR N, CR:INTEGER; {N - число месяцев, CR – число кроликов} FUNCTION FIB(N:INTEGER):INTEGER; BEGIN IF (N=1) OR (N-2) THEN FIB:=1 ELSE FIB:=FIB(N-1)+FIB(N-2) END; BEGIN WRITE (‘Ввод N’);READ(N); CR:=FIB(N); WRITE(‘Число пар кроликов =’,CR:5 END. Первый вызов функции происходит в основной программе, а затем выполняется рекурсивный вызов внутри функции. Пример выполнения программы: Ввод N 12 Число пар кроликов = 233. 4.6 Жадные алгоритмы

Жадный алгоритм – это алгоритм, на каждом шаге которого выбирается оптимум, соответствующий условиям этого шага. Такой локально оптимальный алгоритм далеко не всегда дает глобальный оптимум. В то же время имеются классы жадных алгоритмов, дающих глобальный оптимум /5/. Пример – Кратчайший путь из А в B имеет длину 16 (АЕВ, например); по локально оптимальному алгоритму получается длина, равная 30 (ACFDGEB) (рисунок 4.5). Говорят, что к оптимизационной задаче применим принцип жадного выбора, если последовательность локально оптимальных (жадных) выборов дает глобально оптимальное решение. Дает ли данный алгоритм оптимальное решение определить не просто. Достаточными условиями являются: жадный выбор на первом шаге не исключает оптимального решения (то есть возможно продолжение с результатом, не уступающим оптимальному решению), и подзадача, возникающая после жадного выбора на первом шаге, аналогична исходной. (Вывод об оптимальности теперь можно сделать по индукции.) Решаемые с помощью жадных алгоритмов задачи обладают (как и в динамическом программировании) свойством оптимальности для подзадач.

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

11

C

10

E

4

5

1

2 D

F

6

7

G

8

3 B

Рисунок 4.5 Если задача порождает множество подзадач, то, как правило, необходимо динамическое программирование. Например, непрерывная задача о рюкзаке решается с помощью жадного алгоритма, а дискретная − динамического программирования. Напомним дискретную задачу о рюкзаке: имеется n вещей стоимостями ci и весами vi, i=1..n. Требуется отобрать вещи с наибольшей общей стоимостью и общим весом ≤ V. В случае непрерывной задачи вес vi произволен для каждого i=1..n. 4.6.1 Равномерные и неравномерные коды

Допустим, строится посимвольный двоичный код, то есть каждый символ кодируется конечный битовой последовательностью, называемый кодовым словом. Если все кодовые слова имеют одинаковую длину, код называется равномерным. Например, если длина кода 4, то можно закодировать 16 различных символов. Для файла длина 1000 символов длина кода будет 4000. Общую длину кода файла можно сократить, если использовать неравномерный код, то есть часто встречающиеся символы закодировать короткими битовыми последовательностями, а редко встречающиеся – более длинными. Каждому двоичному коду – равномерному и неравномерному соответствует двоичное дерево. Пример – задана таблица кодов (таблица 4.2) Соответствующие деревья изображены на рисунке 4.6. Таблица 4.2 Символ

a

b

c

d

e

f

Относительная 0,45 частота Равномерный 000 код Неравномерный 0 код

0,13

0,12

0,16

0,09

0,05

001

010

011

100

101

101

100

111

1101

1100

100

100

0

1

8

1

0

1 5

0

0

2 1

0

0

1

4

5

a 1

1

0

1

0

0

1

2

3

1

4

1

1

1

0

0

1

a

b

c

d

e

f

c

0 1 b

1 1

1

01

d

0

0

f

e

Рисунок 4.6 4.6.2 Префиксные коды

Коды, в которые из двух последовательностей битов, представляющих различные символы, ни одна не является префиксом другой, называются префиксными кодами. Известно, что для любого кода, допускающего однозначное восстановление информации, существует не худший его префиксный код. Поэтому, в принципе, можно ограничиться префиксными кодами. При кодировании каждый символ заменяется на свой код. Например, для рассматриваемого неравномерного кода строка abc запишется как 0101100. Для префиксного кода декодирование однозначно (что следует из его определения) и выполняется слева направо. Первый символ текста, закодированного префиксным кодом, определяется однозначно, так как кодирующая его последовательность не может быть началом кода какого-то символа. Найдя этот первый символ и отбросив кодирующую его последовательность битов, повторяем процесс для оставшихся битов, и так далее. В частности строка 001011101 в

случае неравномерного кода разделяется на части 0-0-101-1101 и декодируется как aabc. Оптимальному для данного файла коду всегда соответствует двоичное дерево, в котором любая вершина (кроме листьев) имеет двух непосредственных потомков. Отсюда следует, что дерево оптимального префиксного кода с n символами содержит n листьев и n-1 узлов, не являющихся листьями. Рассмотренный равномерный код, как легко видеть, этим свойством не обладает. Зная дерево Т, соответствующее префиксному коду, найдем количество битов, необходимое для кодирования файла. Пусть ƒ(S) обозначает число вхождений символа S в файл, gT(S) – глубину соответствующего листа в дереве (длину последовательности битов, кодирующей S). Тогда для кодирования файла потребуется B(T)=Σ s∈Sƒ(s)gT(s) битов. Число B(T) называется стоимостью дерева Т. Здесь S={S} - алфавит файла. 4.6.3 Коды Хаффмена

Хаффмен построил жадный алгоритм, который строит оптимальный префиксный код (код Хаффмена). Фактически алгоритм строит дерево Т, соответствующие оптимальному коду снизу вверх, начиная с множества |S| листьев и выполняя |S|-1 «слияние». Первому слиянию подлежат листья с наименьшей частотой, а очередным «слиянием» - поддеревья с наименьшей частотой. Для рассмотренного ранее примера последовательность построения дерева дана на рисунке 4.7 (|S|=6=n). Синтезируя полученный элементы, получим дерево Т, как на рисунке 4.6. Псевдокод алгоритма можно записать с применением процедур Allocate_Nod, Extract_Min, Insert, знакомых по работе с кучами /4/. Huffman (S) n←|S| 1 2 0 ←S 3 for i←1 to n-1 4 do z← Allocate_Nod () 5 x←left [z]← Extract_Min (0) 6 y←right [z]← Extract_Min (0) 7 f[z]←f[x]+f[y] Insert (0,7) 8 return Extract_Min (0) 9 End {Huffman}

0)

5

9

12

f

e

c

12

1)

13

13

b

14

16

0

1

5 14

2)

9

16

25

45

0

1

12

25

3)

30

45

0

1

14

45

4)

13

16

55

0

1

25

30

100

5) 0

1 45

55

Рисунок 4.7

16

45

d

a

45

Время работы алгоритма Huffman для алфавита из n символов есть величина 0(n log(n)). При этом предполагается, что для нахождения двух объектов, подлежащих слиянию, используется очередь с приоритетами, а сама очередь реализована в виде двоичной кучи. Присваивание в строке 2 проводится с помощью процедуры BuildHeap. Доказательство того, что жадный алгоритм Huffman дает оптимум, проводится в такой последовательности /4/: сначала доказываются леммы 4.1, 4.2, затем теорема 4.1 Лемма 4.1 Пусть в алфавите S, каждый символ s∈S имеет частоту f[s] и пусть x,y∈S-два символа с наименьшими частотами, тогда для S существует оптимальный префиксный код, в котором последовательности битов, кодирующие x и y, имеют одинаковую длину и различаются только в последнем бите. Эта лемма показывает, что построение оптимального дерева всегда можно начать со слияния двух символов с наименьшей частотой. Назовем стоимостью слияния сумму частоты сливаемых узлов. Стоимость дерева равна стоимостей всех слияний, необходимых для его построения. Тогда алгоритм Huffman на каждом шаге выбирает слияние, наименее увеличивающее стоимость. Установим теперь свойство оптимальности для подзадач. Пусть фиксирован алфавит S и два символа х, у этого алфавита, а S’-алфавит, который получится из S, если удалить х и у и ввести новый символ Z. Рассмотрим кодовые деревья для S, в которых х и у представлены листьями-братьями. Каждому такому дереву соответствует кодовое дерево для S’, которое получится, если убрать вершины х и у, а их общего родителя считать кодом символа Z. (При этом каждому кодовому дереву для C’ соответствует два кодовых дерева для C: в одном из них х − слева, а в другом − справа). Пусть f[s]-частота символа s∈S. Положим для символов S’ f[z]=f[x]+f[y]; для остальных символов частоты оставим теми же, что и в S. Теперь для обоих алфавитов определены стоимости кодовых деревьев. Лемма 4.2 Стоимости соответствующих друг другу деревьев Т и Т' отличаются на вершину f[x]+f[y] (в принятом описании). Эта лемма показывает, что выполнено свойство оптимальности для подзадач, то есть оптимальное дерево Т соответствует оптимальному дереву Т' для меньшей задачи. Теорема 4.1 Алгоритм Huffman стоит оптимальный префиксный код. Доказательство Лемма 4.1. показывает, что оптимальные кодовые деревья можно искать среди таких, у которых два наиболее редких символа (назовем их х и у) являются братьями. Им соответствуют деревья для алфавита S', в котором символы х, у слиты в один символ z. Считая частоту символа z, равной сумме частот х и у, можно, применив лемму 4.2 и увидев, что остается, найти оптимальное кодовое дерево для алфавита S' и затем добавить к вершине z двух потомков, помеченных символами х и у. Именно это и записано в алфавите Huffman. 4.6.4 Матроиды

Матроидом называется пара М=(S,I), удовлетворяющая условиям: S-конечное непустое множество; 1) I-непустое семейство подмножеств S, которые называются незави2) симыми, таких, что из B∈I и A∈B следует A∈I. Семейство I называется наследственным; Если A∈I, B∈I и A< B, то существует элемент x∈B\A такой, что 3) A∪{х}∈I. Это свойство семейства I называется свойством замены. Примеры Матричный матроид – Пусть Т – вещественная матрица, S1 множество её столбцов, и подмножество A⊂S называется независимым, если оно линейно независимо. Тогда получается матроид. Графовый матроид – Пусть G – неориентированный граф; SG – 2 множество ребер графа, IG состоит из всех ацикличных множеств ребер (то есть являющихся лесами). Тогда (SG, IG) – матроид. Графовые матроиды являются частным случаем матричных, если ребро графа рассматривать как формальную сумму его вершины с коэффициентами в поле вычетов по модулю 2. Если M=(S, I) – матроид, то элемент x∉A∈I называется независимым от х, если множество AU{x} независимо. Например, в графовом матроиде ребро е независимо от А тогда и только тогда, когда его добавление к А не создает цикла. Независимое подмножество в матроиде называется максимальным, если оно не содержится ни в каком большем независимом подмножестве. Имеет место теорема: Теорема 4.2 Все максимальные независимые подмножества данного матроида состоят из одинакового числа элементов. Доказательство Пусть А, В – независимые подмножества, и  А < В . тогда из свойства замены следует, что существует х∈А, для которого A∪{x} независимо, что противоречит максимальности. Пример – Пусть G – связный граф, MG – соответствующий матроид. Тогда всякое максимальное независимое подмножество MG должно быть деревом с  V -1 ребром (V – множество вершин), соединяющим все вершины G. Такое дерево называется основным деревом графа G. Матроид M=(S, I) называется взвешенным, если на множестве S задана весовая функция W со значениями в множестве положительных чисел – W: S→R+. Функция W распространяется по аддитивности на все подмножества множества S. Вес подмножества определяется как сумма весов его элементов: W(A)=∑x∈A W(x). Например, если MG – графовый матроид, W(e) – длина ребра e, то W(A) – сумма длин ребер подграфа A. Независимое подмножество максимального веса называется оптимальным подмножеством взвешенного матроида. 5 Алгоритмы Евклида в кольце полиномов

5.1 Кольцо полиномов от одной переменной

Пусть J-область целостности /8/, x - некоторый символ, тогда выражение вида

P(x)=anxn+an-1xn-1+…+a1x+a0,

(5.1)

где ai ∈ J, i=0.. n, называется полиномом от x над J. Полином можно задать набором его коэффициентов (an, … , a0). Два полинома называются равными, если они заданы одинаковыми наборами коэффициентов. Подвыражение вида aixi называется членом i-той степени. Коэффициент при xn называется старшим коэффициентом полинома, если он отличен от нуля, то n называется степенью полинома, если равен единице, то полином называется нормированным. На множестве полиномов над J введем операцию суммирования и мультисуммирования, по обычным правилам, то есть, если P(x), Q(x) заданы наборами (an , … , a0 ), (bn , … , b0 ) соответственно, то сумма P(x)+Q(x) зададим набором (al+bl, … , a0+b0 ), l=max(m,n), а произведение P(x) ⋅Q(x) набором (

∑a b ,

i + j =m+ n

i i

... ,

∑ a b ).

i + j =0

i i

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

нетривиальным коммуникативным кольцом. Предположим, что P(x)≠0, Q(x)≠0 (не есть полиномы вида 0xk + … + 0 при некотором k), а m, n –их соответствующие степени. Тогда am≠0, bn≠0 и в силу их принадлежности области целостности J их произведение ambn≠0. Поскольку ambn есть старший k коэффициент полинома P(x)Q(x), этот полином не есть 0. Из этого следует что множество полиномов от x над областью целостности J само является областью целостности. Обозначим её через J[x]. Эта область содержит, в частности J и x. Примечание. Если рассматривать полином как отображение x∈J в P(x)∈J[x], то в случае конечной области J не равные между собой полиномы могут иногда осуществлять одно и тоже отражение. Например, если J[x]=Z2[x], то различные полиномы P1(x)=x3-1 и P2(x)=x5-1 равны как функции: P1(0)=P2(0)=1, P1(1)=P2(1)=0. 5.2 Делимость

Говорят, что полином P1(x) делится на полином P2(x), или P2(x) есть делитель полинома P1(x), если существует полином Q(x) такой, что P1(x)=P2(x) ⋅ Q(x). Если P1(x) ≠0 как полином, то степень P2(x) не превосходит степени P1(x). m

n

i =0

i =0

Основная теорема Пусть P1(x)= ∑ ai x i , P2(x)= ∑ bi x i ≠0 – многочлены степени m, n соответственно над областью целостности J1 и пусть коэффициент bn обратим в J. Тогда существуют единственные полиномы Q(x), R(x)∈J[x], называемые частным и остатком соответственно, для которых

P1(x)=P2(x)Q(x)+R(x),

(5.2)

причём степень R(x) меньше степени P2(x). Доказательство Применим метод математической индукции по степени делимого P1(x). Если P1(x)=0 или его степень меньше P2(x), то (5.2) выполняется для Q(x)=0 и R(x)=P1(x). Если P1(x) ≠0, то ∧P1(x)= ∧P2(x)+k, k≥0 (∧ − знак степени многочлена). Образуем полином P′?(x)=P1(x)-(am /bn ) xk P2(x). Очевидно, ∧ P′?(x)< ∧P?(x). Теперь, если ∧P′?(x)=0 или ∧P′?(x)> ∧P2(x), то существование доказано; в противном случае по предположению метода имеет место разложение типа (6.2), то есть P′?(x)= P2(x)Q0(x)+R(x) для некоторых Q0(x) и R(x) с неравенством ∧R(x)< ∧P2(x). Из построения P′?(x) находим в этом случае P?(x)= P2(x) (Q0(x)+(am/bn )xk)+R(x), что доказывает существование Q(x) и R(x). Эти полиномы входят в кольцо J[x], при этом либо R(x)=0, либо ∧R(x)< ∧P2(x). Единственность доказываем от противного. Если, кроме Q(x), R(x), существуют Q1(x), R1(x), удовлетворяющие условию (6.2). Путём вычитания равенств типа (6.2) находим R(x)-R1(x)=P2(x)(Q1(x)-Q(x)), откуда P2(x)/(R(x)-R1(x)), что возможно лишь при R(x)=R1(x), и затем Q(x)=Q1(x). Теорема доказана. Примечание Если J-поле, то коэффициент bn обратим. 5.3 Полиномиальное деление с остатком

Алгоритм PDF m

n

Вход: P1(x)= ∑ ai x i , P2(x)= ∑ bi x i над полем, m≥n≥0, b≠0. i =0 m−n

i =0 n −1

i =0

i =0

Выход: Q(x)= ∑ qi x i , R(x)= ∑ ri x i , удовлетворяющие основной теореме. Шаги алгоритма: 1 Для k от (m-n) до 0 выполнять Qk:=an+k/bn для j от (n+k-1) до k выполнять ai:=ai-qkbj-k {Основной цикл} 2 Вернуть qi, i=0..(m-n) {Коэффициенты полинома Q(x), вычисленного на шаге 1} и ri=ci, i=0..(n-1){Коэффициенты полинома R(x), вычисленные по ci, i=0..(n-1) на шаге 1} {Выход} Пример - Пусть P(x)=7x5+4x3+2x+1, P2(x)=x3+2 –полиномы с целыми коэффициентами. Так как старший коэффициент P2(x) обратим, можно применить PDF. (Алгоритм работает над областью целостности J при условии, что bn обратим в J). Опуская запись степеней x, имеем: 704 0 21

10 02

700 14

70 4 0 4-14 21 0 0 00 414 21 4 0 08 14 2 -7 Таким образом, Q(x)=7x2+4, R(x)=-14x2+2x-7. 5.4 Наибольшие общие делители полиномов над полем

Определение. Евклидова область есть область целостности I с функцией степени S: I→N такой, что выполняются условия: 1 S ( p1 p2 ) ≥ S ( p1 ), p1 p2 ≠ 0; 2 Для любых p1 p2 ∈ I , p2 ≠ 0 , в I существуют элементы q, r, обладающие свойством евклидовости, то есть p1 = p2 q + r , S ( r ) < S ( p2 ) или r = 0 . Примеры 1 I = Z , S ( p ) = ( p ) - евклидова область, так как для p1 , p2 ∈ Z , p2 ≠ 0 , сущеествуют q, r такие, что p1 = p2 q + r , 0 ≤ r < p2 . Кроме того, если I – поле, то I [ x ] c S ( p( x )) =^ ( p( x )) - евклидова область, потому что для любых p1( x ), p2 ( x ) ∈ I [ x ], p2 ( x ) ≠ 0 в I(x) существуют единственные полиномы q(x), r(x) такие, что p1( x ) = p2 ( x )q( x ) + r( x ), ^ r( x ) <^ p2 ( x ) . 2 I=Q (поле рациональных чисел), S(p) = (p) не является евклидовой областью, потому что S(5⋅(1/5)) = S(1) < S(5), и первое условие определения евклидовой области не выполняется. Кольцо Z[x], S(p(x)) = ^p(x) также не является евклидовой областью, так как если, например, разделить 7 x 5 + 4 x 3 + 2 x + 1 на 5 x 3 + 2 , то частное не принадлежит кольцу Z[x]. Определение Говорят, полином p1(x) делится на полином p2(x) если ∃ q(x): p1(x)=p2(x)q(x). Запись: p2(x)|p1(x). Если p1(x)?0, то ∧ p2(x) ≤ ∧ p1(x). Определение Пусть p1( x ), p2 ( x ) ∈ I [ x ], p2 ( x ) ≠ 0 , I – область целостности. Тогда наибольшим общим делителем полиномов р1(х), р2(х) называется полином ph(x) ∈ I[x], удовлетворяющий условиям: а) ph(x) / р1(х) и ph(x) / р2(х); б) если q(x) / р1(х) и q(x) / р2(х), то ^ q(x) <^ ph(x) и q(x) < ph(x). Обозначение : НОД[р1(х), р2(х)] = ph(x).

НОД двух полиномов в I[x], где I – область целостности и р2(х) ≠ 0, можно найти повторным применением алгоритма деления PDF, рассмотренного ранее. Этот процесс называется алгоритмом Евклида для полиномов. При этом имеет место следующая теорема. Теорема Пусть p1( x ), p2 ( x ) ∈ I [ x ], p2 ( x ) ≠ 0 , I – область целостности. Тогда алгоритм Евклида дает НОД [р1(х), р2(х)] – это последний отличный от нуля остаток ph(x). Последовательность остатков полиномов, полученная при выполнении алгоритма Евклида, называется последовательностью полиномиальных остатков. Два полинома р(х) и q(x)называются ассоциированными, если каждый из них является скалярным кратным другого. Любой полином ассоциирован ровно с одним нормированным полиномом. Поэтому, когда ph(x) нормирован, можно говорить о единственном наибольшем общем делителе. Примечание В Z НОД двух целых чисел единствен среди положительных; если брать по абсолютной величине, то, например, числа 6 и 9 имеют НОД: 3 и –3. Два полинома в I[x] называются взаимно простыми, если любой их НОД – обратимая константа из I. В этом случае говорится, что единичный элемент кольца I – их наибольший общий делитель. 5.5 Алгоритм Евклида для полиномов над полем

Теорема Пусть, p1( x ), p2 ( x ) ≠ 0 ∈ I [ x ], I – поле. Тогда существуют поu(x), v(x) ∈ I[x] такие, что линомы

р1(х) v(x) + р2(х) u(x)= ph(x)

(5.3)

где ph(x)= НОД [р1(х), р2(х)]. Следствие Для того, чтобы два полинома р1(х), р2(х) ∈ I[x], I – поле, были взаимно простыми, необходимо и достаточно существования полиномов u(x), v(x) ∈ I[x], таких, что р1(х) v(x) + р2(х) u(x)= 1. Примечание Если u(x), v(x) соответствуют следствию,то полиномы u1( x ) = u( x ) − t( x ) p1( x ), v1( x ) = v( x ) + t( x ), p2 ( x ), t ∈ I [ x ] тоже соответствуют следствию. Полиномы u(x), v(x) не единственны; они могут иметь произвольно высокую степень, но ограниченную снизу. Теорема В условиях предыдущей теоремы существуют единственные полиномы f(x), q(x), степени которых ниже степеней полиномов p1(x), p2(x) сооph(x) = НОД [p1(x), тветственно, для которых p1(x) q(x)+ p2(x) f(x) = ph(x), p2(x)]. Конструктивное доказательство этой теоремы можно усмотреть из приведенного ниже расширенного алгоритма Евклида для полиномов.

5.6 Расширенный алгоритм для полиномов над полем

Алгоритм Ext_Euclid_P Вход: р1(х), р2(х) ∈ I[x], p2 ( x ) ≠ 0, m =^ p1( x ) ≥^ p2 ( x ) = n; I - поле . Выход: ph ( x ), f ( x ), q( x ) ∈ I ( x ) :^ f ( x ) <^ p1( x )−^ p2 ( x ), ^ q( x ) <^ p2 ( x )−^ ph ( x ), ph ( x ) = НОД [ p1( x ), p2 ( x )] = p1( x )q( x ) + p2 ( x ) f ( x ). Шаги алгоритма {Инициализация} [p0(x), p1(x)]:= [p1(x), p2(x)]; [q0(x), q1(x)]:=(1,0); [f0(x),fq1(x)]:=(0,1) {Основной цикл} Пока p1( x ) ≠ 0 выполнять q(x):=POF [p0(x), p1(x)] [p0(x), p1(x)]:= [p1(x), p0(x) - p1(x)q(x)] [q0(x), q1(x)]:=[q1(x), q0(x) - q1(x)q(x)] [f0(x), f1(x)]:= [f1(x), f0(x) - f1(x)q(x)] 3 {Выход} Вернуть [ ph ( x ), q( x ), f ( x )] := [ p0 ( x ) q0 ( x ), f 0 ( x )]

Пример – Пусть p1( x ) = 7 x 5 + 4 x 3 + 2 x + 1, p2 ( x ) = 5 x 3 + 2 полиномы над полем Z11. Тогда расширенный алгоритм Евклида дает таблицу 5.2 Таблица 5.1 Функция

Итерация 1 8x2+3 5x3+2

2 10x+4 6x2+2x+6

3 8x+10 9x

4 7x 6

p1(x) q0(x)

0 7x5+4x3+2x +1 5x3+2 1

6x2+2x+6 0

9x 1

6 x+7

0 3x2+8

q1(x)

0

1

x+7

3x2+8

-

f0(x)

0

1

3x2+8

f1(x)

1

3x2+8

q(x) p0(x)

3x3+10x2+8x+ 9x4+4x2+3x+1 1 0 3 2 4 2 3x +10x +8x 9x +4x +3x+1 +1 0

Проверка: (7x5+4x3+2x+1)(3x2+8)+(5x3+2)(9x4+4x2+3x+10)=6. Ответ, который дает алгоритм, есть 6. Как ранее отмечалось, лучше в качестве ответа взять нормированный полином (разделить на старший коэффициент) и его назвать наибольшим общим делителем данных двух полиномов Ответ: НОД [p1(x), p2(x)]=1.

Рассмотренный алгоритм можно применить к вычислению обратного полинома для данного полинома p(x)≠0 в Zp[x]m(x), где ∧p(x)< ∧m(x), p-простое число, m(x)-непрерывный полином в Zp[x]. Действительно, применяем алгоритм Ext_Euclid_P к m(x) и p(x); получаем полиномы f(x) и g(x), для которых m(x)f(x)+p(x)g(x)=1. Затем, вычисляем значение в точке α=[x]m(x),m(α)=0; получается p(α)g(α)=1 в Zp[x]m(x), то есть p(α) обратим Zp[x]m(x).

6 Языки и грамматики

Для реализации алгоритмов на ЭВМ требуется составить программу на входном языке этой машины. Обычно под входным языком понимают язык программирования высокого уровня. Такие языки предоставляют пользователю достаточно развитые изобразительные средства и дружественный интерфейс. Распространёнными языками высокого уровня являются Фортран, Паскаль, Си, Aда, и другие. Выполнение программ, записанных на языке программирования, производится с помощью языковых процессоров – программ на машинном языке, входящем в состав по ЭВМ. Основными типами языковых процессоров являются трансляторы и интерпретаторы. Транслятор имеет входом программу на входном языке, а выходом – эквивалентную программу на машинном (или промежуточном) языке. Интерпретатор – программа, которая по мере распознавания конструкций входного языка реализует их, то есть выходом интерпретатора являются результаты действий предусмотренных исходной программой. В этом смысле интерпретатором выходной программы транслятор служит сама ЭВМ. (Для промежуточного языка снова используется либо транслятор, либо интерпретатор). Транслятор для языка высокого уровня называется компилятором. В основе методики проектирования компиляторов лежит синтаксически управляемый метод обработки языков. При этом исходная программа рассматривается как композиция разделов описания входного языка: лексики, синтактики, семантики, прагматики /9/. В соответствии с общими принципами семантики (науки о знаковых системах) базой языка программирования является алфавит – множество символов, называемых буквами. Лексику языка составляет множество допустимых элементарных цепочек символов, называемых словами, вместе с описанием способов их представления. Слова объединяются в более сложные конструкции – предложения. В языках программирования предложение есть оператор. Правила построения предложений составляют синтактику языка. Семантика описывает значение слов, смысл предложений и связи между ними. Прагматика определяет соотношение между смыслом языка и разрешающими возможностями языкового процессора. 6. 1 Нормальные формы Бэкуса

Для описания языка программирования используется метаязык. Одним из метасинтаксических языков для языков программирования являются так называемые нормальные формы Бэкуса (НФБ). В форме Бэкуса описываются объекты: -символы языка программирования; -имена конструкций языка (металингвистические переменные). Металингвистическая форма состоит из двух частей (левой и правой), соединённых символом : : = (металингвистическая связка); означающем «есть по определению». В левой части находится имя конструкции, в правой – варианты (один или несколько), реализующие конструкции. Если вариантов несколь-

ко, они разделяются символом |, означающим «или». Имена конструкции заключаются в угловые скобки <, >. В расширенном варианте НФБ используются символы: [, ] – для необязательных элементов и т. д. Существенной чертой металингвистических форм является наличие в них рекурсий – явных и неявных. Пример – НФБ – описание десятичного числа: <десятичное число>: : = [±]<цифра>… <цифра>: : = 0/1/2/3/4/5/6/7/8/9. Многоточие в примере означает повторение элемента. 6.2 Формальные языки и грамматики

Формальным языком L над алфавитом А называется множество цепочек символов этого алфавита. Если а1, а2, … ∈ А, то а1 … аn –цепочка длины n. Обозначения цепочек α, β, ... . Цепочка β называется подцепочкой α, если α=γβδ, где γ, β тоже цепочки. Цепочки можно рассматривать как элементы множества * 0 1 0 1 n ∞ n А =А ∪А ∪…= ∪ n =0 A , где А ={λ}, λ - пустая цепочка, А =А, … , А =A× … ×A (n раз). Множество непустых цепочек определяющихся как A+=A*\A0= ∪ ∞n =1 A n . Длина цепочки α обозначатся через |α|, при этом |λ|=0. На множестве цепочек определяется операция конкатенации. Обозначение: ⊕. Для двух цепочек α, β конкатенация означает приписывание второй цепочки к первой. Например, если α=ко, β=нец, то α⊕β=αβ=конец. При этом λα=αλ=α. Операция ⊕ ассоциативна, но не коммутативна. Для записи повторяющихся символов можно использовать верхний индекс. Например, xx=x2, xyxyx=(xy)2y=x(xy)2. Кроме того, можно писать x0 вместо λ, x1 вместо x. Формальной грамматикой называется формальное определение синтактики языка. Существует два основных способа задания языка: с помощью порождающей процедуры и с помощью распознающей процедуры. 6.3 Порождающие грамматики

Определение Формальной порождающей грамматикой называется четвёрки П=, глее Т- конечное непустое множество символов, называемых нетерминалами; S – начальный символ, называемый главным нетерминалом; P – конечное множество правил грамматики. Правила называются двуместными отношениями вида ϕ→ψ, где ϕ,ψ - цепочки над алфавитом V=T∪N, причём в левой части должен содержаться хотя бы один нетерминал ; → символ отношения – интерпретируется как «заменить ϕ на ψ».Здесь терминалы будем обозначать через a,b,c, … , нетерминалы – A, B, C, … .Цепочка β называется непосредственно выводимой из цепочки α в грамматике G, если α=ξ1ϕ ξ2, βα=ξ1ψ ξ2 и существует правило ϕ→ψ. Запись α⇒β. Цепочка β называется выводимой из цепочки α в грамматике G, если либо α=β, либо существует последовательность цепочек α=ω0, ω1, … ωn=β та-

кая, что ωi+1 непосредственно выводима из ωI, i=0,1,…,n-1, ωi∈(N∪T)*. Запись α⇒β. Определение Множество всех цепочек терминальных символов, выводимых из главного нетерминала, называется языком, порождённым этой грамматикой. Обозначение: L(G)={α| S⇒ α, α∈T*}. Пример - Грамматики G=: N={I}, T={a, b, c, ∨ , ∧ , ¬ , (,)}, S={I}, P={I→(I ∨ I), (I ∧ I), I→ ¬ I, I→a, I→b, I→c} описывает язык булевых формул с переменными a, b, c и логическими операциями ∨ , ∧ , ¬ . В частности, имеет место вывод: I⇒(I ∨ I) ⇒((I ∧ I) ∨ I) ⇒((a ∧ b) ∨ c). Язык называется распознаваемым, если существует алгоритм, который для произвольной цепочки за конечное число шагов даёт ответ на вопрос, принадлежит ли цепочка языку. 6.4 Классификация языков по Хомскому

Н. Хомский (американский лингвист) предложил классифицировать формальные языки по типу правил порождающих их грамматик. Класс 0. Правила вывода имеют вид ϕ→ψ. Ограничений на строки ϕ, ψ не вводится. Языки этого класса близки моделям естественных языков. Класс 1 Правила вывода имеют вид ϕ→ψ, где ϕ=ξ1αξ2, ψ=ξ1βξ2, α∈Ν, + β∈V , ξ1, ξ2 ∈V*. Грамматика называется контекстной грамматикой. Языки, порождённые грамматиками этого типа называются контекстно зависимыми. Относятся к числу легко распознаваемых. Пример – Грамматика G= : N={I, A, B, C, D}, T={a, b, c}, S={I}, P={I→ABA, B→ABCA, B→b, bC→bb, AC→DC, DC→DA, DA→CA, A→a} имеет класс 1. Она порождает язык anbnan. Класс 2 Все порождающие правила имеют вид: A→β, где A – нетерминальный символ, β∈V+. Грамматики этого класса называются контекстно-свободными. Они играют главную роль при формальном изучении синтактики языков программирования. Класс 3 Порождающее правила имеют вид: A→bB или A→b, где A, B∈Ν, b∈T. Языки этого класса называются регулярными или автоматными, а порождающие их грамматики – автоматными грамматиками. Используются на этапе лексического анализа. Иерархия языков задаётся включением L0⊃L1⊃L2⊃L3. Из четырёх классов грамматик контекстно-свободные грамматики наиболее приложимы к языкам программирования. С их помощью можно определить значительную часть синтаксической структуры языка программирования. Интересно отметить, что между НФБ и КС –грамматиками имеется тесная связь; различия касаются лишь обозначений. В частности связке «: : =» из НФБ соответствует отношение «→» в КС – грамматике, металингвистическим переменным из НФБ соответствуют нетерминалы в КС – грамматике и т.д.

6.5 Лексический анализ

Лексический анализ (ЛА)- этап предварительной обработки исходной программы на лексемы и составные таблицы лексем. Сама же программа представляется последовательностью пар – дескрипторов: <дескриптор>::=(<тип лексемы>, <указатель>), где тип лексемы – код класса лексем, указатель – ссылка на область памяти, где хранится лексема или номер в таблице, куда помещено значение лексемы. Наиболее распространёнными классами лексем являются: идентификаторы, служебные слова, разделители, константы. Содержимое таблиц дополняется на этапе семантического анализа исходной программы генерацией объектного кода программы. Программа, выполняющая лексический анализ, называется лексическим анализатором. Последовательность работ лексического анализатора следующая. Сначала, при просмотре слева направо, выделяется последовательность символов, которая предположительно является лексемой. Затем (или параллельно) проводится идентификация лексемы и проверка правильности её записи. Это делается, например, путём сравнения с эталонным значением. В случае неуспешной идентификации формируются сообщения об ошибках. Могут выполняться и другие виды лексического контроля: парность символов и т. п. При успешной идентификации значение лексемы данного класса (если её там нет). Выходной поток лексического анализатора поступает на вход синтаксического анализатора. При построении лексических анализаторов используются формальный математический аппарат – теория регулярных языков и грамматик. Пример – Вход лексического анализатора Program Glob; Var a, b: integer; Begin a:=10; b:=12; a:=1+b; writeln(a) End. Выход лексического анализатора N

Идентификатор

N

Значение константы 1 10 2 12

1 Glob 2 a 3 b Последовательность дескрипторов: (10, 1)(30, 1)(20, 1)(10, 6)(30, 2)(20,2)…(30, 3)(20, 9). Внимание! Здесь используются таблицы:

Таблица служебных слов N

Служебное

Таблица разделителей N

слово 1 2 3 4 5 6 …

Значение константы

Program Begin End For Integer Var

1 2 3 4 … 9 …

; , + …………………… . ……………………

В качестве кодов типов лексем используются числа: 10(служебное слово), 20(разделитель), 30(идентификатор), 40(константа). 6.6 Регулярные языки. Конечные автоматы

Порождающая грамматика G= называется регулярной, если её правила имеют вид: A→aB или C→b, где A, B, C∈N, ab∈T. Язык L(G), порождаемый регулярной грамматикой, называется регулярным языком. Пример – G=: N={I, K}, T={δ, u}, S={I}, P={I δ, δK, K δK, K uK, K v, K u}, где δ, u – терминальные I символы для обозначения букв и цифр соответственно, является регулярной грамматикой, порождающей идентификаторы. Идентификатором называется последовательность букв и цифр, начинающихся с буквы. В частности, идентиbK δδK δδuK δδ фикатор < δδuδu > порождается цепочкой: I ubK δδuδu. Поскольку основной задачей ЛА является распознавание лексических единиц, рассмотрим одну из математических моделей распознавателя регулярного языка – конечный автомат (КА). Конечным автоматом называется пятёрка A=< V, Q, δ, q0F >, где V={a1, … ,am} – входной алфавит, Q={q0, q1, … , qn-1} – алфавит состояний, δ: Q×V→Q – функция переходов, q0 – начальное состояние КА, F⊂Q – множество конечных состояний. Графическое представление отображения δ называется диаграммой состояний конечного автомата а. Это – ориентированный граф, вершины которого поставлены в соответствие символы алфавита состояний, а другим символы входного алфавита. Пример – Конечный автомат для грамматики предыдущего примера имеет вид: A=< V, Q, δ, q0F >, гдеV=T={δ, u}, Q=N∪{Z}={I, K, Z}, q0={S}={I}, f={Z}. Его можно представить диаграммой состояний (рисунок 6.1).

δ

δ

ц

δ

к Рисунок 6.1 В принципе, возможен обратный переход от конечного алфавита к регулярной грамматике. 6.7 Синтаксический анализ. Контекстно-свободные грамматики

Основной задачей синтаксического анализа – выявление синтаксической структуры исходной программы. Одним из способов решения той задачи является моделирование построения дерева вывода в грамматике, описывающей входной язык программирования. Такими грамматиками являются контекстносвободные грамматики. Различают левосторонние и правосторонние выводы. Вывод в КС – грамматике называется лево- | правосторонним, если правила вывода применяются к самому левому | правому вхождению нетерминального символа каждой цепочки вывода. Пример – КС-грамматики G=< N, T, P, S >, N={E, R, F}, T={I, +, *, ), (}, E+R, E R, R R*F, R F F (E), F i} порождает S={E}, P={E арифметические выражение, причём идентификатору соответствует терминальный символ i, а арифметическим операциям – символы + и * ; скобки (и) имеют обычный смысл. В частности, для терминальной цепочки i+i*I левостоE+R R+R F+R I+ ронний вывод представляется цепочкой E * * R I+R F I+F F I+I*F I + I * I, а правосторонний – цепочкой E+R E+R*F E+R*I E+F*I E+I*I R+I*I F E I + I * i. +I*I Наглядным представлением структуры программы является дерево синтаксического разбора. Дерево разбора в КС – грамматике G=< N, T, P, S > есть упорядоченное дерево, каждая вершина которого взвешена символом X∈T∪N. При этом, если внутренняя вершина помечена символом А, а её прямые потомки символами X1, … ,Xk, то A→ X1… Xk – правило грамматики G.

На рисунке 6.2 показано дерево синтаксической разборки цепочки i+i*I для грамматики из предыдущего примера. Левостороннему выводу соответствует обход сверху вниз, слева направо. Для правостороннего вывода ориентацию пути обхода дерева надо менять на обратную. E R

+

R

R

F

F

i

i

R *

F

i

Рисунок 6.2 6.8 Магазинные автоматы

Одной из основных задач при разборке блока синтаксического анализа транслятора является построение алгоритма распознавания языка. Этот алгоритм может быть представлен распознающим устройством. Для КС-языков используется устройства, с магазинной памятью (МП-автоматы). Недетерминированным МП-автоматом называется семёрка M=< A, Q, Г, δ,q0, Z0, F >, где А-конечный входной алфавит; Q-конечный алфавит состояний; Г- конечное множество магазинных символов; q0∈Q – начальное состояние автомата; Z0∈Г –начальный символ в магазинной памяти; F⊂Q – множество конечных состояний; δ -отображение Q×A×Г в Q×Г*. Магазинная память определяется правилом «первый вошел – последний вышел». При записи нового символа содержимое магазинной памяти сдвигается в глубь на одно место, а верхнее отдается новому символу. Чтению доступен только введенный последним символ. Он после чтения либо остается в магазинной памяти, либо извлекается. Такт работы магазинной памяти-автомата предполагает извлечение не более одного символа. Обработку входной цепочки магазинная память-автомат начинает в некотором выделенном состоянии при определенном содержимом магазинной памяти. В каждый такт работы автомат выполняет операции трех типов:

над магазином (ввести/вывести один символ или не менять содержимое магазина); над состоянием (перейти в новое или остаться в прежнем); над входом (перейти к следующему входному символу или оставить текущий до следующего шага) Множество правил перехода называется управляющем устройством. Магазинная память-автомат называется магазинной памятью-распознавателем, если он имеет два выхода: «допустить», «отвергнуть». Пример – Автомат А={0,1,├}, Q={q1,q2}, Г={z, #}, где ├ - символ конца цепочки на входной ленте, # - маркер дна магазина, q1 – начальное состояние магазина, # - начальное содержимое магазина, имеет управляющую таблицу 6.3. Таблица 6.3 Магазин z # Магазин

Вход q10 q1 ввести сдвиг q1 ввести сдвиг Вход q20

отвергнуть

отвергнуть

отвергнуть q2

отвергнуть

q21 q2 ввести сдвиг

отвергнуть

отвергнуть

отвергнуть

допустить

z #

q1

q11 q2 ввести сдвиг

Этот автомат распознает слова языка L={0n1n | n≥1}. Работа магазинной памяти-автомата при распознавании конкретной цепочки может быть представлена последовательностью конфигураций, определяемых содержимым магазина, состоянием автомата, входом. В частности, при анализе входного слова 000 111 эта последовательность представлена таблицей 6.4. Таблица 6.4 Магазин # #z # zz # zzz # zz #z # Выход

Состояние q1 q1 q1 q1 q2 q2 q2 Допустить

Вход 000 111├ 00 111 ├ 0 111├ 111├ 11├ 1├ ├

Существуют много других типов автоматов, применяемых в А. соответствующие грамматики образуют иерархию. Наиболее известны из них грамматики предшествования /6/. 6.9 Семантический анализ Синтез объектной программы

Рассматриваемый этап обработки входной программы представляет собой преобразование синтаксического дерева программы на входном языке в код эквивалентной формы объектной программы. При этом синтаксический анализ может чередоваться с семантическим: синтаксический анализатор формирует синтаксическую единицу (выражение, оператор, вызов и т.п.) из последовательности лексем а затем распознанная структура обрабатывается. Результатом работы семантического анализатора является объектная программа (или промежуточная программа). Основными функциями семантического анализатора являются: выполнение проверки контекстных (семантических) условий; распределение памяти; анализ объектной (или промежуточной) программы. Кроме того, в ведении семантического анализатора таблица идентификаторов. К общим примерам контекстных условий относятся: условие единственности описания идентификатора, условие соответствия между определяющими и использующими вхождениями идентификаторов; условия соответствия типов значений; количественные ограничения и другие. Что касается таблиц идентификаторов, то начальные поля таблиц создаются лексическим анализатором. Далее, по мере распознавания описаний идентификаторов в процессе синтаксического анализа формируются новые поля таблицы. Для каждого типа идентификатора хранится соответствующая информация. В частности, для имен переменных указывается тип, точность, вид, адрес и т.д. Новое поле добавляется один раз, но поиск ведется при каждом упоминании в программе этого идентификатора. В конце трансляции таблица идентификаторов прекращает существование, если не используется во время выполнения программы (например, при отладке). 6.10 Распределение памяти

После выявления структуры программы реализуется фаза распределения памяти. Транслятор выделяет место в памяти машины для значений переменных программы и указывает адреса переменных в таблице идентификаторов. Для простых типов данных (числа, литеры и т.п.) применимо, как правило, прямое аппаратное представление, для сложных (массивы, записи и т.д.) создаются вспомогательные промежуточные структуры (информационные векторы). Физическая память для команд объектной программы выделяется во время загрузки программы загрузчиком, а для данных всю область памяти разделяют на статическую (постоянное число ячеек на все время работы программы), автоматическую (переменную, но предопределенную), динамическую. Статическая часть отводится, например, глобальным переменным, автоматическая – локаль-

ным, динамическая – ее логика изменения транслятору не известна. Кроме областей для хранения значений локальных и промежуточных переменных, транслятор должен выделить ячейки для сохранения состояния вычислительного процесса процедур, для приема значений фактических параметров, решать многие другие вопросы. 6.11 Операторные грамматики

Контекстно свободные грамматики включают в себя так называемые операторные грамматики /10/. Правила этих грамматик таковы, что никакие два нетерминала не являются смежными в правой части. В этом случае лежащий между ними терминал можно представить как оператор. Рассмотрим частный случай операторных грамматик – грамматику операторного предшествования (ГОП). Определим правила: a≈b, если A→αaβbγ∈P; здесь α,γ∈V* и β∈N∪{λ}; a≺ b, если A→ αaBβ∈P; здесь B ⇒+γbδ, γ∈N∪{Λ} и α,β,δ∈V*; a>b, если A→ αBbβ∈P; здесь B ⇒+γaδ, δ∈N∪{Λ} и α,β,γ ∈V*;

├ a, если S ⇒+αaβ, α∈N∪{Λ}, β∈V*; a≻ ┤, если S ⇒+αaβ, β∈N∪{Λ}, α∈V*. Здесь символы ≺ , ≈ и ≻ обозначают отношения предшествования: «имеет меньшее старшинство», «имеет равное старшинство» и «имеет большее старшинство» соответственно. Сами отношения определяются на множестве T∪{├, ┤}, где и - новые символы, ограничивающие предложения. Пример - E→E+T T, T→T*P P, P→(E) x. Для этой грамматики отношения предшествования соответствуют таблице Таблица ├ + * ( ) x

+ ≺ ≻ ≻ ≺ ≻ ≻

* ≺ ≺ ≻ ≺ ≻ ≻

( ≺ ≺ ≺ ≺

) ≻ ≻ ≈ ≻ ≻

x ≺ ≺ ≺ ≺

┤ ≻ ≻ ≻ ≻

Построим вывод предложения ├ x*(x+x) ┤ в этой ГОП. Заменяя x целыми числами, 2, 3, 4, получаем ├2*(3+4) ┤. Записывая отношения предшествования под этим выражением, замечаем , как определяется порядок вычислений. ├ 2 *; ≺ ≻ ;

a) выберем число 2 и сохраним его в стеке: ├ * ( 3 + , ≺ ≺ ≺ ≻ ; б) аналогично удалим 3 из выражения и поместим в стек: ├ * ( + 4 ), ≺ ≺ ≺ ≺ ≻ ; в) с 4 поступим подобным образом: ├ * ( + ), ≺ ≺ ≺ ≻ ; г) выполним сложение двух верхних элементов в стеке и результат оставим там же; удалим символ +: ├ * ( ), ≺ ≺ ≈; д) отбросим скобки: ├ * ┤, ≺ ≻ ; е) произведём умножение двух верхних элементов стека, оставляя результат в стеке; удалим символ *: ├ ┤; ж) останов; ответ находится в стеке. 6.12 Представление промежуточной программы

Промежуточная программа представляет собой линейную запись синтаксического дерева программы, легко транслируемую в магнитный код. основными терминальными символами промежуточной программы являются операторы и операнды. Операторы представляются внутри компилятора числовыми кодами, а операнды – указателями на соответствующие таблицы и идентификаторов. Одной из форм представления промежуточной программы является постфиксная польская запись, которая (в отличие от инфиксной) указывает порядок выполнения операций. Например арифметическое выражение а+b*c в постфиксной польской записи будет выглядеть как аbc*+d+. Расшифровка в постфиксной польской записи выглядит очень просто: выражение просматривается слева направо, и его элементы помещаются в стек. Если очередной элемент – знак операции, то (в случае двухместной операции) два верхних элемента извлекаются из стека, над ними выполняется операция и результат помещается в стек; операция удаляется из входной строки, просмотр продолжается. В постфиксной польской записи можно представить также все операторы исходной программы. Например, условный оператор if <выражение> then <оператор1> else <оператор2> будет иметь вид: <выражение> <метка1> BZ <оператор1> <метка2> BR <метка1> <оператор2> <метка2>. Здесь BZ – бинарная операция, которая осуществляет переход на <метка1>, если значение <выражение>

- ложь; BR – унарная операция, осуществляющая безусловный переход на <метка2>.

Упражнения

1 Доказать, что множество всех рациональных чисел, меньших e (основа ние натуральных алгоритмов), разрешимо. 2 Доказать, что непустое множество натуральных чисел разрешимо тогда и только тогда, когда оно есть множество значений всюду определённой неубывающей вычислимой функции с натуральными аргументами и значениями. 3 Множество тех n, для которых в числе π есть не менее n девяток подряд, разрешимо. Доказать. 4 Доказать перечислимость пересечения и объединения перечислимых множеств. 5 Доказать перечислимость декартова произведения A×B⊂N×N, если A⊂N и B⊂N перечислимы. 6 Доказать перечислимость множества диофантовых уравнений, то есть уравнений вида P(x1,…,xn)=0, где P – многочлен с целыми коэффициентами. 7 Выяснить перечислимость множества показателей n, для которых существует решение уравнения xn+yn=zn в целых числах. 8 Доказать, что действительное число α вычислимо тогда и только тогда, когда множество рациональных чисел, меньших α, разрешимо. 9 Пусть U – перечислимое множество пар натуральных чисел, универсальное для класса всех перечислимых множеств натуральных чисел. Доказать, что его «диагональное сечение» K={x|(x,x)∈U} является перечислимым неразрешимым множеством. 10 Некоторое множество S натуральных чисел разрешимо. Разложим все числа из S на простые множители и составим множество D всех простых чисел, встречающихся в этих разложениях. Можно ли утверждать, что множество D разрешимо? 11 Построить главную универсальную функцию. 12 Пусть U – главная универсальная функция. Докажите, что для любой вычислимой функции V(m,n,x) существует такая всюду определённая вычислимая функция S(m,n), что V(m,n,x)=U(s(m,n),x) при всех m,n и x. 13 Пусть h – всюду определённая вычислимая функция, у которой мы хотим найти неподвижную точку. Вычисляющий её алгоритм , допустим, имеет вид: function Compute_h(x:String):String; begin … end; Используя процедуру GetProgramText(var s:String), помещающую текст исходной программы в строку s, записать программу, являющуюся неподвижной точкой функции h. Указание: Использовать также процедуру ExecuteProgram(s:String), которая передаёт управление программе, текст которой находится в строке s.

14 Приведите пример вычислимой универсальной функции, не являющейся главной. 15 Пусть X, Y – два различных множества. Рассмотрим программы, имеющие доступ к двум оракулам для X и для Y и функции, которые можно вычислить с помощью таких программ. Укажите такое множество Z, что X – Y – вычислимость совпадает с Z – вычислимостью. 16 Описать конструкцию функции Аккермана. 17 Составить программу для решения на машине Тьюринга задачу удвоения числа. 18 Составить схему примитивной рекурсии для двуместных функций [x/y] – неполное частное, rest(x,y) – остаток от деления x на y. 19 Составить нормальный алгоритм для функции λ(x)=x+1. 20 Доказать, что алгоритм распознавания несамоприменимости нормальных алгоритмов невозможен. 21Как работает сортировка вставками на входе A=(31,41, 59, 26, 41, 58)? 22 Измените процедуру сортировки вставками так, чтобы она сортировала числа в невозрастающем порядке. 23 Рассматривается задача поиска. Вход: Последовательность n чисел A=(a1,…,an) и число v. Выход: Индекс i, для которого v=A[i] или NIIL. Напишите алгоритм (линейного поиска), который последовательно просматривает A в поисках v. 24 Сколько сравнений потребуется в среднем алгоритму линейного поиска, если искомым элементом может быть любой элемент массива с одинаковой вероятностью? Каково время работы в худшем случае и в среднем? Как записать эти времена с помощью θ - обозначений? 25Дана последовательность чисел x1,…,xn. Покажите, что за время θ(nlog(n)) можно определить, есть ли в этой последовательности два одинаковых числа. 26 Как записать выражение n3/1000-100n2-100n+3 с помощью θ - обозначений? 27 Даны коэффициенты a0,…,a n-1 многочлена; требуется найти его значение в заданной точке x. Естественный алгоритм требует времени θ(n2). Как выполнить вычисления за время θ(n), не используя дополнительного массива? Используйте «схему Горнера»:

n −1

∑ i =0

a i x i=(…(an-1x+an-2)x+…+a1)x+a0

28 Покажите работу сортировки слиянием для массива A=(3, 41, 52, 26, 38, 57, 9, 49). 2, если n = 2, 29 Покажите по индукции, что если T(n)= 2T (n / 2), если n = 2 n , то T(n)=nlog(n) (при всех n, являющихся степенями двойки).

{

30 Сортировку вставками можно оформить как рекурсивную процедуру: желая отсортировать A[1..n], мы (рекурсивно) сортируем A[1..(n-1)], а затем

ставим A[n] на правильное место в отсортированном массиве A[1..(n-1)]. Напишите рекуррентное соотношение для времени работы такой процедуры. 31 Пусть сортировки вставками и слиянием исполняются на одной и той же машине и требуют 8n2 и 64n log(n) операций соответственно. Для каких значений n сортировка вставками является более эффективной? 32 При каком наименьшем значении n алгоритм, требующий 100n2 операций, эффективнее алгоритма, требующего 2n операций? 33 Пусть f(n) и g(n) – неотрицательны для достаточно больших n. Покажите, что max(f(n), g(n))=Θ(f((n)+g(n)). 34 Покажите, что (n+f)b= Θ(nb) для любого вещественного a и для любого b>0. 35 Можно ли утверждать, что a) 2n+1=O(2n); b) 22n =O(2n). 36 Приведите пример функций f(n) и g(n), для которых f(n)=О(g(n)),но f(n) ≠ о(g(n)) и f(n) ≠ Θ (g(n)). 37 Покажите, что свойства f(n)=o(g(n) и f(n)=ω g(n не могут быть выполнены одновременно. 38 Докажите, что log(n!)= Θ(nlog(n)) и что n!=o(nn). 39 Будет ли функция log(n) ! полиномиально ограниченной? Будет ли функция log(log(n)) полиномиально ограниченной? 40 Покажите, что из T(n)=T(n/2)+1 cледует T(n)=O(log(n)), а из T(n)=2 T(n/2+n следует T(n)=Ω(nlog(n)), и тем самым T(n)= Θ(nlog(n)). 41 Используя основную теорему, найдите асимптотически точные оценки для соотношений: а) T(n)=4T(n/2)+n; б) T(n)=4T(n/2)+n2. 42 Используя основную теорему, покажите, что соотношение T(n)=T(n/2)+ Θ(1) (для двоичного поиска) T(n)= Θ(log(n)). 43 Докажите, что для непрерывной задачи о рюкзаке выполнен принцип жадного алгоритма. 44 Разработайте основанный на динамическом программировании алгоритм для решения дискретной задачи о рюкзаке. Алгоритм должен сработать за время O(nW), где n – количество вещей, W – максимальный вес рюкзака. 45 Докажите, что в бинарном дереве, соответствующем оптимальному префиксному коду, всякая вершина либо является листом, либо имеет двух детей. 46 Найдите код Хаффмена для алфавита, в котором частоты символов совпадают с первыми восемью числами Фибоначчи: a:1 b:1 c:2 d:3 e:3 f:8 g:13 h:21Что будет, если в алфавите n символов, частоты которых совпадают с первыми n числами Фибоначчи? 47 Некто утверждает, что написанная им программа сжатия информации позволяет сжать любой файл длины 1000 (8 – битовых байтов) хотя бы на один

бит, после чего написанная им же программа восстановления сможет восстановить исходный файл. Почему он неправ? 48 Пусть S – конечное множество, k – натуральное число, Ik – семейство всех подмножеств S, содержащих не более k элементов. Покажите, что (S, Ik) – матроид. 49 Покажите, что отношение ≤ p транзитивно, то есть из L1≤ pL2 и L2≤ pL3 следует L1≤ pL3. 50 Множество вершин V′⊂V графа G=(V, E) называется независимым, если никакие две его вершины не соединены ребром. Задача о независимом множестве состоит в отыскании в данном графе независимого множества максимального размера. Сформулируйте соответствующую задачу разрешения и докажите её - полноту. 51 Показать, что в алгебре число 2 порождает множество всех положительных чисел, число 1 – положительных чисел, а совокупность {0;1} порождает всю алгебру. 52 Выяснить, что все подалгебры алгебры исчерпываются следующими: 1) подалгебра, порожденная нулем и состоящая из него; 2) подалгебра, порожденная числом 1 и совпадающая с самой алгеброй; 3) подалгебра, порожденная произвольным числом a>1 и состоящая из чисел 0, а, 2а, 3а,… 53 Каждая подалгебра алгебры состоит из всевозможных кратных подходящего числа а, за исключением, быть может, конечного числа таковых. Доказать. 54 Рассмолтрим алгебру , где “-“ – частичная операция:  x − y, x ≥ y, Какие функции представляются термами: 0(x-(x+1)), (x-y)+y, x −& y =  ∃, x < y.

(x+y)-y? Показать, что функция 2-х переменных не может быть представлена термом в указанной алгебре (т.е. термом, записанным в алфавите {x, +, *, -}). 55 Операция подстановки одноместной функции в одноместную функцию дает снова одноместную функцию. Эту операцию обозначим *. Таким образом, по определению f * g = S (f,g), (f * g)(x) =f (g(x)) Операция * ассоциативна, но не коммутативна: f * (g*h)= (f*g) * h, s * sg = sg * s Показать, что для любой одноместной функции f I11*f=f*I11, f-1*f*f-1=f-1. Если f-1 всюду определена, то (f* f-1)(x)=x. Показать, что существуют одноместные функции f, для которых f-1 всюду определена и в то же время f-1f≠I11. 56 Для двуместных функций введем операцию τ полагая fτ(x,y)=f(x,y). Операция τ удовлетворяет следующим соотношениям: fτ=S3(f,I22,I12), µx(f(x,y)=z)=(Mfτ)(y,z). 57 Если x-вещественное число, то символом [x] обозначим целую часть x, т.е. наибольшее целое число, не превосходящее x . Показать, что функция q(x)=x-[√ x]2 удовлетворяет соотношениям q-1(2x)=x2+2x, q-1(2x+1)=x2+4x+2. 58 Пусть F-множество всех частичных функций на N от любого числа переменных. . Основное определение частичной рекурсивнос-

ти дает: совокупность всех частичных функций, частично рекурсивных относительно заданной системы частичных функций G, есть подалгебра алгебры (1), порожденная в (1) системой G, Imn , O, S. Обозначим через Fl совокупность всех всюду определенных функций из F и рассмотрим частичную подалгебру

(2)

алгебры (1). Тогда совокупность всех общекурсивных функций есть подалгебра алгебры (2), порожденная в (2) простейшими функциями 0,s,Imn. 59 Доказать, что каждая всюду определенная функция, равная натуральному числу a везде, за исключением конечного числа точек, является примитивно рекурсивной. 60 Доказать примитивную рекурсивность двуместных функций [x/y], rest (x,y), где [x/y] означает (неполное) частное, а rest(x,y) - остаток от деления x на y . По определению полагаем также, что [x/0]=x и rest (x,0)=x.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1 Новиков П.С. Элементы математической логики. - М: Наука, 1973. 328с. 2 Новиков Ф.А. Дискретная математика для программистов. – СПб: Питер, 2000. – 304с. 3 Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. – М.: МЦНМО, 1999. – 176с. 4 Мальцев А.И. Алгоритмы и рекурсивные функции. – М.: Наука, 1965. – 392с. 5 Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ. – М.: МЦНМО, 1999. – 960с. 6 Информатика / Учебное пособие для пед. спец. высш. учеб. заведений. – М.: Просвещение, 1991. – 288с. 7 Поддубная Л.М., Шаньгин В.Ф. Мне нравится Паскаль. – М.: Радио и связь, 1992. – 160с. 8 Акритас А.Основы компьютерной алгебры с приложениями./ Пер. с англ. – М.: Мир, 1994. – 544с. 9 Компаниец Р.И., Маньков Е.В., Филатов Н.Е. Системное программирование. / Учебное пособие для высших и средних учебных заведений. – СПб: КОРОНА принт, 2000. – 256с. 10 Кук Д., Бейз Г. Компьютерная математика. / Пер. с англ. – М.: Мир, 1990. – 384с.