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

1) Нет одинаковых элементарных конъюнкций

2) В каждой элементарной конъюнкции присутствует X_i либо для всех i от 1 до n.

Совершенные КНФ - функции от n аргументов, есть КНФ, удовлетворяющие двум условиям:

1) Нет одинаковых элементарных дизъюнкций

2) В каждой элементарной дизъюнкции присутствует X_i либо для всех i от 1 до n.

Теорема. Любую ДНФ (КНФ) можно преобразовать к совершенной ДНФ (КНФ)

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

F = F(x₁, x₂ … x_n)_ДНФ = K₁ K₂ … K_m K₂,

так как K₂ = K₂ K₂,

то допустим, что получили ДНФ:

F = F(x₁, x₂ … x_n) = (x₁ x₂ /x₃) (/x₁ /x₃) = (x₁ x₂ /x₃) [(/x₁ /x₃) (x₂ /x₂ )] = (x₁ x₂ /x₃) (/x₁ /x₃ x₂) (/x₁ /x₃ /x₂)

Получили совершенную дизъюктивную нормальную форму. Что и требовалось доказать.

Правило получения СДНФ (СКНФ):

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

Расставляем отрицание следующим образом: если переменная входит как 0 (1), то остается без изменений, если 1 (0), то над ней ставится отрицание. То есть каждая элементарная конъюнкция (дизъюнкция) должна обращаться в ноль.

Пример:

Получить СДНФ функции:

F(x₁, x₂, x₃) = x₁ (x₂ x₃ /x₁)

x1	x2	x3	/x1	x3 /x1	x2 x3 /x1	x1 (x2 x3 /x1)
0	0	0	1	0	0	0
0	0	1	1	1	1	0
0	1	0	1	0	1	0
0	1	1	1	1	1	0
1	0	0	0	0	0	0
1	0	1	0	0	0	0
1	1	0	0	0	1	1
1	1	1	0	0	1	1

F_СДНФ = (x₁ x₂ /x₃) (x₁ x₂ x₃)

1.9.2 Методы определения минимальных функций (ДНФ, КНФ)

Логические основы широко используются для решения задач анализа и синтеза логических систем.

Этапы анализа систем:

Формирование функций, описыващих работу логических систем.

Минимизация этих функций.

Анализ схемы, посредством исследования минимальных ФАЛ.

Этапы синтеза:

Запись закона функционирования схемы (таблиц истинности и др.)

Выбор логического базиса (в нем записывается уравнение)

Минимизация логических уравнений

Построение схемы по логическим уравлениям

Минимальная ДНФ - это ДНФ, содержащая минимальное количество букв по сравнению с любой другой, эквивалентной ДНФ.

F₁,F₂ …F_k - эквивалентные ДНФ

F(x₁, x₂ … x_n) _ДНФ =

Минимальная КНФ - это КНФ, содержащая минимальное количество букв по сравнению с любой другой, эквивалентной КНФ.

F₁,F₂ …F_k - эквивалентные КНФ

F(x₁, x₂ … x_n) _КНФ =

Методы определения минимальных ФАЛ:

Метод Квайна (классический)

Метод Квайна - Мак - Класки

Метод диаграмм Вейча

Метод Блейка - Порецкого

Метод Петрика

1.9.3 Минимизация ФАЛ методом Квайна

Метод Квайна основывается на применении двух основных соотношений:

1. Соотношение склеивания xy V x/y = xy V x/y V x

2. Соотношение поглошения x~y V x = x, где ~x E {x;/x}

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

Метод применим к совершенной ДНФ. Из соотношения поглощения следует, что произвольное элементарное произведение поглощается любой его частью.

Для доказательства достаточно показать, что произвольная простая импликанта р = x_i1x_i2 ... x_in может быть получена. В самом деле, применяя к р операцию развертывания (обратную операции склеивания): A = A (x v /x) = Ax v A/x по всем недостающим переменным x_i^(k+l), ..., x_i^n исходной функции f, получаем совокупность S конституент единицы. При склеивании всех конституент из S получим импликанту р. Последнее очевидно, поскольку операция склеивания обратна операции развертывания. Множество S конституент обязательно присутствует в совершенной ДНФ функции f поскольку р - ее импликанта.

