Содержание и значение математической символики

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

Для уравнения четвертой степени он также указал условие разрешимости; оно состоит в разрешимости его кубической резольвенты, т. е. соответствующего уравнения шестой степени, кубического относительно у2.

Декарт не показал, как он получил окончательный результат. Ф. Схоотен вывел резольвенту с помощью метода неопределенных коэффициентов. Он представил многочлен четвертой степени в виде x4 - px2 - qx + r = (x2 + yx + z)(x2 - yx +v), откуда получил уравнения для нахождения у, z, у: z - y2 + v = -p, -zy+vy = -q, vz = r.

Разрешающее уравнение (резольвента) имеет вид у6 - 2ру4 + (р2 - 4г)y2 - q2 = 0.

В конце третьей книги «Геометрии» Декарт графически решал уравнения третьей, четвертой, пятой и шестой степеней, отыскивая их корни как пересечение некоторых линий.

Вклад Декарта в математику не ограничивается одной «Геометрией»: в его переписке содержатся решения многих задач, в том числе связанных с бесконечно малыми.

§3 Обозначение производной и интеграла у Лейбница и развитие анализа

Лейбниц внес большой вклад в развитие математического анализа. Ему принадлежит создание многих символов, которые мы используем сейчас, например, dx, ddx,…, d2x, d3x, ,. Но символы эти появились у Лейбница не сразу. Первоначально выражение = хu (1)

у него выглядело следующим образом: omn. xw = ult. х?omn. w - omn. omn. w. При этом он еще не употреблял привычного нам знака равенства.

В этом выражении omn. - начальные буквы латинского слова omnia, т. е. все, - обозначает объединение, суммирование «всех» бесконечно малых элементов, стоящих под этим знаком, х обозначает абсциссу точки на кривой, исходящей из начала координат, w в этих выкладках Лейбница обозначает то элемент дуги (ds), то дифференциал ординаты (dy), ult. - начальные буквы латинского слова ultima (т. е. последняя) - относится к абсциссе.

Для Лейбница в данном случае его omn.w выступает в роли новой функции, которая сама становится объектом операции, обозначенной omn. Как это обстоятельство, так и то, что он рассматривает результат многократного применения преобразования вида (1) и получает выражения, в которых операция omn. наслаивается несколько раз, заставило его искать более удобное обозначение, и в записи от 29 октября мы читаем: полезно писать вместо omn., так что будет вместо omn. (- это начальная буква слова summa и Лейбниц называет этот знак суммой). И для нового исчисления, как в той же записи выражается Лейбниц, имеем

Первое из этих соотношений соответствует преобразованию (1), а, b - постоянные, черта сверху играет роль скобки, и она, собственно, лишняя, да и Лейбниц не всегда ее пишет, но ее, пусть несистематическое, появление характерно: так, в записи х мы видим, что пишущему кажется необходимым дополнительно указать, что на х действительно умножаются все , собранные в сумму знаком. Лейбниц далее записывает (по поводу формул (2) и их вариантов): «Это достаточно ново и примечательно, поскольку указывает на новый вид исчисления», и переходит к обратному исчислению (contraРазмещено на http://www.allbest.ru/

rio calculo), вводя символ d, который «уменьшает измерение так, как увеличивает», но пишет его в знаменателе (не dy, a y/d).

Тут же читаем: обозначает сумму, d - разность. Несколькими днями позже, в рукописи, помеченной 10 ноября, Лейбниц записывает: «dРазмещено на http://www.allbest.ru/

x -- то же самое, что x/d, то есть разность между двумя ближайшими».

Замечательно то, что Лейбниц сразу, введя новое обозначение, начинает с ним обращаться как с символом операции, отделяя его от объекта операций: он сразу отметил, что его «сумма» от (двух) слагаемых равна сумме «сумм» слагаемых и что постоянный множитель или делитель можно выносить за знак «суммы». В записях последующих дней (от 1, 10, 11 ноября) он отмечает такие же свойства операции, обозначенной через d. За эти дни Лейбниц убедился, что d(xy) не то же самое, что dx?dy, и что d(x/y) ? dx/dy, но не вывел еще соответствующих формул. Отметил он и что , конечно, не то же самое, чтоРазмещено на http://www.allbest.ru/

. Он уже систематически использует обратность действий и d, например, после равенства Размещено на http://www.allbest.ru/

он пишет: или wz = y2/2d (тут d еще в знаменателе). Отмечены им уже формулы для производной степенной функции при целых показателях степени, например, «из квадратуры треугольника ясно, что y2/2d = у; = из квадратуры параболы».

А в том, что он открывает здесь нечто весьма существенное, Лейбниц, вероятно, окончательно убедился, когда смог использовать пока как бы нащупываемый им алгоритм при решении задач на обратный метод касательных. Он писал: «Еще в прошлом году я поставил перед собой вопрос, который можно отнести к труднейшим во всей геометрии, поскольку распространенные до сих пор методы здесь почти ничего не дают. Сегодня я нашел его решение и я приведу его анализ».

Свою задачу Лейбниц формулирует как определение кривой, у которой поднормали обратно пропорциональны ординатам. Такая задача сводится, в современных обозначениях, к решению дифференциального уравнения ydy/dx = k/y, где k - постоянная. Решение Лейбница состоит по сути в составлении такого уравнения и последующем его интегрировании с помощью разделения переменных. Он получил, таким образом, уравнение искомой кривой, и она оказалась кубической параболой.

По записям Лейбница видно, что к середине 1676 г. он, располагая уже всеми основными правилами дифференцирования и интегрирования, решил еще несколько задач на обратный метод касательных, в том числе знаменитую в XVII в. задачу де Бона, предложенную в свое время Декарту, который не смог получить ее общее решение. И это результат вполне самостоятельного хода мыслей. То, что Лейбниц знал к тому времени относительно результатов Ньютона и Грегори, никак не могло помочь ему пройти избранный им путь. Операционный подход Лейбница к проблеме и его поиски рациональной символики для нового исчисления, в чем наиболее полно выразилась творческая индивидуальность Лейбница, были в достаточной мере чужды его английским соперникам.

