Математическая логика и теория алгоритмов что это

Математическая логика и теория алгоритмов

ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ И ТЕОРИИ АЛГОРИТМОВ:

Лекция 1. Теория формальных языков.

Содержание лекции: 00:07 начало вводной части 13:32 теорема о корректности 28:07 конец вводной части 28:51 начало лекции 31:32 цепочка определений (символ, алфавит, слово, язык) 42:12 отношения 50:42 операции над языками 01:09:46 правильные алгебраические выражения 01:11:47 теорема 01:12:53 лемма

Лекция 2-3. Пропозициональные формулы.

Лекция 5. Исчисление высказываний.

Содержание лекции: Исчисление высказываний.

Лекция 6. Исчисление высказываний (продолжение)

Содержание лекции: Исчисление высказываний

Лекция 7. Полнота исчисления высказываний (продолжение). Непротиворечивость и совместность

Лекция 8. Метод резолюций

Лекция 9. Формулы с кванторами. Языки I-го порядка

Лекция 10. Общезначимые формулы

Лекция 11. Метод автоморфизмов

Лекция 12. Элиминация кванторов

Источник

Курс лекций по математической логике и теории алгоритмов

МИНИСТЕРСТВО ОБРАЗОВАНИЯ МОСКОВСКОЙ ОБЛАСТИ

Государственное бюджетное профессиональное образовательное

учреждение Московской области «Ногинский колледж»

математической логике и теории алгоритмов

Введение

Зададимся вопросом: «для чего инженеру–программисту нужен данный курс?». Краткий ответ: Изучение его преследует две цели – изучить логические основы процесса написания программ и приобрести навыки строгого, формализованного мышления. А теперь более подробно.

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

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

Рассмотрим вкратце этапы развития логики.

1) Все млекопитающие имеют скелет.

Все киты – млекопитающие.

Следовательно, все киты имеют скелет.

2) Все квадраты ромбы,

все ромбы – параллелограммы.

Следовательно, все квадраты – параллелограммы.

В общем виде этот силлогизм имеет форму:

А вот пример силлогизма неправильной формы:

Все квадраты – ромбы.

Некоторые ромбы имеют острый угол.

Следовательно, некоторые квадраты имеют острый угол.

Аристотель выделил все правильные формы силлогизмов, которые можно составить из рассуждений вида: «Все A суть B «; «Некоторые A суть B «; «Все A не суть B «; «Некоторые A не суть B «.

2-й этап. Однако, развитие математики выявило недостаточность формальной логики, поэтому в конце 17в. Г.Лейбниц предложил понятия логики обозначить символами, которые соединялись бы по особым правилам. Это позволяло всякое рассуждение заменить вычислением.

Первая реализация идей Г.Лейбница принадлежит английскому математику Дж.Булю (1815-1864). Он создал алгебру, в которой буквами обозначены высказывания, и это привело к алгебре высказываний (или булевой алгебре). Именно благодаря введению символов в логику была получена основа для создания новой науки – математической логики.

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

3-й этап связан с XX веком и попытками обосновать справедливость математических доказательств, с исследованиями теории чисел, а также с попыткой разрешить известные логические парадоксы.

Некто говорит: ’’я лгу’’. Если он при этом лжет, то сказанное им есть ложь, и, следовательно, он не лжет. Если же он не лжет, то сказанное им есть истина, и следовательно, он лжет. В любом случае оказывается, что он лжет и не лжет одновременно.

Развитие математической логики особенно активизировалось в XX нашего века в связи с развитием вычислительной техники и программирования. Очевидно, что к омпьютерные науки носят прикладной характер и конечной их целью является создание и использование вычислительных систем. Здесь теоретические знания подтверждаются идеями воплощенными в ”железе” и в получении результатов по обработке информации. Поэтому для инженера, программиста, математическая логика является наукой о правильных вычислениях, обоснованных алгоритмах, надежно функционирующих программах. Она не рассматривает вопросы проектирования программ, но изучает языки программирования как формальные системы и касается аспектов эффективности тех или иных алгоритмов.

В учебном пособии излагается материал по математической логике и основам теории алгоритмов, изучаемый в курсе «Математическая логика и теория алгоритмов» и предназначенный для специалистов инженерного профиля.

Глава I. Алгебра логики

§1.1. Определение булевой функции

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

Булеву функцию от n переменных можно задать таблицей истинности, в которой наборы значений аргументов расположены в порядке возрастания их номеров: сначала идет набор, представляющий собой двоичное разложение 0 (этот набор имеет номер 0); затем идет набор, являющийся двоичным разложением 1, потом 2, 3 и т.д. Последний набор состоит из n единиц и является двоичным разложением числа (такой порядок расположения наборов назовем лексикографическим порядком). Учитывая, что отсчет начинается с 0, а значение булевой функции может быть либо 0 либо 1, заключаем, что существует всего различных булевых функций от n переменных. Таким образом, имеется, например, 16 булевых функций от двух переменных, 256 — от трех и т. д.

