Пономарев И.Н. Введение в математическую логику и роды структур

Подождите немного. Документ загружается.

ВНИМАНИЕ! Эта электронная версия книги содержит

исправления ошибок и опечаток, замеченных

на ДЕКАБРЬ 2009 года и ряд небольших улучшений

по сравнению с бумажной версией. И. Н. Пономарёв.

И. Н. Пономарёв

ВВЕДЕНИЕ

В МАТЕМАТИЧЕСКУЮ ЛОГИКУ

И РОДЫ СТРУКТУР

Учебное пособие

Москва

МФТИ

2007

УДК 510.6+510.22(075)

ББК 22.12я73

П56

Р е ц е н з е н т ы:

кафедра «Криптология и дискретная математика»

Московского инженерно-физического института,

доктор физ.-мат. наук, профессор Ю. Н. Павловский

Пономарёв И. Н.

П56 Введение в математическую логику и роды структур: Учеб-

ное пособие. — М.: МФТИ, 2007. — 244 с.

ISBN 5-7417-0174-4

В учебном пособии, написанном по материалам семинаров, про-

водившихся автором в Московском физико-техническом институте,

изложены элементы классической логики и аксиоматической тео-

рии множеств, а также аппарат родов структур Бурбаки. В книге

применяется стандартная (не бурбаковская) терминология и аксио-

матика логики и теории множеств, что позволяет использовать это

пособие совместно с другими учебниками.

Предназначено для студентов младших курсов факультета инно-

ваций и высоких технологий МФТИ. Пособие разработано в рамках

инновационной образовательной программы «Разработка методиче-

ского обеспечения учебного процесса» по направлению «Наукоем-

кие технологии и экономика инноваций».

УДК 510.6+510.22(075)

ББК 22.12я73

ISBN 5-7417-0174-4

○ Пономарёв И. Н., 2007

○ МФТИ, 2007

ПРЕДИСЛОВИЕ

1. Аппарат родов структур был разработан группой француз-

ских математиков под коллективным псевдонимом «Никола Бурба-

ки» в 40-х годах XX в. Цель, поставленная Бурбаки, заключалась

в создании универсального способа описания (экспликации) мате-

матических объектов средствами теории множеств. Б´ольшая часть

современных на тот момент разделов анализа, абстрактной алгеб-

ры и топологии была изложена в родах структур в многотомном

трактате Н. Бурбаки «Начала математики».

Основная идея школы концептуального анализа и проектиро-

вания заключается в использовании аппарата родов структур для

описания нематематических предметных областей. Такое описа-

ние производится в виде концептуальных схем — родов структур,

снабжённых комментариями, указывающими на соответствие меж-

ду термами и объектами описываемой предметной области. Одно

из главных приложений концептуальных методов — создание ав-

томатизированных систем управления предприятиями с использо-

ванием концептуальных схем.

Кафедра концептуального анализа и проектирования (КАиП)

Московского физико-технического института готовит специалистов

в этой области с 1991 года. Однако систематическое изложение ма-

тематического аппарата концептуальных методов до сих пор пред-

ставляет собой нерешённую задачу. Отчасти это имеет место из-за

того, что оригинальное изложение аппарата родов структур, содер-

жащееся в книге Бурбаки [15], использует специфическую терми-

нологию и аксиоматику, отличающуюся от принятой в большин-

стве современных учебников по логике и теории множеств, что се-

рьёзно затрудняет использование этой книги в учебном процессе.

Настоящая книга, основанная на семинарах, проводившихся ав-

тором на кафедре КАиП МФТИ, — первая попытка строго изло-

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

4 Предисловие

материал, придерживаясь при этом терминологии и аксиоматики

стандартных учебников, таких, как [1], [2], [5], и многих других,

что позволяет использовать её совместно с другими учебными по-

собиями.

2. Что может служить отправной точкой изложения? Студен-

ты, начинающие заниматься концептуальными методами, как пра-

вило, знакомы с понятиями и символикой математической логи-

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

ния стандартных программ высшей математики технического ву-

за. Кроме того, в нашем распоряжении имеются программные про-

дукты с функциями синтаксического и семантического контроля

родоструктурных текстов концептуальных схем. Всё это облегча-

ет освоение формального языка родов структур. Но от знакомства

с языком ещё далеко до успешной практики создания концепту-

альных схем — точно так же, как от знакомства с синтаксически-

ми конструкциями языка программирования далеко до успешного

программирования на этом языке. В процессе обучения требуется

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

множественных выражений, что невозможно без хотя бы базового

знакомства с математической логикой и теорией множеств.

Разделы книги, посвящённые логике и теории множеств, содер-

жат элементарные сведения, которые необходимы в процессе изло-

жения и обоснования аппарата концептуальных методов. Из мате-

матической логики это (глава 1): исчисления высказываний и пре-

дикатов, теоремы об их непротиворечивости и полноте, а также

материал, направленный на развитие навыков формального логи-

ческого вывода и эквивалентных преобразований логических фор-

мул. Приступая к изучению теории множеств (глава 2), мы, таким

образом, будем способны работать с теорией множеств как с ак-

сиоматической теорией, используя формальный язык и исчисле-

ние для построения доказательств теорем. Изучение отображений

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

зультаты теории множеств, связанные с мощностями и порядковы-

ми числами, но и познакомиться с целым рядом стандартных ро-

Предисловие 5

дов структур (бинарными отношениями и множествами множеств),

способами их определения и их свойствами.

Наконец, глава 3 посвящена изложению аппарата родов струк-

тур. Затрагиваются вопросы синтаксиса биективно переносимых

термов и формул, приводятся примеры родов структур и их ин-

терпретаций, описываются вывод структур и операции над родами

структур. Сведения глав 1 и 2 существенным образом используют-

ся для обоснования результатов главы 3.

Текст книги снабжён упражнениями для самоконтроля. Мно-

гие из них были заимствованы из других книг — в этих случаях

за номером задачи следует библиографическая ссылка.

3. На протяжении всего текста, если не оговаривается особо,

используются следующие обозначения:

1) заглавные буквы латинского алфавита обозначают знакосо-

четания формального языка, имеющие характер высказыва-

ний или утверждений (формулы);

2) буквы Γ,