lec07 производная булевой функции

Добавил:

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

Вуз:

МИРЭА - Российский технологический университет

Предмет:

Математическая логика и теория алгоритмов

Файл:

f ( , , . . . , ,

= , , . . . ,

, ( = 1 ÷ )

= , , . . . ,

, ( = 1 ÷ )

.pdf

Скачиваний:

Добавлен:

23.06.2023

Размер:

1.47 Mб

Скачать

☆

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

Пусть g = ∂f /∂xi производная функции f (x1,x2,... xi,...,xn) по переменной xi, тогда существует множество БФ {f1,f2,...,fm}, называемое булевым интегралом функции g, таких что:

g = xi g h

где h – БФ, зависящая от n-1 переменных (x1,x2,... xi−1,xi+1,...,xn).

!!! Если не оговорено особо, то для операции .

Утверждение 7.1. Любая БФ f (x1,x2,...,xn) может быть получена в результате n-кратного логического интегрирования константы {0} :

1		)	= f (x1,x2,...,xn)
(… ( C	) …	)

Пример 7.10.

n-кратное интегрирование C для получения функций f(x1,x2).

1) f0	≡ 0.	= () =	0	f			0 h =		0
1) f0	≡ 0.	= () =							0
		?	1			= x1 f0 h =
			1	0	1	= x1 f0 h =	1	?	1
									1

2) f	1	= 0	. = () = 0
	1	1					1
		1					1
										0
		f1 1		= x	f	h =	0 0		=	1
				1	1		1	? 1		1
										1

				0
Пример 7.10.		3) f2	=	1		.
		3) f2	=	1		.
				1
				1
				0
f	= x2 f2 h =			2		?
f	= x2 f2 h =
2	2
2	2			1	2
				1	2
				1 2

= ?		0
= ?		1
= (x1)	=	1
		1

11 =

	0		0		0		2		2
a) 0	1	=	1	b) 2	1		2		2
a) 0	1	=	1	b) 2		?	=	=	1	2
						?	1 2		1	2
	1		1		1		1 2
	1		1		1		1 2
									1	2

Пример 7.10.

		0			1 2
c)	1 2	1	=		1 2
c)	1 2		=		1 1 2
		?1			1 1 2
		1
					1	1	2
		0			1 2
d)	1 2	1	=		1 2		=
d)	1 2		=	1 1 2			=
		?1		1 1 2
		1
				1	1	2

1 2

1| 2

= (x1 x2) x1 x2

2 1 2		(x2	x1)
1 2	=	x2 x1
1 1 2 2		x1	x2

1 1 2 21		x1 x2

Интегрируя каждую из полученных 4 функций ( С 1) по x2,

получили все 16 БФ f(x1,x2). Продолжая интегрирование по следующей переменной x3 получим 256 функций f(x1,x2,x3) и т. д.

Интеграл от булевой функции f (x1,x2,...,xn) по переменной xn+1 для операции р(a,b)

f (x1,x2,...,xn) +1

есть множество булевых функций {f1,f2,...,fm}, зависящих от n+1 переменных, таких, что

Пример 7.12. Найти интеграл от функции f(x1) = x1 для операции . Найдем для (x1,x2) все ∂f /∂x2 для операции .

1) f0 ≡ 0.

f0(1, 2)	=					x1	x2		f0		f1	f2	f3		f4 f5		f6 f7		f8 f9		f10	f11	f12	f13	f14	f15
f0(1, 2)		?0				0	0	0			0	0 0			0	0	0	0	1	1	1	1	1	1	1	1
2		?0				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
						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
2) f1 = 1 2.
						1	1	0			1	0 1			0	1	0	1	0	1	0	1	0	1	0	1

f1(1, 2)	= f			, 0 f						, 1 =				0 = 0
	= f		1	, 0 f					1	, 1 =				0 = 0
2			1		1				1	1						? 1
2

Пример 7.12.		x1	x2	f0	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15
Пример 7.12.		0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
		0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1

3) f2	= 1 2.	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	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

