ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2015, том 55, № 1, с. 135-144
УДК 519.7
БИНАРНЫЕ ФУНКЦИИ МНОГОЗНАЧНЫХ АРГУМЕНТОВ. ОБОБЩЕНИЯ И ИССЛЕДОВАНИЯ ДИЗЪЮНКТИВНЫХ НОРМАЛЬНЫХ ФОРМ ДЛЯ ТАКИХ ФУНКЦИЙ1)
© 2015 г. А. В. Панов
(119991 Москва, Ленинские горы, МГУ, ВМК) e-mail: panov.al.vit@gmail.com Поступила в редакцию 05.03.2014 г.
Теория дизъюнктивных нормальных форм, обобщаемая на случай бинарных функций многозначных аргументов. Рассматриваются фундаментальные понятия и свойства этих обобщений. Предлагается эффективный метод построения дизъюнктивных нормальных форм для бинарных функций многозначных аргументов с малым числом нулей. Подробно изучаются дизъюнктивные нормальные формы аналога функции Яблонского. Библ. 8.
Ключевые слова: дизъюнктивные нормальные формы, бинарные функции многозначных аргументов, булевы функции, к-значная логика, функции с малым числом нулей, формула Яблонского.
Б01: 10.7868/80044466915010196
1. ВВЕДЕНИЕ
Предлагаемое обобщение теории дизъюнктивных нормальных форм (ДНФ) булевых функций [1] на случай функций, принимающих значение из множества {0, 1}, зависящих от переменных, которые могут принимать значения от 0 до к — 1, где к > 2. Значительное число разнообразных задач, решение которых сводится к построению дизъюнктивных нормальных форм булевых функций, может быть решено более эффективно при переходе от бинарных переменных к к-значным. Так, в алгоритмах распознавания, основанных на переборе конъюнкций или выделения представительных наборов (см. [2], [3]), часто считается, что описание объектов задано набором бинарных признаков. Использование бинарных функций к-значных аргументов, а точнее, их ДНФ, позволяет уйти от этого ограничения и считать, что признаки, описывающие объекты, принимают значения от 0 до к — 1.
В первой части работы описывается ряд понятий теории ДНФ бинарных функций к-значных аргументов, а также доказываются основные свойства данных ДНФ. Аналогичная теория была введена в [4] и [5] в рамках рассмотрения вопроса о ДНФ функций к-значной логики. В данной работе доказывается ряд свойств, не охваченных в [4] и [5].
Вторая часть посвящена методике построения ДНФ для функций с малым числом нулей. Аналогичная теория для случая булевых функций была введена в [6] и в дальнейшем развита в [7] и [8]. Большое число задач, в том числе и задача распознавания на основе представительных наборов (см. [2], [3]) сводится к построению ДНФ функций, заданных конъюнктивной нормальной формой
■ег \ г М М\ р Р ^ М
Лхь х2,..., хп) = (х v...v хп ) & ...&(х v...v хп ).
При этом требуется построить либо простейшую (кратчайшую или минимальную) ДНФ, ре-ализующую/(х1, х2, ..., хп), либо ДНФ, близкую к простейшей по сложности. Непосредственно перемножение скобок в КНФ неэффективно, т.е. практически невыполнимо даже при сравнительно небольших т. В данной работе предлагается гораздо более эффективный способ построения ДНФ бинарных функций многозначных аргументов, заданных конъюнктивной нормаль-
1) Работа выполнена при финансовой поддержке РФФИ (код проекта 14-01-00824, 14-07-00965).
ной формой (КНФ) или, что тоже — набором нулевых точек. Данный метод позволяет переходить от построения ДНФ функции /(х1, х2, ..., хп) к построению ДНФ функции, зависящей, вообще говоря, от меньшего числа переменных. Представленный способ основан на использовании функций специального вида
) I 0, а! = а2 = ... = ап е D, fD(а!,а2, ...,ап) = \
I 1 иначе,
где D — некоторое подмножество множества {0, 1, ..., к — 1}. Бинарный аналог данной функции был рассмотрен С.В. Яблонским. Большая часть работы посвящена изучению данного класса функций, а точнее их дизъюнктивных ДНФ, при этом предлагается специальный вид тупиковых ДНФ достаточно маленькой сложности.
2. БИНАРНЫЕ ФУНКЦИИ МНОГОЗНАЧНЫХ АРГУМЕНТОВ
Рассмотрим множество Кп, где К = {0, 1, ..., к — 1}, п е Кп — множество векторов длины п из чисел 0, 1, ..., к — 1. Будем рассматривать функции/: Кп —- {0, 1}. Множество всевозможных функций/(х), где х = (х1, ..., хп) е Кп, принимающих значения из множества {0, 1}, обозначим через Рк(х). Для описанного класса функций введем обобщение понятия ДНФ, для этого сначала опишем вид элементарной конъюнкции.
2.1. Определение элементарной конъюнкции
Все множество Кп состоит из кп элементов, для любой функции/(х) е Рк(х) множество Кп можно разбить на прямую сумму двух множеств ^0(/) и таких, что ^0(/) = {х е Кп |/(х) = 0}, = {х е Кп |/(х) = 1}. Для определения элементарной конъюнкции необходимо указать простой способ описания некоторого подмножества множества Ы1(/). Будем рассматривать следующую конструкцию:
М1 м2 мп
х1 х2 •■■ хп ,
где М I с К, М IФ 0, / = 1, ..., п, под этой записью мы будем понимать подмножество множества Кп такое, что х^х^..х^ = {(а1, ..., ап) е Кп | а(- е М V/ = 1, ..., п}, в некоторых случаях, когда это не
будет вызывать путаницы, под х^х^-.х^ мы также будем понимать функцию/(х) е Рк(х) такую, что ^(/) = {(а1, ..., ап) е Кп | а,- е М1 V/ = 1, ..., п}. К элементарным конъюнкциям также отнесем пустое множество. Множество Мх будем называть допустимым множеством для перемен-
м
ной х I, / = 1, ..., п. Иногда для краткости записи, мы будем опускать член х 1 , если М, = К, / е е {1, ., п}. Не трудно видеть, что при к = 2 данное определение элементарной конъюнкции совпадает с определением элементарной конъюнкции для булевых функций.
Опишем теперь обобщение ДНФ для бинарных функций к-значных аргументов, используя введенное определение элементарной конъюнкции.
2.2. ОпределениеДНФ
Начнем с определения дизъюнкции. Пусть даны две функции/(х), g(x) е Рк(х), тогда дизъюнкцией функций/(х) и g(x) будем называть функцию Н(х) = /(х) V g(x), Н(х) е Рк(х) такую, что Ы1(И) = = ^(/) и N1(g). ДНФ функции/(х) е Рк(х) будем называть функцию
к(х) = Щ V Щ V ... V Ц,
где и,- — элементарная конъюнкция, / = 1, ..., I, такую, что ^(/) = М1(Н). При этом будем говорить, что ДНФ реализует функцию/(х). Очевидно, что для каждой функции/(х) е Рк(х) существует реализующая ее ДНФ. При этом такая ДНФ может быть не единственной.
2.3. Некоторые свойства ДНФ
Конъюнкцией двух функций f (x), g(x) e Pk(x) будем называть функцию h(x) = f (x)&g(x), h(x) e e Pk(x) такую, что N1(h) = N1(f) n N1(g). Для любых функций f(x), g(x), h(x) e Pk(x), очевидно, справедливо соотношение
f(x)&(g(x) v h(x)) = f(x)&g(x) vf(x)&h(x). Данную операцию будем называть операцией раскрытия скобок.
Для элементарных конъюнкций имеет место следующая формула:
M1 M2 M N1 N2 Nn M1 n N1 Mn n Nn X1 X2 •■■Xn &X1 X2 •■■ Xn = X1 •■■Xn .
Это свойство непосредственно следует из определения элементарной конъюнкции. При этом если нашлось i e {1, ..., n} такое, что M n N = 0, то правая часть представляет собой тождественный нуль, которому соответствует элементарная конъюнкция (ЭК) пустое множество. Имеет место соотношение
f(x) vf(x)&g(x) = f(x)
(тождество поглощения). Докажем справедливость этой формулы: f(x) v f(x)&g(x) = f(x)&(1 v v g(x)) = f(x)&1 = f(x), где через 1 обозначена тождественная единица (функция, всюду принимающая значение 1).
Для случая ЭК тождество поглощения можно сформулировать в следующем виде:
M1 Mn N1 Nn M1 Mn xj •■■Xn v xj • .. Xn = xj •..Xn
тогда и только тогда, когда N с Mi Vi = 1, ..., n.
Для любого i e {1, ..., n} справедливо соотношение
Mj A Mn Ml B Mn = Mj A и B Mn X1 •.. Xi • .. Xn v X1 • ■■ Xi • ■■ Xn = X1 •■■ Xi •■■ Xn .
Действительно, множества единиц функций в правой и левой частях равенства совпадают и равны: {(a1, ..., an) | a1 e M1, ..., a, e A u B, ..., an e Mn}.
Применение последних двух тождеств будем называть операцией приведения подобных.
Справедлив аналог формулы обобщенного склеивания:
f(x)&XM v g(x)&XN = f(x)&XM v g(x)&XN v f(x)&g(X)&XMu N.
Докажем справедливость формулы, заметим f(x)&xm = f(x)&xm f(x)&g(x)&xm, аналогично
g(x)&XN = g(x)&xN v g(x)&f(x)&XN, тогдаf(x)&xM v g(x)&xN = f(x)&xm vf(x)&g(x)&xM v g(x)&xN v
v g(x)&f(x)&xN = f(x)&xM v g(x)&xN v f(x)&g(x)&( XN vxM ) = f(x)&xM v g(x)&xN v f(x)&g(x)&xM u N, в последнем равенстве мы воспользовались предыдущим тождеством.
Будем говорить, что функция f (x) e Pk(x) поглощает функцию g(x) e Pk(x) или функция g(x) имплицирует f(x), если N1(g) с N1(f).
M1 Mn N1 Nn
Элементарная конъюнкция x1 •..xn имплицирует x1 • .. xn тогда и только тогда, когда Mj с N,, i = 1, ..., n. Это непосредственно следует из определения элементарной конъюнкции.
2.4. Понятие сокращенной, тупиковой, кратчайшей и минимальной ДНФ
Здесь и далее мы будем рассматривать функции, отличные от 0, таким образом, во все рассматриваемые ДНФ не будет ЭК 0. Для функции 0 существует единственная ДНФ ее реализующая, поэтому не ограничивая общности мы не будем распространять дальнейшую теорию, связанную с минимальностью ДНФ на функцию 0 и на ЭК 0 ее реализующую.
Как уже было сказано, для некоторой функции/(х) е Рк(х) может существовать более одной ДНФ ее реализующей. Как и в бинарном случае, возникает задача выделения из всех ДНФ неко-
торой функции минимальных в том или ином смысле. Формализуем понятие минимальности.
М1 М- Мп
Введем сначала понятие ранга ЭК. Рангом ЭК и = х1 ...х¡' ...хп назовем число
п
г( и) = £ к - \М\.
' = 1
Не трудно видеть, что при к = 2 данное определение совпадает с определением ранга ЭК для булевых функций. Данное определение является корректным в том смысле, что если ЭК и1 поглощает ЭК и2, то г(Щ) < г(Ц2). Минимальным рангом ЭК является 0, для ЭК, реализующей функцию тождественной единицы, максимальным рангом ЭК является п(к — 1), так как МФ 0 V I = 1, ..., п, а значит, |М| ^ 1. Рангом ДНФ/ = и1 V и2 V ... V ит назовем число
т
г (/) = £ г( и).
' = 1
Введем сначала понятие сокращенной ДНФ. Пусть дана функция/(х) е Рк(х), ЭК, которую имплицирует /(х), будем называть импликантой /(х). Импликанту и функции /(х) будем называть простой импликантой, если она не поглощается никакой другой отличной от нее импликантой /(х). Дизъюнкцию всех простых импликант функции/(х) будем называть сокращенной ДНФ функции /(х).
Теорема 1. Пусть Fи G — сокращенныеДНФ функцииf, g е Рк(х
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.