2.3: Методи доведення умовних пропозицій

Last updated
Save as PDF

Page ID: 65522

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

Кожна з теорем, які ми довели в розділі 2.1, є прикладами умовних суджень. Однак деякі висловлювання були замасковані під такі. Наприклад, теорема 2.3 говорить: «Сума двох послідовних цілих чисел непарна». Ми можемо переформулювати цю теорему як: «Якщо n Z, то n + (n + 1) непарна».

Проблема 2.47. Переформуйте теорему 2.7, щоб вона явно читалася як умовна пропозиція.

Кожен з доказів, які ви створили в розділі 2.1, мав однаковий формат, який ми називаємо прямим доказом.

Доказ скелета 2.48 (Доказ A = ⇒ B прямим доказом). Якщо ви хочете довести імплікацію A =⇒ B через пряме доказ, то структура доказу така.

Доказ. [Створити будь-які попередні припущення.] Припустимо, А.

... [Використовуйте визначення та відомі результати для отримання B]...

Тому Б.

Приділіть кілька хвилин, щоб переглянути докази, які ви написали в розділі 2.1, і подивитися, чи можете ви стати свідками структури Skeleton Proof 2.48 у своїх доказах.

Підсумок теореми 2.39 полягає в тому, що якщо ви хочете довести умовну пропозицію, ви можете довести його контрапозитивне. Такий підхід називають доказом протиставлення.

Доказ скелета 2.49 (Доказ A = ⇒ B за контрапозицією). Якщо ви хочете довести імплікацію A =⇒ B, доводячи його контрапозитивний ¬B =⇒ ¬A замість цього, то структура доказу така.

Доказ. [Створити будь-які попередні припущення.] Ми будемо використовувати доказ за контрапозицією.

Припустимо, ¬Б.

... [Використовуйте визначення та відомі результати для отримання ¬А]...

Тому, ¬А., Ми довели контрапозитив, а отже, якщо А, то Б.

Ми ввели логічні символи ¬,, ∨, =⇒, і ⇒, оскільки це забезпечує зручний спосіб обговорення формальності логіки. Однак при написанні математичних доказів слід уникати використання цих символів.

Проблема 2.50. Розглянемо наступне твердження:

Якщо x Z такий, що x2 непарний, то х непарний.

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

Припустимо, що х - парне ціле число.
Ми будемо використовувати доказ за контрапозицією.
Таким чином, x ² - це двічі ціле число.
Оскільки х = 2k, ми маємо, що х ² = (2k) ² = 4k ².
Оскільки k є цілим числом, 2k ² також є цілим числом.
За визначенням парного існує ціле число k таке, що x = 2k.
Ми довели контрапозитив, і, отже, бажане твердження вірно.
Припустимо, х Z.
За визначенням парного цілого числа x ^{2 є парним} цілим числом.
Зверніть увагу, що x2 = 2 (2k ²).

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

Теорема 2.51. Якщо n Z таке, що n ² парне, то n парне.

Теорема 2.52. Якщо n, m Z такий, що nm парний, то n парний або m парний.

Припустимо, що ми хочемо довести деяку пропозицію P (яка може бути чимось на кшталт A =⇒ B або навіть більш складною). Один підхід, який називається доказом протиріччям, полягає в тому, щоб припустити ¬P, а потім логічно вивести протиріччя форми Q¬Q, де Q - деяке судження. Оскільки це абсурд, припущення ¬P мало бути помилковим, тому P вірно. Складна частина доказу протиріччя полягає в тому, що зазвичай не очевидно, яким має бути твердження Q.

Скелет Доказ 2.53 (Доказ П протиріччям). Ось як виглядає загальна структура доказу протиріччям, якщо ми намагаємося довести пропозицію П.

Доказ. [Створити будь-які попередні припущення.] Заради протиріччя припустимо ¬П.

... [Використовуйте визначення та відомі результати для отримання деякого Q та його заперечення ¬Q.]...

Це протиріччя. Тому П.

Доказ протиріччям може бути корисним для доведення тверджень виду A =⇒ B, де ¬Б легше «взяти руки», оскільки ¬ (A =⇒ B) логічно еквівалентно A ¬B (див. Наслідок 2.41).

Скелет Доказ 2.54 (Доказ A = ⇒ B через протиріччя). Якщо ви хочете довести підтекст A =⇒ B через доказ протиріччям, то структура доказу така.

Доказ. [Створити будь-які попередні припущення.] Заради протиріччя припустимо A і ¬B.

... [Використовуйте визначення та відомі результати для отримання деякого Q та його заперечення ¬Q.]...

Це протиріччя. Тому якщо А, то Б.

Проблема 2.55. Припустимо, що x Z. розглянемо наступну пропозицію: Якщо х непарний, то 2 не ділить x.

(а) Доведіть контрапозитив цього твердження.

(б) Доведіть твердження, використовуючи доказ протиріччям.

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

Теорема 2.56. Припустимо, що x, y N. Якщо x ділить y, то x ≤ y.

Часто умовна пропозиція може бути доведена прямим доказом і за допомогою доказу протиріччя. Більшість математиків вважають прямий доказ більш елегантним, ніж доказ протиріччя. При наближенні до доказу умовного судження слід прагнути до прямого доказу. Загалом, якщо ви намагаєтеся довести A =⇒ B, використовуючи доказ протиріччям, і ви закінчуєте ¬B і B (що дає протиріччя), то це доказ того, що доказ протиріччя був непотрібним. З іншого боку, якщо

ви в кінцевому підсумку з ¬Q і Q, де Q не те саме, що B, то доказ протиріччя - розумний підхід. нам потрібно довести обидва

У світлі теореми 2.29, якщо ми хочемо довести біумову форми A ⇒ B, A =⇒ B і B =⇒ A. Ви завжди повинні дати зрозуміти читачеві, коли ви доводите кожне підтекст. Один з підходів полягає в тому, щоб позначити кожен піддоказ «(=⇒)» та «(=)» (включаючи дужки) відповідно. Іноді ви виявите, що доказ одного імплікації є саме зворотним доказом іншого. Якщо це станеться так, ви можете пропустити написання двох піддоказів і просто написати єдиний доказ, який об'єднує кожен крок за допомогою двоумовних. Такі докази майже завжди будуть коротшими, але можуть бути складними для написання красномовно. Завжди безпечною ставкою є написання окремого піддоказу для кожного підтексту.

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

Наступна теорема дає можливість отримати певний досвід написання доказів біумовних тверджень.

Теорема 2.57. Нехай n Z. Тоді n є парним якщо і тільки якщо 4 ділить n ².