Добавил:

guap4736_vkclub152685050 Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Национальный минерально-сырьевой университет «Горный»

Предмет:

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

Файл:

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

.pdf

Скачиваний:

Добавлен:

11.08.2019

Размер:

1.66 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 45 / 115 6 7 8 9 10 11 > Следующая >>>

vk.com/club152685050 | vk.com/id446425943

A(t) (a0			2					k 1
		a1t a2t	2		... ak 1t			k 1
		a1t a2t			... ak 1t				) p1t A(t)

p	t k 1 A(t) a			0	p	k	t k A(t) 0.
	k 1			0		k

Из полученного равенства выразим функцию:

k 2
amt	m	...
amt		...
m 0

t(a

p ) t 2

p a

) ... t k 1 (a

k 1

p a

k 2

... p

k 1

)

A(t)

0 1

1 1

1 p t p

2 ... p

t k

Пример. Найти производящую функцию последовательности из примера 3: an 2 2an 1 an 0, a0 1, a1 2 .


Решение: an 2t n 2			2 an 1t n 2					ant n 2 0 ,
	n 0			n 0				n 0
		A(t) a a t				2t A(t) a			t 2 A(t) 0,
			0		1			0
		A(t)(1 2t t 2 ) (a					0	a t 2ta ) 0 ,
							0	1	0
Отсюда	A(t)	1 4t		.


		1 2t t 2
Замечание. Разложив A(t) в степенной ряд,									можно получить формулу

общего члена последовательности.

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

Рассмотрим рекуррентное соотношение (1)

an k	р1an k 1 р2an k 2 ... рk an 0 .	(1)
Опр. Уравнение
k р1 k 1 р2 k 2 ... рk 1 рk 0		(2)

называется характеристическим уравнением рекуррентного соотношения (1).

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

1.Пусть корень характеристического уравнения (2), тогда последовательность an С п удовлетворяет уравнению (1), С .

2.Пусть уравнение (2) имеет k различных корней, тогда общее решение уравнения (1) имеет вид an C1 1n C2 2n ...Ck k n , где Ci .

vk.com/club152685050 \| vk.com/id446425943

3. Пусть уравнение (2) имеет корни i кратностей ri ,	i 1, s , тогда
общее решение уравнения (1) имеет вид

ii , Cij .

4.Пусть уравнение (2) имеет комплексные корни 1,2 r(cos i sin ). Тогда им в формуле общего решения будет отвечать слагаемое2 nr 1

r n (C1 cosn C2 sin n ) .

Доказательство этого утверждения мы опускаем.

Пример. Найти общий член последовательности, заданной рекуррентным уравнением второго порядка (иначе – найти решение, удовлетворяющее начальным данным)

an 2 2an 1 15an 0, a0 1, a1 2.

Решение. Составляем характеристическое уравнение

2 2 15 0

3 .

Составляем

C ( 5)n C

общее

решение.

Коэффициенты

C ,C

находим из начальных условий a0 1,

a1 2 :

C1 C2 1,

. Таким образом, искомое частное решение

, C2

5C1

3C2

имеет вид: a

( 5)n

3n .

Пример. Найти общее решение линейного однородного рекуррентного

уравнения второго порядка

an 2 2an 1 2an 0 .

Составляем характеристическое уравнение 2

2 2 0 . Находим его

корни:

1 i . Решения

вида

( 1 i)n , ( 1 i)n являются

частными

1,2

решениями в комплексном виде. Найдем

вещественные решения.

Для этого

воспользуемся формулой Муавра и свойством линейности нашего рекуррентного уравнения

( 1 i)	n		n	3	i sin	3 n

		2	cos

				4		4

a(1)		n cos	3 n	,	a(2)		n sin	3 n	вещественные решения.
	2					2

n	4				n	4

						42

vk.com/club152685050 | vk.com/id446425943

Общее решение уравнения имеет вид

a		C		n cos	3 n	C			n sin	3 n	.
	n		2				2	2

		1	4					4

