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

Глава 2. Логика и доказательство

Высказывания и логика

Высказывание называется утверждение, которое имеет значение истинности, т.е. может быть истинным(обозначается буквой И) или ложным(обозначается буквой Л) -

земля плоская
Сара - доктор
29 - простое число

Использую логические операции не, или, и можно построить составные высказывания -

(не P) - земля не плоская
(P или Q) - земля плоская или Сара - доктор
(P и Q) - земля плоская и Сара доктор

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

$R=(не(P \bold{и}(\bold{не} Q)))$ $((\bold{не} P)\bold{или} Q)$

Две последние колонки идентичны. Значит высказывание 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$ . Неверно.

Методы доказательств

Прямое рассуждение. Предполагаем, что высказывание P истинно и показываем справедливость Q. Такой способ доказательства исключает ситуацию, когда P истинно, а Q - ложно, поскольку именно в этом случае импликация( $P\implies{Q}$ ) принимает ложно значение.
Обратное рассуждение. Предполагаем, что высказывание Q ложно и показываем ошибочность P. То есть, фактически прямым способом проверяем истинность импликации ((не Q)) $\implies$ (не P)), что логически эквивалентно истинности исходного утверждения( $P\implies{Q}$ ).
Метод от противного. Предположив, что высказывание 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

Принцип математической индукции.

Пусть P(n) - предикат, определенный для всех натуральных чисел n. Предположим, что:

P(1) истинно и
$\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.

a делится на b, если выполняет равенство $a=mb$ .
Сумма делящихся на 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 = {сыр, яйцо, молоко, сметана}

$a\in{S}$ объект a - элемент множества S(принадлежит множеству S).
$a\cancel{\in} S$ объект a не принадлежит множеству S
$S=$ { $x:P(x)$ } множества состоит из элементов x, для которых предикат P(x) имеет истинное значение.( $S =$ {x: x - нечетное натуральное число} либо $S =$ { $2n-1$ : n - натуральное число} то есть $S=$ { $1,3,5,7,\dots$ })
$\varnothing$ - пустое множество
$\mathbb{N} =$ { $1,2,3,\dots$ } - множество натуральных чисел
$\mathbb{Z} =$ { $0,\pm{1},\pm{2},\pm{3},\dots$ } - множества целых чисел
$\mathbb{Q} =$ { $\frac{p}{q}: p, q \in{\mathbb{Z}},q \not={0}$ } - множество рациональных чисел
$\mathbb{R}=$ {все десятичные дроби} - множество вещественных чисел

Алгебра множеств

Дальнейшие свойства множеств

Глава 9. Булева алгебра

Булева алгебра

Карты Карно

Функциональные схемы

Глава 4. Отношения

Бинарные отношения

Свойства отношений

Отношения эквивалентности и частичнго порядка

Глава 5. Функции

Обратные отношения и композиция отношений

Функции

Обратные функции и композиции функций

Принцип Дрихле

Глава 6. Комбинаторика

Правила суммы и произведения

Комбинаторные формулы

Бином Ньютона

Глава 7. Графы

Графы и терминология

Гамильтоновы графы

Деревья

Глава 8. Ориентированные графы

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

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

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

Обозначения

PreviousМатематический анализ NextПолезные ссылки

Last updated 3 years ago