IX Международная студенческая научная конференция Студенческий научный форум - 2017

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

Мы решили учебно-исследовательскую задачу об исследовании и количестве каждого из двенадцати видов бинарных отношений, заданных на множестве из n элементов [2]. Значительную помощь при решении данной задачи оказала вычислительная техника. В данной статье мы представим одну из разработанных нами программ, на основе которой были написаны четыре программы, подсчитывающие количества отдельных видов бинарных отношений. Для разработки различных алгоритмов и программ, связанных с ними, мы использовали матричное представление бинарных отношений.

Рассмотрим бинарное отношение P  М  М, где М = {1, 2, …, n}. Определим матрицу АP = [P] = [a_ij] размерности n n бинарного отношения P по следующему правилу:

Между бинарными отношениями P на множестве М = {1, 2, …, n} и матрицами АP, элементы которых равны 1 или 0, можно установить взаимно однозначное соответствие. Количество различных матриц бинарных отношений P, заданных на множестве М, равно количеству размещений с повторениями: [3]. Следовательно, количество всех бинарных отношений P, заданных на n-элементном множестве, равно количеству различных матриц бинарных отношений P размерности n n, то есть тоже равно . Мы разработали алгоритм генерации матриц всех бинарных отношений на n-элементном множестве и написали программу на языке «Паскаль».

Program Z1;

var a: array[1..500, 1..500] of LongInt;

i, j, n: LongInt;

X, Y: LongInt;

Begin

ReadLn(n);

X:=0;

Repeat

{Алгоритм вычисления элементов матрицы бинарного отношения}

Y:=X;

for i:=n downto 1 do

for j:=n downto 1 do begin

a[i,j]:=Y-(Y div 2)*2;

Y:=Y div 2;

end;

{Вывод матрицы произвольного бинарного отношения}

for i:=1 to n do begin

for j:=1 to n do begin

Write(a[i,j]);

end;

WriteLn;

end;

WriteLn;

X:=X+1;

Until X>exp(sqr(n)*ln(2));

End.

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

Приведем пример. Отношение P транзитивно при выполнении условия: если в матрице равной произведению АPᵒАP (АP – булева матрица, задающая бинарное отношение P на n-элементном множестве) на некоторых местах стоят единицы, то на тех же местах в матрице АP тоже стоят единицы. Мы разработали алгоритм, состоящий из двух частей: генерация матриц АP и вычисление произведения АPᵒАP; сравнение единичных элементов матриц АPᵒАP с соответствующими элементами матриц АP и подсчет всех матриц АP, для которых выполняется условие транзитивности бинарного отношения P.

Например, при n = 2 с помощью разработанной нами программы можно вычислить 13 транзитивных бинарных отношений на множестве M = {1, 2}, заданных следующими матрицами:

, , , , , , , , , , , , .

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

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

Таблица 1

Виды бинарных отношений	Количество бинарных отношений P  MM, М = {1, 2, …, n}
	n = 1	n = 2	n = 3
транзитивные б.о.	2	13	171
строгие порядки	1	3	19
квазипорядки	1	4	29
порядки	1	3	19

Литература

1. Евсюкова Е. В. Проектирование курса «Элементы алгебры, логики и теории множеств» на основе технологического подхода // Вестник Вятского государственного гуманитарного университета. – Киров: Изд-во ВятГГУ, 2015. – № 7. Педагогика. Психология. – С. 92-100.

2. Евсюкова Е.В., Оленькова М. Н., Смирнов В.Б. Классификация и исследование различных видов бинарных отношений на множестве // Современное естественнонаучное образование: содержание, инновации, практика. Материалы Всерос. науч.-практ. конф. – Тобольск, 2016. С. 41 - 45.

3. Костин С. В. О компьютерном моделировании в курсе дискретной математики // Проблемы математического образования в вузах и школах России в условиях его модернизации: IV Всерос. науч-метод. конф.: сб. материалов. – Сыктывкар: Изд-во СыктГУ, 2014. – С. 170 - 177.

Код для цитирования: Скопировать