Ш.И._Галиев_МЛ_и_ТА_2004

Пусть заданы две дедуктивные теорииЯ, иЯ3,такие что:

II алфавит теории В содержится в алфавитетеории В2 или эти

алфавиты совпадают; 2) каждая формула из В яапяетсн формулой т В2,

5) кавда» теорема из 2| является теорем™ вS;

При выполнении этих условий гсварат, что теория й; является расширением теории Зь

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

революцией в облости 'ianwpiewoii мыску, ктую только

§ 4. Пример полуформальной аксиоматической теории -

геометрия

Согласно § 2 полуформальная аксиоматическая тадриг считает­ ся ЯШвкой, если задан .язык этпй теории и из мжясества предложе­ ний (формул) этого языка выделено 'голмвожестяомножество акси­ ом. Таким образом, полуформальная аксиоматическая теория (теория В) считается заданной, если:

И1

1)заданы алфавит А (алфавиттеории В) и правила образования выражений (слов) теории в;

2)заданы правила образования правильна построенных выра­ жений (формул) теории В;

3)ип мнтокеезяа правильно построенных выражений выделяется некоторое подмножествомножество аксиомтеории S.

В настоящее время многие математические теории сгроатсн (задаются) в виде полуформальных аксиоматических теорий. Однако при этом построение их не доводится до того вида, какого требуют пп.1) - 3). Во многих случаях алфавит не перечисляется, кроме того, не задаются правил» образования слов и правильно построенных вьь ражеиий, а считается, что мы в состоянии отличите, яьтзетея ли про­

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

основании равны" отнесем к правильно	Построенным выражениям
геометрии, а "треугольник - зеленый"	к таковым ие отнесем, хотя

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

Прежде чем задать геометрию в виде полуформальной аксиома­ тической теории, нужно отметитьследующее.

Гиомстрия вначале развивалась как эмпирическая няукаив ран­ ний периоддостигла особо высокого уровня разами* в Египте. В пер­ вом тысячелетни да н. э. греческие геомелры на только обогатили геометрию многочисленными новыми фактами, но к предприняли такжг серьезные шагик строгому ее логическому обоснованию.

Многовековая работа гречески* геометров за этот период была подытожена исистематизирована Бвигадом (330-275 тт. до н. э.) в «та знаменательном труде "Начала". На протяжении более чем 20 веков

142

"Начал»" Евклиэл служили образном ясного и строгого изложения. Кризис основ математики, в частности, и создание неевклидовых гео­ метрий вынудили пересмотреть основы ггометрни и отказаться at по­ нятия аксиомы как самоочевидной истины. Выяснилось, что интуиция во многих случаях может "подводить", приводить к неприятноегям (противоречиям), Поэтому пришлось, по возможности, отказаться от попыток обращения к интуиции при построении геометрии и ввести как ахеиомы все свойства и "очевидные" положения, которые Еаклид использовал в геометрии, но не вводил их в постулаты и аксиомы. Доведение строгости геометрии до некоторых современных понятий строгости было завершено а работах Паша (1882г.) и Гильберта (1899г.).

В настоящее время имеются различные редакции задания гео­ метрии. Введем задание геометрии (аксиомашку Гильберта) согласно работа [11]. Геометрии считаете» чеканной, если:

чаются через А,Ъ,С.....,А\, Лг,.... йь	С]. С*...;
б) элгменты второго множества насыпаются прямыми и обозна­
чаются через а, Ь,с,.., а,, а*,,, Ь,, fci .,	Ст,. ;
в) элементы третьего множества		называются плоскостями
и обозначаются черет 0,3 ,у,...,, а а ь ..., р„		ц,

пространством. На множестве точек, прямых н плоскостей введены отношения, обозначаемые словом "лежат”, ’'меэкду" и "конгруэнтно".

последовательность выражений правильно построенным выражением

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

"лежат" "между" и "конгруэотно" - любые отношения между объек-

Будгм употреблять такие термины как "отрезок", "прямая", "приходит», через точку" ит.п., не вводя их определений. Считаем, что чот*1*л1.этосделаетсаи,либо обратятся к курсу геометрии.

Теперь зададим аксиомы. Ное аксиомы подразделяются яа

Порвав группа - аксиомы связи.

1.Каковыбы ни были днеточкиЛ, В, существует прямая а, прочадящая через каждую източек А, Я.

2.Каковы бы ни были две различные точки А, й, существует неболееодной прямой, которая проходитчерез каждую източекA S.

3.На каждой прямой л о т , по крайк:Я м«ре, две точки. Сущест­ вуют, по крайней мере, триточки, не лежащие наодной прямой.

4.Каковы бы ни были три точки А, В. С, ж лежащие на одной

прямой, существует плоскость о , проходящая через каждую го трех точекЛ, Д С.Нв каждойплоскости лежит хотя бы однатечка.

