Применение логiки предикатiв

Исчисление предикатiв, не какое мiстить функцiональних букв i предметных констант, называется Чистым исчислением предикатiв. Досi речь шла преимущественно именно о чистом исчислении предикатiв. Такi исчисления мiстять тiльки означенi выше так званi Логiчнi аксiоми или схемы аксiом.

Прикладнi исчисления теорiї первого порядка характеризуются тем, что в них к логiчних аксiом добавляются власнi Спецiальнi Аксiоми, в которых определяют властивостi конкретных iндивiдуальних предикатних букв i предметных констант из определенной предметной областi.

Найтиповiшi примеры iндивiдуальних предикатних букв - предикаты = рiвностi i, порядку, а функцiональних букв - знаки арифметических операцiй +, -, / и тому подобное и iнших популярных математических функцiй. Как предметнi областi найчастiше выступают множество N натуральных чисел, множество Z цiлих чисел, множество R дiйсних чисел, булеан b A некоторого множества A но iн.

Бiльшiсть прикладных исчислений мiстить Предикат рiвностi = i аксiоми, что его определяют. Например, аксiомами для рiвностi могут быть такi:

E1. X X= X

E2. X= Y F X, X F X, Y,

Где F X, Y получено из F X, X путем замiни некоторых не обязательно всiх воджень X на Y при условии, что Y в этих вхождениях также остается вiльним.

Любая теорiя, в якiй E1 i E2 есть аксiомами или теоремами, называется Теорiєю или Исчислением Из рiвнiстю.

Из аксiом E1 i E2 нетрудно вывести теоремы, которые описывают основнi властивостi рiвностi, - рефлексивнiсть, симетричнiсть i транзитивнiсть:

T T= T

X= Y Y= X

X= Y Y= Z X= Z.

Аналогiчно могут быть введенi три аксiоми, что задают бiльш общий предикат - Предикат еквiвалентностi E X, Y:

Q1. XE X, X

Q2. X Y E X, Y E Y, X

Q3. X Y Z E X, Y E Y, Z E X, Y.

Iншим прикладным исчислением является Теорiя частичного порядка, какая мiстить три конкретнi аксiоми для предиката,:

O1. X X, X

O2. X Y X, Y Y, X X= Y

O3. X Y Z X, Y Y, Z X, Z.

Присоединив к этих аксiом аксiому

O4. X Y X, Y Y, X X= Y,

Дiстанемо Теорiю лiнiйного строгого порядка.

Еще одна аксiома Аксiома щiльностi

O5. X Y X, Y$ Z X, Z Z, Y

Формалiзує вiдношення лiнiйного строгого порядка в щiльних множествах см. роздiл 1.8, например, в множинi рацiональних или множинi дiйсних чисел.

Найбiльш дослiдженою на сьогоднi формальной теорiєю, какая вiдiграє определяющую роль для аналiзу проблемы обоснования принципов математики, есть так называемая Формальная арифметика [......].

В формальнiй арифметицi используют три функцiональнi буквы +, . Также одна предикатна буква - символ бiнарного предиката рiвностi = i одна предметная константа 0.

Девять схем спецiальних аксiом задают основнi законы формальной арифметики.

A1. F0 X F X F X F X Принцип iндукцiї

A2. T1 = T2 T1= T2

A3. T1 =0

A4. T1= T2 T1= T3 T2= T3

A5. T1= T2 T1 = T2

A6. T1+0= T1

A7. T1+ T2 = T1+ T2

A8. T10=0

A9. T1 T2 = T1 T2+ T1.

Заметим, что формальная арифметика допускает так называемую Стандартную iнтерпретацiю, в якiй символ = отождествляется зi привычным знаком рiвностi, 0 - с числом нуль, + i - с традицiйними знаками арифметических бинарных операцiй добавления i умножения, а - с унарной операцiєю "непосредственно слiдує за". Такая iнтерпретацiя отвечает привычной содержательной арифметике. Каждый терм вiдповiдає некоторому натуральному числу, а формула - утверждению об определенную властивiсть натуральных чисел или числовых змiнних.

Ретельнi дослiдження формальной арифметики позволили выдающемуся австрiйському математику i логiку Курту Гьоделю i его послiдовникам получить в 30-х годах ХХ столiття фундаментальнi результаты в галузi реалiзацiї задекларированной на межi ХIХ i ХХ столiть iншим выдающимся математиком Давидом Гiльбертом программы формального обоснования математики. Двi славные Теоремы Гьоделя о неполноте знаменовали новый этап развития математики.

