Інтуїционістськая логіка

Попередня ↔ Наступна

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

Синтаксис формул в интуиционистской логіці схожий з синтаксисом логіки висловлювань або логіки першого порядку. Різниця полягає в тому, що багато тавтології цих класичних логік не можуть бути доведені в рамках логіки интуиционистской. Як приклади можна привести не тільки закон виключення третього (\ (P \ and \ neg P \)), але і закон Пірса (\ (((P \ rightarrow Q) \ rightarrow P) \ rightarrow P \)) і навіть закон заперечення заперечення У класичній логіці обидва вирази \ (P \ rightarrow \ neg \ neg P \) і \ (\ neg \ neg P \ rightarrow P \) є теоремами. У интуиционистской логіці тільки перший вираз є теоремою: заперечення заперечення може бути виведено, але не може бути видалено.

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

Аксіоматика [ред]

Що використовується правило виведення - Modus Ponens. Система аксіом наступна:

THEN-1: \ (\ phi \ rightarrow (\ chi \ rightarrow \ phi) \)
THEN-2: \ ((\ phi \ rightarrow (\ chi \ rightarrow \ psi)) \ rightarrow ((\ phi \ rightarrow \ chi) \ rightarrow (\ phi \ rightarrow \ psi)) \)
AND-1: \ (\ phi \ and \ chi \ rightarrow \ phi \)
AND-2: \ (\ phi \ and \ chi \ rightarrow \ chi \)
AND-3: \ (\ phi \ rightarrow (\ chi \ rightarrow (\ phi \ and \ chi)) \)
OR-1: \ (\ phi \ rightarrow \ phi \ or \ chi \)
OR-2: \ (\ chi \ rightarrow \ phi \ or \ chi \)
OR-3: \ ((\ phi \ rightarrow \ psi) \ rightarrow ((\ chi \ rightarrow \ psi) \ rightarrow (\ phi \ or \ chi \ rightarrow \ psi)) \)
NOT-1: \ ((\ phi \ rightarrow \ chi) \ rightarrow ((\ phi \ rightarrow \ neg \ chi) \ rightarrow \ neg \ phi) \)
NOT-2: \ (\ phi \ rightarrow (\ neg \ phi \ rightarrow \ chi) \)

Для того щоб зробити наведену систему аксіом сумісної з логікою предикатів першого порядку, додається правило узагальнення і наступний набір аксіом:

PRED-1: \ ((\ forall x Z (x)) \ rightarrow Z (t) \)
PRED-2: \ (Z (t) \ rightarrow (\ forall x Z (x)) \)
PRED-3: \ ((\ forall x (W \ rightarrow Z (x)) \ rightarrow (W \ rightarrow \ forall x Z (x)) \)
PRED-4: \ ((\ forall x (Z (x) \ rightarrow W)) \ rightarrow (\ forall x Z (x) \ rightarrow W) \)

Взаємна определяемости операцій [ред]

У класичній пропозіціональной логіці (логікою висловлювань) можливо побудувати базис операцій, який дозволить визначати одні операції через інші. Наприклад, базисом є три операції Лукасевича - кон'юнкція. диз'юнкція і заперечення. Більш того, існують базиси, що складаються з однієї операції, а тому перераховані операції можна визначити через такі однооператорние базиси. До них, наприклад, відносяться: стрілка Пірса (NOR - НЕ АБО) і штрих Шеффера (NAND - Хіба ж то й). Абсолютно також в класичній логіці першого порядку один з кванторів може бути визначений через інший за допомогою заперечення.

Нижче наведені фундаментальні формули, за допомогою яких операції визначаються один через одного. Всі ці формули є всього лише Булевського функціями (в силу закону бівалентності). Але закон бівалентності не діє в интуиционистской логіці, оскільки в ній прийнятий закон несуперечності. В результаті цього багато тотожності з класичної логіки є в логіці интуиционистской всього лише теоремами з одним напрямком слідства (хоча деякі залишаються теоремами еквівалентності). Ось ці теореми:

Зв'язок кон'юнкції і диз'юнкції:
- \ ((\ Phi \ wedge \ psi) \ to \ neg (\ neg \ phi \ vee \ neg \ psi) \)
- \ ((\ Phi \ vee \ psi) \ to \ neg (\ neg \ phi \ wedge \ neg \ psi) \)
- \ ((\ Neg \ phi \ vee \ neg \ psi) \ to \ neg (\ phi \ wedge \ psi) \)
- \ ((\ Neg \ phi \ wedge \ neg \ psi) \ leftrightarrow \ neg (\ phi \ vee \ psi) \)
Зв'язок кон'юнкції і імплікації:
- \ ((\ Phi \ wedge \ psi) \ to \ neg (\ phi \ to \ neg \ psi) \)
- \ ((\ Phi \ to \ psi) \ to \ neg (\ phi \ wedge \ neg \ psi) \)
- \ ((\ Phi \ wedge \ neg \ psi) \ to \ neg (\ phi \ to \ psi) \)
- \ ((\ Phi \ to \ neg \ psi) \ leftrightarrow \ neg (\ phi \ wedge \ psi) \)
Зв'язок диз'юнкції і імплікації:
- \ ((\ Phi \ vee \ psi) \ to (\ neg \ phi \ to \ psi) \)
- \ ((\ Neg \ phi \ vee \ psi) \ to (\ phi \ to \ psi) \)
- \ (\ Neg (\ phi \ to \ psi) \ to \ neg (\ neg \ phi \ vee \ psi) \)
- \ (\ Neg (\ phi \ vee \ psi) \ leftrightarrow \ neg (\ neg \ phi \ to \ psi) \)
Зв'язок кванторів загальності та існування:
- \ ((\ Forall x \ \ phi (x)) \ to \ neg (\ exist x \ \ neg \ phi (x)) \)
- \ ((\ Exist x \ \ phi (x)) \ to \ neg (\ forall x \ \ neg \ phi (x)) \)
- \ ((\ Exist x \ \ neg \ phi (x)) \ to \ neg (\ forall x \ \ phi (x)) \)
- \ ((\ Forall x \ \ neg \ phi (x)) \ leftrightarrow \ neg (\ exist x \ \ phi (x)) \)

Для роз'яснення можна розглянути наступні приклади. У интуиционистской логіці висловлювання «a або b» є більш сильним, ніж висловлювання «якщо не a, то b», оскільки з першого слідують другі, але не навпаки (в класичній логіці ці висловлювання тотожні). З іншого боку, висловлювання «ні (a і b)» еквівалентно висловом «Не a або НЕ b», оскільки кожне з них може випливати з іншого.

Обчислення наслідків [ред]

Герхард Гентца виявив, що наявність простого обмеження в його системі \ (LK \) (обчислення наслідків для класичної логіки) веде до того, що система стає сповнена з точки зору интуиционистской логіки. Він назвав цю нову систему з обмеженням як \ (LJ \).

Семантика интуиционистской логіки складніша, ніж для класичної логіки. Теоретична модель може бути описана за допомогою алгебри Хейтінга або еквівалентної нотацією у вигляді семантики Крипкая.

Семантика алгебри Хейтінга [ред]

У класичній логіці часто обговорюються значення істинності. які можуть приймати змінні. Такі значення зазвичай вибираються з безлічі значень алфавіту булевої алгебри. Операції кон'юнкції і диз'юнкції позначаються в булевої алгебри символами \ (\ and \) і \ (\ or \) відповідно, так що формула \ (A \ and B \) позначає диз'юнкцію двох значень істинності (\ (A \) і \ (B \)) в булевої алгебри. В цьому випадку є теорема, в якій мовиться, що формула є правильною в класичній логіці тоді і тільки тоді, коли її значень дорівнює \ (1 \) для будь-яких значень істинності вхідних в неї змінних.

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

Можна показати, що для того щоб довести правильність формули, досить знайти просту алгебру Хейтінга, елементи якої є множинами на простий площині \ (R ^ 2 \). У цій алгебрі операції \ (\ and \) і \ (\ or \) відповідають перетинанню і об'єднанню множин, а значенням формули \ (A \ rightarrow B \) є вираз \ ((A ^ C \ cap B) ^ \), тобто внутрішність перетину безлічі \ (B \) і доповнення безлічі \ (A \). Самим нижнім елементом є порожня множина, самим верхнім - універсум \ (R ^ 2 \). Заперечення зазвичай визначається як \ (\ neg A \ equiv A \ rightarrow \ empty \), тому заперечення редукується в вираз \ (A ^ \), тобто внутрішність доповнення безлічі \ (A \).

Наприклад, формула \ (\ neg (A \ and \ neg A) \) правильна, оскільки байдуже, яке безліч буде вибрано в якості значення безлічі \ (A \), значенням цієї формули буде вся двовимірна площину: $$ Value (\ neg (A \ and \ neg A)) = $$ $$ (Value (A \ and \ neg A)) ^ = $$ $$ (Value (A) \ cap Value (\ neg A)) ^ = $$ $ $ (X \ cap (Value (A)) ^) ^ = $$ $$ (X \ cap X ^) ^ $$

Одна теорема топології говорить про те, що \ (X ^ \) є підмножиною \ (X ^ C \), тому перетин множин порожньо: $$ \ empty ^ = (R ^ 2) ^ = R ^ 2 $$

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

Також можна показати, що закон виключеного третього неправильний в интуиционистской логіці. Для цього значенням терма \ (A \) необхідно зробити безліч \ (\ 0 \> \). В цьому випадку значенням заперечення \ (\ neg A \) буде внутрішність безлічі \ (\\), що є $\$. Значним формули \ (A \ or \ neg A \) (закон виключення третього), тобто значення об'єднання множин \ (\ 0 \> \) і \ (\\), що є $\$. У свою чергу останній отриманий вираз не тотожне всій площині \ (R ^ 2 \).

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

Семантика Крипкая [ред]