5.Каковы бы ни были три точки А, В, С, не лежащие на одной прямой, существует не более одной плоскости, которая прохода через каждую нзтрех точекА, В, С.

6.Если дае точки А, В прямойа лежат на плоскости о , то к.тадяиточка прямой а лежит на плоскостяа .

7.Если две плоскости а, (5 имеют общуютечкуА, то они имеют еще, по крайней мере, одну общуютечкуВ.

8.Существуют, по крайней мере, четыре точки, не лежащие водной плоскости.

Вторая группа—шгатчы порядка.

Если точки В лежит между точкойЛ и точкой С, то А, В, С- различныеточки одной пряиойЛ иточкв Ялежиттакже между С иА 2. Каковы бы ни были точки А а С, существует, но кра

мере, однаточка В на прпюойАС такая, чтоС лежитмеждуА и В.

144

3.Среда любых трех точек прямой существует не более одной точки, лежащей между двумя другими.

4.Аксиома Паша. Пусть А, В, 0' - три точки, не лежащие на од­ ной прямой, и а - некоторая прямая в плоскостиЛЛС, не содержащая ни одетой из точек А. В, С. Тогда, если прямая и проходит через точку

отрезка АВ, -го ока нрпходиг также либо через точку отрезкаАС, либо через точку отрезка ВС.

Кроме 'лих групп вксяом, задается еще третья группа-аксиомы котружтчосши (5 аксиом), четвертая группа - аксиомы непрерывно­ сти (2 аксночы) и пятая группа - аксиома траазелъносш. Здесь ке приволятм все STH аксиомы, ибо ваша цель - не изучение геомет­ рии, я толыо рассмотрение, каким образом (методом) задается геометрия.

Однако все же приведен аксиому параллельности как для евклидовой ггометрии (аксиома Евклида), так и ала неевклидовой геометрии (аксиоча Лобачевского).

Аксиома ЕеклиОа. Пусть а - произвольная прямая и А - точка, лежащая пне прямой и, тогда в плоскости, определенной точкой А и прямой а, можно провести не более одной прямой, проходящей че|>ез А и не пересекающей а.

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

Если примам первые четырегруппы аксиом и аксиому Евклида, то получим евклмову геометрию.

Если примем первые четыре группы аксиом и аксиому Лобачев­ ского, то получимнеевклидову геометрию(геометриюЛобачевского - Бойяи-Гаусса).

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

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

Q матемагической практике аксиоматические теории обычно описываются, как и геометрии, в виде полуформальных теорий и предполагается, что логика, используемая в ЭТОЙ теории, есть та интуитивна» логика, которая усваивается входе «учения математики.

§ S. Формальные аксиоматические теории

Как уж» известно, формальнаяаксиоматическая теория В ечига-

1.Задано некоторое множество символов - алфавит теории В. Конечная последовательность бука алфавита называется выражением теории. Алфявит, екелоьательио, и выражения теории задаются эффегавным йбрязом.

2.Задави формулы теории В как некоторое подмножество выражений теории. Формулы тоже обычно эадштен эффективным образом.

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

4. Задано конечное число правил выводя Д„ Я2,..., согласно каждому из которых некоторая формула, именуемая непосредствен­ ным следствием (заключением), непосредственно выводима из неко­ торого конечного множества формул, называемых ппешхами. При эгом чля каждогоД существует целоеположительноек чакое, что для

146

каждого множества, сг,стоящего из к формул, и каждой формулы А эффективна решается вопрос о том, ав'вется лиА непосредственным

Выводам в В называется всякая последовательность А], Аъ- .уЛ, формул, такая что для каждого ( (1< г < и) формула^, есть либо ак­ сиома теории В, либо непосредственной следствие каких-либо преды­ дущих фирмул эюй послсцозатгльнаош по одниму ю правил иывода.

Формула А течрии В называется теоремой теории В, если существует вывод в В, в котором последней формулой является Л, такой выводназывается выводом фюрмуиы

Формула А называется,c.wcmeirtui в В множества формул G тогда и топью» тогда, когда сушествубт такал последовательность формул А\, А», что Ан-А и дла любого i А, есть либо аксиома, либо элемент О, либо непосредственное следствие некоторых преды­ дущие формул этой последовательности по одному из правил вывода. Такая последовательность называется еаеодом А И2 С. Элементы G

утверждения яА есть следствие Сч будем употрвбл'гть запись: С\-А . Например, сели 0 =(81,87,.,.В,,}, то будем писать

Нетрудно видеть, что если G есть пустое множество, т. е. G =<Z, то 0 (-А имеет место тогда и только тогда, когда А является теоре­ мой. Вместо 0 \-А принято писать просто \-А, что читается: «фор­ мула А является теоремой» Чтобы дабежвп. пуготщм там, где будут рассматриваться не одна, а иегкодько теорий, употребляют запись:

в [А и \-А,

ВВ

указывая индексом В нато, о какойтеории идет речь.

§ б. Свойства выводимости

11усть О - некоторое множество формул дгннойтеории, А, В и С - произвольные формулы той же теории, Рассмотрим некоторые свойства выводимости в формальных аксиоматических теориях,

1. Если G солоркится в некотором множестве форчул F и исли

G H . to F \А.
Доказательство. ПустьА имеет вывод
Л,.Л'..-Л	(4.1)

из гипотез G. Если некоторая формула А, принадлежит G, то, очевид­ но, А, £ F. Следовательно, вывод (4.1) формулы А является выводом формулы А из гипотез F. Что и требовалось доказать.

2. С \- А тогда и только тогда, когда 8 G существует конечное подмножество //такое, чти Я \-А

Доказательство следует да определения вывода.

3. Пусть С \-А и каждая форчула В, принадлежащая G, выво­ дима ял некоторого множества формул Р, тотда F \-А.

Доказательство. Пусть А имеет вмвод

(4.2) из гипотез G По определению вывода некоторые А, из (4.2) мопт принадлежать G, но каждая формула н.< G, имеет сыаод ил F. Заменим в (4.2) асе А„ принадлежащие G, выводом А, из F. В результате полу­ чим последовательность формул;

В,.£-,... В„

которая уже является выводом.4 из F. Что и требовалосьдоказать. Как частный случай п.З имеем:

З'.ЕслиЛ [В и В		[-С, то Л (-С.
4. НслиО,/)	|-В иС \-A,ioG I-В.
Доказательство. Пусть Вимеет вывод
B , , В	В,	(4.3)
из гипотезО и . а	формула/J имеет вывод
ЛуМ	А„	(4.4)

из гипотез G. В выводе (4.3) формулы В некоторые hj Э, могут быта равны А. Заменим такие Д. последовательностью (4.4). В результате получим последовательное^ формул

C,,С, С„

которая является выводом для В из пшелй G. Что и требовалось доказать.

§7. Исчисление высказываний (теория L)

Вкачестве первого примера формальной аксиоматической тео­ рии ра^смигрим исчисление высказываний - тмрию L,

положительными числами в качестве индексов: А,,А;,Аj,... Символы

i=> будем называть примитивным! связками, а А^А^, А^... -пропозн- |циокалькыии буквами.

2, Формулы теории L определиминдуктивнымобразом

1)tts буквыAi.A^

суть формулы;

2)еслиА и В формулы, то (U.) и (Л=г/!) тоже формулы;

