Дискретная математика

Глава 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. Ориентированные графы

Ориентированные графы

Пути в орграфах

Кратчайший путь

Обозначения