Размещено на http://www.allbest.ru/

93

Размещено на http://www.allbest.ru/

Реферат

программирование булевой функция

Пояснительная записка страниц, таблица, рисунков, источников.

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

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

Цель работы - разработка исследовательского комплекса минимизации полинома Жегалкина частично определенных булевых функций, то есть необходимо разработать комплекс, решающий задачу формирования минимального полинома Жегалкина по вектору значений булевой функции методом частных полиномиальных нормальных форм (ЧПНФ).

Метод исследования и аппаратура - персональный компьютер с операционной системой Microsoft Windows 7, среда разработки Microsoft Visual Studio 2012 (Microsoft Visual C# 2012 Express Edition).

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

Введение

На протяжении последних 20 лет в России, странах СНГ и особенно в дальнем зарубежье, ведутся научно-технические разработки по реализации логических преобразователей в электронной компонентной базе (ЭКБ) на основе представления реализуемых булевых функций в виде различных полиномиальных форм, среди которых в первую очередь выделяют полиномы Жегалкина и полиномы Рида-Маллера с фиксированной полярностью.

Теоретический интерес к полиномиальным формам булевых функций (БФ) обусловлен тем, что нахождение полиномиальной формы БФ относят к NP-трудным задачам [1], в связи с чем асимптотические вычислительная (О) и объемная (V) сложности алгоритмов полиномиального преобразования БФ имеют оценку порядка О(2ⁿ) и V(2ⁿ), где n - количество аргументов преобразуемой БФ. Асимптотические оценки вычислительной и объемной сложности характеризуют весь класс алгоритмов полиномиального преобразования БФ, подчеркивая то, что любой алгоритм из данного класса не может быть реализован быстрее чем за 2ⁿ шагов алгоритма, при этом потребуется более чем 2ⁿ бит (слов) памяти. Таким образом, теоретический интерес состоит в отыскании наилучших алгоритмов полиномиального преобразования БФ, ориентированных на практическую реализацию средствами вычислительной техники (программными или аппаратурными).

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

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

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

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

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

В-третьих, необходимо проработать (детализировать, уточнить, определить типы данных) алгоритм программы. На данном этапе должна быть разработана схема алгоритма, а также, определена структура интерфейсной части будущей программы.

В-четвертых, проверить работоспособность программы на контрольных примерах.

1. Общие сведения о булевых функциях

1.1 Частично определенные булевы функции

Логическая функция -- это сложное высказывание, состоящее из нескольких простых, связанных между собой соединительными союзами. Она записывается аналитически в виде Y = f(x₁,x₂, ..., x_n), где х_i-- двоичная переменная, х_i { 0,1}; Y{0,1 }.

Частично определенная функция - это логическая функция, значения которой определены не на всех входных наборах. На тех входных наборах, где функция не определена, проставляется прочерк (или любой другой символ, отличный от 0 и 1) [2].

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

Алгоритм поиска минимальной дизъюнктивной нормальной формы (ДНФ) частично определенной функции f можно представить следующим образом:

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

- выбрать минимальную ДНФ по импликантной матрице, где в столбцах выписаны лишь те конституенты единицы функции f, которые соответствуют полностью определенным единичным наборам.

Аналогичный алгоритм (с доопределением нулевыми наборами) может быть предложен для поиска конъюнктивной нормальной формы (КНФ). При этом доопределение таблицы истинности функции f может быть произведено по-разному для КНФ и ДНФ.

1.2 Методы формирования полинома Жегалкина

Известно, что любую булеву функцию можно представить полиномом Жегалкина (полиномом по модулю 2), и это представление с точностью до перестановки слагаемых единственно. Приведем некоторые наиболее известные способы построения такого полинома [3].

1.2.1 Преобразование произвольной формулы алгебры логики

Метод преобразования произвольной формулы алгебры логики состоит в следующем: сначала строим ДНФ или КНФ БФ, а затем формируем полином Жегалкина, используя известные соотношения

.

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

Преобразуем логическую формулу :

Таким образом, полином Жегалкина для данной функции имеет вид .

1.2.2 Метод неопределенных коэффициентов

Метод неопределенных коэффициентов состоит в следующем [4]: записываем булеву функцию в виде полинома Жегалкина с неопределенными коэффициентами. Приравниваем значения функции к значениям полинома на соответствующих наборах переменных и находим неизвестные коэффициенты. На значениях исходной функции строим треугольник Паскаля, складывая каждый раз соответствующие значения функции по модулю 2. Тогда числа на левой стороне полученного треугольника определяют коэффициенты полинома Жегалкина при монотонных конъюнкциях, соответствующих наборам переменных. Напомним, что элементарная конъюнкция называется монотонной, если она не содержит отрицаний переменных. Константа 1 (т. е. элементарная конъюнкция нулевого ранга) считается по определению монотонной конъюнкцией.

Теперь воспользуемся методом неопределенных коэффициентов. Для этого запишем нашу функцию в виде многочлена с неопределенными коэффициентами:

,

где A, B, C, D, E, F, G, H ?{0,1}.

Таблица истинности нашей функции выглядит следующим образом:

Таблица 1.1 - Таблица истинности функции

x	y	z	x?y	y	xz	y?xz	(x?y)(y?xz)
0	0	0	0	1	0	1	0
0	0	1	0	1	0	1	0
0	1	0	1	0	0	0	0
0	1	1	1	0	0	0	0
1	0	0	1	1	0	1	1
1	0	1	1	1	1	1	1
1	1	0	1	0	0	0	0
1	1	1	1	0	1	1	1

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

Решая систему, получим коэффициенты равные: H=0, G=0, F=0, D=0, E=1, C=0, B=1, A=1. Подставляя найденные значения A, B, C, D, E, F, G, H в формулу

,

получим полином Жегалкина того же вида, что и методом преобразования произвольной формулы алгебры логики: .

1.2.3 Метод минимизации полностью определенных логических функций с помощью карт Карно

Для реализации метода зададим исходную функцию набором значений f(x,y,z)=(00001101). На строке значений функции построим треугольник Паскаля, представленный на рисунке 1.1, складывая попарно по модулю 2 соседние значения функции.



Рисунок 1.1 - Треугольник Паскаля

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

Сравнивая предложенные методы построения полинома Жегалкина, студенты (да и преподаватели тоже) отдают предпочтение последнему методу, обосновывая выбор быстротой получения результата и простотой алгоритма построения треугольника Паскаля.

1.2.4 Метод минимизации полностью определенных логических функций с помощью карт Карно

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

Пусть с помощью карты Карно задана логическая функция , необходимо найти ее тупиковую ДНФ. Тогда задача минимизации решается следующим образом: среди единичных значений логической функции , предварительно нанесенных на карту Карно, отыскиваются прямоугольники и/или квадраты с числом клеток , где k=(n-1),…,0. Выделяемые прямоугольники и/или квадраты могут пересекаться между собой.

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

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

Импликанты - это элементарные конъюнкции ранга меньше максимального, которые не могут быть склеены (т.е. объединены) между собой.

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

Если необходимо найти тупиковую КНФ логической функции , то задача минимизации решается следующим образом: среди нулевых значений логической функции , предварительно нанесенных на карту Карно, отыскиваются прямоугольники и/или квадраты с числом клеток , где k=(n-1),…,0. Выделяемые прямоугольники и/или квадраты могут пересекаться между собой.

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

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

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

Минимизируем с помощью данного метода логическую функцию, СДНФ которой определяется соотношением:

(1.1)

Построим для функции карту Карно (рисунок 1.2).

ab c	00	01	11	10
0	1	1	1	0
1	1	0	1	1

Рисунок 1.2 - Карта Карно функции

Определим максимальный размер прямоугольника, которым можно покрыть клетки карты. Величина прямоугольников вычисляется как , где k=(n-1),(n-2),…,0, а n - число аргументов, от которых зависит логическая функция. В нашем случае n=3, следовательно, максимальный размер прямоугольника равен ==4. В карте Карно нет прямоугольника, состоящего из четырех единиц, стоящих рядом, поэтому объединять клетки карты можно только по две, например так, как показано на рис. 1.3.

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

+ = = ,

то есть переменная из этой группы может быть исключена.

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

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

Рисунок 1.3 - Карта Карно функции

Объединяя знаком дизъюнкции найденные из каждого прямоугольника импликанты, получаем тупиковую ДНФ функции :

(1.2)

Объединить клетки карты Карно можно и другим образом (рисунок 1.3),



Рисунок 1.4 - Карта Карно функции

тогда получим еще одну тупиковую ДНФ, реализующую функцию (1.3):

(1.3)

1.2.5 Метод минимизации частично определенных логических функций с помощью карт Карно

Пусть не полностью определенная логическая функция R(a,b,c,d) задана с помощью карты Карно (рисунок 1.5).

Рисунок 1.5 - Карта Карно логической функции R(a,b,c,d)

Для представления функции R(a,b,c,d) в виде минимальной ДНФ целесообразно следующее доопределение логической функции (рисунок 1.6):



Рисунок 1.6 - Доопределенная карта Карно логической функции R(a,b,c,d)

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

Рисунок 1.7 - Карта Карно логической функции R(a,b,c,d)

В результате минимизации получим минимальную ДНФ логической функции R(a,b, c,d):

(1.4)

Сравнение эффективности минимизированных форм часто проводят по способу Шеннона. Этот способ базируется на введении такого понятия как цена схемы - Ц. Цену схемы можно рассчитать по следующей формуле:

, (1.5)

где - количество входов у j-ого элемента, i-количество элементов.

Пусть логическая функция R(a,b,c,d) задана в виде СДНФ (1.6):

(1.6)

Оценим минимальную ДНФ логической функции R(a,b, c,d) (1.5):

Элементов “И” в выражении присутствует 5 (два элемента “И” по 2 входа, три элемента “И” по 3 входа), элементов “ИЛИ”- 1 (один элемент на 5 входов), элементов “НЕ”- 4 (4 элемента по 1 входу), следовательно:

Ц=2*2+3*3+1*5+4*1=22 входа

Тем же способом оценим СДНФ логической функции R(a,b,c,d) - выражение (1.6):

Элементов “И” - 11 (одиннадцать элементов по 4 входа), элементов “ИЛИ”- 1 (один элемент на 11 входов), элементов “НЕ”- 4 (4 элемента по 1 входу), следовательно:

Ц=11*4+1*11+4*1=59 входов.

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

1.3 Полиномы Жегалкина для частично определенных булевых функций

Как уже было сказано, частичной называется булева функция, значения которой заданы лишь на некоторых наборах, образующих в совокупности область определения функции. Предположим, что на всех остальных наборах значения рассматриваемой функции могут быть любыми - их можно определить произвольно. Если число таких наборов равно k, то существует 2^k различных доопределений функции и каждому из них соответствует свой полином Жегалкина. Из практических соображений возникает задача выбора среди них, самого простого, с минимальным числом конъюктивных термов.

Эту задачу можно решить «в лоб», перебирая все 2^k доопределения, находя для каждого их них полином Жегалкина и выбирая среди них наилучший. Суть метода заключается в следующем.

Совокупность значений функции, определяемых на k безразличных наборах, представляется булевым k - вектором. Значения этого вектора перебираются по коду Грея, введенному первоначально для представления натуральных чисел. При этом, как и в случае двоичного позиционного кода, представляются числа меньшие, чем 2^k, начиная с 0.

В соответствии с кодом Грея, значения вектора, кодирующие число 0, составляется из нулей, а каждое последующее получается из предыдущего изменения значения в одном разряде - самом младшем (правом) из тех, которые обеспечивают получение еще не использованной комбинации [2].

1.4 Обзор программных средств решения задачи

1.4.1 Анализ современных языков и сред программирования

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

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

Несмотря на огромное множество языков программирования, лишь немногие из них получили широкую известность и признание программистов. Для того, что бы определить самые популярные языки программирования воспользуемся данными голландской компании «TIOBE Software BV» в первую очередь известной своим регулярно рассчитываемым рейтингом популярности языков программирования. Результаты рейтинга представлены на рисунке 1.8.

Рисунок 1.8 - Популярность языков программирования за 2014 год

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

Сравнение языков программирования между собой, по их возможностям, по способам реализации и даже сложности освоения, задача очень сложная. Оценить удобство тех или иных семантических конструкций возможно только на реальных примерах и для каждого языка программирования можно найти задачу, для которой он подходит лучше, чем все остальные. Зачастую подобные сравнения выливаются в настоящие «войну» между сообществами программистов. Каждая из сторон защищает «свой» язык программировании и никак не принимает доводы другой стороны. Как правило, такие «войны» заканчиваются «ничьей» или не заканчиваются вовсе.

Однако, рассмотрение языков программирования по общим для них всех концепциям, позволяет судить о развитии программирования в целом. Рассмотрим наиболее востребованные из них языки.

1.4.2 Язык программирования Java

Java -- язык программирования, разработанный компанией SunMicrosystems. Приложения Java обычно компилируются в специальный байт-код, поэтому они могут работать на любой виртуальной Java-машине(JVM) независимо от компьютерной архитектуры. Дата официального выпуска -- 23 мая 1995 года. Сегодня технология Java предоставляет средства для превращения статических Web-страниц в интерактивные динамические документы и для создания распределенных не зависящих от платформы приложений.

Программы на Java транслируются в байт-код, выполняемый виртуальной машиной Java (JVM) --программой, обрабатывающей байтовый код и передающей инструкции оборудованию как интерпретатор.

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

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

- применение технологии трансляции байт-кода в машинный код непосредственно во время работы программы (JIT-технология) с возможностью сохранения версий класса в машинном коде,

- широкое использование платформенно - ориентированного кода (native-код) в стандартных библиотеках,

- аппаратные средства, обеспечивающие ускоренную обработку байт-кода (например, технология Jazelle, поддерживаемая некоторыми процессорами фирмы ARM).

Основные возможности языка:

- автоматическое управление памятью;

- расширенные возможности об работки исключительных ситуаций;

- богатый набор средств фильтрации ввода/вывода;

- набор стандартных коллекций, таких как массив, список, стек и т.п.;

- наличие простых средств создания сетевых приложений (в том числе с использованием протокола RMI);

- наличие классов, позволяющих выполнять HTTP-запросы и обрабатывать ответы;

- встроенные в язык средства создания многопоточных приложений;

- унифицированный доступ к базам данных:

- на уровне отдельных SQL-запросов--на основе JDBC,SQLJ;

- на уровне концепции объектов, обладающих способностью к хранению в базе данных--на основе Java Data Objects и Java Persistence API;

- поддержка шаблонов (начиная с версии 1.5);

- параллельное выполнение программ [6].

1.4.3 Язык программирования C#

В июне 2000 года стало известно о новом языке программирования, родившемся в недрах компании Microsoft. Он стал частью новой технологии Microsoft, названной .NET (читается «Dot Net»). В рамках этой технологии предусмотрена единая среда выполнения программ (Common Language Runtime, CLR), написанных на разных языках программирования. Одним из таких языков, основным в этой среде, и является C# (C#, читается «C sharp», «Си шарп»). Названием языка, конечно же, хотели подчеркнуть его родство с Си++, ведь # -- это два пересекшихся плюса. Но больше всего новый язык похож на Java . И нет сомнений, что одной из причин его появления стало стремление Microsoft ответить на вызов компании Sun.

Хотя официально авторы C# не называются, но на титульном листе одной из предварительных редакций справочника по языку обозначены Андерс Хейльсберг (Anders Hejlsberg) -- создатель Турбо Паскаля и Дельфи, перешедший в 1996 году в Microsoft, и Скотт Вилтамут (Scott Wiltamuth).

Единая среда выполнения программ основана на использовании промежуточного языка IL (Intermediate Language -- промежуточный язык), исполняющего почти ту же роль, что и байт-код виртуальной машины языка Ява. Используемые в рамках технологии .NET компиляторы с различных языков транслируют программы в IL-код. Так же как и байт-код Явы, IL-код представляет собой команды гипотетической стековой вычислительной машины. Но есть и разница в устройстве и использовании IL.

Во-первых, в отличие от JVM, IL не привязан к одному языку программирования. В составе, предварительных версий Microsoft.NET имеются компиляторы с языков Си++, C#, Visual Basic. Независимые разработчики могут добавлять другие языки, создавая компиляторы с этих языков в IL-код.

Во-вторых, IL предназначен не для программной интерпретации, а для последующей компиляции в машинный код. Это позволяет достичь существенно большего быстродействия программ. Содержащие IL-код файлы несут достаточно информации для работы оптимизирующего компилятора [7].

«C# -- простой, современный, объектно-ориентированный язык с безопасной системой типов, происходящий от Си и Си++. C# будет удобен и понятен для программистов, знающих Си и Си++. C# сочетает продуктивность Visual Basic и мощность Си++.» Такими словами начинается описание C#.

Рассмотрим технические особенности языка:

- единицей компиляции является файл (как в Си, Си++, Яве). Файл может содержать одно или несколько описаний типов: классов (class), интерфейсов (interface), структур (struct), перечислений (enum), типов-делегатов (delegate) с указанием (или без указания) об их распределении по пространствам имен;

- пространства имен (namespace) регулируют видимость объектов программы (как в Си++). Пространства имен могут быть вложенными. Разрешено употребление объектов программы без явного указания пространства имен, которому этот объект принадлежит. Достаточно лишь общего упоминания об использовании этого пространства имен в директиве using (как в Турбо Паскале). Предусмотрены псевдонимы для названий пространств имен в директиве using (как в языке Оберон);

- элементарные типы данных: 8-разрядные (sbyte, byte), 16-разрядные (short, ushort), 32-разрядные (int, uint) и 64-разрядные (long, ulong) целые со знаком и без знака, вещественные одиночной (float) и двойной (double) точности, символы Unicode (char), логический тип (bool, не совместим с целыми), десятичный тип, обеспечивающий точность 28 значащих цифр (decimal);

- структурированные типы: классы и интерфейсы (как в Яве), одномерные и многомерные (в отличие от Явы) массивы, строки (string), структуры (почти то же, что и классы, но размещаемые не куче и без наследования), перечисления, несовместимые с целыми (как в Паскале);

- типы-делегаты или просто «делегаты» (подобны процедурным типам в Модуле_2 и Обероне, указателям на функции в Си и Си++);

- типы подразделяются на ссылочные (классы, интерфейсы, массивы, делегаты) и типы-значения (элементарные типы, перечисления, структуры). Объекты ссылочных типов размещаются в динамической памяти (куче), а переменные ссылочных типов являются, по сути, указателями на эти объекты. В случае типов-значений переменные представляют собой не указатели, а сами значения. Неявные преобразования типов разрешены только для случаев, когда они не нарушают систему безопасности типов и не приводят к потере информации. Все типы, включая элементарные, совместимы с типомobject, который является базовым классом всех прочих типов. Предусмотрено неявное преобразование типов-значений к типу object, называемое упаковкой (boxing), и явное обратное преобразование -- распаковка (unboxing);

- автоматическая сборка мусора (как в Обероне и Яве);

- обширный набор операций с 14 уровнями приоритета. Переопределение операций (как в Алголе-68, Аде, Си++). С помощью операторов checked и unchecked можно управлять контролем переполнения при выполнении операций с целыми;

- методы с параметрами значениями, параметрами-ссылками (ref) и выходными параметрами (out). Слова ref и out нужно записывать перед параметром не только в описании метода, но и при вызове. Наличие выходных параметров позволяет контролировать выполнение определяющих присваиваний. По правилам языка любая переменная должна гарантированно получить значение до того, как будет предпринята попытка ее использования;

- управляющие операторы: if, switch, while, do, for, break, continue (как в Си, Си++ и Яве). Оператор foreach, выполняющий цикл для каждого элемента «коллекции», несколько разновидностей оператора перехода goto;

- обработка исключений (как в Яве);

- свойства -- элементы классов (объектов), доступ к которым осуществляется так же, как и к полям (можно присвоить или получить значение), но реализуется неявно вызываемыми подпрограммами get и set (как в Объектном Паскале -- входном языке системы Delphi);

- индексаторы -- элементы классов (объектов), позволяющие обращаться к объектам так же, как к массивам (указанием индекса в квадратных скобках). Реализуются неявно вызываемыми подпрограммами get и set. Например, доступ (для чтения) к символам строки может выполняться как к элементам массива благодаря тому, что для стандартного класса string реализован индексатор;

- события -- элементы классов (поля или свойства) процедурного типа (делегаты), к которым вне класса, где они определены, применимы только операции += и -=, позволяющие добавить или удалить методы-обработчики событий для объектов данного класса;

- небезопасный (unsafe) код, использующий указатели и адресную арифметику, локализуется в частях программы, помеченных модификатором unsafe;

- препроцессор, предусматривающий, в отличие от Си и Си++, только средства условной компиляции [8].

Разумеется, обсуждавшиеся недостатки C# вовсе не лишают язык перспектив. Он во многих отношениях предпочтительней Си++. Общая неудовлетворенность языком Си++, признанием которой является само появление нового языка, является одной из основных предпосылок успеха C#.

Сравнивая C# с Явой, можно увидеть много общих черт. Правда, если Ява-системы многоплатформны, то реализация C# существует пока только для операционной системы Windows и только одна. Но, несмотря на тяжеловесность, можно ожидать, что язык будет реализован и для других систем. Кроме того, сама платформа Microsoft .NET с единой средой выполнения программ может быть продвинута на альтернативные архитектуры, в первую очередь на UNIX-системы.

C# представляется более реалистичным языком, чем Ява. В отличие от Явы, он самодостаточен. То есть на C# можно написать любую программу, не прибегая к другим языкам. Это возможно благодаря наличию «небезопасных» блоков кода, которые открывают доступ непосредственно к аппаратуре. В языке Ява для доступа к средствам низкого уровня должны использоваться «родные методы» (native methods), которые необходимо программировать на других языках.

И, разумеется, перспективы C# в первую очередь связаны с теми усилиями, которые, конечно же, приложит компания Microsoft для его продвижения [8].

1.4.4 Сравнение сред программирования

Eclipse -- свободная интегрированная среда разработки модульных кроссплатформенных приложений. Развивается и поддерживается Eclipse Foundation.

Наиболее известные приложения на основе Eclipse Platform -- различные «Eclipse IDE» для разработки ПО на множестве языков (например, наиболее популярный «Java IDE», поддерживавшийся изначально, не полагается на какие-либо закрытые расширения, использует стандартный открытый API для доступа к Eclipse Platform).

Eclipse служит в первую очередь платформой для разработки расширений, чем он и завоевал популярность: любой разработчик может расширить Eclipse своими модулями. Уже существуют Java Development Tools (JDT), C/C++ Development Tools (CDT), разрабатываемые инженерами QNX совместно с IBM, и средства для языков Ada (GNATbench, Hibachi), COBOL, FORTRAN, PHP, X10 (X10DT) и пр. от различных разработчиков. Множество расширений дополняет среду Eclipse диспетчерами для работы с базами данных, серверами приложений и др.

Eclipse JDT (Java Development Tools) -- наиболее известный модуль, нацеленный на групповую разработку: среда интегрирована с системами управления версиями -- CVS, GIT в основной поставке, для других систем (например,Subversion, MS SourceSafe) существуют плагины. Также предлагает поддержку связи между IDE и системой управления задачами (ошибками). В основной поставке включена поддержка трекера ошибок Bugzilla, также имеется множество расширений для поддержки других трекеров (Trac, Jira и др.). В силу бесплатности и высокого качества, Eclipse во многих организациях является корпоративным стандартом для разработки приложений.

Eclipse написана на Java, потому является платформо-независимым продуктом, за исключением библиотеки SWT, которая разрабатывается для всех распространённых платформ (см. ниже). Библиотека SWT используется вместо стандартной для Java библиотеки Swing. Она полностью опирается на нижележащую платформу (операционную систему), что обеспечивает быстроту и натуральный внешний вид пользовательского интерфейса, но иногда вызывает на разных платформах проблемы совместимости и устойчивости приложений.

Основой Eclipse является платформа расширенного клиента (RCP -- от англ. rich client platform). Её составляют следующие компоненты:

- ядро платформы (загрузка Eclipse, запуск модулей);

- OSGi (стандартная среда поставки комплектов (англ. bundles));

- SWT (портируемый инструментарий виджетов);

- JFace (файловые буферы, работа с текстом, текстовые редакторы);

- рабочая среда Eclipse (панели, редакторы, проекции, мастеры);

- GUI в Eclipse написан с использованием инструментария SWT.

Последний, в отличие от Swing (который самостоятельно эмулирует графические элементы управления), использует графические компоненты данной операционной системы. Пользовательский интерфейс Eclipse также зависит от промежуточного слоя GUI, называемого JFace, который упрощает построение пользовательского интерфейса, базирующегося на SWT.

Гибкость Eclipse обеспечивается за счёт подключаемых модулей, благодаря чему возможна разработка не только на Java, но и на других языках, таких как C/C++, Perl, Groovy, Ruby, Python, PHP, Erlang, Компонентного Паскаля,Zonnon и прочих [6].

Microsoft Visual Studio -- линейка продуктов компании Microsoft, включающих интегрированную среду разработки программного обеспечения и ряд других инструментальных средств. Данные продукты позволяют разрабатывать как консольные приложения, так и приложения с графическим интерфейсом, в том числе с поддержкой технологии Windows Forms, а также веб-сайты, веб-приложения, веб-службы как в родном, так и в управляемом кодах для всех платформ, поддерживаемых Windows, Windows Mobile, Windows CE, .NET Framework, Xbox, Windows Phone .NET Compact Framework и Silverlight.

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

Visual Studio позволяет создавать и подключать сторонние дополнения (плагины) для расширения функциональности практически на каждом уровне, включая добавление поддержки систем контроля версий исходного кода (как например, Subversion и Visual SourceSafe), добавление новых наборов инструментов (например, для редактирования и визуального проектирования кода напредметно-ориентированных языках программирования или инструментов для прочих аспектов процесса разработки программного обеспечения (например, клиент Team Explorer для работы с Team Foundation Server) [9].

1.4.5 Обоснование выбора средств для разработки программного продукта

В ходе анализа современных языков программирования, вопрос о выборе средства разработки, на котором будет создаваться программный продукт был решен в пользу языка С#.

Что касается выбора среды разработки, то была выбрана среда Microsoft Visual Studio 2012, в частности, версия Microsoft Visual C# 2012 Express Edition, потому что она является свободно распространяемой. То есть, выбрав эту среду, мы получили возможность разработать наш модуль и приложение, не нарушив ни одного закона об авторском праве.

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

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

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

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

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

i	а	b	с	f
0	0	0	0	1
1	0	0	1	1
2	0	1	0	1
3	0	1	1	0
4	1	0	0	0
5	1	0	1	0
6	1	1	0	1
7	1	1	1	0

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

,

,

,

,

,

.

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

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

Ki	ЧПНФ
	1	с		с	а	ас	а	ас	Bi
	1	1	1	1	1	1	1	1	B0
		1		1		1		1	B1
			1	1			1	1	B2
				1				1	B3
					1	1	1	1	B4
						1		1	B5
							1	1	B6
								1	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	ЧПНФ
	1 000	с 001	b 010	bс 011	а 100	ас 101	аb 110	аbс 111	Bi
000	1	1	1	1	1	1	1	1	B0
001		1		1		1		1	B1
010			1	1			1	1	B2
011				1				1	B3
100					1	1	1	1	B4
101						1		1	B5
110							1	1	B6
111								1	B7
	1	0	0	1	1	0	1	0	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. Разработка программного обеспечения

3.1 Разработка макета программного продукта

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

Таблица истинности необходима в программе. Это удобный инструмент описания поведения логической функции. Она служит для наглядности и удобства пользователя вводить данные и изменять вектор БФ.