Булева функция также однозначно задается перечислением всех наборов, на которых она принимает значение 0, либо перечислением всех наборов, на которых она принимает значение 1. Полученную в примере функцию f можно также задать следующей системой равенств: f (0,0,0) = f (0,0,1) = f (0,1,0) = f (1,0,0) =0.

§1.2. Элементарные булевы функции

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

3. Отрицанием называется булева функция одной переменной, которая определяется следующей таблицей истинности

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

Другие названия: логическое умножение (произведение); логическое «и».

Запись xy может читаться так: «икс и игрек» или «икс умножить на игрек».

5. Дизъюнкцией называется булева функция двух переменных, которая определяется следующей таблицей истинности

Другие названия: логическое сложение (сумма); логическое «или».

Запись xy может читаться так: «икс или игрек» или «сумма икс и игрек».

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

Другое название: логическое следование.

Запись x y может читаться так: «из икс следует игрек».

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

Запись xy может читаться так: «икс эквивалентно игрек» или «икс равносильно игрек».

8. Суммой по модулю_2 называется булева функция двух переменных, которая определяется следующей таблицей истинности

Другое название: антиэквивалентность.

Запись x y может читаться так: «икс плюс игрек».

9. Штрих Шеффера это булева функция двух переменных, которая определяется следующей таблицей истинности

Другое название: отрицание конъюнкции, логическое «не-и».

Запись x y может читаться так: «не икс или не игрек», «икс и игрек несовместны», «икс штрих Шеффера игрек».

10. Стрелка Пирса это булева функция двух переменных, которая определяется следующей таблицей истинности

Другое название: отрицание дизъюнкции, логическое «не-или», функция Вебба.

Запись x y может читаться так: «ни икс и ни игрек», «икс стрелка Пирса игрек».

§1.3. Задание булевых функций посредством элементарных

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

Пример 1.3.1. Пусть задана элементарная булева функция xy. Подставим вместо x функцию x₁x₂. Получаем функцию трех переменных (x₁x₂)y. Если вместо переменной y подставить, например, x₃x₄, то получаем новую функцию от четырех переменных: (x₁x₂)(x₃x₄). Очевидно, что таким образом мы будем получать булевы функции, которые будут выражаться через элементарные булевы функции.

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

1. В формуле x y z скобки расставляются следующим образом: (( x y) z ), т.к. операция сильнее операции согласно нашему соглашению.

2. В формуле x y z x скобки расставляются следующим образом: (( x y)( z x ))

3. В формуле ( x y) z xy z скобки расставляются следующим образом: (( x y)( z (( xy ) ( z )))).

§1.4. Существенные и несущественные переменные

В этом случае x _k называют существенной переменной , в противном случае x _k называют несущественной (фиктивной) переменной . Другими словами, переменная является несущественной, если ее изменение не изменяет значения функции.

Для этих функций переменная x ₁ — существенная, а переменная x ₂ —несущественная.

§1.5. Таблицы истинности. Эквивалентные функции

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

Таким образом, формула F ₁ реализует дизъюнкцию.

Таким образом, формула F ₂ реализует константу 1.

Таким образом, формула F ₃ реализует дизъюнкцию.

Булевы функции f ₁ и f ₂ называются эквивалентными, если на всяком наборе ( a ₁, a ₂,…, a _n ) нулей и единиц значения функций совпадают. Обозначение эквивалентных функций следующее: f ₁= f ₂.

Согласно приведенным примерам 1-3, можно написать

§1.6. Основные эквивалентности

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

Законы де Моргана: при справедливы формулы

Правила операций с константами 0 и 1:

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

Докажем 1-й закон де Моргана методом математической индукции.

Справедливость формулы при проверим непосредственно при помощи таблицы истинности:

Пусть формула верна при . Тогда при имеем:

§1.7. Функциональная полнота

В типичной современной цифровой вычислительной машине цифрами являются 0 и 1. Следовательно, команды, которые выполняет процессор, суть булевы функции. Ниже будет показано, что любая булева функция реализуется через конъюнкцию, дизъюнкцию и отрицание. Следовательно, можно построить нужный процессор, имея в распоряжении элементы, реализующие конъюнкцию, дизъюнкцию и отрицание. Этот раздел посвящен ответу на вопрос: существуют ли (и если существуют, то какие) другие системы булевых функций, обладающих тем свойством, что с их помощью можно выразить все другие функции.

Введем в рассмотрение ряд классов функций.

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

Критерий полноты (Теорема Поста) . Система булевых функций является полной тогда и только тогда, когда она включает хотя бы одну функцию: не сохраняющую константу 0, не сохраняющую константу 1, не самодвойственную, нелинейную и немонотонную.

Не сохрани-мость константы 0

Не сохрани-мость константы 1

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

Система S ₇ = <,0>образует базис.

Пример 1.7.2. Используя теорему Поста проверить, является ли полной система функций S =< f ₁, f ₂>, где

Решение: Проверим какими свойствами обладают данные функции.

1. Сохранимость константы 0.

f ₁(0,0)=01=0 – сохраняет константу 0.

f ₂(0,0)= – не сохраняет константу 0.

2. Сохранимость константы 1.

f ₁(1,1)=10=0 – не сохраняет константу 1.

