Ш.И._Галиев_МЛ_и_ТА_2004
.pdfМинискрсгааобразованияРоссяйскоЯ Фесгропии
КЛ1АНСККЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ нм, А.Н.ТУПОЛКИА
III. И. ГАЛИЕВ
МАТЕМАТИЧЕСКАЯ ЛОГИКА
И ТЕОРИЯ АЛГОРИТМОВ
Учебное пособие
Дояущгчо ШОеу/os м^/йяе/хитеиккат'штешмтаиу
УДК 510.61(075.8)
Галиеа 111. И. Математическая логика и тмрия алгоритмов: Учебно; пособие. Кааань: Иед-во Казан, гос. техи ун-та им. А. Н. Туполева, 20П4. 334 с.
ISBN 5-7579-0778-9
Ил. 15. Табл.2. Библиагр.: 31 назв.
Рецензенты: кафедра информационных технологий и кафедра матема тики (ГИСБИ); ДОКТ. фнз -мат. наук И. 3. Батыршин (Казанский госу
дарственный технологический университет); докт. фнь-мат. наук Ф. Г. Мухлксов (Казанский госу дарственный педагогический университет)
ISBN 5-7579-0778-9 |
© Иэд-по Казан, гос. тсхн. ун-та, 2004 |
|
©Щ-Й. Галиео,2004 |
|
ОГЛАВЛЕНИЕ |
|
|
Введение ....................................... ....... ...................... |
|
8 |
|
Глава 1. Логика высказываний .................................. |
|
11 |
|
§ |
1, Высказывание. Логические операции ............ |
И |
|
§ |
2. Пропо5шшонал1.нь!8 буквы, связи» и формы |
|
|
|
(фирмулылогихи высказываний)..................... |
|
17 |
§ |
3. Упрощения в чипчсях пропозициональных |
|
|
|
форм ............................................................. |
|
20 |
§ |
4, Тавтологии (общезначимые формулы). Проти |
|
|
|
воречия ......................................................... |
|
21 |
§ 2. Равносильность пропозициональных форм .... |
24 |
||
§ |
6. Важнейшие пары равносильных пропозицио |
|
|
|
нальных фори ............................................... |
|
26 |
§ |
7. Зависимости между пропозициональными |
|
|
|
связками ................. |
... |
28 |
| |
8. Нормальные формы ......................................... |
|
31 |
§ |
9. Совершенные нормальные формы |
............... |
34 |
§ 10. Вопросы итемы для самопроверки ................. |
37 |
||
§ 11.Упражнении ................................ |
,.................. |
38 |
|
Глава 2. Логика предикатов ........................................ |
|
46 |
|
§ |
I. Понятие преднкяга ........................................ |
|
46 |
§ |
2. Кванторы ................ ......................... |
............ |
49 |
§ |
3. Формулы логики предикатов ............ |
.......... |
53 |
§ |
4. Интерпретация. Модель ................................ |
|
56 |
§ 5. Свойства формул вданной интерпретации .... |
59 |
||
§ |
б. Логически общезначимые формулы. Выпол |
|
|
нимые и равносильные формулы ................... |
60 |
5 |
7. Правила перенесения отрицания через |
|
|
кванторы ........................................................ |
S3 |
§ |
8. Правила перестановки кванторов .................. |
(56 |
§ |
9. Правила переименования связанных перемен |
|
|
ных ................................................................. |
68 |
§ 10. Правила вынесения кванторов за скобки. |
|
|
|
Приваренная нормальная форма .................. |
70 |
§ П.Вопросыитеыыдшасамопрпберки ............... |
76 |
|
§ 12. Упражнения ................................................... |
77 |
|
Глава 3. Логическое следствие и метод резолюций .... |
89 |
|
§ 1. Логическое следствие и проблема дедукции |
|
|
|
в логике высказываний ................................... |
89 |
§ |
2. Резольвента дятмокктов логики выска |
|
|
зываний ..................................... .................... |
92 |
§ |
3. Метод резолюции |
93 |
§ |
4. Метод насищеяш |
94 |
| |
5. Стратегия вычеркиплтшп ................................ |
96 |
§ |
б. Яок-резолюция ............................................... |
98 |
9 |
7. Мекщрезолюции, |
100 |
§ |
8. Преобразование фипми i ипгики шштимтон |
|
1 |
Скслемовска* стандартная форма................... |
102 |
9. Унификация................................................... |
107 |
|
§ 10. Метод резолюций в логике ггредикатоя ......... |
110 |
|
§ П . Приложение метола резолюцийляа анализа |
|
|
|
силлогизмов Ариетогела ................... ............ |
ИЗ |
§ 12. Использование метода резолюций а языке |
|
|
|
ПРОЛОГ ....................................................... |
117 |
§ 13. Вгедакке ииспользование правил вКЮЛОГе... |
121 |
|
§ 14. Рекурсивное задание правил вПРОЛОГе ..... |
123 |
|
4
§15 Вопросыи темы для самопроверки ............... |
128 |
|
§ 16. Упражнения ................................................. |
130 |
|
Глава 4. Дедуктивные теория ................................... |
135 |
|
§ |
1. Понятие со эффективных ипелуэффектнвных |
|
|
процессах (методах) ...................................... |
135 |
§ |
2. Дедуктивные теории ................................... |
137 |
5 |
3 СвсИствадедуктивныхтеории ...................... |
:39 |
| |
4. Пример полуформальной аксиоматическом |
|
|
теории-геометрия ...................................... |
141 |
§ |
5. Формальные аксиоматические теории ........... |
146 |
§ |
6. Свойстпа выводимости ................................ |
147 |
5 |
7.Исчислениевысхагывпний(теория!) ......... |
149 |
§ |
8. Некоторыетеоремыисчислениявысказываний,.. |
150 |
S, 9. Два определения непротиворечивости........... |
154 |
|
§ 10. Производные (доказуемые) правила вывода в |
|
|
|
исчислении высказываний ........................ |
156 |
§ U. Спойспъа исчисления высказываний ............. |
158 |
|
§ 12. Другие аксиоматизации исчисления выска- |
|
|
§ 13. Теорий первого порядка .............................. |
168 |
|
§ 14. Формальная арифметика (теорииSi .............. |
[/и |
|
§ 15. Свойства теорий первого порядка ................ |
|73 |
|
§ 17. Теориа естественного вывода ...................... |
i >9 |
|
5 |
19.Упражнения ............. .................................. |
is<i |
§ |
1.Тречзкачныелогикн .................................... |
is/ |
§ |
2. МкОгоэначныелогнки .................................. |
|'П |
4 3 Понятненечеткогоподмножсйтва ................. |
194 |
|
§ |
4. Нечеткие высказывания и млксииннные |
|
|
операции ней нами ........................ ................ |
2 0 1 |
§ |
5. Понятиео нечеткой лингвистическойлогике.... |
|
205 |
§ |
6 Модальные логики ........................................ |
|
208 |
§ |
7. Временные (темпоральные) логики ................ |
|
212 |
| |
8. Вопросы и темы для самопроверки ............. |
|
213 |
§ |
9. Упражнения ................................................... |
|
2! 4 |
Глава 6. Творив алгоритмов ................... ................ . |
|
217 |
|
| |
1. Неформальное понятие алгоритма ................. |
|
217 |
3 |
2. Алфавит, слова, алгоритм в алфавите. Вполне |
|
|
|
эквивалентные алгоритмы ............................. |
|
210 |
§ |
3. Нормальный алгоритм (алгоритмА.А.Марко |
|
|
|
ва) ................................................................. |
|
220 |
§ |
4. Функции частично вычислимые и вычисли |
|
|
|
мые поМаркову ........................................ |
|
225 |
§ |
5. Забывание, распространении нормального |
|
|
|
алгоритма ..................................................... |
|
226 |
§ |
6. Операции над нормальными алгоритмами..... |
|
228 |
§ |
7. Машина Тьюринга ........................................ |
|
234 |
§ |
8. Задание машины Тьюринга .................... |
- |
-36 |
|
поТьюрит-у ................................................. |
|
238 |
§ 10. Связь между машинами Тыориига и нормаль |
|
||
|
ными алгоритмами......................................... |
|
239 |
§11. Основная гипотеза теории алгоритмов (прин |
|
||
|
цип нормализации или тезис Черча) ............ |
|
244 |
§ 12. Ироблемаалгсришическойнерщрешимоста...... |
|
245 |
|
§ 13. Примеры ачгордамичеикн неразрешимых |
|
|
|
|
массовых проблем ......................................... |
|
248 |
§ J4. Сведения любого преобразования слов в алфа |
|
||
|
вите к вычислению значений целочисленных |
|
|
|
функция ........................................................ |
|
251 |
§ 15, Примитивно рекурсивные и общерекурсив |
|
|
|
|
ные функции ................................................. |
|
253 |
§ 16. 11римитивно-рекурсивкость некоторых функ |
|
|
|
|
ций. Чао ично рекурсивные функции........... |
|
256 |
§ 17. Ламбда-исчислсние............ .......................... |
|
259 |
|
§ 18. Основные результаты......................... .......... |
|
263 |
|
§ 19. Вопросы и темы для самопроверки ................ |
|
264 |
|
<$20. Упражнении ........................................... ....... |
. |
265 |
|
Глава 7. Слижнисть нычислеина с помощью |
|
|
|
|
алгоритмов |
|
276 |
§ |
1. Понятие о сложностивычислений ................ |
|
276 |
§ |
2. Временная слокноС1ь иычислсний(алгоритма).. |
|
279 |
§ |
3. Полиномиальные алгоритмы и чнничи. |
|
|
|
Класс Я ........................................................... |
|
281 |
§ |
4. N1'- класс ................... |
., |
2*5 |
§ |
5. МР.лолйыеиЛР-трудш |
. |
289 |
§ |
6. Класс Я ...................... |
.. |
290 |
Л |
7. Емкос|-на*(ленточная) сложностьалгоритма...... |
|
292 |
§ |
8. Вопросы и «мы для самопроверки .............. |
|
293 |
§ |
9. Упражнении ................................................... |
|
294 |
Приложение ............ |
|
2«6 |
|
Варианты типового задания ............................ ...... |
|
296 |
|
Тесты для самоконтроля ........................................ |
|
314 |
|
|
Тест 1. Логика высказывании.............................. |
|
315 |
|
Тест 2. Логика препнкатов.................................. |
|
316 |
|
ТестЗ. Логическоеследствие и метод резолюций... |
318 |
|
|
Тест 4. Дедуктивные теории .............................. |
|
320 |
|
Тест 5. Теория алгортмов ............................... |
|
324 |
|
Тест 6. Нсклассические логики и сложность вы |
|
|
|
числений ............ ............................................... |
|
327 |
Отлеты к тестам сямоконгроля .............................. |
|
331 |
|
Список литературы ........................................... ....... |
|
332 |
|
Введение
Логика обычно понимается как наука о способах доказательств и опровержений. Математическая логика - это логика, развийаош с помощью математическихметодов,
Изуча» методы доказательств и опровержении, логика интересуетм 8 первую очередь формой получение истинны* выводов, a нв содержанием посылок и чакшочений в том или ином рассужде нии, Рассмотрим, например, следующие два вывода:
I Все люди cnejmtu. Сократ - человек. Следовательно, Сократсмертен.
2. Все котm любят играть. Мурка - котенок. Следовательно, Муркалюбит играть.
Об» эти выводяимеют однуи ту же форму: ВсеА суть В; Сесть А; следовательно, С есть В. Эти выводы верны в силу своей формы, независимо от содержания и от того,мсгинкы щи ложны взятые сани па ceSe посылки и заключения Систематическая формализация и ка талогизация правильных способов рассуждений - одна из основных задач логики. Если при этом применяется матештическнй аппарат и исследований посвящены в первую очередь тучекию математиче ских рассуждений, то эта логика является математической логикой (формальной логикой). Данное определение не шяется строгим (точ ным) определением. Чтобы понять предмет и метод математической логики, лучше всего приються за ее изучение.
Математическая логика начала формироваться давно. Зарожде ние ее идей и методов происходило в Древней Греции, Древней Индии и Древнем Китае примерно с V! в. до и. э. Уже в этот период
ученые га.ггались расположить цепь математических доказательств в такую цепочку, чтобы переход от энного звена к другому не остав лял сомнений и завоевал всеобще: придание. Уже в самых ранних дошедших до пас рукописи «канон» математического стили изложе ния прочно установлен. Впоследствии он получает окончательное завершение у велики* классиков: Аристотеля, Еоклидэ. Архимеда. Понятие доказательства у тгих авторов уже ничем не отличается
Логика как сямсстпятельна» яяуяя берет свое начало в иссле дованиях Аристотели (384322 г. до н. >.). Вслтчй философ древно сти Аристотель осуществляй' энциклопедическую систсматиацию ытпных знаний во псих области существовавшей тогда науки. Логические исследований Аристогая изложены, в основном, в двух его трудах «11ервая яяалкшк» и «Вторая аниптгиЕа», объединение под общим ншакием «Органон».
Следует особо ответить большое значение для становления и развития математической логики одного из самых блестящих достижений в истории человечества, а именно, превращение геомет рии в точную дедуктивную систему в работе Евклида (330 - 275 г. до я. э.) - «Начала». Именно этот дезукгивный подкад с ясным осп* накием целей и методов был положенв основу развития философской и математической мыслипоследующихстолетий.
Также большое значение для становления и развития логики сыграли достижения в алгебре (алгебра Буля) и в других математиче ских дисциплинах, в той числа и вновь в геометрии (создание неевк лидовой геометрии - геометрии Лсбачсвсксп-о-Гаусса- Бойяи). Краткийобзорстановленияматематическойлогикимсииюнаотив [б].
В формировании и становлении математической логики участаовали многие н многие ученые как дреангос времся, так средневеко вья и последующих времен.
Принципиальное значение ммематаческой ;н |
- обоснова- |
математики(анализ основ математики). |
|
Прикладное значение математической логики я настоящей вре мя аче-кьвелико. Математическая логика применяется для следующих
•анализа и синтеза цифровых вычислительных машин и других дискретных автоматов, в том числе и интеллектуальных систем,
•анализа и синтеза формальных и машинных языков, для ана-
• анализа и формализации интуитивного понятия вычисли-
•выяснения существовании механических процедур для реше ния задач определенного типа;
•анализа проблем сложности вычислений.
Также математическая логика оказалась тесно связанной и с pj • дач вопросов лингвистики, экономики, психологии и философии.
8 данном пособии излагаются основные понятая математиче ский логики и корни алгоритмов. Материал, изложенный в пособии, соответствует государственному образовательному стандарту для на правления «Информатика и вычислетелкная техника» и может быть нсполыован для студентов, обучающихся по разным специальности этого направления.
При написании носабня использовалась литература [1-31J, и, конечно, - другие источники, В прилагаемый список литературы включены книги, которые желательно просмотреть любознательному
итребовательному студенту.
Впособии в каждой главе приведены вопросы и темы ллй са мопроверки теоретического материала к упражнения, предназначен ные для вырабптхи навыков решения задач и углубления знаний
самоконтроля усвоения материала.
Автор выражает благодарность профессору И. 3. Качыршнну за полезные предложения и замечания, которые позволили улучшить работу, профессорам Ф. I'. Мухлисову и А. К. Шалябанову, доцентам JI. Г. Амбарцумову, А. II. ЕСозину, А. И. Белоусову и С. А. Ллшевой за вндашше к работе н полезные замечания.
Автор признателенсвоимстудентамзапомощь по наборутевпа.