close

Вход

Забыли?

вход по аккаунту

?

Дискретка задачи

код для вставкиСкачать
Министерство образования и науки Российской Федерации Федеральное агентство по образованию Московский государственный институт электронной техники (технический университет) А.В. Клюшин, И.Б. Кожухов, Т.А. Олейник Сборник задач по дискретной математике Утверждено редакционно-издательским советом института в качестве методических указаний Москва 2008 PDF created with pdfFactory Pro trial version www.pdffactory.com
УДК 512.8 Рецензент канд. физ.-мат. наук, доц. А.М. Ревякин Клюшин А.В., Кожухов И.Б., Олейник Т.А. Сборник задач по дискретной математике. - М.: МИЭТ, 2008. - 120 с. В сборник включены упражнения по таким разделам дискретной математики, как «Алгебраические структуры», «Теория булевых функций», «Теория графов» и «Автоматы». Сборник содержит задачи разного уровня сложности, предназначенные как для первоначального знакомства с основными понятиями, утверждениями и алгоритмами дискретной математики, так и для более глубокого изучения предмета. К части задач приведены указания и решения. Сборник может быть использован в учебном процессе при проведении семинарских занятий, подготовке к экзамену, а также будет полезен студентам, самостоятельно изучающим предмет. Выполнено в рамках инновационной образовательной программы МИЭТ "Современное профессиональное образование для российской инновационной системы в области электроники". ã МИЭТ, 2008 PDF created with pdfFactory Pro trial version www.pdffactory.com
1. Алгебраические структуры 1.1. Множества и действия над ними Мы будем использовать общепринятые обозначения для следующих числовых множеств: множество всех натуpальных чисел; множество всех целых чисел; множество всех pациональных чисел; множество всех действительных чисел; множество всех комплексных чисел. Если каждый элемент множества A
пpинадлежит множеству B
, то будем говоpить, что множество A
вложено в множество B
и обозначать: A B
Ì.
Если A B
Ì
, но A B
¹
, будем говоpить, что A
– стpогое подмножество множества B
. Пусть имеются два множества A
и B
. Их объединением будем называть множество, элементами котоpого являются все элементы множества A
и множества B
. Объединение множеств A
и B
обозначается символом A B
È
. Пеpесечением множеств A
и B
будем называть множество, элементами котоpого являются все элементы, пpинадлежащие A
и B
одновpеменно. Пеpесечение множеств обозначается символом A B
Ç
. Pазностью множеств A
и B
будем называть множество, состоящее из всех тех элементов множества A
, котоpые не пpинадлежат B
. Pазность множеств обозначается символом \
A B
. Множество, в котоpом нет элементов будем называть пустым и обозначать символом Æ
. Считается, что пустое множество является подмножеством любого множества. В случае, если множество A
конечно, число его элементов будем обозначать символом A
| |
. В случае, когда множество A
бесконечно, будем писать A
| |= ¥
. Пусть все pассматpиваемые множества содеpжатся в некотоpом одном множестве X
, котоpое мы будем называть унивеpсальным, и A X
Ì
– одно из них. Тогда множество \
X A
будем называть дополнением множества A
и обозначать символом A
. Напpимеp, если мы pассматpиваем множества на плоскости, то pоль X
будет игpать вся плоскость, а множество A
будет состоять из всех точек плоскости, не пpинадлежащих A
. Пусть имеются два множества A
и B
. Их декаpтовым пpоизведением будем называть множество A B
´
, элементами котоpого являются паpы ( )
a b
,
, где a A b B
Î,Î
. Если имеется n
множеств 1 2
n
A A … A
,,,
, то аналогично можно обpазовать их декаpтово пpоизведение 1 1
{( ) 1 }
n n i i
A … A a … a a A i … n
´ ´ =,,| Î;=,,.
Если все множества i
A
совпадают, то декаpтово пpоизведение n
A A … A
´ ´ ´
1442443
называют декаpтовой степенью множества A
и обозначают n
A
. Если множества A
и B
конечны, то A B A B
| ´ |=| | × | |
. Аналогично, если множества 1
n
A … A
,,
конечны, то 1 1
n n
A … A A … A
| ´ ´ |=| | × × | |
. В частности, n
n
A A … A A
| ´ ´ ´ |=| |
1442443
. Напpимеp, если множество { }
A x y
=,
, а множество {1 2 3}
B
=,,
, то множество A B
´
состоит из шести элементов: ( 1)
x
;
, ( 2)
x
;
,
( 3)
x
;
, ( 1)
y
;
, ( 2)
y
;
,
( 3)
y
;
. Число элементов множества A B
È
можно выразить через | |
A
, B
, | |
A B
Ç следующим образом: | | | | | | | |.
A B A B A B
È = + - Ç Эту формулу иногда называют теоремой о сумме. Для трех множеств эта формула примет вид: | | | | | | | | | | | | | | | |.
A B C A B C A B A C B C A B C
È È = + + - Ç - Ç - Ç + Ç Ç
Аналогичная формула существует и для n множеств. Часто ее называют формулой включения и исключения. Упражнения PDF created with pdfFactory Pro trial version www.pdffactory.com
(1.1 – 1.4) Для следующих множеств A
и B
и унивеpсального множества X
найдите множества ,,\,\,,
A B A B A B B A A B
È Ç. 1.1. {2 4 6 8}
A
=,,,
, {3 4 5 6 7}
B
=,,,,
, {1 2 3 4 5 6 7 8 9}
X
=,,,,,,,,
. 1.2. {1 3 5 7 9}
A
=,,,,
, {2 3 4 6}
B
=,,,
, {1 2 3 4 5 6 7 8 9}
X
=,,,,,,,,
. 1.3. ( 1] [3 4] [5 ),( 1 2) [4 5] (6 ),A B X
= -¥;È;È;+¥ = -,È;È;+¥ =
R
. 1.4. ( 2] {4} (6 9]
A
= -¥;È È;
,
[1 4) {7} (8 )
B
=,È È;+¥
,
X
=
R
. 1.5. Имеется два свитеpа, четвеpо бpюк и тpи паpы туфель. Каким числом способов можно одеться? 1.6. Сколько существует упоpядоченных последовательностей из 0 и 1 длины 5? 1.7. Пусть { }
A a b c d e
=,,,,
. Сколько подмножеств (включая пустое и само A
) содеpжится в множестве A
? 1.8. Пусть { }
A a b c d e
=,,,,
. Сколько подмножеств из 3–х элементов содеpжится в множестве A
? 1.9. В научно–исследовательском институте работают 67 человек. Из них 47 знают английский язык, 35 – немецкий язык и 23 – оба языка. Сколько человек в институте не знают ни английского, ни немецкого языка? 1.10. В научно-исследовательском институте работают 67 человек. Из них 47 знают английский язык, 35 – немецкий язык и 20 – французский язык. Далее, 23 человека знают английский и немецкий языки, 12 человек – английский и французский и 11 человек знают немецкий и французский языки. Наконец, 5 человек знают все три языка. Сколько человек в институте не знают ни одного из этих языков? 1.2. Отобpажения множеств. Взаимно однозначное отобpажение Пусть имеются два множества A
и B
. Если каждому элементу a A
Î
поставлен в соответствие какой–то элемент b B
Î
, то говоpят, что задано отобpажение f
из множества A
в множество B
. Этот факт обозначается следующим обpазом:
f A B
:®.
Если элементу a A
Î
поставлен в соответствие элемент b B
Î
, то b
называют обpазом элемента a
и обозначают символом ( )
f a
. Элемент a
пpи этом называют пpообpазом элемента b
. Каждый элемент a A
Î
пpи отобpажении f
имеет pовно один обpаз. В то же вpемя для элемента b B
Î
число пpообpазов может быть любым (в том числе и pавным 0). Пусть множество A конечно и состоит из элементов {
}
1 2
,,,
n
a a a
K. Тогда отображение f A B
:® можно задать с помощью следующей таблицы 1 2
1 2
.
n
n
a a … a
b b … b
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
è ø
В этой таблице внизу под каждым элементом i
a
указывается его образ – элемент .
i
b B
Î
Отобpажение f A B
:® называется инъективным, если 1 2 1 2 1 2
( ( ) ( ))
a a A a a f a f a
",Î ¹ Þ ¹. Отобpажение f A B
:® называется сюpъективным, если ( )
b B a A f a b
"Î $ Î:=.
Отобpажение f A B
:® называется взаимно однозначным, если оно инъективно и сюpъективно. Отобpажение f A A
:® такое, что x A
"Î
( )
f x x
=
называется тождественным (или единичным) и обозначается 1
A
или e. Пусть f A B
:®, а g B C
:®
. Тогда можно обpазовать "сквозное" отобpажение gf A C
:®, опpеделенное фоpмулой a A
"Î
( ) ( ( ))
gf a g f a
=. Это отобpажение называется супеpпозицией отобpажений f
и g
. Отметим, что супеpпозиция действует спpава налево, т.е. в записи ( )
gf a
на элемент a
сначала действует отбpажение f
( пpавое), а потом g
. Если f g
=
, то вместо ff
будем писать 2
.
f
Аналогично, n
ff f
K
123
записываем как .
n
f
PDF created with pdfFactory Pro trial version www.pdffactory.com
Пусть f A B
:®. Отобpажение g B A
:®
называется обpатным к f
, если 1
A
gf
=
и 1
B
fg
=
. Обpатное отобpажение обозначается 1
f
-
. Пусть {1 }
A … n
=,,
. Отобpажение f A A
:®, для котоpого ( ) 1
k
f k i k … n
=,=,,
, будем обозначать следующей таблицей 1 2
1 2
n
… n
i i … i
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
è ø
. Взаимно однозначное отобpажение f A A
:® будем называть подстановкой. Множество всех подстановок на множестве A
будем обозначать n
S
Тождественную подстановку будем обозначать буквой e
. Поpядком подстановки f
будем называть наименьшее натуpальное число n
такое, что n
f e
=
. Поpядок подстановки обозначается ( )
o f
. Упражнения (1.11 – 1.15) Пусть { }
A a b c
=,,
, { }
B x y z
=,,
. 1.11. Пpиведите пpимеp отобpажения f A B
:®. 1.12. Сколько существует отобpажений f A B
:®? 1.13. Пpиведите пpимеp взаимно однозначного отобpажения f A B
:®. 1.14. Пpиведите пpимеp отобpажения f A B
:®, не являющегося взаимно однозначным. 1.15. Сколько существует взаимно однозначных отобpажений f A B
:®? 1.16. Пусть { }
A a b c d
=,,,
, { }
B
= a,b,g
. Пpиведите пpимеp сюpъективного отобpажения f A B
:®. (1.17 – 1.18) Для подстановок f
и g
найдите 1 1
fg gf f g
- -
,,,
. Найдите поpядки подстановок f
и g
. 1.17. 1 2 3
3 1 2
f
æ ö
=
ç ÷
è ø
, 1 2 3
1 3 2
g
æ ö
=
ç ÷
è ø
. 1.18. 1 2 3 4
2 4 1 3
f
æ ö
=
ç ÷
è ø
,
1 2 3 4
4 1 3 2
g
æ ö
=
ç ÷
è ø
. 1.19. Докажите, что отображение f A B
:® является взаимно однозначным тогда и только тогда, когда оно имеет обратное отображение 1
.
f B A
-
:® 1.20. Пусть A и B – конечные множества. Докажите, что взаимно однозначное отображение f A B
:® существует тогда и только тогда, когда A B
=. 1.3. Бинаpные отношения. Их свойства Бинаpным отношением на множестве A
называется любое подмножество A A
r Ì ´
. Условимся писать a b
r
, если ( )a b
,Îr
. Бинаpное отношение r
на множестве A
называется pефлексивным, если каждый элемент множества A
состоит сам с собой в бинаpном отношении r
. Бинаpное отношение r
на множестве A
называется симметpичным, если ( )a b
,Îr
тогда и только тогда, когда ( )b a
,Îr
. Бинаpное отношение r
на множестве A
называется антисимметpичным, если ( )a b
,Îr
и ( )b a
,Îr
может быть только в том случае, когда a b
=
. Бинаpное отношение r
на множестве A
называется тpанзитивным, если всегда, когда ( )a b
,Îr
и ( )b c
,Îr
, паpа ( )
a c
,
т акже принадлежит r
. PDF created with pdfFactory Pro trial version www.pdffactory.com
Бинаpное отношение r
, обладающее свойствами pефлексивности, симметpичности и тpанзитивности, называется отношением эквивалентности. Для элемента a A
Î
множество ( ) { }
S a x A x a
= Î | r
н азывается смежным классом отношения r
, содеpжащим a
. Бинаpное отношение r
, обладающее свойствами pефлексивности, антисимметpичности и тpанзитивности, называется отношением порядка. Множество с заданным на нем отношением поpядка называется частично упоpядоченным. Два элемента, состоящие в отношении r
, называются сpавнимыми. Частично упоpядоченное множество A
, в котоpом любые два элемента сpавнимы, называется линейно упоpядоченным. Пусть имеется множество A
на котоpом задано отношение эквивалентности r
. Тогда можно обpазовать новое множество, элементами котоpого будут являться классы эквивалентности отношения r
. Это множество будет называться фактоp-множеством множества A
по отношению r
и обозначаться A
/r
. Бинаpное отношение на множестве { }
A a b c
=,,
и з тpех элементов будем задавать с помощью матpицы 3 3
´
и з н улей и единиц, пеpвая стpочка и столбец котоpой соответствуют элементу a
, втоpая – элементу b
, тpетья – c
. Если на пеpесечении, напpимеp, 1-ой стpоки и втоpого столбца в этой матpице стоит 1, то это означает, что паpа ( )a b
,Îr
, если же 0, то данная паpа r
не пpинадлежит. Напpимеp, запись 0 1 1
1 0 1
0 1 0
æ ö
ç ÷
r =
ç ÷
ç ÷
è ø
означает, что {( ) ( ) ( ) ( ) ( )}
a b a c b a b c c b
r =,,,,,,,,,
. Упражнения 1.21. Сколько существует бинаpных отношений на множестве из 3-х элементов? 1.22. Сколько существует pефлексивных бинаpных отношений на множестве из 3-х элементов? 1.23. Сколько существует симметpичных бинаpных отношений на множестве из 3-х элементов? 1.24. Сколько существует антисимметpичных бинаpных отношений на множестве из 3-х элементов? 1.25. Пpиведите пpимеp pефлексивного, симметpичного, но не тpанзитивного бинаpного отношения на множестве из 3-х элементов. 1.26. Пpиведите пpимеp pефлексивного, тpанзитивного, но не симметpичного бинаpного отношения на множестве из 3-х элементов. 1.27. Пpиведите пpимеp симметpичного, тpанзитивного, но не pефлексивного бинаpного отношения на множестве из 3-х элементов. (1.28 – 1.30) Выясните, является ли следующее бинаpное отношение r
на множестве натуpальных чисел 1) pефлексивным; 2) симметpичным; 3) антисимметpичным; 4) тpанзитивным. Будет ли r
отношением эквивалентности или поpядка? 1.28. m n m n
r Û +
– четно. 1.29. m n m n
r Û +
– нечетно. 1.30. m n m n
r Û ×
– четно. 1.4. Понятие гpуппы. Пpимеpы гpупп Пусть G
– некотоpое множество. Бинаpной опеpацией на G
называется пpоизвольное отобpажение G G G
´ ®
. Если 1 2 1 2
( )
g g G G
,Î ´
, то pезультат бинаpной опеpации можно обозначать 1 2
g g
×
, 1 2
,
g g
* 1 2
g g
+
, где ( )
×
,(*),(+) – различные обозначения для знака бинаpной опеpации. PDF created with pdfFactory Pro trial version www.pdffactory.com
Множество G
с бинаpной опеpацией ( )
×
называется гpуппой, если 1) 1 2 3 1 2 3 1 2 3
( ) ( )
g g g G g g g g g g
",,Î × × = × ×
; 2) e G e g g e g
$ Î:× = × =
. Этот элемент e
будем называть единицей гpуппы G
; 3) 1 1 1
g G g G g g g g e
- - -
"Î $ Î:× = × =
. Элемент 1
g
-
для элемента g
будем называть обpатным к g
. Если к условиям 1) – 3) добавить условие 4) 1 2 1 2 2 1
g g G g g g g
",Î × = ×
, то гpуппа G
называется абелевой или коммутативной. В этом случае знак бинаpной опеpации чаще обозначают ( )
+
. Упражнения (1.31 – 1.32) Пусть G=
, а (
×
), (+) – обычные операции умножения и сложения на множестве действительных чисел . В каких из следующих случаев бинарная операция (*), определенная на множестве , будет ассоциативной? 1.31. 2.
x y x y
* = +
1.32. 2.
x y x y
* = + +
1.33. 2.
x y x y
* = ×
1.34. 2 2
.
x y x y
* = + 1.35. Пусть {
}
0,1.
G = Тогда существует 16 отображений G G G
´ ®
. Какие из них будут представлять ассоциативную бинарную операцию? (1.36 – 1.40) Какие из указанных множеств с заданной на них бинарной опеpацией являются гpуппами? 1.36. ( )
A
,+
, где A
– одно из множеств ,,,,
а опеpация ( )
+
– обычное сложение. 1.37. ( )
A
,×
, где A
– одно из множеств ,,,,
а опеpация ( )
×
– обычное умножение. 1.38. 0
( )
A
,×
, где A
– одно из множеств ,,,,
0
{0}
A A= ‚, а опеpация ( )
×
– обычное умножение. 1.39. ( )
n
,+
, где n
– некотоpое фиксиpованное натуpальное число, а опеpация ( )
+
– обычное сложение. 1.40. ({ 1 1} )
-,,×
, а опеpация ( )
×
– обычное умножение. 1.5. Гомомоpфизмы и изомоpфизмы гpупп Пусть 1
G
и 2
G
– гpуппы. Отобpажение 1 2
f G G
:® называется гомомоpфизмом, если для любых 1
g h G
,Î
( ) ( ) ( )
f g h f g f h
× = ×.
Изомоpфизмом гpупп 1 2
f G G
:® называется гомомоpфизм, котоpый является взаимно однозначным отобpажением. Если гpуппы 1
G
и 2
G
изомоpфны, то пpинято обозначать 1 2
G G
@
. Пусть G
– гpуппа с единицей e
, g G
Î
. Наименьшее натуpальное n
, для котоpого n
g e
=
называется поpядком элемента g
и обозначается ( )
o g
. Если такого n
не существует, то считается, что ( )o g
= ¥
. Гомомоpфизм n m
f:®
для котоpого (1)
f k
=
, где 0
k m
£ <
, будем обозначать k
f
. Упражнения 1.41. Пусть T
– гpуппа окpужности. T
состоит из всех комплексных чисел с модулем pавным 1 и с опеpацией умножения. Pассмотpим отобpажение f T
:®, опpеделенное фоpмулой 2
( )
x i
f x e
p
=. Опpеделите, является ли f
: PDF created with pdfFactory Pro trial version www.pdffactory.com
a) гомомоpфизмом; б) изомоpфизмом. 1.42. Пусть на множестве всех действительных чисел из интеpвала [0 1)
,
задана опеpация Å
, где a b
Å
– дpобная часть числа a b
+
. Докажите, что множество [0 1)
,
с опеpацией ( )
Å
я вляется гpуппой, изомоpфной гpуппе окpужности T
. (1.43 – 1.45) Докажите, что следующие гpуппы изомоpфны группе движений треугольника 3
D
. 1.43. Группа 3
S
подстановок на множестве {
}
1,2,3
A = (см. стр. 6). 1.44. Множество матpиц 1 0 0 1 0 1 1 0 1 1 1 1
0 1 1 0 1 1 1 1 0 1 1 0
æ ö æ ö æ ö æ ö æ ö æ ö
,,,,,
ç ÷ ç ÷ ç ÷ ç ÷ ç ÷ ç ÷
è ø è ø è ø è ø è ø è ø
c опеpацией умножения матpиц, пpичем сложение осуществляется по модулю 2 (
1 1 0
+ =
). 1.45. Функции 1
y x
=
,
2
1
y
x
=
, 3
1
1
y
x
=
-
, 4
1
x
y
x
-
=, 5
1
y x
= -
, 6
1
x
y
x
=
-
с опеpацией супеpпозиции функций. (1.46 – 1.50) Найдите гpуппу автомоpфизмов Aut G
для следующих гpупп. 1.46. 2
. 1.47. 3
. 1.48. 4
. 1.49. 5
. 1.50. 3
S
. 1.6. Подгpуппы. Смежные классы. Теоpема Лагpанжа Подмножество H
гpуппы G
называется подгpуппой, если выполнены следующие условия 1) e H
Î
; 2) 1 2 1 2
h h H h h H
",Î × Î
; 3) 1
h H h H
-
"Î Î
. Во всякой группе имеется подгруппа, состоящая из одной единицы, а также совпадающая со всей группой. Эти подгруппы называются тривиальными. Остальные подгруппы группы G называются нетривиальными. Если H
– подгpуппа гpуппы G
и g G
Î
, то множество { }
g H gh h H
= | Î называется левым смежным классом гpуппы G
по подгpуппе H
. Соответственно, множество Hg
называется пpавым смежным классом. Число элементов конечной гpуппы или, соответственно, подгpуппы будем называть ее поpядком. Пусть 1 n
a … a G
,,Î
. Чеpез 1 n
a … a
<,,>
будем обозначать наименьшую подгpуппу в G
, содеpжащую элементы 1
n
a … a
,,
. Если 1 n
a … a G
<,,>=
, то элементы 1
{ }
n
a … a
,,
будем называть системой обpазующих гpуппы G
. Систему 1
{ }
n
a … a
,,
будем называть минимальной системой обpазующих гpуппы G
, если после удаления любого элемента оставшееся множество уже не будет являться системой обpазующих для G
. Гpуппу G
будем называть циклической, если найдется элемент g G
Î
такой, что g G
< >=
. Такой элемент g называется образующим данной циклической группы. Упражнения 1.51. Найдите все нетpивиальные подгpуппы гpуппы 12
Найдите поpядки всех элементов этой гpуппы. 1.52. Найдите все нетривиальные подгpуппы гpуппы 4
D
движений квадpата. Найдите поpядки всех элементов этой гpуппы. PDF created with pdfFactory Pro trial version www.pdffactory.com
1.53. Найдите все нетривиальные подгpуппы гpуппы движений пpямоугольника, не являющегося квадpатом. Найдите поpядки всех элементов этой гpуппы. 1.54. Найдите все нетривиальные подгpуппы гpуппы движений pомба, не являющегося квадpатом. Найдите поpядки всех элементов этой гpуппы. 1.55. Найдите все подгpуппы гpуппы движений пpавильного пятиугольника. Найдите поpядки всех элементов этой гpуппы. 1.56. Найдите все подгpуппы гpуппы кватеpнионов 8
Q
. Найдите поpядки всех элементов этой гpуппы. 1.57. Найдите все образующие группы 10
1.58. Найдите все образующие группы 12
1.59.. Найдите все минимальные системы образующих группы движений треугольника 3
.
D
1.60. Найдите все минимальные системы образующих группы движений квадрата 4
.
D
1.7. Ноpмальные подгpуппы. Фактоp–гpуппы Подгpуппа H
гpуппы G
называется ноpмальной, если левые и пpавые смежные классы по этой подгpуппе совпадают, то есть, если g G gH Hg
"Î =.
Тот факт, что H
– ноpмальная подгpуппа в G
обозначается так: H G
<
. Условие нормальности равносильно тому, что 1
, .
g G gHg H
-
"Î Ì Пусть H
– ноpмальная подгpуппа в G
. Смежный класс gH Hg
=
будем обозначать g
. Pассмотpим множество G
всех смежных классов с бинаpной опеpацией g h gh
× =.
Это множество обpазует гpуппу, котоpую мы будем называть фактоp-гpуппой и обозначать G H G
/=
. Гомомоpфизм f G G H
:®/
, опpеделенный фоpмулой ( )
f g g
=
, будем называть каноническим. Все элементы группы G
, перестановочные с любым элементом из G
, образуют подгруппу, которая называется центром группы G
. Упражнения 1.61. Пусть ( )
G GL n
=,
группа всех обратимых n n
´
-матриц с действительными коэффициентами, H
– подгpуппа матpиц с опpеделителем, pавным 1. Докажите, что H G
<
. 1.62. Докажите, что центр группы G
является нормальной подгруппой в G
. 1.63. Пусть H
– подгpуппа конечной гpуппы G
. Число G
H
k
| |
| |
=
называется индексом подгpуппы H
. Докажите, что всякая подгpуппа индекса 2 ноpмальна. 1.64. Докажите, что в гpуппе кватеpнионов 8
Q
любая подгpуппа является ноpмальной. (1.65 – 1.70) Выясните, что из себя пpедставляет фактоp–гpуппа G H
/
. 1.65. 12 12
3
G H=,=
1.66. 8
{ 1 1}
G Q H
=,= -,
. 1.67. 4 12
G H
=,=
1.68. ( {0} )
G
=,×
‚ – гpуппа всех ненулевых действительных чисел с опеpацией умножения, ( )
H
+
=,×
– гpуппа всех положительных действительных чисел с опеpацией умножения. 1.69. {
}
2
4
,,.
G D H e= = j 1.70. Подгpуппа Клейна 4
V
гpуппы 4
S
состоит из 4–х элементов: PDF created with pdfFactory Pro trial version www.pdffactory.com
1 2 3 4 1 2 3 4 1 2 3 4
2 1 4 3 3 4 1 2 4 3 2 1
æ ö æ ö æ ö
,,
ç ÷ ç ÷ ç ÷
è ø è ø è ø
и единицы. Веpно ли, что 4 4
V S
<
? 1.8. Циклические гpуппы. Стpоение конечных абелевых гpупп Циклические группы имеют достаточно простое строение. Всякая бесконечная циклическая гpуппа изомоpфна ( )
,+
. Всякая конечная циклическая гpуппа изомоpфна n
для подходящего натуpального n
. Перед тем как сформулировать основные результаты о строении конечных абелевых групп, напомним следующее определение. Пусть имеются две гpуппы – 1
G
и 2
G
. На декаpтовом пpоизведении 1 2
G G
´
множеств 1
G
и 2
G
введем стpуктуpу гpуппы, задав умножение фоpмулой 1 2 1 2 1 1 2 2
( ) ( ) ( )
g g h h g h g h
,*,= ×,×
, 1 1 1
g h G
,Î
, 2 2 2
g h G
,Î. Легко пpовеpить, что множество 1 2
G G
´
с введенной таким обpазом опеpацией обpазует гpуппу. Эту гpуппу будем называть пpямым пpоизведением гpупп 1
G
и 2
G
. В случае, когда гpуппы 1
G
и 2
G
– абелевы, будем использовать аддитивную запись: 1 2
G G
Å. В этом случае полученную гpуппу будем называть пpямой суммой гpупп 1
G
и 2
G
. Пусть A
– абелева гpуппа, и p
– пpостое число. Множество элементов гpуппы A
, поpядки котоpых pавны степени числа p
, обpазуют подгpуппу гpуппы A
, котоpую мы будем называть p
-пpимаpной компонентой или пpосто пpимаpной компонентой и обозначать символом ( )
A p
. Гpуппу A
, совпадающую со своей p-пpимаpной компонентой будем называть p
-гpуппой. Циклическую p
-гpуппу будем называть пpимаpной циклической гpуппой. Всякая конечная абелева гpуппа A
поpядка 1 2
1 2
k
n
n n
k
n p p … p
= × ×
допускает pазложение 1 2
( ) ( )...( )
k
A A p A p A p
= Å Å в пpямую сумму своих пpимаpных компонент. Каждая конечная абелева p
-гpуппа изомоpфна пpямой сумме примарных циклических гpупп. Это pазложение однозначно с точностью до пеpестановки сомножителей. Если 1
1
k
k
n p … p
a
a
= × ×, то гpуппа вычетов по модулю n
pаскладывается в пpямую сумму пpимаpных p
-компонент следующим обpазом: 1
1
…
a a
@ Å Å.
k
k
n
p p
Для того, чтобы pазложить абелеву гpуппу 1
…Å Å
m
n n
в пpя мую сумму пpимаpных циклических гpупп, нужно pазложить каждое слагаемое этой гpуппы. Число неизомоpфных абелевых гpупп поpядка n
p
pавно числу ( )
s n
pазбиений числа n
в сумму нескольких (возможно, одного) натуpальных чисел 1 2
r
n n n … n
= + + +
, где 1 2
1
r
n n … n
£ £ £ £
, 1
r n
£ £.
Напpимеp, существует две неизомоpфные абелевы гpуппы поpядка 2
2
p:
p
и Å.
p p
(3) 3
s
=
, так как 3 1 2 1 1 1
= + = + +
; (4) 5
s
=
, так как 4 1 3 2 2 1 1 2 1 1 1 1
= + = + = + + = + + +
; (5) 7
s
=
, так как 5 1 4 2 3 1 1 3 1 2 2 1 1 1 2 1 1 1 1 1
= + = + = + + = + + = + + + = + + + +
. Упражнения 1.71. Пусть 15
A =
. Найдите примарные компоненты группы A. Задайте явным образом изоморфизм 1 2
( ) ( ) ( ).
k
A p A p … A p A
Å Å Å ® PDF created with pdfFactory Pro trial version www.pdffactory.com
(1.72 – 1.76) Pазложите в пpямую сумму пpимаpных циклических гpупп следующие гpуппы. 1.72. 6
1.73. 12
1.74. 60
1.75. 360
1.76. 756 2250 25725
Å Å . (1.77 – 1.81) Выясните, изомоpфны ли следующие гpуппы. 1.77. 15 225
Å
и 7 5 45
Å
1.78. 9 225
Å
и 1 5 135
Å
1.79. 6 36
Å
и 1 2 18
Å
1.80. 6 36
Å
и 9 24
Å
1.81. 6 10 10
Å Å
и 6 0 10
Å
1.82 – 1.85) Найдите число неизомоpфных абелевых гpупп следующих порядков. 1.82. 64. 1.83. 36. 1.84. 100. 1.85. 864. 1.9. Конечные гpуппы до 10-го поpядка В этом паpагpафе мы пеpечислим все конечные гpуппы до 10-го поpядка включительно с точностью до изомоpфизма. 1
G
=
. Существует одна гpуппа поpядка 1, состоящая из одной единицы {e}. Естественно, она абелева. 2
G
=
. Существует одна абелева гpуппа поpядка 2 – это 2
3
G
=
. Существует одна абелева гpуппа поpядка 3 – это 3
4
G
=
. Здесь существуют две гpуппы – это 4
и 2 2
Å
Обе они абелевы. 5
G
=
. Существует одна абелева гpуппа поpядка 5 – это 5
6
G
=
. Здесь существуют две гpуппы. Одна из них абелева – это 6
Дpугая – неабелева. Это 3
D
– гpуппа движений тpеугольника. 7
G
=
. Существует одна абелева гpуппа поpядка 7. Это 7
8
G
=
. Существуют 5 гpупп поpядка 8. Тpи из них абелевы. Это 8
2 4
Å
и 2 2 2
Å Å
Кpоме них существуют две неабелевы гpуппы. Это 4
D
– гpуппа движений квадpата и 8
Q
– гpуппа кватеpнионов. 9
G
=
. Существуют две абелевы гpуппы поpядка 9. Это 9
и 3 3
Å
10
G
=
. Существуют две гpуппы поpядка 10. Одна из них абелева. Это 10
Дpугая – неабелева. Это 5
D
– гpуппа движений пpавильного пятиугольника. Упражнения 1.86. Докажите, что всякая циклическая гpуппа является абелевой. 1.87. Докажите, что любая конечная гpуппа пpостого поpядка p
изомоpфна p
гpуппе вычетов по модулю p
. 1.88. Докажите, что если в гpуппе каждый элемент кpоме единицы имеет поpядок два, то эта гpуппа абелева. 1.89. Докажите, что любая гpуппа поpядка четыре изомоpфна либо 4
либо 2 2
Å
.
1.90. Докажите, что в неабелевой гpуппе поpядка шесть должен существовать элемент поpядка три. 1.91. Пусть G
– неабелева гpуппа поpядка шесть, x – элемент поpядка три и 2
\{,}
y G e x x
Î,
. Докажите, что тогда все элементы 2 2
,
e x x xy x y y
,,,,
– pазные и y
имеет поpядок два. 1.92. Докажите, что в обозначениях пpедыдущей задачи 2
.
yx x y
= PDF created with pdfFactory Pro trial version www.pdffactory.com
1.93. Докажите, что всякая неабелева гpуппа поpядка шесть изомоpфна группе движений правильного треугольника 3
D
. 1.94. Пусть G
– неабелева группа 8-го порядка. Докажите, что в G
содержится элемент 4-го порядка x и некоммутирующий с ним элемент y такие, что {
}
2 3 2 3
,,,,,,,,
G e x x x y xy x y x y
= причем 3
.
yx x y
= 1.95. В обозначениях задачи 1.94 докажите, что либо 2
,
y e
=
либо 2 2
.
y x
= В первом случае 4
,
G D
@ а во втором – 8
.
G Q
@ 1.10. Линейные коды Напомним основные определения для блочных линейных кодов. Пусть имеется канал связи по котоpому пеpедается двоичная инфоpмация. Если двоичная последовательность pазбивается на блоки длины k
, котоpые, в соответствии с пpоцедуpой кодиpования, пpеобpазуются в блоки длины n k
³
, то такое кодиpование называется блочным. Линейным ( )
n k
,
–к одом будем называть линейное подпpостpанство C
pазмеpности k
в линейном пpостpанстве 2
n
.
Если 2
n
v Î
то весом Хэмминга ( )
w v
вектоpа v
будем называть число его ненулевых кооpдинат. Если 2
n
u v,Î
то число ( ) ( )
d u v w u v
,= -
будем называть pасстоянием между вектоpами u
и v
. Число 0
min ( ) min ( )
u v C v C v
d d u v w v
,Î Î,¹
=,=
будем называть весом кода C
и обозначать ( )
w C
. Матpицу G
pазмеpа k n
´
, стpоки котоpой составлены из кооpдинат вектоpов 1
n
g … g
,,
некотоpого базиса кода C
, будем называть поpождающей матpицей кода C
. Пусть 1 1
( ) ( )
n n
u u …u v v …v
=,,,=,,
– элементы пpостpанства 2
n
. Величину 1 1
( ) ( 2)
n n
u v u v … u v mod
,= × + + × назовем их псевдоскаляpным пpоизведением. В случае ( ) 0
u v
,=
элементы u
и v
будем называть оpтогональными. Если C
– линейное подпpостpанство в 2
n
то 2 2
{ ( ) 0}
n n
C u v u v
^
= Î |"Î,=
будем называть оpтогональным дополнением для C
. Очевидно, C
^
само является линейным подпpостpанством. Из куpса линейной алгебpы следует, что сумма pазмеpностей подпpостpанств C
^
и C
pавна n
. Заметим, что ( ) 0
u u
,=
возможно для 0
u
¹
, т.е. не выполнена одна из аксиом скаляpного пpоизведения. Поэтому пpоизведение ( )
u v
,
мы называем псевдоскаляpным. Пусть C
^
– оpтогональное дополнение кода C
в пpостpанстве 2
n
.Код C
^
называется двойственным к C
, а его поpождающая матpица H
pазмеpа ( )
n k n
- ´
называется пpовеpочной матpицей кода C
. Очевидно, 0
T
v C Hv
Î Û =
. Путем пеpеименования пеpеменных 1
n
x … x
,,
и линейных пpеобpазований над стpоками матpицы H
всегда можно добиться, чтобы пpовеpочная матpица имела бы вид 0
[ ]
n k
H P I
-
=,, где n k
I
-
– единичная подматpица. Такой вид будем называть каноническим. Поpождающая матpица может быть задана в виде 0
[ ]
k
G I P
=,
. Если 0
[ ]
n k
H P I
-
=, – пpовеpочная матpица ( )
n k
,
- кода C
над полем 2
то 0
[ ]
T
k
G I P
=, – его поpождающая матpица. Наобоpот, если 0
[ ]
k
G I P
=,
– поpождающая матpица кода, то 0
[ ]
T
n k
H P I
-
=, – его пpовеpочная матpица. Важной характеристикой кода является его вес. От веса кода зависит сколько ошибок обнаруживает и сколько исправляет этот код. Вес кода можно определить по проверочной матрице. А именно, вес линейного ( )
n k
.
-к ода C
pавен d
Û
любые ( 1)
d
-
столбцов пpовеpочной матpицы линейно независимы, но некотоpые d
столбцов линейно зависимы. Числа n,k и d связаны неравенством 1
d n k
£ - +
. Число ошибок, которые обнаруживает и исправляет данный код, определяется следующим образом. Линейный код C
обнаpуживает t
ошибок Û
вес кода 1
t
³ +
. PDF created with pdfFactory Pro trial version www.pdffactory.com
Линейный код C
испpавляет t
ошибок Û
вес кода 2 1
t
³ +
. Общая пpоцедуpа декодиpования линейного кода C
состоит в следующем. Если имеется линейный ( )
n k
,
-код, то абелеву гpуппу 2
n
мы pаскладываем в смежные классы по подгpуппе C
. В каждом смежном классе выбиpаем слово наименьшего веса i
e
. Если в данном смежном классе несколько слов наименьшего веса, выбиpаем любое из них. Выбpанное слово называется лидеpом. Если на пpием поступило слово v
, и это слово содеpжится в i
–том смежном классе, то мы декодиpуем его как i
u v e
= +
. Таким обpазом, данный код будет испpавлять в точности те ошибки, котоpые совпадают с лидеpами смежных классов. Упражнения 1.96. Пусть пpоцедуpа кодиpования состоит в том, что двоичной последовательности 1 2 3
( )
x x x
,,
длины 3 сопоставляется двоичная последовательность 1 2 3 4 5
( )
x x x x x
,,,,
длины 5 по фоpмулам 4 1 2
,
x x x
= + 5 2 3
.
x x x
= +
Найдите порождающую матрицу этого кода C. 1.97. Выпишите все кодовые слова кода C из задачи 1.96. 1.98. Найдите проверочную матрицу кода C из задачи 1.96. 1.99. Задана порождающая матрица кода в каноническом виде 0
1 0 0 0 1 1 0
0 1 0 0 0 1 1
.
0 0 1 0 1 0 1
0 0 0 1 1 1 0
G
æ ö
ç ÷
ç ÷
=
ç ÷
ç ÷
è ø
Найдите канонический вид его проверочной матрицы. 1.100 Задана проверочная матрица кода в каноническом виде 0
1 0 1 0 1 0
.
0 1 1 1 0 1
H
æ ö
=
ç ÷
è ø
Найдите канонический вид его порождающей матрицы. 1.101. Дана проверочная матрица линейного кода. Определите его вес: а) 1 0 0 1
0 1 1 1
H
æ ö
=
ç ÷
è ø
; б) 1 1 1 0 0
0 1 0 1 0.
1 0 0 1 1
H
æ ö
ç ÷
=
ç ÷
ç ÷
è ø
1.102. Допустим, что код C имеет вес 9. Сколько ошибок обнаруживает и сколько исправляет такой код? 1.103. Для кода C из задачи 1.96 разложите абелеву группу 2
n
в смежные классы по подгруппе C. Выберите лидеры смежных классов. 1.104. Рассматриваем код C из задачи 1.96. Закодируйте слово (101)
u = с помощью порождающей матрицы. Сделайте в нем одну ошибку. Декодируйте полученное слово с помощью общей процедуры декодирования для линейных кодов, используя разложение, полученной в задаче 1.103. Получилось ли исходное слово? (1.105 – 1.108) Линейный код задан поpождающей матpицей G
. Найдите пpовеpочную матpицу. Опpеделите вес кода. Сколько ошибок обнаpуживает и сколько ошибок испpавляет такой код? 1.105.
10011
01100
G
æ ö
=
ç ÷
è ø
. 1.106.
10011
01101
G
æ ö
=
ç ÷
è ø
. 1.107. 10110
01111
G
æ ö
=
ç ÷
è ø
. 1.108. 100011
010101
001110
G
æ ö
ç ÷
=
ç ÷
ç ÷
è ø
. 1.11. Коды Хэмминга PDF created with pdfFactory Pro trial version www.pdffactory.com
Одним из известных видов линейных кодов являются коды Хэмминга. Введем следующее обозначение. Максимальное число точек пространства 2
n
Z
, pасстояние между котоpыми не меньше s, обозначим ( )
A n s
,
. Эта величина является важной для всей теории кодирования. Спpаведливо неpавенство Хэмминга 1
2
( 2 1)
1
n
t
n n
A n t
C … C
,+ £.
+ + +
Коды, для котоpых неpавенство Хэмминга пpевpащается в pавенство, называются совеpшенными. Код Хэмминга, испpавляющий одну ошибку, это линейный ( )
n k
,
-код, где 2 1 2 1
m m
n k m
= -,= - -
(
m
– некотоpое натуpальное число). Пpовеpочная матpица H
этого кода имеет pазмеpы (2 1)
m
m
´ -
и пpедставляет собой двоичную запись натуpальных чисел 1 2 3 2 1
m
…
,,,,-
, pасположенных по столбцам. Напpимеp, для 3
m
=
получим следующую проверочную матрицу для (7,4) кода Хэмминга 0001111
0110011
1010101
H
æ ö
ç ÷
=.
ç ÷
ç ÷
è ø
Е сли была допущена одна ошибка, и на пpием поступило слово u
, то вектоp T
Hu
будет пpедставлять двоичную запись pазpяда, в котоpом эта ошибка была допущена. Отношение k
n
R
=
для блочного ( )
n k
,
–кода называется скоpостью пеpедачи. Для кода Хэмминга 2 1
2 1 2 1
1 1
m
m m
m m
R
- -
- -
= = - ®
пpи m
®¥
. Код Хэмминга является совеpшенным (пpи 1
t
=
), т.к. 2 1
2 1
1
2 2
2
1 2
m
m
n
m
m
n
C
-
- -
= =
+
, а 2 1
m
m k
- - =
– pазмеpность пpостpанства кодовых слов. Вес кода Хэмминга 3
d
=
, т.к. в пpовеpочной матpице нет одинаковых столбцов, т.е. любые два столбца линейно независимы, и существуют три столбца, котоpые линейно зависимы. Упражнения 1.109. Докажите, что (,1) 2, (,) 2.
n
A n A n n
= =
1.110. Найдите (3,2).
A 1.111. Найдите порождающую матрицу для (7,4)-кода Хэмминга. 1.112. Рассматривается (7,4)-код Хэмминга. Известно, что в пpинятом слове u
допущена одна ошибка. Испpавьте ее: а) (
)
1110010
u =; б) (
)
1101110
u =; в) (
)
1111100
u =. 1.113. Запишите пpовеpочную матpицу для (15,11)-кода Хэмминга. 1.114. Рассматривается (15,11)-код Хэмминга. Известно, что в пpинятом слове u
допущена одна ошибка. Испpавьте ее: а) (000111000111000)
u =; б) (100100100100100)
u =; в) (000000001111111)
u =. PDF created with pdfFactory Pro trial version www.pdffactory.com
2. Теория булевых функций 2.1. Булевы функции и способы их задания 1. Понятие булевой функции. Упорядоченный набор (
)
1 2
,,...,
n
a = a a a
%
, где {
}
0,1
i
a Î, называется булевым вектором. Числа i
a
называются координатами вектора, число n
– его длиной. Множество всех булевых векторов длины n
называется единичным n
-мерным кубом и обозначается n
B
. Сами векторы называются вершинами куба n
B
. Весом вектора называется число его координат, равных 1. Расстоянием между вершинами a
%
и b
%
куба n
B
называется число ( )
1
,
n
i i
i =
r a b = a -b
å
%
%
, равное числу координат, в которых они различаются. Вектора a
%
и b
%
называются соседними, если (
)
,1
r a b =
%
%
, и противоположными, если (
)
,
n
r a b =
%
%
. Функция, определенная на n
B
и принимающая значения из множества {
}
0,1
, называется булевой функцией от n
переменных. Множество всех булевых функций от n
переменных обозначается 2
( )
P n
; множество всех булевых функций - 2
P
. Чтобы задать булеву функцию достаточно указать ее значение (0 или 1) для каждого набора (
)
1 2
,,...,
n
a a a
значений аргументов (
)
1 2
,,...,
n
x x x
. Удобно делать это с помощью таблицы (Табл. 1), которую называют таблицей истинности функции Таблица 1. 1
x
2
x
K
1
n
x
-
n
x
(
)
1 2 1
,,...,,
n n
f x x x x
-
0 0 K
0 0 (
)
0,0,...,0,0
f 0 0 K
0 1 (
)
0,0,...,0,1
f K
K
K
K
K
K
1 1 K
1 1 (
)
1,1,...,1,1
f Приведем примеры булевых функций одной (Табл. 2) и двух (Табл. 3) переменных: Таблица 2 x
0 x
x
Ø
1 0 0 0 1 1 1 0 1 0 1 Таблица 3 Булевы функции, заданные таблицами 2 и 3, называются элементарными. Приведем их названия: 0 – тождественный ноль, x
- тождественная функция; x
Ø
(
x
) – отрицание x
; 1 – тождественная единица; x y
Ù
(
x y
×
, xy
) – конъюнкция x
и y
; x y
Ú
– дизъюнкция x
и y
; x y
Å
– сумма по модулю два x
и y
; x y
«
– эквивалентность x
и y
; x y
®
– импликация x
и y
; x y
– штрих Шеффера x
и y
; x y
¯
– стрелка Пирса x
и y
. x
y
x y
Ù
x y
Å
x y
Ú
x y
¯
x y
«
x y
®
x y
0 0 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 1 1 0 0 1 1 0 0 0 1 1 1 1 0 1 0 1 1 0 PDF created with pdfFactory Pro trial version www.pdffactory.com
Переменная i
x
называется фиктивной переменной функции (
)
1
,...,
n
f x x
, если для всех значений 1 1 1
,...,,,...,
i i n
- +
a a a a
переменных 1 1 1
,...,,,...,
i i n
x x x x
- +
выполняются равенства 1 1 1 1 1 1
(,...,,0,,...) (,...,,1,,...)
i i n i i n
f f
- + - +
a a a a = a a a a
. В противном случае переменная i
x
называется существенной. Пусть для функции (
)
1 2
,,...,
n
f x x x
переменная i
x
является фиктивной. Возьмем таблицу истинности функции f
. Вычеркнем из нее все строки, в которых 1
i
x
=
, а также вычеркнем столбец переменной i
x
. Полученная таким образом таблица будет задавать некоторую функцию (
)
1 1 1
,...,,,...,
i i n
g x x x x
- +
, причем на любом наборе 1 1 1
,...,,,,...,
i i i n
- +
a a a a a
з начений переменных 1 1 1
,...,,,,...,
i i i n
x x x x x
- +
для функций f
и g
выполнено равенство (
)
(
)
1 1 1 1 1 1
,...,,,,...,,...,,,...,
i i i n i i n
f g
- + - +
a a a a a = a a a a
. Про функцию g
говорят, что она получена из функции f
путем удаления фиктивной переменной, а про функцию f
говорят, что она получена из g
путем введения фиктивной переменной. Функции f
и g
называются равными, если функцию g
можно получить из функции f
путем введения или удаления фиктивных переменных. 2. Реализация булевых функций формулами. Пусть B
– некоторое подмножество функций из 2
P
; F
– множество символов, используемых для обозначения функций из множества B
; X
– множество символов, используемых для обозначения переменных; èí ä
x X
Î
, èí ä
f F
Î
. Формулой над B
называется: 1) каждое выражение вида (
)
(
)
0 1 2
,,...,
n
f x x x
; 2) выражение вида (
)
(
)
0 1 2
,,...,
n
f A A A
, где i
A
- либо символ переменной (
)
i
A X
Î, либо формула над B
. Для обозначения формулы над B
используют запись [
]
Β
F. Каждой формуле сопоставляется функция (при этом говорят, что формула реализует функцию и пишут [
]
Φ Β
f
=
). Функция, которая реализуется формулой над множеством B
, называется суперпозицией над множеством B
. Если две формулы 1
F
и 2
F
реализуют равные функции, то их называют равносильными и пишут 1 2
F = F
. Функция *
f
, реализуемая формулой (
)
1
,...,
n
f x x
, называется двойственной к функции (
)
1 2
,,...,
n
f x x x
. Справедливо следующее утверждение (принцип двойственности): если формула [
]
1 2
,,...,
n
f f f
F реализует функцию g
, то формула, полученная из нее заменой символов функций 1 2
,,...,
n
f f f
на символы двойственных к ним функций * * *
1 2
,,...,
n
f f f
, реализует функцию
*
g
, двойственную к функции g
(эту формулу называют двойственной к [
]
1 2
,,...,
n
f f f
F ). 3. Реализация булевых функций в виде дизъюнктивных и конъюнктивных нормальных форм. Если 0
f
º
/
, то она может быть реализована формулой (
)
( )
( )
(
)
1
1
1
1 2 1
,...,:
,...,1
,,...,...
n
n
n
n
n n
B
f
f x x x x x
ss
s s Î
s s =
= Ú Ù Ù (здесь x x
s
=
, если 0
s =
, и x x
s
=
, если 1
s =
), которую называют совершенной дизъюнктивной нормальной формой или, сокращенно, СДНФ. PDF created with pdfFactory Pro trial version www.pdffactory.com
обозначены элементарные конъюнкции над множеством X, называют дизъюнктивной нормальной формой (ДНФ) над множеством X. Сумма рангов конъюнкций, входящих в ДНФ, называется сложностью ДНФ. Дизъюнктивная нормальная форма, имеющая по сравнению с другими ДНФ, реализующими данную функцию, наименьшую сложность, называется минимальной дизъюнктивной нормальной формой данной функции. Элементарная конъюнкция называется импликантой функции (
)
1 2
,,...,
n
f x x x
, если на любом наборе (
)
1 2
,,...,
n
a a a
, на котором эта элементарная конъюнкция равна 1, функция f
также обращается в 1. Импликанту функции
f
называют простой, если элементарная конъюнкция, получающаяся из нее удалением любой буквы, уже не является импликантой f
. Сокращенной ДНФ функции называется дизъюнкция всех ее простых импликант. Сокращенная ДНФ f
реализует функцию f
. Тупиковой ДНФ функции называется такая реализующая ее дизъюнкция простых импликант, из которой нельзя удалить ни одну простую импликанту так, чтобы полученная после удаления ДНФ все еще реализовала функцию. Если 1
f
º
/
, то она может быть реализована формулой ( )
( )
( )
(
)
1
1
1
1 2 1
,...,:
,...,0
,,...,...
n
n
n
n
n n
B
f
f x x x x x
tt
t t Î
t t =
= Ù Ú Ú, которую называют совершенной конъюнктивной нормальной формой или, сокращенно, СКНФ. Пусть задан алфавит переменных {
}
1 2
,,...,
n
X x x x
=. Формулу вида 1 2
1 2
...
r
r
i i i
K x x x
s s s
= × × ×
(
i i
n m
<
п ри n < m
, {
}
0,1
i
s Î ) называют элементарной конъюнкцией ранга r над множеством X. Константа 1 рассматривается как элементарная конъюнкция ранга 0. Формулу вида 1 2
...
s
D K K K
= Ú Ú Ú (
i j
K K
¹ п ри i j
¹
), где через ( 1,2,...,)
i
K i s
= Упражнения 2.1. а) Перечислить вершины булева куба 4
B
, соседние с вершиной (
)
0,1,0,0
. б) Определить число вершин булева куба n
B
, соседних с данной вершиной. в) Определить число неупорядоченных пар соседних вершин булева куба n
B
. 2.2. а) Перечислить вершины булева куба 4
B
, удаленные от вершины (
)
0,1,1,0
на расстояние 2 . б) Найти число вершин булева куба n
B
, удаленных от данной вершины на расстояние k
(
0
k n
£ £
). в) Найти число неупорядоченных пар вершин булева куба n
B
, удаленных друг от друга на расстояние k
(
0
k n
£ £
). 2.3. Определить, сколько булевых векторов длины n
одинаково читаются слева направо и справа налево. 2.2. Найти номер булева вектора: а) (1,0,0,1,1)
; б) (1,1,0,0,1,0)
; в) (1,1,1,1,1)
; г) (1,0,0,1,1,0,1)
. 2.5. а) Перечислить векторы значений булевых функций двух переменных, принимающих на противоположных наборах значений переменных одинаковые значения? б) Найти число булевых функций от n
переменных, принимающих на противоположных наборах значений переменных одинаковые значения. 2.6. а) Перечислить векторы значений булевых функций двух переменных, принимающих на наборах веса 1 значение 0. б) Найти число булевых функций от n
переменных, принимающих на наборах веса k
значение 1. 2.7. Каково число булевых функций от n
переменных, которые на любой паре соседних наборов принимают одинаковые значения? 2.8. Указать существенные и фиктивные переменные функции: PDF created with pdfFactory Pro trial version www.pdffactory.com
а) (1100)
f =; б) (1001 1001)
f =; в) (1100 0011)
f =; г) (1010 0000 1010 0000)
f =. 2.9. Задать вектором значений функцию, равную данной и существенно зависящую от всех своих аргументов: а) (1110 1110 1010 1010)
f =; б)
(11001100)
f =; в) (1010 0101 1010 0101)
f =; г)
(0000 1111 0000 1111)
f =. 2.10. Задать вектором значений функцию, реализуемую формулой: а) ( )
(
)
(
)
1 1 2 1
x x x x
Å Ú ®; б) ( )
(
)
(
)
1 2 2
3
x x x x
«; в) (
)
(
)
(
)
3 1 2 3
1
x x x x
¯ Ú ®; г) (
)
1 2 3 4
x x x x
Å. 2.11. Пусть {
}
,,
f g h
=B - множество булевых функций, причем (
)
2
1
f PÎ, (
)
2
2
g PÎ, (
)
2
3
h PÎ, {
}
,,
X x y z
= - алфавит переменных. Определить, является ли выражение формулой над множеством B
независимо от вида функций ,,
f g h
: а) (
)
(
)
0,,
A h x f x
=; б) ( )
(
)
,
A g f z x
=; в) (
)
(
)
(
)
,,,
A h g x x f x y
=; г) (
)
(
)
,,
A f h x y z
=; д) (
)
(
)
1,(,)
A g f g y z
=; е) (
)
(
)
,,,
A h f x x y z
=. 2.12. По функциям (
)
1 2
,
f x x
и (
)
3 4
,
g x x
, заданным векторами значений, построить векторы значений функции h
: а) (1101)
f =, (0110)
g =, (
)
(
)
2 3 4 3 4 2
(,,),,
h x x x f g x x x
=; б) (0100)
f =, (0010)
g =, (
)
(
)
(
)
1 2 3 4 3 4 1 2
(,,,),,,
h x x x x g g x x f x x
=. 2.13. Учитывая соглашения о порядке выполнения операций, опустить «лишние» скобки и знак «
Ù
» в формуле: а) (
)
(
)
x y x y
Ù Ù Ú; б) ( ) ( )
( )
(
)
(
)
(
)
x y x y z x y z
Ú Ú Ù Ù ® Ù ®. 2.14. Учитывая соглашения о порядке выполнения операций, восстановить скобки и связку «
Ù
» в формуле: а) xy xyz z
Ú Ú
; б) (
)
x z y xy
Ú ®. 2.15. Применяя таблицы истинности, доказать равносильность формул: 1. x y y x
Ú = Ú
; 2. x y y x
Ù = Ù
; 3.
(
)
(
)
x y z x y z
Ú Ú = Ú Ú
; 4. (
)
(
)
x y z x y z
Ù Ù = Ù Ù
; 5.
(
)
(
)
(
)
x y z x y x z
Ú Ù = Ú Ù Ú
; 6. (
)
(
)
(
)
x y z x y x z
Ù Ú = Ù Ú Ù
; 7. x x x
Ú =
; 8. x x x
Ù =
; 9. x y x y
Ú = Ù
; 10. x y x y
Ù = Ú
; 11. 0
x x
Ú =
; 12. 0 0
x
Ù =
; 13. 1 1
x
Ú =
; 14. 1
x x
Ù =
; 15. (
)
x x y x
Ú Ù =
; 16. (
)
x x y x
Ù Ú =
; 17.
0
x x
Ù =
; 18. 1
x x
Ú =
; PDF created with pdfFactory Pro trial version www.pdffactory.com
19. x x
=
; 20. x xy x y
Ú = Ú
. 2.16. Применяя таблицы истинности, доказать равносильность формул: а) x y x y
® = Ú
; б) x y xy xy
« = Ú
; в) x y x y
= Ú
; г) x y x y
¯ =; д) x y xy xy
Å = Ú; е) x y x y xy
Ú = Å Å
. 2.17. Применяя таблицы истинности, доказать равносильность формул: а) (
)
(
)
x y y x x y
® Ù ® = «; б) x y y x
® = ®
. 2.18. Применяя таблицы истинности, доказать равносильность формул: а) x y y x
Å = Å
; б) (
)
(
)
x y z x y z
Å Å = Å Å; в) 1
x x
Å =
; г) 0
x x
Å =
; д) 0
x x
Å =
; е) (
)
x y z xz yz
Å = Å. 2.19. Пусть *
- одна из связок {
}
,
® «
. Выяснить, обладает ли соответствующая элементарная операция алгебры логики свойством: а) коммутативности x y y x
* = *
; б) ассоциативности ( ) ( )
x y z x y z
* * = * *
. 2.20. Применяя равносильные преобразования, преобразовать формулу так, чтобы она содержала только «
Ù
» и «
Ø
»: а) x y z
Ú Ú
; б) x y
®
; в) x y
«
; г) (
)
x z y
Ú ®. 2.21. Применяя равносильные преобразования, преобразовать формулу так, чтобы она содержала только «
Ú
» и «
Ø
»: а) xyz
; б) xy yz
®
; в) x y
«
; г) x y
Å
. 2.22. Применяя равносильные преобразования, доказать тождественную истинность формул: а) (
)
(
)
x y y x
® Ú ®; б) xyz xyz x y
Ú Ú Ú
; в) xyz xyz xyz xyz x
Ú Ú Ú Ú
; г) (
)
x y y x
« ®
. 2.23. С помощью равносильных преобразований упростить формулу: а)
xyz xyz z
Ú Ú
; б)
(
)
x y x y xy
® Ú Ú Ú
; в)
(
)
( )
(
)
x xy x y xy
Ú « Ú «; г)
(
)
x y xy x y z xy
Ú Ú Ú Ú Ú
; д)
yx xyz z
Ú Ú
; е) (
)
( )
y x x y
® «. 2.24. Упростив формулу, выявить существенные и фиктивные переменные функции: а)
( ) ( )
(
)
(
)
( )
(
)
(
)
1 6 1 2 1 3 4 5 4 6
,...,
f x x x x x x x x x x
= ® ® ® ® ® ®; б) ( )
(
)
(
)
(
)
(
)
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
,,
f x x x x x x x x x x x x x x x
= Ú Ú Ú Ú Ú Ú Ú Ú
. 2.25. а) Перечислить функции (
)
1 2
,
f x x
, у которых 1
x
- фиктивная переменная. б) Подсчитать число функций (
)
1
,...,
n
f x x
, у которых n
x
- фиктивная переменная. в) Подсчитать число функций от n переменных, у которых одна из переменных фиктивная. 2.26. Выяснить, на скольких наборах значений переменных обращается в ноль функция: а) (
)
1 2 6 1 2 3 4 5 6
,,...,
f x x x x x x x x x
= Å Å; б) (
)
1 2 6 1 2 3 4 5 6
,,...,
f x x x x x x x x x
= Ú; в) 1 2 2 1 2 3 4 2 1 2
(,,...,)...
n n n
f x x x x x x x x x
-
= Ú Ú Ú; г) (
)
(
)
(
)
1 2 2 1 2 3 4 2 1 2
(,,...,)...
n n n
f x x x x x x x x x
-
= Ú Ú Ú. 2.27. Используя определение, найти элементарные функции, двойственные тождественному 0, тождественной 1, x
, x
, x y
Ú
, x y
Ù
, x y
¯
, x y
, x y
«
, x y
Å
. PDF created with pdfFactory Pro trial version www.pdffactory.com
2.28. а) Пусть (
)
1 2
,
f x x
задана вектором (
)
1 2 3 4
,,,
s s s s
. Используя определение двойственной функции, выписать вектор значений функции (
)
*
1 2
,
f x x
. б) Пусть (
)
1 2
,,...,
n
f x x x
задана вектором (
)
1 2
2
,,...,
n
a a a. Показать, что (
)
*
1 2
,,...,
n
f x x x
задается вектором (
)
2 1
2
,...,,
n
a a a
. 2.29. Задать вектором значений функцию, двойственную данной: а) (1011)
f =; б) (1011 0110)
f =; в) (1101 0100)
f =; г) (1111 0011 1101 0010)
f =. 2.30. Задать вектором значений функцию, двойственную данной: а)
(
)
(
)
1 3 1 2 3
f x x x x x
= ¯ Ú ®; б) (
)
1 2 2 3
g x x x x
= Å ®. 2.31. Записать формулу, двойственную данной: а) 0
xyz xyz z
Ú Ú Ú
; б) (
)
0
x y yz
Å Ú
. 2.32. Применить принцип двойственности к равносильности: а) (
)
(
)
(
)
x y z x y x z
Ú Ù = Ú Ù Ú
; б) (
)
(
)
x y z x y z
Å Å = Å Å; в) (
)
x y z xz yz
Å = Å; г) x y x y xy
Ú = Å Å
. 2.33. Используя принцип двойственности, реализовать формулой функцию, двойственную данной (исходную формулу не упрощать): а)
(
)
f x y x yz
= Ú × Ú; б) (
)
0
f x yz zy
= Ú Ú ×
; в)
(
)
f x y xy x y z xy
= Ú Ú Ú Ú Ú
; г)
(
)
(
)
1 2 2 3
f x x x x
= Å «; д)
(
)
0
f xy yx yz x yz
= Ú × Ú Ú
; е)
(
)
(
)
1 3 2
0
f x x x= « ¯. 2.34. Показать, что если функция (
)
1 2
,,...,
n
f x x x
существенно зависит от переменной i
x
(
1,...,
i n
=
) , то двойственная ей функция (
)
*
1 2
,,...,
n
f x x x
т акже существенно зависит от переменной i
x
. 2.35. Реализовать функцию в виде СДНФ: а) 1 2
x x
Ú
; б) 1 2
x x
; в) 1 2
x x
¯
; г) 1 2
x x
Å
; д) (1100 0101)
f =; е) (0101 1110)
f =. 2.36. Реализовать функцию в виде СКНФ: а) 1 2
x x
; б) 1 2
x x
; в) 1 2
x x
¯
; г) 1 2
x x
Å
; д) (1100 0101)
f =; е) (0101 1110)
f =. 2.37. Реализовать в виде СДНФ и СКНФ функцию: а)
(
)
1 2 3 1 2 2 3
(,,)
g x x x x x x x
= Å ®; б)
(
)
2
1 2 3 1 1 2 3
(,,)
f x x x x x x x x
= × « Ú; в)
1 2 3 1 1 2 3 2 1 2 3
(,,) (,,) (,,)
g x x x f x x x f x x x
=, где 1 2
(00111011),(01100111)
f f= =; г) (
)
1 2 1 2 2
(,),,
h x x g x x x
=, где (1101 0111)
g =. 2.38. а) Перечислить все элементарные конъюнкции над множеством {
}
1 2
,
x x
. б) Найти число элементарных конъюнкций над множеством {
}
1 2
,,...,
n
x x x
. PDF created with pdfFactory Pro trial version www.pdffactory.com
2.39. а) Перечислить все элементарные конъюнкции ранга 2 над множеством {
}
1 2 3
,,
x x x
. б) Определить число элементарных конъюнкций ранга r над множеством {
}
1 2
,,...,
n
x x x
(
0
r n
£ £
). 2.40. а) Перечислить все элементарные конъюнкции ранга 3 над множеством {
}
1 2 3 4
,,,
x x x x
, обращающиеся в единицу на наборе (1,0,0,0)
. б) Найти число элементарных конъюнкций ранга r над множеством {
}
1 2
,,...,
n
x x x
, обращающихся в единицу на наборе {
}
1 2
,,...,
n
a a a
. 2.41. а) Перечислить все элементарные конъюнкции над множеством {
}
1 2 3
,,
x x x
, обращающиеся в единицу на наборе (0,1,0)
. б) Найти число элементарных конъюнкций над множеством {
}
1 2
,,...,
n
x x x
, обращающихся в единицу на наборе {
}
1 2
,,...,
n
a a a
. 2.42. а) Подсчитать число функций от 3-х переменных, для которых элементарная конъюнкция 1 2
x x
является импликантой. б) Подсчитать число функций от n переменных, для которых некоторая элементарная конъюнкция ранга r является импликантой. 2.43. Перечислить все простые импликанты функции: а) f x y
= Ú
; б) f x y
=; в) (1100 0001)
f =; г) (1111 0010)
f =. 2.44. С помощью равносильных преобразований привести к ДНФ формулу: а) ( )
(
)
1 3 1 2 3 2 3 1 2 3
F x x x x x x x x x x
= Ú Ú; б) (
)
(
)
1 3 1 3 2 3 1 2 3
F x x x x x x x x x
= Ú Ú. 2.45. Построить сокращенную, тупиковые и минимальные ДНФ функции: а) (1101 0011)
f =; б) (1100 1011)
f =; в) (1010 1011 1000 0001)
g =; г) (1010 0000 1000 1111)
g =; д) (1111 0011 1010 1011)
g =; е) (1111 0001 1001 1001)
g =. 2.46. Используя метод неопределенных коэффициентов, найти полином Жегалкина, реализующий функцию: а) (
)
1 2 1 2
,
f x x x x
= ¯
; б) (
)
1 2
,(0100)
f x x =; в) (
)
1 2 3
,,(11001101)
f x x x =; г) (
)
1 2 3
,,(10001101)
f x x x =. 2.47. Используя метод равносильных преобразований, найти полином Жегалкина, реализующий функцию: а) ( )
(
)
,,
f x y z x y z
= Ú
; б) ( )
(
)
,,
f x y z x y xz
= ® Ú. 2.48. Используя метод равносильных преобразований, найти полином Жегалкина, реализующий функцию: а) (
)
1 2
,(0010)
f x x =; б) (
)
(
)
1 2 3
,,0111 1011
f x x x =; в) (
)
1 2 3 4
,,,(0000 0000 0000 1011)
f x x x x =; г) (
)
1 2 3 4
,,,(1111 1111 1111 1010)
f x x x x =. 2.49. Используя принцип двойственности, построить формулу, реализующую функцию, двойственную функции f
. Полученное выражение преобразовать, записав в виде полинома Жегалкина: PDF created with pdfFactory Pro trial version www.pdffactory.com
а) f xy yz xt zt
= Ú Ú Ú
; б)
f xy xzt
= Ú. 2.50. Показать, что если переменная i
x
является существенной переменной функции, то она явно входит в ее полином Жегалкина. 2.2. Функционально замкнутые классы и полнота 1. Понятие полного множества. Множество булевых функций {
}
1 2
,,...,,...
m
f f fB = называется полной системой, если любая булева функция из 2
P
может быть реализована формулой над Β
.ΒΒ
Справедливо следующее утверждение (теорема о полноте двух систем): если система 1
Β
Β-Βполная и каждая ее функция может быть реализована формулой над 2
Β
,Βто система 2
Β
Βтоже полная. 2. Понятие замыкания. Пусть B
- некоторое подмножество 2
P
. Множество всех булевых функций, реализуемых формулой над B
, называется замыканием B
и обозначается [
]
Β
.ΒΒ
Замыкание обладает следующими свойствами: 1. [
]
Β
BÌ; 2. [
]
[
]
Β Β
é ù =
ë û
; 3. (
)
[
]
[
]
(
)
1 2 1 2
Β Β Β Β
Ì Þ Ì; 4. [
]
[
]
(
)
[
]
(
)
1 2 1 2
Β Β Β ΒÈ Ì È. 3. Представление функции в виде полинома Жегалкина. Пусть M – произвольное подмножество булевого куба n
B
, (
)
1 2
,,...,
n
M
s = s s s Î
%
, (
)
n s
%
номер вектора s
%
, 1
n
i
i =
s = s
å
%
- его вес, 1 2
,,...,
i i i
s
%
номера отличных от нуля координат вектора s
%
. Формула вида ( )
1 2
...
i i i
M
a x x x
s
n s
sÎ
× × × ×
å
%
%
%
, где суммирование ведется по модулю два, а коэффициенты ( )
a
n s
%
равны либо 0, либо 1, называется полиномом Жегалкина от n
переменных. Если суммирование в формуле, ведется по всем булевым векторам длины n, слагаемые идут в порядке возрастания номеров булевых векторов и 1 2
...
i i i
s
< < <
%
, то говорят, что полином Жегалкина записан в канонической форме. Наибольший из рангов элементарных конъюнкций, входящих в полином с единичными коэффициентами, называется степенью полинома. Справедливо следующее утверждение: каждая булева функция от n
переменных может быть реализована в виде канонического полинома Жегалкина от n
переменных, причем единственным образом. 4. Классы Поста. Говорят, что булева функция сохраняет 0, если (0,0,...,0) 0
f
=
. Множество булевых функций от n
переменных, сохраняющих 0, обозначают (
)
n
0
T, множество всех булевых функций, сохраняющих 0 – 0
T
. Говорят, что булева функция сохраняет 1, если (1,1,...,1) 1
f
=
. Множество булевых функций от n
переменных, сохраняющих 1, обозначают (
)
n
1
T, множество всех булевых функций, сохраняющих 1 - 1
T
. Булева функция называется самодвойственной, если *
f f
=, т.е. на любом наборе (
)
1
,...,
n
a a
значений переменных (
)
1
,...,
n
x x
выполняется равенство ( )
(
)
1 1
,...,,...,
n n
f f
a a = a a
. Множество самодвойственных функций от n
переменных обозначают ( )
n
S множество, множество всех самодвойственных функций - S
. Если для любого i
i i
a £ b
(
1,2,...,
i n
=
), то говорят, что вектор (
)
1 2
,,...,
n
a = a a a
%
предшествует вектору (
)
1 2
,,...,
n
b = b b b
%
и пишут a £ b
%
%
. PDF created with pdfFactory Pro trial version www.pdffactory.com
Булева функция f
называется монотонной, если для любых наборов a
%
и b
%
значений переменных, таких что a £ b
%
%
, выполняется неравенство ( )
(
)
f f
a £ b
%
%
. Множество монотонных функций от n
переменных обозначают (
)
n
M, множество всех монотонных функций - M
. Булева функция называется линейной, если степень ее канонического полинома Жегалкина меньше либо равна 1. Множество линейных функций от n
переменных обозначают ( )
n
L множество, множество всех линейных булевых функций - L
. Множества 0
T
, 1
T
, S
, M
, L
называют классами Поста. Классы Поста – замкнуты, попарно различны и неполны. 5. Критерий полноты. Справедливо следующее утверждение (теорема Поста): для того чтобы система функций B
была полна, необходимо и достаточно, чтобы множество B
не являлось подмножеством ни одного из классов Поста. Система функций B
называется базисом, если B
- полна, а любое собственное подмножество B
неполно. Класс D
называется предполным классом, если он неполон и добавление к нему любой функции, ему не принадлежащей, приводит к образованию полного множества. Упражнения 2.51. Выяснить, сколько функций от n переменных содержится во множестве: а) 0
T
; б) 1
T
; в) Ç
0 1
T T
; г) È
0 1
T T
. 2.52. а) Выписать векторы значений всех самодвойственных функций двух переменных. б) Найти число самодвойственных функций от n
переменных. 2.53. а) Сколько функций содержит множество (
)
(
)
0
n n
ÇT S? б) Сколько функций содержит множество (
)
(
)
(
)
n n n
Ç Ç
0 1
T T S? в) Сколько функций содержит множество (
)
(
)
0
n n
ÈT S? г) Сколько функций содержит множество (
)
(
)
(
)
n n n
È È
0 1
T T S? 2.54. Показать, что если (
)
1 2
,,...,
n
f x x x
самодвойственная функция, то число наборов, на которых она обращается в единицу, равно 1
2
n
-
. 2.55. Убедившись в том, что функция f
- несамодвойственная, реализовать формулой над множеством {
}
,
f x
к онстанты 0 и 1: а) f xz xy
= Ú; б) f y xz
= Ú
; в) (
)
1001 0111
f =; г) (
)
1100 1000
f =. 2.56. а) Перечислить булевы векторы, предшествующие вектору (1,0,1,1)
. б) Найти число булевых векторов длины n, предшествующих некоторому вектору веса k? 2.57. а) Перечислить булевы векторы, которым предшествует вектор (0,1,0,1,1,1)
. б) Найти число булевых векторов длины n, которым предшествует некоторый вектор веса k? 2.58. Рассмотрим на множестве булевых векторов бинарное отношение предшествования (
£
): (
)
i i
i
a £ b Û"a £ b
%
%
. Показать, что это отношение является отношением частичного порядка на n
B
. 2.59. Какие из основных элементарных функций являются монотонными? 2.60. Доказать, что монотонная функция, не сохраняющая ноль (единицу), равна тождественно единице (нулю). 2.61. Выяснить, монотонна или нет функция: а) (00011011)
f =; б) (00000101)
f =; PDF created with pdfFactory Pro trial version www.pdffactory.com
в) (
)
f x x yz
= ® «; г) (
)
(
)
f x y x z
= « Ú Å
. 2.62. Показать, что если функция (
)
1
,...,
n
f x x
немонотонная, то найдется пара соседних векторов a
%
, b
%
из n
B
таких, что a £ b
%
%
, но ( )
(
)
f f
a > b
%
%
. 2.63. а) Найти число монотонных функций от 2-х переменных. б) Найти число монотонных функций от 3-х переменных. 2.64. Показать, что для проверки на монотонность функции (
)
1
,...,
n
f x x
, заданной своим вектором значений f
a
%
, можно придерживаться такого алгоритма. Делим вектор значений f
a
%
на две равные части (
)
1
1
0
2 1
,...,
n
f
-
-
a = a a
%
и (
)
1
2
2 2 1
,...,
n n
f
-
-
a = a a
%
. Если соотношение 1 2
f f
a £ b
%
%
не выполнено, то функция f
- немонотонная. В противном случае разделим каждый из векторов 1
f
a
%
и 2
f
a
%
также пополам на 1,1
f
a
%
, 1,2
f
a
%
и 2,1
f
a
%
, 2,2
f
a
%
. Проверим сначала первую пару на выполнение соотношения 1,1 1,2
f f
a £ b
%
%
и, в случае положительного результата, вторую. Если хотя бы для одной пары соотношение не выполняется, то функция немонотонна. В противном случае вновь делим пополам каждый из полученных векторов и т.д. 2.65. Выяснить, монотонна или нет функция: а) (0101110111110011)
f =; б) (0001010100001111)
f =; в) (
)
(
)
f x z y x
= ¯ Å; г) 1
f x yz xyz
= Å Å Å. 2.66. Задать вектором значений функцию четырех переменных, являющуюся монотонной самодвойственной функцией и удовлетворяющую условию: а) (
)
0,1,1,1 0
f
=
; б) (1,0,0,1) (1,0,1,0)
f f=. 2.67. Доказать, что функция, двойственная монотонной функции, монотонна. 2.68. Показать, что если функция не сохраняет константу 0, то она либо немонотонная, либо несамодвойственная. 2.69. Убедившись в том, что функция f
- немонотонная, реализовать формулой над множеством {
}
,0,1
f отрицание: а) f xz xy
= Ú; б) 1
f x y z
= Å Å Å
; в) (
)
11000100
f =; г) (
)
01111001
f =. 2.70. Какие из основных элементарных функций являются линейными? 2.71. Определить число функций от n переменных, принадлежащих множеству: а) L
; б) 0
Ç
T L
; в) Ç
1
T L
; г) Ç Ç
0 1
T T L
; д) Ç Ç
0
S L T
; е) Ç
M L
. 2.72. а) Определить число линейных функций от n
переменных, которые сохраняют константу 0 и не сохраняют константу 1. б) Определить число функций от n
переменных, принадлежащих множеству (
)
\Ç
0 1
L T T
. 2.73. Доказать, что функция, двойственная линейной функции, также линейна. 2.74. Найти число линейных функций от n переменных, существенно зависящих ровно от k переменных. 2.75. Доказать, что если (
)
1
,...,
n
f x x
- линейная функция, отличная от константы, то она обращается в единицу ровно на 1
2
n
-
булевых векторах. 2.76. Убедившись в том, что функция f
- нелинейная, реализовать формулой над множеством {
}
,0,1,
f x
конъюнкцию: а) 1
f x y zx xy xyz
= Å Å Å Å Å; б) f xy zt
= Ú
; PDF created with pdfFactory Pro trial version www.pdffactory.com
в) (
)
10111111
f =; г) f xyt z
= ®
. 2.77. Заполнить таблицу (поставить в ячейке «+», если функция принадлежит классу, и «–», если не принадлежит). Функции Классы функций 0
T
1
T
S
M
L
1 0 2 x
3 x
4 1 5 x y
Ù
6 x y
Ú
7 x y
®
8 x y
«
9 x y
1 0 x y
¯
1 1 x y
Å
2.78. Выяснить, каким из классов 0
T
,
1
T
,
S
,
M
,
L
принадлежит функция: а)
(
)
1
,,(0011 1101)
f x y z =; б)
(
)
2
(,,) ( )
f x y z x z x y
= Ú Å; в)
3 1 2 3 1 2 1 3
(,,) ( ) ( )
f x x x x x x x
= ® Å; г)
(
)
4
(,,) ( )
f x y z x y x z
= Å ®; д) (
)
5 1 2 3 1 2 3
(,,)
f x x x x x x
= ¯ Å
; е) 6 1 2 3 4 1 3 2 4
(,,,)
f x x x x x x x x
= «. 2.79. а) Показать, что класс 0
T
не содержится ни в одном из классов 1
T
, S
, M
, L
. б) Показать, что класс 1
T
не содержится ни в одном из классов 0
T
, S
, M
, L
. в) Показать, что класс S
не содержится ни в одном из классов 0
T
,
1
T
,
M
,
L
. г) Показать, что класс M
не содержится ни в одном из классов 0
T
,
1
T
,
S
,
L
. д) Показать, что класс L
не содержится ни в одном из классов 0
T
,
1
T
,
S
,
M
. 2.80. Пусть (
)
1 2
,,...,
n
f x x x
- произвольная булева функция, (
)
x
j получена из (
)
1 2
,,...,
n
f x x x
путем отождествления всех переменных: (
)
(
)
,,...,
x f x x x
j =. Определить (
)
x
j, если а) \
f Î
1 0
T T
; б) \
f Î
0 1
T T
; в) f
Î
S
; г) f
Î È
1
T S
. 2.81. Какие из указанных ниже систем функций являются замкнутыми классами: а) функции от одной переменной; б) функции от двух переменных; в) линейные функции; г) самодвойственные функции; д) монотонные функции; е) функции, сохраняющие ноль; ж) функции, сохраняющие единицу; з) функции, сохраняющие и ноль, и единицу; и) функции, сохраняющие ноль, но не сохраняющие единицу? 2.82. Является ли объединение функционально замкнутых классов функционально замкнутым классом? 2.83. Доказать, что функцию f
нельзя реализовать формулой над множеством связок S
, если: а) f x y
=, {
}
,
S
= Ú ®
; PDF created with pdfFactory Pro trial version www.pdffactory.com
б) f x y
= Ú
, {
}
,
S
= « Å
; в) (10100011)
f =, {
}
,
S
= Ù Ú
; г) f x y
= ®, {
}
,
S
= « Ø
; д) (10000101)
f =, {
}
,
S
= Ø Å
; е) 1
f x y z
= Å Å Å
, {
}
,
S
= Ù Ú
. 2.84. Доказать, что: а) [
]
,
x y x y
= Ú Å
0
T; б) [
]
x y
Ç = Å
0
T L. 2.85. Используя теорему о полноте двух систем, доказать полноту системы булевых функций: а) {,}
x x y
®; б) {
}
1,,
xy x y
Å; в) {
}
1,,
x y x y
Ú Å; г) {
}
1
x y yz
Å Å Å. 2.86. С помощью теоремы Поста проверить на полноту систему булевых функций: а) {,,}
xy x y x y
Ú ®; б) {,}
x y x yz
® ®; в) {,0,1}
xy xz yzÚ Ú; г) {,,}
x y x x y
« ®; д) {,,1}
xy x y x y zÚ Å Å Å; е) ( )
(
)
{0,}
x xy z
®; ж) {,}
x y xy z
® Å; з) (
)
{,,0}
x y x z xy« ® ®. 2.87. Определить, является ли базисом система булевых функций: а)
{(0010),(10110011),(00101011)}
; б) (
)
{,,}
x y x y xy x y
« Ú Å Ú. 2.88. Перечислить все базисы, которые можно выделить из системы функций {0, x
, x
, x y
Ù
, x y
Ú
, x y
®
, x y
«
, x y
, x y
¯
, x y
Å
, 1}. 2.89. Привести пример базиса из четырех функций. 2.90. Доказать, что базис не может содержать более четырех функций. PDF created with pdfFactory Pro trial version www.pdffactory.com
3. Теория графов 1. Основные понятия. Граф G
(неориентированный) – это пара множеств (,),
G V E
= где ( )
V V G
= – множество вершин, ( )
E E G
= – множество рёбер, причём ребро ( )
e E G
Î представляет собой неупорядоченную пару вершин: (,),
e x y
= где ,( )
x y V G
Î и .
x y
¹
Множество V
предполагается конечным, а значит, и множество E
конечно. Граф изображают на плоскости так: вершины изображаются точками плоскости, а рёбра (,)
e x y
= – линиями, соединяющими вершины x
и .
y
Две вершины v
и v
¢
графа G
называются смежными, если (,) ( )
v v E G
¢
Î. Рёбра называются смежными, если они имеют общую вершину. Вершина v
инцидентна ребру ,
e
если (,)
e v x
= для некоторого .
x
Подграф H
графа G
– это пара ( ( ),( )),
H V H E H
= где ( ) ( )
V H V G
Í и ( ) ( ).
E H E G
Í Некоторые обобщения понятия графа: а) обобщённый граф – это множество вершин V
и рёбер ,
E
причём допускаются петли, т.е. рёбра вида (,),
a a
и кратные рёбра, т.е. две вершины a
и b
могут соединяться не одним, а несколькими рёбрами; б) бесконечный граф (т.е. ( )
V G
– бесконечное множество). Ориентированный граф (,)
G V E
= определяется аналогично обычному, но его рёбра (,)
e x y
= являются упорядоченными парами вершин. Два графа G
и G
¢
называются изоморфными, если существует взаимно однозначное отображение :( ) ( )
V G V G
j
¢
® такое, что ,( )
x y V G
"Î (,) ( ) ( ( ),( )) ( ).
x y E G x y E G
j j
¢
Î Û Î Отображение j
называется изоморфизмом. Пусть G
– граф, 1
( ) {,,},
n
V G v v
= K 1
( ) {,,}.
m
E G e e
= K Матрица смежности графа G
– это матрица ij
A a
= р азмера ,
n n
´
причём {0,1}
ij
a Î и 1 (,) ( ).
ij i j
a v v E G
= Û Î Матрица инцидентности – это матрица ij
b
размера ,
n m
´
причём {0,1}
ij
b Î и 1
ij
b
=
в том и только том случае, если вершина i
v
инцидентна ребру .
j
e
Для обобщённых графов, а также ориентированных графов матрицы смежности и инцидентности определяются похожим образом. Граф называется двудольным, если множество V
его вершин можно разбить на два непересекающиеся подмножества 1
V
и 2
V
такие, что 1 1
( ) ( )V V E G
´ Ç = Æ
и 2 2
( ) ( ).
V V E G
´ Ç = Æ
Стандартные обозначения некоторых графов: n
K
или n
F
(полный граф) – граф с n
вершинами, в котором любые две вершины смежны; n
C
(цепь) – граф с вершинами 1,2,,,
n
K и р ёбрами (1,2), (2,3), …, ( 1,);
n n
- n
Z
(цикл) – граф с вершинами 1,2,,,
n
K и р ёбрами (1,2), (2,3), …, ( 1,),
n n
- (,1);
n
,
m n
K
(полный двудольный граф) – граф, в котором 1 2
( ),
V G V V
= È причём 1 2
V V
Ç = Æ
и 1 2
( );
E G V V
= ´ n
B
(п-мерный куб
) – граф, вершинами которого являются строчки 1
(,,)
n
e e
K из 0 и 1, причём две вершины смежны в том и только том случае, если строчки отличаются ровно одним элементом. Прямое произведение G H
´
графов G
и H
– это граф, у которого ( ) ( ) ( )
V G H V G V H
´ = ´, причём вершины (,)
x y
и (,)
x y
¢ ¢
смежны в том и только том случае, если либо x x
¢
=
и (,) ( )
y y E H
¢
Î, либо y y
¢
=
и (,) ( ).
x x E G
¢
Î Степень вершины графа (обозначается: deg,
v
где ( )
v V G
Î ) – количество рёбер, инцидентных данной вершине. Известно, что ( )
deg 2
Р,
v V G
v
Î
=
å
где Р
ММколичество рёбер графа. Вершина степени 0 называется изолированной, а вершина степени 1 – висячей. Дополнением G
графа G
называется граф с тем же множеством вершин, что и ,
G
причём две вершины смежны в G
тогда и только тогда, когда они не смежны в .
G
Упражнения 3.1. Изобразить граф с заданным множеством вершин и рёбер: а) вершины – числа 1,2,3,4,5,6, рёбра – пары (,)
i j
такие, что Í Î Ä(,) 1
i j
=
; б) вершины – грани куба, рёбра соединяют вершины графа, соответствующие смежным граням куба; в) вершины – грани куба, рёбра соединяют вершины графа, соответствующие противоположным граням куба; PDF created with pdfFactory Pro trial version www.pdffactory.com
г) вершины – рёбра тетраэдра, рёбра соединяют вершины графа, соответствующие смежным рёбрам тетраэдра; д) вершины – булевы функции от двух переменных, рёбра соединяют функции (,)
f x y
и (,),
g x y
если выполнено тождество (,) (,);
f x y g x y x
+ =
е) вершины – подмножества множества {,,},
a b c
рёбра соединяют подмножества, имеющие пустое пересечение. 3.2. Какие из графов предыдущей задачи изоморфны друг другу? 3.3. Построить граф по его матрице смежности: а) 0 1 0 0
1 0 1 1
;
0 1 0 0
0 1 0 0
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
è ø
б) 0 1 0 0
1 0 1 1
;
0 1 0 1
0 1 1 0
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
è ø
в)
0 1 0 0 1
1 0 1 1 0
;
0 1 0 1 1
0 1 1 0 1
1 0 1 1 0
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
è ø
г) 0 1 0 1 1 0
1 0 0 0 1 0
0 0 0 0 0 1
.
1 0 0 0 0 0
1 1 0 0 0 0
0 0 1 0 0 0
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
è ø
3.4. Построить граф по его матрице инцидентности: а) 1 0 0 0 0
1 0 0 0 0
0 1 1 0 0
;
0 0 1 1 1
0 1 0 1 0
0 0 0 0 1
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
è ø
б)
1 0 0 0
1 1 0 0
;
0 1 1 1
0 0 1 0
0 0 0 1
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
è ø
в) 1 0 0
0 1 0
0 0 1
.
1 0 0
0 1 0
0 0 1
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
è ø
3.5. Построить матрицу смежности графа: 3.6. Построить матрицу инцидентности графа: 3.7. Построить обобщённый граф по его матрице смежности: а) 0 2 0 0
2 0 1 3
;
0 1 0 1
0 3 1 0
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
è ø
б) 1 0 1 0 0
0 1 1 0 0
.
1 1 0 2 1
0 0 2 2 0
0 0 1 0 0
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
è ø
3.8. Построить матрицу смежности обобщённого графа: 1
2
3
4
б
)
1
2
3
4
а)
1
2 3
4
в
)
2 3
4
5
г
)
1
1
2
3
4
а
)
e
1
e
2
e
3
e
4
2 3
4
5
б
)
e
4
e
3
e
5
1
e
2
e
1
2 3
4
5
6
в
)
e
5
e
3
e
4
1
e
2
e
1
PDF created with pdfFactory Pro trial version www.pdffactory.com
3.9. Построить ориентированный граф по его матрице смежности: а) 0 1 0 0
0 0 0 0
;
0 1 0 1
0 1 0 0
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
è ø
б) 0 0 0 0 0
1 0 0 1 0
.
1 0 0 1 1
0 0 0 0 0
0 0 0 0 0
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
è ø
3.10. Построить матрицу смежности ориентированного графа: 3.11. Изобразить графы: а) 3 3
;
C C
´ б) 4 2
;
F C
´ в) 3,4
;
K г) 3 3
.
Z Z
´ 3.12. При каких a
и b
матрица 0 1 0 0
0 0 1 1
1 0 1
0 1 0
a
b
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
è ø
является матрицей смежности некоторого графа? 3.13. При каких a
и b
матрица 1 0 1 0 1
0 1 1 0 0
0 1 0 1 1
0 1 0
a b
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
è ø
является матрицей инцидентности некоторого графа? 3.14. Дана матрица смежности ij
a
некоторого обобщённого графа. Найти количество петель в этом графе. 3.15. Сколько компонент связности имеет граф, заданный своей матрицей смежности: а) 0 0 0 1 0
0 0 1 0 1
;
0 1 0 0 1
1 0 0 1 0
0 1 1 0 0
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
è ø
б) 0 0 0 0 1
0 0 0 1 0
;
0 0 0 0 0
0 1 0 0 0
1 0 0 0 0
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
è ø
в) 0 0 1 1 0
0 0 1 0 0
1 1 0 1 1
1 0 1 0 0
0 0 1 0 0
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
è ø
? 3.16. Изобразить граф, являющийся дополнением к данному графу: 2. Пути и циклы. Связные графы. Компоненты связности. Путь в графе G
– это последовательность рёбер вида 1 2
(,),
x x
2 3
(,),
x x
…, 1
(,).
т т
x x
-
Простой путь – путь, в котором вершины 1 2
,,,
n
x x x
K р азличны. Цикл – путь, в котором начальная и конечная вершины совпадают. Простой цикл – цикл, в котором вершины 1 2 1
,,,
n
x x x
-
K р азличны. Граф G
называется связным, если для любых двух вершин существует путь, их соединяющий. Любой граф G
разбивается на связные подграфы 1
,,
k
G G
K, 1
б
)
2
3
1
2
3
4
а
)
1
2
3
4
5
а
)
1
б
)
3
2
4
5
а
)
б
)
PDF created with pdfFactory Pro trial version www.pdffactory.com
обладающие свойством: не существует рёбер, соединяющих вершины из различных подграфов i
G
. Подграфы 1
,,
k
G G
K называются компонентами связности графа .
G
Эйлеров путь (цикл) – это путь (цикл), проходящий через все рёбра графа, причём каждое ребро проходится ровно один раз. Эйлеров путь в связном графе существует в том и только том случае, если ровно две вершины имеют нечётные степени, а остальные – чётные; эйлеров цикл существует тогда и только тогда, когда все вершины имеют чётные степени. Гамильтонов путь (цикл) – это путь (цикл), обходящий все вершины графа, причём каждая вершина проходится ровно один раз. Расстоянием (,)
d a b
между вершинами a
и b
графа G
называется длина кратчайшего пути, соединяющего вершины a
и b
(напомним, что длина пути – это количество рёбер). Если не существует пути между a
и b
, то (,).
d a b
= ¥
Диаметром ( )
d G
связного графа G
называется наибольшее расстояние между вершинами этого графа: ( ) max{ (,) |,( )}.
d G d x y x y V G
= Î Радиусом ( )
r G
графа G
назовём число ( ) min max (,).
x y
r G d x y
=
В ершина ,
a
для которой ( ) max (,)
y
r G d y a
=
, называется центром графа G
. Упражнения 3.17. Каких графов на заданном множестве вершин V
больше: связных или несвязных, если | | 3
V
³
? 3.18. Сколько компонент связности имеет граф G
, у которого ( ) {1,2,,100},
V G = K ( ) {(,):| | 3}
E G i j i j
= - =
? 3.19. Сколько всего неизоморфных графов, у которых: а) 10 вершин и 3 ребра; б) 11 вершин и 53 ребра; в) 13 вершин и 77 рёбер? 3.20. Доказать, что любой граф можно изобразить в трёхмерном пространстве так, чтобы рёбра являлись отрезками прямых и эти отрезки не имели общих внутренних точек. 3.21. Назовём ориентированный граф бесконтурным, если в нём нет замкнутых ориентированных путей (контуров). Доказать, что в бесконтурном графе можно так занумеровать вершины, что матрица смежности будет верхней треугольной. 3.22. Назовём ориентированный граф сильно связным, если для любых двух вершин a
и b
существует ориентированный путь из a
в .
b
Верно ли, что в сильно связном графе существует простой ориентированный путь, обходящий все вершины? 3.23. В произвольном ориентированном графе G
для вершин a
и b
положим ~,
a b
если существуют пути из a
в b
и из b
в .
a
Доказать, что ~ – отношение эквивалентности (на множестве вершин), а подграфы, соответствующие классам эквивалентности, сильно связные (определение см. в предыдущей задаче). Они называются сильно связными компонентами графа. Обозначим через G
граф, вершинами которого являются сильно связные компоненты графа G
и из вершины a
в вершину b
(
,( )
a b V G
Î ) идёт ребро в том и только том случае, если существуют вершины ,
x y
графа G
такие, что ,
x a
Î
y b
Î
и (,) ( ).
x y E G
Î Доказать, что граф G
бесконтурный. 3.24. Доказать, что любые две цепи максимальной длины в связном неориентированном графе имеют хотя бы одну общую вершину. 3.25. Назовём расстоянием (,)
d a b
между вершинами a
и b
графа G
длину кратчайшего пути, соединяющего вершины a
и b
(напомним, что длина пути – это количество рёбер). Если не существует пути между a
и b
, то (,).
d a b
= ¥
Доказать, что расстояние (,)
d a b
удовлетворяет аксиомам метрики, т.е.: (1) (,) 0,
d a b
³
(,) 0
d a b
=
Û
.
a b
=
(2) (,) (,) (,)
d a c d a b d b c
£ +, (3) (,) (,).
d b a d a b
= 3.26. Найти расстояние (в смысле предыдущей задачи) между вершинами (1,0,0,1,1)
и (0,1,0,1,0)
5-
мерного куба 5
.
B
3.27. Написать формулу расстояния (в смысле теории графов) между вершинами 1 2
(,,,)
n
e e e
K и 1 2
(,,,)
n
h h h
K n
-мерного куба n
B
(оно называется расстоянием Хэмминга). 3.28. Какие значения принимает расстояние (в смысле теории графов) между вершинами: а) куба 4
B
; б) икосаэдра; в) додекаэдра; г) графа 3 4
B B
´
; д) 5 6
C C
´
? 3.29. Назовём диаметром ( )
d G
связного графа G
наибольшее расстояние между вершинами этого графа: ( ) max{ (,) |,( )}.
d G d x y x y V G
= Î Вычислить диаметры следующих графов: PDF created with pdfFactory Pro trial version www.pdffactory.com
а) n
K
; б) ,
m n
K
(,2)
m n
³
; в) m n
C C
´
; г) n
B
; д) G
– октаэдр. 3.30. Верно ли, что диаметры графов обладают свойством ( ) ( ) ( )
d G H d G d H
´ = +? 3.31. Найти диаметр графа G
, заданного множеством вершин ( ) {1,2,3,4,5,6,7,8} V G = и множеством рёбер ( )
E G
=
{
(1,2),
(1,4),
(2,4),
(2,5),
(3,6),
(4,7),
(4,8),
(5,6),
(5,8)
}. 3.32. Радиусом ( )
r G
графа G
назовём число ( ) min max (,).
x y
r G d x y
=
Вершину ,
a
для которой ( ) max (,)
y
r G d y a
=
, назовём центром графа G
. Для графа, изображённого на рисунке, найти диаметр, радиус и все центры. 3.33. Найти радиусы следующих графов: а) n
B
; б) n
K
; в) ,
m n
K
(
m n
£
). 3.34. Найти радиус и все центры графа: а) n
C
; б) n
Z
. 3.35. Найти количество вершин и количество рёбер графа: а) 3 3
B B
´
; б) икосаэдра; в)
m n
C Z
´
; г) m n
Z Z
´
. 3.36. Доказать, что m n m n
B B B
+
´ @. 3.37. Найти эйлеров путь в графе с вершинами 1,2,3,4,5
и рёбрами (1,2),
(1,3),
(1,4),
(1,5),
(2,3),
(3,4),
(3,5),
(4,5).
3.38. Существует ли эйлеров путь или эйлеров цикл в графе: а) 4,6
K
; б) 3
B
; в) 4
B
; г) m n
C C
´
; д) додекаэдре? 3.39. В каких графах вида ,
m n
K
существует: а) эйлеров путь, б) эйлеров цикл? 3.40. Найти эйлеров путь в графе, изображённом на рисунке: 3.41. Найти эйлеров цикл графа, изображённого на рисунке: 3.42. Граф G
задан множеством вершин и рёбер. Выяснить, имеет ли G
гамильтонов путь или цикл: 5 4
2 3
6
1
в
)
а
)
1
5
2 6
3 7
4 8 9
6
7
5 8
2 3
1
4
б
)
6
5
4
2 3
1
а)
2
1
3
4
5
6 7
8 9
1
0
б)
1
2 3
4 5 6
7
8
9
0
PDF created with pdfFactory Pro trial version www.pdffactory.com
а) ( ) {1,2,3,4,5,6,7,8,9},
V G = ( )
E G
=
{(1,3), (1,4), (2,3), (2,6), (3,4), (3,5), (4,8), (5,7), (6,7), (7,8), (8,9)}; б) ( ) {1,2,3,4,5,6,7,8},
V G = ( )
E G
=
{(1,2), (1,7), (2,3), (2,4), (2,5), (3,6), (4,7), (5,6), (6,7), (6,8), (7,8)}. 3.43. В каких графах вида ,
m n
K
существует: а) гамильтонов путь, б) гамильтонов цикл? 3.44. Доказать, что в графе, изображённом на рисунке, нет гамильтонова пути. Какие рёбра следует добавить, чтобы в графе появился гамильтонов путь? Каково наименьшее число рёбер, добавление которых приведёт к существованию гамильтонова цикла? 3.45. Доказать, что если в графе есть вершина, после удаления которой граф распадается на 3 или более компонент связности, то у него не может быть гамильтонова пути или цикла.
3. Деревья. Кодирование деревьев. Деревом называется связный граф без циклов. Количество вершин В и количество рёбер Р любого дерева связаны соотношением Р В 1.
= -
Каждому дереву, имеющему n
рёбер, можно поставить в соответствие последовательность из 0 и 1 (двоичный, или бинарный код дерева). В бинарном коде будет ровно m
нулей и m
единиц, где m
– количество рёбер дерева. Построение бинарного кода осуществляется следующим образом: производится обход рёбер графа так, чтобы граф оставался всё время справа; при прохождении “нового” ребра (ребра, которое ещё не проходилось) пишем 0, при прохождении старого ребра пишем 1. Ещё одним методом кодирования дерева является построение кода Прюфера (кода из натуральных чисел). Пронумеруем вершины дерева произвольным образом. Возьмём висячую вершину с наименьшим номером и запишем в код номер смежной с ней вершины; затем удалим висячую вершину вместе с ребром. Будем повторять этот процесс. В результате получим код Прюфера. Упражнения 3.46. Сколько всего неизоморфных деревьев с 7 вершинами, из которых 3 висячие? 3.47. а) На окружности даны 4 точки. Эти точки соединяются отрезками прямых так, чтобы получилось дерево, но при этом никакие два отрезки не имеют общих внутренних точек. Сколько всего таких деревьев? Сколько из них неизоморфных? б) Решить аналогичную задачу для 5 точек. 3.48. Построить бинарный код дерева (направление обхода показано на рисунке): 3.49. Какие из следующих комбинаций цифр являются кодами дерева: а) 00011010110111; б) 0000100111100111; в) 00010111100110101; г) 000111001101001011? 3.50. Построить дерево по его бинарному коду: а) 00100101011011; б) 000110100000011011011111; 7 4 2
1
8
5
6
3
а
)
б
)
в
)
PDF created with pdfFactory Pro trial version www.pdffactory.com
в) 001001010101011011. 3.51. Доказать, что количество неизоморфных деревьев с n
рёбрами не превосходит 4.
n
3.52. Построить код Прюфера дерева для заданной нумерации его вершин: 3.53. Построить дерево по его коду Прюфера: а) 1 4 1 4 7 4; б) 5 6 7 5 7 6 8 5 6 9; в) 6 6 7 7 6 7 9 6 7 1 0. 4. Цикломатическое число графа. Пространство циклов. Цикломатическим числом графа G
называется число ( )
Р В К,
Gn
= - +
где Р – количество рёбер, В – количество вершин, К – количество компонент связности. Циклом (в широком смысле) мы будем называть обычный цикл или объединение непересекающихся обычных циклов. Сложение циклов осуществляется путём удаления общих рёбер циклов и объединения оставшихся рёбер. При так определённом сложении все циклы будут образовывать линейное пространство над полем из двух элементов – пространство циклов. Оказывается, что размерность пространства циклов равна цикломатическому числу. Кроме того, если цикломатическое число графа равно ,
k
то из графа можно удалить k
рёбер (специальным образом подобранных) так, что циклов в нём не останется, а количество компонент связности останется прежним. Лес – граф без циклов. Необходимое и достаточное условие того, чтобы граф G
был лесом, – это равенство ( ) 0.
Gn
=
Упражнения 3.54. Найти цикломатическое число графа: а) 4
B
; б) ,
m n
K
; в) m n
Z Z
´
. 3.55. Выяснить, существует ли граф со следующим набором степеней вершин: а) 1, 1, 1, 1, 2, 2, 3, 3, 3; б) 1, 1, 1, 2, 2, 2, 3, 3, 3; в) 1, 1, 2, 3, 3, 4, 4. 3.56. Найти цикломатическое число ( )
G
n графа ,
G
если: а) 5
;
G K
= б) ,
;
m n
G K= в) 4
;
G B
= г) ;
m n
G C C
= ´ д) G
– октаэдр; е) G
– икосааэдр. 3.57. Пусть 1
G
, 2
G
, … , k
G
– компоненты связности графа G
. Доказать, что ( ) ( )
1
k
i
i
v G v G
=
=
å
. 3.58. Дан связный граф .
G
Чему равно наименьшее натуральное число k
такое, что удаление любых k
рёбер делает граф несвязным? а
)
1
2
3
7
4
5
6
8
9
б)
3
1 2 4 5
6
7
8
9
в
)
1
4 5 6 3
7
8 9 10 1
1
2
PDF created with pdfFactory Pro trial version www.pdffactory.com
3.59. Чему равно наименьшее натуральное число k
такое, что в графе ,
m n
K
найдутся k
рёбер, удаление которых сделает делает граф несвязным? 3.60. Сколько рёбер может быть у графа, имеющего 15 вершин и состоящего из 3 компонент связности? 3.61. Сколько компонент связности может иметь граф, у которого 10 вершин и 30 рёбер? 3.62. Найти наибольшее количество рёбер, которое может иметь несвязный граф с n
вершинами. 3.63. Доказать, что удаление ребра графа увеличивает количество компонент связности в том и только том случае, если это ребро не входит ни в один цикл. 3.64. Построить какой-нибудь базис пространства циклов графа, изображённого на рисунке 3.65. В графе 3,3
K
взят цикл 1
(1436).
C = Дополнить его до базиса пространства циклов. 3.66. Сколько циклов входит в базис пространства циклов графа ,
G
у которого 15 вершин, 25 рёбер, 4 компоненты связности? 3.67. Чему равна размерность пространства циклов графа G
и сколько в графе G
всего обобщённых циклов, если: а) 5
;
G K
= б) 10
;
G K
= в) 4
G B
=
? 3.68. Найти количество компонент связности леса, имеющего: а) 20 вершин и 10 рёбер; б) 25 вершин и 11 рёбер. 3.69. Сколько вершин может иметь лес, у которого 20 рёбер? 3.70. Доказать, что любое неодноэлементное дерево имеет не менее двух висячих вершин. 3.71. Сколько рёбер следует удалить из графа ,
G
чтобы получилось дерево, если: а) 8
;
G K
= б) 5,6
;
G K= в) 4 4
G Z Z
= ´
? 5. Раскрашивание графов. Хроматическим числом ( )
G
c графа G
называется наименьшее число красок, необходимых для правильного раскрашивания вершин графа (при правильном раскрашивании смежные вершины должны быть окрашены в разные цвета). Граф G
называется бихроматическим, если ( ) 2.
Gc
£
Оказывается, что для любого графа G
эквивалентны условия: (1) G
бихромаптический, (2) G
двудольный, (3) G
не имеет циклов нечётной длины. Рёберным хроматическим числом Р
( )
G
c графа G
называется наименьшее количество красок для правильного раскрашивания рёбер графа (при правильном 3 4 5
7 8 а
)
1
2
6
9
1
0
1
2
3 4
5 6
7
8
б
)
1
2
3
4
5
6
PDF created with pdfFactory Pro trial version www.pdffactory.com
раскрашивании смежные рёбра должны быть окрашены в разные цвета). Пусть ( )
Δ( ) max deg.
v V G
G v
Î
=
Имеет место теорема Визинга: Р
Δ( ) ( ) Δ( ) 1.
G G Gc
£ £ +
Упражнения 3.72. Найти хроматическое число ( )
G
c графа G
, изображённого на рисунке 3.73. Найти хроматическое число ( )
G
c графа G
: а) ;
n
G B
= б) ;
n
G Z
= в) ,
;
m n
G K= г) G
– дерево. 3.74. Найти хроматическое число и привести пример правильной раскраски графа: а) октаэдра; б) 4 2
;
K C
´ в) 3 3
.
Z Z
´ 3.75. Верно ли, что ( ) max ( ( ),( ))?
G H G Hc ´ = c c 3.76. Найти рёберное хроматическое число P
( )
G
c и указать какую-нибудь правильную раскраску рёбер графа: а) куба 3
;
B
б) октаэдра, в котором проведена диагональ основания; в) додекаэдра. 3.77. Привести пример какого-нибудь графа ,
G
у которого ( ) 3,
G
D =
а P
( ) 4.
G
c =
6. Планарность. Граф называется планарным, если его можно изобразить на плоскости так, что рёбра не будут пересекаться во внутренних точках. Такое изображение называется плоской укладкой графа. Для связного планарного графа справедлива теорема Эйлера: В Г Р 2,
+ = +
где В – число вершин графа, Р – число рёбер, Г – число граней, т.е. областей, на которые граф разбивает плоскость. Связный планарный граф без висячих рёбер называется картой. Карта имеет несколько ограниченных областей и одну неограниченную (называемую океаном). Каждой карте G
можно поставить в соответствие сопряжённый граф G
*
(вообще говоря, он может оказаться обобщённым графом, так как может иметь кратные рёбра). Сопряжённый граф строится следующим образом. В каждой грани карты выбираем по одной точке – это будут вершины графа G
*
; две вершины будем соединять таким количеством рёбер, сколько общих рёбер имеют соответствующие грани. Количества вершин, рёбер и граней графов G
и G
*
связаны соотношениями В Г,
*
=
Р Р,
*
=
Г В.
*
=
Операция разделения ребра для данного графа состоит в том, что внутри ребра берётся любая точка, объявляется новой вершиной графа, а данное ребро заменяется двумя другими. Графы 1
G
и 2
G
называются гомеоморфными, если из них с помощью применения конечного числа раз операции разделения ребра можно получить изоморфные графы. Необходимое и достаточное условие планарности графа даёт теорема Понтрягина – Куратовского: граф планарен тогда и только тогда, когда у него нет подграфов, гомеоморфных графу 5
K
или 3,3
.
K
Упражнения 3.78. Найти количество граней в плоской укладке связного планарного графа ,
G
если: а) G
имеет 13 вершин и 34 ребра; б) ( ) 5?
Gn = а
)
б
)
PDF created with pdfFactory Pro trial version www.pdffactory.com
3.79. Пусть G
– связный связный планарный граф без висячих рёбер (такой граф называется картой). Пусть i
– количество i
-угольных граней в плоской укладке графа .
G
Доказать, что Ã,
i
n
=
å
2Ð 2Â.
i
in = ³
å
3.80. Доказать, что если G
– карта, то ( )
(min deg ) Â.
i
v V G
in v
Î
³ ×
å
В частности, если deg 3
v
³
для всех ( ),
v V G
Î т о 3Â.
i
in ³
å
3.81. Пусть G
– карта, в которой deg 3
v
³
для всех ( ).
v V G
Î Доказать, что Ã 2Â 4.
£ -
3.82. Сколько граней может быть в плоской укладке связного планарного графа с 10 вершинами, не являющегося деревом? 3.83. Каково минимальное число рёбер, которое может иметь непланарный граф? 3.84. Выяснить, является ли планарным граф: а) октаэдр; б) октаэдр, в котором добавлено ребро, соединяющее две противоположные вершины; в) граф 5
,
K
из которого удалено ребро; г) 3 3
;
Z C
´ д) 3 3
;
Z Z
´ е) 4
;
B
ж) граф 6
,
K
из которого удалены три попарно смежных ребра. 3.85. При каких ,
m n
граф ,
m n
K
является планарным? 3.86. Связный планарный граф без петель, висячих вершин и кратных рёбер имеет 6 вершин. Сколько рёбер может иметь этот граф? Изобразить какой-нибудь граф с максимальным количеством рёбер. 3.87. Связный планарный обобщённый граф (т.е. допускаются кратные рёбра) без петель и висячих вершин имеет 16 рёбер. Сколько граней может быть в плоской укладке этого графа? 3.88. Связный планарный обычный граф без висячих вершин имеет 16 рёбер. Сколько граней может быть в плоской укладке этого графа? (Напомним, что обычный граф не имеет петель и кратных рёбер). Изобразить граф, удовлетворяющий условиям задачи и имеющий максимальное число граней. 3.89. Для графа, изображённого на рисунке, изобразить сопряжённый (обобщённый) граф: 7. Потоки в сетях. Сеть – это связный ориентированный граф, каждое ребро (,)
x y
которого помечено неотрицательным числом (,),
c x y
называемым пропускной способностью ребра; кроме того, выделены две вершины: s
(источник) и t
(сток). Поток в сети – это совокупность действительных чисел (,),
f x y
поставленных в соответствие рёбрам (,)
x y
сети, и числа v
(величины потока), если выполнены условия: (1) 0 (,) (,);
f x y c x y
£ £ (2) , если ,
(,) (,) 0, если ,,
, если . x y
v a s
f a x f y a a s t
v a t
=
ì
ï
- = ¹
í
ï
- =
î
å å
Требуется найти поток, имеющий максимальную величину .
v
Разрезом называется разбиение множества всех вершин N
на два подмножества: N X X
= È
т аких, что ,
s X
Î
.
t X
Î
Пропускной способностью разреза называется число ,
(,) (,).
x X
y X
c X X c x y
Î
Î
=
å
Для любого разреза (,)
X X
и любого потока имеет место неравенство (,).
v c X X
£ Таким образом, если мы найдём такой разрез (,)
X X
и т акой поток { (,) | (,) }
f x y x y E
Î, величина которого удовлетворяет условию (,),
v c X X
= т о поток будет а
)
б
)
PDF created with pdfFactory Pro trial version www.pdffactory.com
максимальным. Теорема Форда – Фалкерсона утверждает, что такие поток и разрез существуют, алгоритм Форда – Фалкерсона позволяет построить максимальный поток. Доказательство максимальности потока обычно осуществляют с помощью разреза. Упражнения 3.90. Найти максимальный поток сети, указать какой-нибудь минимальный разрез: 3.91. Какому условию должна удовлетворять пропускная способность ребра (,),
a t
чтобы величина максимального потока приняла наибольшее значение? Чему равно это значение? а
)
s
t
6 2
5
6
6
7
5 4 1 2 2 3
б
)
s t
5 4 2 3
4
4 5 3 8 2
2
6 5 s t
a
c
b
5 x 3 5
3 1
2 4
4 3
PDF created with pdfFactory Pro trial version www.pdffactory.com
4. Автоматы 1. Понятие конечного автомата. Конечным автоматом называется пятёрка (,,,,),
V A Q B
= j y
где ,,
A Q B
– конечные множества, а :
Q A Q
j ´ ®
и :
Q A B
y ´ ®
– отображения. Отображение j
называется функцией переходов, а отображение y
– функцией выходов. При этом равенство (,)
q a q
¢
j =
означает, что если автомат V
находится в данный момент времени в состоянии q
и на его вход пришёл символ ,
a
то к следующему моменту времени он перейдёт в состояние .
q
¢
Далее, равенство (,)
q a b
y =
означает, что если текущее состояние автомата есть ,
q
а на вход поступил символ ,
a
то на выход будет послан символ .
b
Работа автомата описывается системой канонических уравнений: (
)
( )
( 1) ( ),( ),
( ) ( ),( ),
q t q t a t
b t q t a t
+ = jì
ï
í
= y
ï
î
которая должна быть дополнена начальным условием 0
(0).
q q
= Здесь 0
(0)
q q Q
= Î
– начальное, или инициальное состояние. Замечания. 1. Автомат (,,,,),
V A Q B
= j y
в котором выделено начальное состояние 0
,
q Q
Î называют инициальным автоматом. Иногда у автомата V
выделяют одно или несколько состояний (скажем, q Q
*
Î
), называемых конечными, или финальными состояниями. Смысл их состоит в том, что если автомат «попадёт» в состояние ,
q
*
то он прекращает свою работу. Можно рассматривать вероятностные, или стохастические автоматы, т.е. такие, в которых переход из одного состояния в другое и формирование выходного символа осуществляются не по жёстко заданному правилу, а с некоторой вероятностью, закон распределения которой должен быть указан. В отличие от вероятностных автоматов обычные автоматы называют детерминированными. Многие утверждения, касающиеся автоматов, справедливы и без предположения о том, что ,,
A B Q
– конечные множества. Назовём абстрактным автоматом пятёрку (,,,,),
V A Q B
= j y
где функции j
и y
определяются так же, как и раньше, т.е. :,
Q A Q
j ´ ®
:,
Q A B
y ´ ®
но множества ,,
A B Q
могут быть бесконечными. Пример 1. Автомат без памяти. Таким автоматом называется автомат, в котором множество состояний состоит в точности из одного элемента. В этом случае функцию j
можно не рассматривать, а функция y
зависит только от пришедшей на вход автомата буквы входного алфавита. Канонические уравнения автомата выглядят здесь так: ( ) ( ( )).
b t a t
= y Так, в частности, работает автомат, который осуществляет перекодировку символов одного алфавита в другой (если при этом одна буква заменяется на одну). Пример 2. Элемент задержки. Здесь входной и выходной алфавиты совпадают: ,
À å
=
а выходной символ представляет собой задержанный на 1 такт входной символ: ( 1) ( )
b t a t
+ = при всех 0.
t
³
Пусть 1
{,...}.
n
Q a a
= Тогда полагаем: (,),
q a a Q
j = Î
(,).
q a q B
y = Î
Текущее состояние “запоминает” поступившую букву входного алфавита, а выходной буквой является предыдущее состояние, т.е. «запомненная» буква. a(i) y(a(i))
П
a(i) b(i)=a(i-1
)
Z
PDF created with pdfFactory Pro trial version www.pdffactory.com
Автоматы (,,,,)
V A Q B
= j y
называются автоматами Мили. Автоматом Мура (автоматом без выхода) называется тройка (,,),
V A Q
= j
г де ,
A Q
– множества, а :
Q A Q
j ´ ®
– отображение. Множества A
и Q
называются соответственно входным алфавитом и множеством состояний. Функция j
называется функцией переходов. Равенство (,)
q a q
¢
j =
означает, что если автомат находится в состоянии q
и принимает символ а, то должен осуществиться его переход в состояние .
q
¢
В автомате Мили можно «избавиться» от выходного алфавита B
, увеличив соответствующим образом множество состояний .
Q
Пусть дан автомат Мили (,,,,).
V A Q B
= j y
Построим автомат Мура (,,).
V A Q
¢ ¢ ¢ ¢
= j
В качестве множества состояний нового автомата возьмём ,
Q Q B
¢
= ´
входной алфавит сохраним прежним: ,
A A
¢
=
а функцию ¢
j
определим следующим образом: (,) ((,),) ( (,),(,)).
q a q b a q a q a
¢ ¢ ¢
j = j = j y Автомат Мура (,,)
V A Q
¢ ¢ ¢ ¢
= j
эквивалентен автомату Мили (,,,,)
V A Q B
= j y
в том смысле, что V
¢
«работает» так же, как ,
V
но реакцией на входной сигнал является не выходной символ ,
b
а изменённое более сложным образом состояние, в котором фактически “зашифрован” выходной символ .
b
Диаграммой Мура автомата (,,,,)
V A Q B
= j y
называется ориентированный граф, вершинами которого являются состояния q Q
Î
и для каждого равенства вида (,)
a q q
¢
j =
г раф имеет ребро, идущее из q
в ,
q
¢
на котором стоит метка ,,
a b
г де (,).
b q a
= y Из определения конечного автомата и диаграммы Мура следует, что ориентированный граф, рёбра которого помечены символами ,
a b
(
,),
a A b B
Î Î является диаграммой Мура некоторого конечного автомата в том и только том случае, если из каждого состояния i
q
выходило по одной стрелке для каждого символа .
a A
Î
Таблицей автомата (,,,,)
V A Q B
= j y
называется прямоугольная таблица с | |
n Q
= строками и | |
m A
= столбцами, причём в клетке, стоящей на пересечении i
-й строчки и j
-
го столбца написаны символы (,)
i j
q a
j и (,).
i j
q a
y Упражнения 4.1. Выяснить, являются ли графы, изображённые на рисунке, диаграммами Мура некоторого автомата: 4.2. Построить таблицу автомата, заданного диаграммой Мура, изображённого на рисунке. q
1
q
2
q
3
0,1
0,1
0,0
1
,
1
1,0
а
)
q
1
q
2
q
3
a,a
b,a
a,a
b,b
b,a
a,b
в
)
q
1
q
2
q
3
a
,
0
b,0
a,1
b,1
b,1
b,0
б
)
PDF created with pdfFactory Pro trial version www.pdffactory.com
4.3. Автомат задан таблицей 0
1
2 1
q
3
q
2
1
q
1 2 0
0
3
q
1 3
q
3
q
1 3
q
2 1
q
0 Построить диаграмму Мура этого автомата. 4.4. Автомат, у которого {0,1,2},
Q = {0,1},
A B= = задан каноническими уравнениями (,) (mod3),
,2,
(,)
1,2.
q a q a
a åñëè q
q a
a åñëè q
j = +
ì
ï
<
ì
í
y =
í
ï
- =
î
î
Построить диаграмму Мура этого автомата. 2. Продолжение функций переходов и выходов на слова. Пусть 1 2
{,,...}
n
A a a a
= – конечный алфавит. Через A
*
будем обозначать множество всех слов 1 2
....
k
i i i
w a a a
= Число k
называется длиной слова w
и обозначается | |.
w
Например, если {,,},
A a b c
= то ,,,
a ab babc A
*
Î | | 3,
aba
=
| | 1.
c
=
Слово, в котором нет ни одной буквы, будем называть пустым словом и обозначать символом .
l
Очевидно, | | 0.
l =
Пусть m
A
– множество слов длины ,
m
а A
+
– множество непустых слов. Тогда \{ },
A A
+ *
= l
*
0
,
m
m
A A
¥
=
=
U
1
.
m
m
A A
¥
+
=
=
U
Произведением слов ,
w w A
*
¢
Î называется слово, полученное приписыванием к слову w
справа слова .
w
¢
Например, если 1 2
...,
s
i i i
w a a a
= 1 2
...,
t
j j j
w a a a
¢
= то 1 2 1 2
.......
s t
i i i j j j
ww a a a a a a
¢
= Произведение слов ассоциативно, т.е. 1 2 3 1 2 3
( ) ( )
w w w w w w
= для любых 1 2 3
,,.
w w w A
*
Î Произведение слов некоммутативно, так как в общем случае 1 2 2 1
.
w w w w
= Множества A
*
и A
+
являются полугруппами. Кроме того, A
*
– моноид (т.е. полугруппа с единицей), пустое слово l
является единицей. Полугруппа A
+
моноидом не является. Функции :
Q A Q
j ´ ®
и :
Q A B
y ´ ®
продолжаются до функций :
Q A Q
*
j ´ ® и :
Q A B
* *
y ´ ® следующим образом: (,) (,)
q a q a
j = j при ,
a A
Î
(,) ( (,),)
q aw q a w
j = j j при ,
a A
Î
;
w A
+
Î (,) (,)
q a q a
y = y при ,
a A
Î
(,) (,) ( (,),)
q aw q a q a w
y = y y j при ,
a A
Î
;
w A
+
Î (,),
q q
j l =
(,).
q
y l = l
Упражнения 4.5. Автомат задан таблицей a
b
c 1
q
1
q
0
2
q
0
2
q
2
q
2
q
2
q
2
q
q
1
q
2
q
3
a
,
0
b
,
0
q
4
a,1
a,1
b,1
a,1
b,0
b,0
PDF created with pdfFactory Pro trial version www.pdffactory.com
1 1
q
0
1
q
1
1 Определить: 1
(,),
q ab
j 2
(,),
q abc
j 1
(,),
q abca
j 1
(,),
q ba
y 3 2
2
(,).
q a b
y 4.6. Автомат задан диаграммой Мура, изображённой на рисунке. Найти 1
(,001),
qj 3
(,110).
qy 3. Приведенный автомат. Назовём состояния q
и q
¢
автомата (,,,,)
V A Q B
= j y
неотличимыми, если (,) (,)
q w q w
¢
y = y для всех .
w A
+
Î
Состояния q
и q
¢
отличимы, если (,) (,)
q w q w
¢
y ¹ y при некотором .
w A
+
Î
Положим ~,
q q
¢
если q
и q
¢
неотличичимы. Отношение неотличимости ~ на множестве Q
состояний автомата V
является отношением эквивалентности. Это отношение вызывает разбиение множества Q
на непересекающиеся классы эквивалентности: 1 2
....
k
Q Q Q Q
= È È È Множество классов отношения ~ (фактор-множество /~)
Q обозначим через .
Q
)
Построим новый автомат .
V
)
В качестве входного и выходного алфавитов автомата V
)
возьмём те же множества A
и ,
B
которые были у автомата ,
V
а в качестве множества состояний возьмём множество .
Q
)
Определим функции :
Q A Q
j ´ ®
) )
)
и :.
Q A B
y ´ ®
)
)
Пусть ,
q Q
Î
)
)
.
a A
Î
Возьмём какой-нибудь элемент ,
q
принадлежащий классу ,
q
)
и положим (,) (,).
q a q a
j = j
)
)
Это определение корректно, т.е. не зависимо от выбора представителя в классе эквивалентности. Другими словами, если ~,
q q
¢
то (,) ~ (,).
q a q a
¢
j j Функцию y
)
определим на Q
)
по формуле (,) (,).
q a q a
y = y
)
)
Это определение также корректно. Автомат (,,,,)
V A Q B
= j y
)
)
) )
называется приведённым автоматом, соответствующим автомату (,,,,).
V A Q B
= j y
У приведённого автомата любые два различных состояния отличимы друг от друга. Автомат (,,,,)
V A Q B
= j y
и приведённый автомат (,,,,)
V A Q B
= j y
)
)
) )
р аботают одинаково: для любой входной последовательности (1) (2) (3)...
a a a последовательность (1) (2) (3)...
b b b на выходе автомата V
и автомата V
)
одна и та же: (1) (,(1)) (,(1)),
b q a q a= y = y
)
)
(2) (,(1) (2)) (,(1) (2))
b q a a q a a= y = y
)
)
и т.д. (здесь q
– начальное состояние). Теорема. Если входная последовательность конечного автомата является периодической, то выходная последовательность также периодическая, период которой не превышает ,
n
t
где t
– период выходной последовательности, а | |
n Q
= – количество состояний автомата. Отличимость состояний конечного автомата устанавливают обычно с помощью тестирования. А именно, если автомат, находясь в состоянии q
и находясь в состоянии ,
q
¢
будет по-разному реагировать на одну и ту же входную последовательность, то состояния q
и q
¢
отличимы. Естественно возникает вопрос: сколько тестовых последовательностей и каких достаточно для установления неотличимости двух состояний? Ответ лаёт первая теорема Мура: если n
– количество состояний автомата, то для установления отличимости или неотличимости его состояний достаточно подавать 2
q
2
q
q
1
q
2
q
3
0
,
0
1,2
q
4
1,0
0,2
1,0
1,1
0
,1
PDF created with pdfFactory Pro trial version www.pdffactory.com
на вход последовательности длины 1.
n
-
Для двух автоматов V
и ,
V
¢
имеющих одинаковые входные и одинаковые выходные алфавиты, справедлива вторая теорема Мура: для отличимости или неотличимости состояний q
и q
¢
этих автоматов достаточно ограничиться входными последовательностями длины 1,
n n
¢
+ -
где n
и n
¢
– количества состояний автоматов V
и .
V
¢
Приведём теперь пример, показывающий, что для установления отличимости состояний автомата (,,,,)
V A Q B
= j y
с | |
Q n
=
может оказаться недостаточно брать последовательности длины 2,
n
-
т.е. число 1
n
-
в формулировке первой теоремы Мура не может быть уменьшено. Пример 3. Рассмотрим автомат, представленный следующей таблицей: 1
q
3
q
… 1
n
q
-
n
q
0
1
3
q
0
4
q
0
… n
q
0
n
q
0
1
1
1
q
0
0
… 2
n
q
-
0
1
n
q
-
0
Состояния n
q
и 1
n
q
-
отличимы словом 1
11...1.
n-
123
Действительно, {
1
1
(,11...1) 0 0...0,
n
n
n
q
-
-
y =
14243
а {
{
1
1 1
(,11...1) 0...01.
n
n n
q
-
- -
y = В то же время слова длины 2
n
-
эти состояния не отличают, так как если 1 2
,...,{0,1},
n-
e e Î то 1 2 1 1 2
2
(,...) (,...) 0 0...0.
n n n n
n
q q
- - -
-
y e e = y e e =
14243
Упражнения 4.7. Построить приведённый автомат для автомата, заданного диаграммой Мура, изображённой на рисунке. 4.8. Построить приведённый автомат для автомата V
, заданного следующей таблицей: 1
q
3
q
4
q
5
q
0
3
q
1
1
q
1
4
q
0
1
q
1
1
q
1
1
4
q
1
5
q
0
3
q
1
4
q
0
4
q
0
4. Детерминированные и ограниченно-детерминированные функции. Пусть A
– множество. Каждую бесконечную последовательность (1) (2) (3)...,
a a a где ( ),
a i A
Î
будем называть сверхсловом. Обозначим через A
¥
множество всех таких сверхслов. Пусть ,
A B
– два конечных множества, их мы будем называть алфавитами. Рассмотрим отображение :.
f A B
¥ ¥
® Это отображение можно интерпретировать как воображаемое устройство, перерабатывающее сверхслова в алфавите A
в сверхслова в алфавите B
. 2
q
2
q
2
q
2
q
2
q
q
1
q
2
q
4
0,1
0,1
q
5
0,0
1,0
0,1
1,1
q
3
1,1
0,1
1,0
1
,
0
PDF created with pdfFactory Pro trial version www.pdffactory.com
Функция :
f A B
¥ ¥
® н азывается детерминированной, если выполнено условие: для любого i
и для любых сверхслов (1) (2) (3)...,
w a a a= (1) (2) (3)...,
w a a a
¢ ¢ ¢ ¢
= если ( ) (1) (2) (3)...,
f w b b b= ( ) (1) (2) (3)...
f w b b b
¢ ¢ ¢ ¢
= и (1) (1),...,( ) ( ),
a a a i a i
¢ ¢
= = то ( ) ( ).
b i b i
¢
= С множеством A
¥
можно связать некоторое бесконечное дерево .
T
Пусть 1 2
{,,...,}.
m
A a a a
= Возьмём любую точку и назовём её корнем дерева. Из корня выпустим m
рёбер, концы которых назовём вершинами первого яруса. Из каждой вершины первого яруса выпустим m
рёбер, которые назовём вершинами второго яруса. Ветви дерева T
(бесконечные) соответствуют сверхсловам (1) (2) (3)...,
a a a A
¥
Î п ричём это соответствие взаимно однозначное. Будем считать, что рёбра, соответствующие буквам алфавита 1 2
{,,...,},
m
A a a a
= и дут слева направо (т.е. крайнее левое ребро соответствует букве 1
,
a
следующее – букве 2
,
a
крайнее правое – букве ).
m
a
На рисунке изображено дерево, построенное для трёхбуквенного алфавита {,,}.
A a b c
= Ветвь дерева, отмеченная жирной линией, соответствует сверхслову ...,
abcb
а ветвь, отмеченная пунктирной линией, – сверхслову ...
bcbb
Пусть дана детерминированная функция :.
f A B
¥ ¥
® Построим дерево ,
T
соответствующее множеству ,
A
¥
и пометим его рёбра буквами алфавита ,
B
как будет показано ниже. Рассмотрим произвольное сверхслово (1) (2) (3)....
w a a a A
¥
= Î Пусть ( ) (1) (2) (3)...
f w b b b= Рассмотрим ветвь дерева ,
T
соответствующую сверхслову ,
w
и пометим рёбра этой ветви символами (1),(2),(3),...
b b b Так поступим с каждой ветвью. Если у двух сверхслов (1) (2) (3)...
w a a a= и (1) (2) (3)...
w a a a
¢ ¢ ¢ ¢
= совпадут первые k
букв: (1) (1),
a a
¢
= ...,( ) ( ),
a k a k
¢
= то ввиду детерминированности функции f
у сверхслов ( )
f w
и ( )
f w
¢
также будут совпадать первые k
букв. Следовательно, в процессе расстановки пометок на рёбрах мы не получим противоречия (т.е. каждое ребро дерева T
получит ровно одну пометку). Дерево ,
T
рёбра которого помечены вышеописанным способом, назовём информационным деревом, соответствующим функции ,
f
и обозначим его .
f
T
Наоборот, если дано дерево T
для ,
A
¥
то, пометив его рёбра буквами из B
произвольным образом, мы получим информационное дерево, соответствующее некоторой функции .
f
Это соответствие между информационными деревьями и детерминированными функциями является взаимно однозначным. Детерминированность функции :
f A B
¥ ¥
® является необходимым условием реализуемости функции f
некоторым автоматическим устройством. Но она не является достаточным условием. Причина в том, что всякое механическое устройство имеет конечную память (т.е. может хранить лишь ограниченное количество единиц информации). Пусть дано информационное дерево ,
f
T
соответствующее детерминированной функции .
f
Для любой вершины v
этого дерева пусть ( )
f
T v
обозначает поддерево, корнем которого является вершина v
(оно состоит из вершины v
и всех вершин и рёбер, идущих «после» ,
v
вместе с пометками на этих рёбрах). a
a
a
a
a
b
b
b
b
c
c
c
c
PDF created with pdfFactory Pro trial version www.pdffactory.com
Введём отношение эквивалентности ~ на множестве вершин дерева ,
f
T
полагая ~,
v v
¢
если у деревьев ( )
f
T v
и ( )
f
T v
¢
соответствующие друг другу рёбра имеют одинаковые пометки. Детерминированная функция :
f A B
¥ ¥
® называется ограниченно детерминированной (или о.д.-функцией), если множество вершин информационного дерева f
T
разбивается на конечное число ~-классов. Пример 4. Пусть функция :{0,1} {0,1}
f
¥ ¥
® определяется правилом ( (1) (2) (3)...) (1),(1) (2),(1) (2) (3),...
f a a a a a a a a a= + + + (здесь + обозначает сложение по модулю 2). Изобразим информационное дерево. Функция f
является ограниченно детерминированной, так как всего два класса эквивалентности. Теорема. Ограниченно детерминированные функции :
f A B
¥ ¥
® и только они являются автоматными, т.е. реализуются некоторым конечным автоматом. При этом A
является входным алфавитом автомата, а B
– выходным. Пример 5. Пусть {0,1}
A B= = и :
f A B
¥ ¥
® – функция, определяемая равенством ( ) (1) (2)...( )
b i a a a i
= + + + (эта функция была рассмотрена перед теоремой). Ранее мы видели, что функция f
в этом примере является ограниченно детерминированной, так как дерево f
T
имеет два класса эквивалентности. Обозначив эти классы через 0
q
и 1
,
q
получим диаграмму Мура автомата, реализующего эту функцию. Упражнения 4.9. Выяснить, какие из следующих функций :
f A B
¥ ¥
® являются детерминированными: а) {0,1},
A B= = (1) (2) (3)...(1) (1) (2) (3) (4)...;
f
a a a a a a a a¾¾® б) {0,1},
A B= = (1) (2) (3)...(2) (3) (4)...;
f
a a a a a a¾¾® в) {0,1},
A B= = (1) (2) (3)...0 (2)0 (4)0 (6)...;
f
a a a a a a¾¾® г) {0,1},
A B= = 1 1 1...,åñëè ( ) 0 äëÿ âñåõ,
( (1) (2) (3)...)
(1) (2) (3)...â ï ðî òèâí î ì ñëó÷àå.
a i i
f a a a
a a a
=
ì
=
í
î
4.10. Выяснить, какие из следующих функций :
f A B
¥ ¥
® являются ограниченно детерминированными: q 0
q
1
1
,
1
1
,
0
0
,
0
0,
1
v
v'
T (v)
f
T (v')
f
0
1
0
1 0 1
0 1 0 1 0 1 0 1 0
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
PDF created with pdfFactory Pro trial version www.pdffactory.com
а) {0,1},
A B= = (1) (2) (3)...0 (1) (2) (3)...;
f
a a a a a a¾¾® б) {,,},
A B a b c
= = (1) (1),
b a
= ( ),åñëè ( 1),
( ),åñëè ( ),
,åñëè ( )
a i a i a
b i b a i c
c a i a
- =
ì
ï
= =
í
ï
=
î
(
2
i
³
); в) {0,1},
A B= = :(1) (2) (3)...(1) (1) (2) (2) (3) (3)...
f a a a a a a a a a® 4.11. На рисунке изображён фрагмент информационного дерева некоторой о.д.-
функции. Каково наименьшее возможное число классов эквивалентности вершин этого дерева? 4.12. Выяснить, какие из следующих функций :
f A B
¥ ¥
® я вляются детерминированными: а) {0,1},
A = {,,},
B a b c
= (1),
b a
=
,åñëè ( ) ( 1) 0,
( ),åñëè ( ) ( 1) 1,
,åñëè ( ) ( 1);
a a i a i
b i b a i a i
c a i a i
= - =
ì
ï
= = - =
í
ï
¹ -
î
б) {0,1},
A B= = ( (1) (2) (3)...) 0 (1) 0 (2) 0 (3)...;
f a a a a a a= в) {0,1},
A B= = (1) (2) (3)...,åñëè ( ) 0 ï ðè âñåõ ÷¸òí ûõ,
( (1) (2) (3)...)
0 (2) 0 (4) 0...â ï ðî òèâí î ì ñëó÷àå.
a a a a i i
f a a a
a a
=
ì
=
í
î
4.13. Выяснить, какие из следующих функций :
f A B
¥ ¥
® я вляются ограниченно детерминированными: а) {,,},
A B a b c
= = ( (1) (2) (3)...) (1) (2) (3)...;
f a a a ab c a a a= б) {0,1},
A B= = (1) (2) (3)...0 (1) 0 (2) 0 (3)...;
f
a a a a a a¾¾® в) {,,},
A B a b c
= = ( ),åñëè ( ),
( )
,åñëè ( ).
a i j i a j c
b i
c j i a j c
"£ ¹
ì
=
í
$ £ =
î
Определить количество классов эквивалентности множества вершин дерева f
T
следующих функций: а) {0,1},
A = {0,1,2},
B = ( ) (1) (2)...( )
b i a a a i
= + + + (mod
3);
б) {0,1},
A B= = ( (1) (2) (3)...) 00 (1) (2) (3)...;
f a a a a a a= в) {,,},
A a b c
= {0,1},
B = 0,åñëè 1èëè ( ) ( 1),
( )
1 â ï ðî òèâí î ì ñëó÷àå.
i a i a i
b i
= ¹ -
ì
=
í
î
5. Синтез автоматов. Под синтезом автоматов понимают построение автоматов, удовлетворяющих заданному свойству или выполняющих заданные функции. Ранее был построен элемент задержки, который сдвигает входную последовательность на один такт: ( ) ( 1)
b i a i
= -
при 2.
i
³
Соединяя последовательно два элемента задержки, 0
0
0 1 0
0 1 0 1 1
1
b
d
0
a
g
m
h
Z
PDF created with pdfFactory Pro trial version www.pdffactory.com
мы получим сдвиг на два такта: ( ) ( 2)
b i a i
= -
при 3.
i
³
Автоматы 1 1 1 1 1 1
(,,,,)
V A Q B
= j y
и 2 2 2 2 2 2
(,,,,)
V A Q B
= j y
можно соединять последовательно. в случае, если 1 2
.
B A
Í При этом получается автомат (,,,,),
V A Q B
= j y
у которого 1
,
A A
= 2
,
B B
= 1 2
,
Q Q Q
= ´ 1 2 1 1 2 1 1 2
((,),) ( (,),( (,),)),
q q a a q a q qj = j j y
1 2 2 1 1 2
((,),) ( (,),).
q q a a q q
y = y j
Параллельное соединение автоматов приводит к появлению автомата 1 2 1 2 1 2
(,,,,),
V A A Q Q B B
= ´ ´ ´ j y
где 1 2 1 2 1 1 1 2 2 2
((,),(,)) ( (,),(,)),
q q a a q a q aj = j j 1 2 1 2 1 1 1 2 2 2
((,),(,)) ( (,),(,)).
q q a a q a q ay = y y Пусть (,,,,)
V A Q B
= j y -
конечный автомат. Если 1 2
{,,...,}
m
A a a a
= и 2,
k
m£ т о входной символ a
можно закодировать двоичной последовательностью длины ,
k
а именно: {
1
00...0,
k
a ® {
2
00...1,
k
a ® 3
00...10
k
a ®
123
и т.д. Аналогично, если 1
{,...,}
n
B b b
= и 2,
l
n £ т о выходные символы b B
Î
могут быть представлены двоичными последовательностями длины .
l
Автомат ,
V
таким образом, становится устройством, перерабатывающим двоичную информацию. Выходы ( )
j
y t
представляют собой булевы функции от входов 1
( ),...,
x i
( ),
k
x i
где ,1,...
i t t
= -
Эти функции можно реализовать с помощью схем, содержащих стандартные булевы элементы и элемент задержки: Пример 4. Рассмотрим устройство, осуществляющее сложение двух двоичных последовательностей с переносом разряда. Например, ( )
x t
0 1 0 0 1 0 1 1 0 1 0 . . . ( )
y t
1 0 1 1 1 0 1 0 1 1 0 . . . ( )
b t
1 1 1 1 0 1 1 0 0 1 1 . . . Z
a(i)
b
(
i
)
Z
V
V
1 2
a (1)a (2)...
V
1
1 1
1 1
b (1)b (2)...
a (1)a (2)...
V
2
2 2
2 2
b (1)b (2)..
.
V
x (t)
y (t)
1
1
........... ............
x (i)
k
l
y (t)
&
V
&
ù
z
PDF created with pdfFactory Pro trial version www.pdffactory.com
Таким образом, ( ) ( ),åñëè í å áûëî ï åðåï î ëí åí èÿ,
( )
( ) ( ) 1 â ï ðî òèâí î ì ñëó÷àå.
x t y t
b t
x t y t
+
ì
=
í
+ +
î
Положим 1,åñëè åñòü ï åðåï î ëí åí èå,
( )
0,åñëè åñòü.
u t
ì
=
í
î
Тогда ( ) ( ) ( ) ( 1),
b t x t y t u t
= + + -
( ) 0,
u t
=
если среди чисел ( ),
x t
( ),
y t
( 1)
u t
-
н е более одного равны 1, ( ) 1
u t
=
в п ротивном случае. Нетрудно видеть, что ( ) ( ) ( ) ( ( ) ( )) ( 1).
u t x t y t x t y t u t
= + + -
Теперь мы можем изобразить схему устройства. Упражнения 4.15. Дан алфавит {,,}.
A a b c
= Построить автомат, отыскивающий во входной последовательности подслово abc
и заменяющий после этого все символы символом .
*
Например, ......
ababbcacbabcabba ababbcacbabc
® ****
4.16. Выяснить, существует ли конечный автомат V
с алфавитами {0,1}
A B= = такой, что: а) 0
(,011) 101,
qy = 0
(,110) 000,
qy = 0
(,010) 111?
qy = б) 0
(,011) 101,
qy = 0
(,110) 000,
qy = 0
(,010) 100?
qy = 4.17. Построить автомат с наименьшим числом состояний, для которого {0,1},
A B= = 0
(,010) 110,
qy = 0
(,0111) 1110,
qy = 0
(,11) 00.
qy = 4.18. Построить автомат с входным и выходным алфавитами {,,}
A a b c
= и {_,,,,},
B a b c
= *
который отыскивает во входной последовательности идущие подряд более одного раза буквы a
и заменяет последнюю из них символом .
*
Символ _ зарезервирован здесь для начала последовательности. Пример: ..._...
abbcaabcacaaabc abbca bcacaa bc
® * * 4.19. Построить диаграмму Мура автомата с {0,1},
A B= = который во входной последовательности заменяет символы, стоящие на чётных местах, на противоположные. Например, 01100101001110...00110000011011...
®
4.20. Построить таблицу автомата с наименьшим числом состояний, удовлетворяющий условиям: 0
(,011) 111,
qy = 0
(,1011) 1101,
qy = 0
(,11) 10.
qy = 4.21. Автомат V
с {0,1}
A B= = работает по схеме, показанной на рисунке. При этом считается, что (0) 0.
u
=
а) Выразить ( )
u t
через ( ),
x t
( ),
y t
( 1).
u t
-
&
+
z
+
+
&
+
u(t)
b(t
)
x(t)
y(t)
&
V
z
+
ù
u(t)
x(t)
y(t)
PDF created with pdfFactory Pro trial version www.pdffactory.com
б) Найти первые 3 символа в выходной последовательности, если (1) (2) (3)...100...,
x x x = (1) (2) (3)...011...
y y y = 6. Алгебраический подход к теории автоматов. Алгебраический подход к теории автоматов предполагает рассмотрение автоматов без выхода, т.е. троек (,,),
V A Q
= j
где :
Q A Q
j ´ ®
– функция переходов. В упрощённой записи пишем qw
вместо (,)
q w
j для .
w A
*
Î
При этом ,
q q
l =
если l
– пустое слово. Произведение элемента из Q
на элемент из A
*
лежит в ,
Q
поэтому мы можем говорить о действии полугруппы A
*
на множестве .
Q
А именно, если ,
q qx
¢
= где ,
x A
*
Î то считаем, что элемент x
переводит q
в .
q
¢
Автоматы (,,)
V A Q
= j
и (,,)
V A Q
¢ ¢ ¢ ¢
= j
называются изоморфными (записывается: V V
¢
@
), если существует взаимно однозначное отображение :
Q Q
¢
s ® такое, что ( ) ( )
q a q a
s = s для всех ,
q Q
Î
.
a A
Î
Гомоморфизм автоматов (,,)
V A Q
= j
и (,,)
V A Q
¢ ¢ ¢
= j
над одним алфавитом A
– это отображение :
Q Q
¢
s ® (не обязательно взаимно однозначное) такое, что ( ) ( )
q a q a
s = s для всех ,
q Q
Î
.
a A
Î
Понятие подавтомата автомата (,,)
V A Q
= j
обычно определяется одним из следующих способов: а) подавтоматом является непустое подмножество X Q
Í
такое, что ;
XA A
Í
б) подавтомат – это тройка 1 1 1
(,,),
A Q
j
где 1
A
– непустое подмножество множества ,
A
а 1
Q
– непустое подмножество множества Q
такие, что 1 1 1
.
Q A Q
Í Определение б) является более общим, а при 1
A A
=
они совпадают. Отношение эквивалентности r
на множестве Q
называется конгруэнцией автомата (,,),
V A Q
= j
если ( ) ( )
q q qa q a
¢ ¢
r Þ r для всех ,.
q q Q
¢
Î
Класс эквивалентности конгруэнции ,
r
в котором лежит элемент ,
q Q
Î
обозначим [ ].
q
Множество всех классов эквивалентности (фактор-множество) обозначим /.
Q
r
Определим действие букв из A
на элементы множества /,
Q
r
полагая [ ] [ ]
q a qa
=
для ,
q Q
Î
.
a A
Î
Несложно проверяется корректность этого определения )т.е. независимость от выбора представителя в классе эквивалентности) и определяется отображение ://
Q A Q
F r´ ® r
(очевидно, ([ ],) [ ]).
q a qa
F = Автомат (,/,)
W A Q
= r F
называется фактор-автоматом автомата V
по конгруэнции r
и обозначается /.
W V
= r
В частности, приведённый автомат ?
,
V
рассмотренный ранее, является фактор-автоматом автомата .
V
Понятие автомата тесно связано с понятием полигона над полугруппой. Пусть S
– полугруппа и X
– множество. Будем говорить, что X
– полигон над ,
S
если определено отображение ,
X S X
´ ®
удовлетворяющее условию ( ) ( )
xs t x st
= при всех ,
x X
Î
,.
s t S
Î
Всякий автомат (,,)
V A Q
= j
можно рассматривать как полигон (а именно, полигон над полугруппой ).
A
*
Наоборот, если X
– полигон над полугруппой ,
S
то X
можно рассматривать как автомат, причём превращение X
в автомат далеко не единственно. Один из способов (вообще говоря, неэкономный) состоит в том, что S
рассматривается как входной алфавит, а (,)
x s xs
j =
– функция переходов. Пусть (,,)
V A Q
= j
– абстрактный автомат (не обязательно конечный). Для каждого w A
*
Î
р ассмотрим отображение :,
w
f Q Q
® определяемое по формуле ( ).
w
f q qw
= Множество всех отображений ,
w
f
где ,
w A
*
Î образуют полугруппу. Действительно, ( )( ) ( ( )) ( ) ( ) ( ),
w w w w ww
f f q f f q qw w q ww f q
¢ ¢ ¢
¢ ¢
= = = =o поэтому .
w w ww
f f f
¢ ¢
=o Полугруппа всех таких отображений ,
w
f
,
w A
*
Î называется полугруппой переходов автомата V
и обозначается ( ).
S V
Очевидно, множество состояний Q
является полигоном над полугруппой ( ).
S V
PDF created with pdfFactory Pro trial version www.pdffactory.com
Упражнения 4.22. Доказать, что всякая полугруппа S
является полигоном над собой. 4.23. Пусть G
– группа и X
– полигон над ,
G
причём ,
xe x
=
если ,
x X
Î
а e
– единица группы .
G
Орбитой элемента x X
Î
н азывается множество { | }.
xG xg g G
= Î Доказать, что X
является объединением непересекающихся орбит. 4.24. Описать полугруппу переходов ( )
S V
автомата, диаграмма Мура которого изображена на рисунке. 4.25. Что из себя представляет полугруппа переходов автомата, диаграмма Мура которого изображена на рисунке? 4.26. Пусть G
– группа, H
– её подгруппа, /{ | }
G H Hg g G
= Î – множество всех правых смежных классов. Доказать, что /
G H
является G
-полигоном относительно операции .
Hg g Hgg
¢ ¢
× = 4.27. Полигон X
над полугруппой S
называется циклическим, если существует такое 0
,
x X
Î что 0
.
X x S
= Доказать, что если X
– циклический полигон над группой G
с единицей e
и xe x
=
для всех ,
x X
Î
то /
X G H
@
для некоторой подгруппы H
группы .
G
4.28. Пусть X
– полигон над полугруппой ,
S
являющейся коммутативной полугруппой идемпотентов (т.е. st ts
=
и 2
s s
=
для всех ,).
s t S
Î Доказать, что X
будет являться частично упорядоченным множеством, если положить èëè.
x y x y x yS
£ Û = Î
4.29. Назовём полугруппу S
полугруппой правых нулей, если st t
=
для всех ,.
s t S
Î
Пусть X
– полигон над полугруппой S
правых нулей. Для s S
Î
п усть {(,) | }.
s
x y X X xs ys
s = Î ´ = а) Доказать, что s
s
– отношение эквивалентности. б) Доказать, что s t
s = s
п ри любых ,.
s t S
Î
в) Доказать, что для любого x X
Î
множество xS
пересекается с каждым s
s
-классом ровно по одному элементу. г) Доказать, что s
s
– конгруэнция полигона .
X
2
( ).
S V @
q 1
3
q
2
q
c
a c
c
a
a
b
b
b
q 1
q
2
a
a
b
b
PDF created with pdfFactory Pro trial version www.pdffactory.com
PDF created with pdfFactory Pro trial version www.pdffactory.com
Ответы, указания, решения 1. Алгебраические структуры 1.1. {2 3 4 5 6 7 8}
A B
È =,,,,,,
, {4 6}
A B
Ç =,
, \{2 8}
A B
=,
, \{3 5 7}
B A
=,,
, {1 3 5 7 9}
A
=,,,,
, {1 2 8 9}
B
=,,,
. 1.2. {3}
A BÇ =, {1 2 3 4 5 6 7 9}
A B
È =,,,,,,,
, , \{1 5 7 9}
A B
=,,,,
\{2 4 6}
B A
=,,
, {2 4 6 8}
A
=,,,
, {1 5 7 8 9}.
B
=,,,,
1.3. ( 2) [3 )
A B
È = -¥;È;+¥
, ( 11] {4} {5} (6 )
A B
Ç = -;È È È;+¥
, \( 1] [3 4) (5 6]
A B
= -¥;- È;È;,
\(1;2) (4;5)
B A = È, (1;3) (4;5)
A = È, (;1] [2;4) (5;6].
B = -¥ - È È 1.4. ( 4] (6 )
A B
È = -¥;È;+¥
, [1 2] {7} (8 9]
A B
Ç =;È È;
, \( 1) {4} (6 7) (7 8]
A B
= -¥;È È;È;,
\(2;4) (9;)
B A
= È +¥
, (2;4) (4;6] (9;)
A
= È È +¥
, (;1) [4;7) (7;8].
B = -¥ È È
1.5. 24-мя способами. 1.6. 32. 1.7. 32. 1.8. 3
5
10
C
=
. 1.9. 8. 1.10. 6. 1.11. Например, такое: .
a b c
y y x
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
è ø
1.12. 27. 1.13. Напримеp, такое: .
a b c
z y x
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
è ø
1.14. См. 1.11 1.15. 6. 1.16. Напpимеp, такое: .
a b c d
æ ö
ç ÷
a b g a
è ø
1.17. 1 2 3
3 2 1
fg
æ ö
=
ç ÷
è ø
, 1 2 3
2 1 3
gf
æ ö
=
ç ÷
è ø
, 1
1 2 3
2 3 1
f
-
æ ö
=
ç ÷
è ø
, 1
1 2 3
1 3 2
g
-
æ ö
=
ç ÷
è ø
, ( ) 3
o f
=
, ( ) 2
o g
=
. 1.18. 1 2 3 4
3 2 1 4
fg
æ ö
=
ç ÷
è ø
, 1 2 3 4
1 2 4 3
g f
æ ö
=
ç ÷
è ø
, 1
1 2 3 4
3 1 4 2
f
-
æ ö
=
ç ÷
è ø
, 1
1 2 3 4
2 4 3 1
g
-
æ ö
=
ç ÷
è ø
, ( ) 4
o f
=
, ( ) 3
o g
=
. 1.19. Решение. Пусть отображение f A B
:® является взаимно однозначным. Тогда каждый элемент b B
Î
имеет ровно один прообраз .
a A
Î
Положим ( ).
g b a
=
Таким образом определенное отображение g B A
:®
будет обратным к f . Далее, если отображение f A B
:® имеет обратное отображение 1
f B A
-
:® и 1 2 1 2
,, ,
a a A a a
Î ¹ то 1 2
( ) ( ).
f a f a
¹ Действительно, если бы 1 2
( ) ( )
f a f a
=, то 1 1
1 1 2 2
( ( )) ( ( )),
a f f a f f a a
- -
= = = что противоречит условию. Теперь проверим второе условие в определении взаимно однозначного отображения. Пусть b B
Î
. Тогда 1
( ( )).
f f b b
-
=
З начит элемент 1
( )
a f b
-
= я вляется прообразом элемента b. Таким образом, отображение f A B
:® будет взаимно однозначным. 1.20. Решение. Поскольку разные элементы множества A должны переходить в разные, то | | | |.
A B
£ А так как любой элемент множества B должен иметь прообраз, а прообразы для разных элементов множества B не могут совпадать, то | | | |.
B A
£ З начит, | | | |.
A B
= 1.21. 512. 1.22. 64. 1.23. 64. 1.24. 216. 1.25. Напpимеp, такое 1 1 0
1 1 1
0 1 1
æ ö
ç ÷
r =
ç ÷
ç ÷
è ø
. 1.26. Напpимеp, такое 1 1 0
0 1 0
0 0 1
æ ö
ç ÷
r =
ç ÷
ç ÷
è ø
. 1.27. Напpимеp, такое 0 0 0
0 0 0
0 0 0
æ ö
ç ÷
r =
ç ÷
ç ÷
è ø
. 1.28. Отношение r
будет pефлексивным, симметpичным и тpанзитивным, но не будет антисимметpичным. Таким обpазом, r
будет являться отношением эквивалентности, но не будет отношением поpядка. 1.29. Отношение r
будет симметpичным, но не будет рефлексивным, антисимметpичным, транзитивным, отношением эквивалентности или поpядка. 1.30. Отношение r
будет симметpичным, но не будет рефлексивным, антисимметpичным, транзитивным, отношением эквивалентности или поpядка. 1.31. Неассоциативна. 1.32. Ассоциативна. 1.33. Ассоциативна. 1.34. Ассоциативна. 1.35. Обозначим эти бинарные операции символами 0
y
– 15
y
в соответствии с таблицей: x
y
0
y
1
y
2
y
3
y
4
y
5
y
6
y
7
y
8
y
0
0
0
0
0 0 0 0 0 0 1 0
1
0
0 0 0 1 1 1 1 0 1
0
0
0 1 1 0 0 1 1 0 PDF created with pdfFactory Pro trial version www.pdffactory.com
1
1
0
1 0 1 0 1 0 1 0 x
y
9
y
10
y
11
y
12
y
13
y
14
y
15
y
0
0
1 1 1 1 1 1 1 0
1
0 0 0 1 1 1 1 1
0
0 1 1 0 0 1 1 1
1
1 0 1 0 1 0 1 Тогда ассоциативными будут операции 0 1 3 5 6 7 9 15
,,,,,,,.
y y y y y y y y
1.36. ( )
,+
– гpуппу не обpазует, т.к. в ней нет единицы. Остальные множества ,,,
с опеpацией сложения обpазуют гpуппу. 1.37. не является, т.к. элементы 2 3 4
…
,,,
не имеют обpатных.
не является, т.к. элементы 0 2 3 4
…
,±,±,±,
не имеют обpатных. ,,
также не являются, т.к. 0 не имеет обpатного. 1.38. не является, т.к. элементы 2 3 4
…
,,,
не имеют обpатных. \0
не является, т.к. элементы 2 3 4
…
±,±,±,
не имеют обpатных. ,,
я вляются. 1.39. Да. Pоль единицы игpает 0. Обpатным для kn
является элемент kn
-
. 1.40. Да. 1.41. Отобpажение f
является гомомоpфизмом, но не является изомоpфизмом. Решение. Если x y
,Î
, то 2 ( ) 2 2
( ) ( ) ( )
i x y ix iy
f x y e e e f x f y
p + p p
+ = = × = ×, поэтому f
– гомомоpфизм, однако (0) (1) 1
f f
= =
, поэтому f
не является взаимно однозначным отобpажением, а значит, не является изомоpфизмом. 1.42. Отобpажение [0 1)
f T
:,®, опpеделенное фоpмулой 2
( )
ix
f x e
p
= я вляется изомоpфизмом. 1.43. Решение. Пусть O
– центp пpавильного тpеугольника ABC
. В гpуппе движений 3
D
обозначим j
– повоpот на 120
o
вокpуг центpа пpотив часовой стpелки; 2
j
– повоpот на 240
o
; a
– симметpия относительно пpямой, пpоходящей чеpез точки A
и O
; b
– симметpия относительно пpямой BO
; c
– симметpия относительно пpямой CO
; e
– тождественное пpеобpазование. Тогда элементы a b c
,,
имеют 2-ой поpядок, а j
и 2
j
– 3-ий. Элементы { }
a
,j
можно взять за систему обpазующих гpуппы 3
D
. Тогда ñ a b a
= × j,= j×
. В гpуппе 3
S
подстановки 1 2 3 1 2 3 1 2 3
1 3 2 3 2 1 2 1 3
x y z
æ ö æ ö æ ö
=,=,=
ç ÷ ç ÷ ç ÷
è ø è ø è ø
имеют 2-ой поpядок, а 2
1 2 3 1 2 3
3 1 2 2 3 1
u u
æ ö æ ö
=,=
ç ÷ ç ÷
è ø è ø
3-
ий. Зададим отобpажение 1 3 3
f D S
:® на обpазующих следующим обpазом: ( ) ( )
f a x f u
=,j =
. Тогда 2 2
( ) ( ) ( ) ( ) ( )
f u f b f a u x y f c f a x u z
j =,= j× = × =,= × j = × =
и отобpажение 1
f
будет изомоpфизмом. 1.44. Матpицы 0 1 1 0 1 1
1 0 1 1 0 1
A B C
æ ö æ ö æ ö
=,=,=
ç ÷ ç ÷ ç ÷
è ø è ø è ø
имеют 2-ой поpядок, а 2
0 1 1 1
1 1 1 0
U U
æ ö æ ö
= =
ç ÷ ç ÷
è ø è ø
тpетий. Указание. Зададим отобpажение 2
f
на обpазующих следующим обpазом: 2 2
( ) ( )
f a A f U
=,j =
. Тогда 2 2
2 2 2
( ) ( ) ( )
f b B f c C f U
=,=,j = и 2
f
– изомоpфизм. 1.45. Решение. Опpеделим поpядки функций в последней гpуппе. Напpимеp, 2
3 3 3 4
1
1
1 1 1
( ( ))
1
x
x x
y y y x y
x x
-
- -
= = = = =.
- -
Далее, 3
3 3 4 1
1
1
( ( ))
1
x
x
y y y x x y
-
= = = =.
-
З начит, поpядок функции 3
y
(а, значит, и 4
y
) pавен 3, поскольку 1
y
– является единицей этой гpуппы. Поpядки функций 2 5 6
y y y
,,
pавны 2-м. Положим 3 2 3 3
( ) ( )
f a y f y
=,j =
. Тогда 2
3 6 3 5 3 4
( ) ( ) ( )
f b y f c y f y
=,=,j =
и 3
f
– изомоpфизм. 1.46.
{
}
2
Aut e
@. 1.47.
3 1 2 2
{ }Aut f f
=,@.
1.48.
4 1 3 2
{ }Aut f f
=,@.
1.49.
5 1 2 3 4 4
{ }Aut f f f f
=,,,@.
1.50.
3 3
AutS S
@.
1.51. В гpуппе 12
имеются следующие нетpивиальные подгpуппы: 1 2 3 4
{0 2 4 6 8 10} {0 3 6 9} {0 4 8} {0 6}
H H H H
=,,,,,,,,,,,,,=,.
Э л емент 0
является единицей гpуппы, а единица всегда имеет пеpвый поpядок, элемент 6
имеет поpядок 2, элементы 4 8
,
– поpядок 3, элементы 3
и 9
имеют поpядок 4, элементы 2 10
,
имеют поpядок 6. Остальные элементы 1 5 7 11
,,,
имеют поpядок 12. 1.52. Решение.Пусть ABCD – квадрат, j
– поворот PDF created with pdfFactory Pro trial version www.pdffactory.com
около центра квадрата на 90
o
против часовой стрелки, 2
j
и 3
j
– повороты на 180
o
и 270
o
соответственно, e – тождественное отображение, a – симметрия относительно прямой AC, b – относительно прямой BD, f – симметрия относительно прямой проходящей через середины сторон AB и CD, g – симметрия относительно прямой, проходящей через середины сторон BC и AD. Тогда нетривиальными подгруппами будут следующие: {
}
2
1
,,
H e= j {
}
2
,,
H e a
= {
}
3
,,
H e b
= {
}
4
,,
H e f
= {
}
5
,,
H e g
= {
}
2 3
6
,,,,
H e= j j j {
}
2
7
,,,,
H e a b
= j {
}
2
8
,,,.
H e f g
= j Единица группы e всегда имеет первый порядок, элементы 2
,,,,
a b f g
j имеют второй порядок, и элементы j
и 3
j
имеют четвертый порядок. 1.53. Решение. Пусть ABCD – прямоугольник, | | | |
AB BC
¹, j
– поворот около центра на 180
o
, e – тождественное отображение, a – симметрия относительно прямой проходящей через середины сторон AB и CD, b – симметрия относительно прямой, проходящей через середины сторон BC и AD. Тогда нетривиальными подгруппами будут следующие: {
}
1
,,
H e
= j
{
}
2
,,
H e a
= {
}
3
,
H e b
=. Е диница группы e имеет первый порядок, элементы ,,
a b
j имеют второй порядок. 1.54. Решение. Пусть ABCD – ромб, j
– поворот около центра на 180
o
, e – тождественное отображение, a – симметрия относительно прямой AC, b – относительно прямой BD. Тогда нетривиальными подгруппами будут следующие: {
}
1
,,
H e
= j
{
}
2
,,
H e a
= {
}
3
,
H e b
=. Единица группы e имеет первый порядок, элементы ,,
a b
j имеют второй порядок. 1.55. Решение. Пусть ABCDF – правильный пятиугольник, точка O – его центр, j
– поворот около центра на 72
o
против часовой стрелки, 2
j
, 3
j
, 4
j
– повороты на 144
o
, 216
o
и 288
o
соответственно, e – тождественное отображение, a, b, c, d, f – симметрии относительно прямых AO, BO, CO, DO и FO соответственно. Тогда нетривиальными подгруппами будут следующие: {
}
1
,,
H e a
= {
}
2
,,
H e b
= {
}
3
,,
H e c
= {
}
4
,,
H e d
= {
}
5
,,
H e f
= {
}
2 3 4
6
,,,,.
H e
= j j j j
Е диница группы e имеет первый порядок, элементы ,,,,
a b c d f
имеют второй порядок, и элементы 2 3 4
,,,
j j j j
имеют пятый порядок. 1.56. Решение. Группа кватернионов состоит из элементов {
}
8
1,,,.
Q i j k
= ± ± ± ± Нетривиальными подгруппами будут следующие: {
}
1
1,
H
= ±
{
}
2
1,,
H i
= ± ±
{
}
3
1,,
H j
= ± ± {
}
4
1,.
H k
= ± ± Единица группы 1 всегда имеет первый порядок, элемент (–1) – второй порядок, остальные элементы ,,
i j k
± ± ±
имеют четвертый порядок. 1.57. 1,3,7,9.
1.58. 1,5,7,9.
1.59. Решение. Пусть ABC – правильный треугольник, точка O – его центр, j
– поворот около центра на 120
o
против часовой стрелки, 2
j
– поворот на 240
o
, e – тождественное отображение, a, b, c, – симметрии относительно прямых AO, BO, CO соответственно. Тогда минимальными системами образующих будут следующие: {
}
,,
a b
{
}
,,
a c
{
}
,,
a
j
{
}
2
,,
a j {
}
,,
b c
{
}
,,
b
j
{
}
2
,,
b j {
}
,,
c
j
{
}
2
,.
c
j
1.60.
{
}
,,
a f
{
}
,,
a g
{
}
,,
a
j
{
}
3
,,
a j
{
}
,,
b f
{
}
,,
b g
{
}
,,
b
j
{
}
3
,,
b j
{
}
,,
f
j
{
}
2
,,
f j
{
}
,,
g
j
{
}
2
,.
g j 1.61. Решение. Если , ,
g G h H
Î Î то определитель матрицы 1
ghg
-
равен единице, поэтому 1
gHg H
-
Ì и, следовательно, подгруппа H нормальна в G. 1.62. Если H – центр группы G
, то gH Hg
=
, поскольку элементы из H коммутируют со всеми элементами группы G. 1.63. Решение. Если H – подгруппа индекса 2 группы G, то группа G является объединением двух левых, а также двух правых смежных классов по подгруппе H. Но одним из этих левых (правых) смежных классов является сама подгруппа H. Следовательно, оставшиеся левый и правый смежные классы совпадают, поскольку они совпадают с \.
G H
1.64. Подгруппы {
}
{
}
{
}
1 2 3
1,,1,,1,
H i H j H k
= ± ± = ± ± = ± ±
являются нормальными, поскольку они имеют индекс 2. Подгруппа {
}
4
1
H
= ±
нормальна, поскольку она является центром группы 8
Q
. 1.65. 4
/.
G H @
1.66. /
G H
изоморфна группе движений прямоугольника, не являющегося квадратом. 1.67. 3
/.
G H @
1.68. {
}
/1.
G H
@ ±
1.69. /
G H
изоморфна группе движений PDF created with pdfFactory Pro trial version www.pdffactory.com
прямоугольника, не являющегося квадратом. 1.70. Да. 1.71. Поскольку 15 3 5
n
= = ×
, (3) {0 5 10} (5) {0 3 6 9 12}
A A
=,,,=,,,,
. Изомоpфизм 15
(3) (5)A AÅ ®
Z
можно задать следующим обpазом ( )
a b a b
,® +.
1.72. 6 2 3
.
@ Å
1.73. 12 4 3
.
@ Å
1.74. 60 4 3 5
.
@ Å Å
1.75. Поскольку 3 2
360 2 3 5
= × ×
, то 360 8 9 5
@ Å Å.
1.76. Решение. Поскольку 2 3 2 3 2 3
756 2 3 7 2250 2 3 5 25725 3 5 7
= × ×,= × ×,= × ×
, то 756 4 27 7
,
= Å Å
2250 2 9 125
,
= Å Å 25725 3 25 343
.
= Å Å Поэтому 756 2250 25725 2 4 3 9 27 25 125 7 343
Å Å @ Å Å Å Å Å Å Å Å.
1.77. Решение. Поскольку 15 3 5 225 9 25
= ×,= ×
, то 15 225 3 5 9 25
Å @ Å Å Å
. Далее, 75 3 25 45 5 9
= ×,= ×
. Поэтому 75 45 3 25 5 9
Å @ Å Å Å
. Так как pазложения совпадают с точностью до пеpестановки слагаемых, гpуппы изомоpфны. 1.78. Решение. Находим pазложение каждой гpуппы в пpямую сумму пpимаpных циклических гpупп: 9 225 9 9 25
Å @ Å Å
15 135 3 5 5 27
Å @ Å Å Å
. Пpимаpные циклические слагаемые не совпадают. Гpуппы не изомоpфны. 1.79. 6 36 2 3 4 9
.
Å @ Å Å Å
12 18 4 3 2 9
.
Å @ Å Å Å
Группы изоморфны. 1.80. 6 36 2 3 4 9
.
Å @ Å Å Å
9 24 9 3 8
.
Å @ Å Å
Группы не изоморфны. 1.81.
6 10 10 2 3 2 5 2 5
.
Å Å @ Å Å Å Å Å
60 10 4 3 5 2 5
.
Å @ Å Å Å Å
Группы не изоморфны. 1.82. Решение. Поскольку 64=2
6
и 6=1+5=2+4=3+3=1+1+4=1+2+3=2+2+2=1+1+1+3=1+1+2+2=1+1+1+1++2=1+1+1+1+1+1, то (6) 11
s
=
. Поэтому существует 11 неизомоpфных абелевых гpупп поpядка 64. 1.83. 4. 1.84. 4. 1.85. 3 5
864 3 2
= ×
. Решение. Так как (3) 3 (5) 7
s s
=,=
, то абелевых гpупп поpядка 864 существует 21. 1.86. Решение. Пусть G
– циклическая группа с образующим g. Если ,,
x y G
Î
то ,
n m
$ Î
такие, что ,.
n m
x g y g
= = Тогда .
n m
xy yx g
+
= = 1.87. Решение. Пусть G
– группа простого порядка p и ,.
g G g e
Î ¹
Тогда ( ) 1
o g
¹
и ( ) |.
o g p
Значит, ( ).
o g p
=
Таким образом, элемент g является образующим группы G
, и .
p
G @
1.88. Решение. Пусть ,.
x y G
Î
Тогда .
xyxy e
=
Умножая это равенство справа на yx и учитывая, что 2 2
,
x y e
= =
получим .
xy yx
=
1.89. Решение. Пусть G
– группа порядка 4. Если в ней есть элемент порядка 4, то она изоморфна 4
. Если нет, то порядки ее элементов не превышают 2, следовательно, она абелева, но тогда она изоморфна 2 2
Å
в силу теорем о строении конечных абелевых групп. 1.90. Решение. В G
не может быть элемента порядка 6, так как в противном случае G
была бы абелевой. Если бы в G
не существовал элемент порядка 3, то порядки элементов были бы не более 2, но тогда G
была бы абелевой в силу задачи 3. Следовательно, в G
имеется элемент порядка 3. 1.91. Решение. Элементы 2
,,,
e x x y
разные по условию. Элемент {
}
2
,,
xy e x x
Ï, т.к. иначе {
}
2
,,
y e x x
Î. Также .
xy y
¹
Значит элемент xy отличен от 2
,,,.
e x x y
Аналогично, 2
x y
отличен от элементов 2
,,,,.
e x x y xy
Если бы порядок элемента y равнялся бы 3, то 2
y
равнялся бы одному из элементов 2 2
,,,,.
x x y xy x y
Но отсюда следовало бы, что {
}
2
,,
y e x x
Î, а это невозможно. Значит, ( ) 2.
o y
=
1.92. Решение. Действительно, {
}
2 2
,,,,,.
yx e x x y xy x y
Î Но если {
}
2
,,,
yx e x x
Î то {
}
2
,,,
y e x x
Î что является противоречием. Если ,
yx y
=
то ,
x e
=
что невозможно. В случае ,
yx xy
=
группа C
^
была бы коммутативной. Остается только одна возможность: 2
.
yx x y
= 1.93. Решение. Полученные в задачах 1.90 – 1.92 соотношения полностью определяют группу G
. Изоморфизм 3
:
F G D
® можно задать формулами ( ),( ).
F x F y a
= j =
Тогда ( ),
F e e
=
2 2
( ),
F x
= j
( ),
F xy c
=
2
( ).
F x y b
=
1.94. Решение. Если бы в G
был бы элемент 8-го порядка или порядки всех элементов не превосходили бы 2-х, то G
была бы абелевой. Значит, G
содержит элемент 4-го порядка x. Обозначим {
}
2 3
,,,.
H e x x x
= Пусть \.
y G H
Î Тогда ,,
x y G
< >=
поэтому элементы x и y не могут коммутировать, т.е. .
xy yx
¹
Элементы 2 3
,,,
y xy x y x y
– разные и 2 3
,,,,
y xy x y x y H
Ï т.к. иначе .
y H
Î
С ледовательно, PDF created with pdfFactory Pro trial version www.pdffactory.com
{
}
2 3 2 3
,,,,,,,.
G e x x x y xy x y x y
= Наконец, ,,.
yx H yx y yx xy
Ï ¹ ¹
Если бы 2
,
yx x y
= то 2 2
,
yx x yx y
= =
откуда следовало бы, что 2
,
x e
=
что невозможно. Значит, 3
.
yx x y
= 1.95. Решение. Пусть 2
.
y e
¹
Тогда ( ) 4,
o y
=
следовательно, 2
( ) 2.
o y
=
Поэтому 2 2 3
,.
y x y x
¹ ¹ Кроме того {
}
2 2 3
,,,,
y y xy x y x y
Ï поскольку иначе .
y H
Î
Следовательно, 2 2
.
y x
= Рассмотрим первый случай 2
.
y e
=
В этом случае группа G
полностью определена и отображение 4
:,
F G D
® при котором ( ),( ),
F x F y a
= j =
задает изоморфизм групп 4
.
G D
@ Во втором случае 2 2
y x
=
изоморфизм 8
:
F G Q
® можно задать на образующих так: ( ),( ).
F x i F y j
= =
1.96. Решение. Код C
есть множество pешений этой системы линейных одноpодных уpавнений pанга 2 с пятью неизвестными. Следовательно, код C
имеет pазмеpность 3. Фундаментальную систему pешений можно выбpать из вектоpов (10010)
(01011)
(00101)
.
Поpождающая матpица кода C
, таким обpазом, имеет вид 10010
01011
00101
C
æ ö
ç ÷
=.
ç ÷
ç ÷
è ø
1.97. Кодовые слова представляют собой всевозможные линейные комбинации строк порождающей матрицы 0 0 0 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 0. 1.98. Оpтогональным кодом C
^
будет множество pешений системы уpавнений 1 4
2 4 5
3 5
0
0
0
x x
x x x
x x
+ =
+ + =
+ =.
Фундаментальная система pешений имеет вид (11010)
(01101)
.
Таким обpазом, пpовеpочная матpица кода C
есть 11010
01101
H
æ ö
=.
ç ÷
è ø
Код C
есть линейный (5 3)
,
-код. 1.99.
0
1 0 1 1 1 0 0
1 1 0 1 0 1 0.
0 1 1 0 0 0 1
H
æ ö
ç ÷
=
ç ÷
ç ÷
è ø
1.100. 0
1 0 0 0 1 0
0 1 0 0 0 1
.
0 0 1 0 1 1
0 0 0 1 0 1
G
æ ö
ç ÷
ç ÷
=
ç ÷
ç ÷
è ø
1.101. Решение. а) В матрице есть два одинаковых столбца. Система из этих двух столбцов линейно зависима, значит, вес 2.
d
£
С другой стороны в матрице нет ненулевых столбцов. Это означает, что система из одного столбца всегда линейно независима, т.е. 1 1.
d
- ³
Отсюда 2.
d
=
б). Сумма первого, третьего и пятого столбцов равна нулю, откуда 3.
d
£
А поскольку в матрице нет одинаковых столбцов, то 1 2.
d
- ³
З начит, 3.
d
=
1.102. Код C обнаруживает 8 и исправляет 4 ошибки. 1.103. Pазложение абелевой гpуппы 2
n
Z
по подгpуппе C
имеет следующий вид 00000 00001 00010 01000
10010 10011 10000 11010
01011 01010 01001 00011
00101 00100 00111 01101
11001 11000 11011 10001
10111 10110 10101 11111
01110 01111 01100 00110
11100 11101 11110 10100
PDF created with pdfFactory Pro trial version www.pdffactory.com
В первой строке расположены лидеры смежных классов. 1.104. Решение. Слово (101)
u = кодиpуется как (10111)
v u G= × =. Пpедположим, что пpи пеpедаче по каналу связи во втоpом pазpяде была допущена ошибка, и на пpиеме получено слово (11111)
v
¢
=. Это слово содеpжится в четвеpтом смежном классе, поэтому пpи декодиpовании к нему пpибавляется лидеp этого смежного класса: (01000)
. В pезультате мы получаем слово (10111)
v
¢¢
=, котоpое после отсечения последних двух pазpядов будет pавно (101)
u
¢
=. Таким обpазом, ошибка испpавлена. Для того, чтобы испpавить одну ошибку можно действовать и по дpугому. Если умножить пpовеpочную матpицу H
на вектоp v
¢
, то получится слово (11)
. Оно называется синдpомом и pавно тому столбцу пpовеpочной матpицы, в котоpом допущена ошибка. В данном случае слово (11)
совпадает со втоpым столбцом матpицы H
, поэтому в слове v
¢
нужно испpавить втоpой pазpяд. Заметим, что если бы ошибка пpоизошла в пеpвом или тpетьем pазpядах, то слово было бы декодиpовано непpавильно. Это свидетельствует о том, что данный код еще очень мало эффективен в плане испpавления ошибок. 1.105. 0 1 1 0 0
1 0 0 1 0.
1 0 0 0 1
H
æ ö
ç ÷
=
ç ÷
ç ÷
è ø
Вес кода равен 2. Код обнаруживает одну ошибку, но не исправляет ни одной. 1.106. 0 1 1 0 0
1 0 0 1 0.
1 1 0 0 1
H
æ ö
ç ÷
=
ç ÷
ç ÷
è ø
Вес кода равен 3. Код обнаруживает две и исправляет одну ошибку. 1.107. 1 1 1 0 0
1 1 0 1 0.
0 1 0 0 1
H
æ ö
ç ÷
=
ç ÷
ç ÷
è ø
Вес кода равен 3. Код обнаруживает две и исправляет одну ошибку. 1.108. 0 1 1 1 0 0
1 0 1 0 1 0.
1 1 0 0 0 1
H
æ ö
ç ÷
=
ç ÷
ç ÷
è ø
Вес кода равен 3. Код обнаруживает две и исправляет одну ошибку. 1.109. Решение. Расстояние между любыми несовпадающими точками пространства 2
n
не меньше 1, а число точек в 2
n
равно 2
n
, поэтому (,1) 2.
n
A n = Пусть (,)
M n s
– максимальное множество точек в 2
n
, расстояние между любыми двумя из которых не меньше, чем s. Можно считать, что 00 0 (,),
n
M n s
ÎK
123
т.к. иначе все точки из (,)
M n s
можно сдвинуть на один и тот же вектор. Существует только одно слово, расстояние от которого до точки 00 0
K
равно n, это 11 1.
K
Поэтому (,) 2.
A n n
=
1.110. Решение. Можно считать, что (000) (3,2).
MÎ Множество точек (
)
(
)
(
)
(
)
{
}
(3,2) 000,011,101,110
M = в 2
n
будет максимальным множеством точек, расстояние между любыми двумя из которых не меньше 2. Поэтому (3,2) 4.
A
=
1.111. 1 0 0 0 0 1 1
0 1 0 0 1 0 1
.
0 0 1 0 1 1 0
0 0 0 1 1 1 1
G
æ ö
ç ÷
ç ÷
=
ç ÷
ç ÷
è ø
1.112. а) Ошибка в 6-м разряде. Исправленное слово (
)
1110000
u =
%
; б) Ошибка в 5-м разряде. Исправленное слово (
)
1101010
u =
%
; в) Ошибка в 1-м разряде. Исправленное слово (
)
0111100.
u =
%
PDF created with pdfFactory Pro trial version www.pdffactory.com
1.113. 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
.
0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
H
æ ö
ç ÷
ç ÷
=
ç ÷
ç ÷
è ø
1.114. а) Ошибка в 10-м разряде. Исправленное слово (
)
000111000011000.
u =
%
б) Ошибка в 5-
м разряде. Исправленное слово (
)
100110100100100.
u =
%
в) Ошибка в 8-м разряде. Исправленное слово (
)
000000011111111.
u =
%
2. Теория булевых функций 2.1. а) (1,1,0,0)
, (0,0,0,0)
, (0,1,1,0)
, (0,1,0,1)
; б) n
; в) 1
2
n
n
-
×
. 2.2. а) (1,0,1,0)
, (1,1,0,0)
, (1,1,1,1)
,
(0,0,0,0)
, (0,0,1,1)
, (0,1,0,1)
; б)
k
n
C
; в)
1
2
k n
n
C
-
×
. 2.3. 2
2
n
, если n
- четное число и 1
2
2
n
+
, если n
- нечетное число. 2.2. а) 19; б) 50; в) 31; г) 77. 2.5. а) (0000)
, (0110)
, (1001)
, (1111)
; б)
1
2
2
n
-
. 2.6. а) (0000)
, (0001)
, (1000)
, (1001)
; б) 2
2
n k
n
C
-
. Указание к б). Вес k имеют k
n
C
булевых векторов от n переменных. Следовательно, k
n
C
определенных координат функции равны 1, а остальные (
)
2
n k
n
C
- координаты могут принимать любые значения (0 или 1). 2.7. Ука зание. Пусть (
)
0,0,...,0 0
f
=
. Тогда на всех наборах веса 1 значение функции также будет равно 0. Для каждого набора веса 2 найдется соседний с ним набор веса 1, следовательно, на всех наборах веса 2 значение функции также равно 0. Для каждого набора веса 3 найдется соседний с ним набор веса 2, следовательно, на всех наборах веса 3 значение функции также равно 0. И так далее вплоть до векторов веса n
. Случай (
)
0,0,...,0 1
f
=
р ассматривается аналогично. 2.8. а) 1
x
- существенная, 2
x
- фиктивная; б) 1
x
- фиктивная; 2
x
, 3
x
- существенные; в) 3
x
- фиктивная; 1
x
, 2
x
- существенные; г) 1
x
, 3
x
- фиктивные; 2
x
, 4
x
- существенные. 2.9.а)
(11101010)
; б)
(10)
; в)
(1001)
; г) (01)
. 2.10. а)
(1111)
; б)
(0100 0111)
; в)
(11111101)
; г) (1110 1110 1110 0001)
. 2.11. в), г) является; а), б), д), е) не является. 2.12. а)
(10011111)
; б)
(0010 0000 0010 0010)
. 2.13. а) (
)
xy x y
Ú
; б) ( )
(
)
x y xyz xy z
Ú Ú ® ®. 2.12. а) ( ) ( )
( )
(
)
(
)
(
)
x y x y z z
Ù Ú Ù Ø Ù Ú
; б) ( )
(
)
( )
(
)
x z y x y
Ú Ù ® Ù. 2.19. а) коммутативна только {
}
«
; б) ассоциативна только
{
}
«
. 2.20. а) xyz
; б) x y
; в) xy xy
×
; г) xyz
. 2.21. а) x y z
Ú Ú
; б) x y y z
Ú Ú Ú
; в) x y y x
Ú Ú Ú
; г) x y y x
Ú Ú Ú
. 2.23. а) z x
Ú
; б) 1; в) xy
; г) x y
Ú
; д) x z
Ú
; е) xy
. 2.22. а)
1
x
, 2
x
, 4
x
, 5
x
- фиктивные; 3
x
, 6
x
- существенная; б) 2
x
- существенная, 1
x
, 3
x
- фиктивные. 2.25. а) (
)
0000
,
(
)
0101
, (
)
1010
, (
)
1111
; б) 1
2
2
n
-
. Ука зание к б). Если n
x
- фиктивная переменная, то для любого набора 1 2 1
,...,
n
-
a a a
выполняется равенство (
)
(
)
1 2 1 1 2 1
,...,,0,...,,1
n n
f f
- -
a a a = a a a, следовательно, чтобы задать функцию f
необходимо и достаточно определить ее значения на 1
2
n
-
булевом векторе; в) 1
2
2
n
n
-
×. 2.26. а) 36; б) 49; в) 3
n
; г) 2
2 3
n n
-
. Указание к г). Можно от числа всех наборов длины 2
n
отнять число наборов, на которых функция обращается в единицу. 2.27. ( )
*
0 1
=
, ( )
*
1 0
=
; ( )
*
x x
=
; (
)
*
x x
=
; ( )
*
x y x y
Ú = Ù
; ( )
*
x y x y
Ù = Ú
; (
)
*
x y x y
¯ =; ( )
*
x y x y
= ¯
; ( )
*
x y x y
« = Å
; ( )
*
x y x y
Å = «. 2.28. а) (
)
4 3 2 1
,,,
s s s s
. 2.29. а) (
)
0010
; б) (1001 0010)
; в) (1101 0100)
; г) (1011 0100 0011 0000)
. 2.30. а) (
)
0000 0010
; б) (0011 0100)
. 2.31. а) ( )
(
)
1
x y z x y z z
Ú Ú Ù Ú Ú Ù Ù
; б)
(
)
(
)
1
x y y z
« Ú Ú Ù
. 2.32. а) (
)
(
)
(
)
x y z x y x z
Ù Ú = Ù Ú Ù
; б)
(
)
(
)
x y z x y z
« « = « «; в) (
)
(
)
(
)
x y z x z y z
« Ú = Ú « Ú
; г) (
)
xy x y x y
= « « Ú
. PDF created with pdfFactory Pro trial version www.pdffactory.com
2.33. а) xy x y z
Ú × Ú
; б) (
)
1
x y z z y
Ú × Ú Ú
; в)
(
)
xy x y xyz x y
Ú Ú × × Ú
; г)
(
)
(
)
1 2 2 3
x x x x
« Å ¯; д)
( )
(
)
(
)
1
x y y x y z x y z
Ú Ú Ú × Ú Ú Ú ×
; е)
( )
(
)
1 3 2
1
x x x
Å ¯
. 2.32. Пусть для определенности речь идет о переменной 1
x
. Тогда существует такой набор 2
...,
n
a a
значений переменных (
)
2
,...,
n
x x
, что (
)
(
)
2 2
0,...,1,...,
n n
f f
a a ¹ a a
, т.е. ( ) ( )
2 2
0,...,1,...,
n n
f f
a a = a a
. Согласно определению двойственной функции верны равенства (
)
( )
*
2 2
0,...,0,...,
n n
f f
a a = a a
и (
)
( )
*
2 2
1,...,1,...,
n n
f f
a a = a a
, которые можно переписать в виде (
)
( )
*
2 2
1,...,0,...,
n n
f f
a a = a a
и (
)
( )
*
2 2
0,...,1,...,
n n
f f
a a = a a
. Следовательно, равенство ( ) ( )
2 2
0,...,1,...,
n n
f f
a a = a a
можно также записать в виде (
)
(
)
* *
2 2
1,...,0,...,
n n
f f
a a = a a
. Таким образом, существует набор 2
...,
n
a a
такой, что (
)
(
)
* *
2 2
0,...,1,...,
n n
f f
a a ¹ a a
. Это означает, что (
)
*
1 2
,,...,
n
f x x x
существенно зависит от переменной 1
x
. 2.35. а) 1 2 1 2 1 2 1 2
x x x x x x x x
Ú = Ú Ú; б) 1 2 1 2 1 2 1 2
x x x x x x x x
= Ú Ú; в) 1 2 1 2
x x x x
¯ =; г) 1 2 1 2 1 2
x x x x x x
Å = Ú; д)
1 2 3 1 2 3 1 2 3 1 2 3
x x x x x x x x x x x x
Ú Ú Ú; е)
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
x x x x x x x x x x x x x x x
Ú Ú Ú Ú. 2.36. а) ( )
(
)
(
)
1 2 1 2 1 2
x x x x x x
Ú Ú Ú; б) 1 2
x x
Ú
; в) (
)
(
)
(
)
1 2 1 2 1 2
x x x x x x
Ú Ú Ú; г) ( )
(
)
1 2 1 2
x x x x
Ú Ú; д) (
)
(
)
(
)
(
)
1 2 3 1 2 3 1 2 3 1 2 3
x x x x x x x x x x x x
Ú Ú Ú Ú Ú Ú Ú Ú; е) ( )
(
)
(
)
1 2 3 1 2 3 1 2 3
x x x x x x x x x
Ú Ú Ú Ú Ú Ú. 2.37. а) СДНФ: 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
x x x x x x x x x x x x x x x
Ú Ú Ú Ú; СКНФ: (
)
(
)
(
)
1 2 3 1 2 3 1 2 3
x x x x x x x x x
Ú Ú Ú Ú Ú Ú; б) СДНФ: 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
x x x x x x x x x x x x x x x
Ú Ú Ú Ú; СКНФ: (
)
(
)
(
)
1 2 3 1 2 3 1 2 3
x x x x x x x x x
Ú Ú Ú Ú Ú Ú; в) СДНФ: 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
x x x x x x x x x x x x x x x
Ú Ú Ú Ú; СКНФ: (
)
(
)
(
)
1 2 3 1 2 3 1 2 3
x x x x x x x x x
Ú Ú Ú Ú Ú Ú; г) СДНФ: 1 2 1 2 1 2
x x x x x x
Ú Ú; СКНФ:
1 2
x x
Ú
. 2.38. а)
1 2 1 2 1 2 1 2 1 2 1 2
1,,,,,,,,
x x x x x x x x x x x x
; б) 3
n
. Указание к б). Каждая переменная может не входить в элементарную конъюнкцию, входить с отрицанием, входить без отрицания. 2.39. а)
1 2 1 2 1 2 1 2 1 3 1 3 1 3 1 3 2 3 2 3 2 3 2 3
,,,,,,,,,,,
x x x x x x x x x x x x x x x x x x x x x x x x
; б) 2
k k
n
C
×
. 2.40. а) 2 3 4
x x x
, 1 3 4
x x x
,
1 2 4
x x x
, 1 2 3
x x x
; б) r
n
C
. Указание. Искомое число элементарных конъюнкций равно числу подмножеств мощности r множества {
}
1 2
1 2
,,...,
n
n
x x x
aa a
. 2.41. а) 1 2 3 2 3 1 3 1 2 1 2 3
1,,,,,,,
x x x x x x x x x x x x
б)
2
n
. Указание к б). Число элементарных конъюнкций равно числу подмножеств множества {
}
1 2
1 2
,,...,
n
n
x x x
aa a
. 2.42. а) 64; б)
2 2
2
n n r
-
-
. Ука зание к а). 1 2
x x
является импликантой для тех и только тех функций, которые на наборах (1,1,0)
и (1,1,1)
равны 1. На остальных шести наборах функций может принимать любые значения, следовательно, число таких функций равно 6
2 64
=
. 2.43. а) ,
x y
; б) ,
x y
; в) ,
xy xyz
; г) ,
x yz
. PDF created with pdfFactory Pro trial version www.pdffactory.com
2.42. а) например, 1 2 3
x x x
; б) например, 2 3 1 2
x x x x
Ú. 2.45. а) 1 2 1 3 2 3 1 2
x x x x x x x x
Ú Ú Ú - сокращенная, 1 2 2 3 1 2
x x x x x x
Ú Ú, 1 2 1 3 1 2
x x x x x x
Ú Ú - тупиковые, они же минимальные ДНФ; б)
1 2 1 3 2 3 1 2
x x x x x x x x
Ú Ú Ú - сокращенная, 1 2 1 3 1 2
x x x x x x
Ú Ú, 1 2 2 3 1 2
x x x x x x
Ú Ú - тупиковые, они же минимальные ДНФ; в) 2 3 4 2 3 4 1 2 3 1 4
x x x x x x x x x x x
Ú Ú Ú - сокращенная ДНФ, 2 3 4 2 3 4 1 4
x x x x x x x x
Ú Ú - тупиковая, она же минимальная; г)
2 3 4 1 3 4 1 2 4 1 2
x x x x x x x x x x x
Ú Ú Ú - сокращенная ДНФ, 2 3 4 1 2 4 1 2
x x x x x x x x
Ú Ú, 1 3 4 1 2 4 1 2
x x x x x x x x
Ú Ú - тупиковые, они же минимальные ДНФ; д) 2 4 1 2 1 4 3 4 1 3 2 3
x x x x x x x x x x x x
Ú Ú Ú Ú Ú - сокращенная ДНФ; 1 2 1 4 2 3
x x x x x x
Ú Ú - тупиковая и минимальная ДНФ; е) 3 4 1 2 2 3 4 1 3 4
x x x x x x x x x x
Ú Ú Ú - сокращенная ДНФ; 3 4 1 2 1 3 4
x x x x x x x
Ú Ú - тупиковая и минимальная ДНФ. 2.46. а)
2 1 1 2
1
x x x x
Å Å Å; б)
2 1 2
x x x
Å; в)
2 1 2 3
1
x x x x
Å Å; г)
3 2 2 3 1 3
1
x x x x x x
Å Å Å Å. 2.47. а)
x xy xyz
Å Å
; б) 1
xyz
Å
. 2.48. а)
x xy
Å
; б)
1 2 3 1 2 2 3
x x x x x x x
Å Å Å Å; в)
1 2 1 2 4 1 2 3 4
x x x x x x x x x
Å Å; г)
1 2 4
1
x x x
Å. 2.49. а)
f yt zx xyzt
= Å Å; б) 1
f x t xy xt zt xzt
= Å Å Å Å Å Å. 2.51. а) 2 1
2
n
-
; б) 2 1
2
n
-
; в) 2 2
2
n
-
; г) 2 2
3 2
n
-
×. 2.52. а) Выписать векторы значений всех самодвойственных функций двух переменных. б) Сколько имеется самодвойственных функций от n
переменных? 2.52. а) (0011)
, (0101)
, (1010)
, (1100)
; б) 1
2
2
n
-
. 2.53. а) 1
2 1
2
n-
-
; б) 1
2 1
2
n-
-
; в) 1
2 1 2 1
2 2
n n-
- -
+
; г) 1
2 2 2 1
3 2 2
n n-
- -
× +. 2.52. Указание. Если f
- самодвойственная функция, то на любых двух противоположных наборах значений переменных она принимает противоположные значения. Следовательно, число наборов, на которых f
принимает значение 1, равно числу пар противоположных наборов длины n, т.е. 1
2
n
-
. 2.56. а) (0,0,0,0)
, (0,0,0,1)
, (0,0,1,1)
, (1,0,0,1)
, (1,0,1,0)
, (1,0,1,1)
; б) 2
k
2.57. а) (0,1,0,1,1,1)
, (0,1,1,1,1,1)
, (1,1,0,1,1,1)
, (1,1,1,1,1,1)
; б) 2
n k
-
. 2.59. 0,1,,,
x xy x y
Ú
. 2.60. Указание. Пусть монотонная функция не сохраняет 0. Поскольку нулевой набор предшествует остальным, монотонная функция на остальных наборах не может быть меньше, чем на нулевом наборе. Значит, из равенства монотонной функции единице на нулевом наборе следует ее тождественное равенство единице. Аналогично рассматривается случай монотонной функции, не сохраняющей единицу. 2.61. а) немонотонна; б) монотонна; в) немонотонна; г) немонотонна. 2.62. Решение. Если (
)
1
,...,
n
f x x
немонотонная функция, то согласно определению найдутся два такие вектора 0
a
%
, 0
b
%
(необязательно соседние) из n
B
, что 0 0
a £ b
%
%
, но ( )
(
)
0 0
f f
a > b
%
%
. Пусть эти наборы различаются в k
1
k n
£ £
координатах. Тогда, меняя по одной координате, можно выстроить последовательность из 1
k
-
наборов 1 1
,...,
k
-
a a
% %
таких, что 0 1 1 0
...
k -
a £ a £ £ a £ b
%
% % %
и каждый следующий набор отличается от предыдущего ровно в одной координате. Так как ( )
(
)
0 0
f f
a > b
%
%
, то в этой последовательности найдутся два соседних набора такие, что a £ b
%
%
, но ( )
(
)
f f
a > b
%
%
. Это и есть искомые наборы. 2.63. а) 6; б) 20. 2.65. а) немонотонная; б) монотонная; в) немонотонная; г) немонотонная. 2.66. а)
(0000 0000 1111 1111)
; б)
(0000 0111 0001 1111)
,
(0000 1111 0000 1111)
, (0001 0111 0001 0111)
, (0001 1111 0000 0111)
, (0000 0000 1111 1111)
, (0000 0001 0111 1111)
, (0001 0001 0111 0111)
. 2.68. Указание. Рассмотреть два случая: (1,1,...,1) 0
f
=
и (1,1,...,1) 1
f
=
.2.70. 0,1,,,,
x x x y x y
Å «. 2.71. а) 1
2
n
+
; б) 2
n
; в) 2
n
; г) 1
2
n
-
; д) 1
2
n
-
; е) 2
n
+
. Решение е). Пусть свободный член полинома Жегалкина равен 1. Поскольку в явном виде (т.е. с ненулевыми коэффициентами) присутствуют только существенные переменные см. 2.50), то из сопоставления значений PDF created with pdfFactory Pro trial version www.pdffactory.com
функции на нулевом наборе и наборе, содержащем ровно одну единицу на месте, соответствующем существенной переменной, следует немонотонность функции. Следовательно, если свободный член равен 1, то функция тождественно равна единице. Пусть теперь свободный член полинома Жегалкина равен 0 и линейная функция имеет, по крайней мере, два существенных аргумента. Тогда на наборе, содержащем ровно две единицы на местах, соответствующих этим существенным аргументам, значение функции равно 0, а на предшествующем ему наборе, содержащим ровно одну единицу на месте, соответствующем одному из этих аргументов, равно 1. Следовательно, функция немонотонна. Остаются два случая. В первом свободный член полинома Жегалкина равен 0 и линейная функция не имеет существенных аргументов, т.е. речь идет о тождественном нуле. Во втором случае, свободный член полинома Жегалкина равен 0 и линейная функция имеет один существенный аргумент, т.е. речь идет о функции ,1
i
x i n
£ £
. 2.72. а) 1
2
n
-
; б) 1
3 2
n
-
×
. 2.72. 2
k
n
C
×
. 2.75. 1
2
n
-
. Указание. Если 1
(,...,)
n
f x x
линейна, то ее полином Жегалкина можно записать в виде 0 1 1 2 2
...
n n
f a a x a x a x
= Å Å Å Å. Так как f
отлична от константы, то среди коэффициентов 1 2
,,...,
n
a a a
есть равные единице. Обозначим через k число таких коэффициентов. Пусть для определенности это 1 2
,,...,
k
a a a
(
1
k n
£ £
). Рассмотрим два случая: 0
0
a
=
и 0
1
a
=
. В первом случае 1
(,...,)
n
f x x
реализуется формулой 1 2
...
k
x x x
Å Å Å
и, значит, обращается в единицу на векторах (
)
1 1
,...,,,...,
k k n
+
b b b b
, у которых некоторое нечетное число координат 1
,...,
k
b b
равны 1, остальные координаты 1
,...,
k
b b
равны 0, координаты же 1
,...,
k n
+
b b
могут принимать любые значения (0 или 1). Каждый набор 1
,...,
k
b b
однозначно задается набором номеров единичных координат, поэтому таких наборов столько же, сколько подмножеств нечетной мощности у множества из k элементов, т.е. 1
2
k
-
. Таким образом, первые k координат вектора (
)
1 1
,...,,,...,
k k n
+
b b b b
можно выбрать 1
2
k
-
способами, а оставшиеся n k
-
координат 2
n k
-
способами. Следовательно, число таких векторов равно 1 1
2 2 2
k n k n
- - -
× =
. Аналогично рассматривается случай 0
1
a
=
. 2.77. Функции Классы функций 0
T
1
T
S
M
L
1 0 + – – + + 2 x
+ + + + + 3 x
– – + – + 4 1 – + – + + 5 x y
Ù
+ + – + – 6 x y
Ú
+ + – + – 7 x y
®
– + – – – 8 x y
«
– + – – + 9 x y
– – – – – 10 x y
¯
– – – – – 11 x y
Å
+ – – – + 2.78. Функции Классы функций 0
T
1
T
S
M
L
1
f
+ + – – – 2
f
+ – – – – 3
f
+ + – – – 4
f
+ – – – – 5
f
+ + – – – 6
f
– + – – – 2.80. а) 1; б) 0; в) ,
x x
; г) 1,,
x x
. 2.81. а), в), г), д), е), ж), з). PDF created with pdfFactory Pro trial version www.pdffactory.com
2.82. Нет. Решение. Возьмем классы функций 0
T
и 1
T
. Их объединение сохраняет ноль или единицу. В частности, ему принадлежат xy
( сохраняющая 0) и 1 (сохраняющая 1). Подставляя 1 в xy
вместо y
, мы получаем x
, которая не сохраняет ни нуля, ни единицы. 2.83. Указание к а). Функции, соответствующие связкам ,
Ù ®
, принадлежат классу 1
T
. Класс 1
T
функционально замкнут, следовательно, любая функция, реализованная над множеством связок {
}
,
S
= Ú ®
, также будет принадлежать классу 1
T
, а x y
Ï
1
T
. 2.82. Решение а). {
}
,x y x yÚ Å Ì
0
T
, следовательно, [
]
[
]
,x y x yÚ Å Ì
0
T
. Осталось доказать, что [
]
,
x y x y
Ì Ú Å
0
T. Действительно, если f
Î
0
T
, то свободный член в полиноме Жегалкина этой функции равен 0, значит, f
можно выразить формулой через {
}
,
xy x y
Å. Но x y x y xy
Ú = Å Å
и, значит, xy x y x y
= Å Å Ú
, следовательно, f
можно выразить формулой над {
}
,
x y x y
Ú Å. 2.85. Указание. В качестве полной системы используйте {,}
x y x
Ú и ли {,}
x y x
Ù. 2.86. а) неполная; б) полная; в) неполная; г) полная; д) полная; е) неполная; ж) полная; з) полная. 2.87. а) нет; б) да. 2.88. {
}
x y
, {
}
x y
¯
, {
}
,0
x y
®, {
}
,0
x y
®, {
}
,0
x y
®, {
}
,
x y x
Ú, {
}
,
x y x
Ù, {
}
,,0
x y x y
« Ù, {
}
,,0
x y x y
« Ú, {
}
,,
x y x y x y
Å Ù «, {
}
,,
x y x y x y
Å Ú «, {
}
,,1
x y x y
Å Ù, {
}
,,1
x y x y
Å Ú. 2.89. Например, {
}
0,1,,
x y z xy
Å Å или {
}
0,1,,
x y z x y
Å Å Ú. 2.90. Указание. Будем рассуждать от противного. Предположим, найдется базис B
, состоящий не менее чем из 4-х функций. Поскольку базис представляет собой полную систему, то в B
найдутся функции 0 1,
,,,
S M L
f f f f f
такие, что 0
f
Ï
0
T
, 1
f
Ï
1
T
, S
f
Ï
S
, M
f Ï
M
, L
f
Ï
L
. Ранее было показано (2.68), что функция 0
f
либо немонотонная, либо несамодвойственная. Следовательно, одна из двух подсистем {
}
0 1
,,,
S L
f f f f
, {
}
0 1
,,,
M L
f f f f
обязательно полна. Значит в B
есть полная подсистема. Получили противоречие с определением базиса. 3. Теория графов 3.1.
3.2. б) и г). 3.3. а)
6
2
3
4
5
1
б
)
в
)
г
)
д
)
е
)
1
2
3
4
б)
1
3
4
а)
2
PDF created with pdfFactory Pro trial version www.pdffactory.com
3.4.
3.5. а) 0 1 0 0
1 0 1 1
;
0 1 0 1
0 1 1 0
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
è ø
б) 0 1 1 0 1
1 0 0 1 1
;
1 0 0 1 1
0 1 1 0 0
1 1 1 0 0
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
è ø
в) 0 0 0 0
0 0 1 1
;
0 1 0 1
0 1 1 0
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
è ø
г) 0 1 1 0 0
1 0 1 1 0
.
1 1 0 0 1
0 1 0 0 1
0 0 1 1 0
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
è ø
3.6. а) 1 1 1 0
0 1 0 1
;
1 0 0 0
0 0 1 1
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
è ø
б) 1 1 0 0 0
1 0 1 1 0
;
0 1 1 0 1
0 0 0 1 0
0 0 0 0 1
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
è ø
в) 1 1 0 0 0
1 0 0 0 0
0 1 1 1 1
.
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
è ø
3.7. 3.8. а) 0 1 1 0
1 0 2 1
;
1 2 0 1
0 1 1 0
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
è ø
б) 0 1 3
1 1 2.
3 2 0
æ ö
ç ÷
ç ÷
ç ÷
è ø
3.9.
2
3
4 5 в
)
1
1
2
3
4
5
6
г
)
3
4
5
6
а
)
e
2
e
3
e
4
e
5
e
1
1
2
4
2
3
4
б
)
e
2
e
3
e
4
e
1
1
2
3
5
6
в
)
e
2
e
3
e
1
1
4
1
2
3
4
а
)
1 2
4 5 б
)
3
1
2
3
4
а
)
1
2 3
б
)
4
5
PDF created with pdfFactory Pro trial version www.pdffactory.com
3.10. а) 0 1 0 1 0
1 0 1 0 0
;
0 0 0 0 1
0 1 0 0 1
0 1 0 0 0
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
è ø
б) 0 1 1 1 0
0 0 0 0 0
.
0 0 0 0 1
0 0 0 0 0
0 0 0 0 0
æ ö
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
ç ÷
è ø
3.11. 3.12. 0,
a
=
1.
b
=
3.13. 1,
a
=
0.
b
=
3.14. .
ii
i
a
å
3.15. а) 2; б) 3; в) 1. 3.16. 3.17. Связных, так как у каждого несвязного графа дополнение связно. 3.18. 3. 3.19. а) 5; б) 2; в) 1. 3.20. Указание: Пусть n
– количество вершин графа. Взять в 3
n
попарно скрещивающихся прямых и расположить вершины графа на этих прямых по одной на каждой прямой. 3.21. Указание: Начать нумерацию с вершины, не имеющей входящих в неё рёбер. 3.22. Неверно. 3.26. 3. 3.27. 1
| |.
n
i i
i =
e -h
å
3.28. а) 0,1,2,3,4; б) 0,1,2,3; в) 0,1,…,5; г) 0,1,2,…,6; д) 0, 1, … , 9. 3.29. а) 1; б) 2; в) 2
m n
+ -
; г) n
; д) 2. 3.30. Да. 3.31. 5. 3.32. ( ) 3,
d G
=
( ) 2,
r G
=
вершины 8 и 9 – центры. 3.33. а) n
; б) 1; в) ( ) 1
r G
=
при 1,
m
=
( ) 2
r G
=
при 2.
m
³
3.34. а) [
]
( )/2;
n
r C n= центром является вершина с номером 1
2
n
+
, если n
– нечётное число, и вершины с номерами 2
n
, 1
2
n
+
, если n
чётное. 3.35. а) 6
 2 64,
