1_Algebra_logiki

							Нормальные формы			Cовершенные ДНФ и КНФ
Построение совершенных ДНФ и КНФ
ÄÍÔ		W n
f(~xn) =					x11 xnn
f( 1
( 1		;:::; n)
	;:::; )=1
			x1 x2 x3				f(x1; x2; x3)
			0	0	0		0
			0 0 1			1				x10x20x31 =		1		2x3
											x		x
			0	1	0		0
			0 1 1			1				x10x21x31 =		1x2x3
											x
			1	0	0		0
			1 0 1			1				x11x20x31 = x1				2x3
													x
			1 1 0				1			x11x20x31 = x1				2x3
													x
		1 1 1				1				x11x21x31 = x1x2x3

f(~x3) = x1x2x3 _ x1x2x3 _ x1x2x3 _ x1x2x3 _ x1x2x3

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

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

20 / 50

						Нормальные формы				Cовершенные ДНФ и КНФ
Построение совершенных ДНФ и КНФ
ÄÍÔ									ÊÍÔ
f(~xn) =				x11 xnn
										f(~xn) =			(x11						xnn )
f( 1	W n									f( 1;:::; n)=0
( 1;:::; n)										V							_ _
										( 1;:::; n)
	;:::; )=1
		x1 x2 x3				f(x1; x2; x3)
		0 0 0				0			x11 _ x21 _ x31 = x1 _ x2 _ x3
	0		0	1	1
		0 1 0				0			x11 _ x20 _ x31 = x1 _						2 _ x3
														x
	0		1	1	1
		1 0 0				0			x10 _ x21 _ x31 =			1 _ x2 _ x3
											x
	1		0	1	1
		1	1	0		1
		1	1	1	1

f(~x3) = x1x2x3 _ x1x2x3 _ x1x2x3 _ x1x2x3 _ x1x2x3

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

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

20 / 50

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

Построение совершенных ДНФ и КНФ

ÄÍÔ
f(~xn) = W	x11 xnn

( 1;:::; n) f( 1;:::; n)=1

ÊÍÔ

f(~xn) =		(x11 _ _ xnn )
f( 1		V n
( 1	;:::; n)

;:::; )=0

			x1 x2 x3								f(x1; x2; x3)
				0 0 0							0				x11 _ x21 _ x31 = x1 _ x2 _ x3
0						0		1		1
			0 1 0								0				x11 _ x20 _ x31 = x1 _						2 _ x3
																				x
0						1		1		1
			1 0 0								0				x10 _ x21 _ x31 =				1 _ x2 _ x3
																		x
1						0		1		1
			1			1		0			1
			1			1		1		1
f(~x3) =					1			2x3 _					1x2x3 _ f(~x3) = (x1 _ x2 _ x3)
				x		x						x
x1		2x3 _ x1x2							3 _ x1x2x3						(x1 _		2 _ x3) (						1 _ x2 _ x3)
	x						x									x						x

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

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

20 / 50

Полиномы

Полином Жегалкина

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

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

21 / 50

Полиномы

Полином Жегалкина

Полином Жегалкина

L

Формула ai1;:::;im(xi1 : : : xim) называется полиномом

(i1;:::;im)

Жегалкина булевой функции, коэффициенты ai1;:::;im 2 f0; 1g определяют, какие конъюнкции входят в полином.

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

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

21 / 50

Полиномы

Полином Жегалкина

Полином Жегалкина

L

Формула ai1;:::;im(xi1 : : : xim) называется полиномом

(i1;:::;im)

Жегалкина булевой функции, коэффициенты ai1;:::;im 2 f0; 1g определяют, какие конъюнкции входят в полином.

1

_

x

2

= x

1

2

1

2

x1 xn =

(x1;

n - нечетно.

x

x

x x

0;

n - четно,

x1(x2 x3) = x1x2 x1x3

x1

1 = x1

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

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

21 / 50

Полиномы

Полином Жегалкина

Полином Жегалкина

L

Формула ai1;:::;im(xi1 : : : xim) называется полиномом

(i1;:::;im)

Жегалкина булевой функции, коэффициенты ai1;:::;im 2 f0; 1g определяют, какие конъюнкции входят в полином.

1 _	x	2	= x	1		2	1	2	x1 xn =	(x1;	n - нечетно.
x					x		x x			0;	n - четно,

x1(x2 x3) = x1x2 x1x3

x1 1 = x1

Пример

f = x1x2 _ x1x3 _x2x3

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

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

21 / 50

Полиномы

Полином Жегалкина

Полином Жегалкина

L

Формула ai1;:::;im(xi1 : : : xim) называется полиномом

(i1;:::;im)

Жегалкина булевой функции, коэффициенты ai1;:::;im 2 f0; 1g определяют, какие конъюнкции входят в полином.

1 _	x	2	= x	1		2	1	2	x1 xn =	(x1;	n - нечетно.
x					x		x x			0;	n - четно,

x1(x2 x3) = x1x2 x1x3

x1 1 = x1

Пример

f = x1x2 _ x1x3 _x2x3

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

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

21 / 50

Полиномы

Полином Жегалкина

Полином Жегалкина

L

Формула ai1;:::;im(xi1 : : : xim) называется полиномом

(i1;:::;im)

Жегалкина булевой функции, коэффициенты ai1;:::;im 2 f0; 1g определяют, какие конъюнкции входят в полином.

1

_

x

2

= x

1

2

1

2

x1 xn =

(x1;

n - нечетно.

x

x

x x

0;

n - четно,

x1(x2 x3) = x1x2 x1x3

x1

1 = x1

Пример

f = x1x2 _ x1x3 _x2x3 = (x1x2 x1x3 x1x2x3) _x2x3

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

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

21 / 50

Полиномы

Полином Жегалкина

Полином Жегалкина

L

Формула ai1;:::;im(xi1 : : : xim) называется полиномом

(i1;:::;im)

Жегалкина булевой функции, коэффициенты ai1;:::;im 2 f0; 1g определяют, какие конъюнкции входят в полином.

1

_

x

2

= x

1

2

1

2

x1 xn =

(x1;

n - нечетно.

x

x

x x

0;

n - четно,

x1(x2 x3) = x1x2 x1x3

x1

1 = x1

Пример

f = x1x2 _ x1x3 _x2x3 = (x1x2 x1x3 x1x2x3) _x2x3

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

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

21 / 50