Примерно через год после открытий 1675 г., во время поездки по Голландии и после встречи там с Гудде, Лейбниц составил заметку, озаглавленную «Дифференциальное исчисление касательных». Она начинается записями:

Отсюда выводится общее правило для разностей и сумм простых степеней:

Как видно, здесь знак d обозначает операцию вычисления производной. Но Лейбниц еще не вполне выработал к тому времени свою символику и чуть ниже можно прочитать, что «общее правило устанавливается так: и, наоборот,». Такая редакция общего правила следует за замечанием: «пусть у = x2, тогда будет = 2xРазмещено на http://www.allbest.ru/

, следовательно, Размещено на http://www.allbest.ru/

= 2x». И на полях, вероятно, позРазмещено на http://www.allbest.ru/

же, Лейбниц написал, что это отличное замечание к его исчислению разностей: «если by+ + etc. = 0, то b+ = 0, и так с остальными». Здесь он начинает свободно обращаться с дифференциалами, как это ему удобно при решении дифференциальных уравнений, не предопределяя, какое из переменных независимое, какое функция.

Дальше в том же наброске следует замечание, что вот, «возьмем какое-либо уравнение (но берется уравнение алгебраической кривой, притом второго порядка) ... и напишем у +dy вместо у и подобным образом x + dx вместо х, тогда, опустив то, что опустить надлежит, получим другое уравнение» (т. е. оставляются только слагаемые первого порядка относительно дифференциалов, и это показано на примере).

Отсюда вытекает правило, обнародованное Слюзом, продолжает Лейбниц, и это, конечно, верно. Тут же он добавляет, что «мы бесконечно расширим это правило: пусть букв будет сколько угодно и из них составлена формула, например, из трех букв...». И Лейбниц сопоставляет уравнение алгебраической поверхности опять-таки второго порядка и небезупречно составленное путем дифференцирования соотношение между дифференциалами, чтобы заявить без дополнительного обоснования: «Отсюда явствует, что по такому методу получаем касательные плоскости поверхностей, и не имеет значения при этом, существует ли еще иное соотношение между теми же буквами х, у, z, его ведь можно будет подставить позже».

Конечно, указание на то, как определить касательную плоскость к поверхности, следовало еще развить, что в рассматриваемом отрывке отсутствует, но мы видим здесь пример того, как Лейбниц постепенно, по разным поводам, возвращается к своему исчислению, расширяет область его применения, наряду с новыми результатами получает с его помощью известные старые.

В 1678 г. Чирнгаус заявил Лейбницу, что надо по возможности избегать новых обозначений, ибо это только затрудняет доступ к науке. Вот Виет заслуживает похвалы за то, что обходится буквенными обозначениями, не вводя новых чудовищных знаков. Лейбниц, возражая подчеркивал, что надо искать обозначения, которые кратко выражают сокровенную сущность предмета, облегчая путь к открытиям и значительно уменьшая затрату умственного труда. И таковы, продолжал Лейбниц, использованные мною знаки - я часто с их помощью в несколько строк решаю самые трудные задачи.

В 1684 г. в «Лейпцигских ученых заметках» появилась одна из самых знаменитых математических работ: «Новый метод максимумов и минимумов, а также касательных, для которого не являются препятствием ни дробные, ни иррациональные величины, и особый для этого род исчисления». В этой небольшой статье даны основы дифференциального исчисления. Правила дифференцирования приводятся без доказательств, хотя есть указания на то, что здесь все можно обосновать, рассматривая дифференциалы как бесконечно малые разности. Определение дифференциала функции дано как произведение производной (но производная задается геометрически как отношение ординаты к подкасательной) на дифференциал аргумента. Последний можно задавать произвольно. Еще не вводится определенное соглашение относительно выбора знака для длин отрезков, которыми оперирует Лейбниц, поэтому он привод некоторые формулы с двумя знаками. В статье были опечатки, затруднявшие чтение, были и ошибочные утверждения (относительно определения точек перегиба). Но в ней были и эффективные примеры применения нового алгоритма, и автор, приведя их, имел право заявить: «Во всех таких и много более сложных случаях наш метод обладает одной и той же поразительной и прямо беспримерной легкостью. Но это лишь начала некой более высокой Геометрии, которая распространяется на труднейшие и прекраснейшие задачи прикладной математики, и едва ли кому-нибудь удастся заняться с той же легкостью такими вещами, не пользуясь нашим дифференциальным исчислением или ему подобным».

Год 1690-й отмечает новый этап: начинается переписка и многолетнее научное общение Лейбница с Яковом Бернулли, а затем и его младшим братом Иоганном, напечатана первая работа по анализу старшего из братьев, и оба они, математики первого ранга, отныне все усилия приложат для развития нового исчисления.

Через посредство И. Бернулли с новым исчислением знакомится и становится его приверженцем самый значительный французский механик тех лет П. Вариньон.

На Лейбница появление приверженцев его метода и умножение примеров, показывающих плодотворность созданного им исчисления, действовало стимулирующе.

Новые результаты Лейбница достаточно разнообразны. Некоторые из них относятся к технике дифференцирования. Так, в «Новом методе...» 1684 г. дифференцируются только алгебраические функции, рациональные и иррациональные, и, в неявном виде, логарифм, а в 90-е годы Лейбниц, можно сказать, мимоходом в различных работах указывает дифференциалы синуса и арксинуса, функции вида uv, где основание и показатель степени -- функции независимого переменного, вводит дифференцирование по параметру. Позже Лейбниц дает носящую его имя формулу для дифференциала любого порядка от произведения функций. Можно сказать, что на этой стадии операция дифференцирования у Лейбница охватила весь запас известных тогда функций.

Другая группа результатов Лейбница относится к дифференциальной геометрии. Один из наиболее существенных - введение огибающей семейства плоских кривых, зависящих от некоторого параметра.