f ₂(1,1)=00=1 – сохраняет константу 1.

Составим таблицы истинности для функций:

Используя таблицу истинности для f ₂, полученную в п.3, имеем

Итак, f ₂=1 yxy – не линейна.

Очевидно, что наборы упорядочены следующим образом:

Проверим на монотонность функцию f ₁:

Итак, мы получили, что для (1,0)(1,1), не выполняется f ₁(1,0) f ₁(1,1), следовательно функция f ₁–не монотонна.

Проверим на монотонность функцию f ₂(0,0)=1; f ₂(0,1)=0. Итак, для (0,0)(0,1) мы не получили что f ₂(0,0) f ₂(0,1). Следовательно, функция f ₂–не монотонна.

Сведем наши вычисления в таблицу.

Из теоремы Поста, заключаем, что система – полная.

§2.1. Нормальные формы

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

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция конечного числа конъюнктов .

Конъюнктивной нормальной формой (КНФ) называется конъюнкция конечного числа дизъюнктов .

xyyzx ― это ДНФ (сумма произведений).

―это КНФ (произведение сумм).

― это ДНФ и КНФ (одновременно).

― это ДНФ и КНФ (одновременно).

( xxy )·( yzx )· z ― это КНФ.

― это не нормальная форма (не ДНФ и не КНФ).

используем законы де Моргана, чтобы преобразовать формулу к виду, в котором знаки отрицания относятся только к отдельным переменным;

применяем правило снятия двойного отрицания: x = x ;

далее использовать законы дистрибутивности, причем необходимо использовать первый закон дистрибутивности для приведения к ДНФ

и второй закон дистрибутивности для приведения к КНФ.

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

Пример 2.1.1. Для приведения к ДНФ используем 1-ый закон дистрибутивности.

§2.2. Совершенные нормальные формы

Если в каждом члене нормальной формы представлены все переменные (либо сами, либо их отрицания), причем в каждом отдельном конъюнкте или дизъюнкте любая переменная входит ровно один раз (либо сама либо ее отрицание), то эта форма называется совершенной нормальной формой (СДНФ или СКНФ).

это совершенная ДНФ.

это совершенная КНФ.

xyz это совершенная ДНФ.

1. Любая булева функция, не являющаяся тождественным нулем, имеет только одну СДНФ, с точностью до расположения членов.

2. Любая булева функция, не являющаяся тождественной 1, имеет только одну СКНФ, с точностью до расположения членов.

Доказательство теоремы проведем конструктивно, как решение следующей задачи: по данной таблице истинности построить СДНФ.

Пример 2.2.1. По данной таблице истинности (таб.2.2) построить СДНФ.

Очевидно, что конъюнкция равна 1 только на наборе (0,0,0), а равна 1 на наборе (0,0,1) и т.д. (см. по таблице). Далее, заметим, что дизъюнкция двух основных конъюнкций равна 1 ровно на двух наборах, которые соответствуют данным основным конъюнкциям. Например, функция равна 1 только на двух наборах – (0,0,0) и (0,0,1), а на всех других наборах она равна 0. Аналогично, дизъюнкция трех основных конъюнкций равна 1 ровно на трех наборах, которые соответствуют данным основным конъюнкциям и т.д.

Таким образом, получаем правило: для построения СДНФ следует выбрать строки, в которых функция равна 1, а затем взять дизъюнкцию соответствующих основных конъюнкций, получим искомую СДНФ. Так для нашего примера, имеем

Задача. По данной таблице истинности построить СКНФ.

Правило для построения СКНФ: следует выбрать строки, в которых функция равна 0, а затем взять конъюнкцию соответствующих конституент_0. В результате получится искомая СКНФ. Так для нашего примера, имеем

Построим СКНФ для нашего примера на основании замечания.

Строим СДНФ для отрицания.

Используем законы де Моргана

Описанный способ нахождения СДНФ (и СКНФ) по таблице истинности бывает часто более трудоемким, чем следующий алгоритм.

Для нахождения СДНФ данную формулу приводим сначала к ДНФ.

Если в полученной ДНФ имеется несколько одинаковых конституент единицы, то оставляем только одну из них. В результате получается СДНФ.

Пример 2.2.2. Построить СДНФ для функции f при помощи эквивалентных преобразований.

§2.3. Минимизация ДНФ методом Квайна

Каждая формула имеет конечное число вхождений переменных. Под вхождением переменной понимается место, которое переменная занимает в формуле. Задача заключается в том, чтобы для данной булевой функции f найти ДНФ, представляющую эту функцию и имеющую наименьшее число вхождений переменных.

называется литерой. Конъюнктом называется конъюнкция литер. Например, формулы являются конъюнктами. Элементарным произведением называется конъюнкт, в который любая переменная входит не более одного раза (либо сама либо ее отрицание).

Пример 2.3.1. Найдем все импликанты и простые импликанты для формулы f = xy . Всего имеется 8 элементарных произведений с переменными х и у. Ниже, для наглядности, приведены их таблицы истинности:

Сокращенной ДНФ называется дизъюнкция всех простых импликант данной формулы (функции).

