Математика для инженеров(теория)I том

тех и только тех значений x X , при которых оба исходных предиката являются истинными высказываниями.

Множество истинности предиката p(x) q(x) представляет собой пересечение множеств истинности для предикатов p(x) и q(x) (т.е. p+ Ç q+ ).

Понятие конъюнкции предикатов тесно связано с понятием системы уравнений. В самом деле, рассмотрим систему двух уравнений с двумя

Задача решения такой системы есть, по существу, задача нахожде- ния множества истинности для предиката, являющегося конъюнкцией двух предикатов: « F1(x, y) = 0 » и « F2 (x, y) = 0 ». В этом смысле часто

говорят, что система (1) есть конъюнкция уравнений F1(x, y) = 0 и

ределения X = X1 Ç X2 , который превращается в истинное высказывание

для тех и только тех значений x X , при которых хотя бы одно из высказываний p(x) и q(x) истинно.

Множество истинности предиката p(x) q(x) есть объединение

множеств истинности для предикатов p(x) и q(x) (т.е. p+ È q+ ).

Так, например, дизъюнкцией предикатов « x > 5 » и « x < −5 » (с областью определения ), является предикат « (x > 5) (x < −5) »

или, что равносильно, «| x |> 5 ».

IV. Пусть p(x) и q(x) – два предиката, определенные соответ- ственно на множествах X1 и X2 . Импликацией p(x) и q(x) называется предикат, обозначаемый p(x) => q(x) (читается «если p(x) то q(x) »), с областью определения X = X1 Ç X2 , который превращается в ложное

высказывание для тех и только тех значений x X , при которых пер- вый предикат является истинным высказыванием, а второй – ложным.

Множество истинности предиката p(x) => q(x) есть дополнение

до X множества p+ Ç q− (где q− – дополнение к q+ ), т.е. множество p− È q+ .

13

Упражнение 2. Убедиться в справедливости следующего пред- ложения: если предикат q(x) есть следствие предиката p(x) , то пре-

дикат p(x) => q(x) тождественно истинен; обратно, если предикат

только тех значений x Î X1 Ç X2 , при которых оба данных предиката

превращаются одновременно либо в истинные, либо в ложные выска- зывания.

Множество истинности предиката p(x) <=> q(x) является объе- динением двух множеств p+ Ç q+ и p− Ç q− .

50. Кванторные операции над предикатами. Для предикатов можно ввести операции, не имеющие аналогов среди операций над высказываниями. Это – так называемые кванторные операции.

Каждая из них применяется к одноместному предикату и превращает его в высказывание.

Операцией квантор общности будем называть правило, которое каждому одноместному предикату p(x) определенному на множестве X ,

сопоставляет высказывание, обозначаемое (x) ( p(x)) (читается: «для всякого x X справедливо p(x) ») которое истинно тогда и только тогда, когда предикат p(x) тождественно истинен.

Операцией квантор существования называется правило, которое каждому одноместному предикату p(x) , определенному на множестве Х,

сопоставляет высказывание, обозначаемое (x)( p(x)) (читается: «Суще- ствует значение x X , такое, что верно p(x) »), которое ложно тогда и только тогда, когда предикат p(x) тождественно ложен.

Упражнение 3. Проверить следующие равносильности: ("x)( p(x)) @ ($x)( p(x)); ($x)( p(x)) @ ("x)( p(x)) ;

("x)( p(x)) @ ($x)( p(x)); ($x)( p(x)) @ ("x)( p(x)) ; (x)( p(x) q(x)) (x)( p(x)) (y)(q(y)) ; (x)( p(x) q(x)) (x)( p(x)) (y)(q(y)) .

14

§ 3. Метод математической индукции

10. Полная и неполная индукция. В основе всякого математи-

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

Полная индукция имеет в математике лишь ограниченное при- менение. Неполная индукция часто приводит к ошибочным результатам.

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

20. Метод математической индукции. Во многих разделах арифметики, алгебры, геометрии, анализа приходится доказывать ис- тинность предложений A(n) , зависящих от натуральной переменной,

для всех значений этой переменной. Доказательство истинности пред- ложения A(n) для всех значений переменной часто удается провести

методом математической индукции, который основан на следующем принципе: если предложение A(n), зависящее от натурального числа n, истинно для n =1 , и из того, что оно истинно для n = k (где k – любое натуральное число), следует, что оно истинно и для следующего числа n = k +1 (кратко это записывают так: A(k) => A(k +1) ), то предложение