В третью группу можно объединить результаты по интегральному исчислению. Кроме формул, представляющих собой обращение упомянутых формул дифференцирования, Лейбниц дал две работы об интегрировании рациональных дробей (1701 и 1703 гг.). В первой из них он допустил ошибку, сделав вывод, что при наличии комплексных корней у знаменателя рациональной дроби с действительными коэффициентами интегрирование должно ввести новые трансцендентные функции, кроме обратных круговых и логарифмов. Когда же И. Бернулли указал правильный результат, Лейбниц с ним не согласился и повторил свое ошибочное заключение во второй работе. Эта ошибка Лейбница - не только математический недосмотр, она имеет любопытные корни. Утверждение, что интегралы вида дают новые трансцендентные функции казалось ему и привлекательным и правдоподобным еще потому, что это соответствовало лейбницевой метафизике. Если бы все интегралы такого вида сводились, как выражается Лейбниц, только к квадратуре гиперболы (т. е. логарифмам) и к квадратуре круга (к обратным круговым функциям), то все было бы единообразно. «Но природа, мать вечного разнообразия, или, лучше сказать, божественный дух слишком цепко оберегает свою прекрасную многоликость, чтобы допустить слияние всего в одну породу. И таким образом он находит изящный и удивительный выход в этом чуде анализа, этом побочном порождении мира идей, двойственном существе как бы между бытием и небытием, что мы называем мнимым корнем. И посему всякий раз, когда знаменатель рациональной дроби имеет мнимые корни, что может получиться бесконечно многими способами, будет мнимой и гипербола, квадратура которой нам нужна, и ее никоим образом нельзя будет построить».

От Лейбница не ускользнуло и то, что интеграл можно рассматривать как дифференциал с показателем -1, и это привело его к введению дифференциалов любых отрицательных и дробных порядков с помощью бесконечных рядов. Теорию интегралов и производных дробного порядка развивали в XVIII в. Эйлер, в XIX в. - Лиувилъ, Риман, Летников, в XX в. - Г. Вейль, М. Рис и др., и сейчас она составляет один из разделов анализа. Лейбниц же первый в печати указал на то, что операция интегрирования вводит произвольную постоянную и на связь между определением первообразной функции и квадратурой. Он указал также, как интегрировать некоторые типы обыкновенных дифференциальных уравнений. Существенно то, что Лейбниц отчетливо определил взаимоотношение интегрирования дифференциальных уравнений и интегрирования функций (первое следует считать выполненным, если оно сведено ко второму), и, аналогично, интегрирования функций и алгебраических операций (например, определение корней знаменателя подынтегральной рациональной дроби считается при интегрировании задачей решенной).

Лейбниц много занимался также интегрированием иррациональностей (в конечном виде, как стали позже выражаться) и глубоко проник в суть этой проблемы.

Заслугой Лейбница является и применение к интегрированию и функций и дифференциальных уравнений бесконечных рядов с использованием метода неопределенных коэффициентов (последний метод восходит к Декарту). Немалое значение для успехов нового анализа имело достаточно общее введение такого понятия, как функция, и систематические выступления Лейбница против ограничения (по Декарту) предмета геометрии изучением алгебраических кривых. Наконец, Лейбниц на деле доказал достоинства своего исчисления, с успехом участвуя в конкурсах на решение таких трудных для того времени задач, как задача Галилея о цепной линии и задача И. Бернулли о брахистрохроне.

Историческое значение математического творчества Лейбница огромно. Оно длилось около сорока лет, и за такой сравнительно небольшой срок математика преобразилась. Наука, в которую вступил Лейбниц, и наука, которую он оставил, принадлежит разным эпохам, и это плод главным образом его трудов и трудов его школы. До Лейбница в обширную область неведомого пытались проникнуть то тут, то там, наскоками, пусть порою очень удачными, не имея общего плана. Благодаря Лейбницу разрозненные прежде усилия были подчинены общей программе, прояснились и близкие и далекие цели, средства для их достижения оказались в распоряжении не только сверходаренных одиночек и значительно выиграли в эффективности.

§ 4. Язык кванторов и основания математической логики

В связи с тем, что элементы логики представляют собой неотъемлемую составную часть школьного обучения математике, они должны изучаться в единстве с собственно математическим материалом на всех этапах обучения. Соответствующий язык необходимо вводить постепенно для обозначения уже разъясненных математических и логических понятий, чтобы в дальнейшем он становился необходимым компонентом обиходного математического языка.

4.1 Алгебра высказываний

Эта тема важна для школьной математики. Не овладев ее основными действиями, нельзя понять последующие темы, как, не овладев таблицами сложения и умножения, нельзя научиться арифметике и тем более алгебре.

Исходные объекты алгебры высказываний - это простые высказывания. Их будем обозначать строчными латинскими буквами a, b, c, …, x, y, z. Предполагается, что всякое простое высказывание обладает одним и только одним из двух свойств: либо оно истинно, либо ложно.

Будем пользоваться почти повсеместно принятой терминологией: свойства истинности (и) и ложности (л) мы будем называть значениями истинности высказываний. При такой терминологии значение истинности сложного высказывания есть функция от значений истинности простых высказываний; такая функция называется логической связкой.

4.1.1 Определения основных логических связок

а) Отрицание (знак u ). Если а - высказывание, то uа (читается: «не а») также высказывание; оно истинно или ложно в зависимости от того, ложно или истинно высказывание а.

Таким образом, операция отрицания описывается следующей таблицей:

Мы видим, что операция u в теории высказываний вполне соответствует понятию отрицания в обыденном смысле слова. Если, например, а - высказывание «Число три делит число шесть», то отрицанием uа этого высказывания будет «Число три не делит число шесть». Высказывание а при этом истинно, высказывание uа, - ложно.

Если же в качестве высказывания а взять какое-нибудь ложное высказывание, например «Число три делит число пять», то его отрицание uа будет высказывание «Число три не делит число пять» - истинное высказывание.

