Добавил:

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

Вуз:

Липецкий государственный технический университет

Предмет:

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

Файл:

Ответы на вопросы к экзамену 2011

.pdf

Скачиваний:

Добавлен:

20.06.2014

Размер:

1.11 Mб

Скачать

☆

<<< < Предыдущая 1 23 / 53 4 5 > Следующая >>>

1 1 0 1 1

0 1 c 1 0 c c 1

Смешанной производной

, x

,..., x

переменным xi

,..., xi

называется функция:

k 1

, x

,..., x

, x

,..., x

ik 1

Общей

производной

k -го

порядка

от булевой функции f (x1 ,..., xn ) по

k f		от булевой функции
xi ,..., xi		от булевой функции
xi ,..., xi
1	k

f (x1 ,..., xn ) по переменным xi

,..., xi

называется функция:

k f

2 f

3 f

k f

...

x ,..., x

x x

... x

i 1

i, j,

i, j,s,

i j

i j, j s,i s

Общая производная k -го порядка определяет условия, при которых эта функция изменяет значение при одновременном изменении значений переменных xi1 ,..., xik и при одинаковых остальных значениях переменных.

f a, b, c ab abc.

Cмешанная производная:

f 1 b 0 b c 0 b 1 b c b bca

2 f

a b3 f

a b c

Общая производная 2-го порядка функции:

2 f

a, b

a b

b bc

1c a1

0c a

2 f

c 1

ac,

a b

2 f

b bc a ac c 1 b bc a ac c

a, b

Функция

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

2 f

значений a,b в том случае, когда

a, b


				(	)
0	0	0	0		0
0	0	1	0		0
0	1	0	0		1
0	1	1	1		0
1	0	0	1		1
1	0	1	1		0
1	1	0	0		0
1	1	1	0		0

Функция f меняет значение при одновременном переключении

значений a,b,c в том случае, когда				3 f			1.
значений a,b,c в том случае, когда			a, b, c				1.


						(		)
	0	0		0	0			0
	0	0		1	0			0
	0	1		0	0			1
	0	1		1	1			0
	1	0		0	1			0
	1	0		1	1			1
	1	1		0	0			0
	1	1		1	0			0

Вопрос №21. Разложение булевой функции в заданной точке пространства.

Многочлен Жегалкина:

P x1 ,..., xn a0 ai

xi aij xi

x j ... a12...n x1 x2 ... xn .

i 1

i, j 1,

i j

, i 1,..., n.

Доказательство.

f x1

,..., xn

x1,..., xn

[ f x1,...,0,..., xn x1,...,0,..., xn ]

[ f x1,...,1,..., xn x1,...,1,..., xn ] [ f x1,...,0,..., xn f x1,...,1,..., xn ]

[ x ,...,0,..., x

x ,...,1,..., x ]

... x

i 1

Доказательство.

x1 ... xn (x1 ... xi 1

0 xi 1 ... xn )

(x1 ... xi 1 1 xi 1 ... xn )

x1 ... xi 1 xi 1 ... xn .

0, г деc const 0 или 1 .

Доказательство.

c c c 0 .xi

0 0 0 ,

1 1 0 .

Продифференцируем исходный многочлен:

P x1 ,..., xn

a1 x1 a2 x2 ...

an xn

a12 x1 x2 a13 x1 x3

... a1n x1 xn

a23 x2 x3 ..

an 1,n xn 1

...

a1,n 1,n x1 xn 1 xn

a123 x1

x2 x3 a124 x1

x2 x4 ...

a12...n x1 x2

... xn

0 a1 0 ... 0

a12 x2 a13 x3 ... a1n xn

0 ... 0

a123 x2 x3 a124 x2 x4 ... a1,n 1,n xn 1 xn ...

a12...n x2 ... xn .

2 P x1,..., xn a12 a123 x3 a124 x4 ... a12n xn ...x1 x2

a12...n x3 ... xn .

3P x1,..., xn a123 ... a12...n x4 ... xn .x1 x2 x3


k P x ,..., x		a	... a		x	... x .
1	n	a	... a		x	... x .
x1... xk		12...k		12...n	k 1	n
x1... xk
Таким	образом,			после	дифференцирования по x1 ,..., xk все члены в
исходном многочлене до a12...k					обращаются в нуль. Если подставить (0,0,…,0) ,

то остальные члены разложения, кроме a12...k , будут равны 0.

Вопрос №22. Теорема о функциональной полноте (теорема Поста).

Примеры функционально-полных базисов.
Для того, чтобы система булевых функций *	+	была		полной,
необходимо и достаточно, чтобы для каждого из классов	,	,	,	и
нашлась функция из системы, не принадлежащая этому классу.
Докажем только необходимость этого условия. Классы		,	,	, и

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

содержаться в функционально замкнутом классе, отличном от класса		всех
булевых функций, в силу его замкнутости система *	+ не была бы
полной.
Вопрос №25. Метод Квайна – Мак-Класски.
Табличный метод минимизации булевых функций.
Одной из важнейших интерпретаций булевых алгебр	является	булева

