3.3: Непрямі докази

Last updated
Save as PDF

Page ID: 64138

$ \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}}$

Замість того, щоб доводити$p \Rightarrow q$ прямо, іноді простіше довести це побічно. Існує два види непрямих доказів: доказ контрапозитивним і доказ протиріччям.

Доказ контрапозитивного ґрунтується на тому, що імплікація еквівалентна його контрапозитиву. Тому замість того, щоб доводити$p \Rightarrow q$, ми можемо довести його контрапозитив$\overline{q} \Rightarrow \overline{p}$. Оскільки це підтекст, ми могли б використовувати прямий доказ:

Припустімо, що$\overline{q}$ це правда (отже, припустимо,$q$ є помилковим).

Показати, що$\overline{p}$ є істинним (тобто показати, що$p$ є помилковим).

Доказ може діяти наступним чином:

Доказ: Ми хочемо довести контрапозитив заявленого результату.

$q$Припустімо, помилково,.

. Тому$p$ є помилковим.

Приклад$\PageIndex{1}\label{eg:indirectpf-01}$

$n$Дозволяти ціле число. Покажіть,$n^2$ що якщо рівний,$n$ то теж рівний.

Рішення: Доказ контрапозитивним: Ми хочемо довести, що якщо$n$ непарний, то$n^2$ непарний. Якщо$n$ непарне, то$n=2t+1$ для деякого цілого числа$t$. Отже,\[n^2 = 4t^2+4t+1 = 2(2t^2+2t)+1\] це непарно. На цьому доказ завершено.

Приклад$\PageIndex{2}\label{eg:indirectpf-02}$

Показати, що якщо$n$ є додатним числом таким, що сума його позитивних дільників є$n+1$, то$n$ є простим.

Рішення: Доведемо контрапозитив даного твердження. Ми хочемо довести, що якщо$n$ є складовим, то сума його позитивних дільників не є$n+1$. $n$Дозволяти складеним числом. Тоді його дільники включають 1$n$, і принаймні один інший позитивний дільник,$x$ відмінний від 1 і$n$. Таким чином, сума його позитивних дільників є принаймні$1+n+x$. Оскільки$x$ є позитивним, ми збираємо, що\[1+n+x > 1+n.\] Ми виводимо, що сума дільників не може бути$n+1$. Тому, якщо сума дільників$n$ дорівнює точно$n+1$, то$n$ повинна бути простою.

Приклад$\PageIndex{3}\label{eg:indirectpf-03}$

$x$Дозволяти бути дійсним числом. Доведіть, що якщо$x^3-7x^2+x-7=0$, то$x=7$.

Рішення: Припустимо$x\neq7$, то\[x^3-7x^2+x-7 = x^2(x-7)+(x-7) = (x^2+1) (x-7) \neq 0.\] Таким чином, якщо$x^3-7x^2+x-7=0$, то$x=7$.

практичні вправи$\PageIndex{1}\label{he:indirectpf-01}$

$x$Дозволяти бути дійсним числом. Доведіть, що якщо$(2x^2+3)(x+5)(x-7)=0$, то або$x=-5$, або$x=7$.

практичні вправи$\PageIndex{2}\label{he:indirectpf-02}$

$y$Дозволяти$x$ і бути двома дійсними числами. Доведіть, що якщо$x\neq0$ і$y\neq0$, то$xy\neq0$.

Ще одним непрямим доказом є доказ протиріччя. Щоб довести це$p \Rightarrow q$, діємо наступним чином:

Припустимо,$p\Rightarrow q$ є помилковим; тобто припустимо, що$p$ це правда і$q$ є помилковим.

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

Як це доводить це$p\Rightarrow q$? Припускаючи, що логіка, що використовується на кожному кроці аргументу, є правильною, але ми все одно закінчуємо протиріччям, тоді єдиний можливий недолік повинен виходити з припущення, яке$p\Rightarrow q$ є помилковим. Отже,$p\Rightarrow q$ має бути правдою.

Ось як може виглядати типовий доказ протиріччя:

Доказ: Припустимо$ p \Rightarrow q$, що помилково. Тоді$p$ істинно і$q$ є помилковим. Тоді

.. що є протиріччям. Тому$ p \Rightarrow q$ має бути правдою.

Існує більш загальна форма доведення заяви$r$, яка не повинна бути підтекстом. Щоб довести судження$r$ протиріччям, дотримуємося наступних кроків:

