3.2: Прямі докази

Last updated
Save as PDF

Page ID: 64132

\( \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}}\)

Щоб показати, що твердження\(q\) є істинним, виконайте наступні дії:

Або знайти результат, який стверджує\(p \Rightarrow q\), або довести, що\(p\Rightarrow q\) це правда.
Покажіть або переконайтеся, що\(p\) це правда.
Зробіть висновок, що\(q\) має бути правдою.

Логіка дійсна, тому що якщо\(p \Rightarrow q\) істинно і\(p\) є істинним, то\(q\) має бути істинним. Символічно ми говоримо, що логічна формула\[[(p \Rightarrow q) \wedge p ] \Rightarrow q\] - це тавтологія (ми можемо легко переконатися в цьому за допомогою таблиці істинності). Символічно ми представляємо аргумент як\[\begin{array}{cl} & p \Rightarrow q \\ & p \\ \hline \therefore & q \end{array}\] Такий аргумент називається modus ponens або закон відстороненості.

Приклад\(\PageIndex{1}\label{eg:directpf-01}\)

Аргумент

\(b^2>4ac \Rightarrow ax^2+bx+c=0\)має два реальних рішення.

\(x^2-5x+6\)задовольняє\(b^2>4ac\).

\(\therefore\) \(x^2-5x+6=0\)має два реальних рішення.

є прикладом modus ponens.

Зрозуміло, що наслідки відіграють важливу роль у математичних доказах. Якщо у нас є послідовність наслідків, ми могли б об'єднати їх «голова до хвоста», щоб сформувати інший підтекст:\[\begin{array}{cl} & p \Rightarrow q \\ & q \Rightarrow r \\ \hline \therefore & p \Rightarrow r \end{array}\] Це називається законом силогізму.

Приклад\(\PageIndex{2}\label{eg:directpf-02}\)

Аргумент

Німецькі вівчарки - собаки.

Собаки - ссавці.

Ссавці - хребетні.

\(\therefore\) Німецькі вівчарки - хребетні.

діє через закон силогізму.

Велике питання полягає в тому, як ми можемо довести підтекст? Самим основним підходом є прямий доказ:

Припустімо\(p\), що це правда.

Вивести з\(p\) цього\(q\) вірно.

Важливо пам'ятати: використовуйте інформацію, отриману з,\(p\) щоб показати, що\(q\) це правда. Ось як може виглядати типовий прямий доказ:

Доказ: Припустімо\) p\) вірно. Потім.

Через те\(p\), що ми знаходимо.

. Тому\(q\) вірно.

Приклад\(\PageIndex{3}\label{eg:directpf-03}\)

Доведіть, що якщо\(m\times n\) шахова дошка може бути повністю покрита не перекриваються доміно, то\(mn\) повинна бути рівною.

Рішення: Припустимо, що шахова дошка може бути покрита не перекриваються доміно, і нехай\(t\) буде кількість доміно, які покривають шахову дошку. Тоді шахова дошка повинна містити\(2t\) квадрати. Значить\(mn=2t\), що означає\(mn\) має бути парне число.

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

Визначення

Ціле число є парним, якщо його можна записати як\(2q\) для деякого цілого числа\(q\), і непарне, якщо його можна записати як\(2q+1\) для деякого цілого числа\(q\).

Ми не повинні використовувати для\(q\) позначення цілого числа, яке при множенні на 2 виробляє парне ціле число. Будь-яка буква буде працювати, за умови, що ми згадуємо це ціле число. Наприклад, якщо\(n\) парне ціле число, то ми можемо записати\(n=2t\) для деякого цілого числа\(t\). Поняття парних цілих чисел можна додатково узагальнити.

Визначення

\(m\)Дозволяти бути ненульовим цілим числом. Ціле число, як кажуть, кратне,\(m\) якщо його можна записати як\(mq\) для деякого цілого числа\(q\).

Тепер ми готові вивчити більше прикладів.

Приклад\(\PageIndex{4}\label{eg:directpf-04}\)

Показати, що квадрат непарного цілого числа непарний.

Рішення: \(n\)Дозволяти непарне ціле число. Потім\(n=2t+1\) для деякого цілого числа\(t\), а\[n^2 = (2t+1)^2 = 4t^2+4t+1 = 2(2t^2+2t)+1,\] де\(2t^2+2t\) - ціле число. Отже,\(n^2\) це непарно.

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

\(n\)Дозволяти ціле число. Показати, що якщо\(n\) непарний, то\(n^3\) непарний.

Приклад\(\PageIndex{5}\label{eg:directpf-05}\)

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

Рішення: \(y\)Дозволяти\(x\) і бути двома непарними цілими числами. Ми хочемо довести, що\(xy\) це дивно. Потім\(x=2s+1\) і\(y=2t+1\) для деяких цілих чисел\(s\) і\(t\), а\[xy = (2s+1)(2t+1) = 4st+2s+2t+1 = 2(2st+s+t)+1,\] де\(2st+s+t\) - ціле число. Тому\(xy\) це непарно.

У цьому доказі нам потрібно використовувати дві різні величини\(s\) і\(t\) описати\(x\) і\(y\) тому, що вони не повинні бути однаковими. Якщо ми пишемо\(x=2s+1\) і\(y=2s+1\), ми фактично говоримо, що\(x=y\). Ми повинні підкреслити, що\(s\) і\(t\) є цілими числами, тому що просто кажучи\(x=2s+1\) і\(y=2t+1\) не гарантує\(x\) і\(y\) непарні. Наприклад, парне число 4 може бути записано як\(2\cdot\frac{3}{2}+1\), який має форму\(2s+1\). Очевидно, що 4 не дивні. Незважаючи на те, що ми можемо написати число у формі\(2s+1\), це не обов'язково означає, що число має бути непарним, якщо ми не знаємо з упевненістю, що\(s\) це ціле число. Цей приклад ілюструє важливість звернення уваги на деталі в нашому написанні.

Приклад\(\PageIndex{6}\label{directpf-06}\)

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

Рішення: Припустимо\(x^3-7x^2+x-7=0\). Так як\[x^3-7x^2+x-7 = x^2(x-7)+(x-7) = (x^2+1)(x-7),\] якщо вона дорівнює нулю, нам потрібно або\(x^2+1=0\), або\(x-7=0\). Оскільки ніколи не\(x^2+1\) може бути нулем, ми повинні мати\(x-7=0\); таким чином\(x=7\).

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

Покажіть, що якщо\(x^3+6x^2+12x+8=0\), то\(x=-2\).

Останній приклад демонструє методику, яка називається доказом випадків. Є дві можливості, а саме: або (i)\(x^2+1=0\), або (ii)\(x-7=0\). Остаточний висновок робиться після того, як ми вивчимо ці два випадки окремо.

Приклад\(\PageIndex{7}\label{eg:directpf-07}\)

Показати, що якщо ціле число\(n\) не ділиться на 3, то\(n^2-1\) має бути кратним 3.

Зауваження

Лист\(n\) був використаний для ідентифікації цілого числа, яке нас цікавить, і воно з'являється в гіпотезі про підтекст, який ми хочемо довести. Тим не менш, багато авторів починали б свої докази зі знайомої фрази «Нехай\(n\) буде...».

Відповідь

\(n\)Дозволяти ціле число, яке не ділиться на 3. При його діленні на 3 залишок дорівнює 1 або 2. Отже,\(n=3q+1\) або\(n=3q+2\) для деякого цілого числа\(q\).

Випадок 1: Якщо\(n=3q+1\) для деякого цілого числа\(q\), то\[n^2-1 = 9q^2+6q = 3 (3q^2+2q),\] де\(3q^2+2q\) є ціле число.

Випадок 2: Якщо\(n=3q+2\) для деякого цілого числа\(q\), то\[n^2-1 = 9q^2+12q+3 = 3(3q^2+4q+1),\] де\(3q^2+4q+1\) є ціле число.

В обох випадках ми показали, що\(n^2-1\) це кратне 3.

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

Покажіть,\(n^3+n\) що навіть для всіх\(n\in\mathbb{N}\).

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

Покажіть,\(n(n+1)(2n+1)\) що ділиться на 6 для всіх\(n\in\mathbb{N}\).

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

Закриваємо нашу дискусію двома поширеними помилками (логічними помилками). Перший - це помилка зворотного або заперечення попереднього:\[\begin{array}{cl} & p \Rightarrow q \\ & \overline{p} \\ \hline \therefore & \overline{q} \end{array}\] це фактично доводить зворотне\(\overline{p}\Rightarrow \overline{q}\), яке, як ми знаємо, логічно не еквівалентно початковому підтексту. Значить, це неправильний метод доведення імплікації.

Приклад\(\PageIndex{8}\label{eg:directpf-08}\)

Є наступний аргумент

Словники цінні.

Ця книга не є словником.

\(\therefore\) Ця книга не є цінною.

Дійсний? Чому?

Ще одна поширена помилка відома як помилка зворотного або твердження наслідку:\[\begin{array}{cl} & p \Rightarrow q \\ & q \\ \hline \therefore & p \end{array}\] Це лише доводить зворотне\(q\Rightarrow p\). Оскільки зворотне логічно не еквівалентно оригінальному підтексту, це неправильний спосіб довести підтекст.

Приклад\(\PageIndex{9}\label{eg:directpf-09}\)

Чи є цей аргумент

Жодне ліки не смакує.

Цей напій поганий на смак.

\(\therefore\) Це повинно бути ліки.

вагомий аргумент? Чому?

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

Щоб довести підтекст\(p\Rightarrow q\), почніть з припущення, що\(p\) це правда. Використовуйте інформацію з цього припущення разом з будь-якими іншими відомими результатами, щоб показати, що це також\(q\) повинно бути правдою.
При необхідності ви можете\(p\) розірватися на кілька\(p_1, p_2, \ldots\,\) випадків і довести кожен підтекст\(p_i\Rightarrow q\) (окремо, по одному), як зазначено вище.
Обов'язково пишіть математичні вирази чітко. Використовуйте різні змінні, якщо задіяні величини можуть бути неоднаковими.
Для початку запишіть надану інформацію, припущення і те, що ви хочете довести.
На наступному етапі використовуйте визначення при необхідності, і перепишіть інформацію в математичні позначення. Справа в тому, спробуйте отримати деякі математичні рівняння або логічні твердження, якими ми можемо маніпулювати.

Вправа\(\PageIndex{1}\label{ex:directpf-01}\)

Довести або спростувати:\(2^n+1\) є простим для всіх невід'ємних цілих чисел\(n\).

Вправа\(\PageIndex{2}\label{ex:directpf-02}\)

Показати, що для будь-якого цілого числа\(n\geq5\), цілих чисел\(n\)\(n+2\) і\(n+4\) не може бути усіма простими числами.

Підказка: Якщо\(n\) кратне 3, то\(n\) сам є складовим, і доказ буде повним. Таким чином, ми можемо припустити\(n\), що не ділиться на 3. Тоді як би\(n\) виглядали, і, що можна сказати про\(n+2\) і\(n+4\)?

Вправа\(\PageIndex{3}\label{ex:directpf-03}\)

\(n\)Дозволяти ціле число.

Покажіть, що якщо\(n\) непарний, то\(n^2\) теж непарний.
Покажіть, що якщо\(n\) непарний, то\(n^4\) теж непарний.
Наслідком є результат, який можна легко отримати з іншого результату. Вивести (b) як наслідок (a).
Покажіть, що якщо\(m\) і\(n\) непарні, то так і є\(mn\).
Покажіть,\(m\) що якщо парне, а\(n\) непарне,\(mn\) то парне.

Вправа\(\PageIndex{4}\label{ex:directpf-04}\)

Доведіть, що для будь-якого непарного цілого числа\(n\), число\(2n^2+5n+4\) повинно бути непарним.

Вправа\(\PageIndex{5}\label{ex:directpf-05}\)

\(n\)Дозволяти ціле число.

Доведіть,\(n\) що якщо кратна 3,\(n^2\) то також кратна 3.
Доведіть,\(n\) що якщо кратна 7,\(n^3\) то також кратна 7.

Вправа\(\PageIndex{6}\label{ex:directpf-06}\)

Доведіть,\(n\) що якщо не кратна 3,\(n^2\) то також не кратна 3.

Підказка: Якщо\(n\) не кратна 3, то\(n=3q+1\) або\(n=3q+2\) для деякого цілого числа\(q\).

Вправа\(\PageIndex{7}\label{ex:directpf-07}\)

Використовуйте факти, які

\(\sqrt{2}\)є ірраціональним, і

якщо\(x\) нераціонально, то\(\sqrt{x}\) теж нераціонально,

довести, що\(\sqrt[8]{2}\) нераціонально.

Вправа\(\PageIndex{8}\label{ex:directpf-08}\)

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

Якщо\(x\) і\(y\) є цілими числами такі\(x^2>y^2\), що, то\(x>y\).
Якщо\(n\) є натуральним числом, то\(n^2+n+41\) є простим.

Вправа\(\PageIndex{9}\label{ex:directpf-09}\)

Поясніть, чому такі аргументи є недійсними:

\(n\)Дозволяти ціле число. Якщо\(n^2\) непарний, то\(n\) непарний. Тому\(n\) повинен бути непарним.
\(n\)Дозволяти ціле число. Якщо\(n\) рівний, то\(n^2\) теж рівний. Як ціле число,\(n^2\) може бути непарним. Отже,\(n\) не може бути рівним. Тому\(n\) повинен бути непарним.

Вправа\(\PageIndex{10}\label{ex:directpf-10}\)

Проаналізуйте наступні міркування:

\(S\)Дозволяти бути набір дійсних чисел. Якщо\(x\) є в\(S\), то\(x^2\) знаходиться в\(S\). Але\(x\) не в\(S\), отже,\(x^2\) не в\(S\).
\(S\)Дозволяти бути набір дійсних чисел. Якщо\(x\) є в\(S\), то\(x^2\) знаходиться в\(S\). Тому, якщо\(x^2\) є в\(S\), то\(x\) знаходиться в\(S\).

	\(b^2>4ac \Rightarrow ax^2+bx+c=0\)має два реальних рішення.
	\(x^2-5x+6\)задовольняє\(b^2>4ac\).
\(\therefore\)	\(x^2-5x+6=0\)має два реальних рішення.

	Німецькі вівчарки - собаки.
	Собаки - ссавці.
	Ссавці - хребетні.
\(\therefore\)	Німецькі вівчарки - хребетні.

	Словники цінні.
	Ця книга не є словником.
\(\therefore\)	Ця книга не є цінною.

	Жодне ліки не смакує.
	Цей напій поганий на смак.
\(\therefore\)	Це повинно бути ліки.