Лекция дискрет 07
.pdf
Пример 3: множества и векторы
Если │M│ = n, то алгебра множеств [ B (M); , , ]
изоморфна алгебре двоичных векторов [ Bn; , &, ¬ ]
Строим соответствие Г: B (M) Bn, для чего произвольному
подмножеству множества М = { m1,m2,...,mn } сопоставляем двоичный вектор длины n по следующему правилу:
M |
jk |
= { |
m1 |
m2 m3 m4 m5 |
m6 |
m7 |
m8 ......... mn-1 |
mn |
|
|
|
|
|
|
|
|
|
|
|
σj |
= ( |
0 |
1 0 1 1 |
0 |
1 |
1 ......... 0 |
1 |
) |
|
|
k |
|
|
|
|
|
|
|
|
Доказываем взаимную однозначность построенного соответствия и проверяем условие гомоморфности
Г ( φi ( Mj1, Mj2, … , Mjli ) ) = ψi ( Г(Mj1), Г(Mj2), … , Г(Mjli) ) при i = 1…3, l1 = 2, l2 = 2, l3 = 1 для любых Mjk M [Mjk B (M)]
Проверяем условие гомоморфности
Г ( φi ( Mj1, Mj2, … , Mjli ) ) = ψi ( Г(Mj1), Г(Mj2), … , Г(Mjli) )
при i = 1…3, l1 = 2, l2 = 2, l3 = 1 для любых Mjk B (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); , , |
|
] |
Алгебра [ Bn; , &, ¬ ] |
||||||
|
|||||||||
|
φ1 |
M1 M2 |
ψ1 |
σ τ |
|
||||
|
φ2 |
M1 M2 |
ψ2 |
σ & τ |
|||||
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|||
|
φ3 |
|
M1 |
ψ3 |
¬σ |
||||
Γ(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 |
|
|
|
|
|
1, если mi M1 или mi M2 0, если mi M1 и mi M2
εi = σi τi ε = σ τ
Γ(M1 M2)=Γ(M1) Γ(M2)
Аналогично j=2 и j=3
Пример 4: матрицы и определители
A = [ {Mn} ; ] |
B = [ R; ] |
|
|
{Mn} – множество квадратных матриц n-го порядка |
|
|
|
- операция матричного умножения |
|
||
Г: {M } R задано функцией |
Г(M ) = det ( M |
) |
|
n |
n |
n |
|
φ (Mn , Mn ) = Mn Mn |
ψ (d , d ) = d |
d |
|
|
det (Mn Mn ) = det (Mn ) det (Mn ) |
|
||||||||
|
|
|
|
|
|
|||||
M = 1 |
2 M |
= 5 6 M |
M = 19 22 |
|||||||
2 |
3 |
4 |
2 |
7 |
8 |
2 |
2 |
43 |
50 |
|
|
|
|
|
|
||||||
det (M2 ) = -2 |
|
|
|
|
|
|
|
|||
|
|
|
|
|
det (M2 M2 ) = 4 |
|
|
|||
det (M2 ) = -2 |
|
det (M2 ) det (M2 ) = 4 |
|
|||||||
соответствие – не взаимно однозначное, значит только гомоморфизм
Нет инъективности,
например,
det (M2 ) = det (M2 )
Th.2.1.1 Заданы две алгебры одинакового типа (l1, l2, … , lp)
A = [ K; φ1, φ2, … , φp ] |
B = [ M; ψ1, ψ2, … , ψp ] |
Если Г: К М – изоморфизм алгебры А на алгебру В, то существует обратный изоморфизм Г -1: М К алгебры В на алгебру А
Доказательство Th.2.1.1
Согласно Th.1.2.1: так как Г: К М – изоморфизм, т.е. взаимно однозначное соответствие, то существует обратное отображение Г -1: М К и оно – взаимно однозначно. Докажем, что это отображение удовлетворяет условию гомоморфности ( )
Г ( φi ( kj1, kj2, … , kjli ) ) = ψi ( Г(kj1), Г(kj2), … , Г(kjli) ) ( )
для всех i = 1…p |
для любых kj |
r |
K |
|
|
|
kj Κ |
|
Γ(kj) = mj, mj M |
kj = Γ-1(mj) |
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
подстановка в ( ) |
|
|
|
|
|
|
|
|
|||||||
Г ( φi ( kj , kj , … , kj |
|
) ) = ψi ( Г(kj |
|
), Г(kj ), … , Г(kj ) ) ( ) |
|||||||||||||||||||
1 |
2 |
|
|
|
li |
|
|
|
1 |
|
2 |
|
|
|
|
|
li |
|
|
|
|||
Γ (φ (Γ -1(m |
j |
), … , Γ -1(m |
j |
|
))) = ψ |
(m |
j |
|
, … , m |
j |
) |
|
|||||||||||
|
i |
|
|
|
|
|
|
|
li |
i |
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
1 |
|
|
li |
|
||||
Применяем Γ -1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
φ (Γ |
-1(m |
j |
|
), … , Γ -1(m |
j |
)) = Γ -1 (ψ |
(m |
j |
, … , m |
j |
)) |
||||||||||||
|
i |
|
|
|
|
|
|
li |
|
|
|
|
i |
|
|
|
|
|
|||||
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
li |
|
|
Сравнение с условием гомоморфности ( ) |
|
|
|
|
|
|
|||||||||||||||||
Г ( φi ( kj |
, kj |
, … , kj |
li |
) ) = ψi ( Г(kj |
|
), Г(kj |
), … , Г(kj ) ) ( ) |
||||||||||||||||
1 |
2 |
|
|
|
|
|
|
|
|
|
1 |
2 |
|
|
|
|
li |
|
|
|
|||
показывает, что Г-1: М К – гомоморфизм, а, в силу ранее доказанной взаимно однозначности - изоморфизм
Доказано Th.2.1.1
Пример 1: логарифм и экспонента
Для алгебр A = [ R+; ] и B = [ R; + ] был построен изоморфизм Г: R+ R, заданный функцией y = ln ( x )
Условие гомоморфности имеет вид
ln ( x1 x2 ) = ln ( x1 ) + ln ( x2 )
Согласно Th.2.1.1 существует обратный изоморфизм Г-1: R R+, определяемый функцией x = ey
с условием гомоморфности ex1+x2 = ex1 ex2
Пример 2: множества |
|
|
|
|
|
|
|||||||||
A = [ B (M); ] |
B = [ B (M); ] |
||||||||||||||
|
|
|
|||||||||||||
-1 (L) = L для любого L B (M) (т.е. L M) |
|||||||||||||||
Проверим условие гомоморфности ( ) |
|
|
|
|
|||||||||||
Г -1 ( φ ( k |
j |
|
, k |
j |
|
, … , k |
j |
) ) = ψ |
( Г -1(k |
j |
), … , Г -1(k |
j |
|
) ) ( ) |
|
i |
|
|
|
|
|
i |
|
|
li |
||||||
|
|
1 |
|
|
|
2 |
|
|
li |
|
1 |
|
|
||
для всех i = 1…p |
|
для любых kj |
|
K |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
r |
|
|
В примере: p = 1 |
|
1 есть , 1 есть |
|||||||||||||
-1 (M1 M2) = M1 M2 = M1 M2 = -1 (M1) -1 (M2)
-1 (L) = L – взаимно однозначное соответствие, значит
алгебра В изоморфна алгебре А
Пример 3: множества и векторы
Построили изоморфизм Г: B (M) Bn: произвольному подмножеству
множества М = { m1,m2,...,mn } ставится в соответствие двоичный вектор длины n по следующему правилу:
Mjk = { m1 m2 m3 m4 m5 m6 m7 m8 …… mn-1 mn }
σj |
k |
= ( 0 |
1 0 1 1 0 1 1 …… 0 |
1 |
) |
|
|
|
|
|
|
Обратный изоморфизм Г-1: B B (M): двоичный вектор длины n |
|
||||
|
|
|
n |
|
|
определяет подмножество множества М = { m1,m2,...,mn } |
|
|
|||
σj |
k |
= ( 0 |
1 0 1 1 0 1 1 …… 0 |
1 |
) |
|
|
|
|
|
|
Mjk = { m1 m2 m3 m4 m5 m6 m7 m8 …… mn-1 mn }
Пример 4: матрицы и определители
Для алгебр A = [ Mn; ] и B = [ R; ] был построен
гомоморфизм Г: {Mn} R, заданный функцией
Г(Mn ) = det ( Mn ) с условием гомоморфности
det (Mn Mn ) = det (Mn ) det (Mn )
Данный гомоморфизм не является взаимно однозначным соответствием (не выполнено требование инъективности), значит, он не является изоморфизмом.
Согласно Th.2.1.1, обратное соответствие Г-1: R {Mn} не является изоморфизмом