Алгоритм получения минимальной формы (ДНФ, КНФ):

1 этап. Формируется СДНФ (СКНФ) для данной функции.

2 этап. Из полученной СДНФ (СКНФ) получаем сокращенную ДНФ (КНФ).

3 этап. Из сокращенной ДНФ (КНФ) получаем тупиковые ДНФ (КНФ).

4 этап. Из тупиковых ДНФ (КНФ) выбираем минимальные ДНФ (КНФ).

Сокращенная ДНФ (КНФ) - это функция, получаемая из исходной СДНФ (СКНФ) при выполнении всех операций полного склеивания и всех операций поглощения

Тупиковая ДНФ (КНФ) - это дизъюнкция (конъюнкция) простых элементарных конъюнкции (дизъюнкции), ни одну из которых исключить нельзя.

Алгоритм поиска сокращенной ДНФ (КНФ):

1. К исходной СДНФ (СКНФ) выполняются все операции неполного склеивания над элементарными конъюнкциями (дизъюнкциями) n - го ранга.

Получение конъюнкции (дизъюнкции) (n-1) - го ранга. Проведение всех операций поглощения.

2. Выполнение всех операций неполного склеивания над элементарными конъюнкциями (n-1) - го ранга, получение конъюнкции (дизъюнкции) (n-2) - го ранга. Проведение всех операций поглощения.

Так выполняются все операции до получения элементарных конъюнкции (дизъюнкции) 1 - го ранга.

Получение тупиковых ДНФ (КНФ)

Исключение лишних элементарных конъюнкции (дизъюнкции) с помощью импликантной матрицы. В импликантной матрице количество столбцов равно количеству элементарных конъюнкции (дизъюнкции) совершенных ДНФ (КНФ), а количество строк равно количеству конъюнкции (дизъюнкции) сокращенной ДНФ (КНФ).

Пример:

Пусть имеется булева функция, заданная таблицей истинности (табл. 9.1.1).

X1	X2	X3	X1	F
0	0	0	0	0
0	0	0	1	1
0	0	1	0	0
0	0	1	1	1
0	1	0	0	0
0	1	0	1	1
0	1	1	0	0
0	1	1	1	1
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	0
1	1	0	0	0
1	1	0	1	0
1	1	1	0	1
1	1	1	1	1

Ее СДНФ имеет вид:

F = /x₁/x₂/x₃x₄ v /x₁/x₂x₃x₄ v /x₁x₂/x₃x₄ v /x₁x₂x₃x₄ v x₁x₂x₃/x₄ v x₁x₂x₃x₄.

Для удобства изложения пометим каждую конституенту единицы из СДНФ функции F каким-либо десятичным номером (произвольно). Выполняем склеивания. Конституента 1 склеивается только с конституентой 2 (по переменной x₃ ) и с конституентой 3 (по переменной х₂), конституента 2 с конституентой 4 и т.д. В результате получаем:

1 - 2: /x₁/x₂x₄ 1 - 3: /x₁/x₃x₄ 2 - 4: /x₁x₃x₄ 3 - 4: /x₁x₂x₄ 4 - 6: x₂x₃x₄ 5 - 6: x₁x₂x₃

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

/x₁/x₂x₄ v /x₁x₂x₄ = /x₁/x₂x₄ v /x₁x₂x₄ v /x₁x₄ /x₁/x₃x₄ v /x₁x₃x₄ = /x₁/x₃x₄ v /x₁x₃x₄ v /x₁x_4,

с появлением одного и того же элементарного произведения /x₁x_4. Дальнейшие склеивания невозможны. Произведя поглощения (из полученной ДНФ вычеркиваем все поглощаемые элементарные произведения), получим сокращенную ДНФ: x₂x₃x₄ v x₁x₂x₃ v /x₁x₄

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

Простые импликанты	Конституенты единицы
	/x1/x2/x3x4	/x1/x2x3x4	/x1x2/x3x4	/x1x2x3x4	x1x2x3/x4	x1x2x3x4
