1_Algebra_logiki

Нормальные формы

Разложение булевой функции по подмножеству переменных

Разложение булевой функции по подмножеству переменных

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

( 1; : : : ; n) произвольный набор значений переменных

(x1; : : : ; xn)

Николаева Екатерина Александровна (ТГУ)

Алгебра логики

16 / 50

Нормальные формы

Разложение булевой функции по подмножеству переменных

Разложение булевой функции по подмножеству переменных

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

( 1; : : : ; n) произвольный набор значений переменных

(x1; : : : ; xn)

f( 1; : : : ; n)

Николаева Екатерина Александровна (ТГУ)

Алгебра логики

16 / 50

Нормальные формы

Разложение булевой функции по подмножеству переменных

Разложение булевой функции по подмножеству переменных

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

( 1; : : : ; n) произвольный набор значений переменных

(x1; : : : ; xn)

	( 1	W m	1	m
			1	m f( 1; : : : ; m; m+1; : : : ; n):
	f( 1; : : : ; n)=
		;:::;	)

Николаева Екатерина Александровна (ТГУ)

Алгебра логики

16 / 50

Нормальные формы

Разложение булевой функции по подмножеству переменных

Разложение булевой функции по подмножеству переменных

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

( 1; : : : ; n) произвольный набор значений переменных

(x1; : : : ; xn)

	iW		1	m
			1	m f( 1; : : : ; m; m+1; : : : ; n):
	f( 1; : : : ; n)=
	( 1;:::; m)
	Åñëè i 6= i, òî i	= 0

Николаева Екатерина Александровна (ТГУ)

Алгебра логики

16 / 50

Нормальные формы

Разложение булевой функции по подмножеству переменных

Разложение булевой функции по подмножеству переменных

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

( 1; : : : ; n) произвольный набор значений переменных

(x1; : : : ; xn)

		iW	1	m
	f( 1; : : : ; n)=		1	m f( 1; : : : ; m; m+1; : : : ; n):
		( 1;:::; m)

Åñëè i 6= i, òî i = 0 Åñëè i = i, òî i i = 1

Николаева Екатерина Александровна (ТГУ)

Алгебра логики

16 / 50

Нормальные формы

Разложение булевой функции по подмножеству переменных

Разложение булевой функции по подмножеству переменных

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

( 1; : : : ; n) произвольный набор значений переменных

(x1; : : : ; xn)

		iW	1	m
	f( 1; : : : ; n)=		1	m f( 1; : : : ; m; m+1; : : : ; n):

( 1;:::; m)

Åñëè i 6= i, òî i = 0 Åñëè i = i, òî i i = 1

_

11 mm f( 1; : : : ; m; m+1; : : : ; n)

( 1;:::; m)

Николаева Екатерина Александровна (ТГУ)

Алгебра логики

16 / 50

Нормальные формы

Разложение булевой функции по подмножеству переменных

Разложение булевой функции по подмножеству переменных

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

( 1; : : : ; n) произвольный набор значений переменных

(x1; : : : ; xn)

		iW	1	m
	f( 1; : : : ; n)=		1	m f( 1; : : : ; m; m+1; : : : ; n):

( 1;:::; m)

Åñëè i 6= i, òî i = 0 Åñëè i = i, òî i i = 1

_

11 mm f( 1; : : : ; m; m+1; : : : ; n) =

( 1;:::; m)

1 1 mm f( 1; : : : ; m; m+1; : : : ; n)

Николаева Екатерина Александровна (ТГУ)

Алгебра логики

16 / 50

Нормальные формы

Разложение булевой функции по подмножеству переменных

Разложение булевой функции по подмножеству переменных

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

( 1; : : : ; n) произвольный набор значений переменных

(x1; : : : ; xn)

		iW	1	m
	f( 1; : : : ; n)=		1	m f( 1; : : : ; m; m+1; : : : ; n):
		( 1;:::; m)

Åñëè i		6= i, òî i = 0
Åñëè i		= i, òî i = 1
	_ m							i
( 1			11		mm f( 1; : : : ; m; m+1; : : : ; n) =
	;:::;		)
	1 1 mm f( 1; : : : ; m; m+1; : : : ; n)
	|			{z			}
		i			8
			i	1
	ò.ê.			= 1;		i=1;n

Николаева Екатерина Александровна (ТГУ)

Алгебра логики

16 / 50

Нормальные формы

Разложение булевой функции по подмножеству переменных

Разложение булевой функции по подмножеству переменных

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

( 1; : : : ; n) произвольный набор значений переменных

(x1; : : : ; xn)

		iW	1	m
	f( 1; : : : ; n)=		1	m f( 1; : : : ; m; m+1; : : : ; n):
		( 1;:::; m)

Åñëè i		6= i, òî i = 0
Åñëè i		= i, òî i = 1
	_ m							i
( 1			11		mm f( 1; : : : ; m; m+1; : : : ; n) =
	;:::;		)
	1 1 mm f( 1; : : : ; m; m+1; : : : ; n) = f( 1; : : : ; n)
	|			{z			}
		i			8
			i	1
	ò.ê.			= 1;		i=1;n

Николаева Екатерина Александровна (ТГУ)

Алгебра логики

16 / 50

Нормальные формы Cовершенные ДНФ и КНФ

Разложение Шеннона и

Cовершенная дизъюнктивная нормальная форма

Николаева Екатерина Александровна (ТГУ)

Алгебра логики

17 / 50