Категорії

Дипломні, курсові
на замовлення

Дипломні та курсові
на замовлення

Роботи виконуємо якісно,
без зайвих запитань.

Замовити / взнати ціну Замовити

4.1.3. Я.Лукасевич і історія логічних досліджень у Львівсько-Варшавській школі. (класична логіка)

В історії розвитку логіки, головним чином класичного пропозиціонального числення, ім'я Лукасевича займає в школі центральне місце. Створена їм бездужкова нотація вважається візитною карткою польської логічної думки. У Львівсько-Варшавській школі цей вид запису формул використовувався повсюдно (виключення становить Леснєвський, але і він писав функтори перед аргументами).[1]

Наступна таблиця встановлює відповідність між однією з нотацій, яка використовує дужки, і польським записом функторів[2]:

 

заперечення

ù p

Np

імплікація

p®q

Cpq

кон'юнкція

pÙq

Kpq

альтернатива

pÚq

Apq

диз'юнкція

p/q

Dpq

еквівалентність

p«q

Epq

 

Два прості приклади дозволять пояснити використовування бездужкової символіки. Розглянемо формули p ® (p ®ù q) і (p ® p)®ù q. В т.зв. польської нотації ці формули мають наступний вигляд: CpCpNq і CCppNq. Правильно побудована формула повинна починатися з великої літери, тобто з функтора, який одночасно є головним функтором всієї формули; в обох прикладах такий функтор позначається літерою С (перше входження). Аргументом головного функтора є або пропозиціональна змінна (перший приклад), або формула, складена з констант і змінних (другий приклад). Для бездужкової нотації існують суто структурні критерії, завдяки яким встановлюють, чи є дана послідовність, що складається з великих букв і малих літер, правильно побудованою формулою.[3]

Розглянемо критерій правильності побудови формули в бездужковій нотації на прикладі числення речень еквівалентності з роботи Лукасевича [1939], критерію, який є незначною модифікацією аналогічного критерію Яськовського для системи, що містить тільки функтори імплікації і заперечення.[4] Вираз, складений з літер E і малих літер правильно побудований тоді і тільки тоді, коли виконуються наступні дві умови:

(1) число літер E, що входять у вираз, повинне бути на одиницю менше числа малих літер;

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

Обидві умови незалежні, що легко може бути показано на прикладах. Так, виразом EpEqr виконуються обидві умови і він правильно побудований. Вираз EpqEr виконує першу умову, однак не виконує другої, бо в частині, що починається з другої літери E, кількість літер E не менше кількості малих букв. Вираз pEEqrs виконує другу умову, але не виконує першої, оскільки число літер E в цьому виразі не на одну, а на дві літери менше кількості малих букв. Нарешті, вираз pqEErs не виконує ані першої, ані другої умови. Останні три вирази не є правильно побудованими.

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

Правило перевірки правильності довільного виразу полягає на тому, що спочатку кожній літері E приписується число -1, а кожній малій літері - +1. Потім послідовно, починаючи з останнього правого числа, підпорядкованого літері, підсумовуємо числа, просуваючись наліво до початку виразу. Наступний приклад пояснює ці дії:

 E E E p q E r s E t u

 1 2  3 4  3 2 3 2 1 2 1

Літері u відповідає +1, літері t - також +1; 1 плюс 1 дає 2. Літері E відповідає -1, а тому, підсумовуючи це значення з попередньою сумою, тобто 2+(-1) = 1 і отриманий результат підписуємо під E. Якщо вираз правильно побудований, то згідно першій умові сума, яка відповідає всьому виразу і записана в самому початку, повинна дорівнювати 1, а згідно другій умові всі часткові суми, що відповідають окремим відрізкам виразу, повинні бути позитивними. Достатньо поглянути на наведений вираз з тим, щоб переконатися в його правильності.

