Александр Соловьев - ДИСКРЕТНАЯ МАТЕМАТИКА БЕЗ ФОРМУЛ

Коль скоро логика не интересуется смыслом высказываний, а лишь их истинностью, то ее (истинность) и об'явили смыслом высказываний. Вдумайтесь, смысл высказывания, например, «Газ при нагревании расширяется» не в том, что это отражение физического закона, а в том что оно истинно. Следовательно, точно такой же смысл( ! ) имеет высказывание «Никита Михалков – кинорежиссер». То есть его смысл в том, что оно тоже истинное.

Дальше – больше. Язык предикатов – это существенное расширение языка высказываний и обычным образом перебрать все случаи даже в простейшей ситуации, вроде «Икс любит кашу», не всегда возможно. Тем более, что речь может идти и о бесконечностях. Для решения проблем семантики в этом случае прибегают к теории моделей. Но это теория также, в конечном итоге, упирается в «смысл» типа истинно-ложно.

Возвращаясь к аксиоматическим теориям следует сказать, что в математике «практический смысл» имеют лишь такие теории, в которых можно выводить только истинные формулы. И нельзя ложные.

Одна ложная формула «уничтожает без остатка» любую аксиоматическую теорию.

Наша теория, созданная из буквы Я, не привязана к понятию истинности. Поэтому она бессмысленна, как бессистемная перестановка детских кубиков.

С кубиками все ясно. Но проблемы аксиоматических теорий на этом не исчерпываются. Пожалуй самым фундаментальным открытием в этой сфере следует считать доказанную Геделем ТЕОРЕМУ О НЕПОЛНОТЕ . Оказывается, в сколько-нибудь сложной аксиоматической системе (посложнее, чем кубики, но достаточно даже арифметики) существуют формулы, которые нельзя ни доказать, ни опровергнуть. Может в этом причина, что не все школьные задачки имеют решения?!

Так что, создавая свои аксиоматические теории помните, что они должны обладать какими-то полезными свойствами. А такие теории создавать уже не так-то просто. Хотя создать свою собственную математику может каждый!

Известно высказывание одного крупного математика: «Преимущество аксиоматизации – это преимущество воровства перед честным трудом».

Теория алгоритмов не учит «составлять» алгоритмы. Она занимается более важным вопросом. Основная задача классической теории алгоритмов – это ответ на вопрос: «Можно ли (вообще) для задач данного типа построить алгоритм?». Говоря более наукообразно: «Являются ли задачи данного типа алгоритмически разрешимыми»?

Это связано с тем, что, во-первых, не для всех задач возможно создать алгоритмы их решения. А, во-вторых, чтобы сделать математически строгий вывод о невозможности построить алгоритм, надо иметь строгое (формальное) определение самого алгоритма. Но понятие АЛГОРИТМА относится к фундаментальным неопределяемым понятиям. В вопросе об алгоритме у нас собачья позиция. Понимать понимаем, а сказать не можем. Если где-то встречаете «определение» алгоритма, то там, что ни слово – то аллегория…

Из этого тупика был найден нетривиальный выход. Понятие алгоритма заменили строго формализованными математическими моделями. Среди самых известных рекурсивные функции, машины Тьюринга и нормальные алгорифмы Маркова.

Эти математические модели выступают в роли «конкретизаций понятия алгоритма». То есть длительная практика подтверждает так называемый тезис Черча, который можно пересказать так:

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

РЕКУРСИВНЫЕ ФУНКЦИИ основаны на той идее, что исходные данные и возможные результаты решения любой задачи можно пронумеровать. Для чего, естественно, достаточно множества натуральных чисел (целых положительных чисел, начиная с нуля). А далее базовыми об'являются функции, возможность выполнить (вычислить) которые не вызывает сомнений.

НУЛЬ– ФУНКЦИЯ – это функция, которая дает значение ноль для любого значения аргумента. Реализовать эту функцию может не только ребенок. Можно посадить попугая и подучить его на любой вопрос о значении функции кричать «Ноль!».

ФУНКЦИЯ СЛЕДОВАНИЯ дает следующее, по сравнению с аргументом, значение. Для пяти это шесть, для миллиона – миллион один. Можно бы было сказать, что здесь надо просто прибавлять 1.

Но операции сложения у нас пока нет!

ФУНКЦИЯ ВЫБОРА АРГУМЕНТА . Это вообще забавная даже для первоклассника функция, содержащая в своем имени номер аргумента. Если у вас есть несколько аргументов, то эта функция в качестве значения возьмет значение указанного в ней аргумента. Например, функция выбора третьего из Иванова, Петрова и Сидорова, которых мы ранее пронумеровали, например, как 22, 13 и 49, даст значение 49.