ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 5046
Скачиваний: 25
11
ла. Предметные переменные этой формулы свободны.
3.
Если
A
– формула и y – свободная переменная в ней, то
∀ y
A
и
∃ y
A
– формулы. Свободными переменными этих формул яв-
ляются все свободные переменные формулы
A
, исключая y.
Связанными переменными формул
∀ y
A
и
∃ y
A
являются все
связанные переменные формулы
A
и переменная y.
4.
Если
A
и формулы такие, что в них нет предметных перемен-
ных, связанных в одной формуле и свободных в другой, то
(
A
٨ ) , (
A
٧ ) , (
A
→ ) ,⎯
A
– формулы. Свободными пере-
менными этих формул являются все свободные переменные
формул
A
и , а связанными – связанные переменные формул
A
и .
Выпишем аксиомные схемы исчисления предикатов. В каче-
стве первых схем возьмем схемы 1 – 11 исчисления высказываний и
к ним добавим следующие две схемы.
12.
∀ x
A
(x)
→
A
(y).
13.
A
(y)
→ ∃ x
A
(x).
К правилам вывода исчисления предикатов кроме уже из-
вестного правила заключения отнесем следующие:
1.
Пусть (
A
(x))
→ ) и не содержит предметной переменной x,
тогда ((
∃ x
A
(x))
→ ).
2.
Пусть (
→
A
(x)) и не содержит предметной переменной x,
тогда (
→ (∀ x
A
(x))) .
Пример. Покажем, что ((
∀ x
A
(x))
→ (∃ x
A
(x))) – теорема
для произвольной формулы
A
(x):
1)
(
∀ x
A
(x)
→ (
A
(y)
→ ∃ x
A
(x)))
→ ((∀ x
A
(x)
→
A
(y))
→
(
∀ x
A
(x)
→ ∃ x
A
(x))) (схема 2);
2)
((
A
(y)
→ ∃ x
A
(x))
→ (∀ x
A
(x)
→ (
A
(y)
→ ∃ x
A
(x))))
(схема 1);
3)
(
A
(y)
→ ∃ x
A
(x)) (схема 13);
4)
(
∀ x
A
(x)
→ (
A
(y)
→ ∃ x
A
(x))) (из 2) и 3) по правилу заклю-
чения);
5)
((
∀ x
A
(x)
→
A
(y))
→ (∀ x
A
(x)
→ ∃ x
A
(x))) (из 1) и 4) по
правилу заключения);
12
6)
(
∀ x
A
(x)
→
A
(y)) (схема 12);
7)
(
∀ x
A
(x)
→ ∃ x
A
(x)) (из 5) и 6) по правилу заключения).
Исчисление предикатов можно интерпретировать в логику пре-
дикатов. Было установлено, что эта интерпретация адекватна. Од-
нако при решении этого вопроса не удается ограничиться средства-
ми конечной метатеории ввиду того, что в постановку вопроса вхо-
дит понятие тождественно истинной формулы (тавтологии). Эта
формула должна содержать рассмотрения всех интерпретаций, а
значит и интерпретаций с бесконечным полем.
Можно показать непротиворечивость рассмотренного исчис-
ления предикатов. Доказательство его непротиворечивости можно
свести к доказательству непротиворечивости исчисления высказы-
ваний, поставив в соответствие каждой теореме исчисления преди-
катов теорему исчисления высказываний.
Вопрос полноты (по Посту) в исчислении предикатов решает-
ся отрицательно. Существует формула
∃ x W(x) → ∀ x W(x), которая
не является теоремой, и добавление которой не нарушает непроти-
воречивости исчисления высказываний.
13
2
ОСНОВЫ
ТЕОРИИ
АЛГОРИТМОВ
Теория алгоритмов – раздел математики, изучающий теорети-
ческие возможности эффективных процедур вычисления (алгорит-
мов) и их приложения. Теория алгоритмов является крупнейшим
достижением науки XX века. Теория электронных вычислительных
машин, теория и практика программирования не могут обойтись без
нее. Кибернетика и математическая логика предъявляют на нее свои
права: во многих учебниках и справочниках отмечается, что она
входит крупным разделом в эти науки. Однако теория алгоритмов
является самостоятельной наукой и имеет собственный предмет ис-
следования.
Само название теории говорит о том, что ее предмет – алго-
ритмы. Понятие алгоритма является и очень простым, и очень слож-
ным. Его простота в многочисленности алгоритмов, с которыми мы
встречаемся повсюду, в их обыденности. Но эти же обстоятельства
делают понятие алгоритма туманным, расплывчатым, трудно под-
дающимся строгому научному определению.
2.1
Интуитивное
понятие
алгоритма
и
проблема
его
уточнения
Содержательные явления, которые привели к образованию по-
нятия «алгоритм», прослеживаются в математике в течение всего
времени ее существования. Слово «алгоритм» происходит от
algorithmi – латинской формы написания имени узбекского матема-
тика Хорезми (по-арабски: аль-Хорезми), который сформулировал
в IX веке правила четырех арифметических действий над числами в
десятичной системе счисления. В Европе совокупность этих правил
стали называть «алгоризм», «алгорифм». Затем это слово перероди-
лось в «алгоритм» и стало общим названием отдельных правил оп-
ределенного вида (и не только правил арифметических действий).
Длительное время этот термин употребляли только математики,
обозначая им правила решения различных задач.
Только в 30-е годы XX века понятие алгоритма стало объектом ма-
тематического изучения, а до этого этим понятием только пользовались.
С появлением ЭВМ понятие алгоритма получило широкую из-
вестность. Развитие ЭВМ и методов программирования способство-
14
вало уяснению того факта, что разработка алгоритмов является не-
обходимым этапом автоматизации.
Сейчас слово «алгоритм» вышло за пределы математики. Его
стали применять в самых различных областях. Под ним понимают
точно сформулированное правило, назначение которого – быть ру-
ководством для достижения необходимого результата. Иными сло-
вами, алгоритм – точно определенное правило действий (предписа-
ние, программа), для которого задано указание, как и в какой после-
довательности необходимо применять это правило к исходным дан-
ным задачи, чтобы получить ее решение. Перечислим характерные
свойства алгоритма.
1.
Дискретность. Алгоритм описывает процесс последователього
построения величин, идущий в дискретном времени. Необходи-
мый для вычисления интервал времени разбит на малые отрезки
– такты. Система величин в конце каждого такта получается в
результате осуществления элементарного шага алгоритма из
системы величин, имеющейся к началу такта.
2.
Определенность (детерминированность). Программа преобра-
зований в каждом такте однозначно определена.
3.
Результативность (направленность). Алгоритм направлен на
получение определенного результата. В частности, если вычис-
ляемая функция в данном такте не определена, совокупность
правил определяет, что нужно считать результатом применения
алгоритма.
4.
Массовость. Исходные величины могут варьироваться в из-
вестных пределах. Алгоритм служит для решения не одной кон-
кретной задачи, а целого класса задач.
Эти свойства алгоритмов являются эмпирическими, подмечен-
ными для всех известных алгоритмов. Рассмотренное понятие алго-
ритма, даже подкрепленное перечислением данных свойств, нельзя
считать математически строгим. Его называют непосредственным,
или интуитивным, понятием алгоритма, оно лишь объясняет смысл
слова «алгоритм», но не определяет, что следует понимать под «пра-
вилом действия».
На протяжении длительного времени интуитивное понятие ал-
горитма в своей основе не изменялось, хотя и приобретало все
большую выразительность. Математики удовлетворялись его со-
держательным пониманием, поскольку этот термин рассматривался
15
только в связи с построением конкретных алгоритмов и в положи-
тельных высказываниях, типа «для решения таких-то задач имеется
алгоритм и вот в чем он состоит». Теоремы о несуществовании ал-
горитма не могли быть доказаны в силу нечеткости интуитивного
определения. Как уже отмечалось, только в 30-х годах XX века воз-
никла необходимость в рассмотрении общих способов формализа-
ции задач и процессов их решения, в уточнении понятия алгоритма
как объекта математической теории. Эта необходимость возникла в
связи с вопросом обоснования математики и с развитием вычисли-
тельной математики и вычислительной техники.
К настоящему времени разработаны теории, ведущие к уточне-
нию понятия алгоритма. Основанием для одного из уточнений слу-
жит теория рекурсивных функций, другие уточнения связаны с по-
нятиями машин Тьюринга и нормального алгоритма Маркова. Эти
теории иногда называют традиционными теориями алгоритмов и не
без основания, так как в связи с бурным развитием теории алгорит-
мов упомянутые теории уже стали классикой. Далее будут последо-
вательно изложены основы данных теорий, каждая из которых
уточняет понятие алгоритма. Но предварительно заметим, что уточ-
нение распространяется не на все алгоритмы, а лишь на узкое их
семейство. Можно сказать, что каждая теория является теорией не-
которых избранных алгоритмов. Избранные алгоритмы каждого
вида пригодны для решения ряда теоретических вопросов.
Доказано, что в теоретическом отношении все рассмотренные
теории эквивалентны, т.е. научные результаты, полученные с помо-
щью алгоритмов, изученных в какой-либо из этих теорий, могут
быть также получены с помощью алгоритмов, изученных в любой
другой. Тем не менее, отказаться от одной из них в пользу другой
теории нельзя, поскольку в одних случаях легче получить результат
с помощью алгоритмов одного класса, а в других – с помощью алго-
ритмов другого класса. Связь каждой теории избранных алгоритмов
со всеми остальными алгоритмами осуществляется с помощью ос-
новных тезисов теорий. Но основной тезис позволяет выявлять слу-
чаи невозможности алгоритмов, однако ничего не дает нам, если
требуется получить хороший, удобный для практики алгоритм. Кро-
ме того, нужно иметь в виду, что основной тезис каждой теории из-
бранных алгоритмов является лишь очень вероятной гипотезой, а не
строгой теоремой.