$r$Припустимо, помилково.

Сперечаємося, поки не отримаємо протиріччя.

Доказ: Припустимо$r$, що помилково. Потім.

.. що є протиріччям. Тому$r$ має бути правдою.

Приклад$\PageIndex{4}\label{eg:indirectpf-04}$

Покажіть, що якщо$x^3-7x^2+x-7=0$, то$x=7$.

Рішення: Припустимо$x^3-7x^2+x-7=0$, ми хочемо показати, що$x=7$. Припустимо$x\neq7$$x-7\neq0$, значить, і\[0 = x^3-7x^2+x-7 = x^2(x-7)+(x-7) = (x^2+1)(x-7)\] мав на увазі те$x^2+1=0$, що неможливо. Тому ми повинні мати$x=7$.

Приклад$\PageIndex{5}\label{eg:indirectpf-05}$

Показати,$P$ що якщо точка не на прямій$L$, то існує рівно одна$P$ перпендикулярна лінія від до$L$.

Рішення: Припустимо, ми можемо знайти більше однієї перпендикулярної лінії від$P$ на$L$. Виберіть будь-які два з них і позначте їх перетину за допомогою$L$ як$Q$ і$R$. Потім у нас виходить трикутник$PQR$, де кути$PQR$ і$PRQ$ є обидва$90^\circ$. Це означає, що сума внутрішніх кутів трикутника$PQR$ перевищує$180^\circ$, що неможливо. Отже, є тільки одна перпендикулярна лінія від$P$ на$L$.

Приклад$\PageIndex{6}\label{eg:indirectpf-06}$

Покажіть, що якщо$x^2<5$, то$|x|<\sqrt{5}$.

Рішення: Припустимо$x^2<5$, ми хочемо показати, що$|x|<\sqrt{5}$. Припустимо, навпаки, у нас є$|x|\geq\sqrt{5}$. Тоді або$x\geq\sqrt{5}$, або$x\leq-\sqrt{5}$. Якщо$x\geq\sqrt{5}$, то$x^2\geq5$. Якщо$x\leq-\sqrt{5}$, у нас знову є$x^2\geq5$. У будь-якому випадку у нас є протиріччя. Звідси$|x|<\sqrt{5}$.

практичні вправи$\PageIndex{3}\label{he:indirectpf-03}$

Доведіть, що якщо$x^2\geq49$, то$|x|\geq7$.

Приклад$\PageIndex{7}\label{eg:indirectpf-07}$

Доведіть, що логічна формула\[[(p\Rightarrow q) \wedge p] \Rightarrow q\] - це тавтологія.

Рішення

Припустимо$[(p\Rightarrow q) \wedge p] \Rightarrow q$, є помилковим для деяких тверджень$p$ і$q$. Тоді знаходимо

$(p\Rightarrow q) \wedge p$вірно, і
$q$є помилковим.

$(p\Rightarrow q) \wedge p$Щоб кон'юнкція була правдою, нам потрібно

$p\Rightarrow q$щоб бути правдою, і
$p$щоб бути правдою.

Маючи$p$ істинний і$q$ хибний, зробить$p\Rightarrow q$ помилковим. Це прямо суперечить тому, що ми знайшли. Тому логічна формула$[(p\Rightarrow q) \wedge p] \Rightarrow q$ завжди вірна, звідси і є тавтологія.

Приклад$\PageIndex{8}\label{eg:indirectpf-08}$

Доведіть, протиріччям,$x$ що якщо$y$ раціонально і нераціонально,$x+y$ то нераціонально.

Рішення: $x$Дозволяти раціональне число і$y$ ірраціональне число. Ми хочемо показати, що$x+y$ це нераціонально. Припустимо, навпаки,$x+y$ це раціонально. Потім\[x+y = \frac{m}{n}\] для деяких цілих чисел$m$ і$n$, де$n\neq0$. Так як$x$ є раціональним, у нас також є\[x = \frac{p}{q}\] для деяких цілих чисел$p$ і$q$, де$q\neq0$. Звідси випливає, що\[\frac{m}{n} = x+y = \frac{p}{q} + y.\] звідси,\[y = \frac{m}{n}-\frac{p}{q} = \frac{mq-np}{nq},\] де$mq-np$ і$nq$ обидва цілі числа, з$nq\neq0$. Це робить$y$ раціональним, що суперечить припущенню, яке$y$ є ірраціональним. Таким чином,$x+y$ не може бути раціональним, воно повинно бути нераціональним.