б) Конъюнкция. В качестве знака для конъюнкции мы будем употреблять знак U (можно также &).

Если а и b - высказывания, то а U b (читается: «а и b») - новое высказывание; оно истинно тогда и только тогда, когда а истинно и b истинно.

В отличие от операции отрицания, зависящей от одного элементарного высказывания, конъюнкция, как и все последующие приводимые нами связки, зависит от двух элементарных высказываний, поэтому они называются двуместными связками, отрицание же - связка одноместная.

Для задания двуместных связок удобно записывать матрицы истинности в виде таблиц с двумя входами: строки соответствуют значениям истинности одного элементарного высказывания, столбцы - значениям другого элементарного высказывания, а в клетке пересечения столбца и строки помещается значение истинности соответствующего сложного высказывания.

Значение истинности сложного высказывания а U b задается матрицей

Как видно, определение операции конъюнкции вполне соответствует обыденному значению союза «и»:

в) Дизъюнкция. В качестве знака для дизъюнкции мы будем употреблять знак U.

Если а и b - высказывания, то а U b (читается: «а или b») - новое высказывание, оно ложное, если а и b ложны; во всех остальных случаях а U b истинно.

Таким образом, матрица истинности для операции дизъюнкции выглядит так:

Операция дизъюнкции довольно хорошо соответствует обыденному значению союза «или».

Примеры.

«Три делит пять или три больше шести» ложно;

«Три делит шесть или три больше шести» истинно;

«Три делит шесть или три меньше шести» истинно.

г) Импликация. В качестве знака для импликации будем употреблять знак ?.

Если а и b - два высказывания, то а ? b (читается: «а имплицирует b») - новое высказывание; оно всегда истинно, кроме того случая, когда а истинно, а b ложно.

Матрица истинности операции импликации следующая:

В импликации а ? b первый член а называется антецедентом, второй b - консеквентом.

Операция ? описывает в некоторой мере то, что в обыденной речи выражается словами «Если а, то b», «Из а следует b», «а - достаточное условие для b», но на этой аналогии не следует слишком настаивать. Действительно, учитывая определение импликации, данное выше, и интерпретируя выражение а ? b как «если а, то b», мы получаем: «Если дважды два - четыре, то трижды три - девять» - истинное высказывание; «Если дважды два - пять, то трижды три - восемь» - истинное высказывание и только высказывание типа «Если дважды два - четыре, то трижды три - восемь» ложно.

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

Несколько позже мы убедимся, что операция импликации достаточно точно выражает понятие логического следования в той форме, как оно употребляется в математике.

д) Эквиваленция. Для этой операции мы будем употреблять знак U. Операция эквиваленции определяется так: если а и b - два высказывания, то а U b (читается: «а эквивалентно b»; U соответствует словесному выражению «...тогда и только тогда, когда...») - новое высказывание, которое истинно, если либо оба высказывания истинны, либо оба - ложны.

Из этого определения связки U следует, что ее матрица истинности выглядит так:

Введенными пятью связками (u, U, U, ?, U) мы ограничимся.

С помощью уже введенных связок мы можем строить сложные высказывания, зависящие не только от двух, но и от любого числа элементарных высказываний.

Отметим в этой связи, что так называемое нестрогое неравенство а ? b (читается: a меньше или равно b») представляет собой дизъюнкцию (а < b) U (a = b); оно истинно, если истинно по меньшей мере одно из входящих в него простых высказываний. Хорошими примерами сложных высказываний, встречающихся в школьной практике, являются так называемые двойные неравенства. Так, формула а < b < с означает (а < b) U (b < с), а, например, а < b ? c означает сложное высказывание (а < b) U ((b < c) U (b = c)).

Построение сложных высказываний делается аналогично тому, как в элементарной алгебре с помощью операций сложения, вычитания, умножения и деления строятся сколь угодно сложные рациональные выражения. А именно, предположим, что мы уже построили два каких-нибудь сложных высказывания, которые мы ради удобства сокращенно обозначим большими латинскими буквами А и В (при этом мы условимся, что элементарные высказывания следует рассматривать как частный случай сложных). Тогда новые высказывания можно получить, соединив А и В одним из знаков U, U, ?, U или же построив высказывание uА и заключив результат в скобки. Сложными высказываниями будут, например, высказывания следующего вида:

((а ? b) U (с U а)); ((а ? b) U (с ? uа)).

При этом предполагается, что встречающиеся здесь буквы являются сокращенными обозначениями каких-либо высказываний.

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

Располагая значением истинности простых высказываний, легко подсчитать на основании определения связок значение истинности сложного высказывания. Пусть, например, дано сложное высказывание

((bU с) U (b U a))

и пусть входящие в него элементарные высказывания имеют следующие значения истинности: а = л, b = и, с = и. Тогда b U с = и, b U a = л, так что (( bU с) U (b U а)), т. е. рассматриваемое высказывание ложно.

4.1.2 Высказывания и булевы функции

Одной из основных задач алгебры высказываний является установление значения истинности сложных высказываний в зависимости от значения истинности входящих в них простых высказываний. Для этого целесообразно рассматривать сложные высказывания как функции входящих в них простых высказываний. С другой стороны, так как значение истинности (и или л) сложного высказывания зависит по определению логических связок не от самих простых высказываний, а лишь от их значения истинности, то можно считать, что любое сложное высказывание определяет функцию, аргументы которой независимо друг от друга принимают значения и или л, а значение самой функции также принадлежит множеству {и, л} (конечно, существенно не то, что речь идет о функциях от нескольких аргументов из множества {и, л} в множество {и, л}, а лишь то, что данные множества двухэлементны. Эти множества зачастую обозначают не через {и, л}, а, например, через {0, 1}, считая, что 1 означает «истину», а 0 - «ложь»).

Такие функции называются булевыми функциями (по имени Д. Буля). Например, формула F (а, b, с) = (а U b) ? (с U а) описывает, учитывая определение входящих в нее связок, булеву функцию, задаваемую следующей таблицей:

