Розділ 01: Основні правила для SL

Розробляючи систему доказів, ми могли б просто почати з диз'юнктивного силогізму та modus ponens. Всякий раз, коли ми виявили вагомий аргумент, який не можна було довести за допомогою правил, які ми вже мали, ми могли б ввести нові правила. Продовжуючи таким чином, ми мали б несистематичне захоплення сумки правил. Ми могли б випадково додати деякі дивні правила, і ми, безсумнівно, закінчимо з більшою кількістю правил, ніж нам потрібно.

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

Крім правил для кожного логічного оператора, ми також матимемо правило повторення. Якщо ви вже щось показали в ході доказу, правило повторення дозволяє повторити це на новому рядку. Наприклад:

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

Очевидно, що правило повторення не дозволить нам показати нічого нового. Для цього нам знадобиться більше правил. Інша частина цього розділу дасть правила введення та усунення для всіх речень зв'язків. Це дасть нам повну систему доказів для SL. Пізніше в розділі ми вводимо правила для квантіфікаторів та ідентичності.

Кон'юнкція

Подумайте на мить: що вам потрібно показати, щоб довести\(E\) &\(F\)?

Звичайно, ви можете показати\(E\) &,\(F\) доводячи\(E\) та окремо доводячи\(F\). Це відбувається, навіть якщо два сполучники не є атомними реченнями. Якщо ви можете довести [\(A\)(J) →\(V\)] і [(\(V\)→\(L\))\(F\) ↔ (\(N\)─)], то ви ефективно довели

[(\(A\)J) →\(V\)] & [(\(V\)→\(L\)) ↔ (\(F\)∨\(N\))].

Отже, це буде наше правило введення кон'юнкції, яке ми скорочуємо &I:

Рядок доказів повинен бути виправданий якимось правилом, і тут ми маємо «&I\(m\),»\(n\). Це означає: Введення кон'юнкції застосовується до лінії\(m\) та лінії\(n\). Це змінні, а не дійсні номери\(m\) рядків; це якийсь рядок і\(n\) якийсь інший рядок. У фактичному доказі рядки пронумеровані 1,2,3,... і правила повинні застосовуватися до певних номерів рядків. Однак, коли ми визначаємо правило, ми використовуємо змінні, щоб підкреслити точку, що правило може бути застосовано до будь-яких двох рядків, які вже є в доказі. Якщо у вас є\(K\) на рядку 8 та\(L\) на рядку 15, ви можете довести (\(K\)&\(L\)) в якийсь пізніше момент доказу з виправданням «& I 8, 15».

Тепер розглянемо правило ліквідації для кон'юнкції. Що ви маєте право зробити висновок з речення на кшталт\(E\) &\(F\)? Звичайно, ви маєте право зробити висновок\(E\); якби\(E\) &\(F\) були правдою, то\(E\) було б правдою. Аналогічним чином ви маєте право зробити висновок\(F\). Це буде наше правило усунення сполучників, яке ми скорочуємо &E:

Якщо у вас є сполучник на якомусь рядку доказу, ви можете використовувати &E для отримання будь-якого з кон'юнктів. Правило &E вимагає лише одного речення, тому ми пишемо один номер рядка як обґрунтування його застосування.

Навіть маючи лише ці два правила, ми можемо надати деякі докази. Розглянемо цей аргумент.

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

З передумови ми можемо отримати кожен з кон'юнктів за допомогою &E, доказ тепер виглядає так:

Правило &I вимагає, щоб у нас був доступний кожен з кон'юнктів десь у доказі. Вони можуть бути відокремлені один від одного, а з'являтися вони можуть в будь-якому порядку. Таким чином, застосовуючи правило &I до рядків 3 і 2, ми приходимо до бажаного висновку. Готовий доказ виглядає наступним чином:

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

диз'юнкція

Якби\(M\) були правдою, то\(M\) ∨ також\(N\) було б правдою. Отже, правило введення диз'юнкції (\(I\)─) дозволяє нам вивести диз'юнкцію, якщо у нас є одна з двох диз'юнктів:

Зверніть увагу, що\(\mathcal{B}\) може бути будь-яке речення. Отже, наступне є законним доказом:

Це може здатися дивним, що просто знаючи, що\(M\) ми можемо зробити висновок, який включає речення\(A\)\(B\), як, і rest— пропозиції, які не мають нічого спільного з\(M\). І все ж висновок випливає з I Це так і повинно бути: Істинні умови для диз'юнкції означають, що, якщо\(\mathcal{A}\) це правда, то\(\mathcal{A}\) ∨\(\mathcal{B}\) вірно незалежно від того, що\(\mathcal{B}\) є. Таким чином, висновок не може бути помилковим, якщо передумова була істинною; аргумент є дійсним.

Тепер розглянемо правило усунення диз'юнкції. Що можна зробити висновок з\(M\) ¬\(N\)? Ви не можете зробити висновок\(M\). Це може бути\(M\) істина, яка робить\(M\) ∨\(N\) правдою, як у прикладі вище, але це може не так. З\(M\)\(N\) одних тільки, ви не можете нічого зробити висновок ні про що,\(M\) ні\(N\) конкретно. Якби ви також знали, що це\(N\) помилково, однак, тоді ви могли б зробити висновок\(M\).

Це всього лише диз'юнктивний силогізм, це буде правило усунення диз'юнкції (∨\(E\)).

Умовні

Розглянемо цей аргумент:

Аргумент, безумовно, є дійсним. Яким має бути правило умовного введення, таким, щоб ми могли зробити такий висновок?

Ми починаємо доказ з того, що записуємо передумову аргументу і малюємо горизонтальну лінію, ось так:

Якби ми мали ¬\(R\) як подальшу передумову, ми могли б вивести\(F\) за правилом E. Ми не маємо ¬\(R\) як передумова цього аргументу, і ми не можемо вивести його безпосередньо з приміщення, яке ми робимо have— так що ми не можемо просто довести\(F\). Те, що ми зробимо замість цього, - це запустити доказ, доказ в межах основного доказу. Коли ми починаємо піддоказ, ми малюємо ще одну вертикальну лінію, щоб вказати, що ми більше не в головному доказі. Потім пишемо в припущенні на піддоказ. Це може бути все, що ми хочемо. Тут корисно буде припустити ¬\(R\). Наш доказ тепер виглядає так:

Важливо зауважити, що ми не стверджуємо, що довели ¬\(R\). Нам не потрібно писати в жодному обґрунтуванні для припущення рядка піддоказу. Ви можете думати про піддоказ як поставити питання: що ми могли б показати, якби ¬\(R\) були правдою? З одного боку, ми можемо вивести\(F\). Отже, ми робимо:

Це показало, що якби ми мали ¬\(R\) як передумову, то ми могли б довести\(F\). По суті, ми довели ¬\(R\) →\(F\). Таким чином, умовне введення правило (→I) дозволить нам закрити піддоказ і вивести ¬\(R\) →\(F\) в основному доказі. Наш остаточний доказ виглядає так:

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

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

Може здатися, що це доказ того, що ви можете зробити будь-які висновки\(\mathcal{B}\) з будь-якої передумови\(\mathcal{A}\). Коли вертикальна лінія для підвлаштування закінчується, підзахисний закривається. Для того, щоб завершити доказ, ви повинні закрити всі піддокази. І ви не можете закрити підзахисний і використовувати правило R знову на рядку 4, щоб отримати\(\mathcal{B}\) в основному доказі. Після того, як ви закриєте підзахисний пристрій, ви не можете повернутися до окремих рядків всередині нього.

Закриття піддоказ називається розрядженням припущень про це піддоказ. Тож ми можемо поставити крапку таким чином: Ви не можете завершити доказ, поки не вичерпаєте всі припущення, крім вихідних приміщень аргументу.

Звичайно, це законно:

Це не повинно здаватися таким дивним, хоча. Оскільки\(\mathcal{B}\) →\(\mathcal{B}\) - це тавтологія, жодне конкретне приміщення не повинно вимагати його дійсного отримання. (Дійсно, як ми побачимо, тавтологія випливає з будь-яких приміщень.)

Поставте в загальному вигляді, правило →I виглядає так:

Коли ми вводимо піддоказ, ми зазвичай пишемо те, що ми хочемо отримати в стовпці. Це просто для того, щоб ми не забули, чому ми почали піддоказ, якщо він триває п'ять або десять рядків. Не існує правила «хочу». Це записка для себе і формально не є частиною доказу.

