2.5: Детальніше про кількісну оцінку
- Page ID
- 65531
При написанні математичних доказів ми явно не використовуємо символічне зображення заданого твердження з точки зору кванторів і логічних зв'язків. Тим не менш, наявність цього позначення в нашому розпорядженні дозволяє нам розділити абстрактний характер математичних пропозицій і надає нам спосіб говорити про загальну структуру, яка бере участь у побудові доказу.
Визначення 2.74. Дві кількісні пропозиції логічно еквівалентні, якщо вони мають однакову істинну цінність у кожному всесвіті дискурсу.
Проблема 2.75. Розглянемо пропозиції (x U) (x 2 − 4 = 0) і (x U) (x 2 − 2 = 0), де U - якийсь всесвіт дискурсу.
(а) Чи мають ці пропозиції однакову істинну цінність, якщо Всесвіт дискурсу є сукупністю дійсних чисел?
(б) Наведіть приклад всесвіту дискурсу таким чином, щоб пропозиції давали різні значення істини.
(c) Що ви можете зробити висновок про логічну еквівалентність цих пропозицій?
Варто вказати на важливе відмінність. Розглянемо пропозиції «Всі автомобілі червоні» і «Всі натуральні числа позитивні». Обидва вони є екземплярами логічної форми (x) P (x). Виявляється, перше судження помилкове, а друге - істинним; однак, не має сенсу надавати логічній формі значення істини. Логічна форма - це план конкретних пропозицій. Якщо ми обережні, має сенс поговорити про те, чи є дві логічні форми логічно рівнозначними. Наприклад, (x) (P (x) =⇒ Q (x)) логічно еквівалентно (x) (¬Q (x) =⇒ ¬P (x)), оскільки умовна пропозиція логічно еквівалентна його контрапозитивному (див. Теорему 2.39). Для фіксованих P (x) і Q (x) ці дві форми завжди матимуть однакове значення істини незалежно від всесвіту дискурсу. Якщо змінити P (x) і Q (x), то значення істинності може змінитися, але дві форми все одно погодяться.
Наступна теорема розповідає, як звести нанівець логічні форми за участю квантіфікаторів. Ваше доказ має включати кілька міні-аргументів. Наприклад, в частині (a) вам потрібно буде довести, що якщо ¬ (x) P (x) вірно, то (x) (x) (¬P (x)) також вірно.
Теорема 2.76. Нехай P (x) буде присудком у якомусь всесвіті дискурсу. Тоді
(а) ¬ (x) P (x) логічно еквівалентний (x) (¬P (x));
(b) ¬ (x) P (x) логічно еквівалентний (x) (¬P (x)).
Проблема 2.77. Звести нанівець кожне з наступних пропозицій. Нехтуйте цінністю істини та всесвітом дискурсу.
(а) (х) (х> 3)
(b) (x) (х є primex парний)
(c) Всі автомобілі червоного кольору.
(d) Кожен Вукі називається Чубакка.
(e) Деякі хіпі є республіканськими.
(f) Деякі птахи не сердяться.
(g) Не кожна відеоігра буде гнити ваш мозок.
(h) Для всіх x N, x 2+ x + 41 є простим.
(i) Існує x Z такий, що 1/x < Z.
(j) Немає функції f такої, що якщо f є безперервним, то f не диференціюється.
Використовуючи теорему 2.76 та наші попередні результати, що включають кількісну оцінку, ми можемо звести нанівець складні математичні пропозиції, працюючи зліва направо. Наприклад, якщо звести нанівець помилкове судження
(х R) (y R) (х + у = 0),
отримуємо пропозицію
¬ (х R) (y ¬ R) (х + у = 0),
що логічно еквівалентно
(х ¬ Р) (у ¬ Р) (х + у, 0)
і має бути правдою. Для більш складного прикладу розглянемо (помилкове) пропозицію
(x) [x > 0 =⇒ (y) (y < 0∧xy > 0)].
Тоді його заперечення
¬ (x) [x > 0 =⇒ (y) (y < 0∧xy > 0)]
логічно еквівалентний
(x) [х > 0¬ (y) (y < 0∧xy > 0)],
що логічно еквівалентно
(x) [x> 0( y) (y ≥ 0xy ≤ 0)].
Чи можете ви визначити теореми, які були використані в двох прикладах вище?
Проблема 2.78. Звести нанівець кожне з наступних пропозицій. Нехтуйте цінністю істини та всесвітом дискурсу.
(а) (n ÷ N) (м ÷ N) (м < n)
(b) Для кожного y R існує x R такий, що y = x 2.
(c) Для всіх y R, якщо y не від'ємний, то існує x R такий, що y = x 2.
(d) Для кожного x R існує y R такий, що y = x 2.
(e) Існує x R такий, що для всіх y R, y = x 2.
(f) Існує y R такий, що для всіх x R, y = x 2.
(г) (x, y, z Z) (xy рівноyz парний) =⇒ xz парний)
(h) Існує одружена особа х така, що для всіх одружених людей y, x одружений на y.
Проблема 2.79. Розглянемо наступну пропозицію в якомусь всесвіті дискурсу.
«Для всіх тупих воблерів x існує dinglehopper y такий, що якщо х не самородок, то y - це doofus».
Знайдіть заперечення цієї пропозиції, щоб воно включало в себе фразу «не дуфус».
Проблема 2.80. Розглянемо наступну пропозицію в якомусь всесвіті дискурсу.
«Якщо х і у обидва розумні, то xy не є витонченими».
Знайдіть контрапозитив цієї пропозиції так, щоб воно включало в себе фразу «не зухвалий».
На цьому етапі ми повинні мати можливість використовувати наше розуміння кількісної оцінки для побудови контрприкладів складних помилкових пропозицій та доказів складних істинних пропозицій. Ось деякі загальні доказові структури для різних логічних форм.
Доказ скелета 2.81 (Пряме доказ (x) P (x)). Ось загальна структура для прямого доказу пропозиції (x) P (x). Припустимо, U - це всесвіт дискурсу.
Доказ. [Створіть будь-які авансові припущення.] Нехай x U.
... [Використовувати визначення та відомі результати.]...
Тому P (x) вірно. Оскільки х був довільним, для всіх x, P (x).
Поєднуючи Skeleton Proof 2.81 з Skeleton Proof 2.48, ми отримуємо наступне доказ скелета.
Скелет Доказ 2.82 (Доказ (x) (A (x) = ⇒ B (x))). Нижче наведено загальну структуру для прямого доказу пропозиції (x) (A (x) =⇒ B (x). Припустимо, U - це всесвіт дискурсу.
Доказ. [Створіть будь-які авансові припущення.] Нехай x U. припустимо A (x).
... [Використовуйте визначення та відомі результати для отримання B (x)]...
Тому B (x).
Доказ скелета 2.83 (Доказ (x) P (x) протиріччям). Ось загальна структура для доказу пропозиції (x) P (x) через протиріччя. Припустимо, U - це всесвіт дискурсу.
Доказ. [Створіть будь-які авансові припущення.] Заради протиріччя припустимо, що існує x U такий, що ¬P (x).
... [Зробіть щось, щоб вивести протиріччя.]...
Це протиріччя. Тому для всіх х вірно P (x).
Доказ скелета 2.84 (Пряме доказ (x) P (x)). Ось загальна структура для прямого доказу пропозиції (x) P (x). Припустимо, U - це всесвіт дискурсу.
Доказ. [Створіть будь-які попередні припущення.]...
... [Використовуйте визначення, аксіоми та попередні результати, щоб вивести, що існує х, для якого P (x) є істинним; або якщо у вас є х, який працює, просто переконайтеся, що він робить.]...
Тому існує x U такий, що P (x).
Доказ скелета 2.85 (Доказ (x) P (x) протиріччям). Нижче наведено загальну структуру доказу пропозиції (x) P (x) через протиріччя. Припустимо, U - це всесвіт дискурсу.
Доказ. [Створіть будь-які авансові припущення.] Заради протиріччя припустимо, що для всіх x U, ¬P (x).
... [Зробіть щось, щоб вивести протиріччя.]...
Це протиріччя. Тому існує x U такий, що P (x).
Зауважте, що якщо Q (x) є присудком, для якого (x) Q (x) є помилковим, то контрприклад цієї пропозиції дорівнює показу (x) (¬Q (x)), що можна довести, дотримуючись структури Skeleton Proof 2.84.
Важливо зазначити, що іноді нам доведеться поєднувати різні методи доказування в одному доказі. Наприклад, якби ви хотіли довести судження форми (x) (P (x) =⇒ Q (x)) протиріччям, ми б почали з припущення, що існує x у всесвіті дискурсу такий, що P (x) та ¬Q (x).
Проблема 2.86. Визначте, чи є кожне з наступних тверджень істинним чи хибним. Якщо твердження вірно, доведіть це. Якщо твердження неправдиве, наведіть контрприклад.
(а) Для всіх n N, n 2 ≥ 5.
(b) Існує n N таких, що n 2 − 1 = 0.
(c) Існує x N такий, що для всіх y N, y ≤ x.
(г) Для всіх х Z, х 3 ≥ х.
(e) Для всіх n Z існує m Z такий, що n + m = 0.
(f) Існують цілі числа a і b такі, що 2a + 7b = 1.
(g) Не існує цілих чисел m і n таких, що 2m + 4n = 7.
(h) Для всіх a, b, c Z, якщо a ділить bc, то або a ділить b, або a ділить c.
(i) Для всіх a, b Z, якщо ab парний, то або a або b парний.
Проблема 2.87. Поясніть, чому наступне «доказ» не є вагомим аргументом.
Претензія. Для всіх x, y Z, якщо x і y парні, то x + y парні.
«Доказ». Припустимо, x, y Z такі, що х і у парні. Заради протиріччя припустимо, що x+y непарний. Тоді існує k ¬ Z такий, що x+y = 2k+1. Це означає, що (x+y) −2k = 1. Ми бачимо, що ліва частина рівняння навіть тому, що це різниця парних чисел. Однак права сторона непарна. Оскільки парне число не може дорівнювати непарному числу, ми маємо протиріччя. Тому х + у парний.
Іноді корисно розділити всесвіт дискурсу на кілька колекцій, щоб мати справу окремо. Роблячи це, важливо переконатися, що ваші випадки є вичерпними (тобто враховано кожен можливий елемент всесвіту дискурсу). В ідеалі ваші справи також будуть непоєднуваними (тобто ви не розглядали один і той же елемент не раз). Наприклад, якщо наш Всесвіт дискурсу являє собою набір цілих чисел, ми можемо окремо розглянути парні проти непарних цілих чисел. Якщо наш всесвіт дискурсу являє собою набір дійсних чисел, ми можемо розглянути раціональні проти ірраціональних чисел, або, можливо, негативні проти нуля проти і позитивні. Атакуючи доказ таким чином, часто називають доказом у випадках (або доказ виснаженням). Доказ випадків також може бути корисним при роботі з гіпотезами, що стосуються «або». Відзначимо, що використання доказу випадками обґрунтовано теоремою 2.30.
Якщо ви вирішили підійти до доказу, використовуючи випадки, обов'язково повідомте читачеві, що ви робите це, і організуйте своє доказ розумним чином. Зверніть увагу, що робити аналіз випадків слід уникати, якщо це можливо. Наприклад, хоча в доведенні теореми 2.11 допустимо окремо розглядати випадки того, чи є a парним числом проти непарного цілого числа, це абсолютно не потрібно. Щоб довести наступну теорему, ви можете розглянути два випадки.
Теорема 2.88. Для всіх n Z 3n 2 + n + 14 є парним.
Доведіть наступну теорему, доводячи контрапозитив, використовуючи два випадки.
Теорема 2.89. Для всіх n, m Z, якщо nm непарне, то n - непарне, а m - непарне.
Доводячи попередню теорему, ви, ймовірно, відчули деяке дежавю. Ви повинні були припустити, що «n є парним або m рівним» в якийсь момент вашого доказу. Перший випадок - «n is even», а другий - «m парне». (Зауважте, що вам не потрібно обробляти випадок, коли і n і m є навіть, оскільки два окремі випадки вже дають бажаний результат.) Докази для обох випадків ідентичні, за винятком того, що ролі n і m поміняються місцями. У таких випадках, як це, математики мають ярлик. Замість того, щоб писати два по суті однакові докази для кожного випадку, ви можете просто обробити один із випадків і вказати, що решта випадку випливає з майже ідентичного доказу. Найшвидший спосіб зробити це - використовувати фразу «Без втрати спільності припустимо..». Наприклад, ось доказ теореми 2.89, яка використовує цей підхід.
Доказ теореми 2.89. Доведемо контрапозитив. Нехай n, m Z і припустимо n парне або m парне. Без втрати спільності припустимо n парне. Тоді існує k ¬ Z такий, що n = 2k. Ми це бачимо\[nm = (2k)m = 2(km)\].
Оскільки k і m є цілими числами, км - ціле число. Це показує, що нм рівний. Ми довели контрапозитив, а отже, для всіх n, m Z, якщо nm непарний, то n непарний, а m - непарний.
Зауважте, що не було б доцільно використовувати підхід «без втрати загальності» для об'єднання двох випадків у доказі теореми 2.88, оскільки доказ другого випадку не такий простий, як обмін ролями символів у доказі першого випадку.
Бувають випадки, коли теорема буде пред'являти претензію про єдиність того чи іншого математичного об'єкта. Наприклад, у розділі 5.1 вам буде запропоновано довести, що як адитивні, так і мультиплікативні ідентичності (тобто 0 і 1) є унікальними (див. Теореми 5.2 і 5.3). Як інший приклад, Фундаментальна теорема арифметики (див. Теорема 6.17) стверджує, що кожне натуральне число більше 1 може бути виражено однозначно (аж до того порядку, в якому вони з'являються) як добуток одного або декількох простих чисел. Типовий підхід до доведення унікальності полягає в тому, щоб припустити, що потенційно є два об'єкти з бажаною властивістю, а потім показати, що ці об'єкти насправді рівні. Чи підходите ви до цього як до доказу протиріччя - справа смаку. Зазвичай використовується\(∃!\) як символічна абревіатура для «існує унікальне... таке, що».
Скелет Доказ 2.90 (Пряме доказ (! х) П (х)). Ось загальна структура для прямого доказу пропозиції (! х) Р (х). Припустимо, U - це всесвіт дискурсу.
Доказ. [Створіть будь-які попередні припущення.]...
... [Використовуйте визначення, аксіоми та попередні результати, щоб вивести, що існує х, для якого P (x) є істинним; або якщо у вас є х, який працює, просто переконайтеся, що він робить.]...
Тому існує x U такий, що P (x). Тепер, припустимо, x1, x2 U такі, що P (x1) і P (x2).
... [Доведіть, що x1 = x2.]...
Це означає, що існує унікальний х такий, що P (x).
Наступна теорема дає можливість практикувати доведення єдиності.
Теорема 2.91. Якщо c, a, r R такі, що c, 0 і r, a/c, то існує унікальний x R такий, що (ax+ 1)/(cx) = r.