Университетские исследования, 2011
Скачать 109.52 Kb.
|
Университетские исследования, 2011 УДК 510.22 Программный калькулятор множеств подмножеств конечных множеств. Шалимов Александр Александрович, arvalan85@mail.ru, Чечулин Виктор Львович, chechulinvl@mail.ru Пермский Государственный университет, ММФ, каф. ПМиИ Россия, 614990, г. Пермь, ул. им. Букирева, 15. Описанна программная реализация алгоритма определения структуры множества подмножеств множества с самопринадлежностью. Ключевые слова: Теория множеств, множество подмножеств, множество с самопринадлежностью, характеристическая функция Шалимов А.А., Чечулин В.Л., 2011. > 1. Предисловие Описание множеств с самопринадлежностью, введённых Миримановым [1], довольствовалось до сих пор, в работах с [2], [3], [4], [5] качественным описанием свойств множеств. Интерес представляют и количественные результаты, относящиеся к определению порядка (мощности) множеств подмножеств конечных множеств, а также структуры такого множества. В данной работе приведена программная реализация алгоритма определения структуры множества подмножеств множества с самопринадлежностью. 2. Описание алгоритма Рассмотрим для начала несамопринадлежащие множества. Пусть АА и А — конечно, |A| = n, nN, и для всех a, aA, a — единичный объект, |a| = 1. Требуется определить структуру множества всех подмножеств множества Exp(A). Для каждого подмножества Вj из А, Вj А, и каждого объекта аi из А определима характеристическая функция (Bj, аi): (1), которая принимает единичные значения, если объект аi принадлежит подмножеству Вj, и нулевые — если не принадлежит. Подпишем значения характеристической функции (1) под соответствующими объектами ai из А,— строка записи соответствует подмножеству Bj, и является некоторым двоичным числом. В этой записи упорядочим такие двоичные строки-числа, получим запись вида: А={a1, a2, a3,… , аn} 1 0 0 … 0 — B1 = {a1} 0 1 0 … 0 — B2= {a2} 1 1 0 … 0 — B3 = {a1, a2} (2). … 1 1 1 1 — Bm= A В записи (2) m строк; строка, состоящая из одних нулей, соответствующая пустому множеству , в эту запись не входит, т. к. по его свойствам, [2], {} = [] = ("ничто" множеств не образует). Таким образом, в записи (2) всего m = 2n – 1 двоичных строк. Доказана теорема. Теорема 1. Для любого несамопринадлежащего конечного множества A, АА, |A| = n, nN, состоящего из единичных объектов, a, aA, |a| = 1, порядок множества его подмножеств Exp(A), равен |Exp(A)| = 2n – 1. □ Рассмотрим самопринадлежащее множество С, такое, что его внутренность1 равна множеству из условия теоремы 1, V(C) = A; то есть С есть простой последователь2 от А; перенумеруем все объекты из С, тогда запись, аналогичная упорядоченной записи объектов множества, такова: C = Сk = {a1, a2, a3,… , аk–1, Сk} (3). То же самое проделаем с характеристической функцией, построенной аналогично (1) для объектов из С и подмножеств Dj, Dj C. Запись двоичных слов, аналогичная (2) в первом приближении такова: C=Сk={a1, a2, a3,… , аk–1, Сk} (4) 1 0 0 … 0 0 — D1 = {a1} 0 1 0 … 0 0 — D2= {a2} 1 1 0 … 0 0 — D3 = {a1, a2} … 1 1 1 1 0 — Dr–1= A 0 0 0 0 1 — Dr= C 1 0 0 … 0 1 — Dr+1 ={a1, C}=C … 1 1 1 1 1 — Ds= C где s=2k. В этой записи среди подмножеств имеются одинаковые,— это те подмножества, которые содержат С, поскольку в этом случает по тереме о транзитивности отношения принадлежности [2] подмножество С, содержащее С, совпадает с С. Если быть точными то, подправляя характеристическую функцию в соответствии с теоремой о транзитивности принадлежности, следует записать предыдущую таблицу (5) чуть иначе. Последние строки, начиная с r-ой, будут одинаковы: C=Сk={a1, a2, a3,… , аk–1, Сk} (5) 1 0 0 … 0 0 — D1 = {a1} 0 1 0 … 0 0 — D2= {a2} 1 1 0 … 0 0 — D3 = {a1, a2} … 1 1 1 1 0 — Dr–1= A 1 1 1 1 1 — Dr= C 1 1 1 … 1 1 — Dr+1 ={a1, C}=C … 1 1 1 1 1 — Ds= C Поэтому количество разных подмножеств множества С определяется первыми r строками, количество их равно r = 2k–1–1+1 = 2k–1. Доказана теорема. Теорема 2. Для самопринадлежащего конечного множества С, такого, что его внутренность V(C)=А несамопринадлежаща, АА, и состоит из единичных объектов, a, aA, |a| = 1, порядок множества его подмножеств Exp(C), равен |Exp(C)| = 2k–1, где k=|C|. □ Очевидно, что если F=P(C)=P2(A) (см. условия теорем 1, 2), то |Exp(F)| = 2k–2 + 1, где k = |F|. Доказана теорема. Теорема 3. Для самопринадлежащего конечного множества F, такого, что его s-я внутренность VS(F)=А несамопринадлежаща, АА, и состоит из единичных объектов, a, aA, |a| = 1, порядок множества его подмножеств Exp(F), равен |Exp(F)| = 2k–s+s–1, где k=|F|. □ Рассуждения о самопринадлежащих множествах более сложной структуры, в общем случае, довольно многообразны, ввиду разнообразия структуры конечных самопринадлежащих множеств. При сложности описания структуры конечных самопридлежащих множеств в общем виде заключение о порядках множеств их подмножеств представляется очень громоздким. Однако, алгоритм формирования подмножеств (с учётом теоремы о транзитивности принадлежности), показанный на примерах построения упорядоченного списка подмножеств (2), (5), пусть и с повторяющимися строками, относительно более прост. Посредством этого алгоритма представляется выполнимым калькулятор порядков самопринадлежащих множеств.  Рис 1. Построение таблицы истинности для конечного множества Для вычисления порядка множества подмножеств конечного множества (может быть и с самопринадлежностью) требуется: а) перенумеровать объекты его составляющие, б) построить множество двоичных слов, соответствующим теоретическим подмножествам, в) пользуясь теоремой о транзитивности принадлежности уточнить значения характеристической функции (подправить двоичные строки), г) вычеркнуть повторяющиеся двоичные строки, д) подсчитать количество оставшихся строк. Это количество строк и будет порядком множества подмножеств исходного множества. Таким образом, получается структура множества подмножеств множества (может быть и с самопринадлежностью). 3. Программная реализация В том случае, если мы имеем дело с множеством с самопринадлежностью, нам необходимо каким-то образом выделить самопринадлежащий элемент множества. В данной программе он обозначается двойкой при составлении характеристической функции.  Рис. 2. Добавление структуры множества в список масок Принцип работы программы. Пользователь задаёт порядок конечного множества (без саммопринадлежности). Программа строит для множества этого порядка таблицу истинности, которая одновременно является характеристической функцией для конечного несамопринадлежащего множества указанного порядка. (Блок-схема этого действия указанна на рисунке 1) После чего пользователь задаёт структуру множества с самопринадлежностью. Эта структура представима в виде: {a1,а2,…,аn-1,А}, где А={a1,а2,…,аn-1,А}, то есть множество самопринадлежаще. Соответствующая ему характеристическая функция будет иметь вид: 1 1 … 1 2, где двойкой обозначается самопринадлежащая часть. Пользователь вводит маску, соответствующую этому множеству в поле “маска”, и эта маска переносится в список, расположенный в правом верхнем углу экрана. Соответствующая блок-схема представлена на рисунке 2).  Рис.3. заполнение второго списка.  Рис. 4. процедура RunПодобных множеств может быть несколько. Поскольку множество с самопринадлежностью конечно, количество элементов этого списка так же будет конечно. После того, как составлена характеристическая функция для несамопринадлежащего множества указанного порядка и есть хотя бы одна запись в списке масок во втором списке, строится таблица заданной структуры с учётом таблицы истинности и битовой маски (блок-схемы представлены на рисунках 3 и 4).  Рис. 5. Заполнение третьего и четвёртого списков После того, как построена таблица заданной структуры с учётом таблицы истинности и битовой маски формируется уточнённая структура подмножеств и её в третьем списке. А также производится сокращение повторяющихся строк запись результата в четвёртый список. Уточнение структуры списка подмножеств производится следующим образом: запоминается позиция двойки в структуре самоприналежащего множества, которая берётся из списка масок; просматриваются все элементы второго списка, и, если в позиции, в которой у выбранной маски стоит двойка, у элемента списка стоит единица, то единица меняется на двойку, если же у элемента списка на этой позиции стоит ноль, то он и остаётся. Для тех позиций в записи самопринадлежащего множества, где стоит единица или ноль при уточнении строки из второго списка действует следующее правило: если либо в строке из списка, либо в записи самопринадлежащего множества стоит единица, то в уточнённом списке на этой позиции ставится единица, если же в обеих строках стоит ноль, то в уточнённом списке остаётся ноль. Эти действия повторяются для всех элементов списка масок (блок-схемы представлены на рисунках 5 и 6) Для упрощения работы программы для случая нескольких масок присутствует также кнопка дублирующая описанные выше действия (блок-схема представлена на рисунке 7).  Рис. 6. процедура Call.  Рис. 7. Действия, задаваемые кнопкой «запись строк в третье окно» При дальнейшем анализе этого списка можно обратно преобразовать запись характеристических функций к записи элементов множества подмножества конечного множества с самопринадлежностью. Внешний вид программы показан на рис. 8.  Рис. 8. Внешний вид программы с результатами контрольного примера Назначение элементов управления: 1. Поле "n=" Задаётся размерность множества с самопринадлежностью (минимум 2). 2. Поле "маска" Задаётся битовая маска, определяющая структуру множества с самопринадлежностью. 3. Кнопка "запись маски в список" Записывается маска из поля "маска" в список, расположенный в правом верхнем углу окна программы. 4. Кнопка "Таблица истинности" Генерируется таблица истинности всех чисел размерности, заданной в поле "n=" в первый список. Строится таблица заданной структуры с учётом таблицы истинности и битовой маски во второй список. 5. Кнопка "Сокращение повторяющихся" Формирование уточнённой структуры подмножеств и запись её в третий список. Сокращение повторяющихся строк и запись результата в четвёртый список. 6. Кнопка "Запись строк в третье окно" Дублируются действия первых двух кнопок для упрощения работы программы для случая нескольких масок. 7. Кнопка "применение масок" Модификация всех четырёх список с учётом новой маски, добавленной в список, расположенный в правом верхнем углу окна программы.  Рис. 9. Пример вычисления4. Примеры вычислений Рассмотрим пример нахождения структуры множества подмножества конечного множества с самопринадлежностью. Для начала рассмотрим процесс вычисления этой структуры вручную. Пусть у нас имеется множество порядка 3. Тогда несамопринадлежащее множество будет выглядеть как A = {a1, a2, a3}. Множество его подмножеств: Exp(A) = {{a1}, {a2}, {a3}, {a1, a2}, {a1, a3}, {a2, a3}, {a1, a2, a3}} = = {a1, a2, a3, [a1, a2], [a1, a3], [a2, a3], [a1, a2, a3]}. Пример самопринадлежащего множества: А1={a1, a2, А1}. Тогда множество подмножеств этого множества будет иным: Exp(A1) = {{a1},{a2},{a1, a2}{a1, A1}, {a2, A1}, {A1}, {a1, a2, А1}}=(после свёртывания) = {{a1}, {a2}, {a1, a2}, {A1}}={a1, a2 , [a1, a2], A1}. Если проделать те же самые вычисления посредством программы, то получим результат, указанный на рис. 9. Из окна программы видно, что даже при добавлении новых масок в список вид результирующего списка (четвёртого) не изменится, см. рис. 10.  Рис. 10, Пример вычисления с добавленными масками. Будем интерпретировать четвёртый список по правилу . То есть в том случае, если i-й элемент массива А принадлежит маске B, то в соответствующей позиции маски стоит единица, если не принадлежит, то в соответствующую позицию маски ставится ноль, а под двойкой понимать самопринадлежащую часть множества. Из этого правила следует, что множество подмножеств конечного самопринадлежащего множества А1 = {a1, a2, А1} будет иметь вид Exp(A1} = {a1, a2 , [a1, a2], A1}. Соответствующие строки: “100”, ”010’ а строчки “112” и “110” интерпретируются как {a1, a2, A1} = A1 и {a1, a2} соответственно. Строчка “000” обозначает пустое множество. 5. Заключение В данной программе реализован алгоритм определения структуры множества подмножеств конечного множества (с самопринадлежностью),— программный калькулятор. Использование такого программного калькулятора множеств подмножеств позволяет облегчить труд вычисления множеств подмножеств с самопринадлежностью, что служит и образовательным целям. Библиографический список 1. Френкель А., Бар-Хиллел И., Основания теории множеств, пер. с англ. под. ред. А. С. Есенина-Вольпина, М.: Мир, 1966,—366 с. 2. Чечулин В. Л., О множествах с самопринадлежностью // Вестник Перм. ун-та, серия Математика. Механика. Информатика, г. Пермь, 2005, сс. 133–138. (реферат в РЖ Математика, 2006., №7, 7А48) 3. Чечулин В. Л., Об упорядоченных структурах в теории множеств с самопринадлежностью // Вестник Перм. ун-та, серия Математика. Механика. Информатика, 2008, сс. 37–45. 4. Чечулин В. Л., Теория множеств с самопринадлежностью (основания и некоторые приложения): монография / В. Л. Чечулин; Перм. гос. ун-т. – Пермь, 2010. – 100 с. http://elibrary.ru/item.asp?id=15267103 5. Chechulin V. L., About the selfconsidering semantic in the mathematical logic // Bull. Symbolic Logic, Vol. 16, Issue 1 (2010), pp. 111–112. Software calculator sets of subsets of finite sets. Shalimov A. A. , arvalan85@mail.ru Chechulin V. L., chechulinvl@mail.ru Perm State University, mathematical faculty Russia, 614990, Perm, Bukirev nom. st, 15. Describes the implementation of the algorithm for determining the structure of the set of subsets to selfconsidering sets. Keywords: Sets theory, selfconsidering set, set of subsets, characteristic function. © Shalimov A. A., Cheсhulin V. L., 2011. Рекомендация специалиста Статья продолжает цикл работ по описанию свойств множеств с самопринадлежностью. Автоматизация вычислений множеств подмножеств конечных множеств может служить и образовательным целям. Описанные в статье результаты являются оригинальными. Статья может быть опубликована. Русаков С. В., д. ф.-м н., проф. 1 Внутренность множества X — это множество всех объектов из Х, за исключением самого Х, см. подробнее в [3]. 2 см. там же [3]. |
Добавить документ в свой блог или на сайт
Похожие:
 | Гоу впо «Иркутский государственный университет» к 90-летию Иркутского... Вторые университетские социально-гуманитарные чтения 2008 года : материалы. – Иркутск : Изд-во Иркут гос ун-та, 2008. – 847 с | | Задачами дисциплины являются Научные и практические исследования. Коллективные и индивидуальные исследования. Роль исследований в различных сферах развития производства.... |
