Лекция дискрет 11

Th.3.2.2 Если │M│ = n, то булева алгебра [ B (M); , , ]

изоморфна булевой алгебре [ Bn; , &, ¬ ]

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

Строим соответствие Г: B (M) Bn, для чего произвольному

подмножеству множества М = { m1,m2,...,mn } сопоставляем двоичный вектор длины n по следующему правилу:

Mjk =

σjk =

{ m1 m2 m3 m4 m5 m6 m7 m8 .........									mn-1 mn
(	0	1	0	1	1	0	1	1 .........	0	1 )

Доказываем взаимную однозначность построенного соответствия и проверяем условие гомоморфности

Г ( φi ( Mj1, Mj2, … , Mjli ) ) = ψi ( Г(Mj1), Г(Mj2), … , Г(Mjli) )

при i = 1…3, l1 = 2, l2 = 2, l3 = 1 для любых Mjk M

Проверяем условие гомоморфности

Г ( φi ( Mj1, Mj2, … , Mjli ) ) = ψi ( Г(Mj1), Г(Mj2), … , Г(Mjli) )

при i = 1…3, l1 = 2, l2 = 2, l3 = 1 для любых Mjk M Для алгебр

[ B (M); , ,							[ Bn; , &, ¬ ]
					]
φ1	M M					2	ψ	1	σ τ
	1
φ2	M		M			2	ψ	2	σ & τ
	1
φ3									σ
		M		1			ψ	3

условие гомоморфности имеет следующий вид:

Γ(M1 M2) = Γ(M1) Г(M2) докажем Γ(M1 M2) = Γ(M1) & Г(M2)

Γ(M1) = ¬Γ(M1)

Рассматриваются алгебры:

Алгебра [ B (M); , ,						]
	φ1	M1 M2
	φ2	M1 M2
	φ3		M1

Γ(M1 M2) = ε = (ε1,ε2,…,εn) =
				i
mi M1
	σi =1	σi	τi	εi
mi M2
	τi =1	0	0	0
mi M1
	σi =0	0	1	1
mi M2
	τi =0	1	0	1
		1	1	1

Алгебра [ Bn; , &, ¬ ]

ψ1	σ τ
ψ2	σ & τ
ψ3		σ
1, если mi M1		или mi M2
0, если mi M1		и mi M2

εi = σi τi ε = σ τ

Γ(M1 M2)=Γ(M1) Γ(M2)

Аналогично j=2 и j=3

Доказано Th.3.2.2

					Пример								M	=	{	a,	b,	c,	d		}
			Алгебра [B (M); ,									] изоморфна алгебре [B4; , &, ¬ ]
										,
B (M)								b					a				a	b
B4		0		0	0	0	0	1	0			0	1	0	0	0	1	1	0		0
						d		b				d	a			d	a	b			d
		0		0	0	1	0	1	0			1	1	0	0	1	1	1	0		1
					c			b		c			a		c		a	b	c
		0		0	1	0	0	1	1			0	1	0	1	0	1	1	1		0
					c	d		b		c		d	a		c	d	a	b	c	d
		0		0	1	1	0	1	1			1	1	0	1	1	1	1	1		1

Th.3.2.3 Если │M│ = 2m, то булева алгебра [ B (M); , , ]

изоморфна булевой алгебре [ P2(m) ; , &, ¬ ]

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

1) Применяя Th.3.2.2, строим алгебру [ B2m; , &, ¬ ], изоморфную алгебре [ B (M); , , ]

2)Строим соответствие Г: B2m P2(m) , для чего всякому двоичному вектору σi длины 2m сопоставляем логическую функцию m переменных, вектор значений которой совпадает

с вектором σi. Доказываем, что построенное соответствие является изоморфизмом.

3)Изоморфизм – отношение эквивалентности на множестве

алгебр (§ 2.1) пользуясь его транзитивностью, получаем

изоморфизм алгебр [ B (M); , ,

] и [ P2(m) ; , &, ¬ ]

Доказано Th.3.2.3

					Пример								M	=		{	a,	b,	c,		d	}
		Алгебра [B (M); , ,									] изоморфна алгебре [P2(2); , &, ¬ ]
B (M)								b					a					a	b
B4		0	0		0	0	0	1		0		0	1	0		0	0	1	1		0	0
Р2(2)				ψ0				ψ4						ψ8					ψ12
						d		b				d	a				d	a	b			d
		0	0		0	1	0	1		0		1	1	0		0	1	1	1		0	1
				ψ1				ψ5						ψ9					ψ13
					c			b		c			a			c		a	b		c
		0	0		1	0	0	1		1		0	1	0		1	0	1	1		1	0
				ψ2				ψ6						ψ10					ψ14
					c	d		b	c			d	a			c	d	a	b	c		d
		0	0		1	1	0	1		1		1	1	0		1	1	1	1		1	1
				ψ3				ψ7						ψ11					ψ15

Булева алгебра

Булева
алгебра
множеств	Булева	Булева
[B(M); , , ]	алгебра	алгебра
	логических	логических
	функций	функций
	[ P ; , &, ¬ ]	[P2(n); , &, ¬]
	2

подалгебра

Булева

алгебра

векторов

[Bn; , &, ¬ ]

изоморфные алгебры

4) Функционально полные системы логических функций

	Из § 3.1:		Логическая формула глубины k над множеством
			логических функций Σ = { f1, f2, … , fm, … }:

1. Символы переменных x1, x2, … , xn, … - логические формулы глубины 0 над множеством логических функций Σ.

2. Пусть F1, F2, … , Fni – логические формулы глубины не более k над множеством логических функций Σ, причём хотя бы одна из них имеет глубину ровно k. Пусть также

fi ( x1, x2, … , xni ) Σ – логическая функция.

Тогда fi ( F1, F2, … , Fni ) – логическая формула глубины (k+1) над множеством логических функций Σ.

3. Других логических формул над множеством логических функций Σ нет.

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

Σ0 = { , &, - функционально полная (Th.3.2.1) Th.3.2.4

Заданы две системы логических функций:

Σ* = { f1, f2, …

Σ = { g1, g2, …

Система Σ* - функционально полная и любая логическая функция из Σ* может быть реализована формулой над Σ.

Тогда система Σ – функционально полная

«исследуемая»	«эталонная» полная	произвольная
система функций	система функций *	логическая функция
g1
g2	f1

……………

g1

g2 f2 h

……………

g1

g2 ……………

……………