Інтуїціоністська логіка
Інтуїціоністська логіка є однією з найбільш важливих гілок некласичної логіки. Ставлячи на перший план математичну інтуїцію, інтуїціоністи не надавали великого значення систематизації логічних правил. Тільки в 1930 р. голландський математик і логік А. Гейтінг - учень творця інтуїціонізму Л. Брауера ‒ дав аксіоматичне формулювання інтуїціоністської логіки. Так, у інтуїціоністській логіці не діє закон виключаючого третього. Відкидання закону виключаючого третього не означає прийняття заперечення цього закону, а навпаки, інтуїціоністська логіка стверджує, що заперечення заперечення цього закону, тобто його подвійне заперечення, є правильним.
У класичній логіці центральну роль відіграє поняття істини. На його основі визначаються логічні зв'язки, що дозволяють будувати складні висловлювання. В інтуїціоністській логіці сенс зв'язок задається шляхом зазначення тих необхідних і достатніх умов, при яких може стверджуватися складне висловлювання.
Так, наприклад, якщо р і q ‒ деякі висловлювання, то їх кон'юнкцію р і q можна стверджувати, тільки якщо можна стверджувати як р , так і q. Диз'юнкцію висловлювань р або q можна стверджувати тоді і тільки тоді, коли можна стверджувати хоча б одне з висловлювань р або q. Математичне висловлювання р можна стверджувати лише після проведення деякої математичної побудови з певними властивостями; відповідно заперечення р можна стверджувати, якщо і тільки якщо є побудова, що приводить до суперечностей припущення про те, що побудова р виконана. Імплікацію висловлювань, якщо р, то q, можна стверджувати так, якщо є така побудова, яка, будучи об'єднана з побудовою р, автоматично дає побудову q.
Інтуїціоністське розуміння логічних зв'язок є таке, що з доказу істинності висловлювання завжди можна витягнути спосіб побудови об'єктів, існування яких стверджується.
Мова інтуїціоністської логіки висловлювань є така, як і в класичної логіки: формули будуються із множини змінних Var = {P, Q,.. } за допомогою зв'язок < & , ˅, ¬ , → >.
9.1. Числення висловлювань в інтуїціоністській логіці
Означення 9.1.1. Численням висловлювань в інтуїціоністській логіці називають числення висловлювання , серед аксіом якого немає закону виключаючого третього А ˅ ¬ А. Таке числення називають інтуїціоністським численням висловлювань.
Інтуїціонізм відкидає ідею про те, що всі висловлювання діляться на істинні й помилкові. Із цієї точки зору закон виключаючого третього є безпідставним: А ˅ ¬ А означає, що для задовільного твердження А можна встановити або А, або його заперечення.
Інтуїціоністське числення висловлювань має вивідні формули:
1. Щоб зрозуміти сенс формули (А → В) → ( ¬В → ¬А), необхідно згадати, що заперечення ¬ Х можна розуміти , як ( Х → ┴ ) , де ┴ ‒ наперед хибне твердження. Ця формула показує те, що якщо із А слідує В, а із В випливає наперед хибне твердження, то із А також випливає наперед хибне твердження (поодинокий випадок транзитивності відношення слідування). Виведення цієї формули не використовує закону виключаючого третього. Насправді, за лемою про дедукцію (доведення якої залишається таким самим і для інтуїціоністського числення висловлювань) достатньо довести, що із (А →В ) і із ¬ В виводиться ¬ А.
2. Щоб вивести формулу ( А→¬¬ А ), необхідно показати, що із А виводиться ¬¬А, для цього достатньо із А і ¬А вивести дві взаємо протилежні формули (тривіально підходять самі формули А і ¬А).
3. Формула (¬ ¬ ¬ А → ¬ А) отримується із двох попередніх: візьмемо В таким, що дорівнює ¬ ¬А у першій із них.
4. Формула ( ¬ А → ¬¬¬ А), з іншого боку, є поодиноким випадком другої формули, оскільки три заперечення еквівалентні одному.
5. Комутативність та асоціативність операцій ˄ і ˅ , також як і дві властивості дистрибутивності, не використовують закону виключаючого третього.
6. Як і раніше, формула (( А ˅ В ) → С ) рівносильна формулі (( А → С ) ˄ ( В → С )) ( імплікації в обидві сторони, які з’єднують ці формули, вивідні в ітуїціоністському численні висловлювань).
7. Застосувавши знак ┴ як С у попередніх формулах, можна спостерігати, що один із законів де Моргана , а саме закон ¬ ( А˅ В ) ↔ ¬ А ˄ ¬ В не спирається на закон виключаючого третього.
8. Формулу ¬ ¬ ( А ˅ ¬ А ) за допомогою збереженого закону де Моргана можна переписати у вигляді ¬ (¬ А ˄ ¬ ¬ А ), і необхідно лише вивести із ( ¬ А ˄ ¬ ¬А ) дві протилежні формули, що очевидно.
9.2. Доведення формул числення висловлювань в інтуїціоністській логіці висловлювань
Теорема 9.2.1. Формула р ˅ ¬ р не вивідна в інтуїціоністській логіці.
Доведення. У класичній логіці кожна пропозиційна змінна може набувати два значення – істина ( І ) або хибність ( Х ). Розширимо множину істинністних значень шляхом введення нового значення Н (назвемо це значення словом «невідомо» ). Оскільки ми ототожнюємо значення І з одиницею, а значення Х з нулем, то логічно можливо ототожнювати значення Н з числом ½. Ми доведемо, що інтуїціоністські вивідні формули завжди набувають значення І, а формула р ˅ ¬ р не така і тому не вивідна.
Щоб визначити значення формул у тризначній логіці, необхідно задати таблиці істинності для всіх пропозиційних зв'язок. Кон'юнкцію визначимо як мінімум із двох значень ( Х ˄ Н = Х, а І ˄ Н = Н ), а диз’юнкцію – як максимум ( Х ˅ Н= = І , Х ˅ І = І, Н ˅ І = І ). Заперечення діє як : ¬ І = Х, ¬ Х = І, ¬ Н = Х. В останньому не можна вважати ¬ Н = Н, тому що тоді формула ¬ ( р ˄ ¬ р) , яка вивідна в ітуїціоністській логіці , матиме значення Н при р = Н.
Найскладніше визначення істинності для імплікації. Ми вважаємо, що
( І → х ) = х і ( Х → х ) = І
для будь-якого значення істинності х, а також що
( Н → Х ) = Х, ( Н → Н ) = І і ( Н → І ) = І.
Назвемо формулу потрійною тавтологією, якщо вона набуватиме значення І при будь-яких значеннях змінних із множини { І, Х, Н }. Тепер потрібно перевірити дві речі: усі аксіоми інтуїціоністського числення є потрійними тавтологіями; якщо посилка імплікації й уся імплікація є потрійною тавтологією, то і висновок теж є потрійною тавтологією. Друге відразу випливає з визначення імплікації, а перше ‒ із доведення усіх аксіом за допомогою таблиць істинності. Отже, будь-яка інтуїціоністська формула, що виводиться, є потрійною тавтологією. Тепер помітимо, що формула р ˅ ¬ р набуває значення Н при р = Н і тому не є потрійною тавтологією , а це означає, що вона невивідна , що й потрібно було довести.
9.3. Застосування моделі Кріпке в інтуїціоністській логіці
Для задання моделі Кріпке необхідно:
1. Вказати частково впорядковану множину { W, ≤ }, яку називають множиною світів.
2. Для кожного світу вказати, які із пропозиційних змінних вважаються істинними у цьому світі (інші змінні вважаються хибними у цьому світі). Якщо змінна х істинна у світі W, то ми пишемо W ╟ х.
При цьому необхідно, щоб була виконана наступна умова, якщо u ≤ v і и ╟ х , то v ╟ х (область істинності будь-якої формули спадкова вгору). Коли модель Кріпке задана, то можна визначити істинність будь-якої формули у цьому світі індукцією щодо побудови самої формули.
Приклад 9.3.1. Визначити істинність формули W ╟ А ˄ В у світі W .
Розв’язання. Користуючись індукцією визначення побудови формули визначаємо, якщо W ╟ А і W ╟ В, то тоді є істинною і формула W ╟ А ˄ В.
Приклад 9.3.2. Визначити істинність формули W ╟ А ˅ В у світі W .
Розв’язання. Користуючись індукцією визначення побудови формули визначаємо, якщо W ╟ А або W ╟ В, то тоді є істинною і формула W ╟ А ˅ В.
Приклад 9.3.3. Визначити істинність формули W ╟ А → В у світі W .
Розв’язання. Користуючись індукцією визначення побудови формули в будь-якому світі и ≥ w, в якому істинна формула А, тоді буде також істинною і формула В.
Приклад 9.3.4. Визначити істинність формули W ╟ ¬ А у світі W .
Розв’язання. Користуючись індукцією, якщо ні в якому світі и ≥ w, формула А не є істинною , тоді формула W ╟ ¬ А є істинною у світі W .
Індукцією щодо побудови формули А легко перевірити, що якщо вона істинна в будь-якому світі, то вона є істинною і в усіх більших світах.
Формула, яка не є істинною в заданому світі, називається хибною в ньому.
Визначення істинності для заперечення узгоджене з розумінням ¬ А як А → ┴ , де ┴ - тотожно хибна у всіх світах формула.
Теорема 9.3.1. Якщо формула вивідна в інтуїціоністському численні висловлювань, то вона істинна в усіх світах усіх моделей Кріпке.
Доведення. Для доведення необхідно перевірити, що всі аксіоми істинні в усіх світах, а також, що правило « modus ponens » зберігає цю властивість.
Інше очевидно , тому що , якщо А→ В істинна в усіх світах і А істинна в усіх світах, то за визначенням істинності імплікації В також буде істинна в усіх світах. Тепер перевіримо істинність усіх аксіом. Для першої аксіоми А→ ( В → А ) можна сказати, що якщо формула А істинна в деякому світі, то внаслідок монотонності вона також істинна і вище , тому і В → А також є істинною. Для другої аксіоми ( А→ ( В → С )) → (( А → В) → ( А → С )) можна сказати таке. Нехай и ╟ А→ ( В → С ). Необхідно впевнитися, що и ╟ ( А → В) → ( А → С ). Але це означає, що якщо v ≥ и і v ╟ А → В, то v ╟ А → С. Останнє, в свою чергу, означає, що якщо w ≥ v і w ╟ А, то w ╟ С. Проте внаслідок монотонності ми знаємо, що w ╟ А→ ( В → С ) і w ╟ А → В. Тому із w ╟ А випливає w ╟ В, w ╟ ( В → С ) і w ╟ С , що і потрібно було довести. Доведення решти аксіом відбувається ще простіше, а тому їх доведення пропонується виконати самостійно.
Теорема 9.3.2. Якщо деяка формула не вивідна в ітуїціоністському численні висловлювань, то достатньо подати модель Кріпке в одному зі світів , у якому вона хибна.
Доведення. Для доведення покажемо , що в цьому випадку є модель, у якій серед світів є найменший і в ньому формула хибна. Для формули р ˅ ¬ р така модель будується просто. Візьмемо два світи так, щоб перший був менший, ніж інший. Нехай р є істинним тільки в другому світі. Тоді ¬ р буде не істинним ніде, а р ˅ ¬ р буде істинним тільки в другому світі. Це доведення, по суті, збігається з наведеним у § 9.2 , оскільки в цій моделі Кріпке для формули є три можливості: вона істинна в обох світах; вона істинна тільки в другому світі; вона не істинна ні в одному зі світів. Ці три інтерпретації моделі Кріпке відповідають таким значенням тризначної логіки : І, Н, Х § 9.2 . Для формули ¬ ¬ р → р можна застосувати ту саму шкалу ( р істинне тільки в другому світі). Цю шкалу можна застосувати для формули ( ¬ q → с ) → ( q → р ), поклавши р істинним у двох світах, а q ‒ тільки в другому. Для решти трьох формул доцільно розглянути шкали з трьома світами: початковим світом и , із якого можливо потрапити в v ≥ и і w ≥ и ; світи v і w є непорівнянними. Якщо формула р істинна тільки у світі v , то формула ¬ р істинна тільки у світі w, а ¬ ¬ р ‒ істинна тільки у світі v , так, що у світі и обидві формули ¬ р і ¬ ¬ р є хибні й диз’юнкція ¬ р ˅ ¬ ¬ р теж хибна. Для того, щоб побудувати контрмодель для формули ¬ ( р ˄ q ) → ¬ р ˅ ¬ q, необхідно вважати,що р істинна тільки у світі v , а q істинна тільки у світі w. Таку саму шкалу можна застосовувати і для формули (( р ˅ q ) → р ) ˅ (( р ˅ q ) → q ).
