Психологіка - Введення у дедуктивні методи
Якщо двозначної логіці висловлювання (судження) діляться на істинні і хибні, то дедуктивних системах формули діляться на доведені і недоведені. Різниця суттєва. Якщо я скажу, що рівно через рік після читання цих слів ви отримаєте грошовий приз, ця заява не буде хибною, оскільки випадково якийсь приз ви можете отримати. З іншого боку, ця заява не буде істинною, оскільки жодного призу може й не бути. Зрозуміло, що я не пророк і подібні речі передбачати не можу. Тому моя заява і не хибна, і не істинна, вона не доведена. І я в цей момент і не брешу, не кажу правду, а роблю, як то кажуть, "необґрунтовану заяву".
Ідея будь-якої дедуктивної системи полягає в тому, щоб довести хоча б деякі формули на основі інших, вже доведених формул. Таким чином, нові доведені судження виходять із раніше доведених суджень. У такому разі треба з чогось розпочати. Починати потрібно з аксіом.
[правила побудови аксіом]: Правила побудови аксіом - це суворі правила, що дозволяють побудувати деякі формули даної (і лише даної) дедуктивної системи.
[аксіома]: Формула дедуктивної системи отримує звання "аксіома", якщо її можна отримати за допомогою правил побудови аксіом.
Кількість аксіом, в принципі, може бути нескінченною. Якщо кількість аксіом, звичайно, то правила побудови аксіом можна написати у вигляді простого перерахування. Якщо кількість аксіом нескінченна, тоді необхідно задати якісь інші суворі правила. Зазвичай вони дуже примітивні і недалеко уникають простого перерахування. Наприклад, це можуть бути так звані "схеми аксіом" - формули із змінними, на місце яких можуть бути підставлені певні символи.
[правила висновку]:Правила виведення - це суворі правила, за якими від однієї або кількох формул дедуктивної системи можна перейти до однієї або кількох формул тієї ж дедуктивної системи (зазвичай це будуть інші формули).
[дедуктивний перехід]:
[крок дедукції]:
[дедуктивний крок]: Дедуктивний перехід (дедуктивний крок, крок дедукції) - це одноразовий перехід від деякої сукупності формул до іншої сукупності формул згідно з правилами виведення.
Кількість формул, з якими мають справу правила виведення протягом одного кроку дедукції має бути звичайно, адже наш еталон суворості (персоналка) не може обробити нескінченно велику кількість тексту.
Отже, у будь-якій ДС є три групи суворих правил:
- Правила побудови формул, що дозволяють відрізнити формулу цієї ДС від будь-якого іншого рядка тексту.
- Правила побудови аксіом, що дозволяють відрізнити аксіому цієї ДС від будь-якої іншої формули цієї ДС.
- Правила висновку, що дозволяють перейти від одних формул цієї ДС до інших.
F1, F2. FN G1, G2. GM // R(1)
Щодо форми запису дедуктивного кроку. Цей варіант перестав бути загальноприйнятим. Найчастіше використовують два інші. В одному випадку пишуть вихідний набір формул, проводять довгу горизонтальну межу, а під нею пишуть отриманий набір формул. Виходить щось на кшталт дробу:
Я не використовую цей запис не так тому, що його можна сплутати з арифметичним дробом, як тому, що дроби незручно записувати в комп'ютерних текстах, а символ можна зімітувати трьома символами "->". В іншому варіанті виписують всі формули поспіль але так, щоб вихідні формули завжди передували отриманим:
Кількість формул ліворуч від теоретично може бути велика, але зазвичай одно-двох. Праворуч(Також теоретично) може стояти хоч сотня формул, але зазвичай стоїть тільки одна.
У дедуктивній системі є два "звання" для формул: "аксіома" та "теорема". Формула отримує звання "аксіома", якщо її можна отримати за допомогою правил побудови аксіом. Інші формули можуть отримати звання "теорема". Для цього треба знайти дедуктивний крок виду (1), в якому всі формули ліворуч вже отримали звання "теорема" або "аксіома" раніше, а наша формула знаходиться в списку формул праворуч від . Іншими словами, нові теореми можуть бути отримані лише на основі старих теорем та аксіом.
[теорема]: Формула, яка не є аксіомою, отримує звання "теорема", коли виявляється крок дедукції від групи формул, кожна з яких вже отримала раніше звання, до іншої групи формул, до якої входить дана формула.
[доведена формула]: Формула називається доведеною, якщо вона вже отримала на даний момент звання "аксіоми" або "теореми".
Тут ми ще раз бачимо різницю між істинністю та доведеністю. Будь-яка аксіома є за визначенням доведена формула. Однак ми можемо оголосити аксіомою будь-яку формулу, у тому числі і свідомо маячню. Така аксіома буде доведена (у рамках цієї ДС), але не буде істинною.
Таким чином, у ДС доведеної вважаються по-перше, всі аксіоми - просто тому, що вони отримані за допомогою правил побудови аксіом і, по-друге, усі формули, що виходять із раніше доведених формул за допомогою правил виведення. Процес присвоєння гордого звання "теорема" все новим формулам якраз і називається "доказом" (принаймні у контексті розмови про дедуктивні системи).
[декукція]:
[дедуктивний доказ]:
[дедуктивний висновок]: дедукцією або дедуктивнимдоказом чи дедуктивним висновком називатимемо текст, у якому перераховані один чи кілька дедуктивних кроків, у яких хоча одна формула отримує звання " теореми " .
Наприклад, нехай є три аксіоми A1, A2 і A3. Нехай є два правила виведення P1 та P2. Нехай правило P1 дозволяє одержати з однієї формули дві нові, а P2 - із двох формул одну. Ми зараз не уточнюватимемо, що це за правила, які саме формули вони дозволяють отримувати, це просто приклад. Тоді доказ міг би виглядати так:
A1 T1, T2 // P1
A3, T1 T4 // P2
A2 T3, T2 // P1
A3, T2 T5 // P2
T4, T5 T6 // P2
Ви бачите, як деяка формула-теорема T6 була отримана з аксіом A1, A2, A3 за допомогою правил P1 і P2. У ході доказу було отримано додаткові теореми T1, T2, T3, T4, T5. Деякі їх потім були використані для продовження виведення, а теорема T3 так і не знадобилася. Проміжні теореми, які потрібні лише для того, щоб довести одну-дві важливіші теореми, в математиці часто називаютьсялемами.
Можна намалювати схему, де вузлами є формули і правила виведення, а лінії показують дедуктивні кроки. У прикладі схема виглядає так:
Отже, якщо говорити формально, то поняття дедуктивної системи входять такі складові: алфавіт, правила побудови формул, правила побудови аксіом, правила виведення і всі формули.