Проектирование программного средства

2.1 Метод частных полиномиальных нормальных форм

В [5] предложен алгоритм полиномиального преобразования БФ на основе метода частных полиномиальных нормальных форм (ЧПНФ). Метод заключается в формировании ПНФ БФ путём последовательного преобразования каждого минтерма СДНФ (совершенная дизъюнктивная нормальная форма) функции в ЧПНФ. Рассмотрим метод ЧПНФ подробнее.

Пусть логическая функция f(а, b, с) задана таблицей истинности, представленной в таблице 2.1, индексом i обозначен номер набора значений логических переменных.

Таблица 2.1 - Истинности логической функций f(а,b,с)

i	а	b	с	f

Преобразуем каждый минтерм СДНФ функции f(а, в, с) в частные ПНФ – В_j, где , если известно, что и , для .

,

,

,

,

,

.

Сведем полученные данные в таблицу 2.2.

Таблица 2.2 – Частные полиномиальные нормальные формы B_i

Ki	ЧПНФ
	с		с	а	ас	а	а с	Bi
									B0
									B1
									B2
									B3
									B4
									B5
									B6
									B7

В таблице 2.2 в первом столбце перечислены все возможные минтермы функции f(а, b, с) – K_i, а в первой строке указаны все возможные члены ПНФ той же функции. В остальных строках метками «1» отмечены те члены ПНФ, которые входят в частные ПНФ в соответствии с вычисленными выше ЧПНФ. Жирным шрифтом выделены те B_j, которые соответствуют единичным значениям функции f(а, b, с). Просуммируем по модулю 2 в символьном виде те ЧПНФ, которые соответствуют выделенным в таблице 2.2 минтермам логической функции. В результате, после раскрытия скобок и приведения подобных членов, получим

Тождественный результат с использованием данных таблицы 2.2 может быть получен путём суммирования по модулю 2 двоичных векторов В_j, соответствующих выделенным минтермам, что иллюстрируется в таблице 2.3.

Таблица 2.3 - Частные полиномиальные нормальные формы B_j

Ki	ЧПНФ
	с	b	bс	а	ас	аb	аbс	Bi
									B0
									B1
									B2
									B3
									B4
									B5
									B6
									B7
									B

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

Анализ данных таблицы 2.3 наглядно демонстрирует следующую закономерность: разряды двоичных векторов Bj принимают единичные значения только в том случае, если единичные значения переменных в номерах строк полностью входят в двоичные номера столбцов таблицы. Исключение составляет только вектор В₀, все элементы которого равны 1.

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

Алгоритм формирования ПНФ с использованием ЧПНФ представлен на рисунке 2.1.

Рисунок 2.1 – Алгоритм формирования ПНФ с использованием ЧПНФ

2.2 Модульная структура ПС

Исходя из цели дипломного проектирования и рассмотренного выше алгоритма полиномиального преобразования БФ, сформулированы основные требования к разрабатываемому исследовательскому комплексу минимизации полинома Жегалкина частично определенных булевых функций. Исследовательский комплекс должен обеспечивать пользователю следующие возможности:

- ввод количества аргументов булевой функции;

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

- заполнение значений БФ таблице истинности;

- ввод вектора значений БФ в автоматическом и ручном режиме;

- доопределение вектора БФ;

- вычисление минимального полинома Жегалкина;

- подсчет количества минтермов.

Учитывая вышесказанное, была предложена функциональная схема разрабатываемого исследовательского комплекса минимизации полинома Жегалкина частично определенных БФ, которая представлена на рисунке 2.2.

Блок входных данных

Блок вычисления

Блок формирования полинома Жегалкина методом ЧПНФ

Управляющий блок

Блок заполнения таблицы истинности

Блок поиска количества минтермов

Блок доопределения вектора и построения минимального полинома

Блок Справка

Рисунок 2.2 – Структура функциональных блоков

программного средства

«Управляющий блок» программного обеспечения предназначен для взаимодействия пользователя с программой и обеспечения взаимосвязи между остальными блоками.

Блок «Справка» предназначен для вывода информации о возможностях программы, ее технических и программных требованиях, а также о функциональных элементах и их расположении.

