Вопросы для самоконтроля

1. Дайте определение одноместного и двухместного предикатов. Приведите примеры.

2. Дайте определение тождественно истинного и тождественно ложного предикатов.

3. Что называется отрицанием предиката?

4. Как определяется конъюнкция и дизъюнкция двух предикатов?

5. Что называется областью определения и множеством истинности предиката?

6. Дайте определение импликации двух предикатов.

7. Дайте определение кванторной операции всеобщности.

8. Дайте определение кванторной операции существования.

9. Можно ли произвольно менять порядок следования кванторов в формулах? Если нет, то почему?

10. Как связана кванторная операция всеобщности с операцией конъюнкции?

11. Как связана кванторная операция существования с операцией дизъюнкции?

12. Какие выражения являются формулами логики предикатов?

13. Какие формулы логики предикатов называются равносильными?

14. Приведите две пары каких-нибудь равносильных формул.

15. Дайте определение предваренной нормальной формы.

16. Какие формулы относятся к категории выполнимых?

17. Какие формулы относятся к категории общезначимых?

4. Основные положения теории алгоритмов

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

Слово алгоритм связывают с именем среднеазиатского математика IX века аль-Хорезми в его латинском написании – algorithmi (иногда употребляется равнозначное слово алгорифм).

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

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

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

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

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

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

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

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

Несмотря на это, можно отметить некоторые характерные черты алгоритма.

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

2. Детерминированность алгоритма. Совокупность величин, получаемых в какой-то неначальный момент времени, определяется совокупностью величин, полученных в предшествующие моменты времени.

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

4. Массовость алгоритма. Начальная совокупность величин может варьироваться в бесконечных пределах.

5. Результативность алгоритма. Последовательный процесс получения совокупности величин должен быть конечным и должен давать ожидаемый результат.

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