Теорема 2.3.1. Любая булева функция, не являющаяся константой 0, представима в виде сокращенной ДНФ.

В примере 2.3.1 функция, соответствующая формул e x y представима формулой которая является ее сокращенной ДНФ.

Сокращенная ДНФ может содержать лишние импликанты, удаление которых не меняет таблицы истинности. Если из сокращенной ДНФ удалить все лишние импликанты, то получается ДНФ, называемая тупиковой.

Заметим, что представление функции в виде тупиковой ДНФ в общем случае неоднозначно. Выбор из всех тупиковых форм, формы с наименьшим числом вхождений переменных дает минимальную ДНФ <МДНФ).

Рассмотрим метод Квайна, для нахождения МДНФ, представляющей данную булеву функцию. Определим следующие три операции:

операция полного склеивания: ;

операция неполного склеивания:

Теорема 2.3.2 (теорема Квайна). Если исходя из СДНФ функции произвести все возможные операции неполного склеивания, а затем элементарного поглощения, то в результате получится сокращенная ДНФ, т. е. дизъюнкция всех простых импликант.

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

Тогда, производя операции склеивания, а затем элементарного поглощения, имеем

Для получения минимальной ДНФ из сокращенной ДНФ используется матрица Квайна, которая строится следующим образом. В заголовках столбцов таблицы записываются конституенты единицы совершенной ДНФ, а в заголовках строк — простые импликанты из полученной сокращенной ДНФ. В таблице звездочками отмечаются те пересечения строк и столбцов, для которых конъюнкт, стоящий в заголовке строки, входит в конституенту единицы, являющейся заголовком столбца.

Для примера 2.3.3. матрица Квайна имеет вид

В тупиковую ДНФ выбирается минимальное число простых импликант, дизъюнкция которых сохраняет все конституенты единицы, т. е. каждый столбец матрицы Квайна содержит звездочку, стоящую на пересечении со строкой, соответствующей одной из выбранных импликант. В качестве минимальной ДНФ выбирается тупиковая, которая имеет наименьшее число вхождений переменных.

§ 2.4. Карты Карно

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

Для построения минимальной ДНФ производится процедура склеивания «1». Склеивающимся значениям «1» соответствуют соседние клетки, т.е. клетки отличающиеся лишь значением одной переменной (на графическом изображении разделенных вертикальной или горизонтальной линией с учетом соседства противоположных крайних клеток).

Процесс склеивания «1» сводится к объединению в группы единичных клеток карты Карно, при этом необходимо выполнять следующие правила;

Количество клеток, входящих в одну группу, должно выражаться числом кратным 2, т.е. 2 m где m =0,1,2.

Каждая клетка, входящая в группу из 2 m клеток, должна иметь m соседних в группе.

Каждая клетка должна входить хотя бы в одну группу.

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

Число групп должно быть минимальным.

Считывание функции f по группе склеивания производится следующим образом: переменные, которые сохраняют одинаковые значения в клетках группы склеивания, входят в конъюнкцию, причем значениям 1 соответствуют сами переменные, а значениям 0 их отрицания.

Приведем шаблоны, которые помогают строить покрытия 1 (переменные считаем теми же, но их писать не будем). Для упрощения записи мы не будем отмечать переменные, хотя сохраним их обозначения, как и в таблицах 2.4.1, 2.4.2.

Приведем шаблоны для n =3, которые помогают строить покрытия единицы (1).

Приведем шаблоны для n =4, которые помогают строить покрытия единицы (1).

Пример 2.4.1. С помощью Карт Карно, построить МДНФ и МКНФ функций заданных вектором своих значений.

Решение. 1) Занесем данные в карту Карно. Удобно сначала отметить клетки, где функция равна нулю. Функция f равна нулю на наборах, являющимися двоичными разложениями чисел 1,4,6 (т.к. отсчет начинается с 0). Таким образом, f (0,0,1)= f (1,0,0)= f (1,1,0)=0.

Для построения МКНФ, построим МДНФ для функции :

2) Заносим данные в карту Карно. Получаем, что

f (0,0,0,1)= f (1,0,0,1)= f (1,1,1,0)= f (1,1,1,1)=0.

Далее, Сначала смотрим, есть ли покрытия_1 из 16 клеток покрывающих хотя бы одну непокрытую 1. Таких покрытий нет. Переходим к покрытиям из 8 клеток. Смотрим, есть ли покрытия 1 из 8 клеток покрывающих хотя бы одну непокрытую 1. Таких покрытий нет. Переходим к покрытиям из 4 клеток. Смотрим, есть ли покрытия 1 из 4 клеток покрывающих хотя бы одну непокрытую 1. Таких покрытий четыре. Таким образом, все 1 стали покрытыми. Далее, смотрим можно ли убрать некоторые покрытия, так чтобы все единицы остались покрытыми. Убрать некоторые покрытия нельзя. Производим считывание функции:

Множество булевых функций, заданный в базисе Жегалкина S ₄= <,&,1>называется алгеброй Жегалкина.

Утверждение 3.1.1. Через операции алгебры Жегалкина можно выразить все другие булевы функции:

xy=1 xxy, xy=1xyxy, xy=1xy.

