Логіка та доказ. Доказ: прямий, зворотний, від протилежного

Теорема- Це твердження, справедливість якого встановлюється шляхом міркування. Сама міркування називається доказом теореми.

Теорема зворотна даної– це теорема, у якій умовою є висновок цієї теореми, а висновком – її умова. Наприклад: Теорема: У рівнобедреному трикутнику кути при основі рівні. Зворотна теорема: Якщо в трикутнику два кути рівні, то він є рівнобедреним.

Слідство- Це твердження, яке виводиться безпосередньо з теореми. Наприклад: наслідкомз теореми про висоту рівнобедреного трикутникає: Медіана рівнобедреного трикутника, проведена до основи, є висотою та бісектрисою.

Доказ методом від протилежногополягає в наступному:

1) Робиться протилежне припущення тому, що треба довести.

2) Потім, виходячи з припущення, шляхом міркувань суперечать або з умовою, або з відомим фактом.

3) З отриманого протиріччя робиться висновок у тому, що припущення неправильно, отже правильно те, що потрібно довести.

Ознака рівності прямокутних трикутників з гіпотенузи та катету.

Якщо гіпотенуза та катет одного прямокутного трикутникавідповідно рівні гіпотенузі та катету іншого прямокутного трикутника, то такі трикутники рівні.

Дано :

DАВС – пр/уг

НД=В 1 З 1

Довести:

DАВС = DА 1 В 1 С 1

Доведення:

1. Прикладемо до DАВС до DА 1 В 1 З 1 так, щоб вершина А суміщалася з вершиною А 1 , вершина В з вершиною В 1 , а вершини С і С 1 виявилися по різні сторони від прямої АВ.

2. Оскільки АВ= А 1 В 1 Þ вони збігатимуться.

3. ÐСА 1 С 1 = 90 0 + 90 0 = 180 0 ÞÐСА 1 С 1 – розгорнутий і Þточки С, А 1 і С 1 – лежать на одній прямій.

4. Розглянемо DСВС 1 – р/б (ВС= В 1 С 1 за умовою) Þ ÐС = ÐС 1 (за якістю)

5. Таким чином, DАВС = DА 1 В 1 С 1 – з гіпотенузи та гострому кутку. (Ч.т.д.)

Білет №9.

Перпендикулярні до прямих. Перпендикуляр до прямої.

Перпендикулярні прямі- Це дві прямі, які при перетині утворюють чотири прямі кути. (Показати на малюнку)

Перпендикуляр до прямої –це відрізок, опущений із точки на пряму під прямим кутом. Точка перетину відрізка і прямої називається основою перпендикуляра (показати малюнку)

Теореми:

1) З точки, що не лежить на прямій, можна провести перпендикуляр до цієї прямої і до того ж тільки один.

2) Дві прямі перпендикулярні до однієї і тієї ж прямої не перетинаються.

Ознака рівнобедреного трикутника.

Якщо трикутнику два кути рівні, він є равнобедренным.

Дано:

ÐА = ∠С

Довести:

DАВС - р/б

Доведення:

1. Подумки скопіюємо DАВС і перевернемо копію – отримаємо DСВА.

2. Накладемо DСВА на DАВС, щоб вершина З копії суміщалася з вершиною А DАВС.

3. Оскільки ÐА = ÐС (за умовою) Þ ÐА копії та ÐС трикутника при накладенні збігатимуться, так само ÐС копії та ÐА трикутника при накладенні збігатимуться.

4. Відрізок СВ копії накладеться на промінь АВ трикутника та відрізок АВ копії накладеться на промінь СВ трикутника.

5. Оскільки дві прямі можуть мати лише одну загальну точкуперетину ⇒

т. У 1 збігається з точкою В і ⇒ АВ суміситься з СВ ⇒ АВ=СВ

6. З того, що АВ = СВ ⇒ за визначенням ΔАВС - рівнобедрений (ч.т.д.)

Білет №10.