алгебра переключательных функций. Первоначально этот математический аппарат был применен для анализа и синтеза множества релейно-контактных схем с операциями последовательного (конъюнкция) и параллельного (дизъюнкция) соединения контактов и операцией дополнения. 1 – проводник, 0

– разрыв.

Множество всех переключательных функций (ПФ) обозначают Р2. Алгебра ( ̅ )называется булевой алгеброй

переключательных функций.

Импликантой переключательной функции			(	) называется
функция	(	) которая обращается в 1 на некотором подмножестве
единичных наборов функции Y.
Пример.
Импликанты		данной функции: x1 x2 x3 ,	x1 x2 x3 ,	x1 x2 x3 ,

x1 x2 x3 - элементарные конъюнкции.

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

Пример.

((x1 x2 ) x3 ) (( x1 x2 ) x3 ) x1 x2 .

Простой (первичной) импликантой (минималью) функции Y=F(x1,...,xn)

называется импликанта, которая не склеивается с никакой другой и не поглощается никакой другой импликантой данной функции Y.

Пример.

Y (x1, x2 , x3 ) x1x2 x3 x2 x3

y1 (x1, x2 , x3 ) x1x2 x3 –

импликанта функции Y, y2 (x1 , x2 , x3 ) x2 x3 простая

импликанта функции Y, т.к. она поглощает импликанту y1:

x1x2 x3 x2 x3 x2 x3 (x2x3 x1) x2 x3

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

Тупиковая ДНФ (ТДНФ) – это ДНФ, из которой нельзя исключить ни одной простой импликанты без потери эквивалентности формулы.

Минимальная ДНФ (МДНФ) – это ТДНФ, содержащая минимальное число символов среди возможных ТДНФ функции.

Метод Квайна – Мак-Класки состоит из двух этапов:

1)Получение всех простых импликант ПФ (построение СкДНФ).

2)Поиск всех ТДНФ по импликантной таблице покрытий и выбор их

них МДНФ.

Исходная функция должна быть представлена в СДНФ.

Каждая элементарная конъюнкция может быть представлена двоичным числом.

Каждой конъюнкции присваивается индекс – число единиц в двоичном представлении конъюнкции

Первый этап основан на последовательном применении операции склеивания (формула расщепления).

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

1)индексы данных чисел отличались на единицу;

2)сами числа отличались на 2i (i=0, 1, …);

3)число с большим индексом было больше числа с меньшим индексом.

Одна и та же конъюнкция может быть склеена с другими несколько раз. При этом компонента, меняющая свое значение, заменяется «–».

Пример.

При склеивании 0011 и 0111 получаем 0–11.

Теорема 6.14. Любая булева функция f (x1 ,..., xn ) определяется своим значением в точке ( 1 ,..., n ) и значениями своих производных в этой точке в виде:

f (x1,..., xn ) f ( 1,..., n )

( 1,..., n ) (xi

i )

i 1

2 f

( 1,..., n ) (xi i ) (x j

j )

x x

i, j 1

i j

...

n f

( 1

,..., n ) (x1 1)

... (xn n ).

x1,..., xn

f (x, y, z y ~ [

x y] в точке

Пример.

Найти

разложение

функции

(0,1,1):

f (0,1,1) 1 ~ [(0 0) 1] 1 ~ [0 1] 1 ~ 1 1.

(0,1,1)

z x

(0,1,1)

x y

(0,1,1)

2 f

(0,1,1) z

(0,1,1)

x y

2 f

(0,1,1) y

(0,1,1)

x z

2 f

(0,1,1) x

(0,1,1)

y z

3 f

(0,1,1)

x y z

Вопрос №26. Схемы из функциональных элементов.

Вопрос №27. Понятие конечного автомата. Автоматы Мили и Мура.

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

x(t)		y(t)
x(t)	М	y(t)
	М

К.А. – A (X , Q,Y , , , q0 )

X (x1,..., xm ) - входной алфавит, его элементы – входные сигналы, их последовательности – входные слова;

Q (q1,..., qn ) - алфавит состояний, его элементы – состояния автомата в моменты времени t; их последовательности – слова состояний;

Y ( y1,..., yp ) - алфавит выходов, его элементы – выходные сигналы, их

последовательности – выходные слова;

Функция : X Q Q - функция переходов, (x, q) Q ; Функция : X Q Y - функция выходов, (x, q) Y ; q0 = q(0) – начальное состояние.

Если в момент времени t = 1, 2, … на вход автомата A (X , Q,Y , , , q0 )

последовательно подаются	входные	символы x(t) X	и при этом	автомат
находится в состоянии q(t) Q , то		под воздействием	символа x(t)	автомат
перейдет в новое состояние q(t 1) Q и выдаст выходной сигнал y(t) .
q(t 1) (x(t); q(t)),	t 1,2,...
	t 1,2,...
y(t) (x(t); q(t)),

Если функция выходов зависит от входов и состояний, то КА называется автоматом Мили.

Если функция выходов зависит от состояний, но явно не зависит от входов, то КА называется автоматом Мура.

Вопрос №28. Способы задания конечного автомата.

1) Таблично

