Понятие операции, ассоциативной операции, дистрибутивной операции. Понятие алгебры, алгебраической системы, модели. Понятие группоида, полугруппы, коммутативной полугруппы.

Говорят, что на множестве X определена алгебраическая операция (*), если каждой упорядоченной паре элементов поставлен в соответствие некоторый элемент,называемый их произведением.

Ассоциати́вная опера́ция — это бинарная операция , обладающая ассоциативностью или сочетательностью: для любых элементов .

Дистрибути́вность — свойство согласованности двух бинарных операций, определённых на одном и том же множестве. Говорят, что две бинарные операции + и × удовлетворяют свойству дистрибутивности, если для любых трех элементов :

— дистрибутивность слева;

— дистрибутивность справа.

Алгеброй А называется совокупность множества М с заданными в нем операциями.

А=(M,S), где M- носитель,S-сигнатура(множество различных операций).

Алгебраической системой <M;S; O > называется объект, состоящий из трёх множеств: непустого множества M, множества алгебраических операций S, определёных на M, и множества отношений O, определёных на M. Множество M называется носителем алгебраической системы. Если алгебраическая система не содержит операций, она называется моделью, если не содержит отношений, то – алгеброй.

Алгебра А=<M,*> с одной бинарной операцией называется группоид.

Полугруппа - алгебра с одной бинарной операцией, в которой операция ассоциативна:

А=<M,*>, .

Коммутативная полугруппа (абелева полугруппа)- алгебра с одной бинарной операцией, в которой операция ассоциативна и коммутативна:

А=<M,*>, 1. .

2.

Понятие группы. Группа подстановок.

Группой(А=<M,*>) называется множество элементов, на котором задана операция умножения, которая удовлетворяет следующим четырём аксиомам:
Замкнутость группы относительно операции умножения. Для любых двух элементов группы существует третий, который является их произведением:
Ассоциативность операции умножения. Порядок выполнения умножения несущественен:
Существование единичного элемента. В группе существует некоторый элемент E, произведение которого с любым элементом A группы даёт тот же самый элемент A:
Существование обратного элемента. Для любого элемента A группы существует такой элемент A ⁻¹, что их произведение даёт единичный элемент E:

Группа подстановок -совокупность подстановок на некотором множестве X, образующих группу относительно операции умножения подстановок. Иначе, группа подстановок.- это пара (G, X), где G - группа, X - множество и каждому соответствует подстановка множества X такая, что 1) , , и 2) х ^a =х для любого тогда и только тогда, когда a=e - единица группы G

 

Понятие кольца. Кольцо вычетов.

Определение кольца

Кольцом называется множество элементов, на котором определены две операции – сложение и умножение, и в выполняются следующие аксиомы:

1. R.1. Множество является аддитивной абелевой группой.
2. R.2. Для любых двух элементов и из определено их произведение: (замкнутость операции умножения).
3. R.3. Для любых трех элементов , и из выполняется ассоциативный закон, т.е. и .
4. R.4. Для любых трех элементов , и из выполняется дистрибутивный закон, т.е. справедливы равенства: и .

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

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

Кольцо вычетов по модулю

При описании блочных кодов [25, 30, 33] широко используется понятие кольца вычетов по модулю некоторого полинома с коэффициентами из поля .

Для полиномов существуют понятия, аналогичные введенным в 5.8 для чисел, если заменить в этих понятиях слово «число» словом «полином». Так, если при делении полиномов и из на получаются одинаковые остатки, то многочлены и сравнимы между собой по модулю многочлена из или .

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

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

Пример 5.13.Рассмотрим кольцо классов вычетов по модулю полинома над двоичным полем. Полиномы вида , где – произвольный полином, степень которого меньше 2, при фиксированном образуют класс вычетов по модулю . Так как всего имеется 4 разных полинома степени меньше 2, то возможны 4 следующие класса вычетов:

Здесь – произвольный полином. В качестве представителей классов обычно выбирают вычеты наименьшей степени, которые совпадают с полиномами и образуют кольцо классов вычетов по модулю полинома , т.е. множество .

10. Определение поля

Полем называют коммутативное кольцо с единицей, в котором каждый ненулевой элемент имеет мультипликативный обратный элемент (т.е. обратный по умножению).

Другими словами, полем называют множество, которое является аддитивной абелевой группой; ненулевые же элементы этого множества образуют мультипликативную абелевую группу, и выполняется закон дистрибутивности.

