Синтез аналитической записи функций непрерывной логики по таблицам выбора

Научные руководители:
Доктор технических наук, профессор Слепцов А.И.
Кандидат технических наук, доцент Зайцев Д.А.

Работу выполнил:
В.Г.Сарбей

Содержание

Введение

1. Постановка задачи

2. Основные понятия

2.1. Квазибулева алгебра

2.2. Канонические формы записи функций непрерывной логики

3. Табличное представление

3.1. Таблица выбора

3.2. Перекрывающиеся строки

3.3. Теорема 1

4. Построение ФНЛ по таблице выбора

4.1. Конституэнты минимума

4.2. Лемма

4.3. Теорема 2

4.4. Критерий непрерывности функции, заданной таблично

5. Примеры синтеза функций

6. Минимизация функций непрерывной логики

6.1. Простые импликанты

6.2. Итеративный консенсус

6.3. Теорема о минимизации

7. Примеры минимизации функций по таблице

8. Запись функций, не являющихся ФНЛ, в предикатной алгебре выбора

8.1. Операции предикатной алгебры выбора

8.2. Алгоритм 1 записи кусочно-непрерывной функции, заданной таблицей выбора

8.3. Алгоритм 2

9. Примеры синтеза кусочно-непрерывных функций

Заключение

Список литературы

Введение

В первой половине девятнадцатого века попытка Джорджа Буля формализовать пропозициональную логику привела к понятию булевой алгебры. В своей монографии "Исследование законов мышления, на которых основаны математические теории логики и вероятностей" Буль первым указал на связь логических исчислений с основаниями теории вероятностей. Эта связь основывается на аналогии между событиями и высказываниями, позволяющей обслуживать логику и теорию вероятностей одним формальным аппаратом. Грубо говоря, "событие" - это то, что может произойти или не произойти; "высказывание" - это то, что может быть истинно или ложно. Среди событий есть достоверные и невозможные; высказывания могут оказаться тождественно истинными или тождественно ложными.

Классическое исчисление высказываний использует двузначную алгебру. Однако реальные, практически значимые данные и знания редко бывают абсолютно точными и достоверными.

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

Используются, например, к-значные логики. Часто указывают, что непрерывная логика, еще называемая бесконечнозначной, континуумзначной, À-значной, является обобщением к-значной логики.

Непрерывная логика является, в частности, языком представления неточности в системах искусственного интеллекта, экспертных и интеллектуальных системах, математическим аппаратом проектирования аналоговых автоматов, используется в нейронных сетях в качестве одного из законов преобразования распространяемых сигналов.

В этой работе представлены результаты исследования вопросов синтеза и минимизации функций непрерывной логики, заданных с помощью таблиц выбора. Ее основная цель - описать и обосновать метод построения аналитической записи в непрерывной логике и в предикатной алгебре выбора функций, заданных с помощью таблиц выбора.

1. Постановка задачи

Одним из способов представления функций непрерывной логики является таблица выбора. Задачи синтеза функций по таблицам выбора возникают при проектировании гибридных и аналоговых вычислительных устройств, а также в других областях применения непрерывной логики, обзор которых представлен в книге "Непрерывная логика" В.И.Левина (1991 год). Структура исходной таблицы при этом определяется внешними спецификациями проектируемого устройства или узла. Известны алгоритмы синтеза функции непрерывной логики по таблицам выбора специального вида, например, по таблицам упорядоченного выбора. В.И.Левин отмечает, что общий алгоритм синтеза аналитической записи функции непрерывной логики в квазибулевой алгебре по произвольной таблице выбора неизвестен.

Заметим, что способ определения алгебры непрерывной логики как квазибулевой алгебры является в настоящее время наиболее распространенным, но не единственным. Так в бесконечной логике Мак-Нотона использованы две базисные операции: отрицание и влечение, причем результат операции влечения в общем случае не совпадает со значением одного из аргументов либо отрицания аргумента.

Система функций бесконечнозначной логики (f₁...f_n) называется полным базисом в некотором классе Á, если любую функцию из Á можно представить суперпозицией функций f₁...f_n. Базис называется минимальным, если удаление хотя бы одной из f_i делает систему неполной.

На основании изложенного определим постановку задачи следующим образом: на множестве всех таблиц выбора найти класс всех тех и только тех функций, которые возможно записать в квазибулевой алгебре по заданной системе базовых операций квазибулевой алгебры, разработать алгоритм синтеза аналитической записи функций непрерывной логики, заданных таблично. Исследовать связь ДСНФ и МДНФ ФНЛ. Разработать алгоритм синтеза аналитической записи в предикатной алгебре выбора функций, заданных с помощью таблиц выбора, но не являющихся функциями непрерывной логики.

2. Основные понятия

2.1 Квазибулева алгебра