| И 4 статьи, получено: 2 гранта и 184 награды Факультет традиционно принимает активное участие, организует и проводит университетские мероприятия студенческой научной жизни |  | Рабочая программа утверждена на заседании кафедры протокол №10 от... «Статистические методы исследования юридически значимой информации» является освоение закономерностей сбора, обработки, оценки и... |
| Программа по формированию навыков безопасного поведения на дорогах... Программа «Университетские субботы» создана специально для школьников 8-11 классов, учителей, а также студентов колледжей и вузов... | | Программа для подготовки аспирантов специальности 07. 00. 09 «Историография,... «Историография, источниковедение и методы исторического исследования» (07. 00. 00 Исторические науки и археология) [Электронный ресурс]... |
| Пояснительная записка Цели и задачи дисциплины (модуля) Целями преподавания... В. А. Давыденко, А. И. Ковальчук Маркетинг и маркетинговые исследования. Учебно-методический комплекс. Рабочая программа для студентов... | | Пояснительная записка Цели и задачи дисциплины (модуля) Целями преподавания... В. А. Давыденко, А. И. Ковальчук Маркетинг и маркетинговые исследования. Учебно-методический комплекс. Рабочая программа для студентов... |
| Гоу впо «Иркутский государственный университет» четвертые университетскиЕ социально-гуманитарныЕ В издании представлены работы по истории, географии, философии, лингвистике, юриспруденции, политологии, педагогике, социологии,... | | Рекомендации по оформлению реферата практикума по курсу Реферат включает в себя следующие блоки: «введение», «глава I. Обзор литературных источников», «глава II. Цель, задачи, методы, организация... |
| Качество комплекса мероприятий по обновлению системы повышения квалификации... Инновационность такого подхода в том, что обеспечивается овладение новыми компетенциями всеми участниками школьной команды. В настоящее... | | Исследования Тема исследования Концепт abneigung и способы его объективации в современном немецком языке |
| Диссертационного исследования «Когнитивные и лингвокультурологичсекие исследования языка» магистерской программы «Английский язык» на 2014-2015 уч год | | Памятка по организации исследования Продемонстрировать анимированные картинки своим друзьям, родителям и т д и провести опрос по теме исследования |
| «Роль женщины в современном мире» Введение (аннотация, актуальность, проблема, цель и задачи, предмет и объект исследования, гипотеза и методы исследования) | | Доклад Оформление исследовательской работы Детализация цели. Последовательное решение каждой задачи в ходе исследования можно назвать этапами исследования |