Определение. Полиномом Жегалкина (полиномом по модулю 2) от n переменных x ₁, x ₂,…, x _n называется выражение вида

где постоянные с_к могут принимать значения 0 ли 1.

Если полином Жегалкина не содержит произведений отдельных переменных, то он называется линейным ( линей ная функция).

Например, f = xyzxyz и f 1=1 xyz –полиномы, причем второй является линейной функцией.

Теорема (Жегалкина). Каждая булева функция представляется в виде полинома Жегалкина единственным образом.

Приведем основные методы построения полиномов Жегалкина от заданной функции.

Найдем коэффициенты с_к. Для этого последовательно придадим переменным x ₁, x ₂,…, x _n значения из каждой строки таблицы истинности. В итоге получим систему из 2 n уравнений с 2 n неизвестными, имеющую единственное решение. Решив ее, находим коэффициенты полинома P ( x ₁, x ₂,…, x _n ).

2. Метод, основанный на преобразовании формул над множеством связок <, &>. Строят некоторую формулу Ф над множеством связок<,&>, реализующую данную функцию f ( x ₁, x ₂,…, x _n ). Затем заменяют всюду подформулы вида на A 1, раскрывают скобки, пользуясь дистрибутивным законом (см. свойство 3), а затем применяют свойства 4 и 5.

Решение. 1. (метод неопределенных коэффициентов). Запишем искомый полином в виде

Пользуясь таблицей истинности

Откуда последовательно находим, c ₀=1, с₁=1, c ₂=0, c ₁₂=1. Следовательно

xy =1 xxy (сравните с утверждением 3.1).

2.(Метод преобразования формул.) Имеем

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

§4.1. Высказывания

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

Высказыванием назовем повествовательное предложение относительно которого можно однозначно сказать истинно оно (значение И или 1) или ложно (значение Л или 0) в конкретный момент времени. Например, «5-простое число», «нажата клавиша « Esc »» и т.д. При помощи связок «не», «и», «или», «если,… то», «если и только если» (им отвечают операции «», «&», «», «», «» соответственно) можно построить более сложные высказывания (предложения). Так строится алгебра высказываний.

Для упрощения записи сложных высказываний вводится старшинство связок: «», «&», «», «», «», что помогает опустить лишние скобки.

Простые высказывания назовем пропозициональными переменными.

Введем понятие формулы.

Пропозициональные переменные являются формулами.

Если А, В формулы, то выражения А, АВ, АВ, АВ, АВ являются формулами.

Формулами являются только выражения, построенные в соответствии с пунктами 1 и 2.

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

Описание свойств алгебры высказываний аналогично описанию соответствующих функций в булевой алгебре и мы их опускаем.

Пример. После обсуждения состава участников предполагаемой экспедиции было решено, что должны выполняться два условия:

а) если поедет Арбузов, то должны поехать еще Брюквин или Вишневский;

б) если поедут Арбузов и Вишневский, то поедет и Брюквин.

Требуется установить, кто из перечисленных сотрудников войдет в состав экспедиции.

Решение. Назначение в экспедицию Арбузова, Брюквина и Вишневского будем обозначать буквами А, Б, В соответственно.

Тогда условие а) можно записать в виде АБВ, а условие б) в виде А&В Б. Так как оба условия должны выполняться одновременно, то они должны быть соединены логической связью «и» (конъюнкция равна 1 только в одном случае, когда все переменные равны 1). Поэтому принятое решение можно записать в виде формулы L =(АБВ)&(А&ВБ) эта формула должна быть истинной.

Следовательно, для решения задачи можно построить таблицу истинности формулы L и найти значение пропозициональных переменных А,Б,В на которых формула L равна 1. А можно построить СДНФ или СКНФ и естественным образом сделать заключение.

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

Применяя к последнему выражению второй закон дистрибутивности, получим

L = [(БВ)&(Б)] = [Б( B &)] = Б= A Б.

Отсюда следует, что если поедет в экспедицию Арбузов, то с ним должен ехать и Брюквин.

§4.2. Предикаты. Логические операции над предикатами

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

Пример 4.2.1. D ( x ₁, x ₂) = «Натуральное число х₁ делится (без остатка) на натуральное число х₂» — двуместный предикат, определенный на множестве пар натуральных чисел M =NN. Очевидно, D (4,2) = И, D (3,5) = 0.

§4.3. Кванторы. Логика предикатов

