27. Непрерывные случайные величины. Равномерное, экспоненциальное.

Закон равномерной плотности

Равномерным называется распределение непрерывной случайной величины Х все

значения которой лежат на отрезке [a;b] и имеют при этом постоянную плотность

распределения

площадь под кривой распределения равна 1 и поэтому с(в-а)=1

вероятность попадания случайной величины Х на интервал от (α;β)

α=а, если α<а

β=в, если β>в

основные числовые характеристики закона распределения плотности вычисляются

по общим формулам и они равны

Показательное (экспоненциальное распределение)

Показательным называют распределение непрерывной случайной величины Х которое

описывается следующей дифференциальной функцией

Экспоненциальное распределение для непрерывных случайных величин является

аналогом распределения Пуассона для дискретных случайных величин и имеет

следующий вид.

вероятность попадания случайной величины Х на интервал (α;β)

Следует отметить, что время безотказной работы удовлетворяется именно

показательному закону, а поэтому это понятие часто используется в понятии

надежности.

28. Разложение булевой функции по переменным

Обозначим

Посмотрим, чему равно x^ при разных значениях x и .

Из таблицы следует: x^=1 тогда и только тогда, когда x=.

Теорема о разложении функции по переменным П усть f(x₁, ..., x_n) P₂. Тогда для любого m: 1 ≤ m ≤ n допустимо представление:

,

где дизъюнкция берется по всем наборам из 0 и 1, которое называется разложением функции f по переменным x₁, ..., x_n. Прежде чем доказать утверждение, рассмотрим примеры. Пример 1. m = 1, запишем разложение по переменным х:

f(x₁, ..., x_n) = = f(0, x₂ , …,x_nx₁f(1, x₂, ..., x_n). (1)

Пример 2. m=2, запишем разложение по переменным х и :

.

Если f(x_, x_ = x_x_, то последняя формула дает x_x_= x_x_ .

Доказательство. Для доказательства возьмем произвольный набор  и покажем, что левая и правая части формулы (1) принимают на этом наборе одинаковые значения. Слева имеем f__n. Cправа : .

Дизъюнкция берется по всевозможным наборам (__). Если в этих наборах хотя бы одно __i (1≤i≤m), то = 0 и , следовательно, ненулевой член будет только на наборе __) = __), тогда c3

f__n.

Следствие 1. Любую функцию f(x₁, ..., x_n) не равную тождественно нулю можно представить в виде: , причём единственным образом. Этот вид называется совершенной дизъюнктивной нормальной формой функции f(x₁, ..., x_n) и записывается СДНФ.

Доказательство. Существование СДНФ для функции не равной тождественно нулю вытекает из предыдущей теоремы. Покажем, что эта СДНФ единственная. В самом деле, имеется n-местных функций, не равных нулю тождественно. Подсчитаем число различных СДНФ от n переменных. Путь означает число сочетаний из n элементов по k. Тогда число одночленных СДНФ равно . Число k-членных СДНФ равно . Число n-членных СДНФ равно . Число всех различных СДНФ

Итак, функций реализуются посредством СДНФ, т.е. каждой функции соответствует единственная СДНФ.

Замечание. – элементарная конъюнкция ранга n по числу входящих переменных, предполагается, что при i  j , х_i  х_j. СДНФ для f(x₁, ..., x_n) –дизъюнкция элементарных конъюнкций ранга n. Если функция представлена в виде дизъюнкций элементарных конъюнкций, где ранг хотя бы одной элементарной конъюнкции меньше n, то такая форма называется дизъюнктивной нормальной формой (ДНФ).

Cледствие 2. Любая функция алгебры логики может быть представлена в виде формулы через отрицание, & и  а) Если f ≡ 0, то f(x₁, ..., x_n) = & . б) Если f(x₁, ..., x_n)  0 тождественно, тогда ее можно представить в виде СДНФ, где используются только связки , &,  СДНФ дает алгоритм представления функции в виде формулы через

&,  .

Следствие 3. Мы умеем представлять функцию в виде . Нельзя ли представить ее в виде . Пусть функция f(x₁, ..., x_n) 1 тождественно. Тогда функция f* 0 тождественно, и ее можно представить в виде СДНФ:

. По принципу двойственности заменим & на и наоборот, получим