«Блок ввод данных» предназначен для ввода основных параметров вычисления - числа аргументов булевой функции и значений вектора F(). Функция F() в программном продукте, может быть как полностью определена, так и частично. Если функция определена частично, то программа дополняет вектор БФ произвольно.

«Блок заполнения таблицы истинности»: при выборе числа аргументов БФ, автоматически рассчитывается размерность таблицы истинности и заполняются ее значения.

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

«Блок вычисления» предназначен для систематизации введенной информации и выполнения расчетов (записи функции в виде полинома Жегалкина с вычисленными коэффициентами). Реализуется алгоритм минимизации полинома Жегалкина частично определенных булевых функций

Он включает в себя следующие блоки:

1 - «Блок поиска количества конъюнкций»;

2 - «Блок формирования полинома Жегалкина методом ЧПНФ».

Блочная структура ПС состоит из 8 модулей. В разделе 2.3 спроектирован алгоритм использования частных полиномиальных нормальных форм БФ.

2.3 Алгоритм работы программного средства

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

Суть алгоритма заключается в следующем, пользователь вводит n – число аргументов булевой функции. По числу n определяем, как будет производиться ввод вектора значений БФ: вручную, если n<5 или автоматически, если 5<n<8. Далее доопределяем БФ первый раз и реализуем алгоритм формирования полинома Жегалкина методом ЧПНФ. Выводим на экран полином, подсчитываем количество конъюнкций в сформированном полиноме Жегалкина. Затем снова выполняется процесс доопределения БФ и реализуется алгоритм формирования полинома Жегалкина методом ЧПНФ.

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

Процесс доопределения происходит 2^k раз, где k – число неопределенных наборов.

Схема алгоритма разрабатываемого программного модуля представлена на рисунке 2.3.

Рисунок 2.3 – Cхема алгоритма

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

- получить таблицу истинности для установленного пользователем количества переменных;

- заполнить значения функции для каждого из наборов таблицы истинности;

- последовательно вычислить неизвестные коэффициенты;

- записать функцию в виде полинома Жегалкина с вычисленными коэффициентами;

- построить минимальный полином.

2.4 Описание синтаксиса ПС

Опишем данные, которые будут использованы в программном обеспечении. Информация будет делиться на категории, для каждой категории будут определены её компоненты. Например такие, как основы языка С#:

- типы данных;

- одномерные массивы;

- цикл с предусловием while;

- цикл с параметром for;

- оператор выбора switch.

Для каждого компонента категории будут представлены характеристики: описание, синтаксис, листинг.

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

Каждый из функциональных блоков представленных в пункте 2.2, в свою очередь, состоит из классов. Основной класс в программе ZhegalkinMainForm описан ниже. Находим множество двоичных наборов функции, на которых она принимает значение 1. После составления СДНФ в формуле каждый знак дизъюнкции меняем на знак суммы Жегалкина. Упрощаем, полученное выражение, используя тождества. В полученной формуле каждый элемент с отрицанием заменяем на . Раскрываем скобки в полученной формуле, содержащей только
. Приводим подобные члены.

public partial class ZhegalkinMainForm : Form