По аналогии с группами число элементов поля называется порядком поля. Поля, порядки которых конечны, называются конечными полями. Конечные поля имеют наибольшее значение в теории кодирования.

Отметим некоторые свойства полей, вытекающие из их определения.

1. Для любого элемента поля .

2. Для ненулевых элементов и поля .

3. Для любых элементов и поля .

4. Если и , то .

Пример 5.10Множество всех действительных чисел образует поле. Существует также поле комплексных чисел, поле рациональных чисел, но не может быть поля целых чисел, поскольку обратные элементы по умножению, кроме единицы, не являлись бы целыми.

Пример 5.11. Множество чисел , где – простое число, образует конечное поле, в котором сложение и умножение производятся по модулю .

Пример 5.12.При имеем простейшее двоичное поле, состоящее из двух элементов 0 и 1. Эти элементы являются соответственно единичными элементами относительно операций сложения и умножения по модулю 2, которые определяются правилами: ; ; ; ; . Так как , то операции сложения и вычитания в двоичном поле совпадают, а так как , также совпадают операции умножения и деления. Это поле находит широкое применение в теории и технике помехоустойчивого кодирования.

 

Перестановки

Перестановки. Перестановкой называется расположение элементов множества в определенном порядке.

Теорема. Число перестановок n -элементного множества S, т.е. число способов его упорядочивания выражается формулой P_n=n!.

Символом n! обозначается произведение натуральных чисел от 1 до n: n!=1×2×...× n. Считается, что 0!=1.

Доказательство. Будем последовательно выбирать элементы множества S и располагать их в определенном порядке на n местах. На первое место можно поставить любой из n элементов. После того, как заполнено первое место, на второе место можно поставить любой из оставшихся n -1 элементов и т.д. Тогда по правилу произведения все n мест можно заполнить n ×(п -1)×(п -2)×...×2×1= n! способами. Следовательно, n -элементное множество можно упорядочить n! способами.

 

Перестановки с повторениями

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

Теорема. Число перестановок с повторениями для мультимножества выражается формулой

,

где .

Доказательство 1. Рассмотрим одну перестановку мультимножества и заменим в ней все одинаковые элементы разными. Тогда, число различных перестановок, которые можно составить из рассматриваемой перестановки, равно k ₁!× k ₂!×…× k_m!. Проделав это для каждой перестановки, получим n! перестановок. Следовательно,

C_n (k ₁, k ₂,…, k_m)× k ₁!× k ₂!×…× k_m!= n!,

Число C_n (k ₁, k ₂,…, k_m) называется полиномиальным коэффициентом. Приведем еще одно доказательство данной теоремы.

Доказательство 2. Для упорядочивания мультимножества необходимо из n мест выбрать k ₁ мест для элемента s ₁, что можно сделать способами, затем из n - k ₁оставшиеся мест выбрать k ₂ мест для элемента s ₂, что можно сделать способами и т.д. Тогда число способов упорядочивания мультимножества S по правилу произведения равно (напомнив, что 0!=1)

.

 

 

13. Понятие сочетания. Теорема о числе сочетаний из n элементов по k. Свойства сочетаний.

Сочетанием из n элементов по m (иногда читают просто: из n по m) называется m-элементное подмножество некоторого n-элементного множества.

Теорема. Число сочетаний из n элементов по k определяется по формуле:

= .

Свойства сочетаний

 

Первое свойство непосредственно вытекает из формул:

 

Доказательство:

Составим -элементные сочетания из элементов и разобьем их на два класса:

1-й класс - сочетания, содержащие элемент ;

2-й класс - сочетания, не содержащие элемент .

Если из любого сочетания 1-го класса откинуть элемент , то останется сочетание из , их число .

Сочетания 2-го класса являются -элементными сочетаниями, составленными из , их число . Поскольку любое -элементное сочетание из принадлежит одному и только одному из этих классов, а общее число равно , то приходим к равенству

 

Доказательство:

- это число всех размещений с повторениями из элементов двух типов. Разобьем эти размещения на классы, отнеся в -й класс те, в которые входят элементов 1-го типа и элементов 2-го типа. Размещения k-го класса - это не что иное, как всевозможные перестановки из элементов 1-го типа и элементов 2-го типа. Мы знаем, что число таких перестановок равно