(2)

называется элементарной дизъюнкцией ранга n. Представление функции в виде (2) называется совершенной конъюнктивной нормальной формой или в краткой записи – СКНФ. СКНФ для f(x₁, ..., x_n) – конъюнкция элементарных дизъюнкций ранга n. КНФ для f(x₁, ..., x_n) – конъюнкция элементарных дизъюнкций, где ранг хотя бы одной элементарной дизъюнкции меньше n. Пример 4. Пусть f(x₁, x₂, x₃) = x₁ (x₂ (x₃ ~ x₁)). Представим ее в виде СКНФ, для этого получим таблицу истинности.

x1	x2	x3	x3~x1	x 2 (x3~x1)	f
0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1	1 0 1 0 0 1 0 1	1 1 1 0 1 1 0 1	1 1 1 1 1 1 0 1

Функция равна нулю только на наборе (1, 1, 0), поэтому

f(x₁ x₂ x₃)=x₁ x₂ x₃ =x_^x₂^x₃¹=   x₃.

29. Дискр случ величины. биноминальн распредел, распр Пуассона, геометр распред.

Биноминальн распр называется распред вероятностей, определяем формулой Бернулли. Закон назван биномин потому что правую часть можно рассматрив как общий член разложен бинома Ньютона:

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

напишем биномин закон в виде таблицы:

Распределение Пуассона.

в случаях, когда производится n независимых испытаний при котором вероятность наступления событий мала (p<0.1). в этих случаях прибегают к асимптотической формуле Пуассона.

поставим перед собой задачу найти вероятность того что при большом числе испытаний, в каждом из которых вероятность события очень мала, событие наступит ровно k раз. сделав важное допущение: произведение np сохраняет постоянное значение, а именно это означает что среднее число появлений события в различных сериях испытаний, т.е. при различных значениях n, остается неизменным.

воспользуемся формулой Бернулли для вычисления, интересующей нас вероятности:

так как , то . следовательно,

приняв во внимание, что n имеет больш знач, вместо найдём при этом будет найдено лишь приближенное значение отыскиваемой вероятности: n хотя и велико, нно и конечно, а при отыскании предела мы устремим n к бесконечности. замети что поскольку произведение сохраняет постоянное значение, то при вероятность .

таким образом (для простоты записи знак приближенного равенства опущен)

эта формула выражает закон распределения Пуассона вероятностей массовых (n велико) и редких (p мало) событий.

геометрическое распределение

пксть произв независм испытания в кажд из кот вероятность появления события А равна p (0<p<1), вероятн его непоявл q=1-p. испытание заканчив-ся как только появится событие А. Т.о. если событие А появилось в k-ом испытании, в предшествующем k-1 испытании оно не появлялось.

пусть X дискретная случайная величина – число испытаний кот нужно произвести до первого появления события А. возможными значениями X являются натуральные числа:

пусть в первых k-1 испытаниях событие А не наступило, а в k-ом испытании появилось. вероятность этого «сложного события», по теореме умножения вероятностей независимых событий,

полагая что k=1.2...в формуле , получим геометрическую прогрессию с первым членом p и знаменателем q (0<q<1)^

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

Ряд сходится и его сумма равна единице.

30. Полином Жегалкина. f(x₁, ..., x_n) P₂, представим ее в виде формулы через конъюнкцию и сумму по модулю два, используя числа 0 и 1. Это можно сделать, так как {x₁&x₂, x₁x₂, 0, 1} полна в Р₂. В силу свойства x & (yz) = xy xz можно раскрыть все скобки, привести подобные члены, и получится полином от n переменных, состоящий из членов вида х х ...х , соединенных знаком . Такой полином называется полиномом Жегалкина.

Общий вид полинома Жегалкина: где , s = 0, 1, ..., n, причем при s = 0 получаем свободный член а₀.

Представление функции в виде полинома Жегалкина

1. Представим любую функцию формулой над {x₁&x₂, } и сделаем замену =x1. Этот способ удобен, если функция задана формулой.

Пример 2. (x₁ (x₂ x₃))(x₁ x₂) x₃ = (x₁ x₂ x₃)(x₁ x₂) x₃ = (x₁x₂ x₁x₃ x₁x₂ x₂ x₂x₃)x₃ = (x₁x₃ x₂)x₃ = x₁x₃x₂ x₃ = ((x₁x₃1)x₂1)x₃ = x₁x₂x₃x₂x₃x₃.