практичні вправи$\PageIndex{4}\label{he:indirectpf-04}$

Доведіть, що\[\sqrt{x+y} \neq \sqrt{x}+\sqrt{y}\] для будь-яких позитивних дійсних чисел$x$ і$y$.

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

Приклад$\PageIndex{9}\label{eg:indirectpf-09}$

Доведіть, що$\sqrt{2}$ це нераціонально.

Рішення: Припустимо, навпаки,$\sqrt{2}$ раціонально. Тоді ми можемо записати\[\sqrt{2} = \frac{m}{n}\] для деяких позитивних цілих чисел$m$$m$ і$n$ таких, що і$n$ не мають спільного дільника, крім 1 (отже, в$\frac{m}{n}$ найпростішому терміні). Квадратування обох сторін і перехресне множення дає\[2n^2 = m^2.\] Таким чином, 2 ділить$m^2$. Отже, 2 повинні також ділитися$m$. Тоді ми можемо написати$m=2s$ для деякого цілого числа$s$. Рівняння вище стає\[2n^2 = m^2 = (2s)^2 = 4s^2.\] Отже,\[n^2 = 2s^2,\] що означає, що 2 ділить$n^2$; таким чином, 2 також ділиться$n$. Ми довели, що обидва$m$ і$n$ діляться на 2. Це суперечить$m$ припущенню, що і$n$ не мають спільного дільника. Тому$\sqrt{2}$ повинен бути нераціональним.

практичні вправи$\PageIndex{5}\label{he:indirectpf-06}$

Доведіть, що$\sqrt{3}$ це нераціонально.

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

Приклад$\PageIndex{10}\label{eg:indirectpf-10}$

Покажіть, що не$x^2+4x+6=0$ має реального рішення. У символах покажіть, що$\nexists x\in\mathbb{R},(x^2+4x+6=0)$.

Рішення

Розглянемо наступні докази протиріччя:

Припустимо, існує дійсне число$x$ таке, що$x^2+4x+6=0$.
За допомогою числення можна показати, що функція $f (x) =x^2+4x+6$
має абсолютний мінімум at$x=-2$. Таким чином,$f(x) \geq f(-2) = 2$ для
будь-якого$x$. Це суперечить припущенню, що існує$x$
таке, що$x^2+4x+6=0$. Таким чином, не$x^2+4x+6=0$ має реального рішення.

Уважний огляд виявляє, що нам насправді не потрібні докази протиріччя. Суть доказу полягає в тому, що$x^2+4x+6 \geq 2$ для всіх$x$. Це вже показує, що ніколи не$x^2+4x+6$ може бути нулем. Простіше скористатися прямим доказом, наступним чином.

Використовуючи числення, ми знаходимо, що функція$f(x)=x^2+4x+6$ має
абсолютний мінімум при$x=-2$. Тому для будь-якого$x$, у нас завжди є
$f(x) \geq f(-2) = 2$. Значить, не існує$x$ такого, що
$x^2+4x+6=0$.

Чи згодні ви, що другий доказ (прямий доказ) більш елегантний?

Нагадаємо, що двозастережне твердження$p\Leftrightarrow q$ складається з двох наслідків$p\Rightarrow q$ і$q\Rightarrow p$. Отже, щоб довести$p\Leftrightarrow q$, нам потрібно встановити ці два «напрямки» окремо.

Приклад$\PageIndex{11}\label{eg:indirectpf-11}$

$n$Дозволяти ціле число. Доведіть,$n^2$ що навіть якщо і тільки$n$ якщо навіть.

Рішення

($\Rightarrow$) Спочатку доведемо, що якщо$n^2$ рівний, то$n$ повинен бути парним. Доведемо його контрапозитив: якщо$n$ непарний, то$n^2$ непарний. Якщо$n$ непарний, то ми можемо написати$n=2t+1$ для деякого цілого числа$t$. Тоді\[n^2 = (2t+1) = 4t^2+4t+1 = 2(2t^2+2t)+1,\] де$2t^2+2t$ - ціле число. Таким чином,$n^2$ це непарно.