Определим алгебру непрерывной логики как квазибулеву алгебру D = (C, Ù, Ú, Ø), где C = [A,B] - непрерывный отрезок вещественных чисел с заданным на нем обычным образом отношением линейного порядка £; M = (A+B) / 2 - середина отрезка, называемая медианой.

Отрезок C рассматривается как множество значений истинности логических переменных; при этом A представляет собой значение степени истинности абсолютно ложного высказывания, а B - значение степени истинности абсолютно истинного высказывания. Преобразование (x - A) / (B - A) переводит: [A,B]®[0,1]. Базовые операции вводятся для любых x, y Î C следующим образом:

---

1. конъюнкции или произведения   xÙy = min (x,y)
2. дизъюнкции или суммы          xÚy = max (x,y)     (1)
3. отрицания                    `x = 2M - x

---

Буквой называется обозначение некоторой логической переменной либо ее отрицания. Произведение букв будем называть фразой, а сумму букв - предложением.

Через базовые операции можно ввести дополнительные операции, используемые в традиционной логике: импликацию, эквивалентность, исключающую дизъюнкцию и другие. Знак операции конъюнкции далее в формулах алгебры непрерывной логики будем опускать.

Квазибулева алгебра D является дистрибутивной решеткой с псевдодополнениями или алгеброй Клини; в ней выполняется большинство законов, характерных для двоичной логики [1]:

---

1. идемпотентности         xÚx = x                 xÙx = x
2. коммутативный           xÚy = yÚx               xÙy = yÙx
3. ассоциативный           xÚ(yÚz) = (xÚy)Úz       xÙ(yÙz) = (xÙy)Ùz
4. дистрибутивный          xÚ(yÙz) = (xÚy)Ù(xÚz)   xÙ(yÚz) = (xÙy)Ú(xÙz)
5. операции с константой   xÚA = x                 xÙB =x
6. поглощения              xÚ(xÙy) = x             xÙ(xÚy) = x
7. Де-Моргана              Ø(xÚy) =`xÙ`y           Ø(xÙy) =`xÚ`y
8. Клини                   (xÙ`x)Ù(yÚ`y) = (xÚ`x)  (xÙ`x)Ú(yÚ`y) = (yÚ`y)
9. двойного отрицания      ØØx = x

---

Указанные законы являются аксиомами алгебры Клини. Особенностью непрерывной логики является невыполнение законов исключенного третьего и противоречия:

---

xÚ`x № B    xÚ`x № A

---

Функцией непрерывной логики будем называть функцию f: Cⁿ ® C, образованную путем суперпозиции конечного числа базовых операций, примененных к независимым переменным x₁, x₂...x_n Î C. Класс Â функций непрерывной логики также является алгеброй Клини, где

---

1.  f1*f2 (x) = f1(x) Ù f2(x)
2.  f1+f2 (x) = f1(x) Ú f2(x)
3. `f(x) = 2M - f(x)

---

Равные формулы всегда реализуют одну функцию, но не обязательно наоборот: две разные формулы могут обозначать одну функцию. Поэтому в качестве стандартных форм ФНЛ принимают дизъюнктивные (ДСНФ) и конъюнктивные (КСНФ) совершено нормальные формы [1].

2.2 Канонические формы записи функций непрерывной логики

Теорема Биргофа гласит, что в конечной дистрибутивной решетке каждый элемент однозначно представим в виде несократимой суммы неразложимых элементов. Следствием этой теоремы является существование ДСНФ булевых функций.

Некоторый элемент a решетки A называется неразложимым, если его нельзя представить в виде суммы элементов, каждый из которых отличен от самого а. Сумма элементов решетки несократима, если ее члены попарно несравнимы.

Противоречивой называется фраза, содержащая для некоторого индекса вместе с аргументом его отрицание.

Фундаментальной называется фраза (предложение) непротиворечивая или, содержащая для всякого i = 1...n, аргумент x_i или его отрицание Øx_i. Это означает, что, в отличие от аналогичных форм функций двоичной логики, элементарные конъюнкты (дизъюнкты) могут вместе с аргументом содержать его отрицание.

В решетке ФНЛ неразложимыми элементами являются все фундаментальные фразы и только они [1]. Как следствие этого утверждения: ФНЛ однозначно представима в виде дизъюнкции фундаментальных фраз. Таким образом, дизъюнктивной совершенной нормальной формой записи ФНЛ является несократимая сумма фундаментальных фраз.

3. Табличное представление функций непрерывной логики

3.1 Таблицы выбора

Из определения базовых операций следует, что ФНЛ всегда принимает значение одного из своих аргументов либо его отрицания. Кроме того, значение функции полностью определяется способом упорядочения аргументов и их отрицания с помощью отношения £. Таким образом, произвольная ФНЛ может быть однозначно представлена таблицей, в которой перечислены все варианты упорядочения аргументов и их отрицаний и указаны значения функций для каждого варианта. Такие таблицы в соответствии с [1] будем называть таблицами выбора. В таблице 1 представлена таблица выбора для функции F = x₁Úx₂`x₃.

Всего существует (2n)! способов упорядочения n аргументов и их отрицаний. Однако, значения переменной x и ее отрицания `x симметричны относительно медианы M, то есть x<sub>i</sub> £ x<sub>j</sub> тогда и только тогда, когда `x_j £ `x_i. Таким образом, общее число строк таблицы выбора функции n аргументов равно L = 2ⁿn!. Для каждого упорядочения функция может принимать независимо одно из 2n возможных значений. Поэтому существует N=(2n)^L различных таблиц выбора, задающих некоторую функцию n аргументов.

В работах [1] получены оценки различных ФНЛ одного, двух и трех аргументов. В таблице 2 эти значения сопоставлены с количеством различных таблиц выбора для соответствующего числа аргументов. Так как в [1] при подсчете учитывались также функции, принимающие значения a и b, количество таблиц выбора вычислялось по формуле N = (2n+2)^L. Анализ таблицы 2 позволяет сделать вывод, что лишь немногие из функций, задаваемых таблицами выбора, являются функциями непрерывной логики.

Во избежание использования в дальнейшем изложении нескольких уровней индексов введем следующий способ представления таблиц выбора. Пусть x = (x₁, x₂ ... x_n) - набор аргументов, а переменные x с индексами i в пределах от n+1 до 2n обозначают отрицание аргументов: x_i = `x_i-n для "i = n+1,m, где m = 2n. Таблицу выбора T будем рассматривать как множество строк.

---

T = (t)   |T| = L
t = (p, a) - строка таблицы
p = (i1, i2 ... im) - последовательность индексов
                     аргументов в описываемом варианте упорядочения
a - индекс аргумента, являющегося значением функции

---

Таким образом, f(x) = x_a при xÎD_t, где D_t Í Cⁿ, задается неравенством x_i1£ x_i2 £ ... £ x_im.

3.2 Перекрывающиеся строки

Будем говорить, что строка t таблицы выбора T перекрывает строку t', если для подмножества индексов F_t и F^*_t' имеет место включение F_tÍF^*_t', где

---

t  = ((i1 ... ik-1, a, ik+1 ... im), a)
t' = ((j1 ... jr-1, b, jr+1 ... jm), b)

   Ft  = {a, ik+1 ... im} (xa £ xi - для всех i Î Ft)
   F*t' = Ft'\{b} = {jr+1 ... jm}     (2)

---

Строки t и t' таблицы T будем называть перекрывающимися, если одна из них перекрывает другую.

Теорема 1

Таблица выбора функции непрерывной логики не содержит перекрывающихся строк.

Доказательство

Выберем произвольно функцию непрерывной логики f. Не ограничивая общности можно считать, что она записана в нормальной дизъюнктивной форме:

---

f(x) = Úq Kq(x)     (3)

---

где K_q= Ù_iÎIqx_i, - элементарные конъюнкты, и I_q - множество индексов i переменных x_i, входящих в q-тый конъюнкт.

Построим таблицу выбора T для функции f. Предположим, что в таблице T некоторая строка t перекрывает строку t', то есть F_t - подмножество F^*_t' в соответствии с (2). Пусть наборы аргументов x Î D_t и x' Î D_t' удовлетворяет строкам t и t' таблицы Т соответственно в смысле строгого выполнения неравенств.

Так как f(x) = x_a, то по определению дизъюнкции как максимума значений аргументов, по крайней мере один из конъюнктов ДНФ (3) на наборе x примет значение x_a. Пусть это будет конъюнкт K_u:

---

Ku(x) = xa

---

Тогда, по определению конъюнкции как минимума значения аргумента, I_u Í F_t и далее из F_t Í F^*_t' заключаем:

---

Iu Í F*t'     (4)

---

Рассмотрим значение конъюнкта K_u на наборе x'. Так как f(x) = x_b, то K_u(x) £ x_b, значит, существует такое jÎI_u, что x_j £ x_a, следовательно, jÏF_t'. Таким образом, имеем

---

Iu Ë F*t'     (5)

---

Сопоставляя (4) и (5), приходим к противоречию, что доказывает невозможность присутствия в таблице выбора, задающей ФНЛ, перекрывающихся строк.

4. Построение функции непрерывной логики по таблице выбора

4.1 Конституэнты максимума

Конституэнтой максимума строки t таблицы T будем называть конъюнкт:

---

ft = Ùi Î Ft xi,   (xa £ xi | " i Î Ft     (6)

---

Нетрудно видеть, что конституэнта максимума является фундаментальной фразой. Действительно, вследствие того, что любой аргумент и его отрицание всегда симметричны относительно медианы, при |F_t| < n, f_t непротиворечива. Если |F_t| > n, то f_t для каждого " i = 1...n содержит букву с индексом i. По определению любая такая фраза называется фундаментальной.

Из определения операции конъюнкции и способа построения (6) вытекает следующее свойство конституэнт: для всякого набора аргументов x удовлетворяющего строке t, таблицы Т, xÎD_t

---

ft(x) = xa      (7)

---

4.2 Лемма 1

Для двух не перекрывающихся строк t и t' таблицы выбора T и для любого набора аргументов x^', удовлетворяющего t', выполняется неравенство:

---

ft(x') £ ft'(x')     (8)

---

Доказательство

Предположим противное. Пусть f_t(x^') > f_t'(x^'). По свойству конституэнт максимума (7) имеем f_t'(x^') = x_b. Тогда x_b £ Ù_{i Î Ft} x_i или по определению конъюнкции как минимума значений аргументов

---

xb £ xi       " j Î Ft      (9)

---

Множество F_t' в силу определения (2) составляют такие индексы j аргументов, что

---

xb £ xj     " j Î F*t'     (10)

---

Тогда, сопоставляя (9) и (10), имеем F_t Í F^*_t'. Таким образом, строка t таблицы T перекрывает строку t'. Полученное противоречие и завершает доказательство леммы.

4.3 Теорема 2

Произвольная таблица выбора, не содержащая перекрывающихся строк, задает функцию непрерывной логики, равную дизъюнкции конституэнт максимума строк таблицы.

Доказательство

В силу определения конституэнты максимума для любой таблицы выбора можно построить функцию

---

f(x) = Út ÎT ft     (11)

---

Так как таблица не содержит перекрывающихся строк, то конституэнты f_t обладают свойствами (7) и (8).

Рассмотрим значение функции f на произвольном наборе аргументов x^'ÎCⁿ. Любой набор аргументов всегда удовлетворяет одной из строк таблицы T. Пусть набор x^' удовлетворяет строке t'. Тогда f_t'(x^') = x_b. Поэтому в силу определения дизъюнкции как максимума значений аргументов:

---

f(x') = ÚtÎT ft = xb

---

Следовательно, значение функции f заданной соотношением (11) совпадает со значением определяемым таблицей выбора T. В силу произвольности выбора аргументов x^' значения совпадают для "x^'Î Сⁿ. Теорема доказана.

Аналогичным образом можно ввести конституэнты минимума строк таблицы T:

---

Yt = ÚiÎYt xi, где Yt = {i1 ... ik-1, a}     (12)

---

Тогда теорему 2 можно представить в двойственной форме, определяющей ФНЛ как конъюнкцию конституэнт минимума строк таблицы T.

---

f(x) = ÙtÎT Yt     (13)

---

Форма (13) является КСНФ ФНЛ f.

4.4 Критерий непрерывности функции, заданной таблицей выбора

Теорема 3

Таблица выбора задает функцию непрерывной логики тогда и только тогда, когда не содержит перекрывающихся строк. Теорема является непосредственным следствием теорем 1 и 2.

По теореме 2 алгоритм синтеза ФНЛ по таблице выбора состоит в последовательном выполнении следующих шагов:

---

1. построить конституэнты максимума (минимума) строк таблицы
2. построить ДНФ функции как дизъюнкцию (конъюнкцию)
   конституэнт максимума (минимума)
3. сократить запись, используя законы поглощения

---

Полученная формула сразу является канонической записью ФНЛ, заданной таблицей выбора. Средний размер конституэнты равен n = m/2. Поэтому общая сложность алгоритма имеет порядок o(nL). Непосредственный поиск перекрывающихся строк в таблице выбора требует выполнения проверок для каждой из пар различных строк.

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

Этот факт можно использовать для практического синтеза функций. Не проверяя предварительно таблицу выбора T на наличие перекрывающихся строк, выполним синтез ДНФ функции f непрерывной логики. Затем построим таблицу выбора T' функции f. Если T и T' совпадут, то исходная таблица задает ФНЛ. В противном случае функция, задаваемая таблицей Т, не является функцией непрерывной логики. Для аналитического представления таких функций необходимо использовать гибридную логику либо предикатную алгебру выбора (Волгин Л.И. Комплементарная алгебра и предикатная алгебра выбора. - Ульяновск: УлГТУ, 1996. - 67с.).

Описанный метод действителен и для восстановления аналитической записи не везде определенных ФНЛ. В таком случае нет необходимости доопределять недостающие значения функции, достаточно воспользоваться им для заполненной части таблицы.

По теореме 2 на наборах, соответствующих заданным строкам таблицы, функция будет принимать указанные в них значения, а на остальных наборах - значения, обусловленные свойством непрерывности функции.

5. Примеры синтеза функций

Пусть функция f₁ двух аргументов задана таблицей Т₁:

---

          T1                              Dt                  f1

t1 = ((1, 2, 4, 3), 2)        x1  £  x2  £ M £ `x2 £ `x1       x2
t2 = ((1, 4, 2, 3), 2)        x1  £ `x2  £ M £  x2 £ `x1       x2
t3 = ((3, 2, 4, 1), 4)        x1  £  x2  £ M £ `x2 £  x1      `x2
t4 = ((3, 4, 2, 1), 4)        x1  £ `x2  £ M £  x2 £  x1      `x2
t5 = ((2, 1, 3, 4), 1)        x2  £  x1  £ M £ `x1 £ `x2       x1
t6 = ((2, 3, 1, 4), 1)        x2  £ `x1  £ M £  x1 £ `x2       x1
t7 = ((4, 1, 3, 2), 3)       `x2  £  x1  £ M £ `x1 £  x2      `x1
t8 = ((4, 3, 1, 2), 3)       `x2  £ `x1  £ M £  x1 £  x2      `x1

---

Выполним синтез указанной функции. Конституенты максимума функции f₁ имеют вид:

---

f1 =  x2`x2x1
f2 =  x2`x1
f3 = `x2x1
f4 = `x2x2x1
f5 =  x1`x1`x2
f6 =  x1`x2
f7 = `x1x2
f8 = `x1x1x2

---

В силу коммутативности операции конъюнкции

---

f7= f2
f8=f3
f3 поглощает f5 и f5
f2 поглощает f1 и f8

---

Таким образом, получим ДНФ:

---

F1 = f2Úf3 = x1`x2 Ú`x1x2

---

Таблица функции, заданной формулой F₁, совпадает с таблицей T₁ функции f₁, следовательно, f₁ является функцией непрерывной логики, а F₁ - ее дизъюнктивная нормальная форма. Отсутствие перекрывающихся строк в таблице T₁ можно установить также путем непосредственной проверки.

Рассмотрим функцию f₂, заданную таблицей T₂:

---

          T2                             Dt                f2      F2

t1 = ((1, 2, 4, 3), 2)      x1  £  x2  £ M £ `x2 £`x1       x2     `x1
t2 = ((1, 4, 2, 3), 3)      x1  £ `x2  £ M £  x2 £`x1      `x1     `x1
t3 = ((3, 2, 4, 1), 2)      x1  £  x2  £ M £ `x2 £ x1       x2      x2
t4 = ((3, 4, 2, 1), 4)      x1  £ `x2  £ M £  x2 £ x1      `x2     `x2
t5 = ((2, 1, 3, 4), 1)      x2  £  x1  £ M £ `x1 £`x2       x1     `x1
t6 = ((2, 3, 1, 4), 3)      x2  £ `x1  £ M £  x1 £`x2      `x1     `x1
t7 = ((4, 1, 3, 2), 4)     `x2  £  x1  £ M £ `x1 £ x2      `x2     `x1
t8 = ((4, 3, 1, 2), 3)     `x2  £ `x1  £ M £  x1 £ x2      `x1     `x1

---

Построим конституенты максимума функции f₂:

---

f1 =  x2`x2x1
f2 = `x1
f3 =  x2`x2x1
f4 = `x2x2x1
f5 =  x1`x1`x2
f6 = `x1x1`x2
f7 = `x2x1`x1x2
f8 = `x1x1x2

---

Конституэнты:

---

f3=f4
f5=f6
f2 поглощает f1, f5, f6, f7

---

Построим ДНФ:

---

F2 = f2Úf3 =`x1Ú x1x2`x2

---

Таблица функции F₂ не совпадает с таблицей f₂ в областях 1, 5, 7. Действительно, строка 2 таблицы T₂ перекрывает строки 1, 5, 7, а строка 8 перекрывает строку 7:

---

F2 Í F*1
F2 Í F*5
F2 Í F*7
F2 Í F*7

---

Таким образом, f₂ не является функцией непрерывной логики.

6. Минимизация функций непрерывной логики

Минимальной ДНФ ФНЛ (МДНФ ФНЛ) называется ДНФ, содержащая наименьшее число слагаемых, если никакое другое представление с тем же числом слагаемых не содержит меньшего количества букв.

6.1 Простые импликанты

Фраза p называется импликантой ФНЛ F, если выполняется неравенство p £ F. Всякая импликанта q - функции F, включена в некоторую максимальную имликанту q*, удовлетворяющую условиям:

---

q £ q* £ F     (14)

---

Если для некоторой g выполняется условие, что

---

q* £ g £ F     (15)

---

то q*= g. Всякую максимальную импликанту функции называют простой или первичной. Всякая ФНЛ равна сумме всех своих простых импликант.

6.2 Итеративный консенсус

Для минимизации ФНЛ обычно используют метод итеративного консенсуса, предложенный Кенделом. Пусть есть две фразы: f₁ = x_iA и f₂ =`x<sub>i</sub>B, где AB - произведения оставшихся букв. Консенсусом f<sub>1</sub> W f<sub>2</sub> - называется фраза AB, если AB - противоречиво, или x<sub>i</sub>`x_iAB, если AB непротиворечиво. Если f₁ и f₂ не представимы в указанном виде, то их консенсус равен нулю.

Алгоритм итеративного консенсуса

Вход: несократимая ДНФ
Выход: сумма всех простых импликант

---

1. для всех пар p_i и p_j образуется консенсус p_i и p_j

2. к ДНФ присоединяются в качестве слагаемых фразы, полученные на шаге 1

3. на шаге 2 каждая фраза сравнивается с любой другой, и удаляются меньшие фразы

---

Шаги 1, 2, 3 повторяются до тех пор, пока все консенсусы не будут равны нулю, либо будут включены в имеющиеся слагаемые.

6.3 Теорема о минимизации

Пусть f - произвольная функция непрерывной логики.

---

F = ÚiÎIF pi - ДСНФ функции f,
              где IF - множество индексов фундаментальных фраз;
f = ÚjÎIf qj - МДНФ функции f,
              где If - множество индексов простых импликант,
T - таблица выбора, построенная по f

---

Будем говорить, что строка t называется существенной для фундаментальной фразы p*, если "p_k, kÎI_F, xÎD_t выполняется

---

pk(x) £ p*(x) = f(x) = xa     (16)

---

Множество строк, существенных для одной фундаментальной фразы p_i, будем обозначать T_i. Множество T'= T \ T_i, будем называть несущественными для p_i строками. Нетрудно видеть, что {T_i} - покрытие T: T = È_iÎIF T_i и пересечение T_i Ç T_j при i № j не обязательно равно Æ.

Пусть A_i - множество индексов a аргументов x_a, значения которых принимает функция на множестве T_i существенных для p_i строк.

Теорема 4 (о минимизации)

Каждая фундаментальная фраза p_i ДСНФ ФНЛ, включает простую импликанту q_i такую, что

---

qi = ÙaÎAi xa     (17)
f = ÚiÎIF qi      (18)

---

- ДНФ функции f, состоящая из всех ее простых импликант.

Доказательство

Для того, чтобы f являлась записью f необходимо показать, что для любого q_i условия (7) и (8) на T выполняются тогда и только тогда, когда им удовлетворяет p_i. Условие (7) истинно для q_i по построению q_i.

Если p непротиворечива, то на множестве T_i существенных для p_i строк функция f принимает значения всех входящих в p_i аргументов и отрицаний аргументов, другими словами q_i = p_i.

Действительно, вследствие (8) T_i принадлежат и те строки, на которых все входящие в p_i аргументы больше всех не входящих, вне зависимости от порядка расположения в строке первых и вторых между собой. На таких строках функция принимает значения минимального из входящих в p_i аргумента, которым при всех перестановках оказывается любая входящая в p_i буква.

В силу тех же рассуждений условие (8) выполняется, если p_i противоречива и q_i = p_i. Рассмотрим ситуацию, когда p_i противоречива и q_i > p_i. Тогда q_i содержит все пары противоречивых аргументов, входящих в p_i, так как T_i составляют и строки, на которых все непротиворечивые аргументы больше всех противоречивых:

---

t = ((l1...lk,m1...ms, M ,ms+1...m2l,r1...rk) m1), где
l1...lk - индексы аргументов, не входящих в pi
r1...rk - индексы непротиворечивых аргументов, принадлежащих pi
m1...m2s - индексы противоречивых аргументов, принадлежащих pi

---

При всех перестановках противоречивых аргументов, любой может оказаться на месте минимального (с индексом m₁), то есть если p_i противоречива, то все ее противоречивые аргументы с их отрицаниями присутствуют в q_i.

Теперь допустим, что существует строка t, на которой условие (8) выполняется для p_i и не выполняется для q_i. Такая строка имеет вид

---

t = ((l1...l*...lk-1,m1...ms, M ,ms+1...m2s,r1...rk) m1)
где l* - индекс аргумента, который есть в pi, но не входит в qi

---

Тогда за конечное число перестановок пар соседних аргументов (увеличивая x_l* и перемещая его индекс вправо) на строке t' имеем

---

t' = ((l1...lk-1,m1,l*...ms, M ,ms+1...m2s,r1...rk) a)

---

если f(x)=x_a=x_l* (a=l*), то x_l* Î q_i по построению q_i, и для строки t условию (8) q_i удовлетворяет, а если f(x)=x_a=x_m1 (a = m₁), то для t и t' (8) не выполняется для p_i и Т не задает ФНЛ f.

Следовательно, (7) и (8) имеют место для q_i тогда и только тогда, когда они выполняются для p_i. По теореме 2 дизъюнкция фраз, для которых на каждой строке таблицы T выполняются отношения (7) и (8) есть запись ФНЛ заданной T. Таким образом, f является записью ФНЛ f тогда и только тогда, когда F запись f. По условию теоремы F - ДСНФ f.

Покажем, что q_i есть простая импликанта. Если это не так и существует импликанта q' > q_i, то в записи q' меньшее количество букв. Пусть x_l* аргумент, которого нет во фразе q' и есть в q_i. Тогда на наборах, удовлетворяющих тем строкам, где p_i максимальна и f принимает значение x_l*, l*ÎA_i, а q' > q_i = f, следовательно, q' не является импликантой. Теорема доказана.

Этот результат означает, что, построив по таблице ДСНФ ФНЛ и в процессе построения собрав для каждой фундаментальной фразы указанную статистику, получаем ДНФ, по-разному сокращая которую, можем иметь множество всех МДНФ f.

7. Примеры минимизации функций по таблице

Пусть задана функция f:

---

           T                            Dt                 f

t1 = ((1, 2, 4, 3) 1)       x1  £  x2  £ M £ `x2 £`x1       x1
t2 = ((1, 4, 2, 3) 1)       x1  £ `x2  £ M £  x2 £`x1       x1
t3 = ((4, 1, 3, 2) 1)      `x2  £  x1  £ M £ `x1 £ x2       x1
t4 = ((4, 3, 1, 2) 3)      `x2  £ `x1  £ M £  x1 £ x2      `x1
t5 = ((3, 4, 2, 1) 4)      `x1  £ `x2  £ M £  x2 £ x1      `x2
t6 = ((3, 2, 4, 1) 2)      `x1  £  x2  £ M £ `x2 £ x1       x2
t7 = ((2, 3, 1, 4) 3)       x2  £ `x1  £ M £  x1 £`x2      `x1
t8 = ((2, 1, 3, 4) 1)       x2  £  x1  £ M £ `x1 £`x2       x1

---

Построим ДСНФ F функции f:

---

F = x1x2`x2`x1 Ú x1`x2x2`x1 Ú x1`x1x2 Ú `x1x1x2 Ú `x2x2x1 Ú x2`x2x1Ú  `x1x1`x2 Úx1`x1`x2

---

Сократим F:

---

F = x1`x1x2 Ú`x2x2x1 Ú`x1x1`x2 = f3Ú f5Ú f7

---

Построим множество T_i существенных для f_i, i = {3, 5, 7} строк

---

T3 = { t1, t2, t3, t4 }
T5 = { t1, t2, t5, t6 }
T7 = { t1, t2, t7, t8 }

---

И множество A_i индексов a аргументов x_a, значение которых принимает f на T_i

---

A3 = { 1, 3 }
A5 = { 1, 4, 2 }
A7 = { 1, 3 }

---

Имеем

---

f = x1`x1 Ú x1`x2x2Ú x1`x1 = x1`x1 Ú x1`x2x2

---

Отметим, что на вход алгоритма минимизации, основанного на теореме 4, подается ДСНФ ФНЛ F - несократимая сумма фундаментальных фраз. На выходе имеем формулу f, состоящую из всех простых импликант функции f. Cокращая f, получаем МДНФ ФНЛ f.

8. Запись функций, не являющихся ФНЛ, в предикатной алгебре выбора

8.1 Операции предикатной алгебры выбора

Предикатная алгебра выбора (ПАВ) отличается от НЛ тем, что в ней на множестве-носителе С = [A,B] выводится две обобщенные (управляемые) логические операции - предикатные дизъюнкция и конъюнкция:

---

Úp ( x1, x2 ) = x1*p + x2*`p
Ùp ( x1, x2 ) = x1*`p + x2*p       x1, x2 Î С, p Î {0, 1}

---

где "*" и "+" - обычные умножение и сложение,

---

p = p ( y1 ... ym ) - m = местный двузначный предикат
p = 1 - p = булевое отрицание p

---

Предикат играет роль управляющего параметра, значением которого определяется выбор одной из двух альтернативных переменных х₁, х₂, то есть выбор конкретной функции этих переменных. Для записи кусочно-непрерывных функций необходимо:

---

1. выделить множество Pi наборов
2. на которых функция описывается единой формулой fi
3. и определить предикаты pi, i=1...k

---

Тогда дизъюнктивная запись будет иметь вид:

---

F = Úp1(x) ( f1(x), Úp2(x) (f2(x), ... Úpk-1(x) ( fk-1(x), fk(x))...))     (19)

---

Известно, что P_i, f_i и p_i можно сформировать не единственным образом.

8.2 Алгоритм 1 записи кусочно-непрерывной функции, заданной таблицей выбора

Наиболее просто

---

1. в качестве fi выбирать i-ый аргумент xi
2. задать pi = 1 на всех наборах x Î Pi, где Pi= {x | f(x) = xi}

---

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

8.3 Алгоритм 2

Вход: таблица T кусочно-непрерывной функции f.
Выход: дизъюнктивная запись F в ПАВ вида (19) функции f, заданной таблицей T.

---

1. Пусть i = 1; T₁ = T

2. По таблице T_i синтезируется формула f_i, как дизъюнкция конституэнт максимума

3. По f_i вычисляется следующая таблица T_i+1

4. Наборы, на которых значения функции в обеих таблицах совпадают, составляют P_i; строки, соответствующие наборам xÎP_i удаляются из таблицы T_i+1 и в дальнейшем для синтеза функций не участвуют

5. p_i = 1 на наборах x Î P_i, и p_i = 0 - на всех остальных

6. i = i + 1

7. Если T_i № Æ переход на шаг 2, иначе - конец

---

Записанные таким образом функции с небольшим количеством разрывов описываются меньшим числом формул f_i. Нетрудно заметить, что для функций с количеством аргументов n > 2, k < 2n корректность предложенного алгоритма следует из корректности метода построения аналитической записи ФНЛ и определения базовых операций ПАВ.

9. Примеры синтеза кусочно-непрерывных функций

Пусть задана функция f следующей таблицей:

---

    Область определения                          Алгоритм 1                     Алгоритм 2

            Dt                  f         f1  p1  f2    p2  f3  p3  f4             g1  q1  g2

 x1  £  x2  £ M £ `x2 £`x1       x2            0   x2   1        0                 x2  1
 x1  £ `x2  £ M £  x2 £`x1      `x2            0        0        0 `x2             x2  0 `x2
`x2  £  x1  £ M £ `x1 £ x2       x1         x1 1        0        0                 x2  0  x1
`x2  £ `x1  £ M £  x1 £ x2       x2            0   x2   1        0                 x2  1
`x1  £ `x2  £ M £  x2 £ x1       x1         x1 1        0        0                 x1  1
`x1  £  x2  £ M £ `x2 £ x1      `x1            0        0  `x1   1                 x1  0 `x1
 x2  £ `x1  £ M £  x1 £`x2       x1         x1 1        0        0                 x1  1
 x2  £  x1  £ M £ `x1 £`x2       x1         x1 1        0        0                 x1  1

---

Первый алгоритм записи F функции f в ПАВ дает результат

---

F = Úp1(x) (x1, Úp2(x) (x2,  Úp3(x) (`x1, `x2)))

---

Рассмотрим построение функции F с помощью второго алгоритма. По таблице синтезируем функцию:

---

g1 = x2`x2`x1  Ú `x2 x2`x1 Ú  x1`x1x2  Ú  x2  Ú  x1  Ú `x1x2`x2x1  Ú  x1`x2 Ú  x1`x1`x2

---

Сокращая, получаем

---

g1 = x2 Ú x1

---

На наборах, соответствующих строкам 2, 3 и 6 значения g₁№ F, поэтому на них предикат q₁ = 0. Для описания f на этой части таблицы строим функцию g₂

---

g2 = `x2x2`x1 Ú  x1`x1x2 Ú`x1x2`x2x1

---

Сокращаем

---

g2 = `x2x2`x1 Ú  x1`x1x2

---

В указанной области g₂ = f. Запись G функции f:

---

G = Úq1(x)  (g1, g2) =  Úq1(x)  (x2 Ú x1,`x2x2`x1 Ú  x1`x1x2)

---

Заключение

В настоящей работе получен критерий, позволяющий определить, задает ли таблица выбора некоторую функцию непрерывной логики, и построен простой алгоритм, выполняющий синтез аналитической записи функции по таблице выбора. Доказана теорема о минимизации, выявляющая связь ДСНФ ФНЛ со всеми ее простыми импликантами, а следовательно, с МДНФ ФНЛ. Для функций, не являющихся ФНЛ, предложены два алгоритма их записи в предикатной алгебре выбора. Разработаны наиболее общие методы синтеза аналитической записи для всех функций, принимающих значения своих аргументов или их отрицаний.

Работа выполнена автором самостоятельно под руководством доктора технических наук, профессора ДонГТУ Слепцова А.И., была направлена на рецензию в Институт прикладной математики г.Донецка и имеет положительный отзыв кандидата физико-математических наук Грунского И.С.

Список литературы

1. Волгин Л.И., Левин В.И. Непрерывная логика. Теория и применения. - Таллинн: Б.и., 1990.

2. Волгин Л.И. Комплиментарная алгебра и предикатная алгебра выбора. - Ульяновск: УлГТУ, 1996. - 67с.

Владимир Сарбей, 27 мая 2003 года