Отношение конгруэнтности позволяет определить так называемую фактор-структуру, носителем которой является множество классов эквивалентности. Приведём примеры.

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

Отношение эквивалентности элементов группы Gпо нормальной подгруппеHявляется отношением конгруэнтности и позволяет определить на множестве смежных классов фактор-группуG/H.

Контрольные вопросы

1. Дайте определение бинарного отношения.

2. Какое бинарное отношение называют транзитивным?

3. Приведите пример бинарного отношения.

4. Какое бинарное отношение называют отношением эквивалентности?

5. Что называют функцией?

Тест II

1. На множестве А={1,3,5,7} задано бинарное отношение R={(x,y):x-y=4}. Какая из пар принадлежит данному отношению?

а) (1,3); б) (3,7); в) (5,1).

2. Какими свойствами обладает отношение “х делит у” на множествеN?

а) рефлексивность,	б) рефлексивность,	в) только рефлексивность.
симметричность,	антисимметричность,
транзитивность;	транзитивность;

3. Элементназывается минимальным, если изследует, что

а) b<a; б) ; в) a<b.

4.Если изследует а₁=а₂, то функцию называют

а) инъекцией; б) сюръекцией; в) биекцией.

5.Является ли функция, гдеf(x)=x²

а) инъекцией; б) сюръекцией; в) биекцией.

Глава III. Булевы функции.

3.1. Определение и основные свойства.

Булевой или логической функцией от n переменных называется функция, определенная на множестве всех двоичных наборов длиныn и принимающая на каждом из них значение 0 или 1. Так как двоичных наборов длины n имеется 2ⁿ , то булевых функций от n переменных . Булевы функции играют важную роль в логике, а также при проектировании различных логических кибернетических устройств, например, электронных вычислительных машин. Так как область изменения каждой переменной и область значений функции есть одно и то же множество, то это позволяет вместо каждой из переменных некоторой функции подставлять другие функции, получая, таким образом, из имеющегося запаса функций новые функции.

Булевы функции от одной переменной f(x) четыре: (неx) и тождественные 0 и 1 .

Булевых функций от 2 переменных 16 .

Перечислим важнейшие из них;

• конъюнкция (логическое ,,И”), обозначаемая или просто;

• дизъюнкция (логическое ,,ИЛИ”) ;

• импликация (следование) ,

• эквивалентность .

Приведем таблицу, задающую 4 указанных функции (таблицу истинности):

x1 x2	x1x2	x1x2	x1x2	x1x2
0 0	0	0	1	1
0 1	0	1	1	0
1 0	0	1	0	0
1 1	1	1	1	1

Заметим, что и, то есть выполнены законы де Моргана. Вообще, булевой функции от переменных можно поставить в соответствие подмножество тех двоичных наборов, на которых она равна1. Тем самым устанавливается изоморфизм между множеством подмножеств2ⁿ- элементного множества с операциями объединения, пересечения и дополнения и множеством булевых функций отnпеременных с операциями дизъюнкции, конъюнкции и отрицания. Поэтому множество булевых функций отn переменных с тремя перечисленными операциями является булевой алгеброй со всеми вытекающими отсюда свойствами.

Заметим, что импликация и эквивалентность могут быть выражены через дизъюнкцию конъюнкцию и отрицание

что непосредственно может быть проверено с помощью таблицы истинности.

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

что вполне отвечает привычному представлению о том, что х₁эквивалентно х₂, если х₁влечет х₂и х₂влечет х₁.

Булева функция называется двойственной к функцииf(x,..., x_n), f**=f. Если f*=f , то f называется самодвойственной. Дизъюнкция и конъюнкция двойственны друг другу.

На множестве двоичных наборов длины n отношение порядка

вводится следующим образом:

Если считать наборы характеристическими векторами подмножеств n-элементного множества, то это отношение на множестве наборов соответствует упорядоченью подмножеств по включению.

Булева функция f называется монотонной, если из следует.