Польська нотація є однозначною в тому сенсі, що кожна скінчена правильно побудована послідовність великих і малих літер має один і лише один переклад в стандартну нотацію, в якій використовуються дужки. Прагматичний аспект польського запису аналізується Воленським [1985], котрий вважає, що головною перевагою бездужкової символіки є економія алфавіту, оскільки польська нотація не вимагає допоміжних знаків (крапок, дужок) і правил групування таких знаків (їх числа та форми). Якщо в записі з дужками структура, а значить і смисл формули визначаються використанням дужок, то в польській символіці структура формули залежить виключно від позиції літер. Однак з дидактичної точки зору символіка Лукасевича вважається такою, що інтуїтивно важко сприймається і тому більшість підручників з логіки написана з використанням дужок. Наголошується, що коли йдеться про короткі формули, то обидва типи нотації мають однакові можливості орієнтації в структурі виразу, тоді як у формулах середньої довжини символіка з дужками зручніше, але довгі формули - вважає польський дослідник школи - в бездужковому записі більш читабельні..

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

В 20-і роки вже було відомо, що числення висловів можна побудувати, спираючись на різні системи первинних понять і аксіом. Виникло питання: чи можна і як порівнювати такі аксіоматики, припускаючи, що побудовані на них числення висловів є несуперечливими і повними? Певні критерії порівняння аксіоматик використовувалися давно. Так, незалежна система аксіом краще залежної. Далі, можна сказати, що кращою є незалежна аксіоматика, яка базується на незалежних первинних поняттях, ніж незалежна аксіоматика, але яка базується на залежних поняттях. Звідси можна зробити висновок, що кращою є аксіоматика, яка використовує менше число первинних термінів (понять)[5].

В школі були сформульовані також додаткові критерії. Вони торкалися кількості аксіом, їх довжини, кількості різних змінних і т.зв. органічності аксіом. Перший критерій простий: чим менше аксіом містить числення - тим воно краще, тому оптимальною є одноелементна аксіоматика. Цієї позиції, як було показане раніше, дотримувався Леснєвський. Визначимо довжину аксіоматики числом символів, що до неї входять. З двох аксіоматик, що містять однакове число первинних символів і однакове число аксіом, кращою є більш коротка аксіоматика. Припустимо, що існують дві аксіоматики однієї довжини, але записані за допомогою різних змінних. В цьому випадку кращою є аксіоматика, яка містить менше відмінних одна від другої змінних. Органічною називається така формула системи, ніяка власна частина якої не належить численню; наприклад, формула CqCpp є неорганічною. З двох аксіом - органічної і неорганічної кращою є аксіома органічна. Поняття органічної формули походить від Леснєвського, а її дефініція - від Вайсберга. Вперше вона була опублікована Лукасевичем і Тарським [1930a]. Кінець кінцем ідеальна аксіоматика повинна складатися з однієї органічної аксіоми мінімальної довжини і по можливості з якнайменшим числом різних символів. Найбільш природним чином наведені критерії застосовуються до числень висловів, але в школі шукали подібні критерії і для більш багатих систем. Так Лінденбаум [1936] подав критерій простоти для довільних функторів, який полягав на тому, що функтор F1 простіше від функтора F2, якщо число аргументів F1 менше числа аргументів функтора F2, а у випадку, якщо обидва функтора мають однакове число аргументів, то F1 простіше, якщо принаймні один з його аргументів буде більш низького логічного типу, ніж довільний аргумент F2 і жоден з аргументів F1 не належить до більш високого типу, ніж довільний аргумент F2. Цей критерій може бути застосований, наприклад, до систем Леснєвського.

Наведені критерії відображають культивоване у варшавській частині школи гасло «логіка для логіки». Нижче подається огляд деяких результатів класичного числення висловів.

Найбільш відомою системою числення висловів є система, побудована на імплікації і запереченні як первинних термінах. В школі був відомий ряд аксіоматик цієї системи. Одна з перших належить Лукасевичу [1925], а все числення детально викладено в [1929]. Як аксіоми Лукасевич приймає наступні формули:

(1) CCpqCCqrCpr

(2) CCNppp

(3) CpCNpq

Правилами виводу є правила підстановки, відділення і заміни за визначенням. Останнє правило сформульовано таким чином: якщо x доведено в численні, а у є частиною x, еквіморфною правій стороні однієї з дефініцій Dpq = CNpq, Kpq = NCpNq, Apq = CpNq, Epq = NCCpqNCqp щодо підстановки, то кожний вираз, отриманий з x заміною у виразом еквіморфним з лівою стороною дефініції або її підстановкою, може бути доведений в системі.