Определение 4.3.1. Пусть Р(х) — одноместный предикат. Поставим ему в соответствие высказывание, обозначаемое xP ( x ) (читается «для любого х Р(х)»>, которое истинно тогда и только тогда, когда Р(х) — тождественно истинный предикат. О высказывании xP ( x ) говорят, что оно получено из предиката Р навешиванием квантора всеобщности по переменной х.

Определение 4.3.2. Пусть Р(х) — одноместный предикат. Поставим ему в соответствие высказывание, обозначаемое xP ( x ) (читается «существует х Р(х)»), которое ложно тогда и только тогда, когда Р(х) — тождественно ложный предикат. О высказывании xP ( x ) говорят, что оно получено из предиката Р навешиванием квантора существования по переменной х.

Замечание 1. Обозначения и для кванторов — это перевернутые латинские буквы А и Е соответственно, которые являются первыми буквами в английских словах All — все, E xist — существовать.

Замечание 2. Высказывания можно считать предикатами, не содержащими переменных, т. е. 0-местными предикатами (или предикатами любой местности).

Пример 4.3.1. Пусть D ( x 1, x 2) = «Натуральное число х1 делится (без остатка) на натуральное число х2» — двухместный предикат. Навесим последовательно на его переменные кванторы. Ясно, что

1) x 1 x 2 D ( x 1, x 2)=0 2) x 2 x 1 D ( x 1, x 2)=0 3) x 1 x 2 D ( x 1, x 2)=1

4) x 2 x 1 D ( x 1, x 2)=1 5) x 1 x 2 D ( x 1, x 2)=1 6) x 2 x 1 D ( x 1, x 2)=1

7) x 1 x 2 D ( x 1, x 2)=0 8) x 1 x 2 D ( x 1, x 2)=1.

Теорема 4.3.1. Разноименные кванторы, вообще говоря, не коммутируют.

Сравнение 7 и 8 в последнем примере доказывает это утверждение.

Алфавит логики предикатов содержит следующие символы:

1) символы предметных переменных – обычно строчные латинские буквы с индексами или без них;

2) символы предикатов – обычно прописные латинские буквы с индексами или без них;

3) логические символы: ;

4) символы кванторов – ;

5) скобки и запятую.

Слово в алфавите логике предикатов называется формулой, если оно удовлетворяет следующему индуктивному определению:

1) Если P – символ предиката, x₁, x₂. x_n – символы предметных переменных, то P(x₁,x₂. x_n) – формула. Такая формула называется атомарной. Все предметные переменные атомарных формул свободные, связанных переменных нет.

2) Пусть A – формула. Тогда тоже формула. Свободные и связанные переменные формулы – это соответственно свободные и связанные переменные формулы A.

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

4) Пусть A – формула, содержащая свободную переменную x. Тогда тоже формулы, Переменная x в них связана. Остальные переменные, которые в формуле A свободны, остаются свободными, а переменные, которые в формуле A связаны, остаются связанными. Говорят, что формула A есть область действия квантора.

5) Слово в алфавите логики предикатов 1–5 является формулой только в том случае, если это следует из правил 1–4.

Пример 4.3.2. Рассмотрим классический силлогизм Аристотеля «Все люди смертны. Сократ – человек. Следовательно, Сократ – смертен.». Пусть – означает быть человеком, – быть смертным, – Сократ. Тогда данный силлогизм может быть представлен в виде следующей формулы:

Теорема 4.3.2. (основные равносильности, содержащие кванторы)

Имеют место следующие равносильности:

Ограничение действия кванторов

Для любого двухместного предиката

Решение. Очевидно, что = есть двуместный предикат. Построим таблицу истинности предиката :

и т.д. для каждого значения из исходной таблицы истинности. Получим, таблицу истинности предиката:

Формулы F и G равносильны (в логике предикатов), если они равносильны на всех множествах (обозначаетс: F=G).

то можно заключить, что формулы неравносильны.

Приведем к пренексной нормальной форме:

Так как, пренексные нормальные формы не совпадают, то можно заключить, что формулы неравносильны.

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

Формальная теория (или исчисление) — это:

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

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

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

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

Множество символов A может быть конечным или бесконечным. Обычно для образования символов используют конечное множество букв, к которым, если нужно, приписываются в качестве индексов натуральные числа.

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

Множество аксиом B может быть конечным или бесконечным. Если множество аксиом бесконечно, то, как правило, оно задается с помощью конечного множества схем аксиом и правил порождения конкретных аксиом из схемы аксиом.

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

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

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

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

§5.2. Исчисление высказываний

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

Алфавит ИВ состоит из

Множество формул ИВ определяется индуктивно:

все пропозициональные переменные являются формулами ИВ;

выражение является формулой ИВ тогда и только тогда, когда это может быть установлено с помощью пунктов «1» и «2».

Формулы, указанные в пункте 1, называются элементарными формулами, или атомами, а полученные по правилу пункта 2,-сложными формулами.

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

Указанные формулы называются схемами аксиом ИВ. При подстановке конкретных формул в какую-либо схему получается частный случай схемы аксиом.

Правилом вывода в ИВ является правило заключения < modus ponens ):

если A и AB — выводимые формулы, то B — также выводимая формула. Символически это записывается так:.

Например, если высказывания АВ и АВ(АС) выводимы, то высказывание АС также выводимо согласно правилу заключения.

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

Пример 5.2.1. Покажем, что формула AA выводима в ИВ. Для этого построим вывод данной формулы:

из 1 и 2 по modus ponens заключаем

из пп. 3 и 4 по правилу вывода справедливо

(сведение множества гипотез к одной гипотезе).

§5.3. Теорема о дедукции. Полнота ИВ

Теорема 5.3.1. (теорема о дедукции)

1) – аксиома или подстановка в аксиому;

2) – одна из посылок F ₁, F ₂,…, F _n ;

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

