Министерство образования и науки Российской Федерации

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

“Тобольская государственная социально-педагогическая академия

им. Д.И. Менделеева”

Валицкас А.И.

КОНСПЕКТ ЛЕКЦИЙ ПО

МАТЕМАТИЧЕСКОЙ ЛОГИКЕ

Учебно-методическое пособие для студентов

физико-математических специальностей

Рекомендовано

УМО по математике педвузов Волго-Вятского региона в

качестве учебного пособия для студентов

физико-математических специальностей высших учебных заведений

Тобольск – 2010

УДК 510.6 Печатается по решению редакционно-издательского

ББК 22.12 я 73 совета Тобольской государственной социально-

В 15 педагогической академии им. Д.И. Менделеева

Валицкас А.И. Конспект лекций по математической логике: Учебно-методическое пособие для студентов физико-математических факультетов педвузов. – Тобольск, 2010. – 185 c.

Учебно-методическое пособие представляет конспект курса лекций по математической логике, читаемого автором в течение ряда лет на математическом факультете в Тобольской государственной социально-педаго­ги­ческой академии им. Д.И. Менделеева.

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

Рецензенты:

М.А. Люстиг, кандидат педагогических наук, доцент, зав. кафедрой естественно-научных дисциплин Тобольского филиала ТюмГАСУ, г. Тобольск

В.Г. Ярков, кандидат педагогических наук, доцент, декан математичес­кого факультета ТГСПА им. Д.И. Менделеева, г. Тобольск

ISBN 978-5-85944-273-7 © Валицкас Алексей Игоревич

© ГОУ ВПО “Тобольская государственная

социально-педагогическая академия

им. Д.И. Менделеева”, 2010 г.

С О Д Е Р Ж А Н И Е

ПРЕДИСЛОВИЕ	. . . . . . . . . . . . . .	4
Глава I.	Алгебра высказываний . . . . .	5
	§ 1. Понятие высказывания . . . . . .	5
	§ 2. Язык исчисления высказываний . . . .	8
	§ 3. Истинностные значения формул . . . .	12
	§ 4. Законы логики, противоречия, выполнимые и равносильные формулы . . . . . .	18
	§ 5. Совершенные дизъюнктивная (СДНФ) и конъюнктивная (СКНФ) нормальные формы . .	25
	§ 6. Булевы функции . . . . . . . .	33
	§ 7. Логическое следование . . . . . .	43
	§ 8. Некоторые применения алгебры высказываний	47
	I. Анализ логических рассуждений . . . .	47
	II. Оптимизация логики условных переходов в программах . . . . . . . .	49
	III. Автоматизированный логический вывод формул	50
	IV. Проектирование, анализ и оптимизация релейно-контактных и больших интегральных схем	54
Глава II.	Алгебра предикатов . . . . . .	60
	§ 1. Предикаты и кванторы . . . . . .	60
	§ 2. Равносильные и тождественно истинные предикаты . . . . . . . . . .	66
	§ 3. Язык исчисления предикатов . . . .	70
	§ 4. Интерпретации формул исчисления предикатов	72
	§ 5. Предварённая и приведённая нормальные формы	79
	§ 6. О структуре современных математических теорий	83
	§ 7. Виды математических утверждений . . .	86
	§ 8. Некоторые методы доказательства теорем . .	91
Глава III.	Формальные аксиоматические теории	97
	§ 1. Формальные и неформальные аксиоматические теории . . . . . . . . . .	97
	§ 2. Непротиворечивость аксиоматических теорий .	109
	§ 3. Полнота аксиоматических теорий . . . .	112
	§ 4. Разрешимость аксиоматических теорий . .	119
	§ 5. Независимость системы аксиом теории . .	125
	§ 6^. Формальное исчисление высказываний . .	132
ПРИЛОЖЕНИЕ	ФОРМАЛЬНАЯ ТЕОРИЯ МНОЖЕСТВ . . .	146
	§ 1. Азы наивной теории множеств . . . .	146
	§ 2. Аксиоматика Цермело-Френкеля теории множеств	148
	§ 3. Формальная теория множеств: райские кущи или адские дебри ? . . . . . . .	165
ЛИТЕРАТУРА	. . . . . . . . . . . . . .	179
ПРЕДМЕТНЫЙ	УКАЗАТЕЛЬ . . . . . . . . . .	182

П Р Е Д И С Л О В И Е

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

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

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

Автор выражает благодарность всему коллективу кафедры алгебры, геометрии и ТиМОМ ТГСПА им. Д.И. Менделеева за поддержку и заинтересованность в этой работе и благодарен рецензентам, обратившим внимание на некоторые неточности и опечатки. Особая благодарность – д.ф.-м.н., профессору Е.М. Вечтомову, без участия которого этот труд не был бы завершён. Автор будет признателен всем, кто пожелает высказать любые конструктивные замечания и пожелания по тексту данного пособия.