Таким чином, в основі числення лежать правила підстановки, відділення і заміни за визначенням. У варшавській школі схеми аксіом використовувалися тільки при формалізації металогічних і метаматематичних досліджень; конструкції ж логічних систем були сформульовані виключно за допомогою конкретних формул. Символ рівності за визначенням (“=”) не належить мові системи. Лукасевич трактує дефініції як скорочення, вважаючи їх теоретично зайвими. Леснєвський же в питанні про дефініції займав іншу позицію, але і Лукасевич пізніше змінив погляд на дефініції, про що буде сказано нижче. У згаданій вище системі роль дефініцій суто прагматична, бо вони не носять творчого характеру і Лукасевич вважає, що дефініції не є виразами, які слід доводити, це лише "рівності на полях теорії".

З аксіом (1)-(3) за допомогою правил підстановки, відділення і заміни Лукасевич виводить 143 формули числення висловів. Доведення займає 19 сторінок і з урахуванням словесного коментаря для такої значної частини пропозиціонального числення повинно вважатися вельми компактним. Цей ефект був досягнутий завдяки використанню економічного методу запису структури доведення. Приклад пояснює метод Лукасевича[6]:

             (1)p/Cpq,  q/CCqrCpr,  r/s  *C(1)-(4)

(4)          CCCCqrCprsCCpqs.

Реконструкція доведення формули (4) складається з наступних кроків. В аксіому (1) робиться підстановка: замість змінної p - вираз Cpq (цьому крокові відповідає секвенція (1)p/Cpq), замість змінної q - вираз CCqrCpr (секвенція q/CCqrCpr), замість змінної r - змінна s (секвенція r/s); всі підстановки робляться в аксіому (1), що в рядку доказу сигналізується тим, що між першим входженням літери p в цьому рядку і останнім входженням s (остання літера перед зірочкою) не знаходиться жоден номер аксіоми або формули. Після підстановки отримуємо вираз CCCpqCCqrCprCCCCqrCprsCCpqs. Засновок цієї імплікації (головного функтора С), тобто вираз, що починається другим входженням літери С і кінчається другим входженням r, є аксіомою (1), а наслідок – формулою, яка доводиться. Оскільки підстановка здійснювалася у формулу числення, а дана формула є такою, і правило підстановки говорить, що результат підстановки також належить численню, то можна застосувати правило відділення, про що інформує послідовність *C(1)-(4).

Описаний спосіб доведення в подальшому використовувався учнями Лукасевича.[7]

Крім числення, побудованого на аксіомах (1)-(3) у варшавській школі використовувалися і інші імплікативні аксіоматики. Ось деякі трьохелементні системи аксіом: CCCpqrCNpr, CCCpqrCqr, CCNprCCqrCCpqr - Лукасевич [1929]; CpCqp, CCpCqrCCpqCpr, CCNprCCqrCCpqr - Лукасевич [1930]; CNpCpq, CpCqCrp, CCNprCCqrCCpqr - Собоцинський [1954]; CCpqCNqCpr, CpCqCrp, CCNpqCCpqq - Собоцинський [1954].

Всі наведені імплікативно-негативні аксіоматики використовують ті ж правила і дефініції, що і логічна система, представлена аксіомами (1)-(3).

В 20-і роки Лукасевич поставив задачу знаходження одноелементного імплікативно-негативного базису (базис  =  аксіоматика). Історія пошуків (викладена в Собоцинський [1932] і частково в Лукасевич [1936], а більш повно у Воленський [1985]) така:

Тарський (1925) - аксіома з 53 літер:

СССССsCtCtCvCvvCCCCCpCqrCCpqCprCCCNpNqCqpxxyyCCpCqpzz;

Лукасевич (1927) - аксіома з 43 літер:

CCCsCtCtCpCqpCCCCCpCqrCCpqCprCCCNpNqCqpvvee;

Лукасевич (1927) - аксіома з 39 літер:

СССaCbCdaCCCCCpCqrCCpqCprCCCNpNqCqpvvee;

Лукасевич (1927) - аксіома з 38 літер:

СССaCbCdCedCCCNstCCNsNtsCCCpqCCqrCprzz;

Собоцинський (1927) - аксіома з 36 літер:

CCCaCbCdaCCCNmCqCNrNpCCmCqrCCpqCpree;

Лукасевич (1927) - аксіома з 35 літер:

