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

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

Квантор — общее название для логических операций, ограничивающих область истинности какого-либо предиката.

Включая предикат в кванторы мы превращаем его в высказывание.

Стандартные типы рассуждений:

· Прямое рассуждение. Предположим, что А – истинно и показывает справедливость В.

· Обратное рассуждение. Предположим, что высказывание В – ложно и показывает ошибочность А.

· Метод от противного. Предположим, что высказывание А – истинно, а В – ложно, используя аргументированность рассуждения получаем противоречие.

Метод математической индукции:

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

Метод математической индукции состоит в следующем:

Предложение (утверждение) P(n), зависящее от натурального числа n, справедливо для любого натурального n если:

1. P(1) является истинным предложением (утверждением);
2. P(n) остается истинным предложением (утверждением), если n увеличить на единицу, то есть P(n + 1) - истинное предложение (утверждение).

Таким образом метод математической индукции предполагает два этапа:

1. Этап проверки: проверяется, истинно ли предложение (утверждение) P(1).
2. Этап доказательства: предполагается, что предложение P(n) истинно, и доказывается истинность предложения P(n + 1) (n увеличено на единицу).

Понятие бинарного отношения между множествами и на множестве, ориентированного графа. Способы задания бинарного отношения между конечными множествами. Свойства отношений в терминах упорядоченных пар, в изображении ориентированных графов. Замыкание отношения. Обратные отношения. Композиция отношений.

10. Понятие функционального отношения множеств или отображения множеств в множество. Образ и прообраз. Некоторые важные свойства функции: инъективное, сюръективное и биективное отображение. Принцип Дирихле.

Свойства:- инъективным (или инъекцией, или взаимно однозначным отображением множества E в F), если , или если уравнение f(x) = y имеет не более одного решения;- сюръективным (или сюръекцией, или отображением множества E на F), если f(E) = F и если уравнение f(x) = y имеет по крайней мере одно решение;- биективным (или биекцией, или взаимно однозначным отображением множества E на F), если оно инъективно и сюръективно, или если уравнение f(x) = y имеет одно и только одно решение. Принцип Дирихле: Дирихле принцип (по имени П. Г. Л. Дирихле), 1) принцип ящиков — предложение, утверждающее, что в случае m > n при отнесении каждого из m предметов к одному из n классов хотя бы в один класс попадёт не менее двух предметов. Это чрезвычайно простое предложение применяется при доказательстве многих важных теорем теории чисел, относящихся к приближению иррациональных чисел рациональными, в доказательствах трансцендентности чисел и др. вопросах. 2) В теории гармонических функций Д. п. называют следующее предложение: среди всех возможных функций, принимающих заданные значения на границе области G, функция, для которой интеграл достигает наименьшего значения, будет гармонической в области. Предложение это имеет простой физический смысл (если u есть потенциал скоростей в установившемся течении однородной несжимаемой жидкости, то J с точностью до постоянного множителя выражает кинетическую энергию жидкости). Д. п. находит большие применения в математической физике.

Общие правила комбинаторики (правила суммы и произведения). Примеры решения задач по правилам суммы и произведения. Понятие выборки объема kиз п элементов. Упорядоченные и неупорядоченные выборки. Размещение с повторениями, размещение без повторений. Перестановки. Сочетания с повторениями. Сочетания без повторений.

Правило суммы: Если некоторый объект А можно выбрать m способами, а другой объект В можно выбрать n способами, то выбор "либо А, либо В" можно сделать (m+n) способами. При использовании правила суммы в такой формулировке нужно следить, чтобы ни один из способов выбора объекта А не совпадал с каким-нибудь способом выбора объекта В. Если такие совпадения есть, то правило суммы утрачивает силу и получается лишь m+n-k способов выбора, где k-число совпадений. Правило произведения: Если объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать n способами, то выбор пары(А,В) в указанном порядке можно осуществить mn способами. Пример: Если на одной полке книжного шкафа стоит 30 различных книг, а на другой - 40 различных книг (и не таких, как на первой полке), то выбрать одну книгу из стоящих на этих полках можно 30+40=70 способами.(сумма).Размещения с повторениями-кортежи длины k, составленные из элементов m-множества. Размещения без повторений из n элементов по m - упорядоченные m-множества, состоящие из элементов n- множества. Перестановка n элементов, расположение этих элементов в каком-либо порядке. Всего существует n! = 1•2•...•n различных П. из n элементов.

12. Комбинаторные формулы для подсчёта количества способов (n,k) – размещение с повторениями и без повторений, (n,k) – сочетание с повторениями и без повторений. Разбиение множества. Разбиение числа (нулевое и ненулевое). Бином Ньютона. Биноминальные коэффициенты.

Разбие́ние мно́жества — это представление его в виде объединения произвольного количества попарно непересекающихся подмножеств. Разбие́ние числа́ n — это представление n в виде суммы положительных целых чисел, называемых частями. При этом порядок следования частей не учитывается (в отличие от композиций), то есть разбиения, отличающиеся только порядком частей, считаются равными. В канонической записи разбиения части перечисляются в невозрастающем порядке. Число разбиений p(n) натурального числа n является одним из фундаментальных объектов изучения в теории чисел. Бино́м Нью́то́на — формула для разложения на отдельные слагаемые целой неотрицательной степени суммы двух переменных. НЬЮТОНА БИНОМ, название формулы, позволяющей выписывать разложение алгебраической суммы двух слагаемых произвольной степени. Биномиальным коэффициентом называется количество способов выбрать набор предметов из различных предметов без учёта порядка расположения этих элементов (т.е. количество неупорядоченных наборов).

Достоверные события. Невозможные события. Случайные события. Совместные и несовместные события. Зависимые и независимы события. Равновозможные элементарные события. Классическое определение вероятности.

Достове́рным собы́тием в теории вероятностей называется событие U, которое в результате опыта или наблюдения непременно должно произойти.

Невозмо́жным собы́тием в теории вероятностей называется событие, которое не может произойти в результате эксперимента. То есть событие, не содержащее ни одного элементарного исхода.

Случа́йное собы́тие — подмножество множества исходов случайного эксперимента; при многократном повторении случайного эксперимента частота наступления события служит оценкой его вероятности.

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

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

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

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