Що таке пряме доведення?

Теорiя

Пряме доведення

Коли ми бажаємо довести, що

p \Rightarrow q,

то маємо здiйснити доведення шляхом наведення аргументiв, якi слiдують один з одного, щоб отримати

p \Rightarrow \dots \Rightarrow q .

У разi прямого доведення передбачається побудова логiчного ланцюжка мiркувань. Починаємо з $p$ . З твердження $p$ має слiдувати щось, з чого слiдує щось ще, й так далi, доки ми в кiнцевому пiдсумку не отримаємо $q$ , де $q$ — це те, що, як ми мали довести, слiдує з $p$ .

Приклад 1

Доведи, що якщо $a$ — парне число, а $b$ — непарне число, то $a + b$ — непарне число.

Виконуючи доведення, доцiльно скласти вираз, з яким можна працювати. У цьому прикладi треба скласти вирази для $a$ та $b$ . Оскiльки $a$ — це парне число, його можна записати як $a = 2 n$ , де $n$ — цiле число. Число $b$ — непарне число, тому його можна записати як $b = 2 m + 1$ , де $m$ — цiле число. Можна вставити цi вирази у вираз $a + b$ , отримавши

\begin{array}{l} a + b & = 2 n + (2 m + 1) \\ = 2 n + 2 m + 1 \\ = 2 (n + m) + 1 \\ = 2 k + 1, \end{array}

де $k = n + m$ — цiле число, тому $a + b = 2 k + 1$ — непарне число, що й треба було довести.

Q.E.D

Приклад 2

Доведи, що $p^{2} + p$ завжди дiлиться на 2

Нам вiдомо, що всi парнi числа можна розкласти на парний множник. Це правда, тому що всi парнi числа можна подiлити на 2, що слiдує з визначення парних чисел.

Отже, тепер ми бачимо, що можна розкласти на множники $p^{2} + p$ як $p (p + 1)$ . Пiсля цього ми бачимо, що $p$ й $p + 1$ — це два цiлi числа, якi йдуть один за одним на прямiй iз дiйсними числами (наприклад, 3 та 4, 4 та 5 $\dots$ ). Тепер можна стверджувати, що незалежно вiд того, яким числом є $p$ , один iз двох множникiв — це парне число, оскiльки кожне друге цiле число в ряду дiйсних чисел парне.

Якщо $p = 2 k$ — парне число, то $p + 1 = 2 k + 1$ — це непарне число. Якщо $p = 2 k + 1$ — непарне число, то пiдставмо цей вираз для $p$ в $p + 1$ . Отримаємо