Рівнобедрений трикутник.

Трикутник, у якого дві сторони рівні, називається рівнобедреним.Рівні сторони називаються бічними сторонами, а третя сторона – основою. (показати малюнку)

Властивість рівнобедреного трикутника:У рівнобедреному трикутнику кути при підставі рівні. (Показати малюнку)

Ознака рівнобедреного трикутника: Якщо в трикутнику два кути рівні, то він є рівнобедреним. (показати малюнку)

Теорема про висоту рівнобедреного трикутника: Висота рівнобедреного трикутника, проведена до основи, є медіаною та бісектрисою. (показати малюнку)

Наслідки з теореми про висоту рівнобедреного трикутника:

1) Медіана рівнобедреного трикутника, проведена до основи, є висотою та бісектрисою. (показати малюнку)

2) Бісектриса рівнобедреного трикутника, проведена до основи, є висотою та медіаною. (показати малюнку)

Практичне заняття № 2

Тема: Логіка та доказ. Доказ: прямий, зворотний, від протилежного. Метод математичної індукції.

Заняття розраховане на 2 академ. години.

Ціль: вивчити різні методидоказів (пряме міркування, метод «від протилежного» і протилежне міркування), що ілюструють методологію міркувань. Розглянути метод математичної індукції.

Теоретичний матеріал

Методи доказів

За доказом теорем застосовується логічна аргументація. Докази в інформатиці невід'ємна частина перевірки правильності алгоритмів. Необхідність доказу виникає, коли ми повинні встановити істинність висловлювання виду (А У). Існує кілька стандартних типів доказів, які включають:

Пряме міркування (доказ).

Припускаємо, що висловлювання А є істинним і показуємо справедливість В. Такий спосіб доказу виключає ситуацію, коли A істинно, a B  хибно, оскільки саме в цьому і тільки в цьому випадку імплікація (А В) набуває помилкового значення (див. табл.).

Таким чином, прямий доказ походить від розгляду аргументів до доказу тези, тобто істинність тези безпосередньо обґрунтовується аргументами. Схема цього доказу така: із даних аргументів(а, b, с, ...) необхідно слідувати доказувану тезу q.

За цим типом проводяться докази у судовій практиці, у науці, у полеміці, у творах школярів, при викладі матеріалу вчителем тощо.

Приклади:

1. Вчитель на уроці за прямого доказу тези “Народ творець історії”, показує;по перше , що народ є творцем матеріальних благ,по-друге , доводить величезну роль народних масу політиці, роз'яснює, як у сучасну епоху народ веде активну боротьбу за мир та демократію,по-третє , Розкриває його велику роль у створенні духовної культури.

2. На уроках хімії прямий доказ про горючість цукру може бути представлений у формі категоричного силогізму: Усі вуглеводи – горючі.Цукор – вуглевод. Цукор горючий.

У сучасному журналі мод "Бурда" теза "Заздрість - корінь усіх зол" обґрунтовується за допомогою прямого доказу такими аргументами: "Заздрість не тільки отруює людям повсякденне життя, але може призвести і до більш серйозних наслідків, тому поряд з ревнощами, злобою та ненавистю, безсумнівно, відноситься до самих поганим рисамхарактеру. Підкравшись непомітно, заздрість ранить боляче та глибоко. Людина заздрить благополуччю інших, страждає від свідомості того, що комусь більше пощастило”.

2. Зворотній міркування(Доведення ) . Припускаємо, що висловлювання В є хибним і показуємо помилковість А. Тобто, фактично, прямим способом перевіряємо істинність імплікації ((не В) (не А)), що згідно з таблицею, логічно еквівалентно істинності вихідного твердження (А В).

3. Метод «від неприємного».

Цей метод часто використовується у математиці. Нехайа - теза чи теорема, яку треба довести. Припускаємо від неприємного, щоа хибно, тобто істинноне-а (або). З припущення виводимо слідства, що суперечать дійсності або раніше доведеним теоремам. Маємо, при цьому- хибно, отже, істинно його заперечення, тобто., яке за законом двозначної класичної логіки (→а) дає а. Значить, істинно а , що й потрібно було довести.

