|
|
 |
|
 | |
Элементы логики в математических исследованиях
Основы математики - это, конечно, не вся математика. Образно говоря, это словарь, в котором изложена лексика математического языка. Если вы овладели этой лексикой, то вам остается научиться составлять правильные "предложения" и "фразы". Для этого ничего уже не нужно придумывать - все исходные понятия и аксиомы определены. Дальнейшее, можно сказать, есть техника - цепочки умозаключений, основанных на логике.
1. Теоремы и задачи.
Математические исследования можно разделить на два вида: решение задач и доказательство утверждений (теорем). Задача здесь понимается как поиск одних величин, если заданы другие (например, найти решение данного уравнения). Утверждение - это предположение о том, что данное высказывание является истинным. Например, "если верно Обычно задачей считается все: и найти что-то, и доказать что-то. Здесь мы сузили это понятие, выделив доказательство утверждений в отдельный вид исследований. При этом процедура решения задачи есть поиск алгоритма, однозначно связывающего неизвестные величины с известными. Такой поиск опирается на математические положения (аксиомы и доказанные теоремы), которые имеют отношения к этим величинам. Подчеркнем, что утверждение, строго говоря, не является высказыванием. А вот доказанные утверждения пополняют класс так называемых достоверных (т.е. заведомо истинных) высказываний и могут служить основой для определения новых понятий и формулировки новых высказываний. И чем более общий вид имеют утверждения, тем больше следствий из них можно вывести. В результате математика пополняется все более и более эффективными инструментами. Решение задач за редким исключением мало чем обогащают математику. Часто задачи служат учебным целям - усвоению положений математики на конкретных примерах. Но важнее иное - именно в возможности решения конкретных прикладных задач и заключается вся ценность математики. Можно формулировать и доказывать множество разнообразных теорем. Однако сомнительна ценность инструмента, который не может быть использован или непосредственно в прикладных задачах или для создания других, действительно полезных инструментов. Математик должен уметь решать задачи, но не обязан их решать. Задач слишком много. Большинство из них точному анализу не поддается. Приходится использовать приближенные методы или прибегать к помощи компьютера. И то, и другое целесообразнее делать для конкретных ситуаций соответствующим специалистам (физикам, программистам и пр.). Тем не менее, по отношению к задачам у математиков есть одна важная обязанность - доказывать существование (или отсутствие) решения задачи. И делать это в общей форме так, чтобы доказательство охватывало как можно больший круг задач. Т.е. доказывать утверждение вида: "каждая задача из данного класса имеет решение, обладающее такими-то свойствами". Например, "алгебраическое уравнение при таких-то условиях имеет только действительные корни, а при таких-то и комплексные". Иногда при доказательстве существования решения вырисовываются и "контуры" алгоритма решения задачи. Но даже если это не так, уверенность в существовании решения во многих случаях важнее, чем его конкретный вид (не говоря уже о том, что можно приступать к решению, зная о том, что усилия не напрасны). Если решение задачи существует, то мы можем говорить о нем, как о реальном математическом объекте, обогащая тем самым базу математики. Излагая основы математики, мы, чтобы не раздувать объем техническими деталями, не приводили доказательства многих утверждений. Была и другая причина - предоставить это самому читателю. Если читатель сможет доказать приведенные утверждения, то он овладеет не только языком математики, но и математической техникой. Т.е. будет в состоянии формулировать и доказывать новые теоремы и определять новые понятия. При этом важнейшее значение имеет строгость формулировок и безупречность доказательств. Математическая логика - это как раз тот особый раздел (можно даже сказать "особый отдел") математики, который оценивает все это ("следит" за этим). Сразу оговоримся, математическая логика не дает (и не может дать) правила, позволяющие автоматически доказать (или опровергнуть) любые утверждения. В каждом случае своя цепочка рассуждений, поиск которой невозможно формализовать в виде четкого алгоритма. Математическая логика задает критерии строгости: как формулировать утверждения, является ли доказательства правильными и т.п. Другими словами, она судит о правильности определений и рассуждений. Уместен вопрос: а правильно ли она судит? И на этот вопрос должна отвечать она сама. Математическая логика, образно говоря, и судья, и подозреваемый. Все, что она утверждает, должно иметь отношение к ней самой. Логика должна быть логичной! Это не "масло масляное", а стремление к исключительной "чистоте" (где-то даже к догматизму), к тому, чтобы вывести себя из списка "подозреваемых". В этом и достоинство, и ограниченность логики. И не удивительно, что в этом стремлении математическая логика сталкивалась (точнее, сама создавала) с неразрешимыми проблемами. Особенно, когда вынуждена была оперировать бесконечностями (например, в теории множеств). Далее мы не будем вдаваться во все тонкости математической логики. Нас будет интересовать лишь та ее часть, в которой то, что мы говорим обычным языком, формулируется в виде определенной комбинации высказываний. Мы уже касались булевой алгебры высказываний. Попробуем выяснить, что понимается под высказыванием, как они формулируются, что с ними можно делать и т.п.
2. Высказывания.
Не всякое выражение из слов и символов (предложение, соотношение) является логическим высказыванием. Основным (и, пожалуй, единственным) требованием является то, что высказывание можно оценить в категориях "истина" и "ложь". Другими словами, каждому высказыванию однозначным образом соответствует один из двух элементов простейшей булевой алгебры: " Таким образом, оперируя высказываниями, мы автоматически следуем основной аксиоме логики - закону исключения третьего (или верно, или неверно - третьего не дано). С помощью логических связок несколько высказываний можно соединять в одно высказывание, называемое составным. Высказывание "
т.е., если Многие высказывания выражаются в форме следования (импликации) или эквивалентности. Следование "если Отметим, что в обычной речи выражение "если Равносильность высказываний Далее знак равенства, если он связывает высказывания, будем считать знаком равносильности. В остальных случаях это будет обычный знак равенства (чисел, функций и т.п.), который может стоять в формулировках высказываний. Для любых высказываний (здесь и ниже, как в обычной алгебре, скобками определяется очередность операций). Простейшая булева алгебра исчерпывается соотношениями: В разделе "Общая алгебра" приведены свойства операций с элементами булевой алгебры (см. начало параграфа "Булева алгебра"). Здесь повторим те свойства, которые отличают логические операции от арифметических: для любых высказываний Множество высказываний становится булевой алгеброй, если существуют заведомо истинные (обозначение: ( Всякое составное высказывание где высказывания Т.е. при отрицании знак отрицания действует на булевы переменные, а знаки сложения и умножения меняют друг друга. Оценка булевой функции удовлетворяет соотношению где Таким образом, для оценки составного высказывания достаточно оценить более простые высказывания, которые в нем содержатся. Если для данного высказывания Структура простых (или относительно простых) высказываний может быть различной. А одна и та же структура может объединять совершенно разные высказывания. Например, высказывания "данное число простое", "данный треугольник равносторонний", "биссектриса делит угол пополам" и т.п. имеют структуру вида "объект Импликацию Чем больше следствий можно получить из данного высказывания, тем оно ценнее. Другими словами, "богатство" истинного высказывания
3. Предикаты.
Рассмотрим два выражения: "у здания есть окна", "в лесу есть деревья". Структурно эти выражения совершенно одинаковы. Однако лишь второе из них можно считать высказыванием (причем, верным по определению). Первое, чтобы оно стало высказыванием, нужно уточнять, так как возможно есть здания и без окон, а в приведенном выражении неясно о каком здании идет речь. Допустим, каждое здание имеет адрес (координаты), который мы обозначим через Выражение о зданиях можно превратить в высказывания и без задания конкретного адреса:
В логике слова "все (каждый, любой)" и "найдется (существует)", обозначаемые соответственно через
а их отрицания имеют вид ( Соотношения (8) имеют всеобщий характер: знак отрицания можно заносить под знак квантора, меняя при этом квантор общности на квантор существования и наоборот. Если переменная Однако в общем случае предикат становится определенным высказыванием или при задании переменной, или в сочетании с каким-либо квантором. При этом область изменения переменной или определена в контексте, или задается в формуле высказывания (например, "при всех Во многих случаях кванторы присутствуют неявно. Например, под высказыванием "если Итак, кванторы не усложняют переменное высказывание, а делают его определенным. Если в какой-то логической формуле, определяющей высказывание, есть предикат, то там обязательно присутствует и квантор. Отметим также, что многие аксиомы, чтобы носить более общий характер, формулируются с помощью предикатов (это касается и ряда важнейших теорем).
4. Примеры доказательств.
Всякое утверждение есть предположение о равносильности вида Главный совет: необходимо иметь четкое представление о тех базисных утверждениях, которые касаются объектов, содержащихся в Весьма полезными могут оказаться следующие положения логики.
При всей своей очевидности эти положения не всегда приходят в голову. Между тем, их использование иногда оказывается эффективным. Допустим надо доказать, что то равноценным будет доказательства того, что Из методов обычно выделяют три: от общего к частному (дедукция), доказательство от противного и метод математической индукции. От общего к частному. Если данное утверждение носит явно частный характер, то имеет смысл рассмотреть возможные варианты его обобщения. Большинство базовых утверждений носит общий характер, и вполне может оказаться, что какой-то из вариантов обобщения входит в этот круг. Например, пусть известно, что высказывание Доказательство от противного. Допустим надо доказать, что Метод математической индукции. Пусть имеется последовательность высказываний Чаще всего этот метод используется в случаях, когда сравниваются две последовательности Ниже приведены примеры доказательств, в которых используются почти все предложенные выше рекомендации. Теоремы, определяющие свойства непрерывных дробей. Пусть
(т.е. где числа
и определим наборы Докажем, что При
(теорема доказана методом математической индукции). Имеют место следующие следствия:
Отметим, что Полагая в полученных результатах Теорема Кэли-Гамильтона. Дана матрица (здесь Доказать, что Обозначим матрицу Каждый элемент матрицы где Приравнивая в (17) коэффициенты при одинаковых степенях от
где Теорема Лагранжа о порядке подгруппы. Пусть Докажем, что порядок подгруппы есть делитель порядка группы, т.е. Обозначим через Покажем, что два множества Возможны два случая.
Оставляя в наборе множеств
5. О бесконечностях.
Нижеследующее не следует считать строгим анализом понятия бесконечности (по мнению автора, такой анализ вряд ли возможен). Большинство положений математики, так или иначе, связано с понятием бесконечности. Все предикаты с кванторами, если они не представимы в виде (9), опираются на это понятие. В то же время, все противоречия и парадоксы, возникающие при логических выкладках, обязаны недостаточно аккуратному обращению с бесконечностями. Для людей бесконечность представляется чем-то невообразимым. Очень трудно осознать бесконечность окружающего мира и примириться с тем, что нет ни начала, ни конца, а есть бесконечное разнообразие природных явлений. И очень остро чувствуется, насколько беспомощен человек (и человечество в целом) перед такой безмерной и неуправляемой силой. Но точно также трудно примириться и с конечным миром. Несколько миллиардов парсек, и конец! Как это может быть? А что дальше за краем? Ничего? Что значит ничего? Нет места? Как это может быть, что больше нет места? Аналогичная реакция, если считается, что мир ограничен в структуре и есть пределы делимости. В голове не укладывается, что, например, электрон нельзя "расколоть", и его внутреннее содержание есть раз и навсегда определенная данность, недоступная для нас. Итак, нам одинаково трудно представить и конечный, и бесконечный мир. Как же жить в таком "недоуменном" состоянии? А ведь живем и не сходим с ума. И не потому, что редко задумываемся обо всем этом. Просто не вдаемся в крайности. Бесконечность нас не пугает, потому что мы с ней в жизни не имеем дело. А конечное не пугает, потому что мы его ничем не ограничиваем - все, с чем мы имели дело сегодня, завтра дополнится новыми фактами. Математики поступают приблизительно так же. В математике понятие бесконечности играет во многом решающую роль. Пределы, ряды, несобственные интегралы и многое другое, связанное с неограниченным числом операционных шагов, - все это представляет набор исключительно эффективных инструментов для математических исследований. Очень часто бесконечная цепочка операций приводят к более простым и наглядным объектам, чем результаты обрывания такой цепочки. Например, тригонометрическая функция, представляемая бесконечным степенным рядом, более наглядна и более удобна для анализа, чем любая частичная (т.е. конечная) сумма этого ряда. То же самое можно сказать о многих интегралах, когда интегрирование в бесконечных пределах приводит к более простым выражениям, чем интегрирование в конечных пределах. Точно также уравнения с производным от функций (т.е. с использованием отношений б.м. величин) легче анализировать, чем их аналоги в конечных разностях. Можно предложить различные объяснения этим фактам. Думается, что одной из причин может быть следующее обстоятельство: бесконечное, как целое, менее разнообразно, чем конечное (меньше проблем в формализации). Например, в бесконечной сумме частичные суммы представляют множество отдельных объектов, чем-то отличающихся друг от друга. В то же время их предел (если он существует) есть один объект, в котором концентрируется все то существенное, что является общим для большей части отдельных объектов. Другими словами, свойства предела будут характеризоваться меньшим числом параметров, чем свойства большинства частичных сумм. Однако при всем этом, важно, как говорилось выше, не впадать в крайности. Математика не может обойтись без бесконечностей, но и представление их реальными объектами (т.е. в виде так называемых актуальных бесконечностей) размывает логические принципы, незыблемые в анализе конечного. Дело в том, что признание чего-то, связанного с бесконечностью, фактом (отображением реальности), может быть обязано тому, что никакая его конечная "часть" не может служить его "представителем", т.е. такое "целое" может обладать свойством, не характерным для любой его части. И не удивительно, что логика может "буксовать" при ее автоматическом распространении на актуальную бесконечность. С учетом сказанного математика имеет дело с бесконечностями совершенно иного плана - с так называемыми потенциальными бесконечностями. Здесь свойства бесконечности предстают не как факты, имеющие реальную основу, а как один из вариантов предела совокупности свойств конечных объектов при неограниченном росте "размеров" этих объектов (вариант предела зависит от выбора последовательности объектов). Например, "бесконечное число" заменяется на понятие "сколь угодно большое число" и характеризуется той или иной неограниченно возрастающей последовательностью. В зависимости от вида последовательности "бесконечное число" превращается в разные по порядку величины б.б. числа, о которых мы говорили в 3-ей главе. При этом, учитывая, что всякому конечному числу соответствует нечто реальное, мы можем быть уверенными, что при такой замене в своих логических выкладках мы все время будем оставаться на "земле". Для иллюстрации сюрпризов, которые может преподносить "работа" с бесконечностями, рассмотрим геометрический объект - отрезок прямой с длиной (мерой) в Допустим, что мы выразили каждое число интервала Выделим из Такое противоречие объясняется тем, что понятие меры является относительным. Если считать, что Рассмотрим более общее разделение множества Выбор наугад в данном случае означает бесконечное число испытаний, в каждом из которых совершенно случайным образом выбирается одно из Но важнее здесь другое. Назовем число из первой части (т.е. вытащенное наугад) случайным. Очевидно, что рациональные числа не являются случайными. Возможно, что не являются случайными и числа, для которых существует конечный алгоритм последовательного расчета членов разложения. Пока данное утверждение не опровергнуто, мы должны допускать, что всякое число, определяемое с любой точностью конечным алгоритмом, не является случайным. Но тогда мы должны допускать, что мы никогда не сможем определить ни одного случайного числа. А это значит, что случайные числа по существу являются недоступными для нас. Образно говоря, являются некими фантомами, призванными для заполнения "пустот", которые неприемлемы в математическом анализе. |
|
, то верно и 
", где 
и 
- некоторые высказывания (подробнее о высказываниях речь пойдет в следующем параграфе). 
" - "ложь", "
" - "истина". Такое соответствие будем обозначать функцией 
, которая принимает одно из двух значений (
или 
) в зависимости от вида высказывания 
. Расчет значения этой функции будем называть 
.
или 
" называют 
), а высказывание "и 
, и 
" - 
. Отрицание "не 
" будем обозначать в виде 
(волнистая линия, обозначавшая отрицание в 
, то 
.
, то 
" (или "из 
следует 
") обозначают в виде 
(здесь и ниже 
и 
есть высказывания). Эквивалентность "
тогда и только тогда (в том и только в том случае), когда 
" обозначим в виде 
(или, что то же самое, 
). Это высказывание истинно, если 
и 
имеют одинаковую оценку, и ложно в остальных случаях.
, то 
" при ложном 
теряет смысл. В логике принято считать, что из ложного следует все, что угодно. Т.е. 
ложно, если 
истинно, а 
ложно, и истинно в остальных случаях: 
. 
и 
означает, что высказывание эквивалентности 
является истинным. Будем обозначать равносильность знаком равенства: 
, если 
. Отметим, что выражение 
нельзя считать высказыванием. А если и считать, то нужно говорить о следующем уровне высказываний. Но тогда такое восхождение с уровня на уровень можно продолжать до бесконечности. 
и 
имеют место соотношения:
и
.
) и заведомо ложные (обозначение: 
) высказывания такие, что 
- любое высказывание). Набор таких высказываний является базисом для оценки остальных высказываний. В математике поначалу такой базис составляют аксиомы (в том числе и определения понятий). Затем он пополняется доказанными теоремами и их следствиями. И работа математиков заключается в непрерывном расширении этого базиса. По сути дела этот базис и есть математический инструментарий.
есть булева функция
, называемые 
являются элементами простейшей булевой алгебры, результаты операций с которыми приведены в (
удается подобрать представление (
можно считать решенным. 
обладает свойством 
" (отметим, что высказывание о биссектрисе является заведомой истиной, так как это есть попросту определение биссектрисы).
и ее отрицание в соответствии с (
сложным высказыванием. Дело в том, что многие аксиомы, определения и теоремы формулируются в виде следований. Поэтому часто импликацию исследуют, так сказать, в целостном виде. Сказанное относится и к высказываниям об эквивалентности.
есть множество высказываний такое, что для каждого высказывания 
из этого множества импликация 
является истиной: 
. В этом плане особую роль играют, так называемые, предикаты.
. Тогда выражение "здание по данному адресу 
имеет окна" есть высказывание. При изменении адреса получим другое высказывание. Выражение "здание по адресу 
имеет окна", которое мы обозначим через 
, представляет весь набор таких высказываний, если задано множество возможных значений 
. Такое выражение называют 
"У всех зданий (у каждого здания) есть окна";
"Найдется (существует) здание с окнами";
"Не у всех зданий есть окна" 
"Найдется здание без окон";
"Не найдется здания с окнами" 
"У всех зданий нет окон".
и 
, образуют так называемые 
и 
можно записать в виде
= "При всех 
(имеет место) 
";
= "Найдется 
такое, что 
",
- "у здания по адресу 
нет окон"). При этом 
называют 
- 
в некотором предикате 
может иметь только конечное число значений, например 
, то высказывания с кванторами можно заменить на произведения и сумму высказываний:
из данной области 
").
, то данная функция 
" понимается не импликация, а предикат с квантором всеобщности: "для всех 
данная функция 
". 
, где 
- некоторое высказывание. Утверждение считается доказанным, если доказано, что 
, и опровергнутым, если доказано обратное. На первый взгляд кажется, что все просто. Достаточно найти представление вида (
с базовыми утверждениями (аксиомами, доказанными теоремами и т.п.). Чаще всего приходится перебирать различные варианты цепочек умозаключений, чтобы найти такую связь. А все рекомендации, методы и пр., носящие общий характер, служат в основном для того, чтобы сузить область перебора вариантов. В этом плане не является исключением и нижеследующее.
. Не только знать эти утверждения, но и представлять, какие следствия могут вытекать непосредственно из них.
. Так как
или 
. И вот часто оказывается, что высказывание 
или 
ближе к базовым утверждениям. Или же представляют проблему с иной, более "освещенной" стороны.
истинно. Это означает, что истинны и все высказывания вида 
, где 
и 
конкретные значения переменных 
и 
.
. Допустим обратное 
, т.е. 
. Это может иметь смысл, если такое предположение богато следствиями. Если среди этих следствий найдутся или противоречащие друг другу, или противоречащие базовому утверждению, то это указывает, что обратное было неверным, и 
.
, и надо доказать, что 
. Допустим, нам удалось доказать, что 
. Тогда достаточно доказать следующее: при любом 
если верно 
, то верно и 
. Т.е. в основе метода математической индукции лежит следующее положение о равносильности:
и 
(
). Непосредственное сравнение возможно, если известна явная зависимость членов последовательности от номера. Если одна последовательность (или обе) определена только рекуррентными соотношениями (или иным неявным образом), то напрашивается именно метод математической индукции.
),
при всех 
. Обозначим
и 
следующим образом:
это верно: 
. Пусть это верно при 
. Тогда
может быть сколь угодно большим. 
целыми положительными числами, получим частные случаи, касающиеся свойств непрерывных дробей (как конечных, так и бесконечных).
порядка 
, и
- единичная матрица) есть характеристический полином матрицы 
, где 
- числовая переменная.
удовлетворяет своему характеристическому уравнению: 
через 
и введем матрицу 
, где 
есть алгебраическое дополнение элемента 
матрицы 
:
является полиномом от 
степени не выше 
, т.е.
- некоторые матрицы, не зависящие от 
.
(возможность этого следует из того, что (
), с учетом (
. Тогда
есть собственная подгруппа конечной группы 
. Обозначим через 
порядок (число элементов) подгруппы 
, а через 
- то же для группы 
.
, где 
- целое число.
элементы группы 
, не входящие в подгруппу 
. Элементы подгруппы 
обозначим 
. Через 
обозначим множество элементов 
(очевидно, что все эти элементы различные). Элементами подгруппы 
и множеств 
исчерпываются все элементы группы 
. При этом каждое множество 
содержит ровно по 
элементов.
и 
при любых 
или полностью совпадают, или не имеют ни одного общего элемента.
. Тогда найдется элемент 
такой, что 
. Отсюда следует, что при любом 
элемент 
, т.е. каждый элемент из 
содержится в 
.
. Допустим, что некоторый элемент 
из 
совпадает с некоторым элементом 
из 
. Тогда
и 
нет общих элементов. 
, попарно не пересекающиеся множества, мы вместе с подгруппой 
получим набор не пересекающихся множеств. Каждый элемент группы 
входит в одно и только одно множество из этого набора, а каждое множество содержит по 
элементов. Теорема доказана. 
см. Множество внутренних точек этого отрезка можно взаимно однозначным образом отобразить множеством действительных чисел интервала 
с мерой равной 
. 
в десятичной системе последовательностью целых чисел, принимающих значения от 
до 
. Множество всех таких последовательностей обозначим через 
. Очевидно, что такое отображение также является взаимно однозначным. Мерой подмножества множества 
будем считать совокупную длину, занимаемую точками отрезка, которые отображаются данным подмножеством. 
подмножество 
последовательностей, не содержащих число 
. Нетрудно убедиться, что подмножеству остальных последовательностей соответствуют на отрезке области точек, суммарная длина которых равна 
см. Это значит, что мера подмножества 
равна нулю. В то же время 
представляет не что иное, как множество 
всех чисел интервала 
, выраженных в девятичной системе. Но это значит, что мера множества 
(а значит и мера 
) равна 
. 
есть подмножество множества 
, то его мера равна 
. А если 
считать представлением чисел интервала 
в девятичной системе, то его мера равна 
. Таким образом, множество ненулевой меры можно взаимно однозначным образом отобразить своим подмножеством, имеющим нулевую меру. Однако на этом неожиданности не кончаются.
на две части. Пусть первая часть состоит из последовательностей, содержащих (подряд и без пропуска) любую конечную последовательность чисел от 
до 
, а вторая - из остальных. Можно доказать, что мера второй части равна 
. Образно говоря, любое наугад выбранное число из интервала 
содержит (с вероятностью 
) в какой-то конечной части своего разложения в десятичной (или в любой другой) системе любой "оцифрованный" роман Л.Н.Толстого.
чисел. А это связано с получением бесконечного количества информации и, конечно, в этой информации будет содержаться любая конечная информация.