( )

2) Диаграмма Мура – граф с n вершинами.

3) Функции переходов и выходов можно задать аналитически.

Вопрос №31. Представление конечных автоматов матрицами соединений.

Матрица соединений КА строится как квадратная матрица размера n n , строки и столбцы которой соответствуют различным состояниям КА, причем первый столбец и первая строка матрицы соответствуют начальному состоянию КА. На пересечении qi строки и q j столбца следует расположить входное

воздействие, вызывающее переход автомата из состояния qi в q j , а через дробь

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

Вопрос №32. Дерево конечного автомата.

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

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

Для КА Мура в каждом столбце матрицы соединений стоит один и тот же выход. Матрица соединений является матрицей смежности для графа КА

КА Мили

*	+	*	+	*	+

		(	)

Q	A			B		C
X	A			B		C
X
1	C			B		A
2	A			B		B
3	A			A		A
4	C			B		B

		(	)
Q	A			B		C
X	A			B		C
X
1	k			m		k
2	m			n		n
3	k			p		p
4	k			n		p

Матрица соединений КА

			в
		A	B	C
из	A
из	B
	C

Дерево КА Мили Пусть

КА Мура
*	+,	*	+,	*	+

			(	)
Q		E		F	G	H
X		E		F	G	H
X
I		F		E	H	F
II		G		H	E	F
III		F		G	E	G
( )		7		6	5	8

из

Дерево КА Мура Пусть

Вопрос №33. Основные формулы комбинаторики.

Правило суммы. Если элемент x может быть выбран m способами, а элемент y – другими n способами, то выбор «либо x либо y» может быть осуществлен (m n) способами.

Правило произведения. Пусть необходимо выполнить последовательно k действий. Если первое действие можно выполнить n1 способами, второе n2

способами, …, k -тое nk способами,	то	все k действий можно			выполнить
n1 n2 ... nk способами.
Кортеж - конечная последовательность элементов.
				n .
Пусть A - конечное множество из n элементов, т.е.			A	n .
Размещения. Кортежи длины	k	(1 k n) , состоящие из			различных

элементов множества A , называются размещениями из n элементов множества

Aпо k , если кортежи отличаются один от другого как самими элементами, так

иих порядком.

Обозначение Ank .

Схема выбора состоит в выборе k элементов из n -элементного множества без возвращения.

Ak	n (n 1) ... (n (k 1)) (n k)!		n!

n	(n k)!		(n k)!

n! 1 2 3 .... (n 1) n		- факториал числа n
Перестановки. Пусть		A -множество,		A	n . Кортежи длины n

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

Обозначение Pn

от

Формула P An		n!		n!

n	n	(n n)!

Сочетания.	Кортежи		длины k (1 k n) , состоящие из различных
элементов множества A ,		называются сочетаниями из n элементов по k , если

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

раз.

Обозначение Cnk

Число сочетаний из n по k меньше числа размещений из n по k в Pk раз, т.е.

Cnk	Ak	n!
	n
	Pk	(n k)!k!
	Pk	(n k)!k!

Тождества

<<< < Предыдущая 1 23 / 53 4 5 > Следующая >>>

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

#
20.06.20143.1 Mб98Лекции по теме Деревья и графы.doc
#
20.06.20141.05 Mб275Лекции. Множества.doc
#
20.06.20141.78 Mб103Лекция Алгоритмы на графах.doc
#
20.06.20141.06 Mб15Лекция Булевы функции.ppt
#
20.06.201483.46 Кб92Метод Квайна – Мак-Класки.doc
#
20.06.20141.11 Mб36Ответы на вопросы к экзамену 2011.pdf
#
20.06.2014133.63 Кб39Теория автоматов.doc
#
20.06.2014309.25 Кб26Теория графов, элементы графов, связность в орграфах.ppt
#
20.06.20141.05 Mб133Транспортные сети. Максимальный поток.doc
#
20.06.2014754.69 Кб11Элементы комбинаторного анализа.ppt

*	+	*	+	*	+

		(	)

Q	A			B		C
X	A			B		C
X
1	C			B		A
2	A			B		B
3	A			A		A
4	C			B		B

		(	)
Q	A			B		C
X	A			B		C
X
1	k			m		k
2	m			n		n
3	k			p		p
4	k			n		p

*	+	*	+	*	+

		(	)

Q	A			B		C
X	A			B		C
X
1	C			B		A
2	A			B		B
3	A			A		A
4	C			B		B

		(	)
Q	A			B		C
X	A			B		C
X
1	k			m		k
2	m			n		n
3	k			p		p
4	k			n		p

*	+	*	+	*	+

		(	)

Q	A			B		C
X	A			B		C
X
1	C			B		A
2	A			B		B
3	A			A		A
4	C			B		B

		(	)
Q	A			B		C
X	A			B		C
X
1	k			m		k
2	m			n		n
3	k			p		p
4	k			n		p