Замечание.

Рекуррентное уравнение (1) всегда можно записать в виде системы уравнений. Продемонстрируем это на примере уравнения второго порядка

xn 2 xn 1 xn

n 1

Полученную систему можно записать

yn 1 xn yn .

n 1

и в матричном виде. Действительно

. Здесь

yn 1

Теорема. Если все корни характеристического уравнения (2) находятся

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

(

k ), то все

решения уравнения (1) обладают свойством

an 0 (n ) . В этом случае

говорят, что решение an 0 n является асимптотически устойчивым.

Контрольные вопросы.

1.Чем занимается комбинаторика?

2.Что такое размещения, перестановки, сочетания?

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

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

5.Приведите формулу для вычисления мощности объединения конечных множеств.

6.Приведите формулу бинома Ньютона.

7.Приведите свойства биномиальных коэффициентов.

8.Дайте определение производящей функции.

9.Напишите производящую функцию числовой последовательности

1, -1, -1, -1, …

10.Дайте определение линейного однородного рекуррентного соотношения с постоянными коэффициентами.

11.В чем заключается алгоритм построения производящей функции для рекуррентного уравнения?

vk.com/club152685050 | vk.com/id446425943

12. Найдите частное решение рекуррентного уравнения an 2 an an 1 с начальными данными: 0,1? Как называется числовая последовательность, отвечающая этим начальным данным?

13.Найдите общее решение уравнения an 2 2an 1 3an 0 .

14.Найдите частное решение уравнения an 3 3an 2 3an 1 an 0 , удовлетворяющее начальным данным a0 1, a1 2, a2 0 . Найдите общее решение уравнения an 2 4an 0

vk.com/club152685050 | vk.com/id446425943

Глава 3. БУЛЕВЫ ФУНКЦИИ

§ 1. Понятие булевой функции

Булевой функцией f x1 , x2 ,..., xn называется функция n переменных,

каждая из которых принимает значение 0 или 1, и при этом функция принимает только одно из двух значений: 0 или 1.

Булеву функцию можно рассматривать как отображение вида

: 0,1 n 0,1 .

Множество 0,1 называют булевым и обозначают B 0,1 . Тогда

f : Bn B .

Область определения булевой

функции

f x1, x2 ,..., xn

– конечное

множество всех возможных

упорядоченных

наборов

x , x

,..., x Bn ,

состоящих из нулей и единиц.

n 2n , т. е.

По теореме о мощности прямого произведения

f x , x

область определения функции

,..., x

содержит

упорядоченных

наборов (или кортежей длины n ), состоящих из 0 и 1.

Множество значений булевой функции – множество B 0,1 .

Любая булева функция n переменных может быть задана таблицей. В

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

Например, булева функция трех переменных f x1, x2 , x3 имеет область

определения, состоящую из 23 8 наборов значений переменных. Приведем для примера таблицу булевой функции, которая называется мажоритарной функцией или функцией голосования. Эта функция принимает значение 1 на наборах переменных, содежащих единиц больше, чем нулей, и принимает значение 0 на всех остальных наборах (таб. 1).

vk.com/club152685050 | vk.com/id446425943

				Таблица 1

Номер	x`1	x2	x3	f x1, x2 , x3
набора	x`1	x2	x3	f x1, x2 , x3
набора

0	0	0	0	0

1	0	0	1	0

2	0	1	0	0

3	0	1	1	1

4	1	0	0	0

5	1	0	1	1

6	1	1	0	1

7	1	1	1	1

При задании булевой функции n переменных нет необходимости каждый раз перечислять все n наборов переменных, достаточно записать вектор значений булевой функции. При этом i -я компонента этого вектора есть значение функции на i -м наборе. Тогда приведенная для примера мажоритарная функция может быть задана так: f x1, x2 , x3 0,0,0,1,0,1,1,1 .

Выясним, сколько различных булевых функций n переменных можно определить. Булева функция полностью определяется вектор-столбцом своих

