12_0_1_63762

Министерство образования Республики Беларусь

Учреждение образования

Международный государственный экологический

университет имени А. Д. Сахарова

Кафедра автоматизированной обработки информации

А. И. Митюхин

ЭЛЕМЕНТЫ КОНЕЧНОЙ АЛГЕБРЫ

Учебно-методическое пособие по курсам ЗАЩИТА ИНФОРМАЦИИ,

ОСНОВЫ ЗАЩИТЫ ИНФОРМАЦИИ для студентов специальности «Информационные технологии в экологии» дневной и заочной форм обучения

Минск

2010

УДК 621.391.37/39(075.8)

ББК 32.973. я 73 М 66

Рекомендовано к изданию НМС МГЭУ им. А.Д.Сахарова (протокол № 6 от 16 марта 2010 г.)

Автор:

А. И. Митюхин, доцент кафедры автоматизированных систем обработки информации МГЭУ им. А. Д. Сахарова

Рецензенты:

доцент кафедры сетей и устройств телекоммуникаций БГУИР к.т.н. Астровский И. И.;

зав. кафедрой автоматизированных систем обработки информации МГЭУ им. А. Д. Сахарова, к.т.н. Кереселидзе Е. В.

Митюхин, А. И.

М66 Элементы конечной алгебры : уч.-метод. пособие по дисциплинам «Защита информации», «Основы защиты информации» для студентов специальности «Информационные технологии в экологии» дневной и заочной форм обуч. / А. И. Митюхин. ‒ Минск : МГЭУ им. А. Д. Са-

харова, 2010. ‒ 44 с. : ил.

ISBN 978-985-6931-54-6.

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

Рассмотрены элементарные сведения теории множеств, групп, колец, полей Галуа. Эти конструкции конечной алгебры лежат в основе теории криптологии, прикладного кодирования, теории дискретных унитарных и теоретико-числовых преобразований, цифровой обработки сигналов. Приведены примеры решения задач, упражнения, контрольные вопросы и задачи.

	УДК 621.391.37/39(075.8)
	ББК 32.973. я 73
ISBN 978-985-6931-54-6	© Митюхин А. И., 2010
	© Международный государственный
	экологический университет
	имени А. Д. Сахарова, 2010

2

Введение

Основой построения наиболее важных известных кодов, корректирующих ошибки, является их алгебраическая структура. Существование особых структурных закономерностей в строении таких кодов желательно по двум причинам:

‒они облегчают изучение свойств кода;

‒обеспечивают возможность практической реализации кодов на аппаратно ‒ программном уровне.

В современной дискретной математике под алгеброй понимается наука о множествах произвольных математических объектов, между которыми установлены алгебраические операции.

3

1 ТЕОРИЯ МНОЖЕСТВ

1.1 Понятие множества

Под множеством понимается некоторая определенная совокупность объектов или элементов. Конечные множества можно описывать, перечисляя их элементы. Например, ={ , , } есть множество, содержащее буквы , , . При перечислении множества часто используется описание характеристического свойства элементов этого множества. Например, H = {α0, α1, α2, …, αn-1} описывает множество степеней элемента α, где {0, 1, 2, …, n} ‒ множество положительных целых чисел.

Множество задается путем указания характеристического свойства, т. е. свойства, которому удовлетворяют элементы этого множества. Для задания множества используют запись { : обладает свойством Р} – множество содержит только те элементы, которые обладают свойством Р.

Определение 1.1. Если есть один из объектов множества G, говорят, принадлежит G. Принадлежность множеству G записывается как

G. Если не является элементом G, это записывается как G. На-

пример, α2 {α0, α1, α2, …, αn-1}, но αn G.

Определение 1.2. Множество есть подмножество множества (обозначается ), если каждый элемент принадлежит множеству G, т. е. если , то G. Если не является подмножеством G, то это записывается как G.

Например, {0, 3} {0, 1, 2, 3, 4, 5}, но {0, 3, 6} {0, 1, 2, 3, 4, 5}.

Множества равны, если они содержат одни и те же элементы.

Определение 1.3. Пусть G и – некоторые множества. G = , если для любого имеем: G тогда и только тогда, когда .

Замечания:

–порядок перечисления элементов множества роли не играет. На-

пример, {0, 1, 2, 3, 4, 5} = {0, 2, 1, 3, 4, 5};

–каждый элемент множества может входить во множество не более одного раза.

Определение 1.4. Пустое множество есть множество, которое не содержит элементов (обозначается Ø). Универсальное множество, или универсум, обозначаемое , есть множество, обладающее таким свойством, что все рассматриваемые множества являются его подмножествами.

Например, множество всех целых или натуральных чисел есть универсальное множество. В математическом анализе универсальное множество есть множество действительных чисел. В теории кодирования множество всех векторов n-мерного пространства образует универсальное множество.

4

1.2 Операции над множествами

