3.4: Відхилення
- Page ID
- 64808
Ідея «спростування» насправді просто семантика — для того, щоб спростувати твердження, нам потрібно довести його заперечення.
Поки що ми обговорювали докази зовсім небагато, але приділяли дуже мало уваги дійсно величезному питанню. Якщо заяви, які ми намагаємося довести, є помилковими, жодних доказів ніколи не буде можливим. Дійсно, обов'язковою умовою розробки об'єкта з доказами є розробка хорошого «детектора брехні». Нам потрібно вміти вгадати, або швидко з'ясувати, чи є твердження істинним чи хибним. Якщо нам дано загальне кількісне твердження, перше, що потрібно зробити, це спробувати його для деяких випадкових елементів Всесвіту, в якому ми працюємо. Якщо ми трапляємося через значення, яке задовольняє гіпотези твердження, але не задовольняє висновку, ми знайшли те, що відомо як контрприклад.
Розглянемо наступне твердження про цілі числа та подільності:
\[∀a, b, c ∈ \mathbb{Z}, a| bc \implies a| b ∨ a| c.\]
Це формулюється як ПСК, так що гіпотеза ясно, ми шукаємо три цілі числа так, що перший ділить добуток інших двох. У наступній таблиці ми зібрали кілька значень для\(a\),\(b\) і\(c\) таких, що\(a| bc\).
| \(a\) | \(b\) | \(c\) | \(a| b ∨ a| c ?\) |
|---|---|---|---|
| \ (a\) ">\(2\) | \ (b\) ">\(7\) | \ (c\) ">\(6\) | \ (a| b ∨ a| с? \) ">\(\text{yes}\) |
| \ (a\) ">\(2\) | \ (b\) ">\(4\) | \ (c\) ">\(5\) | \ (a| b ∨ a| с? \) ">\(\text{yes}\) |
| \ (a\) ">\(3\) | \ (b\) ">\(12\) | \ (c\) ">\(11\) | \ (a| b ∨ a| с? \) ">\(\text{yes}\) |
| \ (a\) ">\(3\) | \ (b\) ">\(5\) | \ (c\) ">\(15\) | \ (a| b ∨ a| с? \) ">\(\text{yes}\) |
| \ (a\) ">\(5\) | \ (b\) ">\(4\) | \ (c\) ">\(15\) | \ (a| b ∨ a| с? \) ">\(\text{yes}\) |
| \ (a\) ">\(5\) | \ (b\) ">\(10\) | \ (c\) ">\(3\) | \ (a| b ∨ a| с? \) ">\(\text{yes}\) |
| \ (a\) ">\(7\) | \ (b\) ">\(2\) | \ (c\) ">\(14\) | \ (a| b ∨ a| с? \) ">\(\text{yes}\) |
Як зазначається в розділі 1.2, вище твердження пов'язане з тим, чи є a простим. Зверніть увагу, що в таблиці\(a\) відображаються тільки прості значення. Це досить широкий натяк. Знайдіть зустрічний приклад до «Гіпотеза»\(3.4.1\).
Можуть бути випадки, коли пошуки зустрічногоприкладу починають відчувати себе дійсно марними. Чи вважаєте ви, ймовірно, що твердження про натуральні числа може бути вірним для (більше, ніж) перших\(50\) чисел, але все ще бути помилковим?
\(∀n ∈ \mathbb{Z} + n^2 − 79n + 1601\)є основним.
Знайдіть зустрічний приклад до «Гіпотеза»\(3.4.2\)
Прихована всередині Евкліда доказ нескінченності простих чисел - послідовність. Нагадаємо, що в доказі ми вивели протиріччя, розглянувши число,\(N\) визначене
\[N = 1 + \prod_{k=1}^{n} p_k. \]
Визначити послідовність за
\[N_n = 1 + \prod_{k=1}^{n} p_k, \]
де\(\{p_1, p_2, . . . , p_n\}\) фактичні перші\(n\) прості числа. Першими декількома значеннями цієї послідовності є:
| \(n\) | \(N_n\) |
|---|---|
| \ (n\) ">\(1\) | \ (n_n\) ">\(1 + (2) = 3\) |
| \ (n\) ">\(2\) | \ (n_n\) ">\(1 + (2 · 3) = 7\) |
| \ (n\) ">\(3\) | \ (n_n\) ">\(1 + (2 · 3 · 5) = 31\) |
| \ (n\) ">\(4\) | \ (n_n\) ">\(1 + (2 · 3 · 5 · 7) = 211\) |
| \ (n\) ">\(5\) | \ (n_n\) ">\(1 + (2 · 3 · 5 · 7 · 11) = 2311\) |
| \ (n\) ">\(⋮\) | \ (n_n\) ">\(⋮\) |
Тепер, на доказ, ми вивели протиріччя, зазначивши, що\(N_n\) це набагато більше\(p_n\), ніж, тому, якщо\(p_n\) це найбільший простий, то випливає, що не\(N_n\) може бути простим - але те, що насправді виглядає так (просто подивіться на цю таблицю!) це те, що\(N_n\) насправді є основним для всіх\(n\).
Знайдіть зустрічний приклад до гіпотези,\(1 + \prod^{n}_{k=1} p_k\) яка сама по собі завжди просте.
Вправи:
Знайдіть поліном, який передбачає лише прості значення для досить великого діапазону вхідних даних.
Знайдіть контрприклад до Гіпотези,\(3.4.1\) використовуючи тільки повноваження\(2\).
Чергуюча сума факторіалів дає цікавий приклад послідовності цілих чисел.
\(1! = 1 \\ 2! − 1! = 1 \\ 3! − 2! + 1! = 5 \\ 4! − 3! + 2! − 1! = 19 \\ \text{et cetera}\)
Чи всі вони прості? (Після перших двох\(1\).)
Було припущено, що всякий раз, коли\(p\) є простим, також\(2^p − 1\) є простим. Знайдіть мінімальний зустрічний приклад.
True або false: Сума будь-яких двох ірраціональних чисел є ірраціональною. Доведіть свою відповідь.
True або false: Є два ірраціональних числа, сума яких є раціональною. Доведіть свою відповідь.
True або false: добуток будь-яких двох ірраціональних чисел є ірраціональним. Доведіть свою відповідь.
Правда чи брехня: Є два ірраціональних числа, твір яких є раціональним. Доведіть свою відповідь.
True або false: Всякий раз, коли ціле число n є дільником квадрата цілого числа\(m^2\), випливає, що\(n\) це\(m\) також дільник. (У символах,\(∀n ∈ \mathbb{Z}, ∀m ∈ \mathbb{Z}, n | m^2 \implies n | m.)\) Доведіть свою відповідь.
У вправі в розділі 3.2 ми довели, що квадратне рівняння\(ax^2 + bx + c = 0\) має два розв'язки if\(ac < 0\). Знайдіть зустрічний приклад, який показує, що цей підтекст не може бути замінений двозастережним.