f2(1, 2)		= f		, 0 f			, 1 =			0 = 0
		= f	2	, 0 f		2	, 1 =			0 = 0
2			2		1	2	1			1 ?
2
4) f3	= 1.	f3(1, 2)				= f			, 0 f			, 1 =	=
						= f		3	, 0 f		3	, 1 =	=
		2						3	1		3	1	1 ? 1	1
		2
5) f4	= 1 2.	f4(1, 2)				= f			, 0 f			, 1 =	0 = 0
						= f		4	, 0 f		4	, 1 =	0 = 0
		2						4	1		4	1	? 1
		2

Пример 7.12.			x1	x2	f0	f1			f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15
Пример 7.12.			0	0	0	0			0	0	0	0	0	0	1	1	1	1	1	1	1	1
			0	0	0	0			0	0	0	0	0	0	1	1	1	1	1	1	1	1

6) f5 =	2.		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	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
f5(1, 2)
f5(1, 2)
2	= f5 1, 0 f5 1, 1 = 0 ?1 = 0
2
		f6(1, 2)						= f6 1, 0 f6 1, 1 =
7) f6 = 1 2 1 2 .			2					= f6 1, 0 f6 1, 1 =
7) f6 = 1 2 1 2 .			2										?	0) (0 1) = 0
													?
											= ( 1
	f7(1, 2)				= f				, 0 f				, 1 = ( 0) ( 1) =
8) f7 = 1	2 .				= f				, 0 f			7	, 1 = ( 0) ( 1) =
8) f7 = 1	2 .	2					7	1				7	1			1?			1			1
		2

Пример 7.12.		x1	x2	f0	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15
Пример 7.12.		0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
		0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1

9) f8 = 1	2.	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	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

f8(1, 2)	= f8	1, 0 f8	1, 1 =	?
	= f8	1, 0 f8	1, 1 =	( 1) ( 0) = 0
2				1	1
2
	f9(1, 2)		= f9 1, 0 f9 1, 1 =
10) f9 = 1 2 1 2.		2	= f9 1, 0 f9 1, 1 =
10) f9 = 1 2 1 2.		2		= (0? 1) ( 1 0) = 0
				= (0? 1) ( 1 0) = 0
	f10(1, 2)				= 1? 0 = 0
11) f10 = 2.	2	=	f10 1, 0	f10 1, 1	= 1? 0 = 0
	2

Пример 7.12.				x1		x2	f0	f1		f2		f3	f4	f5	f6		f7	f8	f9	f10		f11	f12	f13	f14	f15
Пример 7.12.				0		0	0	0		0		0	0	0	0		0	1	1	1		1	1	1	1	1
				0		0	0	0		0		0	0	0	0		0	1	1	1		1	1	1	1	1

12) f11 = 1 2.				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		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
f11(1, 2)
f11(1, 2)	=	f		, 0 f						, 1 =				( 1) ( 0) =
	=	f	11	, 0 f					11	, 1 =				( 1) ( 0) =
2			11		1				11	1					1	?			1				1
2
	f12(1, 2)								= f				1, 0 f					1, 1 =			=
13) f12 = 1.			2						= f				1, 0 f					1, 1 =			=
13) f12 = 1.			2								12					12					?		1		1
											12					12					1		1		1

14) f		=	.	f13(1, 2)	= f13 1, 0	f13 1, 1	= ( 1	0) ( 1 1) =
	13
		1	2	2			?
								= 1

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

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

#
23.06.20231.26 Mб18lec02.pdf
#
23.06.20231.39 Mб12lec03.pdf
#
23.06.20231.23 Mб11lec04.pdf
#
23.06.20231.39 Mб11lec05.pdf
#
23.06.20231.38 Mб10lec06.pdf
#
23.06.20231.47 Mб26lec07 производная булевой функции.pdf
#
23.06.20231.16 Mб10lec07_1.pdf
#
23.06.20231.25 Mб11lec08.pdf
#
23.06.20231.14 Mб11lec09_1.pdf
#
23.06.20231.3 Mб10lec09_2.pdf
#
23.06.20231.02 Mб13lec10.pdf