1.4: Докази

4. Докази

4.1 Проблема зі смисловими демонстраціями валідності

Враховуючи, що ми можемо перевірити аргумент на достовірність, може здатися, що у нас є повністю розвинена система вивчення аргументів. Однак існує значна практична складність з нашим семантичним методом перевірки аргументів за допомогою таблиць істинності (ви, можливо, вже відзначили, в чому полягає ця практична складність, коли ви робили проблеми 1e та 2e глави 3). Розглянемо наступний аргумент:

Елісон піде на вечірку.

Якщо Елісон піде на вечірку, то Беатріс піде.

Якщо Беатріс піде на вечірку, то Кеті піде.

Якщо Кеті піде на вечірку, то Діана піде.

Якщо Діана піде на вечірку, то Елізабет піде.

Якщо Елізабет піде на вечірку, то Фран піде.

Якщо Фран піде на вечірку, то буде Джада.

Якщо Джада піде на вечірку, то буде Хіларі.

Якщо Хілларі піде на вечірку, то Іо піде.

Якщо Іо піде на вечірку, то Джулі піде.

_____

Джулі піде на вечірку.

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

П

(Р → Q)

(Q→R)

(R → S)

(S → Т)

(Т→У)

(U → V)

(В → Ш)

(Ш → Х)

(X → Y)

_____

Y

Однак якщо ми збираємося перевірити цей аргумент, то таблиця істинності зажадає 1024 рядків! Це випливає безпосередньо з нашого спостереження, що для аргументів або пропозицій, що складаються з n атомних речень, таблиця істинності зажадає 2 n рядків. Цей аргумент містить 10 атомних речень. Таблиця істинності, яка перевіряє її дійсність, повинна мати 2 10 рядків і 2 10 = 1024. Крім того, було б тривіально розширити аргумент на інший, скажімо, десять кроків, але тоді таблиця істини, яку ми робимо, вимагатиме більше мільйона рядків!

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

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

Ідея зрозуміліша, коли ми її демонструємо. Метод введення нових пропозицій буде називатися «правилами виведення». Введемо наші перші правила висновку для умовного. Запам'ятайте таблицю істинності для умовного:

Φ	ψ	(Φ→ψ)
Т	Т	Т
Т	F	F
F	Т	Т
F	F	Т