значений. Размерность этого столбца 2n . Сколько разных столбцов (кортежей)

длины 2n , состоящих из 0 и 1, можно построить? По теореме о мощности прямого произведения их число

B2n B 2n 22n .

Таким образом, число различных булевых функций n переменных равно

22n .

Множество всех булевых функций n переменных обозначается P2 n .

		n		22n .
Их число	P
	2
Переменная		xi	в функции f x1, x2 ,...xn называется несущественной

или фиктивной, если

f x1,...xi 1,0, xi 1,..., xn f x1,...xi 1,1, xi 1,..., xn

при любых значениях остальных переменных.

Переменная, не являющаяся фиктивной, называется существенной.

vk.com/club152685050 | vk.com/id446425943

Булевы функции f и g называются равными, если они имеют одни и те же существенные переменные и на каждом наборе значений этих переменных

функции f и g принимают равные значения.
§2. Булевы функции одной переменной
Для булевой функции одной переменной n 1 ,							число	наборов
переменной 21 2 . Всего булевых функций одной переменной 221								4 (табл.
2).
				Таблица 2

	x	f0	f1		f2	f3
	0	0	0		1	1

	1	0	1		0	1

Функция f0 называется константой 0 , её значение не зависит от значения переменной x : f0 x 0

Функция f1 повторяет x и называется функцией тождественности: f1 x x .

Функция f2 принимает противоположное по отношению к x значение и

называется отрицанием x :

							f2 x x x x .
	Функция			f3	называется				константой 1,						её	значение				не		зависит		от
значения переменной x :						f3 x 1.
	§3. Булевы функции двух переменных
	Для булевой функции двух переменных n 2														,			число					наборов
переменных 22 4. Всего булевых функций двух переменных 222																						16 (табл.
3).
																						Таблица 3

x1	x2	f0	f1	f2	f3	f4		f5	f6			f7	f8	f9	f10		f11		f12		f13		f14	f15
0	0	0	0	0	0	0		0	0		0		1	1	1		1		1		1		1	1

0	1	0	0	0	0	1		1	1		1		0	0	0		0		1		1		1	1

1	0	0	0	1	1	0		0	1		1		0	0	1		1		0		0		1	1

1	1	0	1	0	1	0		1	0		1		0	1	0		1		0		1		0	1

										47


vk.com/club152685050 \| vk.com/id446425943
Функция	f0 x1, x2 принимает значение 0 на всех наборах переменных
и называется константой 0 : f0 x1, x2 = 0 .
Функция	f1 x1, x2 принимает единичное значение только тогда, когда
обе переменные принимают единичное значение, и называется конъюнкцией x1
и x2 или логическим умножением x1 и x2 . Обозначение
	f1 x1, x2 x1 x2 x1x2 x1 x2 x1 & x2 .
Функция	f2 x1, x2 называется функцией запрета по переменной x2 :
	f2 x1, x2 = x1				.
				x2
Функция	f3 x1, x2 повторяет значение переменной x1 ,					она называется
функцией тождественной x1 , ( x2 – несущественная переменная):
	f3 x1, x2 = x1 .
Функция	f4 x1, x2 называется функцией запрета по переменной x1 :
	f4 x1, x2 =		x2 .
		x1
Функция	f5 x1, x2 повторяет значение переменной x2 ,					она называется
функцией тождественной x2 : f5 x1, x2 = x2 .
Функция	f6 x1, x2 принимает единичное значение,					когда значения
переменных различны, и равна 0,когда переменные равны. Называется
функцией неравнозначности, а также сложением по модулю 2								x1 и x2 .
Обозначение f6 x1, x2 = x1 x2 .
Функция	f7 x1, x2 принимает единичное значение, когда хотя бы одна
переменная равна 1, и называется дизъюнкцией x1 и x2 или								логическим
сложением x1 и x2 . Обозначение f7 x1, x2 = x1 x2 .
Функция	f8 x1, x2 принимает единичное значение только тогда, когда
обе переменные принимают нулевое значение, и называется стрелкой Пирса
или отрицанием дизъюнкции. Обозначение f8 x1, x2 x1 x2									.
							x1 x2