Прикладів доказу "від неприємного" дуже багато в шкільномукурсі математики. Так, приклад, доводиться теорема про те, що з точки, що лежить поза прямою, на цю пряму можна опустити лише один перпендикуляр. Методом "від неприємного" доводиться і така теорема: "Якщо дві прямі перпендикулярні до однієї і тієї ж площини, то вони паралельні". Доказ цієї теореми прямо починається словами: “Припустимо неприємне, т. е. що пряміАВ та CD не паралельні”.

Математична індукція

Комп'ютерну програму в інформатиці називають правильною чи коректною, якщо вона робить те, що зазначено у її специфікації. Незважаючи на те, що тестування програми може давати очікуваний результат у разі якихось окремих початкових даних, необхідно довести прийомами формальної логіки, що правильні вихідні дані будуть виходити при будь-яких початкових значеннях, що вводяться.

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

В основі будь-якого математичного дослідження лежать дедуктивний та індуктивний методи. Дедуктивний спосіб міркування - це міркування від загального до приватного, тобто. міркування, вихідним моментом якого є загальний результат, а заключним моментом є приватний результат. Індукція застосовується під час переходу від приватних результатів до загальних, тобто. є методом, протилежним до дедуктивного. Метод математичної індукції можна порівняти із прогресом. Ми починаємо з нижчого, в результаті логічного мисленняприходимо до вищого. Людина завжди прагнула прогресу, до вміння розвивати свою думку логічно, отже, сама природа накреслила йому розмірковувати індуктивно.

Принцип математичної індукції це така теорема:

Нехай ми маємо нескінченну послідовність тверджень P 1 , P 2 , ..., P n занумерованих натуральними числами, причому: затвердження P 1  істинно; якщо деяке твердження P k  істинно, то наступне твердження P k +1 теж істинно.

Тоді принцип математичної індукції стверджує, що це твердження послідовності істинні.

Тобто принцип математичної індукції можна сформулювати так: якщо в черзі першою стоїть жінка, і за кожною жінкою стоїть жінка, то все в черзі жінки.

Спосіб міркувань, заснований на принципі математичної індукції, називається методом математичної індукції. Для вирішення завдань методом математичної індукції необхідно:

1) сформулювати затвердження завдання у вигляді послідовності тверджень P 1, P 2, ..., P n, ...;

2) довести, що затвердження P 1 істинно (цей етап називається базою індукції); 3) довести, що якщо затвердження P n істинно при деякому n = k, воно істинно і при n = k + 1 (цей етап називається кроком індукції).

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

Індукція може призвести до помилкового висновку. Так, наприклад, обчислюючи значення виразу n 2 +n+17 при n = 1,2,3, ..., 15 ми отримуємо незмінно прості числа, і це наводить на думку, що значення цього виразу при будь-якому натуральному n є просте число. Інакше кажучи, на підставі п'ятнадцяти приватних посилок отримано загальний висновок, що відноситься до нескінченної множини окремих випадків, і це висновок виявляється помилковим, оскільки вже при n = 16 отримуємо складове число 16 2 +16+17=172.

В історії математики були випадки, коли відомі математики помилялися у своїх індуктивних висновках. Наприклад, П. Ферма припустив, що всі числа виду 22 n + 1 прості, виходячи з того, що за n = 1,2,3,4 вони є такими, але Л. Ейлер знайшов, що вже за n = 5 число 232 + 1 не є простим (воно ділиться на 641). Однак можливість отримання за допомогою індукції хибного висновку не є підставою для заперечення ролі індукції в шкільному навчанніматематики.

Методичні вказівки

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

Рішення. Будь-яке непарне число, зокрема х, можна записати у вигляді х = 2 m + 1, де m  Z . Аналогічно, у = 2 n + 1, n  Z .