/x1x4	X	X	X	X
x2x3x4				X		X
x1x2x3					X	X

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

Минимальные ДНФ строятся по импликантной матрице следующим образом:

Ищутся столбцы импликатной матрицы, имеющие только один крестик. Соответствующие этим крестикам импликанты называются базисными и составляют так называемое ядро булевой функции. Ядро обязательно входит в минимальную ДНФ.

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

В примере ядро функции импликанты: x₁x₂x₃, /x₁x₄. Импликанта x₂x₃x₄ - лишняя, так как ядро накрывает все столбцы импликантной матрицы. Поэтому функция имеет единственную тупиковую и минимальную ДНФ:

F = x₁x₂x₃ v /x₁x₄

1.9.4 Минимизация ФАЛ методом Квайна - Мак - Класки

Мак - Класки предложил элементарные конъюнкции (дизъюнкции) СДНФ (СКНФ) обозначить двоичными эквивалентами.

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

Эти два момента позволили исключить полный перебор при образовании сокращенных ФАЛ.

Непересекающиеся группы - это группы двоичных эквивалентов с одинаковым количеством единиц.

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

Все конституанты единицы из СДНФ (СКНФ) булевой функции f записываются их двоичными номерами.

Все номера разбиваются на непересекающиеся группы. Признак образования i-й группы: i единиц в каждом двоичном номере конституенты единицы.

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

Склеивания производят всевозможные, как и в методе Квайна. Неотмеченные после склеивания номера являются простыми импликантами.

Нахождение минимальных ДНФ (КНФ) далее производится по импликантной матрице, как и в методе Квайна.

Более подробно рассмотрим метод на примере решения следующей задачи:

Пример. Минимизировать методом Квайна - Мак-Класки булеву функцию f, заданную таблицей истинности

X	Y	Z	F
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

СДНФ: F(x,y,z): /x/y/z /x/yz /xy/z xy/z /x/y/z

1. В СДНФ функции F заменим все конституенты единицы их двоичными номерами:

F = 110 111 010 001 000

2. Образуем группы двоичных номеров. Признаком образования i - й группы является i единиц в двоичном номере конституенты единицы

Номер группы	Двоичные номера конституент единицы
0	000
1	001, 010
2	110
3	111

3. Склеим номера из соседних групп таблицы №1. Склеиваемые номера вычеркнем (Прим. - выделяем цветом). Результаты склеивания занесем в таблицу №2. Склеим номера из соседних групп таблицы 2. Склеиваться могут только номера, имеющие черточки в одинаковых позициях. Склеиваемые номера вычеркнем.

Таблица №2

Номер группы	Двоичные номера конституент единицы
0	00-, 0-0
1	-10,
2	11-

4. Составляем импликантную матрицу.

	000	001	010	110	111
00-	X	X	-	-	-
0-0	X	-	X	-	-
-10	-	-	X	X	-
11-	-	-	-	X	X

F1 = /x/y /x/z xy

F2 = /x/y y/z xy

1.9.5 Минимизация ФАЛ методом диаграмм Вейча

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

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

Каждой клетке диаграммы соответствует свой набор; соседние наборы расположены рядом в строке либо в столбце.

Соседними наборами называются наборы, отличающиеся одной компонентой. Напомним, что конституенты, соответствующие таким наборам, склеиваются (см. метод Квайна- Мак-Класки).

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

m = n - log₂M

где n - число переменных функции, М - число склеиваемых наборов. Метод широко используется на практике, благодаря простоте и удобству. После небольшой тренировки достигается элементарный навык определения минимальной ДНФ по диаграмме "с первого взгляда". Минимизация булевой функции заключается в нахождении минимального накрытия всех единиц диаграммы Вейча блоками из единиц (указанной конфигурации), расположенных в соседних клетках диаграммы. При этом всегда считается, что левый край диаграммы Bейча 4-х переменных примыкает к ее правому краю, а верхний oкрай диаграммы примыкает к нижнему ее краю. После получения минимального накрытия всех единиц диаграммы Вейча, минимальная ДНФ булевой функции записывается как дизъюнкция элементарных конъюнкций, соответствующих выделенным блокам единиц в диаграмме. Рассмотрим на примере.