Рассмотренные ниже операции над множествами позволяют строить новые множества, используя существующие.

Определение 1.5. Пересечением множеств G и называется множество, состоящее из тех и только тех элементов, которые принадлежат и G, и . Пересечение множеств обозначается G ∩ . Определение записывается как G ∩ = : и .

Например, если G ={0, 1, 2, 3, 4, 5} и ={0, 3, 6}, то G ∩ ={0, 3}.

Замечание ‒ В описании пересечения множеств G и использована связка «и». В дальнейшем убедимся, что символу ∩ соответствует символ логической схемы «И» ‒ &.

Пересечение множеств в общем случае определяется следующим образом.

Определение 1.6. Если = 1, 2, … , , то = 1 ∩ 2 ∩ 3 ∩

… ∩ = : для всех i .

Объединением множеств G и называется множество, состоящее из всех элементов, которые принадлежат хотя бы одному из множеств G или . Объединение множеств G и обозначается G . Определению соответствует запись H = : или H .

Например, если G ={0, 1, 2, 3, 4, 5} и ={0, 3, 6}, то G = ={0, 1, 2, 3, 4, 5, 6}.

Замечание ‒ В описании объединения множеств G и использова-

на связка «или». В дальнейшем убедимся, что символу соответству-

ет символ логической схемы «ИЛИ» ‒ 1.

Объединение множеств в общем случае определяется следующим

образом.
Определение 1.7. Если =		1, 2, … , , то	= 1 2	3
… =	: для всех i .

Определение 1.8. Пусть G и множества. Разностью множеств и называется множество всех тех элементов , которые не содержатся в . Определению 1.8 соответствует запись − H = : и H .

Например, если ={0, 1, 2, 3, 4, 5} и ={0, 3, 6}, то – = {1, 2, 4, 5}.

Симметрическая разность множеств и (обозначается ∆ ) есть множество ( – ) ( – ).

Например, если ={0, 1, 2, 3, 4, 5} и ={0, 3, 6}, то – ={1, 2, 4, 5}, ( – ) = {6}. ∆ ={1, 2, 4, 5, 6}. Симметрическая разность множестви состоит из тех элементов, которые принадлежат или множеству , или .

5

Замечание ‒ В описании симметрической разности множеств G и

использована связка «или». В дальнейшем убедимся, что символу ∆

соответствует символ логической схемы «ИСКЛЮЧАЮЩЕЕ ИЛИ» – .

Определение 1.9. Дополнение множества , обозначаемое ‒ это множество элементов универсума, которые не принадлежат .

= − = { : и }.

Например,	если		– множество положительных целых чисел,
а = {2, 4, 6,	…}	−	множество четных положительных чисел, то

={1, 3, 5, …} − множество нечетных положительных чисел.

Теорема 1.1. Для произвольных множеств и справедливо равенство – = ∩ .

Доказательство следует из определений разности – , дополнения= G – H и пересечения ∩ .

Теорема 1.2. Для множеств , , справедливы равенства

) ∩ = ∩ ∩ ;) ∩ = ∩ .

Широко используемой операцией над множествами является декартово произведение или прямое произведение множеств.

Определение 1.10. Декартово произведение множеств и , обозначаемое × , есть множество {( , ): и }. Объект ( , ) называется упорядоченной парой с первой компонентой х и второй компонентой у.

Множество × состоит из всех упорядоченных пар ( , ), при этом имеет значение порядок компонент. Если элементы множеств и

представляют собой действительные числа,							то × есть декартова
плоскость. Если содержит элементов,						а содержит элементов, то
множество × состоит из элементов.
Пример 1.1. Пусть =		1, 2, 3, 4 , =				1, 2 . Тогда
× =	1,1 , 1, 2 ,	2, 1 ,	2, 2	,	3, 1 ,		3, 2 ,	4, 1 ,	4,2 .
Декартово произведение
× =	1,1 , 1,2 ,	1,3 ,	1,4	,	2,1 ,		2,2 ,	2,3 ,	2,4 .
Декартово произведение
	× =	1,1 ,	1,2 ,		2,1 ,		2,2 .

1.3. Диаграммы Венна

Диаграммы Венна позволяют иллюстрировать операции над множествами. Множества в диаграммах Венна изображаются внутренними частями кругов, их пересечениями, объединениями и пр. На рисунке 1.1

6

приведена диаграмма Венна для множества . На рисунке 1.2 показана диаграмма Венна для двух множеств: и . Как видно, множества пересекаются.

G

G H

Рисунок 1.1 Рисунок 1.2

Множеству ∩ соответствует закрашенная часть кругов на рисунке 1.3. Множеству соответствуют закрашенные области кругов на рисунке 1.4.

G	H	G	H
	Рисунок 1.3		Рисунок 1.4

Разность множеств и – ( − H) представлена множеством в виде закрашенной области на рисунке 1.5.

G H

Рисунок 1.5