Функция	f9 x1, x2 принимает единичное значение только тогда, когда

значения переменных равны, и равна 0, когда переменные различны.

Называется эквиваленцией или равнозначностью x1 и x2 . Обозначение

f9 x1, x2 = x1 x2 .


vk.com/club152685050 \| vk.com/id446425943
Функция	f10 x1, x2 принимает значение, противоположное значению
переменной x2 , и называется отрицанием x2 : f10 x1, x2 =							.
					x2
Функция	f11 x1, x2 принимает нулевое значение только тогда,							когда
переменная x`1	равна 0, а переменная x2 равна 1, и называется импликацией из
x2 . Обозначение f11 x1, x2 = x2 x1.
Функция	f12 x1, x2 принимает значение, противоположное значению
переменной x1 , и называется отрицанием x1 : f12 x1, x2 =						.
				x1
Функция	f13 x1, x2 принимает нулевое значение только тогда,							когда
переменная x`1	равна 1, а переменная x2 равна 0, и называется импликацией из
x1 . Обозначение f13 x1, x2 = x1 x2 .
Функция	f14 x1, x2 принимает нулевое значение только тогда,							когда
обе переменные принимают единичное значение, и называется штрихом
Шеффера или отрицанием конъюнкции. Обозначение
	f14 x1, x2 x1 \| x2		.
		x1 x2
Функция	f15 x1, x2 принимает единичное значение на всех наборах

переменных и называется константой 1: f15 x1, x2 =1.

С возрастанием числа переменных функции n число булевых функций стремительно растет.

При n 3 имеется 223 256 функций трех переменных f x1, x2 , x3 .

При n 4 имеется 224 65536 функций четырех переменных f x1, x2 , x3 , x4 .

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

§ 4. Суперпозиции и формулы

Суперпозицией функций f1, f2 ,..., fm называется функция f , которая

получается с помощью подстановок этих функций друг в друга. Например, пусть

vk.com/club152685050 | vk.com/id446425943

f f6 y1, y2 , y1 f7 x1, x2 , y2 f1 x3 , x4 .

Тогда

f f6 f7 x1, x2 , f1 x3 , x4

f7 x1, x2 f1 x3 , x4

x1 x2 x3 x4 F x1, x2 , x3 , x4 .

Формулой называется выражение, описывающее эту суперпозицию. Всякая формула, выражающая функцию f как суперпозицию других

функций, задает способ её вычисления.

Например, если x1 0, x2 1, x3 1, x4 1, то

F x1, x2 , x3 , x4 1 1 0 .

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

В отличие от табличного задания представление данной функции формулой не единственно.

Формулы, представляющие одну и ту же функцию, называются

равносильными или эквивалентными.

Равносильность формул будем обозначать знаком равенства.

Для уменьшения числа скобок в формуле вводится приоритет операций. Наиболее приоритетно отрицание, затем идет конъюнкция, дизъюнкция, импликация, эквиваленция. Считается, что стрелка Пирса и штрих Шеффера имеют тот же приоритет, что и конъюнкция, а сложение по модулю 2 – тот же приоритет, что и эквиваленция.

§ 5. Свойства булевых функций

С помощью таблиц булевых функций можно проверить следующие свойства булевых функций:

1. Коммутативность

a b b a,	a b b a.
2. Ассоциативность
a b c a b c ,		ab c a bc .

3. Дистрибутивность

<<< < Предыдущая 1 2 3 45 / 115 6 7 8 9 10 11 > Следующая >>>

Соседние файлы в предмете Дискретная математика

#
11.08.20191.66 Mб54Дискретная математика.pdf
#
10.08.2019171.64 Кб26тест дискретка 3.pdf
#
10.08.2019158.13 Кб45Тесты по Дискретной математике 2.pdf
#
10.08.2019184.97 Кб78Тесты по Дискретной математике.pdf