Оно очевидно для всех. Очевиднее не бывает! А если в системе есть еще и утверждение:
"ЕСЛИ мы гуляем, ТО обязательно заблудимся" то с учетом ранее выведенного
«Мы гуляем» получим
«Обязательно заблудимся»
Видите, как далеко можно зайти маленькими очевидными шажками! Существует много и других правил вывода, но все имеют обязательное свойство – очевидность. Эта очевидность позволяет далее использовать эти правила абсолютно формально. То есть результат вычисляется. Такие символьные вычисления называются ИСЧИСЛЕНИЯМИ .
Есть еще один подход к аксиоматике, когда основной упор делается именно на правила вывода. Такие системы (почему-то) называются системами естественного вывода, намекая на то, что в них собраны базовые естественные правила логических рассуждений.
Логики резвились меж собой до тех пор, пока не был сформулирован подход к созданию аксиоматических систем под названием ПРИНЦИП (МЕТОД) РЕЗОЛЮЦИ . Он очень способствовал продвижению логики в широкие народные массы.
С одной стороны, активизировались работы по использованию компьютеров для реализации логического вывода и работы по искусственному интеллекту в частности. А с другой стороны, на этой основе был создан язык ПРОЛОГ .
Это совсем другое программирование, нежели традиционное процедурное. Это даже не программирование в обычном смысле слова, коль скоро здесь программист не пишет алгоритм решения задачи. Он описывает логические зависимости «мира», в котором существует задача. На основе описанной логики «мира» система (машина) сама создает алгоритм в процессе поиска решения!
Это только кажется, что аксиоматические системы – это сложно. Любой может напридумывать их сколько угодно. Более простым делом вам вряд ли приходилось заниматься.
Например, в качестве языка можно об'явить любые «слова» из последовательности буквы Я.
Букву Я об'явим аксиомой.
Правило вывода будет удваивать букву Я.
То есть сходу придумана теория, в которой выводимы любые последовательности (слова), состоящие из буквы Я.
Я ЯЯ ЯЯЯ… ЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯ…
И все бы хорошо, только такая строго заданная теория мало что дает создателю, кроме радости созидания. Поэтому встает вопрос целесообразности, смысла. Той самой семантики… Здесь логики заняли очень(! ) интересную позицию.
Коль скоро логика не интересуется смыслом высказываний, а лишь их истинностью, то ее (истинность) и об'явили смыслом высказываний. Вдумайтесь, смысл высказывания, например, «Газ при нагревании расширяется» не в том, что это отражение физического закона, а в том что оно истинно. Следовательно, точно такой же смысл(! ) имеет высказывание «Никита Михалков – кинорежиссер». То есть его смысл в том, что оно тоже истинное.
Дальше – больше. Язык предикатов – это существенное расширение языка высказываний и обычным образом перебрать все случаи даже в простейшей ситуации, вроде «Икс любит кашу», не всегда возможно. Тем более, что речь может идти и о бесконечностях. Для решения проблем семантики в этом случае прибегают к теории моделей. Но это теория также, в конечном итоге, упирается в «смысл» типа истинно-ложно.
Возвращаясь к аксиоматическим теориям следует сказать, что в математике «практический смысл» имеют лишь такие теории, в которых можно выводить только истинные формулы. И нельзя ложные.
Одна ложная формула «уничтожает без остатка» любую аксиоматическую теорию.
Наша теория, созданная из буквы Я, не привязана к понятию истинности. Поэтому она бессмысленна, как бессистемная перестановка детских кубиков.
С кубиками все ясно. Но проблемы аксиоматических теорий на этом не исчерпываются. Пожалуй самым фундаментальным открытием в этой сфере следует считать доказанную Геделем ТЕОРЕМУ О НЕПОЛНОТЕ . Оказывается, в сколько-нибудь сложной аксиоматической системе (посложнее, чем кубики, но достаточно даже арифметики) существуют формулы, которые нельзя ни доказать, ни опровергнуть. Может в этом причина, что не все школьные задачки имеют решения?!
Так что, создавая свои аксиоматические теории помните, что они должны обладать какими-то полезными свойствами. А такие теории создавать уже не так-то просто. Хотя создать свою собственную математику может каждый!
Известно высказывание одного крупного математика: «Преимущество аксиоматизации – это преимущество воровства перед честным трудом».
Лекция 11. ТЕОРИЯ АЛГОРИТМОВ
Теория алгоритмов не учит «составлять» алгоритмы. Она занимается более важным вопросом. Основная задача классической теории алгоритмов – это ответ на вопрос: «Можно ли (вообще) для задач данного типа построить алгоритм?». Говоря более наукообразно: «Являются ли задачи данного типа алгоритмически разрешимыми»?
Это связано с тем, что, во-первых, не для всех задач возможно создать алгоритмы их решения. А, во-вторых, чтобы сделать математически строгий вывод о невозможности построить алгоритм, надо иметь строгое (формальное) определение самого алгоритма. Но понятие АЛГОРИТМА относится к фундаментальным неопределяемым понятиям. В вопросе об алгоритме у нас собачья позиция. Понимать понимаем, а сказать не можем. Если где-то встречаете «определение» алгоритма, то там, что ни слово – то аллегория…
Из этого тупика был найден нетривиальный выход. Понятие алгоритма заменили строго формализованными математическими моделями. Среди самых известных рекурсивные функции, машины Тьюринга и нормальные алгорифмы Маркова.
Эти математические модели выступают в роли «конкретизаций понятия алгоритма». То есть длительная практика подтверждает так называемый тезис Черча, который можно пересказать так:
Для любой алгоритмически разрешимой задачи можно построить рекурсивную функцию (машину Тьюринга, нормальный алгорифм Маркова). И наоборот, для задач, для которых нельзя построить перечисленные конкретизации, не существует алгоритма решения.
РЕКУРСИВНЫЕ ФУНКЦИИ основаны на той идее, что исходные данные и возможные результаты решения любой задачи можно пронумеровать. Для чего, естественно, достаточно множества натуральных чисел (целых положительных чисел, начиная с нуля). А далее базовыми об'являются функции, возможность выполнить (вычислить) которые не вызывает сомнений.
НУЛЬ– ФУНКЦИЯ – это функция, которая дает значение ноль для любого значения аргумента. Реализовать эту функцию может не только ребенок. Можно посадить попугая и подучить его на любой вопрос о значении функции кричать «Ноль!».
ФУНКЦИЯ СЛЕДОВАНИЯ дает следующее, по сравнению с аргументом, значение. Для пяти это шесть, для миллиона – миллион один. Можно бы было сказать, что здесь надо просто прибавлять 1.
Но операции сложения у нас пока нет!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
"ЕСЛИ мы гуляем, ТО обязательно заблудимся" то с учетом ранее выведенного
«Мы гуляем» получим
«Обязательно заблудимся»
Видите, как далеко можно зайти маленькими очевидными шажками! Существует много и других правил вывода, но все имеют обязательное свойство – очевидность. Эта очевидность позволяет далее использовать эти правила абсолютно формально. То есть результат вычисляется. Такие символьные вычисления называются ИСЧИСЛЕНИЯМИ .
Есть еще один подход к аксиоматике, когда основной упор делается именно на правила вывода. Такие системы (почему-то) называются системами естественного вывода, намекая на то, что в них собраны базовые естественные правила логических рассуждений.
Логики резвились меж собой до тех пор, пока не был сформулирован подход к созданию аксиоматических систем под названием ПРИНЦИП (МЕТОД) РЕЗОЛЮЦИ . Он очень способствовал продвижению логики в широкие народные массы.
С одной стороны, активизировались работы по использованию компьютеров для реализации логического вывода и работы по искусственному интеллекту в частности. А с другой стороны, на этой основе был создан язык ПРОЛОГ .
Это совсем другое программирование, нежели традиционное процедурное. Это даже не программирование в обычном смысле слова, коль скоро здесь программист не пишет алгоритм решения задачи. Он описывает логические зависимости «мира», в котором существует задача. На основе описанной логики «мира» система (машина) сама создает алгоритм в процессе поиска решения!
Это только кажется, что аксиоматические системы – это сложно. Любой может напридумывать их сколько угодно. Более простым делом вам вряд ли приходилось заниматься.
Например, в качестве языка можно об'явить любые «слова» из последовательности буквы Я.
Букву Я об'явим аксиомой.
Правило вывода будет удваивать букву Я.
То есть сходу придумана теория, в которой выводимы любые последовательности (слова), состоящие из буквы Я.
Я ЯЯ ЯЯЯ… ЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯ…
И все бы хорошо, только такая строго заданная теория мало что дает создателю, кроме радости созидания. Поэтому встает вопрос целесообразности, смысла. Той самой семантики… Здесь логики заняли очень(! ) интересную позицию.
Коль скоро логика не интересуется смыслом высказываний, а лишь их истинностью, то ее (истинность) и об'явили смыслом высказываний. Вдумайтесь, смысл высказывания, например, «Газ при нагревании расширяется» не в том, что это отражение физического закона, а в том что оно истинно. Следовательно, точно такой же смысл(! ) имеет высказывание «Никита Михалков – кинорежиссер». То есть его смысл в том, что оно тоже истинное.
Дальше – больше. Язык предикатов – это существенное расширение языка высказываний и обычным образом перебрать все случаи даже в простейшей ситуации, вроде «Икс любит кашу», не всегда возможно. Тем более, что речь может идти и о бесконечностях. Для решения проблем семантики в этом случае прибегают к теории моделей. Но это теория также, в конечном итоге, упирается в «смысл» типа истинно-ложно.
Возвращаясь к аксиоматическим теориям следует сказать, что в математике «практический смысл» имеют лишь такие теории, в которых можно выводить только истинные формулы. И нельзя ложные.
Одна ложная формула «уничтожает без остатка» любую аксиоматическую теорию.
Наша теория, созданная из буквы Я, не привязана к понятию истинности. Поэтому она бессмысленна, как бессистемная перестановка детских кубиков.
С кубиками все ясно. Но проблемы аксиоматических теорий на этом не исчерпываются. Пожалуй самым фундаментальным открытием в этой сфере следует считать доказанную Геделем ТЕОРЕМУ О НЕПОЛНОТЕ . Оказывается, в сколько-нибудь сложной аксиоматической системе (посложнее, чем кубики, но достаточно даже арифметики) существуют формулы, которые нельзя ни доказать, ни опровергнуть. Может в этом причина, что не все школьные задачки имеют решения?!
Так что, создавая свои аксиоматические теории помните, что они должны обладать какими-то полезными свойствами. А такие теории создавать уже не так-то просто. Хотя создать свою собственную математику может каждый!
Известно высказывание одного крупного математика: «Преимущество аксиоматизации – это преимущество воровства перед честным трудом».
Лекция 11. ТЕОРИЯ АЛГОРИТМОВ
Теория алгоритмов не учит «составлять» алгоритмы. Она занимается более важным вопросом. Основная задача классической теории алгоритмов – это ответ на вопрос: «Можно ли (вообще) для задач данного типа построить алгоритм?». Говоря более наукообразно: «Являются ли задачи данного типа алгоритмически разрешимыми»?
Это связано с тем, что, во-первых, не для всех задач возможно создать алгоритмы их решения. А, во-вторых, чтобы сделать математически строгий вывод о невозможности построить алгоритм, надо иметь строгое (формальное) определение самого алгоритма. Но понятие АЛГОРИТМА относится к фундаментальным неопределяемым понятиям. В вопросе об алгоритме у нас собачья позиция. Понимать понимаем, а сказать не можем. Если где-то встречаете «определение» алгоритма, то там, что ни слово – то аллегория…
Из этого тупика был найден нетривиальный выход. Понятие алгоритма заменили строго формализованными математическими моделями. Среди самых известных рекурсивные функции, машины Тьюринга и нормальные алгорифмы Маркова.
Эти математические модели выступают в роли «конкретизаций понятия алгоритма». То есть длительная практика подтверждает так называемый тезис Черча, который можно пересказать так:
Для любой алгоритмически разрешимой задачи можно построить рекурсивную функцию (машину Тьюринга, нормальный алгорифм Маркова). И наоборот, для задач, для которых нельзя построить перечисленные конкретизации, не существует алгоритма решения.
РЕКУРСИВНЫЕ ФУНКЦИИ основаны на той идее, что исходные данные и возможные результаты решения любой задачи можно пронумеровать. Для чего, естественно, достаточно множества натуральных чисел (целых положительных чисел, начиная с нуля). А далее базовыми об'являются функции, возможность выполнить (вычислить) которые не вызывает сомнений.
НУЛЬ– ФУНКЦИЯ – это функция, которая дает значение ноль для любого значения аргумента. Реализовать эту функцию может не только ребенок. Можно посадить попугая и подучить его на любой вопрос о значении функции кричать «Ноль!».
ФУНКЦИЯ СЛЕДОВАНИЯ дает следующее, по сравнению с аргументом, значение. Для пяти это шесть, для миллиона – миллион один. Можно бы было сказать, что здесь надо просто прибавлять 1.
Но операции сложения у нас пока нет!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16