Отже, твір ху = (2 m + 1) (2 n + 1) = 4mn + 2m + 2n + 1 = 2(2 mn+m+n ) + 1 теж є непарним числом.

Приклад 2: Нехай n  N . Покажіть, використовуючи зворотний спосіб доказу, що якщо n 2 непарно, те й n непарно.

Рішення. Запереченням висловлювання про непарність числа n 2 служить твердження « n 2 парно», а висловлювання про парність n є запереченням затвердження «число n непарно». Таким чином, потрібно показати прямим способом міркувань, що парність числа n тягне парність його квадрата n 2 .

Так як n парно, то n = 2 m для якогось цілого числа m. Отже, n 2 = 4 m 2 = 2(2 m 2 ) - парне число.

Приклад 3: Методом від протилежного покажіть, що рішення рівняння х 2 = 2 є ірраціональним числом, тобто не може бути записано у вигляді дробу з цілим чисельником і знаменником.

Рішення. Тут нам слід припустити, що рішення х рівняння х 2 = 2 раціонально, тобто записується у вигляді дробу х = з цілими m і n, причому n  0. Припустивши це, нам необхідно отримати протиріччя чи з припущенням, чи з якимось раніше доведеним фактом.

Як відомо, раціональне число неоднозначно записується

у вигляді дробу. Наприклад, х = == і т.д. Однак можна вважати, що m і n немає спільних дільників. І тут неоднозначність запису пропадає.

Отже, припускаємо додатково, що дріб х = нескоротний ( m і n не мають спільних дільників). За умовою число х задовольняє рівняння х 2 = 2. Отже, () 2 = 2, звідки m 2 = 2 n 2 .

З останньої рівності випливає, що число m 2 парно. Отже, m теж парно і може бути подане у вигляді m = 2р для якогось цілого числа р. Підставивши цю інформацію на рівність m 2 = 2 n 2 , ми отримаємо, що 4р 2 = 2 n 2 , тобто n 2 = 2р2.

Але тоді n теж є парним числом. Таким чином, ми показали, що як m так і n  парні числа. Тому вони мають спільний дільник 2. Якщо ж тепер згадати, що ми припускали відсутність спільного дільникау чисельника та знаменника дробу, то побачимо явну суперечність.

Знайдене протиріччя призводить до однозначного висновку: рішення рівняння х 2 = 2 може бути раціональним числом, т. е. воно ірраціонально.

Приклад 4: Доведемо по індукції таку рівність (яка, звичайно, припускає й інші докази):

1+2+3+...+n=n(n+1)/2.

База. При n = 1 рівність перетворюється на тотожність 1 = 1 · (1 + 1) / 2.

Крок. Нехай рівність виконана за n = k: 1 + 2 + 3 + ... + k = k(k + 1)/2.

Додамо до обох частин цієї рівності k + 1. У лівій частині ми отримаємо суму 1+2+3+...+k+(k+1),а в правій - k(k+1)/2+(k+1)=(k(k+1)+2(k+1))/2=((k+2)(k+1))/ 2.

Отже, 1 + 2 + 3 + ... + k + (k + 1) = (k + 1) (k + 2) / 2, а це і є необхідна рівність при n = k + 1, де n означає довільне натуральне число.

Контрольні питання

У чому різниця між доказом прямим міркуванням,зворотним, від протилежного?
Що означає математична індукція? Поясніть принцип математичної індукції.

Індивідуальні завдання

1. Використовуючи методи доказу:

1) Прямою міркуванням доведіть істинність висловлювання: n і m ? парні числа ? n + m ? число парне.

2) Дайте зворотний доказ висловлювання: n 2 ? парне число  n ? парне.

3) Методом «від неприємного» доведіть, що n+m непарне число один із доданків є парним, а інше - непарним.

2. Доведіть кожне із висловлювань методом математичної індукції.