Теорема 1.3. Пусть , и – подмножества универсального множества . Тогда справедливы

1)законы идемпотентности

∩ = ;

= .

2)свойства коммутативности

∩ = ∩ ;

= .

7

3)свойства ассоциативности

∩ ( ∩ )= ( ∩ ;

( )= ( ) .

4)свойства дистрибутивности (распределительный закон)

∩ ( )= ( ∩ ) ( ∩ );

( ∩ )= ( ) ∩ ( ).

5)двойное дополнение

= .

6)свойства тождества

= ;

∩ = .

7)свойства дополнения

= ;

∩ = .

8)законы де Моргана

(A B) = ∩ ; (A ∩ B) = .

1.4.Булевы алгебры

Всовременной математике под алгеброй понимается наука о множествах произвольных математических объектов, между которыми установлены алгебраические операции.

Определение 1.11. Алгебраическая операция – это правило, которое произвольному набору элементов данного множества ставит в однозначное соответствие строго определенный элемент этого же множества.

Определение 1.12. Бинарная операция определяет для каждой упорядоченной пары элементов множества элемент этого же множества.

1.4.1. Аксиомы булевой алгебры

Булева алгебра – это область математики, которая занимается логическим анализом. Свое название эта алгебра получила в честь Дж. Буля, основоположника математической логики. Операции и законы булевой алгебры применяются к логическим символам так же, как обычная алгебра оперирует символами, представляющими численные величины. Булевы алгебраические структуры широко используются в синтезе и конструировании логических электронных схем.

Определение 1.13. Булева алгебра есть множество , содержащее элементы 0 и 1, на котором заданы бинарные операции логического сложения и логического умножения. Для всех элементов множества= { , , } должны выполняться следующие аксиомы:

8

1)ассоциативности

( ) = ( ;

+ ( + ) = ( + )+ .

2)коммутативности

= ;

+ = + .

3)дистрибутивности

( + ) = + ;

+ ( ) = ( + ( + ).

4)тождества

+ 0 = ;

1 = .

5)дополнения

+ = 1;

= 0.

Элемент 1 называется единичным элементом; элемент 0 называется нулевым элементом; элемент называется дополнением .

Теорема 1.4. Для элементов и булевой алгебры выполняются следующие законы:

а) идемпотентности

+ = ;

= .

б) свойства констант

+ 1= 1;

0 = 0.

в) законы поглощения

+ ( ) = ;

( + ) = .

Теорема 1.5. Для элементов и булевой алгебры выполняются соотношения:

а) закон инволюции

= .

б) дополнения законов тождества

0 = 1;

1 = 0.

в) законы де Моргана

+ = a ;

= a + .

Замечание – Каждая аксиома булевой алгебры состоит из пары равенств, которые являются двойственными в том смысле, что, если в од-

9

ном равенстве заменить логическое сложение + на логическое умножение и на +, 0 на 1 и 1 на 0, получим другое равенство. Для примера рассмотрим первый из законов де Моргана + = a . Легко убедиться, что двойственное к нему соотношение = a + .

Вновь рассмотрим теорему 1.3 теории множеств. Сравнивая ее теоремами булевой алгебры, можно сформулировать следующий вывод: подмножества , и образуют булеву алгебру, где операции пересечения ∩ и объединения аналогичны логическим операциям + и соответственно. Элементами этих подмножеств являются единичный и нулевой элементы.

1.5. Отношения

Ранее была рассмотрена такая операция над множествами, как декартово произведение.

Определение 1.14. Подмножество R декартова (прямого) произведения × множеств и называется бинарным отношением на паре множеств , . Если ( и ) (записывают как ), то говорят, что элемент связан с элементом отношением . Если = , то отношение есть подмножество × .

Пример 1.2. Пусть =	1, 2, 3, 4 , = 1, 2 . Декартово произведе-
ние множеств и равно
× = 1,1 , 1, 2 ,	2, 1 , 2, 2 , 3, 1 , 3, 2 , 4, 1 , 4,2 .

Выпишем упорядоченные пары на множествах , , принадлежащие отношению

= {( , ) : + = 5}.

Тогда = {(3, 2), (4,1)} есть отношение множеств и . Множество × содержит восемь элементов, поэтому существует

28 = 256 подмножеств множества × . Следовательно, имеется 256 отношений на × .

Пример 1.3. Выписать упорядоченные пары, принадлежащие отношению на множествах = {1, 3, 5, 7} и = {2, 4, 6}, если = {( , ) : < }.

Решение. = {(1, 2), (1, 4), (1, 6), (3,4), (3,6), (5,6)} есть отношение множеств и .

1.5.1. Свойства отношений

Рассмотрим отношения, заданные на одном множестве . Определение 1.15. Отношение на множестве × :

– рефлексивно, если ( , ) для всех из ; ‒ антирефлексивно, если из ( , ) следует ≠ ;

10