Силаенков А.Н. Автоматизированные обучающие системы. Обзор
Подождите немного. Документ загружается.
Алгоритм поиска сокращенной ДНФ (КНФ):
1. К исходной СДНФ (СКНФ) выполняются все операции неполного
склеивания
над элементарными конъюнкциями (дизъюнкциями) n – го ранга.
Получение конъюнкции (дизъюнкции) (n-1) – го ранга. Проведение
всех
операций поглощения.
2. Выполнение всех операций неполного склеивания над
элементарными
конъюнкциями (n-1) – го ранга, получение конъюнкции
(дизъюнкции) (n-2) –
го ранга. Проведение всех операций поглощения.
Так выполняются все операции до получения элементарных
конъюнкции (дизъюнкции) 1 – го ранга.
Получение тупиковых ДНФ (КНФ)
Исключение лишних элементарных конъюнкции (дизъюнкции) с
помощью импликантной матрицы. В импликантной матрице количество
столбцов равно количеству элементарных конъюнкции (дизъюнкции)
совершенных ДНФ (КНФ), а количество строк равно количеству
конъюнкции (дизъюнкции) сокращенной ДНФ (КНФ).
Пример:
Пусть имеется булева функция, заданная таблицей истинности (табл.
9.1.1).
X
1
X
2
X
3
X
1
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
151
Ее СДНФ имеет вид:
F = /x
1
/x
2
/x
3
x
4
v /x
1
/x
2
x
3
x
4
v /x
1
x
2
/x
3
x
4
v /x
1
x
2
x
3
x
4
v x
1
x
2
x
3
/x
4
v x
1
x
2
x
3
x
4
.
Для удобства изложения пометим каждую конституенту единицы
из СДНФ функции F каким-либо десятичным номером (произвольно).
Выполняем склеивания. Конституента 1 склеивается только с конституентой
2 (по переменной x
3
) и с конституентой 3 (по переменной х
2
), конституента 2
с конституентой 4 и т.д. В результате получаем:
1 - 2: /x
1
/x
2
x
4
1 - 3: /x
1
/x
3
x
4
2 - 4: /x
1
x
3
x
4
3 - 4: /x
1
x
2
x
4
4 - 6: x
2
x
3
x
4
5 - 6: x
1
x
2
x
3
Результатом склеивания является всегда элементарное произведение,
представляющее собой общую часть склеиваемых конституент. Далее
производим склеивание получаемых элементарных произведений.
Склеиваются только те произведения, которые содержат одинаковые
переменные. Имеет место два случая склеивания:
/x
1
/x
2
x
4
v /x
1
x
2
x
4
= /x
1
/x
2
x
4
v /x
1
x
2
x
4
v /x
1
x
4
/x
1
/x
3
x
4
v /x
1
x
3
x
4
= /x
1
/x
3
x
4
v /x
1
x
3
x
4
v /x
1
x
4,
с появлением одного и того же элементарного произведения
/x
1
x
4.
Дальнейшие склеивания невозможны. Произведя поглощения (из полученной
ДНФ вычеркиваем все поглощаемые элементарные произведения), получим
сокращенную ДНФ:
x
2
x
3
x
4
v x
1
x
2
x
3
v /x
1
x
4
Переходим ко второму этапу. Для получения минимальной ДНФ необходимо
убрать из сокращенной ДНФ все лишние простые импликанты. Для этого используется
импликантаная матрица Квайна.
Просты
е
импликанты
Конституенты единицы
/
x
1
/x
2
/x
3
x
4
/
x
1
/x
2
x
3
x
4
/
x
1
x
2
/x
3
x
4
/
x
1
x
2
x
3
x
4
x
1
x
2
x
3
/x
4
x
1
x
2
x
3
x
4
/x
1
x
4
X X X X
x
2
x
3
x
4
X X
x
1
x
2
x
3
X X
Простая импликанта поглощает некоторую конституенту единицы,
если является ее собственной частью. Соответствующая клетка
импликантной матрицы на пересечении строки (с рассматриваемой простой
импликантой) и столбца (с конституентой единицы) отмечается крестиком.
152
Минимальные ДНФ строятся по импликантной матрице
следующим образом:
1. Ищутся столбцы импликатной матрицы, имеющие только один
крестик. Соответствующие этим крестикам импликанты называются
базисными и составляют так называемое ядро булевой функции. Ядро
обязательно входит в минимальную ДНФ.
2. Рассматриваются различные варианты выбора совокупности
простых импликант, которые накроют крестиками остальные столбцы
импликантной матрицы, и выбираются варианты с минимальным суммарным
числом букв в такой совокупности импликант.
В примере ядро функции импликанты: x
1
x
2
x
3
, /x
1
x
4
. Импликанта x
2
x
3
x
4
–
лишняя, так как ядро накрывает все столбцы импликантной матрицы.
Поэтому функция имеет единственную тупиковую и минимальную ДНФ:
F = x
1
x
2
x
3
v /x
1
x
4
Минимизация ФАЛ методом Квайна – Мак – Класки
Мак – Класки предложил элементарные конъюнкции (дизъюнкции)
СДНФ
(СКНФ) обозначить двоичными эквивалентами.
Сами двоичные эквиваленты разбить на непересекающиеся группы.
Эти два момента позволили исключить полный перебор при
образовании сокращенных ФАЛ.
Непересекающиеся группы – это группы двоичных эквивалентов с
одинаковым количеством единиц.
Метод представляет собой формализованный на этапе нахождения
простых импликант метод Квайна. Формализация производится следующим
образом:
1. Все конституанты единицы из СДНФ (СКНФ) булевой функции
f записываются их двоичными номерами.
2. Все номера разбиваются на непересекающиеся группы. Признак
образования i-й группы: i единиц в каждом двоичном номере конституенты
единицы.
3. Склеивание производят только между номерами соседних групп.
Склеиваемые номера отмечаются каким-либо знаком (зачеркиванием).
4. Склеивания производят всевозможные, как и в методе Квайна.
Неотмеченные после склеивания номера являются простыми импликантами.
Нахождение минимальных ДНФ (КНФ) далее производится по
импликантной матрице, как и в методе Квайна.
Более подробно рассмотрим метод на примере решения следующей
задачи:
Пример. Минимизировать методом Квайна - Мак-Класки булеву функцию f,
заданную таблицей истинности
X Y Z F
0 0 0 1
0 0 1 1
0 1 0 1
153
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-
5. Составляем импликантную матрицу.
0
00
0
01
0
10
1
10
1
11
0
0-
X X - - -
0
-0
X - X - -
154
-
10
- - X X -
1
1-
- - - X X
F1 = /x/y /x/z xy
F2 = /x/y y/z xy
Минимизация ФАЛ методом диаграмм Вейча
Метод позволяет быстро получать минимальные ДНФ (КНФ) булевой
функции f небольшого числа переменных. В основе метода лежит задание
булевых функций диаграммами некоторого специального вида,
получившими название диаграмм Вейча. Для булевой функции двух
переменных диаграмма Вейча имеет вид:
Рис. 1
Каждая клетка диаграммы соответствует набору переменных булевой
функции в ее таблице истинности. На (рис.1) это соответствие показано, в
клетке диаграммы Вейча ставится единица, если булева функция принимает
единичное значение на соответствующем наборе. Нулевые значения булевой
функции в диаграмме Вейча не ставятся.
Функции 4-х переменных представлена на рисунке 2:
Рис. 2
Каждой клетке диаграммы соответствует свой набор; соседние наборы
расположены рядом в строке либо в столбце.
Соседними наборами называются наборы, отличающиеся одной
компонентой. Напомним, что конституенты, соответствующие таким
наборам, склеиваются (см. метод Квайна- Мак-Класки).
Общее правило склеивания на диаграммах Вейча можно
сформулировать следующим образом: склеиванию подлежат прямоугольные
конфигурации, заполненные единицами и содержащие число клеток,
являющееся степенью 2. Получающееся новое элементарное произведение
определяется как произведение переменных, не меняющих своего значения
на всех склеиваемых наборах. Число m оставшихся переменных в
элементарном произведении определяется легко:
m = n - log
2
M
155
где n - число переменных функции, М - число склеиваемых наборов.
Метод широко используется на практике, благодаря простоте и удобству.
После небольшой тренировки достигается элементарный навык определения
минимальной ДНФ по диаграмме "с первого взгляда". Минимизация булевой
функции заключается в нахождении минимального накрытия всех единиц
диаграммы Вейча блоками из единиц (указанной конфигурации),
расположенных в соседних клетках диаграммы. При этом всегда считается,
что левый край диаграммы Bейча 4-х переменных примыкает к ее правому
краю, а верхний oкрай диаграммы примыкает к нижнему ее краю. После
получения минимального накрытия всех единиц диаграммы Вейча,
минимальная ДНФ булевой функции записывается как дизъюнкция
элементарных конъюнкций, соответствующих выделенным блокам единиц в
диаграмме. Рассмотрим на примере.
Пример. Получить минимальную ДНФ функции, заданной таблицей истинности
методом диаграмм Вейча.
X
1
X
2
X
3
X
1
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
1
, x
2
, x
3
, x
4
) = /x
1
x
2
/x
3
/x
4
/x
1
x
2
/x
3
x
4
/x
1
x
2
x
3
/x
4
/x
1
x
2
x
3
x
4
x
1
/x
2
/
x
3
x
4
x
1
/x
2
x
3
/x
4
x
1
/x
2
x
3
x
4
x
1
x
2
/x
3
x
4
x
1
x
2
x
3
/x
4
x
1
x
2
x
3
x
4
1 1
1 1 1 1
1 1
1 1
156
x
1
x
3
x
4
F(x
1
, x
2
, x
3
, x
4
) = /x
1
x
2
x
1
x
4
x
1
x
3
Минимизация ФАЛ методом Петрика
Метод используется для нахождения всех минимальных покрытий
конституент единицы и позволяет получить все тупиковые ДНФ по
импликантной матрице. Суть метода заключается в следующем. По
импликантной матрице строится так называемое конъюнктивное
представление мипликантной матрицы. Для этого все простые импликанты
обозначаются разными буквами (обычно прописными латинскими). После
этого, для каждого i-ro столбца импликантной матрицы строится дизъюнкция
всех букв, обозначающих строки матрицы, пересечение которых с i-м
столбцом отмечено крестиком. Конъюнктивное представление импликантной
матрицы образуется как конъюнкция построенных дизъюнкций для всех
столбцов матрицы. К конъюнктивному представлению матрицы могут быть
применены все соотношения булевой алгебры с целью его упрощения. После
раскрытия скобок и выполнения всех возможных поглощений получается
дизъюнкция конъюнкций, каждая из которых содержит все импликанты
тупиковой ДНФ.
Пример.
По заданной импликантной матрице найти методом Петрика все тупиковые
ДНФ булевой функции f.
Простые
импликанты
Конституенты единицы
0
001
0
011
0
101
0
111
1
110
1
111
0- -1 X X X X
- 111 X X
111- X X
Имеющиеся простые импликанты обозначим буквами:
/x
1
x
4
= A. x
2
x
3
x
4
= B. x
1
x
2
x
3
= C. Тогда конъюнктивное представление w
матрицы имеет вид
w = A*A*A*(A v B)*C(B v C). Упростим его.
w = A*(A v B)*C(B v C) = AC. Тупиковая ДНФ содержит две простые
импликанты: А = /x
1
x
4
и C = x
1
x
2
x
3
и имеем вид f = /x
1
x
4
v x
1
x
2
x
3
.
Минимизация ФАЛ методом Блейка – Порецкого
Метод позволяет получать сокращенную ДНФ булевой функции f из ее
произвольной ДНФ. Базируется на применении формулы обобщенного
склеивания:
Ax v B/x = Ax v B/x v AB
157
x
1
В основу метода положено следующее утверждение: если в
произвольной ДНФ булевой функции f произвести все возможные
oбобщенные склеивания, а затем выполнить все поглощения, то в результате
получится сокращенная ДНФ функции f.
Пример:
Булева функция f задана произвольной ДНФ:
f = /x
1
/x
2
v x
1
/x
2
/x
3
v x
1
x
2
Найти методом Блейка - Порецкого сокращенную ДНФ функции f.
Проводим обобщенные склеивания. Видно, что первый и второй
элемент заданной ДНФ допускают обобщенное склеивание по переменной х
1
.
В результате склеивания имеем:
/x
1
/x
2
v x
1
/x
2
/x
3
= /x
1
/x
2
v x
1
/x
2
/x
3
v /x
2
/x
3
Первый и третий элемент исходной ДНФ допускают обобщенное
склеивание как по переменной х
1
, так и по х
2
. После склеивания по x
1
имеем:
/x
1
/x
2
v x
1
x
2
= /x
1
/x
2
v x
1
x
2
v /x
2
x
2
= /x
1
/x
2
v x
1
x
2
После склеивания по x
2
имеем:
/x
1
/x
2
v x
1
x
2
= /x
1
/x
2
v x
1
x
2
v /x
1
x
1
= /x
1
/x
2
v x
1
x
2
Второй и третий элемент ДНФ допускают обобщенное склеивание по
переменной х
2
. После склеивания получаем:
x
1
/x
2
/x
3
v x
1
x
2
= x
1
/x
2
/x
3
v x
1
x
2
v x
1
x
3
Выполнив последнее обобщенное склеивание, приходим к ДНФ:
f = /x
1
/x
2
v x
1
/x
2
/x
3
v /x
2
/x
3
v x
1
x
2
v x
1
/x
3
После выполнения поглощений получаем:
f = /x
1
/x
2
v /x
2
/x
3
v x
1
x
2
v x
1
/x
3
Попытки дальнейшего применения операции обобщенного склеивания
и поглощения не дают результата. Следовательно, получена сокращенная
ДНФ функции f. Далее задача поиска минимальной ДНФ решается с
помощью импликантной матрицы точно так же, как в методе Квайна.
Минимизация частично определенных булевых функций
В реальных задачах очень часто бывает так, что значение булевой
функции на некоторых наборах неопределено и может доопределяться
произвольно. В этом случае доопределение функции было бы целесообразно
производить таким образом, чтобы ее минимальная нормальная форма имела
наименьшее число букв из всех возможных вариантов доопределения.
Пример:
Функция задана диаграммой Вейча, представленной (табл. 4.7.1(a)).
Таблица
158
Доопределение функции на неопределенных наборах единицами (табл
4.7.1(b))
Таблица
или нулями (табл 4.7.1(c))
Таблица
приводит к разным минимальным ДНФ. Однако, более простая
минимальная ДНФ получается, если произвести доопределение так, как это
сделано на диаграмме Вейча (табл. 4.7.2)
Таблица
Алгоритм поиска минимальной ДНФ частично определенной
функции F:
1. Найти любым известным способом сокращенную ДНФ
функции получающейся доопределением единицами исходной функции
F на всех неопределенных наборах.
2. Выбрать минимальную ДНФ по импликантной матрице, где
в столбцах выписаны лишь те конституенты единицы функции F,
которые соответствуют полностью определенным единичным наборам
Аналогичный алгоритм (с доопределением нулевыми наборами) может
быть предложен для поиска КНФ. При этом доопределение таблицы
истинности функции F может быть произведено по разному для КНФ и ДНФ.
Для решения рассматриваемой задачи практически достаточно тех
навыков, которые были получены при минимизации полностью
определенных булевых функций непосредственно по диаграмме Вейча.
159
Теоритическая часть
Цели и задачи создания электронного учебника
Данное электронное учебное пособие предназначено в помощь
студентам кафедры «Компьютерные системы и технологии» МИФИ в
изучении логических основ теории компьютеров. Методов представления
функций алегбры – логики, минимизации ФАЛ методом диаграмм Вейча,
методом Квайна – Мак – Класки и методом Петрика.
Помимо вышеозначенных целей электронный учебник предназначен
для проверки знаний студентов в рамках данного курса.
Выбор, обоснование выбора программных продуктов
Для выполнения поставленной задачи необходимо провести анализ
существующих средств разработки и выявить инструмент, отвечающий
следующим требованиям:
Соответствие требованиям концепции 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.
160