Статья:

Аксиоматика списков

Конференция: XVI Студенческая международная научно-практическая конференция «Технические и математические науки. Студенческий научный форум»

Секция: Физико-математические науки

Выходные данные
Голубева М.Д. Аксиоматика списков // Технические и математические науки. Студенческий научный форум: электр. сб. ст. по мат. XVI междунар. студ. науч.-практ. конф. № 5(16). URL: https://nauchforum.ru/archive/SNF_tech/5(16).pdf (дата обращения: 26.01.2022)
Лауреаты определены. Конференция завершена
Эта статья набрала 194 голоса
Мне нравится
Дипломы
лауреатов
Сертификаты
участников
Дипломы
лауреатов
Сертификаты
участников
на печатьскачать .pdfподелиться

Аксиоматика списков

Голубева Мария Дмитриевна
студент, СНИУ имени академика С.П. Королёва, РФ, г. Самара
Тишин Владимир Викторович
научный руководитель, старший преподаватель СНИУ имени академика С.П. Королёва, РФ, г. Самара

 

В настоящей работе рассмотрен и обоснован метод решения задач теории множеств на основе списков. Описана аксиоматика списков, введено понятие списка. Данный способ очень удобен для решения систем уравнений со множествами.

 

Списки.

Под списком будем понимать именованную совокупность элементов некоторого множества.

Пусть у нас есть некоторое множество:

-элементы данного множества.

Тогда L – список множества А:

-элементы множества A.

Будем говорить, что список пустой и писать L=∅, если список не содержит ни одного элемента.

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

Рассмотрим свойства списков.

Отношения между списками:

1)Включение.

Говорят, что список A включен в список B, если каждый элемент списка A является так же и элементом списка B.

2) Равенство.

Говорят, что список А равен списку B, если каждый элемент списка A соответствует элементу списка B, и наоборот.

3)Строгое включение.

Говорят, что список A строго включен в список B, если каждый элемент списка A является так же и элементом списка B, но при этом А не равен B.

4)Общее положение.

Говорят, что списки A и B, находятся в общем положении и пишут A  B, если выполняются следующие 3 условия:

а) ;

б) ;

в) .

5)Списки не имеют общих элементов.

 

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

1) Объединение. 

Элемент принадлежит объединению списков, если он принадлежит хотя бы одному из списков.

2) Пересечение. 

Элемент принадлежит пересечению списков, если он принадлежит каждому из списков.

3) Разность. 

Элемент принадлежит разности списков, если он принадлежит первому списку и не принадлежит второму списку.

4) Симметрическая разность. 

Симметрическая разность списков определяется как разность объединения и пересечения списков.

5) Дополнение. 

Пусть U- некоторое множество, списком которого является A. Тогда  -дополнение списка A до множества U.  То есть  является списком оставшихся элементов множества U.

 

Принцип решения задач при помощи списков.

Алгоритм решения систем уравнений при помощи списков относительно множеств:

1. Построить множества общего положения, если не известно в каком отношении находятся исходные множества, а если известно, то использовать данные отношения при построении. При построении удобно использовать диаграммы Венна;

2. Составим и пронумеруем различные списки, образованные взаимным расположением исходных множеств;

3. Определим, из каких списков состоит каждое из исходных множеств, то есть представим их в виде совокупности списков;

4. Для каждого равенства в системе подсчитать левые и правые части, состоящие из списков.

5. Сравнить эти подмножества. Те списки, которые не попали в пересечение левой и правой частей будем считать пустыми; 

6. Проверить полученные результаты, с учетом исходных отношений между множествами в системе;

7. Таким образом, мы нашли, в каком отношении находятся исходные множества.

 

Рассмотрим работу данного алгоритма на примере:

      Решить систему    

 

1) Построим множества общего положения АВХ и множество С такое, что  и С  Х. (рис. 1)

2) Символом 1 обозначим список элементов множества А, не попавших ни в одно из множеств BCX, символом 7 – список элементов, попавших во каждое из множеств АВСХ и т.д.

3) Будем иметь: A = {1,2,3,5,6,7}, B = {2,3,4,6,7,8}, C = {3, 7}, X = {5,6,7,8,9}.

 

Рисунок 1.

 

4) BΔC = {2,4,6,8}, XA = {5,6,7}.

5) Эти множества равны в силу первого уравнения системы, значит, списки элементов 2,4,5,7 и 8 пусты.

Получили: A = {1,3,6}, B = {3, 6}, C = {3}, X = {6,9}.

4’) Х\С = {6,9}, АВ = {3,6}. 

5’) Данные множества равны в силу второго уравнения системы, следовательно, списки элементов 3 и 9 пусты, и наши множества примут вид:

A = {1,6}, B = {6}, C = ∅, X = {6}.

6) Видим, что Х=ВBAC = ∅.

Проверим, что, множество Х=В является решением исходной системы. 

Если C = ∅ и BA, то  и можно записать:  

B = {b}, A = {ab}, где ab, - списки элементов.

Пусть Х = В = {b}, тогда: ВΔС B\C = {b},

Х\С = Х = {b}= A\X,

CX = {ab} = AВ.

7) Видим, что все соотношения системы удовлетворяются, т.е. множество Х=В является решением исходной системы при выполнении условий BAC = ∅.

Ответ: Х=ВBAC = ∅.

 

Вывод:

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

Введено понятие списка и обозначены основные операции над списками, отношения между ними.

 

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