2-КНФ булевых функций, задающих топологии на конечном множестве

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

ФУНДАМЕНТАЛЬНЫЕ НАУКИ
УДК 519. 7
Н.П. БАШОВА
Запорожский национальный технический университет
ЕВ. СТЕГАЩЕВ
Запорожский национальный университет
2-КНФ БУЛЕВЫХ ФУНКЦИЙ, ЗАДАЮЩИХ ТОПОЛОГИИ НА КОНЕЧНОМ МНОЖЕСТВЕ
Рассматриваются свойства булевых функций, моделирующих топологии на конечном множестве: слабоотрицательность, слабоположительность, биюнктивность. Предлагается алгоритм построения 2-КНФ булевой функции по ее таблице истинности. Доказывается теорема о виде 2-КНФ булевых функций, задающих близкие к дискретной топологии на конечном множестве.
Ключевые слова: булевы функции, существенные и несущественные переменные, 2-КНФ булевых функций, топологии на конечном множестве.
Н.П. БАШОВА
Запорiзький нацюнальний техшчний ушверситет
е.В. етегАнцЕВ
Запорiзький нацюнальний ушверситет
2-КНФ БУЛЕВИХ ФУНКЦ1Й, ЯК1 ЗАДАЮТЬ ТОПОЛОГП НА СК1НЧЕН1Й МНОЖИН1
Розглядаються властивостг булевих функцт, що моделюють топологи на сктчетй множит: слабовгд'-емтсть, слабододаттсть, бгюнктивнгсть. Пропонуеться алгоритм побудови 2-КНФ булево'-1'- функцП за ii таблицею iстинностг. Доводиться теорема про вигляд 2-КНФ булевих функцт, що задають близью до дискретно'-1'- топологп на сктчетй множинi.
Ключовi слова: булевi функцП, iстотнi та нектотт змтт, 2-КНФ булевих функцт, топологи на сктчетй множит.
N.P. BASHOVA
Zaporozhye national technical university
E.V. STEGANTSEV
Zaporozhye national university
2-CONJUNCTIVE NORMAL FORM OF THE BOOLEAN FUNCTIONS, WHICH DEFINE THE TOPOLOGIES ON THE FINITE SET
One considers such properties of the Boolean functions, which modeling the topologies on the finite set as the weak negativeness, the weak positiveness and the bijunctiveness. An algorithm of the construction of the 2-conjunctive normal form of the Boolean function with the help of its truth table has been proposed. The theorem, connected with the form of the 2-conjunctive normal form of the Boolean functions, which define the topologies, which are close to the discrete topology on the finite set, has been proved.
Keywords: Boolean functions, essential and nonessential variables, 2-conjunctive normal form of the Boolean function, topologies on the finite set.
Постановка задачи
Задача перечисления и подсчета числа топологий на конечном множестве сформулирована давно, но до сих пор не решена. Интерес к этой задаче сохраняется и в настоящее время, о чем свидетельствуют многочисленные публикации по этой теме.
Анализ последних исследований и публикаций
В работе [4] было показано, что задача подсчета всех транзитивных графов с p вершинами есть в точности задача о подсчете всех топологий на p -элементном множестве. Использование ориентированных графов для моделирования топологий на конечных множествах оказалось эффективным и привело к получению ряда важных результатов. В работах [3,5,6] были подсчитаны все топологии на n -элементном множестве в k -классах при 2 & lt- k & lt- 12 и T0 -топологии в k -классах при n + 4 & lt- k & lt- n + 6, уточнены
полученные ранее результаты, подсчитаны все топологии в k -классах с k & gt- 6 • 2n 4 элементами при n & gt- 4. Рассматривался вопрос о наименьшей возможной мощности множества, на котором можно реализовать топологию с фиксированным числом элементов.
Формулирование цели исследования
Описать топологии на конечных множествах булевыми функциями специального вида. Решить задачу нахождения вида 2-КНФ булевых функций, моделирующих топологии на п -элементном множестве,
в которых число элементов больше 2п 1.
Изложение основного материала исследования 1 Описание топологий на конечном множестве булевыми функциями Определение 1. Булева функция /(х^, Х2,… хп), п & gt- 1 называется биюнктивной, если / = 1 или существует представление I в виде 2-КНФ
Л
~2 / р р
I —
Г *1 & gt- Г ^
а
Л xsl л Л
V =1 1 i=1
(хв1 V хв 2
Г 2 '-
/
где & gt- 0, 12 & gt- 0, а, Д-1, Д-2 е {0,1}, х0 = х{, х1 = х{ [1].
Пример 1. Булева функция /(х1, Х2, Х3) = (х1 V Х3)(х2 V Х3) является биюнктивной.
Определение 2. Вектор, а = (а,---, ап) еУп назовем выполняющим функции I (х1,Х2,… хп), если I (а1 ,…, ап) = 1. Множество всех выполняющих векторов функции / называется её областью истинности и обозначается Еу.
В работе [2] вводятся понятия слабоположительной и слабоотрицательной булевых функций и формулируются следующие критерии:
Свойство 1 (критерий слабой положительности). Функция I (х1,Х2,… хп) ф 0 является слабоположительной, если и только если для любых двух выполняющих векторов {а, /З} с Еу этой функции справедливо свойство
(а V в) е Еу.
Свойство 2 (критерий слабой отрицательности). Функция I (х1, Х2,… хп) Ф 0 является слабоотрицательной, если и только если для любых двух выполняющих векторов {а, в} с Е^у этой функции справедливо свойство
(алв)е ЕI.
Для классов биюнктивных (Ы), слабоположительных (ШР) и слабоотрицательных (№Ы) булевых функций имеет место равенство [2]
ШР П ШЫ = Ы П ШР П ШЫ. (1)
Свойство 3. Каждая булева функция из Ы П ШР П ШЫ является 0-выполнимой и 1-выполнимой, то есть I (0,0,…, 0) = 1 и I (1,1,…, 1) = 1.
Доказательство. Каждая булева функция из Ы П ШР П ШЫ имеет 2-КНФ, все дизъюнкции
которой имеют вид х^ V. Поэтому каждая такая дизъюнкция на наборах (0,0,…, 0) и (1,1,___, 1) равна 1, а
значит и 2-КНФ равна 1.
Определение 3. Топологией на конечном множестве X называется такой набор т его подмножеств, в который включается 0 и все X, а также вместе с любой парой элементов набора в него включается их объединение и пересечение.
Каждому булевому вектору (а1,а2,…, ап) из области истинности булевой функции I (х1,х2,…, хп) поставим в соответствие подмножество п -элементного упорядоченного множества X = (х1,х2,…, хп), содержащее элемент х{, если, а = 1, и не содержащее элемент х^, если, а = 0 и рассмотрим совокупность всех таких подмножеств для заданной булевой функции. Из этого соответствия, определения топологии, равенства (1), критериев слабоположительной и слабоотрицательной функций следует
Теорема 1. Совокупность подмножеств п -элементного упорядоченного множества X = (х1, х2,…, хп) образует топологию на данном множестве тогда и только тогда, когда соответствующая этому набору булева функция I (х1, х2,…, хп) принадлежит Ы П ШР П ШЫ.
В этом случае о самой булевой функции будем говорить, что она задает топологию.
Следствие. Булева функция I (%1,х2,…, хп), задающая топологию на п-элементном множестве, имеет 2-КНФ вида
/ (х V X, 2).
2 Алгоритм построения 2-КНФ булевой фуНКции, задающей топологию на конечном множестве
Вход: булева функция, заданная таблицей истинности.
Выход: 2-КНФ заданной функции.
Метод.
1. Выделяем наборы, на которых булева функция принимает значение 0.
2. В первом наборе фиксируем х^ Ф ху и составляем дизъюнкции (хг- V х у) и (хг- V х j).
3. Выбираем ту из них, которая равна нулю.
4. Если для выбранной дизъюнкции не существует набора (х1,…, х^,… ху, • • •, хп), на котором заданная функция равна 1, записываем её в 2-КНФ и переходим к следующему набору. В противном случае переходим к шагу 2 для других переменных хк Ф х1 из этого же набора.
5. Процесс заканчивается после перебора переменных из последнего набора, на котором функция равна 0.
3 Вид 2-КНФ булевых функций, задающих близкие к дискретной топологии на конечном множестве
Пусть на конечном множестве X задана топология т. Семейство т конечно и для числа элементов в нем (открытых множеств) будем использовать символ |т|. Будем говорить, что топология т, заданная на
п — элементном множестве, является близкой к дискретной, если Ц & gt- 2п 1.
Определение 4. Минимальной окрестностью Ма элемента, а е X в топологии т на X называется пересечение всех окрестностей этого элемента.
Поскольку семейство т конечно, то для любого элемента, а топологического пространства X существует минимальная окрестность Ма и только одна.
Определение 5. Индексом элемента, а е X относительно топологии т назовем число тёТ (а), равное количеству отличных от, а элементов в его минимальной окрестности Ма.
Пример 2. Пусть на множестве X = {а, Ь, с, ё} задана топология т = {0, а, Ь, аЪ, ас, аЬс, аЬсё}. Минимальные окрестности и индексы всех элементов множества X: Ма = {а}, тёт (а) = 0- МЪ = {Ь}, тёт (Ь) = 0- Мс = {ас}, тёт © = 1- М^ = {аЬсё}, тёт (ё) = 3.
Определение 6. Последовательность индексов всех элементов из X, записанных в порядке неубывания, будем обозначать у (т) = (а^, а2,…, ап) и называть вектором топологии.
Будем считать, что элементы множества X занумерованы так, что тё х^ = а^.
Все близкие к дискретной топологии описываются следующей теоремой, которая сформулирована в работе [1].
Теорема 2. На множестве X, X = п топология т будет близкой к дискретной тогда и только тогда, когда её вектор имеет вид:
1) у (т)=(0,…, 0, ап), 1 & lt-ап & lt-п — 1, причем Ц = 2п-1 + 2п 1 ап
Г
2) у (т) =
0,…, 0,1,…, 1
к
1 & lt- к & lt- п — 2, если П Мх = {у} и Му = {у}. Здесь
т=к+1
Ы = 2п-1 + 2к-11.
3) у (т)=(0,…, 0,1,1), если Мх ПМх =0. При этом Ц = 2п-1 + 2
В этой статье мы исследуем вид 2-КНФ булевых функций, задающих близкие к дискретной топологии на конечном множестве. Нам понадобится топологическое толкование понятий существенной и несущественной переменной булевой функции.
Определение 7. Переменная х^ е X называется несущественной в топологии т, если для любого и ет выполнены условия: и и {хг- }ет и и {хг- }е т. В противном случае переменная х^ называется существенной.
Утверждение (критерий несущественности переменной). Переменная x? будет несущественной в топологии т тогда и только тогда, когда множество {x?} одновременно открыто и замкнуто.
Доказательство. Пусть x? — несущественная переменная. Тогда, по определению 3, так как 0ет, получим 0 U {x? }={x? }ет, то есть {x?} - открытое множество. Аналогично, так как X ет и, по определению 7 X {x? }е т, то {x?} - замкнутое множество.
Обратно, из того, что {x?} открытое множество следует, что для любого U ет множество U U {x?} открыто как объединение открытых множеств. Так как {x?} - замкнуто, то U {x? }= U П (X {x?}) открыто как пересечение открытых множеств. Утверждение доказано.
Обозначим символом e? булев вектор, в котором на i -том месте стоит 1, а на остальных 0, то есть ч
0 … 010 …0. Тогда минимальной окрестностью элемента xi (переменной xi) булевой функции
i-1
f (xi, x2,…, xn), описывающей топологию на множестве X = {xi, x2,…, xn }, есть множество
Mx, = {Л x | f (x) = 1, x л ei = ei}.
Основным результатом этой статьи является следующая
Теорема 3. Булева функция f (xi, x^,---, xn) задает близкую к дискретной топологию на множестве X = (x1, x2,…, xn) тогда и только тогда, когда ее 2-КНФ может быть приведена (при необходимости, после перенумерации переменных) к виду:
an (-
1) л (xn v x1), где 1 & lt- an & lt- n -1. При этом число существенных переменных функции равно an +1-
i=1
2) (xn v xi) л (жп-1 v xi) л — +1 v xi), где 1 & lt- к & lt- n -2 и i = 1, к. При этом функция будет содержать (n — к +1) существенных переменных-
3) (xn v xi) л (яп-1 v xj), где i = 1, n — 2, j = 1, n — 2, i Ф j. При этом существенных переменных будет 4.
Доказательство.
1) Приведем вначале доказательство для an = n -1. В этом случае 2-КНФ имеет вид (xn v x1)(xn v x2)… (xn v xn1) и все переменные существенны. В область Ef входят булевы векторы
(«1,a2,., an-1,0) при любых значениях ai, i = 1, n -1 и вектор (1,1,…, 1). Минимальной окрестностью элемента x1 есть множество {x1}, поскольку один из указанных наборов имеет вид (1,0,…, 0). Аналогичный вывод можно сделать для элементов x2, x3,…, xn-1. Минимальная окрестность элемента xn определяется
единственным содержащим этот элемент набором (1,1,___, 1) и совпадает с множеством X. Таким образом,
f
вектор топологии, задаваемой булевой функцией с такой 2-КНФ, имеет вид 0,0,…, 0, n -1
V n 1 j
Для an = n — 2 в 2-КНФ (xn v x1)(xn v x2). (xn v xn-2) отсутствует переменная xn-1, то есть она является несущественной. Булевы векторы из области Ef этой функции: (а,"2,-., О,-2,0,0),
(а1,а2,…, ап — 2,1,0) при любых значениях а^, 7 = 1, п — 2 и (1,1,…, 0,1), (1,1,___, 1). Здесь минимальные
окрестности первых п — 1 элементов являются одноточечными множествами, а минимальная окрестность
элемента xn равна {x1, x2, -, xn-2, xn }. Они определяют вектор
(
0,0,…, 0, n — 2 V n 1
топологии.
(
В общем случае получим an +1 существенных переменных и вектор
0Д… Л an
n-1
соответствующей топологии на X.
2) Рассмотрим случай 7 = 1. При к = 1 булева функция имеет 2-КНФ вида (хп V х)(хи-1 VХ1)… (х2 VХ1) и ее Еу состоит из булевых векторов: (1,а2,…, ап) при любых значениях
а1, 7 = 2, п и (0,0,…, 0). Все переменные соответствующей топологии существенны и ее вектор имеет вид

о,!,!,---,].
п-1 у
При к = 2 имеем 2-КНФ вида (хп V Х1)(хп-1 V Х1)… (хз V Х1), то есть переменная Х2 несущественна. Область Еу булевой функции состоит из булевых векторов: (1,0,аз,…, ап), (1,1,аз,…, ап) при любых

0,0,1,1,…, 1
7 = 3, п и (0,0,…, 0), (0,1,…, 0), поэтому вектор топологии имеет вид
V п -2 у
При произвольном к, 1 & lt- к & lt- п — 2 булева функция имеет 2-КНФ вида
(хп V Х1)(хп-1 V Х1)… (Хк +1 V Х1), число несущественных переменных равно к — 1 и вектор

соответствующей топологии равен
0… 0,1,1… 1
. Здесь минимальные окрестности первых к
V n-к у
элементов являются одноточечными множествами, минимальные окрестности остальных элементов двухэлементны, причем все они имеют общий элемент Х1.
3) Если 2-КНФ булевой функции имеет вид (xn v Xj)(xn-1 v Xj), i Ф j, то существенными будут
только 4 переменные. Набор значений из Ef запишем для i = 1, j = 2: (а1,а2,а^,…, ап2, 0,0),
(1,a2,a3,., an-2,0,1), («1,1,"з,…, ап _ 2,1,0), (1,1,___, 1). Из этого следует, что первые две и последние две
переменные являются существенными, остальные — несущественными. В топологии, задаваемой этой булевой функцией, минимальные окрестности первых n _ 2 элементов являются одноточечными множествами, а минимальные окрестности остальных переменных — двухточечные непересекающиеся множества.
Поскольку полученные векторы совпадают с соответствующими векторами из теоремы 2, то теорема 3 доказана.
Выводы
Использование булевых функций специального вида для описания топологий на конечном множестве позволило перечислить все близкие к дискретной топологии. Этот аппарат можно использовать для подсчета числа элементов в топологиях, а также для оценки числа топологий.
Список использованной литературы
1. Башова Н. П., Величко И. Г., Стеганцева П. Г. «Существование и строение топологий близких к дискретной на конечном множестве». Тезисы Семнадцатого международного научно-практического семинара «Комбинаторные конфигурации и их применение». Кировоград, 2015, с. 13−15.
2. Горшков С. П. О некоторых свойствах слабо положительных и слабо отрицательных булевых функций. // Прикладная дискретная математика. — 2013. — № 2(20). — С. 5−13.
3. Benoumhani M. The number of topologies on a finite set // Journal of Integer sequences — 2006. — Vol. 9, no. 2 — Article 06.2.6.
4. Harary F. Combinatorial problems in graphical enumeration. // Applied Combinatorial Mathematics (E. F. Beckenbach Ed.) — 1964 — Chap. 6. — P. 185−217.
5. Ragnarsson К. Obtainable sizes of topologies on finite sets / Ragnarsson Kari, Bridget Eileen Tenner // Journal of Combinatorial Theory, Series A. — 2010. — Vol. 117, is. 2. — P. 138−151.
6. Kolli M. Direct and elementary approach to enumerate topologies on a finite set // Journal of Integer sequences — 2007. — Vol. 10, no. 3. — Article 07.3.1.

ПоказатьСвернуть
Заполнить форму текущей работой