{

private Random Rand = new Random(Environment.TickCount);

private ZhegalkinPolinomBuilder builder = new ZhegalkinPolinomBuilder();

public ZhegalkinMainForm()

{

InitializeComponent();

this.FillTable((int)nudN.Value);

}

private void nudN_ValueChanged(object sender, System.EventArgs e)

{

this.FillTable((int)nudN.Value);

}

Добавление строк в таблице истинности происходит при увеличении числа аргументов функции.

private void FillTable(int n)

{

dgvTruthTable.Rows.Clear();

var rowsCount = (int)Math.Pow(2, n);

for (int i = 0; i < rowsCount; i++)

{

dgvTruthTable.Rows.Add();

}

// Заполнение колонок таблицы истинности.

for (int i = 0; i < Constants.MaxN; i++)

{

dgvTruthTable.Columns[i].ReadOnly = true;

if (i < n)

{

dgvTruthTable.Columns[i].DefaultCellStyle.BackColor = Color.White;

this.FillColumn(n, rowsCount, i);

}

else

{

dgvTruthTable.Columns[i].DefaultCellStyle.BackColor = Color.DarkGray;

}

}

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

if (n >= Constants.AutoN || cbRandom.Checked)

{

this.FillF(rowsCount);

}

}

private void FillColumn(int variableCount, int rowsCount, int columnNumber)

{

var c = (int)rowsCount / (int)Math.Pow(2, columnNumber + 1);

var vc = 0;

var v = false;

for(int i = 0; i < rowsCount; i++)

{

dgvTruthTable[columnNumber, i].Value = Convert.ToInt32(v).ToString();

vc++;

if (vc == c)

{

vc = 0;

v = !v;

}

}

}

private void FillF(int rowsCount)

{

for (int i = 0; i < rowsCount; i++)

{

dgvTruthTable[Constants.MaxN,i].Value=Convert.ToInt32(Rand.Next(0, 2)).ToString();

}

}

private void FillFEmpty(int rowsCount)

{

for (int i = 0; i < rowsCount; i++)

{

dgvTruthTable[Constants.MaxN, i].Value = string.Empty;

}

}

private void cbRandom_CheckedChanged(object sender, EventArgs e)

{

var rowsCount = (int)Math.Pow(2, (int)nudN.Value);

if (cbRandom.Checked)

{

this.FillF(rowsCount);

}

else

{

this.FillFEmpty(rowsCount);

}

}

private void btBuild_Click(object sender, EventArgs e)

{

var variableCount = (int)nudN.Value;

var rowsCount = (int)Math.Pow(2, variableCount);

var matrix = new List<int[]>(rowsCount);

var function = new List<int>(rowsCount);

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

// Функция заполнения

for (int i = 0; i < rowsCount; i++)

{

int value;

if (dgvTruthTable[Constants.MaxN, i].Value == null || Int32.TryParse(dgvTruthTable[Constants.MaxN, i].Value.ToString(), out value) == false)

{

this.InputError();

return;

}

function.Add(value);

}

// Матрица заполнения

for (int i = 0; i < rowsCount; i++)

{

matrix.Add(new int[variableCount]);

for (int j = 0; j < variableCount; j++)

{

matrix[i][j] = int.Parse(dgvTruthTable[j, i].Value.ToString());

}

}

Каждая булева функция имеет представление в виде по крайней мере одного полинома Жегалкина. Это представление единственно с точностью до перестановки как самих слагаемых, так и до перестановки сомножителей в слагаемых.

// Нахождение полинома Жегалкина.

try

{

var minterns = 0;

var polynom = builder.BuildZhegalkinPolinom(matrix, function, Constants.Variables, out minterns);

polinomy.Add(polynom);

minterny.Add(minterns);

}

catch

{

this.UnexpectedError();

}

}

// Нахождение минимального полинома

var minPol = polinomy[0];

var minMin = minterny[0];

var nessesaryLine = 0;

for (int k = 1; k < emptyRowsCount; k++)

{

if (minterny[k] < minMin)

{

minMin = minterny[k];

minPol = polinomy[k];

nessesaryLine = k;

}

}

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

Алгоритм минимизации основан на переборе функций меньшей размерности. Здесь большую роль играют группы преобразований, сохраняющих сложность функций, так как вместо функций можно перебрать лишь представителей классов эквивалентности. (Ужас, про что все это?)

var g = 0;

for (int i = 0; i < rowsCount; i++)

{

int value;

if (dgvTruthTable[Constants.MaxN, i].Value == null || Int32.TryParse(dgvTruthTable[Constants.MaxN, i].Value.ToString(), out value) == false)

{

dgvTruthTable[Constants.MaxN, i].Value = indexs[nessesaryLine][g].ToString();

g++;

}

}

lResult.Text = minPol;

if (cbUse.Checked)

{

lResult.Text = lResult.Text.Replace("@", "(+)");

}

lResult.Text = lResult.Text.Replace("^", "&");

lMinternsResult.Text = minMin.ToString();

}

3 Разработка программного обеспечения