1) 1 + 5 + 9 +…+(4 n - 3) = n (2 n  1) для всіх натуральних чисел n.

2) 1 2 +2 2 + ... + n 2 = n (n +1) (2 n +1)/6 для всіх натуральних чисел n.

3) д для всіх натуральних чисел n.

4) Число n 3  n ділиться на 3 при всіх натуральних значеннях числа n.

5) 1*1! + 2 * 2! + ... + - n * n! = (n + 1)!  1 для всіх натуральних чисел n.

(Символ n! читається як «n факторіал» і позначає добуток усіх натуральних чисел від 1 до n включно: n! = l *2*3*** (n  l )* n .)

Додаткові завдання:

1. Знайдіть помилку в наступному «доказі» того, що всі коні однієї масті.

Будемо доводити індукцією по n наступне твердження: «У будь-якому табуні з n це коней, усі вони однієї масті». База (n = 1) очевидна: у цьому випадку всі коні - один кінь, він очевидно однієї масті. Ш: нехай у будь-якому табуні з k коней всі коні мають одну масть. Розглянемо табун із k + 1 коня. Виберемо в ньому двох коней a і b і розглянемо решту k 1 коня. Складемо табун із цих коней, додавши до них a. У ньому k коней, тому, на думку індукції, всі вони однієї масті. Значить, кінь a має ту ж масть, що й коні, що залишилися. Аналогічно доводиться, що ту ж масть має коня b. Отже, все k + 1 кінь мають однакову масть. Твердження доведене.

2. На нескінченному картатим аркуші паперу 100 клітин зафарбовані в чорний колір, а всі інші в білий. За один хід дозволяється перефарбовувати у протилежний колір будь-які чотири клітини, що утворюють квадрат 2x2. Доведіть, що за кілька ходів можна домогтися того, що всі клітини виявляться білими тоді і тільки тоді, коли будь-яка горизонталь та будь-яка вертикаль містить парну кількість чорних клітин.

Хибний, тим самим обгрунтовуємо істинність протилежного йому становища - тези. Напр., лікар, переконуючи пацієнта в тому, що той не хворий на грип, може розмірковувати наступним чином: «Якби ви дійсно були хворі на грип, то у вас була б підвищена температура, був закладений ніс і т.д. Але нічого цього нема. Отже, немає і грипу». Доказ деякого становища від протилежного - це істинності цього положення, що спирається на демонстрацію хибності «противного» (суперечливого) становища та виключеного третього.
Загальна Д. від п. описується в такий спосіб. Потрібно довести деяке А. У процесі доказу спочатку формулюється протилежне йому висловлювання не-А і передбачається, що істинно: припустимо, що А хибно, тоді має бути істинно не-А. Потім з цього нібито істинного антитези виводяться слідства - доти, доки або не вийде, або таке, яке явно суперечить відомому істинному висловлюванню. Якщо показано, що не-А хибно, то цим обґрунтовано істинність тези А ( див.ДОВЕДЕННЯ).

Філософія: Енциклопедичний словник. - М: Гардаріки. За редакцією А.А. Івіна. 2004 .

(лат. reduc-tio ad absurdum), вид доказу, при кром «доведення» деякого судження (тези доказу)здійснюється через суперечить йому судження - антитези. Спростування антитези при цьому досягається встановленням факту його несумісності з к.-л.свідомо істинним судженням. Цій формі Д. від п. відповідає слід.схема доказу: якщо істинно і з А слід помилковість, то А - хибно. Інша, загальніша Д. від п. - це шляхом спростування (обґрунтування хибності)антитези за правилом: допустивши А, вивели , отже - не-А. Тут А може бути як ствердним, і негативним судженням. У разі Д. від п. спирається на і закон подвійного заперечення. Крім зазначених вище, існує «парадоксальна» форма Д. від п., що застосовувалася вже в «Початках» Евкліда: А можна вважати доведеним, якщо вдасться показати, що А випливає навіть з помилки А.

Філософський енциклопедичний словник. - М: Радянська енциклопедія. Гол. редакція: Л. Ф. Іллічов, П. Н. Федосєєв, С. М. Ковальов, В. Г. Панов. 1983 .

ДОВІД ВІД ПРОТИ

Літ.:Тарський Α., Введення в логіку та методологію дедуктивних наук, пров. з англ., М., 1948; Асмус Ст Ф., Вчення логіки про доказ і спростування, [М.], 1954; Кліні С. До., Введення в метаматематику, пров. з англ., М., 1957; Чорч А., Введення в математич. логіку, пров. з англ., [Т.] 1, М., 1960.

Філософська енциклопедія. У 5-х т. – М.: Радянська енциклопедія. За редакцією Ф. В. Константинова. 1960-1970 .

Дивитись що таке "ДОКАЗ ВІД ПРОТИ" в інших словниках:

- (proof by contradiction) Доказ, у якому визнання вихідної причини неправильної веде до суперечності. Тобто припущення про помилковість вихідної посилки дозволяє одночасно і довести якесь твердження, і спростувати його; … Економічний словник

Один із видів непрямого доказу. Великий Енциклопедичний словник

У цій статті не вистачає посилань на джерела інформації. Інформація має бути перевіряється, інакше вона може бути поставлена під сумнів та видалена. Ви можете … Вікіпедія

Один із видів непрямого доказу. * * * ДОВІД ВІД ПРОТИВНОГО ДОВІД ВІД ПРОТИ, одного з видів непрямого доказу (див. НЕДІЛЬНИЙ ДОВІД) … Енциклопедичний словник

Доказ протилежного- (Лат. Reduction ad absurdum) вид доказу, при якому справедливість деякого судження (тези доказу) здійснюється через спростування судження антитези, що суперечить йому. Спростування антитези досягається шляхом... Дослідницька діяльність. Словник

ДОВІД ВІД ПРОТИ- (Лат. reductio ad absurdum) вид доказу, при якому справедливість деякого судження (тези доказу) здійснюється через спростування судження антитези, що суперечить йому. Спростування антитези досягається шляхом... Професійну освіту. Словник

Див: Непрямий доказ … Словник термінів логіки

- (Лат. reductio ad absurdum) вид Докази, при якому «доведення» деякого судження (тези доказу) здійснюється через спростування судження антитези, що суперечить йому. Спростування антитези при цьому досягається. Велика Радянська Енциклопедія

Метод від протилежного

Апагогія- логічний прийом, яким доводиться неспроможність якої-небудь думки таким чином, що або в ньому самому, або в необхідно з нього випливають слідства ми відкриваємо протиріччя.

Тому апогічний доказ є доказом непрямим: тут доказуючий звертається спершу до протилежного становища, щоб показати його неспроможність, і потім за законом виключення третього робить висновок про справедливість того, що потрібно довести. Цей рід доказу називається також приведенням до безглуздя. Істотною його приналежністю є доказ, що третє немає, т. е., що крім думки, справедливість якого треба довести, і другого, йому протилежного, яке є вихідним пунктом докази, ніякий третій факт не допускається. Тому опосередкований доказ виходить із факту, що заперечує становище, справедливість якого потрібно довести.

Приклади

Дивись також

Wikimedia Foundation. 2010 .

Дивитися що таке "Метод від неприємного" в інших словниках:

У математиці метод нескінченного спуску це метод доказу від протилежного, заснований на тому, що безліч натуральних чисел цілком упорядковано. Часто метод нескінченного спуску використовується для доказу того, що у деякого… Вікіпедія

Метод доказу, що застосовувався математиками давнини під час знаходження площ та обсягів. Назва «метод вичерпування» введено у 17 ст. Типова схема доказу за допомогою І. м. може бути викладена в сучасних… Велика Радянська Енциклопедія

Метод доказу, що застосовувався математиками давнини під час знаходження площ та обсягів. назв. метод вичерпування введено у 17 ст. Типова схема доказу з допомогою І. м. може бути викладена у сучасних позначеннях так: для… Математична енциклопедія

- 'БУТТЯ І ЧАС' ('Sein und Zeit', 1927) основна робота Хайдеггера. На створення 'Б.іВ.', як традиційно належить, вплинули дві книги: робота Брентано 'Значення буття згідно з Аристотелем' та 'Логічні дослідження' Гуссерля. Перша з них… Історія Філософії: Енциклопедія

- (від пізньолат. intuitio, від лат. intueor уважно дивлюся) напрям в обґрунтуванні математики та логіки, згідно з яким кінцевим критерієм прийнятності методів та результатів цих наук є наочно змістовна інтуїція. Вся математика … Філософська енциклопедія

Математику зазвичай визначають, перераховуючи назви деяких із її традиційних розділів. Насамперед, це арифметика, яка займається вивченням чисел, відносин між ними та правил дій над числами. Факти арифметики допускають різні… Енциклопедія Кольєра

Термін, який раніше об'єднував різні розділи математич. аналізу, пов'язані з поняттям нескінченно малої функції. Хоча метод нескінченно малих (у тій чи іншій формі) успішно застосовувався вченими Стародавню Греціюі середньовічної Європидля вирішення… … Математична енциклопедія

- (від лат. absurdus безглуздий, безглуздий) безглуздість, протиріччя. У логіці під А. зазвичай розуміється суперечливий вираз. У такому вираженні щось стверджується і заперечується одночасно, як, напр., у висловлюванні «Марнославство існує і марнославство… … Філософська енциклопедія

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

Теорема Евклідапро нескінченність простих чиселє класичним і найпростішим міркуванням від протилежного:

Не існує найбільшого простого числа.

