14.Рекомендованная литература

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

2. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

3. Мендельсон Э. Введение в математическую логику. М.: Наука, 1971.

4. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1984.

5. Гордеев Э.Н. Задачи выбора и их решение. – Сб. «Компьютер и задачи выбора. М.: Наука, 1989.

6. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений.М: МФТИ, 2007.

7. Лупанов О.Б. Курс лекций по дискретной математике. - Конспект лекций. МГУ.

8. Гергель В.П., Фурсов В.А. Лекции по параллельным вычислениям. -Самара: СГАУ, 2009.

9. Ladner R.E. On the structure of polynomialen time reducibility.- J. Assoc. Comput. Mach. 1975, v. 22, p. 155-171.

10. Параллельные вычисленияВ учебном курсе рассмотрены следующие основные вопросы: архитектура параллельных вычислительных систем; программирование параллельных вычислительных систем; параллельные численные методы для решения основных классов вычислительных задач. Разработчик курса: д.ф.-м.н. проф. Карпенко А.П. http://bigor.bmstu.ru/

Наибольшее распространение в системах искусственного интеллекта получила формальная система, носящая название исчисления предикатов первого порядка (ИППП).

Алфавит ИППП состоит из:

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

• предметных констант , , , ... (для их обозначения используются строчные буквы из начала латинского алфавита);

• -местных предикатных букв , , (для их обозначения используются прописные буквы из середины латинского алфавита);

• -местных функциональных букв , , (для их обозначения используются строчные буквы из середины латинского алфавита);

• знаков связок: (коньюнкция), (дизъюнкция), (отрицание), (импликация);

• кванторов общности и существования ;

• круглых скобок и запятой.

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

1. Терм:

   • всякая предметная переменная и константа является термом;

   • если — функциональная буква и — термы, то — также терм.

2. Формула:

   • если — предикатная буква и — термы, то — элементарная формула (атом), являющаяся частным случаем правильно построенной формулы (п.п.ф.);

   • если и — п.п.ф., а — предметная переменная, то , , , , и — также п.п.ф..

Элементарная формула (атом) и ее отрицание называются литералами (соответственно, положительным и отрицательным).

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

Формула называется замкнутой, если она не содержит свободных переменных.

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

Рассматриваемое исчисление предикатов является исчислением первого порядка, поскольку в нем допустимы кванторы лишь по переменным (в исчислении второго порядка — дополнительно по предикатным и функциональным буквам).

Пример 1

Несколько правильно построенных формул ИППП:

• 

• 

• 

• 

Из всех представленных формул только третья является замкнутой.

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

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

• ( )

• 

• 

• 

• 

• 

• 

• 

• 

• 

• 

• 

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

Примечание 1

Фомулы и , а также и эквивалентны, т.е. являются синонимами.

Примечание 2

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

Примечание 3

Аксиомы ИППП совпадают с аксиомами исчисления высказываний.

В ИППП используются следующие правила вывода.

• Правило заключения (modus ponens): (если и являются выводимыми формулами, то — выводимая формула).

• Правило обобщения (правило -введения) где содержит свободное вхождение переменной , а их не содержит.

• Правило введения квантора существования (правило -введения) при тех же требованиях к и , что и в предыдущем правиле.

Примечание 4

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

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

Двумя полезными правилами-"метатеоремами" являются представленные ниже.

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

Доказательство:

• а) (по условию).

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

• в) (результат применения правила заключения к формулам а и б).

• г) (правило обобщения к формуле в).

• д) (правило заключения к формуле г при учете доказуемости ).

• е) (правило заключения к д и аксиоме ).

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

Доказательство для правила-"метатеоремы" :

• а) (по условию).

• б) (аксиома A11).

• в) (правило обобщения к б).

• г) (правило заключения к а и в).