Подивіться на це на мить. Якщо у нас є умовне подібне (P → Q) (дивлячись на таблицю істинності вище, пам'ятайте, що це означало б, що ми дозволяємо Φ бути P і ψ бути Q), чи знаємо ми, чи є істинним будь-яке інше речення? Від (P → Q) поодинці ми цього не робимо. Навіть якщо (P → Q) вірно, P може бути помилковим або Q може бути помилковим. Але що робити, якщо у нас є якась додаткова інформація? Припустимо, у нас є як приміщення (P → Q), так і P. Тоді ми б знали, що якби ці приміщення були правдивими, Q повинен бути правдою. Ми вже перевірили це таблицею істинності.

		приміщення	приміщення
П	Q	(Р → Q)	П	Q
Т	Т	Т	Т	Т
Т	F	F	Т	F
F	Т	Т	F	Т
F	F	Т	F	F

Перший рядок таблиці істинності є єдиним рядком, де всі приміщення є істинними; і для нього ми знаходимо, що Q є істинним. Це, звичайно, узагальнює до будь-якого умовного. Тобто ми маємо, що:

		приміщення	приміщення
Φ	ψ	(Φ→ψ)	Φ	ψ
Т	Т	Т	Т	Т
Т	F	F	Т	F
F	Т	Т	F	Т
F	F	Т	F	F

Тепер ми фіксуємо це розуміння не за допомогою таблиці істинності, а шляхом введення правила. Правило ми випишемо так:

(Φ → ψ)

Φ

_____

Ψ

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

Ми описуємо це, сказавши, що третій рядок є «похідним» від попередніх двох рядків, використовуючи правило висновку.

Це правило умовиводу старе. Тому ми застрягли з його усталеним, але не дуже просвітницьким назвою: «modus ponens». Таким чином, ми говоримо, для наведеного вище прикладу, що третій рядок походить від попередніх двох рядків за допомогою modus ponens.

4.2 Пряме доказ

Нам потрібна ще одна концепція: доказ. Зокрема, почнемо з самого фундаментального виду доказів, який називається «прямим доказом». Ідея прямого доказу така: записуємо як нумеровані рядки передумови нашого аргументу. Потім, після цього, ми можемо записати будь-який рядок, який виправданий застосуванням правила висновку до більш ранніх рядків у доказі. Коли ми записуємо свій висновок, ми закінчили.

Зробимо доказ простого аргументу вище, який має приміщення (P→Q) і P, і висновок Q. Починаємо з того, що записуємо приміщення і нумеруємо їх. Є корисний біт позначення, який ми можемо ввести в цей момент. Він відомий як «Fitch bar», названий на честь логіка Фредеріка Фітча, який розробив цю техніку. Вліво напишемо вертикальну смугу, з горизонтальною лінією, яка вказує на те, що приміщення знаходяться вище лінії.

\ [\ fitchprf {\ лінія [1] {(P\ lif Q)}\\\ рядок [2] {P}} {}\]» клас = «ql-img-відображений-рівняння швидкого латексного автоматичного формату» height="77" title="Відображено QuickLatex.com» width="94" src=» https://human.libretexts.org/@api/de...fb11864_l3.png "/>

Також корисно визначити, звідки взялися ці кроки. Ми можемо зробити це з невеликим поясненням, виписаним праворуч.

\ [\ fitchprf {\ лінія [1] {(P\ lif Q)} [приміщення]\\ pline [2.] {P} [приміщення]} {}\]» клас = «ql-img-відображений-рівняння швидкого латекс-автоформату» висота = «77" title="Відображено QuickLatex.com» width="422" src =» https://human.libretexts.org/@api/de...0581a3d_l3.png "/>

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

\ [\ fitchprf {\ лінія [1] {(P\ lif Q)} [приміщення]\\ pline [2.] {P} [приміщення]} {\ pline [3.] {Q}}\]» клас = «ql-img-відображений-рівняння швидкого латексного автоматичного формату» висота = «77" title="Відображено QuickLatex.com» width="422" src =» https://human.libretexts.org/@api/de...a819263_l3.png "/>

І, нарешті, ми хочемо, щоб читач зрозумів, яке правило ми використовували, тому ми додаємо це в наше пояснення, визначаючи правило та використовувані рядки.

\ [\ fitchprf {\ лінія [1] {(P\ lif Q)} [приміщення]\\ pline [2.] {P} [приміщення]} {\ pline [3.] {Q} [modus ponens, 1, 2]}\]» клас = «ql-img-відображений-рівняння швидкого латексного автоматичного формату» висота = «77" title="Відображено QuickLatex.com» width="511" src =» https://human.libretexts.org/@api/de...5cd7ddd_l3.png "/>

Це повний прямий доказ.

Зверніть увагу на кілька речей. Нумерація кожного рядка та пояснення праворуч - це бухгалтерський облік; вони не є частиною нашого аргументу, а скоріше використовуються для пояснення нашого аргументу. Однак завжди робіть їх тому, що важко зрозуміти докази без них. Крім того, зауважте, що наша ідея полягає в тому, що правило висновку може бути застосовано до будь-якого більш раннього рядка, включаючи самі лінії, отримані за допомогою правил виведення. Це не просто приміщення, до яких ми можемо застосувати правило висновку. Нарешті, зауважте, що ми встановили, що цей аргумент повинен бути дійсним. З приміщення, і правила висновку, що зберігає дійсність, ми дійшли висновку. Обов'язково висновок вірний, якщо приміщення справжні.

Довгий аргумент, з якого ми почали главу, тепер можна дати прямий доказ.

\ [\ fitchprf {\ лінія [1] {P} [приміщення]\\\ pline [2.] {(P\ lif Q)} [приміщення]\\ pline [3.] {(Q\ lif R)} [приміщення]\\ pline [4.] {(R\ lif S)} [приміщення]\\ pline [5.] {(S\ lif T)} [приміщення]\\ pline [6.] {(T\ lif U)} [приміщення]\\ pline [7.] {(V\ lif W)} [приміщення]\\ pline [8.] {(W\ lif X)} [приміщення]\\ pline [9.] {(X\ lif Y)} [приміщення]\\ pline [10.] {(Y\ lif X)} [приміщення]\\} {\ pline [11.] {Q} [режим роботи, 2, 1]\\\ pline [12.] {R} [режим поненса, 3, 11]\\\ pline [13.] {S} [режим поненса, 4, 12]\\\ pline [14.] {T} [режим поненса, 5, 13]\\\ pline [15.] {U} [режим поненса, 6, 14]\\\ pline [16.] {V} [режим поненса, 7, 15]\\\ pline [17.] {W} [режим роботи, 8, 16]\\ pline [18.] {X} [режим поненса, 9, 17]\\\ pline [19.] {Y} [modus ponens, 10, 18]}\]» клас = «ql-img-відображений-рівняння швидкого латексного автоматичного формату» висота = «451" title="Відображено QuickLatex.com» ширина = «530" src =» https://human.libretexts.org/@api/de...66a7395_l3.png "/>

З неодноразових застосувань modus ponens ми прийшли до висновку. Якщо рядки з 1 по 10 мають значення true, рядок 19 має бути true. Аргумент є справедливим. І ми завершили його з 19 кроків, на відміну від написання 1024 рядків таблиці істинності.

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

4.3 Інші правила умовиводу

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

		приміщення	приміщення
Φ	ψ	(Φ→ψ)	¬ψ	¬Φ
Т	Т	Т	F	F
Т	F	F	Т	F
F	Т	Т	F	Т
F	F	Т	Т	Т

(Згадайте, як ми заповнили таблицю правди. Ми посилалися на ті таблиці істинності, які використовуються для визначення «→» і «¬», а потім для кожного рядка цієї таблиці вище, ми заповнили значення в кожному стовпці на основі цього визначення.)

Те, що ми спостерігаємо з цієї таблиці істинності, полягає в тому, що коли обидва (Φ→ψ) і ¬ψ є істинними, то ¬Φ є істинним. А саме це можна побачити в останньому рядку таблиці істинності.

Це правило, як і останнє, старе, і має усталену назву: «modus tollens». Представляємо її схематично з

(Φ→ψ)

¬ψ

_____

¬Φ

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

Φ	¬¬Φ
Т	Т
F	F

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

Φ

_____

¬¬ Φ

і

¬¬ Φ

_____

Φ

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

Φ

_____

Φ

4.4 Приклад

Ось приклад, який буде використовувати всі три правила. Розглянемо наступний аргумент:

(Q→P)

(¬Q→R)

¬R

_____

П

Ми хочемо, щоб перевірити цей аргумент, щоб побачити, якщо він дійсний.

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

\ [\ fitchprf {\ лінія [1] {(Q\ lif P)} [приміщення]\\ pline [2.] {(\ не Q\ lif R)} [приміщення]\\\ лінія [3] {\ lnot R} [приміщення]\\} {}\]» клас = «ql-img-відображений-рівняння швидкого латекс-автоформату» висота = «121" title="Відображено QuickLatex.com» ширина = «422" src=» https://human.libretexts.org/@api/de...afa4d89_l3.png "/>

І, тепер, ми застосовуємо наші правила висновку. Іноді буває важко зрозуміти, як завершити доказ. У найгіршому випадку, коли ви не впевнені в тому, як діяти, ви можете застосувати всі правила, які ви бачите, застосовні, а потім оцінити, чи наблизилися ви до висновку; і повторити цей процес. Тут в будь-якому випадку є прямим доказом шуканого висновку.

\ [\ fitchprf {\ лінія [1] {(Q\ lif P)} [приміщення]\\ pline [2.] {(\ не Q\ lif R)} [приміщення]\\\ лінія [3] {\ not R} [приміщення]\\} {\ рядок [4]. {\ not\ not Q} [модуль доповнення, 2, 3]\\\ рядок [5] {Q} [подвійне заперечення, 4]\\\ pline [6.] {P} [modus ponens, 1, 5]\\}\]» клас = «ql-img-відображений-рівняння швидкого латекс-автоформату» висота = «187" назва = «Відображено QuickLatex.com» width="511" src =» https://human.libretexts.org/@api/de...c60d633_l3.png "/>

Розвиток навичок при заповненні доказів просто вимагає практики. Ви повинні прагнути робити стільки проблем, скільки зможете.

4.5 Проблеми

1. Завершіть пряму деривацію (також звану «прямим доказом») для кожного з наступних аргументів, показуючи, що вона є дійсною. Вам знадобляться правила modus ponens, modus tollens, і подвійне заперечення.
   1. Приміщення: ¬Q, (¬Q → S). Показати: S.
   2. Приміщення: (S → ¬Q), (P → S), ¬¬П. Показати: ¬Q.
   3. Приміщення: (Т → П), (Q → S), (S → T), ¬П. Показати: ¬Q.
   4. Приміщення: R, P, (P → (R → Q)). Показати: Q.
   5. Приміщення: (R → S) → Q), ¬Q, (¬ (R → S) → V). Шоу: V.
   6. Приміщення: (Р → (Q → R)), ¬ (Q → R). Показати: ¬P.
   7. Приміщення: (¬ (Q → R) → P), ¬P, Q. Показати: R.
   8. Приміщення: Р, (Р → Р), (Р → (R → Q)). Показати: Q.