Хоча завжди допустимо відкрити піддоказ з будь-яким припущенням, яке вам подобається, існує певна стратегія, яка бере участь у виборі корисного припущення. Починаючи піддоказ з довільним, дурним припущенням просто витратить рядки доказу. Наприклад, для того, щоб отримати умовний параметр →I, ви повинні припустити, що попередник умовного в піддоказ.

Правило →I також вимагає, щоб наслідком умовного був останній рядок піддоказу. Завжди допустимо закрити підзахисний пристрій і розрядити його припущення, але робити це буде не корисно, поки ви не отримаєте бажане.

Тепер розглянемо правило умовного усунення. Нічого не випливає з\(M\) →\(N\) поодинці, але якщо у нас є обидва\(M\) →\(N\) і\(M\), то ми можемо зробити висновок\(N\). Це правило, modus ponens, буде правилом умовного усунення (→E).

Тепер, коли у нас є правила для умовного, розглянемо цей аргумент:

Ми починаємо доказ з написання двох приміщень як припущення. Оскільки основним логічним оператором у висновку є умовний, можна розраховувати на використання правила →I. Для цього нам потрібно subproof— так що ми пишемо в попередні умовного як припущення про піддоказ:

Ми зробили\(P\) доступним, припускаючи його в незахищеному вигляді, що дозволяє нам використовувати →E на першій передумові. Це дає нам\(Q\), що дозволяє нам використовувати →E у другій передумові. Вивівши\(R\), закриваємо підрозетник. Припускаючи, що\(P\) ми змогли довести\(R\), тому ми застосовуємо правило →I і закінчуємо доказ.

Біумовні

Правила для біумовних будуть схожі на двоствольні варіанти правил для умовних.

Для того, щоб отримати\(W\) ↔\(X\), наприклад, ви повинні бути в змозі довести,\(X\) припускаючи\(W\) і довести,\(W\) припускаючи\(X\). Правило біумовного введення (↔ I) вимагає двох піддоказів. Піддокази можуть надходити в будь-якому порядку, і другий піддоказ не повинен надходити відразу після first— але схематично правило працює так:

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

заперечення

Ось простий математичний аргумент англійською мовою:

Припустимо, що існує якесь найбільше натуральне число. Називайте це\(A\).
Це число плюс один також є натуральним числом.
Очевидно, що\(A\) + 1 >\(A\).
Таким чином, існує натуральне число більше, ніж\(A\).
Це неможливо, так як\(A\) передбачається найбільшим натуральним числом.
.7. Немає найбільшого натурального числа.

Ця форма аргументу традиційно називається reductio. Його повна латинська назва - reductio ad absurdum, що означає «зведення до абсурду». У reductio, ми припускаємо щось заради argument— наприклад, що існує найбільше натуральне число. Потім ми показуємо, що припущення призводить до двох суперечливих речень - наприклад,\(A\) це найбільше натуральне число і що це не так. Таким чином ми показуємо, що початкове припущення повинно було бути помилковим.

Основні правила заперечення дозволять аргументи на кшталт цього. Якщо припустити щось і показати, що це призводить до суперечливих пропозицій, то ми довели заперечення припущення. Це правило введення заперечення (¬I):

Щоб правило застосовувалося, останні два рядки піддоказу повинні бути явним протиріччям: деяке речення слідує на наступному рядку його заперечення. Ми пишемо «for reductio» як записку для себе, нагадування про те, чому ми почали піддоказ. Формально це не є частиною доказу, і ви можете залишити його поза увагою, якщо знайдете це відволікаючим.

Щоб побачити, як працює правило, припустимо, ми хочемо довести закон непротиріччя: ¬ (\(G\)&¬\(G\)). Ми можемо довести це без будь-яких приміщень, негайно запустивши піддоказ. Ми хочемо застосувати ¬I до піддоказ, тому ми припускаємо (\(G\)&¬\(G\)). Потім ми отримуємо явне протиріччя від &E, доказ виглядає наступним чином:

Правило ¬Е працюватиме приблизно так само. Якщо припустити ¬\(\mathcal{A}\) і показати, що це призводить до протиріччя, ми ефективно довели\(\mathcal{A}\). Отже, правило виглядає наступним чином: