Математическая логика и теория алгоритмов

Отыщи всему начало, и ты много поймешь. Козьма Прутков § 2. Дедуктивные теории Дедукция (от латинского deductic - выведение) - форма мышле­ ния, когда заключение выводится чисто логическим путем (т.е. по правилам логики) из некоторых данных посылок. Индукция (от латинского inductio - наведение) - форма мышле­ ния, посредством которой от некоторых фактов или истинных выска­ зываний переходят к некоторой гипотезе (общему утверлсдению). Примеры дедуктивных рассуждений. 1. Все люди смертны. Сократ - человек. Следовательно, Сократ смертен. 2. 5> 3, 3 >1, следователы^о, 5 >1. Примеры индуктивных рассуждений, 1. График функции >>=2х+3 - прямая, график функции_у=Зх+1 - прямая, следовательно, функции вида у=кх+Ь имеют графиком пря­ мую. Полученная здесь гипотеза оказывается истинной. 2. Рассмотрим предположение Ферма, что число р - 1 +1 явля­ ется простым для всех п. При и=0'Л ,2,3,4 получим, что р равно 3, 5, 17, 257, 65537 и все они простые числа. Но Эйлер показал, что для n - S р —А 294 967 297 и это число является составным (делится на 641). Следовательно, это предположение Ферма не верно. 3. Возьмем формулу Эйлера N=x^+x+4\. При каждом х=1,2,3,...,39 число N является простым, следовательно, числа N (ука­ занного вида) являются простыми. Сформулированная здесь гипотеза неверна, например, при х=40 число iV=4p, следовательно, оно не явля­ ется простым. Таким образом, заключение, полученное дедуктивным спосо­ бом, уже не нуждается в доказательстве. Заключение, полученное ин­ дуктивным способом, требует доказательства его истинности. Будем 137