Пример. Получить минимальную ДНФ функции, заданной таблицей истинности методом диаграмм Вейча.

X1	X2	X3	X1	F
0	0	0	0	0
0	0	0	1	0
0	0	1	0	0
0	0	1	1	0
0	1	0	0	1
0	1	0	1	1
0	1	1	0	1
0	1	1	1	1
1	0	0	0	0
1	0	0	1	1
1	0	1	0	1
1	0	1	1	1
1	1	0	0	0
1	1	0	1	1
1	1	1	0	1
1	1	1	1	1

СДНФ: F(x₁, x₂, x₃, x₄) = /x₁x₂/x₃/x₄ /x₁x₂/x₃x₄ /x₁x₂x₃/x₄ /x₁x₂x₃x₄ x₁/x₂/x₃x₄ x₁/x₂x₃/x₄ x₁/x₂x₃ x₄ x₁x₂/x₃x₄ x₁x₂x₃/x₄ x₁x₂x₃x₄

F(x₁, x₂, x₃, x₄) = /x₁x₂ x₁ x₄ x₁ x₃

1.9.6 Минимизация ФАЛ методом Петрика

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

Пример. По заданной импликантной матрице найти методом Петрика все тупиковые ДНФ булевой функции f.

Простые импликанты	Конституенты единицы
	0001	0011	0101	0111	1110	1111
0- -1	X	X	X	X
- 111				X		X
111-					X	X

Имеющиеся простые импликанты обозначим буквами:

/x₁x₄ = A. x₂x₃x₄ = B. x₁x₂x₃ = C

Тогда конъюнктивное представление w матрицы имеет вид

w = A*A*A*(A v B)*C(B v C). Упростим его.

w = A*(A v B)*C(B v C) = AC

Тупиковая ДНФ содержит две простые импликанты: А = /x₁x₄ и C = x₁x₂x₃ и имеем вид f = /x₁x₄ v x₁x₂x₃.

1.9.7 Минимизация ФАЛ методом Блейка - Порецкого

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

Ax v B/x = Ax v B/x v AB

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

Пример:

Булева функция f задана произвольной ДНФ:

f = /x₁/x₂ v x₁/x₂/x₃ v x₁x₂

Найти методом Блейка - Порецкого сокращенную ДНФ функции f.

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

/x₁/x₂ v x₁/x₂/x₃ = /x₁/x₂ v x₁/x₂/x₃ v /x₂/x₃

Первый и третий элемент исходной ДНФ допускают обобщенное склеивание как по переменной х₁, так и по х₂. После склеивания по x₁ имеем:

/x₁/x₂ v x₁x₂ = /x₁/x₂ v x₁x₂ v /x₂x₂ = /x₁/x₂ v x₁x₂

После склеивания по x₂ имеем:

/x₁/x₂ v x₁x₂ = /x₁/x₂ v x₁x₂ v /x₁x₁ = /x₁/x₂ v x₁x₂

Второй и третий элемент ДНФ допускают обобщенное склеивание по переменной х₂. После склеивания получаем:

x₁/x₂/x₃ v x₁x₂ = x₁/x₂/x₃ v x₁x₂ v x₁x₃

Выполнив последнее обобщенное склеивание, приходим к ДНФ:

f = /x₁/x₂ v x₁/x₂/x₃ v /x₂/x₃ v x₁x₂ v x₁/x₃

После выполнения поглощений получаем:

f = /x₁/x₂ v /x₂/x₃ v x₁x₂ v x₁/x₃

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

1.9.8 Минимизация частично определенных булевых функций

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

Алгоритм поиска минимальной ДНФ частично определенной функции F:

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

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

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

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

2. Теоретическая часть

2.1 Цели и задачи создания электронного учебника

Данное электронное учебное пособие предназначено в помощь студентам кафедры «Компьютерные системы и технологии» МИФИ в изучении логических основ теории компьютеров. Методов представления функций алегбры - логики, минимизации ФАЛ методом диаграмм Вейча, методом Квайна - Мак - Класки и методом Петрика.

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

2.2 Выбор, обоснование выбора программых продуктов

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