: Нехай це не так, і найбільше просте число існує Побудуємо число. Воно не ділиться на жодне, і більше ніж. Ми дійшли протиріччя, отже, найбільшого простого числа (як об'єкта!) немає і простих чисел нескінченно багато.

Зауважимо, що не обов'язково просте, тому що його простий множник може бути між , але все одно буде великим .

Теорема про ірраціональність

Не існує натуральних і таких, що .

: Нехай це не так Скоротимо загальні множники у , і зведемо все в квадрат: . Звідси випливає, що є парним числом, тому теж парно і представимо за допомогою деякого натурального , як . Підставляючи вихідне співвідношення, отримуємо , отже, і парно. Але це суперечить тому, що ми скоротили всі спільні множники, а отже, таких і не існує.

Психологічна переконливість обох доказів не викликає сумнівів. Тим не менш, необхідно пам'ятати, що, отримавши протиріччя, ми не завжди доводимо те, що хочемодовести. Суперечність не обов'язково свідчить про помилковість вихідної посилки. Його може дати будь-яке із тверджень використовуваних при доказі. Особливо їх багато в теоремі про ірраціональність. Однак, вони настільки "очевидні", що ми вважаємо помилковою саме вихідну посилку.

Видно, що схема доказу наведених теорем однакова. Ми показуємо, що певний об'єкт немає, якщо припущення про його існування призводить до суперечності.

Проблема Брадобрея. У деякому селі всі чоловіки голяться або самі, або у цирульника. Брадобрей (чоловік) голить тільки тих, хто сам не голиться. Сформулюємо теорему:

Брадобрей голить себе сам.

Нехай це не так, і цирульник себе не голить. Тоді він повинен голитися у цирульника. Значить цирульник голить себе.

Зробивши заперечення теореми, і отримавши протиріччя, ми маємо зробити висновок, що теорема вірна. Але цілком зрозуміло, що це не так, і ми можемо побудувати не тільки зворотний доказ, але й пряме: "якщо цирульник голиться сам, то він не може голитися у цирульника ...". І тут знову виходить протиріччя.

Наведений опис села зі суворими правиламиналежить Бертрану Расселу, як популярне формулювання проблем, що виникають у спробі визначити"Багато всіх тих множин, які не містять себе як свій елемент". Ми навмисне явний парадокс представили у вигляді теореми, щоб продемонструвати простий факт:

Одержання протиріччя як доказ від протилежного може свідчити не про істинність теореми, йдеться про суперечливості об'єктів які у її формулюванні.

Інакше кажучи, не можна сказати: " візьмемо безліч всіх множин... " і доведемо " теорему у тому, що... " Спочатку необхідно переконатися, що об'єкт, про який йтиметься у теоремі, існує. Зокрема, село, описане Расселом, не може існувати. Звичайно, виникає питання - "а що означає існувати чи не існувати, і де не існувати?" Є об'єкт, визначений вище, і ми можемо використовувати його при побудові нових об'єктів і теорем про них.

Справа в тому, що математичне міркування явно чи не явно виходить із деяких аксіом. Саме аксіоми задають властивості об'єкта. Якщо у фіксованій системі аксіом поміняти хоча б одну аксіому, може вийти об'єкт з іншими властивостями. Зрозуміло, що довільно ставити аксіоми не можна. Вони не повинні бути суперечливими, інакше жодного об'єкта не визначатимуть. Або, іншими словами, - об'єкт, що визначається за допомогою суперечливих аксіом не існує.

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

Проблема Бібліотекаря. Існує бібліотека з книгами. Будь-яка книга всередині свого тексту може згадати сама себе (наприклад, у списку літератури навести свою назву). Відповідно, всі книги можна розділити на дві групи. У першу потрапляють книги, які на себе не посилаються, а в другу – книги, що посилаються на себе. Крім цього, існують дві книги, які є каталогами всіх книг Бібліотеки. Перший каталог перераховує всі ті книги, які на себе не посилаються, а другий, навпаки – всі книги, що посилаються на себе:

Сформулюємо тепер теорему:

Перший каталог містить
у списку книг себе.

Нехай це негаразд. Тоді перший каталог міститься у другому (всі книги перелічені в обох каталогах і каталог є книга). Але в другому каталозі перераховуються тільки книги, що самопосилаються, і першого каталогу там бути не може. Ми дійшли протиріччя, отже теорема вірна.

Якщо ми зупинимося на цьому етапі, то отримаємо свідомо неправильний висновок. Зрозуміло, що перший каталог на себе посилатися не може (він є каталогом книг, що не посилаються). Як і у випадку з цирульником, ми можемо провести як зворотний доказ (від противного), так і прямий. І обидва рази одержати протиріччя.

Про що вона говорить? Зрозуміло, що не про істинність чи хибність теореми. Вірячи в те, що два різних доказівповинні завжди приводити до того самого, ми змушені зробити висновок: об'єкт Бібліотека, c заданими властивостями, існувати не може.

Будь-яке посилання " природність " чи " видиму не суперечливість " вихідних визначень недостойна математика, оскільки це вже емоції. Єдиний шлях - спробувати уникнути психологічних формулювань і доказів до формальних.

Парадокс брехуна. Вся математика складається із логічних тверджень. У цьому логіка математики бінарна. Твердження "" чи істинно чи хибно. Третього не дано. Саме ця бінарність надає математичному доказуту чудову переконливість, заради якої все й починалося. Введемо позначення того, що якесь логічне твердження є істинним:

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

де "" - знак логічного заперечення, а після двокрапки йде визначеннязатвердження. Воно є варіантом феномена брехуна: " – істинно, а то й істинно " . Сформулюємо таку теорему:

Твердження L є істинним: L=І.

нехай L=Л => True(L)=Л => L=True(L)=І.

(Далі "" означає логічний висновок; "І" - істина, "Л" - брехня). На доказ протилежного, ми дійшли суперечності. Тому вихідна посилка не вірна і, отже, теорема вірна. Проте зрозуміло, що це негаразд. Ми можемо провести доказ у прямому напрямку.