CCCaCbCdaCCCNmCqCqNpCCmCqrCCpqCpree;

Лукасевич (1927) - аксіома з 33 літер:

CCCpCqpCCCNrCsNtCCrCsuCCtsCtuvCwv.

Цей далеко не повний список завершує аксіома Лукасевича, що складається з 23 літер:

CCCpqCCCNrNstrCuCCrpCsp.

Пошук найкоротшої імплікативно-негативної аксіоми не зводився виключно до питання про число літер. Варшавські логіки шукали також і органічну аксіому. Такою є 27 буквена аксіома Собоцинського (1927): CCCpqCCCNpNrsCrtCuCCtpCvCrp.

В школі досліджувалися також аксіоматики, в яких використовуються інші первинні терміни. Лукасевич [1930] подає диз'юнктивно-негативну аксіоматику: ANANANpqrANpr, ANANApqrANpr, ANANApqrANqr з правилами підстановки, відділення (якщо ANxy і x є істинні формули, то у - також істинна формула), дефініціями решти функторів і правилами заміни за визначенням. Особливо важлива дефініція Cpq = ANpq, яка дозволяє представити аксіоми в наступному вигляді: CCApqrCpr, CCApqrCqr, CCprCCqrCApqr; ці аксіоми є диз'юнктивно-імплікативними і в явному вигляді заперечення не містять.

Вайсберг [1938] сформулював аксіоматику, в якій первинними термінами є С і 0 (фальш): CpCqp, CCpqCCqrCpr, CCCpqpp, C0p + правило підстановки, правило відділення, дефініції, наприклад, Np = Cp0, а також правило заміни за визначенням. Правило заміни за визначенням привернуло увагу польських логіків у зв'язку з функцією Шеффера, котрий знайшов дві взаємно дуальні двохаргументні функції, які дозволяють визначати всі функтори класичної логіки.[8] У використанні функцій Шеффера для аксіоматизації класичного числення висловів першим успіхів добився Ніко (Nicod) [1917]. Його аксіоматика містила єдину аксіому DDpDqrDDtDttDDsqDDpsDps, правило підстановки і правило відділення (якщо DxDxy і x є істинні формули, то у також істинна формула). Лукасевич [1931], замінюючи в аксіомі Ніко змінну t змінною s, отримав формулу DDpDqrDDsDssDDsqDDpsDps. Вона є частковим випадком вихідної формули і разом з тим аксіома Ніко випливає з аксіоми Лукасевича. Цей факт Лукасевич вважав контрприкладом поширеній думці, ніби дедукція не узагальнює і ставив питання: Чи "можуть і які загальні риси мати узагальнюючі формули?" ([1931], S,174) Однак обидві аксіоми є неорганічними (в аксіомі Ніко це вираз DtDtt, а у Лукасевича - DsDss). Пізніше Лукасевичем [1931] і Вайсбергом були знайдені органічні аксіоми числення речень, які використовують виключно функтор строгої диз'юнкції. У всіх диз'юнктивних системах, окрім вже згаданих правил підстановки і відділення, приймалося також правило заміни, яке передбачає дефініцію функторів N, К, А, С, E за допомогою функтора D.