В результатi дослiдження рiзних теорiй математики дiйшли вывода, что их обоснование может быть возведено к дослiдження системам аксiом для элементарной арифметики, с одной стороны, i теорiї множеств, из iншого. Такими дослiдженнями с начала ХХ столiття занималось много математикiв. I лишь в начале 30-х рокiв к. Гьодель опублiкував достаточно несподiваний на то время i песимiстичний результат: ни одна скiнченна система аксiом для элементарной арифметики не является полной. Точнiше в першiй теоремi Гьоделя утверждается, что любая формальная теорiя T, что мiстить формальную арифметику, является неполной, а именно, в T iснує i может быть эффективно построена замкнутая формула F, такая что F iстинна, однако нi F, нi F не есть вивiдними в T. Вторая теорема Гьоделя о неполноте утверждает, что для довiльної непротиворечивой формальной теорiї T, что включает формальную арифметику, формула, которая описывает несуперечнiсть T, есть невивiдною в T. Здесь уместно заметить, что при доведеннi первой из теорем Гьодель использовал метод, подiбний к вiдомого Дiагонального метода Кантора.

Следовательно, нi для арифметики i теорiї чисел, нi тем бiльше для более богатых математических теорiй не iснує адекватных формалiзацiй. Этот достаточно грустный, но объективный факт однако не отрицает i не знецiнює iдеологию формалiзму. Формальный пiдхiд остается основным конструктивным средством построения i дослiдження математических теорiй. Потенцiйна неможливiсть адекватной i полной формалiзацiї теорiї значит, что принадлежит или видiляти i ограничиваться лишь теми фрагментами теорiї, якi формалiзуються, или же строить iншу более мощную формальную теорiю к сожалению, опять неполную, которая расширит сферу дiї формалiзму. В частности, использовав метод трансфiнiтної iндукцiї, который не может быть формалiзований в формальнiй арифметицi, представитель гiльбертивської школы Герхард Генцен довiв несуперечнiсть формальной арифметики i отдельных роздiлiв математического аналiзу.

В нашем роздiлi, посвященному элементам математической логiки, не предоставляется возможным висвiтлити цi цiкавi и актуальнi проблемы в достатнiй мiрi. Детальнiше i глубже из iсторiєю и современным состоянием дослiджень в галузi математической логiки i обоснования принципов математики можно i стоит ознакомиться зi спецiальної лiтератури [......].

Окрiм сугубо формальных построений в классическом численнi предикатiв язык так называемого Узкого исчисления предикатiв используется для записи утверждений свойств, аксиом, лемм, теорем i определений в рiзних конкретных роздiлах математики. Использование символiки логiки предикатiв позволяет достичь бiльшої строгостi i формальностi в викладеннi математических результатiв, избежать неоднозначностi i багатослiвностi обычного языка. Досвiд свiдчить, что усвоение методики символiчного записи способствует как облегчению розумiння смысла достаточно сложных математических утверждений, так i успiшнiшiй побудовi многоэтапных логiчних ланцюжкiв для решения конкретных задач.

Например, утверждение о том, что довiльне цiле число A можно роздiлити с остатком на цiле число B, какое не дорiвнює нулю, может быть записано так:

A Z B Z[ B0$ Q Z$ R Z A= B Q+ R R=00 R R| B|].

Часто, когда предметная область вiдома i не змiнюється, замiсть A Z записывают просто A. В приведенном виразi всi предикатнi буквы для обозначения вiдношень =, i всi знаки арифметических i логiчних операцiй имеют обычный смысл. Словесно записанное утверждение читается так: "Для цiлих A i B, если B не дорiвнює нулю, iснують цiлi числа Q i R, для каких A= Bq+ R i R или дорiвнює 0, или R бiльше нуля i меньше | B|".

Предикатнi формулы удобно использовать для записи определений рiзних понятий. Выше с их помощью были означенi вiдношення предикаты рiвностi, еквiвалентностi i порядка. Подiбним образом можно записать определение, например, предиката X| Y " X дiлить Y" или " X есть дiльником Y" на множинi цiлих чисел : $ K Y= Kx. Часто такi определения записывают в виглядi: X| Y=$ K Y= Kx.

Замiсть знака рiвносильностi = пишут также знак, который читается "за определением".

С помощью предиката X| Y можно естественно означать унарный предикат " X - простое число" обозначим его через P X:

P X Y Y| X Y=1 Y=-1 Y= X Y=- X.

Наведем еще декiлька прикладiв определений из математического аналiзу. Вiдоме определения границi числовой послiдовностi можно записать так:

Lim Ai= A e0$ K N I N I K| Ai - A|e.

Аналогiчно могут быть записанi класичнi определения рiзних варiантiв понятия неперервностi дiйсної фунцiї F:

1 фунцiя F X Непрерывная в точцi a

e0$h0 X R| X- A|h| F A- F X|e;

2 функцiя F X Непрерывная на iнтервалi A, B

C A, Be0$h0 X A, B| X- C|h| F C- F X|e;

3 функцiя F X Рiвномiрно непрерывная на iнтервалi A, B

e0$h0 C A, B X A, B| X- C|h| F C- F X|e.

Определение основных теоретико-множинних операцiй i вiдношення включения для множеств могут быть записанi так:

X A B X A X B,

X A B X A X B,

X A\ B X A X B,

A B X X A X B

И тому подобное.