Заметим, что булевых функций от n аргументов имеется лишь конечное число, а именно столько, сколько возможно функциональных таблиц. Число возможных наборов аргументов равно 2n, а каждому набору аргументов можно независимо друг от друга сопоставлять одно из значений и или л. Таким образом, число всевозможных булевых функций от n аргументов равно Размещено на http://www.allbest.ru/

- Оно очень быстро растет с ростом n. Изучение свойств булевых функций имеет большее значение как для алгебры и математической логики, так и для их приложений в кибернетике и теории автоматов. Естественно распространить определение высказывательных связок, так как мы их определили выше, на булевы функции. Мы ограничимся рассмотрением лишь связок U, U, u называемых булевыми связками (или булевыми операциями). Такое ограничение оправдано тем, что, как легко проверить, связки ? и U могут быть выражены через другие булевы связки. При помощи таблиц истинности, приведенных выше, легко проверяются следующие тождества:

a ? b ? (u a) U b;

a U b ? (a U b) U (u a U ub),

которые позволяют повсеместно заменить связки ?, U на U, U, u.

Если мы теперь имеем булевы функции {F (xl, х2, ..., хn), G (х1, х2, ..., хn)} от n переменных, то действие связок над ними определяется естественным образом:

F (xl, x2, ..., хn) U G (х1, x2, ..., хn), F (xl, x2, ...,хn) U G (xl, x2, ..., хn), uF (xl, x2, ..., хn) - это такие булевы функции, которые принимают значения, предписываемые соответствующими таблицами для каждого возможного значения аргументов. Кратко: булевы операции так переносятся на булевы функции, как действия арифметики переносятся на обычные функции числовых аргументов. Вообще имеет место далеко идущая аналогия между обычной алгеброй чисел и числовыми функциями, с одной стороны, и высказываниями и булевыми функциями - с другой. При этом можно отметить, что в одном определенном смысле алгебра булевых функций проще алгебры числовых функций: если рассматривать лишь функции некоторого конечного числа аргументов, то таких функций лишь конечное число. Поэтому выкладки с булевыми функциями вполне доступны пониманию школьников старших классов.

Естественно, закономерности булевой алгебры менее привычны и вызывают удивление и недоверие: это судьба всякого новшества.

Выпишем законы булевой алгебры. Большими латинскими буквами А, В, ..., X, Y, Z мы обозначим объекты, над которыми осуществляются булевы операции U, U, u. Для определенности будем считать, что эти объекты - булевы функции некоторого фиксированного числа переменных. Среди них есть два особых элемента: 1, 0. Это соответственно функции, принимающие для всех аргументов значения 0 и 1 (постоянные функции - нуль и единица). Тогда

А U В = В U А, A U B = B U A

A U (В U C) = (А U В) U C A U (В U C) = (А U В) U C

A U A = A A U A = A

A U 1 = A A U 1 = A

A U 0 = 0 A U 0 = A

u(A U B) = uA U uB u(A U B) = uA U uB

A U (B U C) = (A U B) U (A U C) A U (B U C) = (A U B) U (A U C)

u uA = A

Если, как это обычно делают, булевы операции U, U, u считать аналогом сложения, умножения и перехода к противоположному числу, то некоторые из вышеприведенных законов те же, что для числового сложения и умножения, другие же существенно отличаются от привычных.

4.1.3 Задания для учащихся

Верно ли высказывание: u(205 кратно 5); 77;Размещено на http://www.allbest.ru/

u(8>10); 1?3?3.

А - множество точек треугольника и В - множество точек четырехугольника.

Верно ли высказывание: CIA U CIB; KIB U KIA; SIB U SIA; u(SIA)USIB?

Известно, что А=и, В=и, Х=л, Y=л. Найдите значение высказывания:

АUuХ; uYUuA; A?X; u(uВUY); (AUB)UX; (XUB)?Y; (XUA)?(YUB); u (AUX)U(YUuX).

Составьте таблицу истинности высказываний: uХUХ; (ХUY)UuY; (XUY)UuX; uX?Y; (XUY)?Y.

Используя переменные X, Y, Z, запишите сочетательное свойство операции «и».

Проверьте равенство (XUY)UZ ? (XUZ)U(YUZ) и (XUY)UZ?(XUZ)U(YUZ), составляя таблицы истинности для левой и правой части.

4.2 Предикаты и кванторы

4.2.1 Предикаты

Алгебра предикатов - тот раздел математической логики, который непосредственно надстраивается над алгеброй высказываний.

Как мы видели, одной из основных задач алгебры высказываний является изучение истинности или ложности высказываний в зависимости от истинности или ложности входящих в них высказываний. Несмотря на большую важность этой области логики, она оказывается слишком бедной для описания и для изучения даже простейших заключений науки и практики. В рамки алгебры высказываний не укладываются ни простейшие заключения арифметики и геометрии, не говоря уже о довольно сложных логических выводах, с которыми мы сталкиваемся в других науках и в повседневной жизни.

Действительно, рассмотрим следующие простейшие заключения.

Из истинных высказываний «3 меньше 5» и «5 меньше 7» мы заключаем, что «3 меньше 7». Из истинных высказываний «Все птицы - животные» и «Все воробьи - птицы» мы делаем заключение: «Все воробьи - животные». Из высказываний «Петр - сын Ивана» и «Павел - сын Петра» мы заключаем: «Павел - внук Ивана» и т. д.

Заметим, что во всех рассмотренных примерах истинность заключения зависит не только от истинности посылок, но и от их содержания. Если изменить вид посылок, то может оказаться, что заключение будет неверным. Так (в первом примере) из истинных высказываний «3 меньше 5» и «5 не равно 7» нельзя делать заключение (которое оказывается истинным), что «3 меньше 7», или, изменив немного второй пример, из истинных высказываний «Все птицы - животные» и «Никакие рыбы не птицы» нельзя выводить ни ложное высказывание «Никакие рыбы не животные», ни истинное высказывание «Все рыбы - животные». Наконец, видоизменив последний пример, из истинных высказываний «Петр - сын Ивана» и «Павел - родственник Петра» мы не имеем права делать заключение (которое в действительности может быть как истинным, так и ложным), что «Павел - внук Ивана» (но можем вывести истинное заключение: «Павел - родственник Ивана»).

