# Дискретная математика ## Глава 2. Логика и доказательство ### Высказывания и логика **Высказывание** называется утверждение, которое имеет значение истинности, т.е. может быть истинным(обозначается буквой И) или ложным(обозначается буквой Л) - * земля плоская * Сара - доктор * 29 - простое число Использую логические операции **не, или, и** можно построить составные высказывания - * (не P) - земля не плоская * (P или Q) - земля плоская или Сара - доктор * (P и Q) - земля плоская и Сара доктор **Логически эквивалентные высказывания** - высказывание которое построено из одних и тех же простых утверждений, но разными путями, могут принимать одинаковые значения истинности на любом возможном наборе значений истинности своих составных частей. $$R=(не(P \bold{и}(\bold{не} Q)))$$ $$((\bold{не} P)\bold{или} Q)$$ | P | Q | не P | не Q | P и (не Q) | R | S | | - | - | ---- | ---- | ---------- | - | - | | И | И | Л | Л | Л | И | И | | И | Л | Л | И | И | Л | Л | | Л | И | И | Л | Л | И | И | | Л | Л | И | И | Л | И | И | Две последние колонки идентичны. Значит высказывание R логически эквивалентно высказыванию S. ### Предметы и кванторы **Предикатом** называется утверждение, содержающее переменные, принимающее значение истины или лжи в зависимости от значений переменных. $$x=x^2$$ истинно при $$x=0,1$$ и ложно при других значениях **Задача**. x и y - вещественые числа, P(x,y) - обозначает предикат $$x+y=0$$. Выразите каждое из высказываний словами и определите их истинность * $$\forall{x}\exists{y}:P(x,y)$$ Высказываение говорит о том, что для любого x существует y, что $$x+y=0$$. Верно поскольку какое бы число x мы не взяли, y будет с противоположным знаком. * $$\exists{y}:\forall{x} P(x,y)$$ Высказывание говорит о том, что существует y, что для любого x выполняется равенство $$x+y=0$$. Неверно. ### Методы доказательств 1. Прямое рассуждение. Предполагаем, что высказывание P истинно и показываем справедливость Q. Такой способ доказательства исключает ситуацию, когда P истинно, а Q - ложно, поскольку именно в этом случае импликация($$P\implies{Q}$$) принимает ложно значение. 2. Обратное рассуждение. Предполагаем, что высказывание Q ложно и показываем ошибочность P. То есть, фактически прямым способом проверяем истинность импликации ((не Q)) $$\implies$$ (не P)), что логически эквивалентно истинности исходного утверждения($$P\implies{Q}$$). 3. Метод от противного. Предположив, что высказывание P истинно, а Q ложно, используя аргументированное рассуждение, получаем противоречие. Этот способ основан на том, что импликация($$P\implies{Q}$$) принимает ложно значение только тогда, когда P истинно, а Q ложно. **Задача 1.** Покажите прямым способом рассуждение, что произведение $$x\*y$$ двух нечетных целых чисел всегда нечетно. Любое нечетное число можно записать в виде $$x=2m+1$$, где m - целое число. Следовательное - $$x\*y=(2m+1)(2n+1)=4mn+2m+2n+1=2(2mn+m+n)+1$$ Произведение является также нечетным числом. **Задача 2** Пусть n - натуральное число. Покажите, используя обратный способ доказаельсва, что если $$n^2$$ нечетно, то и n нечетно. Нам нужно показать, что четность числа n влечет четное его квадрата $$n^2$$. Так как n четно, то $$n=2m$$. Следовательно $$n^2=4m^2=2(2m^2)$$ - четное число. **Задача 3** Методом от противного покажите, что решение уравнения $$x^2=2$$ является иррациональным число, т.е. не может быть записано в виде дроби с целыми числителем и знаминателем. Допустим, что решение x уравнения $$x^2=2$$ рационально, т.е. записывается в виде дроби $$x=\frac{m}{n}$$ с целыми m и n, $$n\cancel{=}0$$. Предположив это, нам необходимо получить противоречие либо с предложением, либо с каким-то ранее доказанным фактом. Дробь можно записать по разному $$x=\frac{m}{n}=\frac{2m}{2n}=\frac{3m}{3n}$$. Предположим, что у нашей дроби нет общих делителей, наша дробь не сократима - $$x=\frac{m}{n}$$ $$x^2=2\iff (\frac{m}{n})^2=2\iff m^2=2n^2$$ m^2 - четное $$\implies$$ m - четно и может быть представленно в видео $$m=2p$$ $$\implies$$ $$4p^2=2n^2\iff n^2=2p^2$$ Получается, что n - четно $$\implies$$ m и n обладают общим делителем 2. Ранее мы предполагали отсутствие общего делителя у числителя и знаминателя дроби $$\frac{m}{n}$$, то увидим явное противоречие. Вывод:решение уравнения не может быть рациональным числом, т.е. оно иррационално. ### Математическая индукция Проверка корректности алгоритма, содержащего циклы, нуждается в довольно мощном методе доказательства, который называется **математическая индукция**. Докажим корректность следующей рекурентного алгоритма, определяющего максимальный элемент из набора $$a\_1,a\_2,a\_3,\dots,a\_n$$ ``` begin i :=0; M :=0; while i < n do begin j := j + 1; M :=max(M, a); end end ``` | j | M | j<4? | | - | - | ---- | | 0 | 0 | yes | | 1 | 4 | yes | | 2 | 7 | yes | | 3 | 7 | yes | | 4 | 8 | no | **Принцип математической индукции.** Пусть P(n) - предикат, определенный для всех натуральных чисел n. Предположим, что: 1. P(1) истинно и 2. $$\forall k\geq 1$$ импликация $$(P(k)\implies P(k+1))$$ верна. Тогда P(n) истинно при любом натуральном значении n. **Задача** Докажие по индукции, что равенство выполнимо при всех натуральных n. $$1+2+\dots+n=\frac{n(n+1)}{2}$$ Пусть P(n) - предикат $$1+2+\dots+n=\frac{n(n+1)}{2}$$. При $$n=1$$ $$1=\frac{1(1+1)}{2}\implies 1=1\implies P(1)=true$$ Предположим теперь, что равенство $$1+2+\dots+k=\frac{k(k+1)}{2}$$ имеет место для какого-то натураьного числа k. Тогда: $$1+2+\dots+k+(k+1)=(1+2+\dots+k)+(k+1)=\frac{k(k+1)}{2}+(k+1)=\frac{1}{2}(k(k+1)+2(k+1))=\frac{1}{2}((k+2)(k+1))=\frac{(k+1)(k+2)}{2}$$ Таким образом, при любом натуральном k импликация $$P(k)\implies P(k+1)$$ справедлива. Значит, по принципу математической индукции предикат P(n) имеет истинное значение при всех натуральных n. **Задача** Методом мат. индукции докажите, что $$7^n-1$$ делится на 6 при любом натуральном показателе n. 1. a делится на b, если выполняет равенство $$a=mb$$. 2. Сумма делящихся на b чисел делится на b. Пусть P(n) обозначает предикат $$7^n-1$$ делится на 6, тогда P(1) истинно. Предположим, что $$7^k-1$$ делится на 6 при каком-то натуральном k. Тогда $$7^{k+1}-1=7(7^k)-1=7(7^k-1)+7-1=7(7^k-1)+6$$ Так как $$7^k-1$$ делится на 6, то сумма $$7(7^k-1)+6$$ делится на 6. Итак, $$7^{k+1}-1$$ делится на 6, так что при любом натуральном k импликация $$P(k)\implies P(k+1)$ истинна. **Задача** Последовательность целых чисел $$x\_1,x\_2,\dots,x\_n$$ определена рекуррентной формулой: $$x\_1=1$$ и $$x\_{k+1}=x\_k+8k$$ при $$k\ge 1$$ Доказать, что имеет место формула: $$x\_n=(2n-1)^2$$ для всех $$n\ge 1$$ Предикат $$x\_n=(2n-1)^2$$ обозначим через P(n). Если $$n=1$$, то $$(2n-1)^2=(2-1)^2=1$$\implies P(1)=true$$. Допустим, что $$x\_k=(2k-1)^2$$ для $$k\ge 1$$. Тогда $$x\_{k+1}=x\_k+8k=(2k-1)^2+8k=4k^2+4k+1=(2k+1)^2=(2(k+1)-1)^2\implies P(k)\implies P(k+1)$$ при всех $$k\ge 1$$ Следовательно, согласно индуктивному принципу, предикат P(n) превращается в истинное высказывание при любом натуральном значении переменной n. ## Глава 3. Теория множеств ### Множества и операции над ними **Множества** - это совокупность объектов, называемых элементами множества. * S = {Эссекс, Йоркшир, Девон} * A = {2, 3, 5, 7, 11} * B = {сыр, яйцо, молоко, сметана} 1. $$a\in{S}$$ объект a - элемент множества S(принадлежит множеству S). 2. $$a\cancel{\in} S$$ объект a не принадлежит множеству S 3. $$S=$${$$x:P(x)$$} множества состоит из элементов x, для которых предикат P(x) имеет истинное значение.($$S =$$ {x: x - нечетное натуральное число} либо $$S =$${$$2n-1$$: n - натуральное число} то есть $$S=$${$$1,3,5,7,\dots$$}) 4. $$\varnothing$$ - пустое множество 5. $$\mathbb{N} =$${$$1,2,3,\dots$$} - множество натуральных чисел 6. $$\mathbb{Z} =$${$$0,\pm{1},\pm{2},\pm{3},\dots$$} - множества целых чисел 7. $$\mathbb{Q} =$${$$\frac{p}{q}: p, q \in{\mathbb{Z}},q \not={0}$$} - множество рациональных чисел 8. $$\mathbb{R}=$${все десятичные дроби} - множество вещественных чисел ### Алгебра множеств ### Дальнейшие свойства множеств ## Глава 9. Булева алгебра ### Булева алгебра ### Карты Карно ### Функциональные схемы ## Глава 4. Отношения ### Бинарные отношения ### Свойства отношений ### Отношения эквивалентности и частичнго порядка ## Глава 5. Функции ### Обратные отношения и композиция отношений ### Функции ### Обратные функции и композиции функций ### Принцип Дрихле ## Глава 6. Комбинаторика ### Правила суммы и произведения ### Комбинаторные формулы ### Бином Ньютона ## Глава 7. Графы ### Графы и терминология ### Гамильтоновы графы ### Деревья ## Глава 8. Ориентированные графы ### Ориентированные графы ### Пути в орграфах ### Кратчайший путь ## Обозначения