2. У звичайній розмовній англійській мові напишіть свій власний вагомий аргумент принаймні з двома передумовами. Ваш аргумент повинен бути просто абзацом (а не впорядкованим списком речень або чимось іншим, схожим на логіку). Переведіть його в логіку пропозиції і використовуйте прямий доказ, щоб показати, що він дійсний.
3. У звичайній розмовній англійській мові напишіть свій власний вагомий аргумент принаймні з трьома передумовами. Ваш аргумент повинен бути просто абзацом (а не впорядкованим списком речень або чимось іншим, схожим на логіку). Переведіть його в логіку пропозиції і використовуйте прямий доказ, щоб показати, що він дійсний.
4. Зробіть свій власний ключ, щоб перевести в логіку пропозиції частини наступного аргументу, які виділені жирним шрифтом. Використовуючи прямий доказ, доведіть, що отриманий аргумент є дійсним.

Інспектор Тарскі сказав своєму помічнику, містеру Керролу: «Якщо у Вітгенштейна була бруд на чоботях, то він був у полі. Крім того, якщо Вітгенштейн був у полі, то він є головним підозрюваним у вбивстві Доджсона. Вітгенштейн мав бруд на чоботях. Зробимо висновок, Вітгенштейн є головним підозрюваним у вбивстві Доджсона. »