Соответствие требованиям концепции RAD (быстрая разработка приложений);

Работа в операционной системе Windows (версии 95, 98 и NT);

Возможность быстрого освоения разработчиком;

Оправданная стоимость.

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

Наличие интегрированной среды разработки (ИСР);

Объектно-ориентированный базовый язык программирования;

Использование библиотеки компонентов, позволяющих повторно применять отлаженный программный код;

Визуальный стиль проектирования интерфейса;

Наличие галерей форм и шаблонов приложений;

Интеграция с другими продуктами через поддержку COM, DDE, создание и использование DLL.

Легкость в освоении разработчиком достигается использованием в качестве базовых языков - объектных версий классических языков программирования.

Delphi базируется на языке Object Pascal. Компиляторы с языков семейства Паскаль фирмы Borland (начиная с Turbo Pascal 1.0) были одними из самых быстрых компиляторов. В настоящее время Object Pascal - это объектно-ориентированный язык с твердой опорой в виде хорошего компилятора. По заявлениям фирмы-разработчика скорость компиляции - до 350000 строк кода в минуту (на Pentium 90).

В итоге в качестве средства разработки приложения была выбрана среда Inprise Delphi 7.

2.3 Разработка структуры системы хранения информации

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

Было рассмотрено три способа хранения информации:

хранение информации в базе данных,

хранение информации в файлах,

две системы: при проведении занятий в лабораториях института, использовать базу данных; при удаленом использовании программы - использовать файловую систему.

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

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

Использование двух систем, также не подходит, так как придется поддерживать обновление двух систем.

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

2.3.1 Логическая модель системы хранения

Информация по управлению процессом обучением включает в себя в качестве объекта знаний ученик, результат обучения.

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

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

1

103

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

2.3.2 Физическая модель системы хранения

В таблице № хранится регистрационная информация о пользователях.

Таблица №

Ключ	Имя поля	Тип поля	Размер/вид поля	Краткое описание поля/комментарий
Да	ID	Smallint	(от - 32768 до 32767)	Идентификатор (первичный ключ)
	PrAdmin	Boolean	Yes/No	Признак того, что пользователь является администратором
	SecondName	Char	100	Фамилия
	FirstName	Char	100	Имя
	OtName	Char	100	Отчество
	GroupNumb	Char	10	Номер группы
	User	Char	10	Логин
	Password	Char	10	Пароль
	Date	Date		Дата регистрации в системе
	Comment	Char	250	Комментарий

В таблице № хранится информация об уроках, существующих в системе.

Таблица №

Ключ	Имя поля	Тип поля	Размер/вид поля	Краткое описание поля/комментарий
Да	ID	Smallint	(от - 32768 до 32767)	Идентификатор (первичный ключ)
	NameLess	Char	50	Название урока

В таблице № хранится информация о результатах выполнения уроков.

Таблица №

Ключ	Имя поля	Тип поля	Размер/вид поля	Краткое описание поля/комментарий
Да	ID_User	Smallint	(от - 32768 до 32767)	Идентификатор пользователя (внешний ключ)
	Date	Date		Дата выполнения урока
	TimeBeg	Date		Время начала выполнения урока
	TimeEnd	Date		Время окончания выполнения урока
	Test	Boolean	Yes/No	Признак тестового урока
Да	ID_Less	Smallint	(от - 32768 до 32767)	Идентификатор урока (внешний ключ)
	Mark	Integer	(от -2e31 до 2e31 - 1)	Оценка за урок
	Comment	Char	250	Комментарий
	Reserv	Char	250	Резервное поле

2.4 Пользовательский интерфейс

Программа предусматривает выполнение четырех уроков: представление ФАЛ (получение СКНФ, СДНФ), мининизация ФАЛ методом диаграмм Вейча, минимизация ФАЛ методом Квайна - Мак - Класки, минимизация ФАЛ методом Петрика.

2.4.1 Начало работы в программе

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

При нажатии на иконку «?» пользователю представляется меню (рис. 4), которое состоит из кнопок «Информация», «О программе».

При нажатии кнопки «О программе» возникает окно, в котором содержится информация о программе: название программы, номер версии, дата, от которой действительна данная версия

