Застосування логіки предикатів для доведення теорем в математиці

Размещено на http://www.allbest.ru/

Математична логіка займає одне з найважливіших місць у сучасній математичній науці. Вона знайшла широке застосування в найрізноманітніших галузях наукових досліджень. Математична логіка з великим успіхом використовується в математиці, теорії автоматів, тобто в кібернетиці, в лінгвістиці, в економічних дослідженнях, у фізіології мозку і психології тощо.

Основним завданням є знаходження і розкриття застосування логіки предикатів, при доведенні теорем, при розв'язанні інтелектуальних задач, при знаходженні оптимального і швидкого алгоритму розв'язку поставленої задачі.

Предметом дослідження є алгоритмічний підхід до доведення теорем з допомогою логіки предикатів.

Математична логіка дуже важлива для вчителів математики. Вона дає можливість краще зрозуміти структурно-логічну схему шкільного курсу математики і не лише шкільного, а й вищої математики, глибше вникнути в суть поняття доведення, з'ясувати зміст поняття логічного слідування, встановити зв'язки між різного роду теоремами тощо.

На мою думку ця тема є важливою в математиці. Тому що розвиток математичної логіки як науки дав значний вплив у розвитку математичної науки. Значну внесок у розвиток математичної логіки зробили такі вчені як: Платон, Аристотель, Лейбніц, Буль, Гільберт.

Історично математична логіка будувалась як алгебраїчна теорія, у якій зв'язки між різними поняттями логіки виражалися за допомогою операцій. Така побудова математичної логіки згодом дістала назву алгебри висловлень і алгебри предикатів, причому алгебра висловлень входить як частина в алгебру предикатів.

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

1. Прикладн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йсних чисел, булеан (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. xy(E(x,y)E(y,x))

Q3. xyz((E(x,y)E(y,z))E(x,y)).

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

O1. x(xx)

O2. xy(((xy)(yx))(x = y))

O3. xyz((xy)((yz)(xz))).

Приєднавши до цих аксiом аксiому

O4. xy((xy)(yx)(x = y)),

дiстанемо теорiю лiнiйного (строгого) порядку.

Ще одна аксiома (аксiома щiльностi)

O5. xy((xy)z((xz)(zy)))

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

2. Найбiльш дослiдженою на сьогоднi формальною теорiєю, яка вiдiграє визначальну роль для аналiзу проблеми обгрунтування засад математики, є так звана формальна арифметика.

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

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

A1. F(0)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. t1t2 = t1t2+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ом для елементарної арифметики, з одного боку, 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зу.

3. Окр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внює нулю, може бути записане так:

(aZ)(bZ)[(b0)((qZ)(rZ)(a = bq+r)((r = 0)((0<r)(r<|b|))))].

, коли предметна область вiдома i не змiнюється, замiсть (aZ) записують просто 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 (>0)(kN)(iNi>k)(|ai -a|<).

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

1) фунцiя f(x) неперервна в точцi a

(>0)(>0)(xR)((|x-a|<)(|f(a)-f(x)|<));

2) функцiя f(x) неперервна на iнтервалi (a,b)

(c(a,b))(>0)(>0)(x(a,b))((|x-c|<)(|f(c)-f(x)|<));

3) функцiя f(x) рiвномiрно неперервна на iнтервалi (a,b)

(>0)(>0)(c(a,b))(x(a,b))((|x-c|<)(|f(c)-f(x)|<)).

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

xAB (xA)(xB),

x AB (xA)(xB),

x A\B (xA)(xB),

AB x((xA)(xB))

Наведемо далі для ілюстрації застосування логіки предикатів приклад доведення теореми з математичного аналізу:

Теорема (Лебег) Нехай -- обмежена на множині функція. -- послідовність вимірних на функцій, яка збігається до функції за мірою на множині . Тоді якщо , то .

Доведення

Очевидно, із умови теореми не випливає, що і гранична функція теж обмежена на множині тією ж константою . З умови теореми маємо,

. (2)

Візьмемо і позначимо . Очевидно, що , -- вимірні множини. Розглянемо

. (4)

Візьмемо і настільки мале, щоб . Оскільки послідовність , то . А це означає, що . Звідси і з (4) одержуємо, що . А це означає, що і теорема доведена.

А також доведення теореми Рісса:

Теорема(Рісс) Якщо послідовність , то існує підпослідовність даної послідовності, яка збіжна до майже всюди на множині .

Доведення

Візьмемо послідовність додатніх чисел збіжну до 0 і знакододатній збіжний ряд: . Оскільки послідовність , то справедлива рівність

. (6)

Поклавши в рівності (6) замість і скориставшись означенням границі послідовності, взявши в якості , одержимо що, . Поклавши в рівності (6) замість і знову скориставшись означенням границі послідовності, взявши в якості , одержимо що, . Продовжуючи цей процес і так далі ми побудуємо послідовність натуральних чисел

. (7)

Ми одержали деяку підпослідовність послідовності . Якщо трапиться що вона збіжна майже всюди на , то теорема буде доведена.

Позначимо через . Зрозуміло, що . Введемо множину . З теореми 5 §1 матимемо, що

. (8)

Оцінимо . Звідси і з (6) маємо що Розглянемо множину . Візьмемо . Звідси маємо, що , а це за теоремою про «два міліціонери» дозволяє стверджувати, що . А це означає, що наша послідовність збігається до в кожній точці множини . А оскільки , то теорема доведена.

Висновок

Таким чином, можна остаточно сказати, що застосування логіки предикатів для доведення теорем в математиці має дуже велике значення.

Використання символiки логiки предикатiв дозволяє досягти бiльшої строгостi i формальностi у викладеннi математичних результатiв, уникнути неоднозначностi i багатослiвностi звичайної мови.

Размещено на Allbest.ru