Логіки варшавської школи будували також аксіоматики з використанням більшого числа первинних термінів. В роботі Вайсберга [1937] наведена, наприклад, наступна аксіоматика: CpCqp, CCpCqrCCpqCpr, CKpqp, CKpqq, CCpqCCprCpKqr, CpApq, CqAqp, CCprCCqrCApqr, CEpqCpq, CEpqCqp, CCpqCCqpEpq, CNpCpq, CCpNpNp з правилами підстановки і відділення. Тарський [1938] подає схеми аксіом (у зв'язку з чим йому достатньо правила відділення) з метазмінними наступного виду: CxCyx, CCxCyzCCxzCyz, CxAxy, CyAxy, CCxzCCyzCAxyz, CKxyx, CKxyy, CCzxCCzyCzKxy, CCNxxx, CCxNxNx.

В школі досліджувалися також і часткові числення висловів. Частковим називається числення, засноване лише на деяких функторах, яких недостатньо для визначення всіх постійних первинних термінів числення. Так в 1921 р. Тарський опублікував аксіоматику для імплікативного числення висловів: CpCqp, CCpqCCqrCpr, CCCpqrCCprr з правилами підстановки і відділення (Лукасевич, Тарський [1930]). Ряд аксіоматик цього виду належить Вайсбергу.

Вивчалася можливість побудови імплікативного числення на одній аксіомі.[9] Вайсберг (1926) обнародував 25-и буквену аксіому (органічну): CCCpqCCrstCCuCCrstCCpuCst, а Лукасевич (1926) навів також 25-и буквену аксіому, але не органічну: CCCpCqpCCCCCrstuCCsuCruvv. Подальші результати отримав Лукасевич, котрий сформулював (1930) органічну 17-і буквену аксіому CCCpqCrsCtCCspCrp, а потім (1936) - 13-и буквену, також органічну аксіому: CCCpqrCCrpCsp. Питання було остаточно вирішено, коли Лукасевич [1948] опублікував доказ того, що аксіома з 13-і літер є найкоротшою.

Першу аксіоматику, в якій використовується еквівалентність як єдиний постійний термін, навів Леснєвський [1929]: EEEprEqpErq, EEpEqrEEpqr + правила підстановки і відділення. Після появи ряду аксіоматик, отриманих Вайсбергом, Бріманом, Лукасевичем і Собоцинським Лукасевич [1938] доводить, що формула, яка містить менше 10 літер не може бути єдиною аксіомою числення, побудованого виключно на функторі еквівалентності.



[1] Я.Воленський ([1985], S.93) наводить дані про те, що ідея бездужкової символіки належить Л.Хвістеку, який про неї говорив у Варшаві на початку 20-х років. Лукасевич ([1931], S.165) стверджує, що основи бездужкового запису він розробив в 1924 р.

[2] В польській логічній літературі альтернатива означає операцію нестрогої диз'юнкції, тоді як диз'юнкція p/q розуміється як диз'юнкція виключна, тобто як функтор, який у вітчизняній літературі трактується як альтернатива. В роботі, присвяченій науковій співдружності, яка внесла вагомий внесок в логічну семіотику, ми визнали потрібним зберегти оригінальну нотацію польської школи логіки. Тим не менш в тексті замість терміну "альтернатива" використовуватиметься термін "диз'юнкція", більш звичний у вітчизняній літературі з логіки; з контексту буде ясно, про який функтор йдеться.

[3] Обговорюючи бездужкову символіку Я.Воленський [1985] згадує вслід за Лукасевичем [1939] "деякого (не названого на ім'я) учня Хвістека", котрий розробив критерій регулярності виразів, побудованих із змінних і констант суто по позиційних ознаках. Цим учнем є Скарженський, критерій якого згадує інший учень Хвістека - Владислав Хетпер, автор роботи "Роль незалежних схем в побудові системи семантики" [1938], в якій зроблено посилання на критерій Скарженського. Сам же Вл.Хетпер використовує правила побудови виразів по індукції.

[4] Приклад запозичений з книги Я.Воленського [1985].

[5] Воленський [1985] слушно зауважує, що контрприкладом такої оцінки є аксіоматика Гільберта-Бернайса, яка складається з 15 аксіом і містить знаки заперечення, кон'юнкції, диз'юнкції, імплікації і еквівалентності; аксіоми цієї системи, як відомо, залежні. Перевагою цієї аксіоматики є елегантна характеристика основних властивостей окремих функторів за допомогою групування аксіом, а також можливість отримання інтуїціоністського або мінімального числень шляхом викреслювання окремих аксіом, що пояснюється цілями, відмінними від намірів варшавських логіків.

[6] Ця манера запису виводу використовується в російському перекладі Лукасевича [1951a].

[7] Хоча сам по собі цей метод не містить яких-небудь оригінальних ідей, проте слід погодитися з думкою Воленського [1985], що простий і елегантний метод доказу тісно пов'язаний з особливостями кодифікувань бездужкової нотації і є природним її доповненням.

[8] Функції отримали свою назву від імені американського логіка Х.М.Шеффера, котрий їх знайшов в 1913 р. (незалежно від Ч.С.Пірса, котрий зробив це у 1880 р.)

[9] Воленський ([1985], S.101) пише, що першу таку аксіому знайшов в 1925 р. Тарський, однак його результат ніколи не був опублікований і форма цієї аксіоми залишилася невідомою.