Статья:

ТЕОРИЯ СПИСКОВ И ЕЕ ПРИМЕНЕНИЕ В РЕШЕНИИ ЗАДАЧ ТЕОРИИ МНОЖЕСТВ

Конференция: XXXIV Студенческая международная заочная научно-практическая конференция «Молодежный научный форум: технические и математические науки»

Секция: 6. Математические науки

Выходные данные
Чернов Р.В. ТЕОРИЯ СПИСКОВ И ЕЕ ПРИМЕНЕНИЕ В РЕШЕНИИ ЗАДАЧ ТЕОРИИ МНОЖЕСТВ // Молодежный научный форум: Технические и математические науки: электр. сб. ст. по мат. XXXIV междунар. студ. науч.-практ. конф. № 5(34). URL: https://nauchforum.ru/archive/MNF_tech/5(34).pdf (дата обращения: 15.08.2018)
Лауреаты определены. Конференция завершена
Эта статья набрала 114 голосов
Мне нравится
Дипломы
лауреатов
Сертификаты
участников
Дипломы
лауреатов
Сертификаты
участников
на печатьскачать .pdfподелиться

ТЕОРИЯ СПИСКОВ И ЕЕ ПРИМЕНЕНИЕ В РЕШЕНИИ ЗАДАЧ ТЕОРИИ МНОЖЕСТВ

Чернов Роман Вячеславович
студент 3 курса, факультет информатики, кафедра геоинформатики и информационной безопасности СНИУ имени академика С.П.Королева, РФ, г. Самара
Тишин Владимир Викторович
научный руководитель, доц., кафедра прикладной математики Самарского университета, РФ, г. Самара

 

Введение.

В работе описывается теория списков, которая позволяет решать некоторые задачи теории множеств. Данная теория была использована на интуитивном уровне в [1, c. 15] при решении ряда задач. В данной работе представлен переход от интуитивных размышлений к теории, основанной на теории множеств. Также рассмотрен пример решения системы уравнений относительно заданного множества, как вариант применения данной теории.

Определение α-элементов.

Пусть множества S1,..,Sn находятся в общем положении. Рассмотрим множество индексов а также множества индексов  Каждое из множеств  представляет собой сочетание из n элементов, взятых по m штук.

Определение 1. Введем множества, определяемые следующим выражением:

Множества αk будем называть α-элементами.

Используя свойства  и ,

получим

В результате имеем выражение для α-элементов, аналогичное (1):

Таким образом каждому α-элементу мы поставили в соответствие набор элементов x из множества 

Замечание. При наличии в задаче универсального множества U определим нулевой α-элемент следующим образом:

Свойства α-элементов.

Для α-элементов определим следующий набор свойств:

Докажем данные свойства.

Из определения α-элементов можно сделать вывод о том, что верно либо выражение  либо выражение  либо оба этих выражения сразу. Тогда после раскрытия скобок в выражении (*) получим выражение, которое будет содержать конструкцию вида  Так как  то и 

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

Определение списков.

Определение 2. Каждому множеству  поставим в соответствие множество α-элементов  представимое в виде

Данное множество будем называть списком.

По определению, множество можно представить в виде

Но ранее было доказано, что  Таким образом, список  является аналогом разбиения множества  за тем исключением, что подмножества(α-элементы) могут оказаться пустыми в процессе решения задачи.

Определим условия пустоты α-элементов:

 

Операции над списками.

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

 - пересечение списков.

 - объединение списков.

 - разность списков.

 - симметрическая разность списков.

 - дополнение списка.

Пример. Рассмотрим пример решения системы уравнений относительно множества Х с помощью списков.

Решить систему уравнений

Будем полагать, что A = S, B = S, C = S, X = S4.

Множества индексов:

I1 = {1}, I2 = {2}, I3 = {3}, I4 = {4}, I5 = {1, 2}, I6 = {1, 3}, I7 = {1, 4}, I8 = {2, 3},

I9 = {2, 4}, I10 = {3, 4}, I11 = {2, 3, 4}, I12 = {1, 3, 4}, I13 = {1, 2, 4}, I14 = {1, 2, 3},

I15 = {1, 2, 3, 4}

α-элементы:

α0 = U\(ABCX), α1 = A\(BCX), α2 = B\(ACX), α3 = C\(ABX),

α4 = X\(ABC), α5 = (AB)\(CX), α6 = (AC)\(BX), α7 = (AX)\(BC),

α8 = (BC)\(AX), α9 = (BX)\(CA), α10 = (CX)\(BA), α11 = (BCX)\A,

α12 = (ACX)\B, α13 = (ABX)\C, α14 = (ABC)\X, α15 = ABCX

Составим списки для множеств:

[A] = {α1 , α5 , α6 , α7 , α12 , α13 , α14 , α15}.

[B] = {α2 , α5 , α8 , α9 , α11 , α13 , α14 , α15}

[C] = {α3 , α6 , α8 , α10 , α11 , α12 , α14 , α15}

[X] = {α4 , α7 , α9 , α10 , α11 , α12 , α13 , α15}

.

 иТогда 

,

Тогда 

Т.к  и  то пустых α-элементов не осталось.

Итого  Тогда 

Заключение.

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

 

Список литературы:
1. Тишин В.В. Дискретная математика в примерах и задачах. – СПб.: БХВ-Петербург, 2008. – 352 с.: ил. – (Учебная литература для вузов).