3) modus ponens 1 и 2.

3) modus ponens 1 и 2,

5) modus ponens 4 и 3.

Аналогично F ₁, F ₂,…, F _{n -2}├ F _{n -1} ( F _n A ), и т. д. Продолжая этот процесс необходимое число раз, получаем

Проведем следующую классификацию формул:

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

Если формула F во всех своих возможных интерпретациях принимает значение ложь, то F называется: тождественно ложная, невыполнимая формула.

Если формула F не является общезначимой и невыполнимой, то она называется нейтральной.

Следующая теорема сводит проверку доказуемости формулы к проверке ее тождественной истинности.

Теорема 5.3.2. (о полноте). Формула F доказуема тогда и только тогда, когда A тождественно истинна (тавтология): ├ F F тавтология.

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

Пример 5.3.1. Докажем, что Р├Р. По теореме о дедукции это равносильно тому, что ├(РР). В свою очередь, по теореме о полноте, достаточно доказать, что (РР) тавтология. Составляя таблицу истинности для формулы (РР), убеждаемся, что (РР) тождественно истинна и, следовательно, доказуема.

Пример 5.3.2. Является ли формула ABAB общезначимой? Составляем таблицу истинности.

Пример 5.3.3. Общезначима ли формула АВАВ?

Допустим, что данная формула не общезначима, тогда уравнение АВАВ=Л должно иметь решение. Следовательно, уравнения АВ=И, АВ=Л также должны иметь решения. Легко видеть, что А= И, В=Л является таким решением. Итак, имеется набор значений формул А, В, при котором формула АВАВ принимает значение Л. Значит эта формула не общезначима.

Теорема 5.3.3. (о непротиворечивости). Исчисление ИВ непротиворечиво.

Доказательство. По теореме о полноте любая формула, не являющаяся тождественно истинной, не доказуема в ИВ. Например, такой формулой является формула А(А).

Множество формул Г называется противоречивым, если Г├А(А). Если Г — противоречивое множество формул, будем обозначать этот факт через Г├.

Утверждение 5.3.1. Формула А выводима из множества формул Г тогда и только тогда, когда множество Г < A >— противоречиво.

§5.4. Автоматическое доказательство теорем

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

§5.5. Метод резолюций в ИВ

называется литерой. Литеры x и x называются контрарными. Конъюнктом называется конъюнкция литер. Дизъюнктом называется дизъюнкция литер.

Пусть S =( D ₁, D ₂,…, D _n ) множество дизъюнктов. Последовательность формул F ₁, F ₂,…, F _n называется резолютивным выводом из S, если для каждой формулы F _k выполняется одно из условий:

Теорема 5.5.1. (о полноте метода резолюций). Множество дизъюнктов S противоречиво в том и только в том случае, когда существует, резолютивный вывод из S, заканчивающийся 0.

Пример 5.5.2. Проверить методом резолюций соотношение

А(ВС), CD Е, FD &() E ├ А(В F ).

Согласно утверждению 5.3.1. надо проверить на противоречивость множество формул

Приведем все формулы из S к КНФ:

Таким образом, получаем множество дизъюнктов

Следствие 5.5.1. Если множество дизъюнктов S содержит резольвенты всех своих элементов, то S выполнимо тогда и только тогда, когда 0S.

§5.6. Исчисление предикатов

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

Теорема Чёрча. Не существует алгоритма, который для любой формулы логики предикатов устанавливает, общезначима она или нет.

Исчисление предикатов – это аксиоматическая теория:

Алфавит – те же символы, что и в логике предикатов.

Понятие формулы – совпадает с понятием формулы в логике предикатов.

1) 1 – 10: – аксиомы Клини исчисления высказываний, где под обозначениями понимаются уже любые формулы исчисления предикатов:

Система правил вывода:

2) правило обобщения ( – правило);

3) правило конкретизации (– правило);

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

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

Теорема 5.6.1. Аксиомы исчисления предикатов – общезначимые формулы.

Теорема 5.6.2. Формула, получающаяся из общезначимой по любому из правил вывода 1–4, является общезначимой.

Теорема 5.6.3. Любая выводимая в исчислении предикатов формула общезначима.

Теорема 5.6.4. Исчисление предикатов непротиворечиво.

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

Теорема о дедукции. Если имеется вывод в исчислении предикатов формулы B из последовательности формул Γ, A, то можно построить вывод формулы из последовательности формул Γ (символически: Если Γ, A├B, то Γ├), где Γ – набор некоторых формул A₁, A₂. A_n.

Пример. Некоторые пациенты любят своих докторов. Ни один пациент не любит знахаря. Следовательно, никакой доктор не является знахарем.

Решение. Введем пропозициональные переменные для простейших предикатов.

Теперь директивные правила примут следующий вид:

Тогда теорему можно записать так:

Проверим является ли логичным утверждение задачи при помощи метода резолюций (заодно продемонстрируем этот метод).

Исследуем множество дизъюнктов:

§6.1. Определение алгоритма

1) разложить число a на простые множители;

2) повторить п. 1 для b и перейти к п. 3;