Чтобы построить систему правил, позволяющую логически выводить правильные заключения, учитывающие в какой-то мере содержание посылок, мы должны проанализировать строение простых высказываний. И здесь нам опять кое-что может подсказать грамматика. Следуя по такому пути, мы придем к разделу логики, называемому алгеброй предикатов. Она предполагает алгебру высказываний уже известной, но идет дальше: простые высказывания, из которых состоят сложные, в свою очередь расчленяются.

Теория предикатов исходит из следующей установки. Простые высказывания выражают, что некоторые объекты обладают некоторыми свойствами или находятся между собой в некоторых отношениях.

При этом понятия «свойство» и «отношение» рассматриваются как частные случаи общего понятия «предиката». Объекты, о которых говорится в высказываниях, называются «термами». Постараемся выяснить смысл этих понятий на примерах.

Рассмотрим сначала некоторое число простых предложений - высказываний, выражающих, что некоторый объект обладает некоторым свойством:

«Сократ - грек»;

«Платон - ученик Сократа»;

«Три - простое число»;

«Василий - студент» и т. д. ,

Все приведенные примеры - простые предложения, С точки зрения грамматики они состоят из подлежащего («Сократ», «Платон», «три», «Москва», «Василий») и сказуемого («есть грек», «есть ученик Сократа», «есть простое число»). Подлежащее является наименованием некоторого объекта - конкретного или абстрактного, сказуемое выражает некоторое свойство. В латинской грамматике сказуемое называется предикатом, и этим термином принято теперь пользоваться в математической логике в рассматриваемых ситуациях. Основным для алгебры предикатов является второй член предложения - сказуемое-свойство. Как же алгебра предикатов трактует понятие «свойство»? Она рассматривает его как некоторую функцию следующим образом.

Возьмем первый пример: «Сократ есть грек».

Вместо человека Сократ мы можем подставить имена всевозможных людей и будем получать всегда осмысленные предложения. Одни предложения будут истинными, другие - ложными:

«Сократ есть грек» - истинно;

«Платон есть грек» - истинно;

«Наполеон есть грек» - ложно;

«Ньютон есть грек» - ложно и т. д.

Более обще можно рассматривать выражение вида «X есть грек», где буква X указывает место, на которое нужно подставить имя некоторого человека, чтобы получить высказывание -- истинное или ложное. Но, как нам уже известно, существенным свойством высказывания является его значение истинности и или л. Становясь на эту точку зрения, логика предикатов считает выражение «X есть грек» функцией, аргумент которой X пробегает класс всех людей, а сама функция принимает в качестве значений и или л. Если мы будем, как это принято в математике, «X есть грек» записывать сокращенно, например в виде Гр (X), то для значения X = Сократ получим Гр (Сократ) - и, а скажем Гр (Наполеон) - л и т. д. Относительно других приведенных примеров можно дословно повторить все то, что было сказано относительно первого.

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

Отсюда сразу видно, что в действительности всякий предикат-свойство вполне определяется подмножеством тех объектов, на которых данная функция принимает значение «истинно». Полезно привести примеры предикатов-свойств из области арифметики. Такими будут, например, свойства натуральных чисел «быть простым числом», «быть четным числом», «быть квадратом» и т. д.

Остановимся на примере «три есть простое число» и на соответствующем предикате-свойстве «быть простым числом». Введем для этого свойства сокращенное обозначение Пр (X). Предикат Пр (X) определен на множестве натуральных чисел. Имеем Пр(1) = л (поскольку 1 не принято рассматривать как простое число). Пр (2) = и, Пр (3) = и, Пр (4) = л, ..., Пр (10) = л, Пр (11) = и и т. д.

Подобно приведенным предикатам-свойствам, математическая логика рассматривает более общее понятие предиката-отношения. В зависимости от того, между каким числом объектов устанавливается отношение, мы различаем двухместные (бинарные), трехместные (тернарные) и т. д., в общем случае - n-местные отношения. Рассмотренные выше предикаты-свойства считаются унарными предикатами. Наконец, оказывается удобным в понятие предиката-отношения как частный случай включить и высказывания в качестве «0 - местных предикатов».

Все математические дисциплины имеют дело с предикатами-отношениями, причем самыми распространенными являются бинарные отношения. Они описываются, различными словами: «равны», «не равны», «больше», «меньше», «делить», «перпендикулярны», «параллельны» и т. д.

По аналогии с предикатом-свойством двухместным предикатом считается опять функция, на этот раз от двух аргументов, определенных на некотором универсальном множестве, принимающая значение и (истинно) и л (ложно): те пары элементов, для которых функция принимает значение и, находятся в рассматриваемом отношении, остальные пары в этом отношении не находятся.

Рассмотрим пример бинарного отношения, определенного на множестве натуральных чисел, а именно отношение, описываемое словом «больше». Если рассматривать это отношение как функцию от двух переменных X и Y (на множестве натуральных чисел), принимающую значения и или л в зависимости от того, будет ли соответствующее отношение выполняться или нет, то эта функция определяет предикат, который обозначим через > (X, Y). Тогда имеем, например, > (3, 2) = и, > (1, 3) = л, > (7, 5) = и и т. д. Более полно и обозримо двухместный предикаты >(Х, Y).