При нажатии кнопки «Информация», пользователю предлагается выбор: «Теория», «Помощь по работе с программой».

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

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

Для продолжения работы в системе пользователю необходимо пройти авторизацию (рис.) в системе, для этого ввести имя пользователя (логин) и пароль.

Для пользователей, первый раз работающих в системе, необходимо зарегистрироваться (рис.).

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

После того, как пользователь прошел авторизацию в системе, пользователю предлагается выбрать урок (рис.).

Предлагается четыре урока: «Представление ФАЛ», «Метод Квайна-Мак-Класки», «Метод Петрика», «Метод диаграмм Вейча».

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

2.4.2 Представление ФАЛ

При выборе урока 1 «Представление ФАЛ» пользователю предлагается интерфейс (рис.6) программы.

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

Пользователю необходимо правильно заполнить все промежуточные и результирующие значения функции в предлагаемой таблице. В таблице значение «0» меняется на «1» одним кликом мыши. В крайней правой колонке символами «+», «-» отмечается правильность заполнения значений функции. После того, как все значения функции заполнены верно, необходимо нажать кнопку «Результат», и программа выдаст СКНФ и СДНФ функции.

Если значения функции были рассчитаны неверно, то при нажатии кнопки «Результат», программа выдаст соощение об ошибке (Рис. 6.1).

2.4.3 Метод диаграмм Вейча

При выборе Урока 2 пользователю представляется интерфейс (Рис. 7) к программе «Минимизация ФАЛ методом диаграмм Вейча».

Необходимо найти минимальную ДНФ. Исходными данными является функция и таблица истинности.

По заданной таблице истинности необходимо правильно заполнить диаграмму Вейча. Значение «0» меняется на значение «1» двойным кликом мыши. Проверить правильность заполнения можно нажатием на кнопку «Начать».



Рис. 7 Интерфейс к программе «Минимизация ФАЛ методом диаграмм Вейча»

Если диаграмма заполнена неверно, то при нажатии на данную кнопку программа выдаст сообщение об ошибке.

Рис. 7.1. Анализ ошибки: неправильное заполнение диаграммы Вейча

После того, как диаграмма заполнена, необходимо выбрать минимальное накрытие всех «1» (или «0», если КНФ). В данной программе выделение блоков осуществляется цветом. После нажатия кнопки «Начать», выбираются ячейки, которые предполагается объединить. Выбор производится кликом мыши по нужной ячейке. После чего ячейка будет выделена цветом. Для объединения ячеек в конъюнкции необходимо нажать кнопку «Выделить». Результат выделения запишется в нижнее поле. И продолжить выделения, пока не будут покрыты все «1».

Если выполняется склеивание единиц, которые не могут склеиваться (например, не смежных и не противоположных ячеек, или «0»), программа выдаст сообщение об ошибке (Рис. 7.1, Рис. 7.2).

Рис. 7.1 Анализ ошибок: «Невозможные объединения»



Рис. 7.2 Анализ ошибок: «Невозможные объединения»

2.4.4 Метод Квайна - Мак - Класки

Необходимо найти минимальную ДНФ (КНФ). Исходными данными является функция для трех переменных и таблица истинности.

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

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

Каждый раз при нажатии кнопки «Склеить», программа проверяет правильность склеивания. Если склеивание невозможно, то выводится сообщение об ошибке (рис. 8.1)

Если склеивание произведено не по всем возможным наборам, то выдается сообщение об ошибке (рис.).

После всех операций склеивания по нажатию кнопки «Продолжить», формируется импликантная матрица (Рис. 9).

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

Если минимальная функция выбрана верно, то выводится результат.

2.4.5 Метод Петрика

Необходимо найти минимальную ДНФ (КНФ). Исходными данными является функция для трех переменных и таблица истинности.

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

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

Каждый раз при нажатии кнопки «Склеить», программа проверяет правильность склеивания. Если склеивание невозможно, то выводится сообщение об ошибке (рис. 8.1)

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

Для продолжения работы необходимо нажать кнопку «Результат».

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

3. Экспериментальная часть

3.1 Разработка программы