Надо помнить, что четное число одинаковых слагаемых в сумме по mod2 дает 0.

2. Метод неопределенных коэффициентов. Он удобен, если функция задана таблицей.

Пример 3. Запишем с неопределенными коэффициентами полином Жегалкина для функции трех переменных f(x₁, x₂, x₃) = (01101001) = а₀ а₁х₁ а₂х₂ а₃х₃ b₁x₁x₂ b₂x₂x₃  b₃x₁x₃  cx₁x₂x₃. Затем находим коэффициенты, используя значения функции на всех наборах. На наборе (0, 0, 0) f(0, 0, 0) = 0, с другой стороны, подставив этот набор в полином, получим f(0, 0, 0) = а₀, отсюда а₀ = 0. f(0, 0, 1) = 1, подставив набор (0, 0, 1) в полином, получим: f(0, 0, 1) = а₀ а₃, т.к. а₀ = 0, отсюда а₃ = 1. Аналогично, f(0, 1, 0) = 1 = а₂, f(0, 1, 1) = 0 = а₂ а₃ b₂ = b₂ = 0; а₁ = 1; 0 = а₁ а₃ b₃ = b₃ = 0; 0 = а₁  а₂ b₁ = b₁ = 0; 1 = 1 1 1 c; c = 0; f(x₁, x₂, x₃) = x₁ x₂ x₃.

3. Многочлен Жегалкина можно получить также с помощью треугольника Паскаля по единицам его левой стороны по таблице следующим образом. Построим многочлен Жегалкина для функции f = (10011110). Верхняя сторона треугольника есть функция f. Любой другой элемент треугольника есть сумма по модулю для двух соседних элементов предыдущей строки. Левая сторона треугольника для функции f содержит шесть единиц. Многочлен Жегалкина будет содержать шесть слагаемых. Первая единица треугольника соответствует набору (000). Первое слагаемое многочлена есть 1. Третья снизу единица в левой стороне треугольника соответсвует набору (101). В качестве слагаемого многочлена берем x₁x₃. Аналогично для других единиц треугольника. Слева от наборов показаны слагаемые многочлена Жегалкина.

		N			x1x2x3	f	Треугольник Паскаля
1 x3 x2 x2x3 x1 x1x3 x1x2 x1x2x3	000 001 010 011 100 101 110 111		1 0 0 1 1 1 1 0	1 0 0 1 1 1 1 0 1 0 1 0 0 0 1 1 1 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 0 1

Тогда

Теорема Жегалкина

Каждая функция из может быть представлена в виде полинома Жегалкина единственным образом.

Здесь единственность понимается с точностью до порядка слагаемых в сумме и порядка сомножителей в конъюнкциях:

, s = 0, 1, ..., n. Доказательство. Любая функция из Р₂ может быть представлена формулой над {x₁ & x₂, x₁x₂, 0, 1}, а эта формула после раскрытия всех скобок и приведения подобных членов дает полином Жегалкина. Докажем единственность представления. Рассмотрим функции f(x₁, ..., x_n) от n переменных. Мы знаем, что всего таких функций, т.е. их таблиц истинности , 2ⁿ. Подсчитаем число различных полиномов Жегалкина от n переменных, т.е. число вариаций вида: . Число наборов равно числу всех подмножеств множества { x₁, ..., x_n }, сюда входит и пустое множество (если s = 0). Число подмножеств множества из n элементов равно 2ⁿ , а так как каждый набор входит с коэффициентом , принимающим два значения: 0 или 1, то число всевозможных полиномов будет . Так как каждому полиному соответствует единственная функция, число функций от n переменных равно числу полиномов, то каждой функции будет соответствовать единственный полином.

Определение. Функция f(x₁, ..., x_n), полином Жегалкина для которой имеет следующий линейный относительно переменных вид: f = а₀ а₁х₁ а₂х₂ ... а_nх_n, называется линейной.

Лемма о нелинейной функции. Суперпозицией нелинейной функции, отрицания и константы 1 можно получить конъюнкцию.