A(n) истинно для любого натурального числа n.

Под методом математической индукции понимают следующий способ доказательства. Если требуется доказать истинность предло- жения A(n) для всех натуральных n, то, во-первых, следует проверить истинность высказывания A(1) и, во-вторых, предположив истинность высказывания A(k) , попытаться доказать, что высказывание A(k +1)

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

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

15

Пример 1. Доказать формулу

13 + 23 + 33 + ...+ n3 = æ n(n +1) ö2 , nÎ .

ç ÷ è 2 ø

Решение. 1. При n =1 обе части равенства обращаются в еди- ницу и, следовательно, первое условие принципа математической ин-

Таким образом, из того, что данная формула верна при n = k , получили, что она верна и при n = k +1. Значит, это утверждение справед- ливо при любом натуральном значении n . Итак, второе условие принципа математической индукции тоже выполнено. Формула доказана. □

Иногда необходимо доказать справедливость некоторого утверждения не для всех натуральных чисел, а лишь для n ³ p , где p

фиксированное натуральное число. Тогда принцип математической индукции формулируется следующим образом: если предложение A(n) истинно при n = p и если A(k) => A(k +1) для любого k ³ p , то

предложение A(n) истинно для любого n ³ p .

Пример 2. Доказать, что если n ³ 2 и x > 0 , то справедливо

неравенство Бернулли

2. Докажем, что A(k) => A(k +1) , если k ³ 2 . Предположим, что A(k) истинно, т.е. что справедливо неравенство

Докажем, что тогда и A(k +1) истинно, т.е. что справедливо не- равенство (1+ x)k+1 >1+ (k +1)x .

16

В самом деле, умножив обе части неравенства (2) на положи- тельное число 1+ x , получим

A(k) => A(k +1) . На основании принципа математической индукции можно утверждать, что неравенство Бернулли справедливо для любого n ³ 2 и x > 0 . □

§ 4. Бином Ньютона

10 Комбинаторика. Простейшие комбинаторные задачи.

Комбинаторная математика, комбинаторика – раздел матема-

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

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

Правило суммы. Если элемент a может быть выбран n спосо- бами, а элемент b – m способами, то один из этих элементов (или а, или b ) можно выбрать n + m способами.

Правило произведения. Если элемент a может быть выбран n способами, а элемент b – m способами, то пару (a, b) можно выбрать

n × m способами.

Например, сколькими способами можно расположить в ряд три различных предмета? Здесь ответ ясен – шестью способами, так как легко перебрать возможные расположения: 123, 132, 213, 231, 312, 321 (роль «различных предметов» играют цифры 1, 2 и 3). Но уже значи- тельную трудность представляет собой решение такой довольно ши- роко известной комбинаторной задачи: сколько существует «счастли- вых» номеров среди 1 000 000 шестизначных номеров трамвайных билетов (номер считается «счастливым», если сумма первых трех цифр равна сумме последних трех цифр)? Здесь ответ 55 252 совсем не очевиден. Приведем решение нескольких простейших комбинаторных задач.

17

Задача 1. О числе выборок из нескольких множеств. Даны два множества предметов, в первом m элементов, второе множество содержит n элементов. Сколько можно составить пар элементов, выбирая по одному из каждого множества?

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

Задача естественным образом обобщается на выборки из нескольких множеств.

Упражнение 1. Пусть даны k множеств, содержащие по m1,m2 ,...,mk элементов соответственно. Показать, что число выборок по одному элементу из всех k множеств равно m1 × m2 ×...× mk .

Задача 2. Перестановки. Сколькими способами можно распо- ложить в ряд n элементов?

Упражнение 2. Методом математической индукции доказать, что число перестановок из n элементов Pn вычисляется по формуле

Pn =1× 2 ×3×...× n = n!.

Замечание 1. Произведение всех натуральных чисел от 1 до n обозначают n ! (читается «эн факториал»), это значит

n! = 1× 2×...×(n -1) × n .

Задача 3. Размещения. Сколькими способами можно выбрать и расположить в ряд m элементов из данного множества, содержащего n элементов?

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

а их число принято обозначать символом Anm (читается «A из n по т»).

Например, из четырех элементов 1, 2, 3, 4 ( n = 4 ) можно составить

12 размещений по 2 элемента (m=2): (1, 2), (2, 1), (1, 3), (3, 1), (1, 4), (4, 1), (2, 3), (3, 2), (2 , 4), (4, 2), (3, 4), (4, 3). Таким образом A42 =12 .

