ГОУ ВПО

«СУРГУТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Ханты-Мансийского  автономного округа – Югры»

 

                                                                              

Кафедра автоматики и компьютерных систем

КУРСОВАЯ  РАБОТА

 

Тема: Приложение «Представление логических выражений в виде карт Карно».

 
 
 
 
 
 
 
 
 

Выполнил: студент 12-61 гр. 4 курса

Факультета  автоматики и телекоммуникаций

Захарова

Мария

Анатольевна

 

                                      Научный руководитель:

                                      доцент

                                      Даниленко

                                      Иван 

                                      Николаевич

 

                                      доцент

                                      Гришмановский

                                      Павел

                                      Валерьевич

 
 
 
 

Сургут  2010

 

СОДЕРЖАНИЕ

Аннотация.......................................................................................................................................3

Задание............................................................................................................................................4

Введение.........................................................................................................................................5

Анализ.............................................................................................................................................6

Проектирование.............................................................................................................................7

Кодирование и  отладка.................................................................................................................9

Тестирование................................................................................................................................11

Руководство пользователя………………………………….….….……......….….…….….….17

Акт независимого тестирования….……………………………….…………………………..18

Заключение...................................................................................................................................19

Список используемой литературы.............................................................................................20

Приложение А..............................................................................................................................21

Приложение Б..............................................................................................................................30

Приложение В..............................................................................................................................32

 

     АННОТАЦИЯ

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

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

 

                 

 

ВВЕДЕНИЕ

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

    Карты Карно — это альтернативный способ представления таблицы истинности в виде двухмерной сетки. Карты Карно для функций, зависящих от n переменных, представляет собой прямоугольник, разделенный на 2ⁿ клеток. Каждой клетке диаграммы ставится в соответствие двоичный n-мерный набор. В карту Карно булевы переменные передаются из таблицы истинности и упорядочиваются с помощью кода Грея, в котором каждое следующее число отличается от предыдущего только одним разрядом. Значения заданной функции f из таблицы истинности вносятся в нужные квадраты, однако если клетке соответствует 0, то обычно она остается пустой[5].

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

 

 

АНАЛИЗ

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

    В задачи анализа входят:

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

     Согласно  техническому заданию, необходимо реализовать приложение, обеспечивающее представление логических выражений в виде карт Карно. Так как приложение будет иметь пользовательский интерфейс, то целесообразно использование графического интерфейса. Среда разработки приложения является Borland C++ Builder 6.0.

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

 

ПРОЕКТИРОВАНИЕ

 

          Целью этапа проектирования является получение формализованного представления о разрабатываемом  продукте.

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

    Проектирование интерфейса приложения.

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

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

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

      Для выбора типа функции ДНФ или КНФ можно использовать компоненты: TGroupBox и TCheckBox или TRadioGroup и TRadioButton. Для отображения информации возможно использование компонента TLabel. 

      Проектирование  карты Карно.

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

    Пример  карты для четырех переменных:

    Составим  таблицу истинности:

    

    Рис.1 Таблица истинности для 4 переменных.

    Перерисуем  таблицу истинности в 2-х мерный вид:

    

    Рис.2 Таблица истинности в 2-ом виде для 4 переменных.

    Переставим  в ней строки и столбцы в  соответствие с кодом Грея, получаем карту Карно:

    

    Рис.3 Карта Карно для 4 переменных.

    В приложение прорисовка карты может  быть реализована через компонент TStringGrid.

    Каждому набору значений переменных по строкам  и столбцам соответствует своя ячейка, расположенная на их пересечении. Она  заполняется в соответствующее значение из таблицы истинности. Карта заполняется только единицами, остальные ячейки остаются пустыми[3].

 
 

 

     КОДИРОВАНИЕ И ОТЛАДКА

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

    Строка №240. int GrayEncode(int g) - Функция преобразования числа в код Грея. Данная функция выполняет преобразование целого числа, представленного в десятичном формате, в код Грея, так же представленного в виде десятичного числа.

    Строка  № 244. AnsiString AddZero (AnsiString, int) - Функция выравнивания строки до указанного числа символов. Для обеспечения возможности корректного сравнения двух строковых переменных, необходимо выровнять длину каждой переменной. Для этих операций была создана данная функция. В качестве формального параметра требуется строка и требуемая длина. Результатов выравнивания будет строка, дополненная нулями до нужной длины.

    Строка  № 251. void DrawGray(void) - Функция прорисовки влияния переменных относительно кода Грея. Данная функция обеспечивает перерисовку события OnDraw() компонента StringGrid. В результате чего становится возможным закрашивать определенную ячейку нужным цветом. Для того, чтобы наглядно показать влияние переменных, соответствующая область, помимо закраски, будет содержать символ «1», информирующий о том, что данная область соответствует влиянию истинного значения переменной. Процесс определения область закрашивания определяется по следующему алгоритму: запускается цикл, перебирающий все индексы столбцов и строк таблицы. Затем каждый индекс преобразуется в код Грея. В результате индекс будет представлен в виде строки, содержащей 0 и 1. Теперь работа производится с полученной строкой. Если i-й элемент строки равен 1, что соответствует истинному значению переменной, то необходимо закрасить индекс текущей строки/столбца. Для этого при помощи стандартной структуры TRect, получаются координаты нужной ячейки (CellRect(i,j)). Затем, устанавливается нужный цвет заливки (Canvas->Brush->Color). Далее по полученным координатам и установленным цветом выполняется заливка нужной ячейки FillRect(Rect). После этого, процесс продолжается, пока индекс не станет равным максимальному значению. Закраска ячеек производится только для «шапки» карты Карно.

    Строка  № 117. AnsiString ImplicantToCode(AnsiString, AnsiString, int) - Функция выделения переменных из строки. Данная функция производит декомпозицию строки, содержащей ДНФ или КНФ. Декомпозиция состоит из двух этапов: выделение импликант, и выделение переменных. В зависимости от формы функции, разделяющим элементом первой декомпозиции будет служить либо знак «+» (для ДНФ) либо «&» (для КНФ). Разделяющим элементом для второй декомпозиции будет служить инверсный символ (+ -> &; & -> +). Выделение импликанты или переменной будет производиться пока не будет достигнут конец строки. Последний параметр необходим для проверки числа переменных в каждой импликанте. Их количество недолжно превышать количество переменных указанных в программе.