Основы дискретной математики

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

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

Основы дискретной математики

Введение

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

1. Направления исследований в дискретной математике

1. Теория множеств.

2. Комбинаторика.

3. Математическая логика

(алгебра логики, логика высказываний и логика предикатов).

4. Теория графов.

5. Алгоритмы.

6. Абстрактные автоматы.

7. Теория кодирования.

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

Примеры графов:

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

1. Снимите трубку телефонного аппарата, наберите 8.

2. Услышав длинный гудок, наберите код города, затем номер телефона вызываемого абонента.

3. Если раздаются короткие гудки, то повесьте трубку и повторите все заново.

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

Приведенная формулировка скорее поясняет, что такое алгоритм, чем дает точное определение, поскольку она использует весьма неоднозначные термины. Например, что значит «точное» описание? Для кого оно должно быть «понятным»?

Пример математического алгоритма. Алгоритм Евклида нахождения наибольшего общего делителя (НОД) двух натуральных чисел.

1. задать два числа;

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

3. определить большее из чисел;

4. заменить большее из чисел разностью большего и меньшего из чисел;

5. повторить алгоритм с шага 2.

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

Абстрактные автоматы. Существуют устройства, которые мгновенно преобразовывают поступающие по входным каналам сигналы из некоторого множества. При этом выходные сигналы формируются из заранее определенного множества в зависимости от входных сигналов в текущий момент времени и от состояний, в которые перешло это устройство в предыдущий момент времени. Такие устройства называют абстрактными автоматами. Они являются математическими моделями таких автоматов, как, например, турникеты в метро, игровые автоматы, торговые автоматы (продающие кофе, билеты на транспорт и т.п.).

Коды. Пусть требуется перевести сообщение из букв алфавита A={a, b, c, d} на язык, понятный компьютеру. Для этого буквам алфавита A поставим в соответствие последовательности элементов из набора B={0, 1}. Набор V={00, 01, 10, 11} называется кодом, а соответствие f между А и В (a00, b01, c10, d11) - кодированием.

2. Обозначения

Знак обозначает «и», - «или».

- следование, - знак равносильности.

- любой, - существует, найдется; - «не А» (условие, противоположное А).

3. Виды теорем

1. AB - «из А следует В»; «если справедливо А, то верно В», «для выполнения условия А необходимо выполнение условия В», «для выполнения условия В достаточно выполнение условия А».

Замечание. Иногда требуется доказать утверждение, которое, на первый взгляд, имеют структуру, отличную от AB. В частности, это касается неравенств. В действительности, структура таких утверждений по сути совпадает с видом AB, отличия имеются лишь по форме изложения утверждения. Например, неравенство х<у можно переформулировать следующим образом: «Если первое число равно х, а второе равно у (условие А), то первое меньше второго (условие В)».

2. AB - «условие А выполняется тогда и только тогда, когда справедливо условие В»;

«для выполнения условия А необходимо и достаточно выполнение условия В»;

«условие А выполняется в том и только том случае, когда справедливо условие В».

Как правило, теоремы вида 2 называются «необходимым и достаточным условием» или «критерием».

4. Способы доказательств теорем

1. Цепочка заключений: AС₁С₂…С_nB.

Пример 1. Доказать, что любое число, делящееся на 6, является четным.

Доказательство: Если число n делится на 6 (А), то его можно представить в виде n=6k, где k - натуральное (С₁). Тогда n=23k (С₂). Следовательно, n - четное (В).

Пример 2. Доказать неравенство .

Доказательство: Если первое число равно , а второе равно (А), то разность их квадратов равна (С₁). По свойству модуля такая разность неположительная для всех действительных а и b, т.е. для всех действительных а и b (С₂). Значит, (С₃). Поскольку числа и неотрицательны, то (В).

2. От противного: AB .

Пример 3. Докажите: если число четное (А), то n - тоже четное (В).

Доказательство: Допустим, что n - нечетное: , где k - натуральное (). Тогда - нечетное число. Получили противоречие с условием А. Значит, наше предположение о том, что n нечетное, неверно. Следовательно, n - тоже четное.

3. Метод перебора (полная индукция)

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

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

4=2+2, 6=3+3, 8=3+5, 10=5+5, 12=5+7, 14=7+7.