3.1.1 Разработка пользовательского интерфейса

Интерфейс программы представляет из себя несколько отдельных форм (TForm). На каждой форме есть три кнопки «Далее», «Назад», «Выход». Переход от одной формы к другой осуществляется обработчиками событий нажатия кнопок. При нажатии кнопки «Выход», вызывается метод Close для главного окна, и программа завершается. При этом окно, на котором произошло нажатие кнопки, скрывается (вызывается Close).

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

использование нескольких форм занимает много памяти,

не удобно постоянно закрывать и вызывать заново по нажатии клавиш формы, так как это существенно замедляет работу программы,

приходится постоянно следить программно за размерами интерфейса,

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

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

Интерфейс представлен несколькими TTabSheet на одном TPageControl.

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

Интерфейс представлен (TTabSheet):

Главное окно

Окно авторизации (регистрации)

Окно выбора урока

Урок «Представление ФАЛ»

Урок «Минимизация методом Квайна-Мак-Класки»

Урок «Минимизация методом Петрика»

Урок «Минимизация методом диаграмм Вейча»

3.1.2 Разработка системы хранения информации

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

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

Формат файлов.

Файл для хранения информации о пользователях:

Идентификатор~ПризнакАдминистратора~Фамилия~Имя~Отчество~Группа~ПризнакАдминистратора~Дата регистрации в системе ~Логин~Пароль

Файл для хранения информации об уроках, существующих в системе:

Идентификатор~НазваниеУрока

Файл для хранения информации о выполнении уроков:

ИдентификаторПользователя~ИдетификаторУрока~ДатаВыполненияУрока~ВремяНачала~ВремяОкончания~ПризнакТестовогоУрока~Оценка

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

Файл для хранения информации о пользователях заполняется при регистрации новых пользователей.

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

3.1.3 Разработка подпрограммы «Представление ФАЛ»

На первом этапе работы программы генерируется функция из трех переменных.

Функция генерируется случайным образом из: x₁, x_2, x_3, /x₁, /x₂, /x₃, , , (, ). При этом анализируется, чтобы переменная и ее отрицание не попадали одновременно в функцию. И чтобы, изначально генерируемое количество знаков , не превышало количество возможных конъюнкций и дизъюнкций переменных (для функции из трех переменных число не может превышать 3).

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

Сначала записываются отрицания всех переменных. Далее отрицания переменных плюс операции выполняемые в скобках (конъюнкция приоритетнее дизъюнкции). И в последний столбец таблицы записывается вся функция.

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

Данная строка сравнивается со строкой значений из таблицы, заполненной пользователем.

Если строки совпадают, то напротив строки выводится знак «+», если не совпадают, то - «-».

Получение результата возможно только после того, как все строки совпадут.

Вывод результата, функции СКНФ, СДНФ. Вывод количества ошибок.

3.1.4 Разработка подпрограммы «Минимизация ФАЛ методом Квайна - Мак - Класки»

На первом этапе работы программы генерируется функция из трех переменных F(x, y, z). Функция генерируется случайным образом из: пяти чисел в диапазоне от 0 до 7, знаков или Р, (, ). Осуществляется проверка на то, что бы числа не повторялись. Знаки , Р, (, ) должны входить в функцию один раз.

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

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

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

Далее проход по всем таблицам. Проверяется флаг выбора. Значения, у которых флаг выбора равен 0, помещаются в импликантную матрицу.

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

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

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

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

3.1.5 Разработка подпрограммы «Минизация ФАЛ методом диаграмм Вейча»

На первом этапе работы программы генерируется функция из четырех переменных F(x₁, x_2, x_3, x₄). Функция генерируется случайным образом из: чисел от 0 до 15, знаков , Р, (, ). Проверка на то, что бы числа не повторялись. Знаки , Р, (, ) должны входить в функцию один раз.

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

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

Далее программа вычисляет все возможные минимальные функции по алгоритму перебора (см. 2.5.2.1).

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

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

Объединение ячеек диаграммы пользователем.

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

По данным объединениям формируются функции.

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

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

Вывод на экран результата. Вывод количества ошибок и оценки.

