Бинарные отношения. 
Криптографические методы защиты информации. 
Часть 1. Математические аспекты

Подмножество А множества X² называется бинарным отношением на X. Произведением бинарных отношений А и В на X называют бинарное отношение С на X такое, что если (а, Ь) е А и (Ь, с) е В, то (а, с) е С. Рассмотрим важнейшие классы бинарных отношений.

Отношения эквивалентности и конгруэнтности

Бинарное отношение А на множестве X называется:

• 1) рефлексивным, если (х, х) е А для любого х е Х
• 2) симметричным, если из (х, у) е А следует (у, х) е А;
• 3) транзитивным, если из (х, у), {у, z) е А следует (х, г) е А.

Если бинарное отношение является симметричным, рефлексивным и транзитивным, то его называют отношением эквивалентности (обозначение =).

Принадлежность двух элементов множества X одному блоку некоторого разбиения множества X является отношением эквивалентности па множестве X. И обратно, всякое отношение эквивалентности = на множестве X определяет разбиение множества X на классы эквивалентности, т. е. на подмножества, каждое из которых состоит из эквивалентных элементов. Множество классов эквивалентности называют фактормножеством множества X но отношению =, обозначается Х/=. В частности, если X — группа (кольцо и др.), то множество Х/= называют факторгруппой, факторкольцом.

Систему представителей всех классов эквивалентности называют трансверсалом множества X по отношению =. Трансверсал множества по отношению эквивалентности в общем случае определен неоднозначно.

Пример 3.1.

Отношения эквивалентности:

• а) в связи с функцией /: X —> У определим: х = х' для х, х' € X /(.г) = /(.г');
• б) подмножества универсума эквивалентны, если равны их порядки;
• в) п = г для п, ге Л^г равны остатки от деления п и г на натуральное число т. С>

Пусть А = (X,/) — алгебра, где X — основное множество,/есть и-арная операция на X.

Отношение эквивалентности = на X называется конгруэнцией на алгебре А, если оно согласовано с операцией / т. е. если х, = y_t для x_j9 г/, е X, i = 1,…, п, то f (x_ly…_fx_n)=f (y_v…, у_п).