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

2 « 2. Рассмотрим предположение Ферма, что число р = 2 +1 является простым для всех п. При п =0, 1, 2, 3, 4 получим, что р равно 3, 5, 17, 257, 65537 и все они простые числа. Но Эйлер показал, что для п=5 р= 4 294 967 297 и это число является составным (делится на 641). Следовательно, это предположение Ферма не верно. 2. Возьмем формулу Эйлера N=x^+x+A\. При каждом х = 1, 2, 3,..., 39 число N является простым, следовательно, числа N, указанного вида, являются простыми. Сформулированная здесь гипотеза неверна, например, при х = 40 число 7V = 41 , следовательно, оно не является простым. Таким образом, заключение, полученное дедуктивным способом, уже не нуждается в доказательстве. Заключение, полученное индуктивным способом, требует доказательства его истинности. Будем рассматривать дедуктивные методы. Введем понятие дедуктивной теории. Дедуктивная теория считается заданной, если задан язык этой теории и из множества правильно построенных выражений (предложений, называемых формулами) языка выделено дедуктивным образом множество теорем. Подробнее: дедуктивная теория считается заданной, если: 1) задан алфавит и правила образования выражений (слов) в этом алфавите; 2) заданы правила образования формул языка (правильно построенных выражений); 3) из множества всех формул языка выделено некоторым дедуктивным способом (который будет описан) подмножество Т, элементы которого будем называть теоремами. В зависимости от того, как задано это подмножество Т, будем различать получающиеся при этом дедуктивные теории. Подмножество Т может задаваться одним из следующих способов. I. Задаются аксиомы и конечное число правил выводов: а) из множества формул (правильно построенных выражений) выделяется подмножество А, элементы которого называются аксиомами (аксиом может быть как конечное число, так и бесконечное); б) задается конечное число правил выводов, используя которые, и только их, из аксиом можно некоторым образом получать теоремы (подробнее этот вопрос будет изучаться в следующих параграфах). Если теоремы заданы указанным образом, т.е. заданием аксиом и конечного числа правил вывода, то эта дедуктивная теория называется формальной аксиоматической теорией или формальным (логическим) исчислением. Особо отметим, что аксиомы лишь задаются, поэтому их часто называют скрытыми определениями. Бытующее мнение, согласно которому аксиомы принимаются без доказательств, не совсем точно передает суть дела. Аксиомы не доказываются не потому, что могут не доказываться, а потому, что не могут быть доказаны. П. Задаются только аксиомы, а правила вывода считаются известными: 101