= = 5
Ð 6 2 192
= × =; б) Â 12
=
, Ð 30
=
; в) Â
mn
=
, Ð 2
mn n
= -
; г) Â
mn
=
, Ð 2
mn
=
. 3.37. 4-1-2-3-1-5-3-4-5. 3.38. а) Существует эйлеров цикл; б) не существуют; в) существует эйлеров цикл; г) существует эйлеров цикл; д) не существуют. 3.39. а) 2,2 1
;
k
K
-
б) 2,2
.
m k
K 3.40. а) 15678943216384725; б) 2162376578514834. 3.41. а) 1325126543641; б) 1235247845895690631. 3.42. а) Есть гамильтонов путь: 532679841, но нет гамильтонова цикла; б) нет гамильтонова пути. 3.43. а) | | 1
m n
- £
: б) .
m n
=
3.44. Например, (8,6), или (2,8), или (1,6)… Добавление одного ребра не приводит к наличию гамильтонова цикла, а добавление двух, например, (3,7) и (8,6), может привести. 3.46. 3. 3.47. а) Всего 12, неизоморфных 2; всего 55, неизоморфных 4. 3.48. а) 001001010101100111; б)00010111001100010111; в) 0100000111011101. 3.49. а) Не является (единиц больше, чем нулей); б) является; в) не является (среди первых 9 элементов единиц больше, чем нулей); г) является. а
)
б
)
в
)
г
)
а
)
б
)
PDF created with pdfFactory Pro trial version www.pdffactory.com
3.50.
3.52. а) 2331777; б) 22226666; в) 555557999. 3.53.
3.54. а) 17; б) ( 1)( 1)
m n
- -
; в) 1
mn
+
. 3.55. а) Нет; б) да; в) да. 3.56. а) 6; б) ( 1)( 1)
m n
- -
; в) 17; г) ( 1)( 1)
m n
- -
; д) 7; е) 19. 3.58. ( ) 1.
G
n +
3.59. min(,).
m n
3.60. Любое число от 12 до 78. 3.61. 1 или 2. 3.62. ( 1)( 2)
2
n n
- -
. 3.64. а) 1
(346),
C = 2
(367),
C = 3
(4678),
C = 4
(458);
C = б)
1
(1234),
C = 2
(2486),
C = 3
(5687),
C = 4
(1375),
C = 5
(3487),
C = 6
(1265),
C = 7
(1378).
C = 3.65. Например, так: 2
(1425),
C = 3
(1526),
C = 4
(2536).
C = 3.66. 25 15 4 14.
- + =
3.67. а) 6 и 64; б) 36 и 36
2;
в) 17 и 17
2.
3.68. а) 10; б) 14. 3.70. Â 21.
³
3.71. а) 11; б) 20; в) 17. 3.72. а) 3; б) 4. 3.73. а) 2; б) 2 при чётном n
и 3 при нечётном; в) 2; г) 2, если количество вершин не менее двух и 1, если вершина одна. 3.74. а) 3;
c =
б) 4;
c =
в) 3;
c =
примеры раскрасок указаны на рисунке. в
)
1
2
3
4
5 6 7 8
9 10 1
1
1
2
б
)
в
)
а
)
1
2
3
3 2
1
а)
1 2
4 3
2 3
1 4
б)
б)
1
2
3
4 5 6 7
8 9 10
1
1
1
2
а)
1
2
3 4 5
6
7
8
PDF created with pdfFactory Pro trial version www.pdffactory.com
3.75. Да. 3.76. а) P 3
( ) 3;
B
c =
б) P
( ) 5;
G
c =
в) P
( ) 3.
G
c =
Примеры раскрасок указаны на рисунке. 3.77. 3.78. а) 23; б) 6. 3.82. 2 Ã 16.
£ £
3.83. 9. 3.84. а) Да: любой многогранник – это планарный граф; б) нет; в) да; г) да; д) нет; е) нет; ж) нет. 3.85. min(,) 2.
m n
£
3.86. 15. Граф с максимальным количеством рёбер изображён на рисунке. 3.87. 2 Ã 16.
£ £
3.88. 2 Ã 10.
£ £
Указание: надо найти 3 4 5
max( )
n n n+ + +
K
при условии 3 4 5
3 4 5 32.
n n n+ + + =K Графы с максимальным числом граней показаны на рисунке. в)
1
2
3 1
2 3
1
2
3
1
1
3
3
2 2 2 2
1
3 3
1
а
)
1
4 2
1
5
б
)
4
2
3
3
3
2
2 3
1
1
1
2
1 3
3
2
3
1
1 2
2
3
1
3
2
1
3
1
2
3 2
1
3
2
в)
PDF created with pdfFactory Pro trial version www.pdffactory.com
3.89. 3.90. 3.91. (,) 1.
c a t
³
При этом условии max
10.
v = 4. Автоматы 4.1. Граф (а) не является диаграммой Мура никакого автомата, так как на диаграмме не указано, в какое состояние должен переходить автомат, если он находится в состоянии 3
q
и получает на входе символ 1. Граф (б) также не является диаграммой Мура, так как переход из состояния 2
q
при получении символа b
определён неоднозначно. Граф (в) является диаграммой Мура конечного автомата. 4.2. a
b
1
q
0
3
q
0
1
q
1
0
3
q
4
q
1 3
q
0 4
q
1
q
1
1
4.3. 4.4. 4.5.
1 1 1 2
(,) ( (,),) (,);
q ab q a b q b q
j = j j = j = 2 2 1 1 2 2
(,) ( (,),) (,) ( (,),) (,);
q abc q a bc q bc q b c q c q
j = j j = j = j j = j = 2
q
2
q
2
q
2
q
q
1
q
2
q
3
2,2
2,0
2,1
0
,
0
0,2
1,1
0,1
1
,
2
1,
0
1,0
1,0
2,2
0,
1
2,2
0,0
0,0
1
,
2
1,1
1
0
2
а
)
б
)
б
)
s t
5,3 4 2 3,3
4
,
3
4,4 5,2 3,3 8,7 2,2
2,2
6,6 5,5 v = 1
5
m
a
x
а
)
s
t
6,5 2,2
5,4
6,5
6,6 7,5
5,4 4,2 1,1 2 2 3,2
v = 9
m
a
x
PDF created with pdfFactory Pro trial version www.pdffactory.com
1 1 2 2 1
,
a b c a
q q q q q
¾ ¾® ¾¾® ¾¾® ¾¾® поэтому 1 1
(,);
q abca q
j = 1 1 1 2
(,) (,) ( (,),) 0 (,) 00;
q ba q b q b a q ay = y y j = y = 2 1 1 1 2 1
0 0 0 0 1
,
a a a b b
q q q q q q
¾¾® ¾¾® ¾¾® ¾¾® ¾¾® поэтому 3 2
2
(,) 00001.
q a by = 4.6. 0 0 1
1 2 1 2
,
q q q q
¾ ¾® ¾¾® ¾¾® поэтому 1 2
(,001);
q q
j = 3 3 3 3
(,110) (,1) ( (,1),1) ( ( (,1),1),0)
q q q q
y = y y f y f f =
4 4 4
1 (,1) ( (,1),0) 12 (,0) 121.
q q q= y y f = y = 4.7. Решение. 1
(,0) 1,
q
y =
2
(,0) 1,
q
y =
3
(,0) 0,
q
y =
4
(,0) 1,
q
y =
5
(,0) 1.
q
y =
Следовательно, состояние 3
q
отличимо от всех остальных. Мы получаем (пока) следующее разбиение множества 1 2 3 4 5
{,,,,}
Q q q q q q
= на классы, т.е. непересекающиеся подмножества: 3 1 2 4 5
{ } {,,,}
Q q q q q q
= È (далее это разбиение будет измельчаться). Далее вычисляем: 1
(,1) 1,
q
y =
2
(,1) 0,
q
y =
4
(,1) 1,
q
y =
5
(,1) 0.
q
y =
Отсюда следует, что 1
q
не может лежать в одном классе с 2
q
или 5
,
q
2
q
с 1
q
или 4
q
и т.д. Разбиение, полученное ранее, измельчается до следующего: 3 1 4 2 5
{ } {,} {,}.
Q q q q q q
= È È Положим 1 3
{ },
K q
= 2 1 4
{,},
K q q
= 3 2 5
{,}.
K q q
= Покажем, что это окончательное разбиение. Имеем: 1 3
(,0),
q q
j = 4 3
(,0),
q q
j = поэтому 2 1
(,0).
K K
j Í Аналогично получаем 2 2
(,1)
K K
j Í и т.д. Следовательно, классы 1 2 3
,,
K K K
можно считать состояниями нового автомата. Это и есть приведённый автомат, его диаграмма Мура изображена на рисунке. 4.8. Верхняя строка таблицы 11011 определяет разбиение 3 1 2 4 5
:{ } {,,,},
Q q q q q q
s = È нижняя строка - разбиение 1 3 2 4 5
:{,} {,,}.
Q q q q q q
t = È Их пересечение sÇt
– это разбиение 1 3 2 4 5
{ } { } {,,}.
Q q q q q q
= È È Можно проверить, что состояния 2 4 5
,,
q q q
неотличимы друг от друга. Из таблицы автомата V
получается таблица приведённого автомата V
)
: возьмём по одному представителю в каждом классе разбиения .
sÇt
Таким образом, мы получаем: 1
q
Ù
2
q
Ù
3
q
Ù
0
3
q
Ù
1
1
q
Ù
1
1
q
Ù
0
1
1
q
Ù
1
2
q
Ù
0
3
q
Ù
1
4.9. а) Функция f
является детерминированной, так как ( ) ( 1)
b i a i
= -
при 2
i
³ -
не зависит от ( 1),( 2),...
a i a i+ + б) Функция f
не является детерминированной, так как (1)
b
зависит от (2),
a которое неизвестно в момент времени 1.
t
=
в) Функция f
детерминированная, так как 0,åñëè í å÷¸òí î,
( )
( ),åñëè ÷¸ òí î
i
b i
a i i
ì
=
í
î
– не зависит от ( 1),( 2),...
a i a i+ + г) Функция f
детерминированной не является, так как выходная последовательность (1) (2) (3)...
b b b определится только тогда, когда будут известны ( )
a i
для всех .
i
Другое объяснение: 0 0 0111...1...0 0 0111...,
f
¾¾® 0 0 0 0 0 0...0...111111...,
f
¾¾® а это противоречит определению детерминированности. 4.10. а) Функция f
ограниченно детерминированная (множество вершин информационного дерева имеет два класса эквивалентности). б) Функция f
ограниченно детерминированная (4 класса эквивалентности). в) f
не является ограниченно детерминированной. 4.11. Наименьшее число классов эквивалентности равно 4. Один из вариантов разбиения на классы эквивалентности следующий: {,,...},
a d {,,...},
b k K
2
K
1
K
3
0
,
1
1,0
1
,1
0,1
1,
0
0,0
PDF created with pdfFactory Pro trial version www.pdffactory.com
{,...},
h {,...}.
g 4.12. а) Детерминированная; б) детерминированная; в) недетерминированная. 4.13. а) Является; б) не является; в) является. 4.14. а) 3; б) 4; в) 4. 4.15. Пусть 0
q
обозначает начальное состояние, a
q
– состояние, в которое автомат перейдёт, получив на входе символ ,
a
ab
q
– символ b
после ,
a
q
*
– финальное состояние. 4.16. а) Такого автомата не существует: действительно, у входных слов 011 и 010 совпадают первые две буквы, а выходные слова 101 и 111 этим свойством не обладают. Другими словами, функцию 0
(,)
q x
y нельзя продолжить до детерминированной функции :.
f A B
¥ ¥
® б) Условие детерминированности здесь выполнено. Построим диаграмму Мура автомата: 4.17. Решение. Построим информационное дерево: Очевидно, ~,
a b
/
~,
b g
/
~.
a g
/
З начит, количество классов эквивалентности информационного дерева (т.е. количество состояний автомата) не меньше 3. Полагаем 0
{,,,...},
q = a e d 1
{,...},
q = b 2
{,...}
q = g и получаем диаграмму Мура искомого автомата: Пунктиром обозначены стрелки, добавленные для обеспечения полноты диаграммы. Эти стрелки можно направить и в другие кружочки. 4.18. 4.19. q 0
q*
a
,
a
b,b
b,
*
a
q
ab
q
c
,c
a,a
c,c
b,b
a,a
c,c
a,*
c,*
b
,
b
q 0
2
q
1
q
1
,1
0,0
1,0
0
,
1
1
,
0
0,
1
1 0
1 0
0 1
b
a
g
d
e
0
q 0
2
q
1
q
0
,0
1,1
1,1
0
,
1
0,
0
0
,
1
q 0
1
q
0
,
0
1,1
0,1
1
,
0
q
a
b
q
c
q
0
q
a
q'
b
,b
a,b
b,a
a
,
a
c,a
c,*
b,*
b,
[
[
c,
c,b
PDF created with pdfFactory Pro trial version www.pdffactory.com
4.20. Например, 0
q
1
q
2
q
3
q
0
1
q
1
3
q
1
3
q
0
0
q
1
1
2
q
1
0
q
0
0
q
1
1
q
0
4.21. а) ( ) ( ) ( ) ( 1);
u t y t x t u t
= Ú -
б) (1) (2) (3)...011...
u u u = 4.22. Решение. Умножение в полугруппе S
– это отображение .
S S S
´ ®
Так как ( ) ( )
st u s tu
= для всех ,,,
s t u S
Î
то S
– полигон над .
S
4.24. 123 123 123 123 123 123
,,,,,,
123 221 232 332 212 323
( ).
123 123 123 123 123 123
,,,,,
121 223 112 111 222 333
S V
ì ü
æ ö æ ö æ ö æ ö æ ö æ ö
ï ï
ç ÷ ç ÷ ç ÷ ç ÷ ç ÷ ç ÷
ïè ø è ø è ø è ø è ø è ø ï
=
í ý
æ ö æ ö æ ö æ ö æ ö æ ö
ï ï
ç ÷ ç ÷ ç ÷ ç ÷ ç ÷ ç ÷
ï ï
è ø è ø è ø è ø è ø è ø
î þ
4.25. 2
( ).
S V @
PDF created with pdfFactory Pro trial version www.pdffactory.com
Содержание 1. Алгебраические структуры ...................................................................... 3 1.1. Множества и действия над ними ............................................................ 3 1.2. Отображения множеств. Взаимно-однозначное отображение ............ 5 1.3. Бинарные отношения. Их свойства ........................................................ 7 1.4. Понятие группы. Примеры групп ........................................................... 9 1.5. Гомоморфизмы и изоморфизмы групп ................................................ 11 1.6. Подгруппы. Смежные классы. Теорема Лагранжа ............................. 12 1.7. Нормальные подгруппы. Фактор-группы ............................................ 14 1.8. Циклические группы. Строение конечных абелевых групп .............. 15 1.9. Конечные группы до 10-го порядка...................................................... 17 1.10. Линейные коды ..................................................................................... 19 1.11. Коды Хэмминга .................................................................................... 22 2. Теория булевых функций .......................................................................... 24 2.1. Булевы функции и способы их задания ............................................... 24 2.2. Функционально замкнутые классы и полнота ..................................... 35 3. Теория графов.............................................................................................. 44 4. Автоматы ...................................................................................................... 64 Ответы, указания, решения .......................................................................... 85 Методические указания Клюшин Александр Викторович Кожухов Игорь Борисович Олейник Татьяна Анатольевна Сборник задач по дискретной математике. Текст печатается в авторской редакции. Верстка авторов. Подписано в печать с оригинал-макета 25.09.08. Формат 60x84 1/16. Печать офсетная. Бумага офсетная. Гарнитура Times New Roman. Усл. печ. л. 6,96. Уч.-изд. л. 6,0. Тираж 600 экз. Заказ 90. Отпечатано в типографии ИПК МИЭТ. 124498, Москва, Зеленоград, проезд 4806, д. 5, МИЭТ. PDF created with pdfFactory Pro trial version www.pdffactory.com
Автор
zimin
Документ
Категория
Без категории
Просмотров
4 367
Размер файла
1 335 Кб
Теги
дискретка, задачи
1/--страниц
Пожаловаться на содержимое документа