Доказательство. Пусть f(x₁, ..., x_n) – нелинейная функция. Тогда полином Жегалкина содержит для нее слагаемое, в котором присутствует произведение x_ix_j. Будем считать для простоты, что x₁x₂ в многочлене Жегалкина является этим произведением. Произведя группировку слагаемых, функцию f представим в виде

Функция h₀ не есть тождественный нуль, иначе в полиноме Жегалкина отсутствует слагаемое с произведением x₁x₂. Тогда существует набор (₃, …, _n) из 0 и 1, для которого h₀(₃, …, _n) = 1. Пусть h₁(₃, …, _n) = a, h₂(₃, …, _n) = b, h₃(₃, …, _n) = c. Тогда

Построим функцию:

где d = ab  c. Если d = 0, то h(x₁, x₂) = x₁x₂. Если d = 1, то h(x₁, x₂) = x₁x₂  1 и тогда Лемма доказана.

Функция f(x₁, ..., x_n) сохраняет константу a  {0, 1}, если f(a, …, a) = a.

Пример 4. Функция xy сохраняет 0, сохраняет 1. Функция xy сохраняет 1 и не сохраняет 0

31. 11) Теорема Бернулли. Случайные величины. Функции распределения случайной величины.

Пусть производится n независимых испытаний, в каждом из которых вероятность появления события А равна р. Тогда, каково бы ни было положительное число , вероятность

, (*)

где m – частота появления события А при n испытаниях.

Из равенства (*) следует

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

Другими словами, если сколь угодно малое положительное число, то при соблюдении условий теоремы будет иметь место равенство

Случайная величина

Уже в первой части приводились события, состоящие в появлении того или иного числа. Например, при бросании игральной кости могли появиться числа 1, 2, 3, 4, 5 и 6. Наперед определить число выпавших очков невозможно, поскольку оно зависит от многих случайных причин, которые полностью не могут быть учтены. В этом смысле число очков есть величина случайная; числа 1, 2, 3, 4, 5 и 6 есть возможные значения этой величины. Случайной называют величину, которая в результате испытания примет одно и только одно возможное значение, наперед не известное и зависящее от случайных причин, которые заранее не могут быть учтены. Пример 1. Число родившихся мальчиков среди ста новорожденных есть случайная величина, которая имеет следующие возможные значения: 0, 1, 2, ..., 100. Пример 2. Расстояние, которое пролетит снаряд при выстреле из орудия, есть случайная величина. Действительно, расстояние зависит не только от установки прицела, но и от многих других причин (силы и направления ветра, температуры и т. д.), которые не могут быть полностью учтены. Возможные значения этой величины принадлежат некоторому промежутку (а, Ь). Будем далее обозначать случайные величины прописными буквами X, Y, Z, а их возможные значения—значения—соответствующими строчными буквами х, у, z. Например, если случайная величина X имеет три возможных значения, то они будут обозначены так: х1, х2, х3.

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

Определение функции распределения

Вспомним, что дискретная случайная величина может быть задана" перечнем всех ее возможных значений и их вероятностей. Такой способ задания не является общим: он неприменим, например, для непрерывных случайных величин. Действительно, рассмотрим случайную величину X, возможные значения которой сплошь заполняют интервал (а, Ь). Можно ли составить перечень всех возможных значений X? Очевидно, что этого сделать нельзя. Этот

п ример указывает на целесообразность дать общий способ задания любых типов случайных величин. С этой целью и вводят функции распределения вероятностей случайной величины. Пусть х—действительное число. Вероятность события, состоящего в том, что X примет значение, меньшее х, т. е. вероятность события X < х, обозначим через F (х). Разумеется, если х изменяется, то, вообще говоря, изменяется и F (х), т. е. F (х)—функция от х. Функцией распределения называют функцию F(х), определяющую вероятность того, что случайная величина X в результате испытания примет значение, меньшее х, т. е.

Геометрически это равенство можно истолковать так: F (х) есть вероятность того, что случайная величина примет значение, которое изображается на числовой оси точкой, лежащей левее точки х. Иногда вместо термина «функция распределения» используют термин «интегральная функция». Теперь можно дать более точное определение непрерывной случайной величины: случайную величину называют непрерывной, если ее функция распределения есть непрерывная, кусочно-дифференцируемая функция с непрерывной производной.

32. Теория графов (основные определения)