Минимизация КНФ частично-монотонных булевых функций
Булеву функцию назовем частично-монотонной, если она монотонна относительно некоторых из своих аргументов и антимонотонна относительно остальных своих аргументов. Мы доказываем, что конъюнктивные нормальные формы частично-монотонных булевых функций можно минимизировать очень эффективно, используя ли...
Збережено в:
| Дата: | 2017 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Видавничий дім "Академперіодика" НАН України
2017
|
| Назва видання: | Доповіді НАН України |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/126539 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Минимизация КНФ частично-монотонных булевых функций / А.П. Пынько // Доповіді Національної академії наук України. — 2017. — № 3. — С. 18-21. — Бібліогр.: 4 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-126539 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1265392017-11-27T03:02:39Z Минимизация КНФ частично-монотонных булевых функций Пынько, А.П. Інформатика Булеву функцию назовем частично-монотонной, если она монотонна относительно некоторых из своих аргументов и антимонотонна относительно остальных своих аргументов. Мы доказываем, что конъюнктивные нормальные формы частично-монотонных булевых функций можно минимизировать очень эффективно, используя лишь частично-монотонные дизъюнкты. Булева функція зватиметься частково-монотонною, якщо вона монотонна відносно деяких з її аргументів та антимонотонна відносно решти її аргументів. Ми доводимо, що кон'юнктивні нормальні форми частково-монотонних булевих функцій можна мінімізувати дуже ефективно з використанням лише частково монотонних диз’юнктів. A Boolean function is said to be partially monotonic provided it is monotonic with respect to some of its arguments, while anti-monotonic with respect to others. We argue that the conjunctive normal forms of partiаlly monotonic Boolean functions can be minimized in a quite effective way with involving just disjuncts possesing the same partial monotonicity. 2017 Article Минимизация КНФ частично-монотонных булевых функций / А.П. Пынько // Доповіді Національної академії наук України. — 2017. — № 3. — С. 18-21. — Бібліогр.: 4 назв. — рос. 1025-6415 DOI: doi.org/10.15407/dopovidi2017.03.018 http://dspace.nbuv.gov.ua/handle/123456789/126539 510.6 ru Доповіді НАН України Видавничий дім "Академперіодика" НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Інформатика Інформатика |
| spellingShingle |
Інформатика Інформатика Пынько, А.П. Минимизация КНФ частично-монотонных булевых функций Доповіді НАН України |
| description |
Булеву функцию назовем частично-монотонной, если она монотонна относительно некоторых из своих аргументов и антимонотонна относительно остальных своих аргументов. Мы доказываем, что конъюнктивные нормальные формы частично-монотонных булевых функций можно минимизировать очень эффективно, используя лишь частично-монотонные дизъюнкты. |
| format |
Article |
| author |
Пынько, А.П. |
| author_facet |
Пынько, А.П. |
| author_sort |
Пынько, А.П. |
| title |
Минимизация КНФ частично-монотонных булевых функций |
| title_short |
Минимизация КНФ частично-монотонных булевых функций |
| title_full |
Минимизация КНФ частично-монотонных булевых функций |
| title_fullStr |
Минимизация КНФ частично-монотонных булевых функций |
| title_full_unstemmed |
Минимизация КНФ частично-монотонных булевых функций |
| title_sort |
минимизация кнф частично-монотонных булевых функций |
| publisher |
Видавничий дім "Академперіодика" НАН України |
| publishDate |
2017 |
| topic_facet |
Інформатика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/126539 |
| citation_txt |
Минимизация КНФ частично-монотонных булевых функций / А.П. Пынько // Доповіді Національної академії наук України. — 2017. — № 3. — С. 18-21. — Бібліогр.: 4 назв. — рос. |
| series |
Доповіді НАН України |
| work_keys_str_mv |
AT pynʹkoap minimizaciâknfčastičnomonotonnyhbulevyhfunkcij |
| first_indexed |
2025-07-09T05:13:36Z |
| last_indexed |
2025-07-09T05:13:36Z |
| _version_ |
1837145019217084416 |
| fulltext |
18 ISSN 1025-6415. Dopov. Nac. acad. nauk Ukr. 2017. № 3
ОПОВІДІ
НАЦІОНАЛЬНОЇ
АКАДЕМІЇ НАУК
УКРАЇНИ
ІНФОРМАТИКА
doi: https://doi.org/10.15407/dopovidi2017.03.018
УДК 510.6
А.П. Пынько
Институт кибернетики им. В.М. Глушкова НАН Украины, Киев
Email: pynko@i.ua
Минимизация КНФ частично-монотонных булевых функций
Представлено академиком НАН Украины А.А. Летичевским
Булеву функцию назовем частично-монотонной, если она монотонна относительно некоторых из своих ар-
гументов и антимонотонна относительно остальных своих аргументов. Мы доказываем, что конъюнктив-
ные нормальные формы частично-монотонных булевых функций можно минимизировать очень эффектив-
но, используя лишь частично-монотонные дизъюнкты.
Ключевые слова: булева функция, литерал, дизъюнкт, конъюнктивная нормальная форма, конъюнкт, дизъ-
юнктивная нормальная форма.
Булеву функцию с 0�n аргументами 1, , nx … x назовем m-монотонной, где 0� �m n , если
она монотонна по своим (без ограничения общности, первым) m аргументам, но антимоно-
тонна по остальным. Понятно, что собственный (т.е., не содержащий комплементарной пары
i ix x,¬ , ни для какого 1� �i n ) дизъюнкт является m-монотонным, если и только если он
состоит из (не обязательно всех) литералов 1 1+, , ,¬ , ¬m m nx … x x … x . Отметим, что чисто
(анти)монотонные функции – это в точности n -монотонные (соответственно, 0 -монотон-
ные) функции. Типичным примером частично монотонной булевой функции, которая не
является ни чисто монотонной ни чисто антимонотонной, является операция импликации
2 1x x¬ ∨ , а функции, которая не является частично-монотонной, – операция эквиваленции
2 1 1 2( ) ( )x x x x¬ ∨ ∧ ¬ ∨ .
В данной работе мы показываем, что всякая конъюнктивная нормальная форма (КНФ)
такой функции эквивалентна КНФ, состоящей из того же числа m-монотонных собствен-
ных дизъюнктов. Более того, минимальная КНФ получается из КНФ всех m-монотонных
собственных дизъюнктов, превышающих (по-аргументно) рассматриваемую булеву
функцию, путем выбора минимальных (по включению) дизъюнктов. Тем самым, в случае
частично-монотонных булевых функций минимизация гораздо эффективнее, чем в об-
щем случае [1, 2], поскольку фактически в нашем случае все дизъюнкты предварительно
минимизированной КНФ, состоящей из всех минимальных дизъюнктов, превышающих
заданную булеву функцию, оказываются ядерными. Представленные здесь результаты
являются частным (двузначным) случаем результатов работы [3]. Однако, учитывая осо-
© А.П. Пынько, 2017
19ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2017. № 3
Минимизация КНФ частично-монотонных булевых функций
бый интерес алгебры логики в общем контексте дискретной математики [4], мы представ-
ляем здесь самодостаточное изложение материала, сопровождаемое непосредственными
доказательствами.
Итак, рассмотрим m-монотонную функцию f. Начнем с доказательства следующих двух
ключевых лемм, которые являются частными (двузначными) случаями лемм 2.7 и 2.12, со-
ответственно, работы [3].
Лемма 1. Пусть D f� — собственный дизъюнкт. Тогда существует m-монотонный
дизъюнкт f D D⊆′� .
Доказательство. Положим { }1 1m m nD D x … x x … x+∩ , , ,¬ , ¬′ � (в дальнейшем, такой дизъ-
юнкт 'D будем называть m-монотонизацией D ). Возьмем произвольные 1 {0 1}na … a, , ∈ , .
Определим новые значения { }1 0 1nb … b, , ∈ , для всех 0 i n� � следующим образом:
0, если и
1, если и
в противном случае
i
i i
i
i m x D D
b i m x D D
a
∈ ,′⎧
⎪ ¬ ∈ ,′⎨
⎪ .⎩
�
�
�
�
�
Так как D собственный 1 1( ) ( )n nD b … b D a … a, , = , ,′ . Кроме того, в силу m-монотонности
f , мы имеем 1 1( ) ( )n nf b … b f a … a, , , ,� . Поскольку 1 1( ) ( )n nf b … b D b … b, , , ,� , мы тем самым
получаем 1 1( ) ( )n nf a … a D a … a, , , ,′� , что и требовалось доказать.
Лемма 2. Пусть S — конечное множество m-монотонных дизъюнктов, а D — собствен-
ный дизъюнкт, такой что S D∧ � . Тогда сущестаует D D S⊇ ∈′ .
Доказательство. От противного. Предположим, что для каждого d S∈ , существует
dl d D∈ � . При этом
dd il x= ¬ или
dd il x= для некоторого 1 di n� � . Определим значения
1 {0 1}na … a, , ∈ , следующим образом. Во-первых для каждого d S∈ положим:
0, если
1, в противном случаеd
d
i
i m
a
> ,⎧
⎨ .⎩
�
Во-вторых для всех остальных 0 i n� � , положим:
0, если
1, в противном случае
i
i
x D
a
∈ ,⎧
⎨ .⎩
�
Тогда, в силу m -монотонности всех d S∈ , 1( ) 1nS a … a, , =∧ , а, так как D — собствен-
ный дизъюнкт и dl D∈/ для всех d S∈ , 1( ) 0nD a … a, , = . Данное противоречие исходному не-
равенству S D∧ � завершает доказательство.
Условия собственности D и m-монотонности f и всех элементов S в формулировках
лемм 1 и 2 являются необходимыми, как это демонстрируется следующими тождественны-
ми неравенствами, соответственно:
2 1 1( )x x x∨¬� ,
1 2 1 2 2( ) ( )x x x x x∨ ∧ ¬ ∨ � .
С учетом лемм 1 и 2 минимизация исходной КНФ S∧ , заданной m-монотонной буле-
вой функции f, оказывается исключительно простой. А именно, построив m-монотони за ции
всех собственных элементов S и выбрав минимальные по включению дизъюнкты, мы по-
лучаем в результате КНФ S ′∧ .
20 ISSN 1025-6415. Dopov. Nac. acad. nauk Ukr. 2017. № 3
А.П. Пынько
Теорема 1. S ′∧ — минимальная КНФ для f.
Доказательство. По леммам 1 и 2.
В силу дуальности, данные результаты легко переформулируются для дизъюнктивных
нормальных форм (ДНФ). А именно, если f — m-монотонная булева функция, то f¬ —
( )n m− -монотонная функция (при надлежащем обращении своих аргументов). Пусть те-
перь S∨ — произвольная ДНФ для f.
Следствие 1. ( ){ C C S}¬ ¬ : ∈ ′∧ — минимальная ДНФ для f.
Доказательство. По теореме 1.
В заключение данной статьи подчеркнем, что упрощение процедуры минимизации ока-
залось возможным благодаря ядерности элементов S ′, которая вытекает из леммы 2. Это
фактически позволяет избежать перебора подмножеств S ′ , содержащих все ядерные эле-
менты, сразу взяв в качестве искомого подмножества само множество S ′.
ЦИТИРОВАННАЯ ЛИТЕРАТУРА
1. Яблонский С.В. Введение в дискретную математику. Москва: Наука. 1986. 384 с.
2. Quine W.V. On cores and prime implicants of truth functions. American Math. Monthly. 1959. 66, № 9. P. 755—
760.
3. Pynko A.P. Minimal sequent calculi for monotonic chain finitely-valued logics. Bulletin of the Section of Logic.
2014. 43, № 1/2. P. 99—112.
4. Капітонова Ю.В., Кривий С.Л., Летичевський О.А., Луцький Г.М., Печурін М.К. Основи дискретної
математики: В 2 т. Київ: ЛітСофт, 2000. Т. 1: Математичні основи. 380 с.
Поступило в редакцию 25.10.2016
REFERENCES
1. Yablonskiy, S. V. (1986). Introduction to discrete mathematics. Moscow: Nauka (in Russian).
2. Quine, W.V. (1959). On cores and prime implicants of truth functions, American Math. Monthly, 66, No. 9,
pp. 755-760.
3. Pynko, A.P. Minimal sequent calculi for monotonic chain finitely-valued logics. Bulletin of the Section of
Logic, 2014, 43, No. 1/2, pp. 99-112.
4. Kapitonova, J.V., Kryvyj, S.L., Letichevskij, O.A., Luckij, G.M., & Pechurin, M.K. (2000). Foundations of
discrete mathematics (in 2 volumes), Kiev: LitSoft (vol. 1: Mathematical foundations) (In Ukrainian).
Received 25.10.2016
О.П. Пинько
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ
E-mail: pynko@i.ua
МІНІМІЗАЦІЯ КНФ ЧАСТКОВО-МОНОТОННИХ БУЛЕВИХ ФУНКЦІЙ
Булева функція зватиметься частково-монотонною, якщо вона монотонна відносно деяких з її аргументів
та антимонотонна відносно решти її аргументів. Ми доводимо, що кон’юнктивні нормальні форми частко-
во-монотонних булевих функцій можна мінімізувати дуже ефективно з використанням лише частково-
мо но тонних диз’юнктів.
Ключові слова: булева функція, літерал, диз’юнкт, кон’юнктивна нормальна форма, кон’юнкт, диз’юнк-
тив на нормальна форма.
21ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2017. № 3
Минимизация КНФ частично-монотонных булевых функций
A.P. Pynko
V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kiev
E-mail: pynko@i.ua
MINIMIZATION OF THE CONJUNCTIVE NORMAL FORMS
OF PARTIALLY MONOTONIC BOOLEAN FUNCTIONS
A Boolean function is said to be partially monotonic provided it is monotonic with respect to some of its arguments,
while anti-monotonic with respect to others. We argue that the conjunctive normal forms of partiаlly monotonic
Boolean functions can be minimized in a quite effective way with involving just disjuncts possesing the same
partial monotonicity.
Keywords: Boolean function, literal, disjunct, conjunctive normal form, conjunct, disjunctive normal form.
|