(1) Разработка функции «перебора»

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

На первом шаге запоминаются координаты ячеек матрицы, в которых стоят знаки «+». Записываются координаты в новый массив (строки, столбцы).

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

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

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

3.1.6 Разработка подпрограммы «минимизация ФАЛ методом Петрика»

На первом этапе работы программы генерируется функция из трех переменных F(x, y, z). Функция генерируется случайным образом из: пяти чисел в диапазоне от 0 до 7, знаков или Р, (, ). Осуществляется проверка на то, что бы числа не повторялись. Знаки , Р, (, ) должны входить в функцию один раз.

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

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

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

Далее проход по всем таблицам. Проверяется флаг выбора. Значения, у которых флаг выбора равен 0, помещаются в импликантную матрицу.

Строится конъюктивное представление импликантной матрицы - конъюнкция построенных дизъюнкций всех столбцов матрицы. Имеющиеся простые импликанты (значения строк) обозначаются буквами.

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

Упрощенная функция является результатом.

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

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

Выводится количество допущенных ошибок и оценка.

3.2 Тестирование и отладка

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

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

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

Тестирование системы проводилось на всем протяжении разработки системы.

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

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

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

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

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

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

Для отладки разрабатываемого модуля применялись встроенные средства отладки среды Delphi 7. Среда включает широкий спектр новейших средств для локализации всех типов ошибок. Ниже перечислены некоторые из них:

В прежних версиях Delphi точки прерывания были предназначены только для остановки процесса выполнения в режиме отладки.

В Delphi 7 можно указать какие именно действия (breakpoint actions) следует выполнить в момент достижения точки остановки. Приостановить выполнение (как в прежних версиях Delphi), добавить текстовое сообщение в log-файл для регистрации событий отладчика (event log), записать в log-файл результат вычисления выражения, содержащего переменные отлаживаемого процесса (или вычислить выражение и никуда результат не записывать), а также сделать доступной, или недоступной, группу точек прерывания (о группах будет сказано ниже). Можно выполнить одновременно несколько действий в одной точке прерывания.

С помощью пункта меню Run/Attach to Process можно начать отлаживать любой из уже запущенных процессов, в том числе, не имеющий отношения к Delphi.

Среда разработки Delphi 7 поддерживает операции drag-and-drop во время отладки. Например, из редактора кода можно перенести выражение в окно Watch List, после чего это выражение останется в соответствующем списке. Можно перенести выражение в Debug Inspector. Можно также перенести выражение на панель, содержащую дамп памяти в окне CPU, и получить его адрес.

Тестирование разработанного приложения проводилось с помощью специальной модели Rational Rose. Она содержит полный набор ситуаций, необходимых для выявления возможных ошибок преобразования. Методика тестирования включает следующие действия:

Преобразование тестовой модели с помощью разработанного модуля;

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

Составление протокола испытаний с указанием ошибок и несоответствий.

В результате тестирование и отладки программы признаны годными к эксплуатации.

Заключение

Целью данной работы было разработать электронный учебник по теме «Логические основы теории компьютеров». Требовалось разработать три урока к данному электронному учебнику: представление ФАЛ, минимизация ФАЛ методом диаграмм Вейча, минимизация ФАЛ методом Квайна - Мак - Класки, минимизация ФАЛ методом Петрика.

Для этого требовалось:

произвести обзор теоретического материала по методам представления ФАЛ

разработать сценарий проведения уроков

алгоритмы программ

написать и отладить программы

разработать пользовательский интерфейс

Для достижения поставленных целей и решения предложенной задачи была проделана следующая работа:

Рассмотрено современная ситуация в процессе компьютеризации нашего общества и конкретно процесса образования в высшей школе.

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

Изучены наиболее популярные средства разработки электронных учебников.

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

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

Были созданы три урока к данному электронному учебнику. Созданы уроки по представлению ФАЛ, минимизации ФАЛ методом диаграмм Вейча, минимизации ФАЛ методом Квайна - Мак - Класки.

Произведен обзор методов представления и преобразования функций.

Разработан сценарий проведения уроков. Определены спецификации исходных данных. Исходные данные генерируются случайным образом.

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