Конечно, совсем нетрудно указать в элементарной математике примеры трехместных предикатов и предикатов от еще большего числа аргументов. Так, трехместным предикатом является в геометрии отношение, описываемое словом «между»: «Точка Y лежит между точками X и Z». В арифметике хорошо известны понятия наибольшего общего делителя и наименьшего общего кратного двух целых чисел: фраза «Число d является наибольшим общим делителем чисел а и b» описывает трехместный предикат. Трехместные предикаты на множестве действительных чисел задают действия сложения, вычитания, умножения и деления: X + Y = Z, X - У = Z, X * Y = Z, X : Y = Z. Примером четырехместного предиката может служить отношение между членами пропорции X : Y = Z : W

Ознакомившись с понятием предиката, мы переходим теперь к рассмотрению операций, позволяющих из некоторых исходных предикатов строить новые. Начнем изучение с простейшего случая одноместных предикатов. Пусть Р (X) и Q (X) - два одноместных предиката, определенных на некотором множестве М. С помощью операций алгебры высказываний мы можем строить новые предикаты на множестве М. Конъюнкция Р (X)UQ (X) - это предикат R1(X) = Р(X)UQ(X), который истинен для тех объектов а из М, для которых оба предиката Р(X) и Q(X) истинны. Аналогично определяется дизъюнкция Р(X)UQ(X):R2(X) = Р(X)UQ(X) - это предикат на М, который истинен в точности для тех аМ, для которых Размещено на http://www.allbest.ru/

истинен по меньшей мере один из предикатов Р (X) и Q (X). Так же определяется отрицание uР (X): R3(X) = uР(X) - предикат на М, истинный для тех и только тех а I М, для которых Р (X) ложен.

4.2.2 Кванторы

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

Понятие, обозначаемое словом «все», лежит в основе квантора всеобщности (или квантора общности). Если через Гр (X) обозначен предикат «X есть грек», определенный на множестве М всех людей, то из этого предиката с помощью слова «все» мы можем построить высказывание «Все люди - греки» (конечно, ложное высказывание). Это пример применения квантора всеобщности.

Вообще же квантор всеобщности определяется так. Пусть Р (X) - какой-нибудь предикат. Тогда квантор всеобщности - это операция, которая сопоставляет Р (X) высказывание

«Все X обладают свойством Р (X)». (*)

Для этой операции («все») употребляется знак Размещено на http://www.allbest.ru/

(перевернутая латинская буква А, напоминающая о немецком слове «alle» или английском «all» - все). Высказывание (*) записывается так: (X)P(X) (читается: «для всех X Р от X»). В соответствии со смыслом слова «все» Размещено на http://www.allbest.ru/

(X)Р(X) - ложное высказывание, кроме того единственного случая, когда Р (X) тождественно-истинный предикат.

Размещено на http://www.allbest.ru/

Наряду с квантором всеобщности в логике предикатов рассматривается другой квантор - «двойственный» ему квантор существования, обозначаемый знаком Размещено на http://www.allbest.ru/

(это перевернутая латинская буква E, напоминающая немецкое слово «existieren» или английское «exist» -- существовать):

(Х)Р(Х)

(читается: «существует такое X, что Р от X») - высказывание, которое истинно тогда и только тогда, когда Р истинно по меньшей мере для одного объекта а из области определения М. Тем самым (X)Р(X) - истинное высказывание для всех предикРазмещено на http://www.allbest.ru/

атов Р (X), кроме одного - тождественно-ложного.

Между кванторами Размещено на http://www.allbest.ru/

и Размещено на http://www.allbest.ru/

имеют место отношения равносильности, позволяющие сводить любой из этих кванторов к другому: u (X) P(X) UРазмещено на http://www.allbest.ru/

(X) u P(X) («Размещено на http://www.allbest.ru/

Неверно, что все X обладают свойством Р (X)» равносильно тому, что «Существует такой объект X, для которого истинно не Р (X)»). Отсюда имеем: (X) U uРазмещено на http://www.allbest.ru/

(X)u P(X). Размещено на http://www.allbest.ru/

Аналогично, имеет место двойственный закон: u (X) P(X) U Размещено на http://www.allbest.ru/

(X)u P(X). («Размещено на http://www.allbest.ru/

Неверно, что существует X, обладающее свойством Р (X)» равносильно «Все X обладают свойством не Р (X)»).

Отсюда (X)Р(X)Размещено на http://www.allbest.ru/

Uu(X)uP(X). Размещено на http://www.allbest.ru/

Эти равносильности называют правилами де Моргана для кванторов.

С помощью квантора существования легко выражается суждение типа «Некоторые Р суть Q» (например, «Некоторые англичане курят», «Некоторые нечетные числа - простые» и т. п.), т. е. что по крайней мере один объект а, обладающий свойством Р, обладает также свойством Q. Этот факт записывается формулой (X)(Р(X)Размещено на http://www.allbest.ru/

UQ(X)) («Существует такой X, что Р от X и Q от X»).

Аналогично с помощью кванторов записывается ряд других отношений между одноместными предикатами.

Гораздо более богатые возможности открывает применение кванторов к многоместным предикатам. Остановимся вкратце на этом вопросе.

Пусть А (X, Y) - некоторый двухместный предикат, определенный на некотором множестве М. Квантор всеобщности и квантор существования можно применять к нему как для переменной X, так и для переменной Y: (X)А(X, У); Размещено на http://www.allbest.ru/

(Y)А(X, Y); Размещено на http://www.allbest.ru/

(X)А(Х,Y); Размещено на http://www.allbest.ru/

(Y)A(X,Y). Переменная, к которой применен квантор, называется связанной, другая переменнРазмещено на http://www.allbest.ru/

ая - свободной. Все четыре приведенных выражения являются записями одноместных предикатов от соответствующей свободной переменной. (X)А(X,Y) (читается: «для всех X, A от X и Y») - одноместный предикат от переменной Y: Размещено на http://www.allbest.ru/

(X)А (X,Y)=F(У), Он истинен в точносРазмещено на http://www.allbest.ru/

ти для тех bIМ, для которых одноместный предикат А (X, b) истинен для всех X. Если представить предикат А (X, Y) его таблицей, то предикат F (Y) = (X) (X, Y) истинен для тех b, для которых столбец с входом b содержит исключительно букву и.