($\Leftarrow$) Далі ми доведемо, що якщо$n$ парний, то$n^2$ парний. Якщо$n$ парний, ми можемо написати$n=2t$ для деякого цілого числа$t$. Тоді\[n^2 = (2t)^2 = 4t^2 = 2\cdot 2t^2,\] де$2t^2$ - ціле число. Отже,$n^2$ навіть, що завершує доказ.

практичні вправи$\PageIndex{6}\label{he:indirectpf-07}$

$n$Дозволяти ціле число. Доведіть, що$n$ це непарно, якщо і тільки якщо$n^2$ непарно.

Резюме та огляд

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

вправа$\PageIndex{1}\label{ex:indirectpf-01}$

$n$Дозволяти ціле число. Доведіть,$n^2$ що якщо рівний, то$n$ повинен бути рівним. Використовувати

Доказ контрапозитивним.
Доказ протиріччя.

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

вправа$\PageIndex{2}\label{ex:indirectpf-02}$

$n$Дозволяти ціле число. Покажіть,$n^2$ що якщо кратне 3, то також$n$ повинно бути кратним 3. Використовувати

Доказ контрапозитивним.
Доказ протиріччя.

вправа$\PageIndex{3}\label{ex:indirectpf-03}$

$n$Дозволяти ціле число. Доведіть, що якщо$n$ парний, то$n^2=4s$ для деякого цілого числа$s$.

вправа$\PageIndex{4}\label{ex:indirectpf-04}$

$n$Дозволяти$m$ і бути цілими числами. Показати, що$mn=1$ означає, що$m=1$ або$m=-1$.

вправа$\PageIndex{5}\label{ex:indirectpf-05}$

$x$Дозволяти бути дійсним числом. Доведіть контрапозитивним: якщо$x$ нераціонально,$\sqrt{x}$ то нераціонально. Застосовуйте цей результат, щоб показати, що$\sqrt[4]{2}$ є ірраціональним, використовуючи припущення, яке$\sqrt{2}$ є ірраціональним.

вправа$\PageIndex{6}\label{ex:indirectpf-06}$

$y$Дозволяти$x$ і бути дійсними числами такі, що$x\neq0$. Доведіть,$x$ що якщо раціонально, і$y$ нераціонально,$xy$ то нераціонально.

вправа$\PageIndex{7}\label{ex:indirectpf-07}$

Доведіть, що$\sqrt{5}$ це нераціонально.

вправа$\PageIndex{8}\label{ex:indirectpf-08}$

Доведіть, що$\sqrt[3]{2}$ це нераціонально.

вправа$\PageIndex{9}\label{ex:indirectpf-09}$

$b$Дозволяти$a$ і бути дійсними числами. Покажіть, що якщо$a\neq b$, то$a^2+b^2 \neq 2ab$.

вправа$\PageIndex{10}\label{ex:indirectpf-10}$

Використовуйте протиріччя, щоб довести, що для всіх цілих$k\geq1$ чисел\[2\sqrt{k+1} + \frac{1}{\sqrt{k+1}} \geq 2\sqrt{k+2}.\]

вправа$\PageIndex{11}\label{ex:indirectpf-11}$

$n$Дозволяти$m$ і бути цілими числами. Покажіть,$mn$ що навіть якщо і тільки тоді$m$, коли навіть або$n$ навіть.

вправа$\PageIndex{12}\label{ex:indirectpf-12}$

$y$Дозволяти$x$ і бути дійсними числами. Покажіть, що$x^2+y^2=0$ якщо і тільки якщо$x=0$ і$y=0$.

вправа$\PageIndex{13}\label{ex:indirectpf-13}$

Доведіть, що, якщо$x$ є дійсним числом такі$0<x<1$, що, то$x(1-x)\leq\frac{1}{4}$.

вправа$\PageIndex{14}\label{ex:indirectpf-14}$

$n$Дозволяти$m$ і бути додатними цілими числами, такими, що 3 ділить$mn$. Покажіть, що 3 ділить$m$, або 3 ділить$n$.

вправа$\PageIndex{15}\label{ex:indirectpf-15}$

Доведіть, що логічна формула\[(p\Rightarrow q) \vee (p\Rightarrow \overline{q})\] - це тавтологія.

вправа$\PageIndex{16}\label{ex:indirectpf-16}$

Доведіть, що логічна формула\[[(p\Rightarrow q) \wedge (p\Rightarrow \overline{q})] \Rightarrow \overline{p}\] - це тавтологія.