Вычислим теперь Anm . Возьмем все перестановки из n элементов

и «вырежем» в каждой из них первые m элементов, отбросив остальные n - m элементов. Останутся размещения из n элементов по m , но каждое размещение встретится столько раз, сколько перестановок можно составить из отброшенных n - m элементов, т.е. Pn−m раз.

Таким образом, число размещений из n элементов по m в Pn−m раз меньше числа перестановок из n элементов, т.е.

18

Задача 4. Сочетания. Сколькими способами из множества, со- держащего n элементов, можно выбрать подмножество, составленное из m элементов?

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

Так, например, из четырех элементов 1, 2, 3, 4 можно составить шесть сочетаний по два {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4} (фигурные скобки подчеркивают отличие сочетаний от размещений; размещения (1,2) и (2,1) считаются различными, хотя и составлены из одних и тех же элементов, а {1, 2} и {2, 1} считаются одним и тем же сочетанием).

Число сочетаний из n элементов по m обозначается символом Cnm , например C42 = 6 . Очевидно, что сочетания тесно связаны с раз-

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

Решение. Всего в рассматриваемом ряду 10 мест. Зная номера мест, в которые устанавливаются 5 черных шашек, мы знаем и все расположения. Следовательно, искомое число равно

C5 = 10× 9× 8× 7× 6 = 252 . □ 10 1× 2× 3× 4× 5

19

20. Бином Ньютона. Из школьного курса математики известны формулы:

(a + b)2 = a2 + 2ab + b2 ,

(a + b)3 = a3 + 3a2b + 3ab2 + b3 ,

называемые формулами сокращенного умножения. Установим анало-

гичную формулу общего вида, которую называют формулой бинома Ньютона.

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

Пусть a1,a2 ,...,an – заданные числа. Их сумма a1 + a2 + ... + an

n

обозначается å am , и читается «сумма по m от 1 до n ». Знак ∑ – это

m=1

большая греческая буква «сигма», а буква m называется индексом суммирования.

Упражнение 4. Показать, что действия со знаком ∑ подчиняются следующим правилам:

nn

1)å cam =cå am , c = const,

Утверждение 1. Для всех действительных чисел a и b и для каждого натурального значения n справедливо равенство

m=0

где коэффициенты Cnm называются биномиальными коэффициентами

и вычисляются по формуле (1).

Утверждение 1 докажем методом математической индукции. Если n =1 , то формула (4) справедлива, ибо

m=0

20

В первой сумме из правой части полученного равенства выде- лим отдельно первое слагаемое, а во второй – последнее. Уменьшим также индекс суммирования в другой сумме на единицу. Получим

Таким образом,

k−1

(a + b)k = akb0 + å(Ckm−1 + Ckm−−11)ak−mbm + a0bk .

m=1

Пользуясь равенством (2), а также тем, что Ck0 =1, Ckk =1 , получим

Значит формула (4) имеет место для всех k . □

На основании формул (2), биномиальные коэффициенты для разных значений n можно выписать в виде таблицы, которую назы-

вают треугольником Паскаля.

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

Cn0 ,C1n ,...,Cnm ,...,Cnn бинома (a + b)n .

21

n

Если в формуле (4) взять a = b =1, то получается å Cnm = 2n .

m=0

Поскольку для множества, которое содержит n элементов, Cnm есть

n

количество его подмножеств по m элементов, то å Cnm определяет

m=0

количество всех подмножеств множества из n элементов и оно равно 2n .

§ 5. Множество действительных чисел. Модуль

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

Если к множеству всех натуральных чисел {1;2;3;...} , присоеди- нить число 0, то получим множество чисел Z0 = {0;1;2;3;...} = U{0}.

Натуральные числа, нуль, а также числа, противоположные нату- ральным, составляют множество целых чисел, т.е. = U{0}U − ,

где − – множество чисел, противоположных натуральным.

Целые и дробные числа составляют множество рациональных чисел. Любое рациональное число можно записать в виде дроби mn ,

где m и n (т.е. числитель есть целое число, а знаменатель – натуральное). Рациональное число может быть записано разными дробями. Среди дробей, изображающих данное число, всегда имеется единственная несократимая дробь; для целых чисел – это дробь, зна- менатель которой равен 1.

Пусть дано рациональное число mn . Деля числитель на знамена-

тель «уголком», получаем конечную или бесконечную десятичную

называется бесконечной периодической дробью, если в ней после запятой

22