3)выражение теории L является формулой только тош , когда |это следует ха I) и 2).

А&В служит обозначением дли формулы (1(^=>(1В))), А^В служит обозначением дли формулы ((Л)—В),

А=В служит обозначением для формулы(1((Л=»В)=»("|(йя>Л)Н). Из определенна формуя видно, что всякая формула из L есть I пропозициональная форме, построенная из пропозициональных букв

iA\,A2... с помошью связок 1 и rj>.

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

3. Аксиомы теории L. Каковы бы пи были формулы А, В и С 1теории L, следующие формулы суть аксиомы теории I:

Л1'. An(BztAy,

А2: {А=>{В=>С))Ы1А^ВУ=,{А=>С)У: Ai: (15=>1Л)=>((13-.->А)=>В).

149

Заметим, что XI - АЗ являются схемами аксиом, т.е. указывают, как строятся аксиомыдля произвольных формулА, В иС. Всилу про­ извольности формуя А, В и С едены аксиом А1-А1 порождают бес­ численное множество аксиом. Легкоубедклси, например, с помощью таблиц исткнисап, что каждая аксиома, полученная по схемам Л(-.43, являетсятавтологией.

4. Единственным правилам вшева теории L служит прави modui ponens: В есть непосредственное следствиеА и А=ьВ. Уго пра­ вило сокращеннообозначаютМР

Modus ponsm в переводе означает «правил» отделения». Оме­ там, «готеорем» 1.1 утверждает, что еслиА нЛ:эЗ тавтологии,тон Э тоже тавтологии. Следовательно, правило modusраптз изтаетологий

Очевидно, правилоМРозначает, чтоА.А=>ВУВ.

Таким образом, задали некоторую формальную аксиоматиче­ скую теорию, которая и называет» исчислением высказываний Рас­ смотрим некоторые доказательствав згойтеории.

10, чтоначатсуществуют, неоютим

Арчтотепь

§ 8, Некоторые теоремы исчисления высказываний

Проведем доказательство некоторыхтеорем исчисления выска­ зываний (теорииI).

Л е м м а 4.1. |- А=>А для любой формулы А теории L, т.е., формуле Л=>А являетсятеоремойтеории I для любой формулы

A m L

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

I) {А=,{(А.-=>А)^А))=:[{А^{А^А))^{А^А)) - является акс мо«. такка* получмяс»по схеме/2, если паложитьВ“Л:г-/( и С"Л;

ISO