Размещено на http://www.allbest.ru/

Применение квантора к одной из переменных двухместного предиката превращает его в одноместный. В случае трехместных предикатов применение квантора приводит к двухместному предикату. Аналогично и для предикатов с большим числом мест применение квантора превращает n-местный предикат в (n - 1)-местный.

К свободной переменной X одноместного предиката (У)А(X, Y) в свою очередь можно применять квантор всеобщности или квантор существования. Получаются выражения

Размещено на http://www.allbest.ru/

(X)( (У)А(X,У)); (X)( (Y)А(X,У)), которые, опуская скобки, принято записывать несколько проще:

(X) (У)А(X,У); (X) (Y)А(X,У),

Это - высказывания. Первое истинно, если все строки, а тем самым и вся таблица предикатов, содержат только букву и, второе истинно, если соответствующая матрица содержит по меньшей мере одну тождественно-истинную строку. Три другие предиката (X)А (X,У), Размещено на http://www.allbest.ru/

(У)А(X, У) и Размещено на http://www.allbest.ru/

(X)А (X,У) также допускают квантификацию, так что в общей сложности мы получаем из одного предиката восемь формально различных высказываний: Размещено на http://www.allbest.ru/

(X) (У)А (X, У); (X) (У)А (X,У); (X) (У)А (X, У); (X) (У)А (X, У); (У)Размещено на http://www.allbest.ru/

(X) А (X, У); (У) (X)А(X, У); (У) (X)А (X, У); (Y) (X) А (X, У).

Нетрудно убедиться в том, что четыре высказывания, содержащие одинаковые кванторы, попарно эквивалентны:

(X)(У)А(X,У) Размещено на http://www.allbest.ru/

U(У)Размещено на http://www.allbest.ru/

(X)А (X, У);

Размещено на http://www.allbest.ru/

(X)(У)Размещено на http://www.allbest.ru/

А (X, У) U (Y)Размещено на http://www.allbest.ru/

(X)А (X, У).

Размещено на http://www.allbest.ru/

(X)(У)А(X,У) Размещено на http://www.allbest.ru/

так же как и (У)Размещено на http://www.allbest.ru/

(X)А(X, У), истинно тогда и только тогда, когда А (X, У) - тождественно-истинный предикат, Размещено на http://www.allbest.ru/

(X)Размещено на http://www.allbest.ru/

(У)А (X, У) и Размещено на http://www.allbest.ru/

(Y)Размещено на http://www.allbest.ru/

(X)А(X,У) оба истинны во всех случаях, кроме одного, когда А(X,У) - тождественнРазмещено на http://www.allbest.ru/

о-ложный предикат. Все остальные высказывания существенно различны. Особенно следует помнить, что порядок следования разноименных кванторов очень важен.

Я считаю, что к окончанию школы ученики должны овладеть кванторами, но введение их должно быть постепенным и начинаться в простых ситуациях. Учащиеся должны хорошо понимать, что от перестановки кванторов может меняться смысл утверждения.

Например, Пусть I=(а,b) - некоторый интервал. Тогда «Для всякого хII существует такой у, что у = f (х)» ((x)Размещено на http://www.allbest.ru/

(у) (у = fРазмещено на http://www.allbest.ru/

(х))), означает, что функция f(х) всюду определена на I. Напротив, «Существует такое у, что для всякого х у=f (х)» ((у)Размещено на http://www.allbest.ru/

(х)(у=f(х))) означает, что функция f(x) принимает для всех х некоторое фиксированное значение у, т. е. постоянна.

Размещено на http://www.allbest.ru/

Приведем еще один пример. Корректное определение периодичности всюду определенной функции f(х) выглядит с использованием кванторов так: (c)Размещено на http://www.allbest.ru/

(x) (c?0 U Uf(x+c) = f(x)), Размещено на http://www.allbest.ru/

между тем если переставить кванторы и сформулировать утверждение «Для каждого х существует такое с, что с?0 и что f(х + с) =f(x)»: (c)Размещено на http://www.allbest.ru/

(x) (c?0 U f(x+c) = f(x)), Размещено на http://www.allbest.ru/

то это означает лишь, что функция принимает каждое значение больше чем один раз, т. е. нечто совсем иное.

В математическом анализе часто приходится сталкиваться с кванторами.

Определение предела последовательности из учебника «Алгебра и начала анализа» для 10-11 классов сформулировано так «Число А является пределом последовательности аn, если для любого >0 существует номер N, такой, что при всех n>N верно неравенствоРазмещено на http://www.allbest.ru/

». В кванторном обозначении это определение записывается так:

(>0) (NIN) (n IN)((n>N) ?

Переставлять кванторы нельзя: именно тот факт, что N под квантором существования Размещено на http://www.allbest.ru/

следует за выражением (> 0), указывает на зависимость N от выбранного .

Размещено на http://www.allbest.ru/

Как выразить утверждение, что последовательность (хn) сходится? Надо указать на то, что предел A существует. С помощью кванторов это утверждение формулируется так:

(A) (> 0) (NI N) (nIN)((n > N) ? ()).

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

Uu((A) Размещено на http://www.allbest.ru/

(Размещено на http://www.allbest.ru/

> 0) (NI N) Размещено на http://www.allbest.ru/

(nIN)((n > N) ? (Размещено на http://www.allbest.ru/

)) U (A)(Размещено на http://www.allbest.ru/

> 0) (NI N) (nIN)((n > N) UРазмещено на http://www.allbest.ru/

).

Задания для учащихся.

Установите, какие из следующих высказываний истинны.

x (x + 1 = x); x (x2 + x + 1>0);Размещено на http://www.allbest.ru/

x (x2 - 5x + 6>0);Размещено на http://www.allbest.ru/

x (x2 -6x+8?0 U x2-4x+3>0);Размещено на http://www.allbest.ru/

x (x2 - 5x + 6 ? 0 U x2 + 5x + 6 < 0)