3) составить произведение общих простых множителей из разложений а и b с показателями, равными наименьшим из показателей вхождения в разложения.

Проанализировав этот пример, отметим важнейшие черты (свойства) алгоритма:

1. Массовость — применимость алгоритма не к одной задаче, а к классу задач.

2. Дискретность — четкая разбивка на отдельные этапы (шаги) алгоритма.

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

4. Конечность — для получения результата при применении алгоритма к решению конкретной задачи выполняется конечная последовательность шагов алгоритма:

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

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

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

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

§6.2. Машина Тьюринга

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

Лента разбита на ячейки. Во всякой ячейке в точности один символ из внешнего алфавита A = <a ₀, a ₁,…, a _n >. Некоторый символ (будем обозначать его ) алфавита A называется пустым, а любая ячейка, содержащая в данный момент пустой символ, называется пустой ячейкой (в этот момент). Лента предполагается потенциально неограниченной в обе стороны.

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

Конфигурацией на ленте (или машинным словом) называется совокупность, образованная:

1) последовательностью символов из внешнего алфавита А, записанных в ячейках ленты, где a _{i (1)}.- символ записанный в первой ячейке слева и т.д. (любая такая последовательность называется словом),

2) состоянием внутренней памяти q _r ;

3) номером k воспринимаемой ячейки.

Конфигурацию машины будем записывать так:

Если в программе машины для пары ( q _i , a _u ) пятерка отсутствует, то в таблице на пересечении строки a _u , и столбца q _i ставится прочерк.

Итак, машина Тьюринга есть, по определению, набор М=(А, Q ,П), где А ― внешний алфавит, Q ― алфавит внутренних состояний, П ― программа.

Пример 6.2.1. Построим машину Тьюринга, складывающую натуральные числа, записанные в унарной системе счисления (т.е. записанные при помощи одного символа . Например 5=.).

Решение. Рассмотрим алфавит А = <, +, >.

Машина определяется следующей программой:

Выпишем последовательно возникающие при работе этой машины конфигурации на исходном слове +, т.е. 2+3. Здесь при записи конфигурации будем использовать следующее соглашение: состояние, в котором находится машина, записывается в круглых скобках справа за обозреваемой буквой.

Пример 6.2.2. Построить машину Тьюринга, удваивающую натуральные числа, записанные в унарной системе счисления.

Введение новой буквы и замена исходных | на позволяет различить исходные | и новые (приписанные) |. Состояние q ₁ обеспечивает замену | на , состояние q ₂ обеспечивает поиск , предназначенных для замены на |, и останов машины в случае, когда не обнаружено, q ₃ обеспечивает дописывание | в случае, когда произошла замена на |.

§6.3. Рекурсивные функции

Договоримся, что в этом параграфе

множество N натуральных чисел содержит 0 (нуль), т.е. N=<0,1,2,3. >;

область значений функций DN ;

рассматриваемые функции f = f ( x ₁,x₂,…, x _n ) могут быть частично определенные, т.е. определенные не для всех наборов натуральных чисел.

Введём в рассмотрение простейшие функции

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

Определение. Функции, которые могут быть получены из простейших о( x )=0, s ( x )= x +1, применением конечного числа раз операторов суперпозиции и примитивной рекурсии, называются примитивно рекурсивными.

Отметим; что примитивно рекурсивные функции всюду определены (т.е. определены для всех значений их аргументов). Действительно, простейшие функции o , s , являются всюду определёнными, а применение операторов суперпозиции и примитивной рекурсии ко всюду определённым функциям даёт также всюду определённые функции. Значит, такая функция, как

Существенно более широким классом функций, чем примитивно рекурсивные функции, является класс рекурсивных функций (определение см. ниже). В литературе эти функции называют также частично рекурсивными. Для их определения введём ещё один оператор.

Оператор минимизации это очевидное обобщение оператора взятия обратной функции. Обобщение довольно глубокое, так как от функции f не требуется, чтобы она была взаимно однозначной (по переменной x _{n +1} )

Определение. Функции, которые могут быть получены из простейших о( x )=0, s ( x )= x +1, применением конечного числа раз операторов суперпозиции, примитивной рекурсии и минимизации, называются рекурсивными.

Класс рекурсивных функций шире класса примитивно рекурсивных функций хотя бы по тому, что он содержит не только всюду определённые функции. Докажем, например, что функция

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

Отметим, что не всякая функция натуральных аргументов является рекурсивной, даже не всякая функция одного аргумента. Существование нерекурсивных функций и является «математической причиной» наличия алгоритмически неразрешимых задач.

§6.4. Алгоритмически неразрешимые задачи

В разных разделах математики встречаются алгоритмически неразрешимые задачи, т.е. задачи, для которых нет алгоритма решения, причём нет не потому что его пока не придумали, а потому что он невозможен в принципе. Разумеется, алгоритм надо понимать в смысле машин Тьюринга и рекурсивных функций. Сформулируем одну из этих задач

§6.5. Алгоритмы и их сложности

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

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

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

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

Допустим, у нас есть пять алгоритмов A 1, A 2,…, A 5 со следующими временными сложностями:

Источник