Математика / 2. Перспективы информационных систем

К.ф.-м.н. Лютикова Лариса Адольфовна

НИИ ПМА КБНЦ РАН, Россия, г. Нальчик

Некоторые свойства операций логического

дифференцирования и интегрирования дискретных

k – значных функций

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

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

Определение 1. Производная первого порядка от булевой функции f(x₁,…,x_n) по переменной x_i есть сумма по модулю 2 соответствующих остаточных функций:

(1)

Определение 2 .Весом производной от булевой функции называется число конституент («1») этой производной.

Утверждение 1 . Чем больше вес производной, тем больше функция f(x_1,…,x_n) зависит от переменной x_i.

Определение 3. Смешанной производной k-го порядка от булевой функции f(x₁,…,x_n) называется выражение вид:

;

При этом порядок фиксированной переменной не имеет значения. Производная k-го порядка определяет условия, при которых эта функция изменяет свое значение при одновременном изменении значений x1,…,xk.
Совершенные нормальные дизъюнктивные формы хотя и дают однозначные представления функции, но являются очень громоздкими. Реализация СДНФ программно или схемотехнически является избыточной, что ведет к увеличению программного кода, поэтому существуют методы упрощения логической записи – минимизации.
Теорема 1. Пусть задана булева функция , тогда 
.

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

Пусть - , , значение переменных на j- том наборе, , дискретная производная по переменной может быть найдена из следующего выражения:

,

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

Функцию, обладающую свойством: , где l - конечное число, назовем конечно дифференцируемой.

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

Теорема 2. Пусть , пусть , где l- конечное число, тогда функция представима в виде псевдополинома.

В системах k=6,10 и выше, если , где p -простое число существуют бесконечно дифференцируемые функции.

Если для дискретной функции f вычислена производная, то целесообразно рассмотреть одну из возможных конструкций неопределенного интеграла, отмечая особо, что природа логических функций обусловливает необходимость осторожного подхода к вопросу формирования конструкции интеграла дискретной функции. При исследовании учитывались результаты практически единственной существующей в этой области работы [5], в которой интеграл булевой функции f от n переменных введен следующим образом: .

Введем следующее понятие интеграла:

Определение 4. пусть производная функции f по переменной x_i , тогда существует функция , называемая булевым интегралом функции g, такая, что: , где h является произвольной булевой функцией переменных x₁,…x_i-1,x_i+1,..,x_n.

Свойство1. Количество L первообразных функции g= , где  - булева функция, равно L=2n.
Теорема 3. Любая булева функция может быть получена в результате n-кратного логического интегрирования константы{0}.
Доказательство:
 
Интегрируя каждую из полученных 4 функций по переменной x2 , получим все 16 булевых функций от двух переменных. Продолжая интегрирование по следующей переменной получим 256 функций Р2(3)=256 и т. д.

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

Утверждение 1. Дискретная первообразная функции ,

по заданной переменной имеет следующее представление:

,

где - значение переменных на j - том наборе, .

Свойство 2. Пусть функция , , и пусть не существует первообразной для заданной функции на наборе , тогда существует первообразная для функции , где , ,…,,

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

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

Если не существует первообразной ни при одном значении переменной тогда переход на n+1 уровень называется безусловным.

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

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

Если переход на n+1 уровень безусловеным - это значит параметров для анализа данной информации недостаточно.

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

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

Свойство 4. Пусть , тогда

образует матрицу, салфетку Серпинского при n=2, и многомерный ковер Серпинского при n=k.

Литература

1. Reddy, S.M. Easily Testable Realizations for Logic Functions // IEEE Trans. Computers. Vol. 21, no. 11, Nov., 1982.

2. Кузьмицкий Д.В., Шмерко В.П., Янушкевич С.И. Булево дифференциальное исчисление в вычислительной технике. Матричный аппарат булева дифференциального исчисления. Минск, 2007.

3. Янушкевич С., Бохманн Д., Станкович Р., Тошич Ж., Шмерко В. Логическое дифференциальное исчисление: достижения, тенденции и приложения. // Автоматика и телемеханика. - 2004. - № 6. - С. 155-170.5.

4. Лютикова Л.А. Исследование систем булевых функций логическими интегро-диффернциальными методами // Материали за 6 Международна научна практична конференция "Найновите постижения на европейской наука-2011". София. Т. 37. С. 31-38.

5. Пантелеев В.И. Полиномиальное разложение K-значных функций по операторам дифференцирования и нормализации // Известия высших учеб-ных заведений: Математика. 1998. №1. С. 82-103.