Поскольку рассмотрены все возможные случаи, утверждение доказано.

4. Метод математической индукции (неполная индукция)

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

Пример 5. Угадать формулу для суммы кубов первых n натуральных чисел.

1³=1

1³+2³=9=3²=(1+2)²

1³+2³+3³=36=6²=(1+2+3)²

1³+2³+3³+4³=100=10²=(1+2+3+4)²

Возникает гипотеза: 1³+2³+3³+ … +n³=(1+2+ … +n)²=(n (n+1)/2)² (1)

Пока неизвестно, верна ли она.

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

Определение 1. Индукцией называют метод рассуждений, ведущий от частных примеров к общему выводу.

Отличие примеров 4 и 5 - в количестве рассмотренных случаев. Если в примере 4 мы перебрали все возможности и, таким образом, доказали справедливость утверждения, то для доказательства методом перебора формулы для суммы кубов первых n натуральных чисел нужно было рассматривать бесконечное множество сумм из n слагаемых, что сделать принципиально невозможно.

Определение 2. Если вывод делается после рассмотрения всех частных случаев, то такой метод рассуждений называется полной индукцией (метод перебора).

Замечание. Если рассматриваются не все случаи, то это неполная индукция.

Забегая вперёд, скажем, что формула (1) верна. Однако далеко не каждая гипотеза, полученная неполной индукцией, является истинной.

Пример 6. Будем искать значения многочлена P(x)=x²+x+41 при целых х, отличных от нуля.

P(1)=43, P(3)=53, P(5)=71, P(-2)=43,

P(2)=47, P(4)=61, P(-1)=41, P(-3)=47.

Возникает гипотеза, что значение многочлена P(x) является простым числом при всех целых х, отличных от нуля. Однако эта гипотеза ошибочна, поскольку P(41)=41²+41+41=4143 - составное число.

Рассмотрим способ доказательства математических утверждений, в формулировку которых входит произвольное натуральное число n. Этот способ основан на принципе математической индукции:

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

1. Проверяют истинность утверждения при n=1 - 1-ый шаг доказательства (1-ый индукционный шаг).

2. Допускают, что утверждение справедливо при n=k, где k - произвольное натуральное число, и доказывают, что тогда утверждение верно и при n=k+1 - 2-ой шаг доказательства (2-ой индукционный шаг).

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

В самом деле, если утверждение справедливо при n=1, то по доказанному в шаге 2 оно верно и при n=1+1=2. Далее, из того, что оно верно при n=2 вытекает его справедливость при n=2+1=3. Затем от n=3 переходят к n=4 и т.д. Ясно, что при этом рано или поздно мы доберемся до любого натурального числа n, а потому данное утверждение истинно для всех n.

Пример 7. Доказать, что для всех натуральных n верно равенство:

1³+2³+3³+ … +n³=n²(n+1)²/4. (1)

Доказательство: 1) Проверим, выполняется ли равенство (1) при n=1. В этом случае левая часть этой формулы принимает вид 1³=1, а ее правая часть превращается в и тоже равна 1. Значит, при n=1 формула (1) верна.

2) Обозначим левую часть равенства (1) через S_n. Допустим, что равенство (1) является истинным при каком-то произвольном натуральном n=k, т.е. что верно равенство

.

Докажем, что тогда формула (1) верна и при n=k+1, т.е. что справедливо равенство

.

Для этого заметим, что левую часть доказываемого равенства можно рассматривать как сумму двух слагаемых: S_k1³+2³+3³+ … +k³ и (k+1)³. Но первое из этих слагаемых по допущению равно . Следовательно,

S_k+1=S_k+(k+1)³=+(k+1)³==.

Таким образом, доказали, что формула (1) верна при n=1 и из истинности ее при каком-то произвольном натуральном n=k следует ее справедливость и при следующем n=k+1. В силу принципа математической индукции это означает справедливость равенства (1) для всех натуральных n.

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

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

5. Комбинированное доказательство: в одном доказательстве применяется несколько методов 1-4. Например, в процессе доказательства методом от противного может использоваться метод перебора.

Доказательство теорем вида 2 состоит из двух частей. Сначала, как правило, доказывается необходимость (AB), затем достаточность (AB). Каждое из этих двух доказательств проводится одним из 5 вышеперечисленных способов.

Размещено на Allbest.ru