Методы минимизации логических функций
Содержание
Задание 1.Определить МДНФ логической функции устройства.
Составить таблицу соответствия (истинности) функции.
Перевести логическую функцию от табличной к аналитической форме в виде ДСНФ
Найти МДНФ различными методами.
прямым (алгебраическим) преобразованием;
методом Квайна;
усовершенствованным методом Квайна (Квайна-Маккласки);
методом карт Карно;
методом неопределенных коэффициентов;
Задание 2. Составить алгоритм метода минимизации
2.1 Составить содержательный (словесный) алгоритм минимизации функции, разработать граф-схему алгоритма, разработать логическую схему алгоритма в нотации Ляпунова для метода Квайна.
2.2 Составить содержательный (словесный) алгоритм минимизации функции, разработать граф-схему алгоритма, разработать логическую схему алгоритма в нотации Ляпунова для метода минимального покрытия Петрика.
2.3 Разработать рабочие программы по алгоритмам.
Задание 3. Синтез схемы логического устройства.
3.1 Выполнить синтез схемы по ДСНФ и МДНФ в базисе Буля с использованием двухвходовых логических элементов и интегральных микросхем серии 155.
3.2 Функцию МДНФ в базисе Буля полученную в первом задании представить в базисах Шеффера и Пирса.
Обосновать выбор базиса по формулам МДНФ.
3.4 Реализовать в выбранном базисе логическую схему.
Задание 1.
1.1 Составить таблицу соответствия (истинности) функции.
Составим таблицу истинности для заданной функции F(X>1>,X>2>,X>3>,X>4>).
|
№ |
X>1> |
X>2> |
X>3> |
X>4> |
F(X>1,> X>2,> X>3,> X>4>) |
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 |
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 |
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 |
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 |
1 0 1 1 0 1 1 1 0 0 1 1 0 0 0 1 |
Матрицу ДСНФ получают путем удаления тех строк, где функция равна нулю. Для нашего случая получим:
|
№ |
X>1> |
X>2> |
X>3> |
X>4> |
|
0 2 3 5 6 7 10 11 15 |
0 0 0 0 0 0 1 1 1 |
0 0 0 1 1 1 0 0 1 |
0 1 1 0 1 1 1 1 1 |
0 0 1 1 0 1 0 1 1 |
1.2 Перевести логическую функцию от табличной к аналитической форме в виде ДСНФ.
Переведем логическую функцию от табличной к аналитической форме в виде ДСНФ.
F(X>1>X>2>X>3>X>4>) = 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 >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>.
1.3 Найти МДНФ различными методами.
1.3.1 Метод эквивалентных преобразований.
В основе метода минимизации булевых функций эквивалентными преобразованиями лежит последовательное использование законов булевой алгебры. Метод эквивалентных преобразований целесообразно использовать лишь для простых функций и для количества логических переменных не более 4-х. При большем числе переменных и сложной функции вероятность ошибок при преобразовании возрастает.
Проведем прямое алгебраическое преобразование, используя закон неполного склеивания.
F(X>1>X>2>X>3>X>4>) = 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
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> =
= (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>) V
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 >V X>1>X>2>X>3>X>4>) V
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 >V X>1>X>2>X>3>X>4>) V
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>) =
= X>1>X>2>X>4 >V X>1>X>2>X>3 >V X>1>X>3>X>4 >V X>2>X>3>X>4 >V X>1>X>3>X>4 >V X>2>X>3>X>4 >V X>1>X>2>X>4 >V
V X>1>X>2>X>3>V X>2>X>3>X>4> V X>1>X>2>X>3> V X>1>X>3>X>4 >=
= (X>1>X>2>X>3 >V X>1>X>2>X>3> V X>1>X>3>X>4 >V X>1>X>3>X>4>) V X>1>X>2>X>4 >V
V (X>1>X>2>X>3 >V X>1>X>2>X>3> V X>2>X>3>X>4 >V X>2>X>3>X>4>) V X>1>X>2>X>4 >V
V (X>1>X>3>X>4 >V X>1>X>3>X>4> V X>2>X>3>X>4 >V X>2>X>3>X>4>) =
= X>1>X>3 >V X>2>X>3> V X>3>X>4> V X>1>X>2>X>4 >V X>1>X>2>X>4>.
Дальнейшее преобразование невозможно. Полученную функцию можно немного упростить с помощью вынесения за скобки общих переменных.
1.3.2 Метод Квайна
При минимизации по методу Квайна предполагается, что минимизируемая логическая функция задана в виде ДСНФ. Здесь используется закон неполного склеивания. Минимизация проводится в два этапа: нахождение простых импликант, расстановка меток и определение существенных импликант (Q-матрица).
|
ДСНФ, ранг 4 |
||
|
1 2 3 4 5 6 7 8 9 |
0000 0010 0011 0101 0110 0111 1010 1011 1111 |
|
|
Наборы 3-го ранга |
||
|
1-2 2-3 2-5 2-7 3-6 3-8 4-6 5-6 6-9 7-8 8-9 |
00*0 001* 0*10 *010 0*11 *011 01*1 011* *111 101* 1*11 |
1 2 3 4 5 6 7 8 9 10 11 |
|
Наборы 2-го ранга |
||
|
2-8 2-10 3-5 4-6 5-11 6-9 |
0*1* *01* 0*1* *01* **11 **11 |
Как видно из таблиц, при получении матрицы второго ранга первый и седьмой наборы третьего ранга не склеились ни с какими другими наборами. Их необходимо занести в конечную матрицу простых импликант. В матрице же второго ранга мы видим, что некоторые наборы одинаковые. Их необходимо вычеркнуть, так как дизъюнкция одинаковых наборов равна этой же дизъюнкции (это следует из закона повторения)
|
Простые импликанты |
|
|
1 2 3 4 5 |
0*1* *01* **11 00*0 01*1 |
Перенеся все выделенные строки в конечный массив, получим матрицу СДНФ. Алгебраическая запись СДНФ будет выглядеть следующим образом:
F(X>1>X>2>X>3>X>4>) = X>1>X>3 >V X>2>X>3> V X>3>X>4> V X>1>X>2>X>4 >V X>1>X>2>X>4>.
Эта же функция в нашем случае является и минимальной ДНФ.
Метод Квайна-Маккласки
В основу данного метода также положен закон неполного склеивания. Только в отличие от метода Квайна здесь производится гораздо меньше сравнений, так как, разбив исходную матрицу на несколько групп, мы сравниваем только те наборы, которые отличаются индексом на 1 или местоположением меток.
Распределим импликанты ДСНФ по индексам.
|
ДСНФ |
Индекс i |
|
|
1 2 3 4 5 6 7 8 9 |
0000 0010 0011 0101 0110 0111 1010 1011 1111 |
0 1 2 2 2 3 2 3 4 |
|
Распределенные наборы 4-го ранга |
||||
|
i=0 |
i=1 |
i=2 |
i=3 |
i=4 |
|
0000 |
0010 |
0011 0101 0110 1010 |
0111 1011 |
1111 |
Сравнивая соседние группы и распределяя полученные наборы по положению символа ‘*’ получим:
|
Наборы 3-го ранга |
|
|
1 2 3 4 5 6 7 8 9 10 11 |
00*0 001* 0*10 *010 0*11 *011 01*1 011* *111 101* 1*11 |
|
Распределенные наборы 3-го ранга |
|||
|
1 |
2 |
3 |
4 |
|
*010 *011 *111 |
0*10 0*11 1*11 |
00*0 01*1 |
001* 011* 101* |
|
Распределенные наборы 2-го ранга |
||
|
12 |
14 |
24 |
|
**11 |
*01* |
0*1* |
Примечание. Во всех выше приведенных таблицах простые импликанты отмечены жирным шрифтом с подчеркиванием.
Анализируя, видим, что СДНФ примет следующий вид:
|
Простые импликанты |
|
|
1 2 3 4 5 |
0*1* *01* **11 00*0 01*1 |
Или в алгебраической форме:
F(X>1>X>2>X>3>X>4>) = X>1>X>3 >V X>2>X>3> V X>3>X>4> V X>1>X>2>X>4 >V X>1>X>2>X>4>.
Метод карт Карно.
Метод карт Карно – это один из графических методов минимизации функции. Эти методы основаны на использовании особенности зрительного восприятия, так как с его помощью можно практически мгновенно распознать те или иные простые конфигурации.
Преимуществами метода карт Карно над другими методами являются:
А) простота отыскания склеивающихся компонент;
Б) простота выполнения самого склеивания;
В) нахождение всех минимальных форм функции.
Построим таблицу метода карт Карно.
|
X>1>X>2> |
X>1>X>2> |
X>1>X>2> |
X>1>X>2> |
|
|
X>3>X>4> |
■ |
|||
|
X>3>X>4> |
■ |
|||
|
X>3>X>4> |
■ |
■ |
■ |
■ |
|
X>3>X>4> |
■ |
■ |
■ |
Теперь накроем совокупность всех квадратов с метками минимальным количеством правильных прямоугольников. Таких прямоугольников в нашем случае будет 5: три четырехклеточных и два двухклеточных. Этим прямоугольникам соответствуют следующие простые импликанты:
для первого – X>3>X>4>;
для второго – X>1>X>3>;
для третьего – X>2>X>3>;
для четвертого – X>1>X>2>X>4>;
для пятого – X>1>X>2>X>4>;
Минимальная ДНФ будет выглядеть так:
F(X>1>X>2>X>3>X>4>) = X>1>X>3 >V X>2>X>3> V X>3>X>4> V X>1>X>2>X>4 >V X>1>X>2>X>4>.
Сравнивая метод карт Карно с другими методами минимизации функции можно сделать вывод, что первый больше всего подходит для ручного исполнения. Время ручной работы значительно сокращается (за счет наглядного представления склеивающихся импликант). Программная реализация данного метода имеет свои сложности. Так, очень сложно будет реализовать оптимальный выбор правильных прямоугольников, особенно для большого числа аргументов.
1.3.5 Метод неопределенных коэффициентов
Этот метод может быть использован для любого числа аргументов. Но так как этот метод достаточно громоздок, то применяется только в тех случаях, когда число аргументов не более 5-6.
В методе неопределенных коэффициентов используются законы универсального и нулевого множеств и законы повторения. В начале все коэффициенты неопределенны (отсюда и название метода).
Построим матрицу неопределенных коэффициентов для четырех аргументов. В этом случае мы будем иметь систему из 16-ти уравнений.
Система приведена на следующей странице.
Приравняем все коэффициенты 0 в тех строках, которым соответствует 0 в векторе столбце. Затем приравняем 0 соответствующие коэффициенты в других строках. После этих преобразований система примет следующий вид:
V
= 1
V
V
V
V
V
V
= 1
V
V
V
V
V
V
= 1
V
= 1
V
V
V
= 1
V
V
V
V
V
V
= 1
V
V
V
= 1
V
V
V
VV
= 1
V
V
V
= 1
Теперь в каждой строке необходимо выбрать коэффициент минимального ранга и приравнять его единице, а остальные коэффициенты – 0. После этого вычеркиваем одинаковые строки, оставляя при этом одну из них (те строки, у которых все коэффициенты равны 0, также вычеркиваются).
= 1
=
1
=
1
=
1
=
1
Запишем теперь конъюнкции, соответствующие коэффициентам, равным единицам. Мы получим минимальную ДНФ.
F(X>1>X>2>X>3>X>4>) = X>1>X>3 >V X>2>X>3> V X>3>X>4> V X>1>X>2>X>4 >V X>1>X>2>X>4>.
Итак, мы получили несколькими способами минимальную ДНФ, Во всех случаях она получилась одинаковой, то есть любой из описанных методов может быть использован для минимизации функции. Однако эти методы существенно отличаются друг от друга как по принципу нахождения МДНФ, так и по времени исполнения. Для ручных расчетов очень удобен метод карт Карно. Он нагляден, не требует рутинных операций, а выбрать оптимальное расположение правильных прямоугольников не составляет большого труда. В то время как машинная реализация данного метода осложняется необходимостью нахождения оптимального расположения прямоугольников. Естественно применение других методов (метод Квайна, метод Квайна-Маккласки, метод неопределенных коэффициентов) для ручных расчетов нецелесообразно. Они больше подойдут для машинной реализации, так как содержат большое число повторяющихся простых операций.
Задание 2.
2.1 Схема алгоритма для метода Квайна
Начало.
Ввести матрицу ДСНФ исходной функции.
Проверить на склеиваемость i-ю (i=1,m-1: где m – количество строк в ДСНФ) и j-ую (j=i+1, m) строки. Если строки склеиваются, то перейти к пункту 6, в противном случае перейти к пункту 5.
Формировать массив простых импликант, предварительно пометив символом ‘*’ ту переменную, по которой данные строки склеиваются.
Перейти к пункту 2.
Строку, которая не склеилась ни с одной другой строкой записать в конечный массив.
Перейти к пункту 2.
Вывод полученной матрицы.
Конец.
Логическая схема алгоритма в нотации Ляпунова
> 1 1 >
V>H>V>1>Z>1>V>2>V>3>V>4>V>K>
V>H> – начало.
V>1> – ввести матрицу ДСНФ исходной функции.
V>2> – формировать массив простых импликант, предварительно пометив символом ‘*’ ту переменную, по которой данные строки склеиваются.
V>3> – строку, которая не склеилась ни с одной другой строкой записать в конечный массив.
V>4> – вывод полученной матрицы.
Z>1> – если строки склеиваются, то перейти к пункту 3, в противном случае перейти к пункту 5.
V>K> – конец.
Граф-схема алгоритма.
V>1>
V>2 >
V>3>
V>4>
0
Описание машинных процедур
Procedure Stuck(S1, S2: Diz; IndexS1, IndexS2 : byte);
Данная процедура склеивает два, передаваемых ей дизъюнкта. Дизъюнкты задаются в параметрах S1, S2. Индексы IndexS1, IndexS2 определяют индексы этих дизъюнктов в главном рабочем массиве . Алгоритм работы процедуры следующий: сначала ищется количество склеивающихся символов. Если их 0, то они одинаковые, и в конечный массив записывается только один из них. Если 1, то определяется местоположение символа, по которому данные две дизъюнкции склеиваются, и заменяем этот символ на ‘*’. Все полученные результаты заносятся в массив REZ.
Все остальные функции и процедуры программы связаны с действиями над массивами, то есть не имеют непосредственного отношения к данному методу нахождения МДНФ. Поэтому нет смысла их описывать.
2.2 Схема алгоритма для метода Петрика
Начало.
Ввести матрицу ДСНФ исходной функции и простые импликанты, полученные в методе Квайна.
Составить таблицу меток.
По таблице меток построить конъюнкцию дизъюнкций, каждая из которых есть совокупность тех импликант, которые в данном столбце имеют метки.
Произвести раскрытие скобок в полученном выражении с учетом законов поглощения.
Выбрать одну из полученных конъюнкций и представить ее как совокупность соответсвующих простых импликант.
Если выбранная комбинация не является минимальной, то перейти к пункту 6, в противном случае перейти к пункту 8.
Формировать МДНФ.
Вывод полученной матрицы.
Конец.
Логическая схема алгоритма в нотации Ляпунова.
> 1 1 >
V>H>V>1>V>2>V>3>V>4>V>5>Z>1>V>6>V>7>V>K>
V>H> – начало.
V>1> – ввести матрицу ДСНФ исходной функции и простые импликанты, полученные в методе Квайна.
V>2> – составить таблицу меток.
V>3> – по таблице меток построить конъюнкцию дизъюнкций, каждая из которых есть совокупность тех импликант, которые в данном столбце имеют метки.
V>4> – произвести раскрытие скобок в полученном выражении с учетом законов поглощения.
V>5> – выбрать одну из полученных конъюнкций и представить ее как совокупность соответсвующих простых импликант.
Z>1> – если выбранная комбинация не является минимальной, то перейти к пункту 6, в противном случае перейти к пункту 8.
V>6> – формировать МДНФ.
V>7> – вывод полученной матрицы.
V>K> – конец.
Граф-схема алгоритма.
V>7>
V>4>
V>3>
V>2>
V>1>
Описание машинных процедур
Procedure FormMatrix;
Данная процедура формирует матрицу меток путем попарного анализа дизъюнктов из ДСНФ и матрицы простых импликант. Если стравнение прошло успешно, то соответствующему элементу матрицы меток присваивается значение 1, в противном случае – значение 0.
Function Pokritie(var S: string16): boolean;
Данная функция проверяет, является ли данная комбинация простых импликант полной, то есть накрывает ли она все дизъюнкты матрицы ДСНФ. Это сравнение происходит следующим образом: вводится новый массив – массив соостветсвия столбцам. Каждому элементу нового массива сначала присваивается значение 0. Далее, пробегая все заданные строки матрицы,определяем в каких столбцах стоит 1 и в новом массиве ставим на соответсвующее место 1. Таким образом, если в векторе есть нули, значит данная комбинация дизъюнктов не накрывает полностью все столбцы матрицы. В этом случае функция возвращает значние False, в противном случае функция возвращает значение True.
Задание 3. Синтез схемы логического устройства.
1. Представление МДНФ в базисе Буля. В базисе Буля используется 3 логические схемы: НЕ, ИЛИ, И. Вот их графическое изображение:
ИЛИ
И
НЕ
X1 X1
__
X X
X1VX2 X1*X2
X2
X2
Для аппаратной реализации минимальной ДНФ нам потребуется 3 ИМС серии К155 : одна ИМС К155ЛН1 (элементы НЕ), одна ИМС К155ЛЛ1 (элементы ИЛИ) и одна ИМС К155ЛИ1 (элементы И). Но в них все элементы не используются. Так в ИМС К155ЛН1 не используются 3 элемента НЕ Это можно использовать в том случае, когда один из элементов выйдет из строя и его нечем будет заменить. Надо будет только перепаять контакты на незадействованный элемент. Всего в базисе Буля используются 11 логических элементов.
2. Представление МДНФ в базисе Шеффера. Для того, чтобы реализовать минимальную ДНФ в базисе Шеффера, необходимо перевести базис Буля в базис Шеффера, в котором используется только один логический элемент: И-НЕ.
Формулы перевода из базиса Буля в базис Шеффера записываются следующим образом:
НЕ: X = X*X ИЛИ: X>1>VX>2> = X>1>*X>1 >* X>2>*X>2>
И: X>1>*X>2> = X>1>*X>2 >* X>1>*X>2>
Минимальная ДНФ выглядит так:
f
(X>1>,
X>2>,
X>3>,
X>4>)
= X>3>X>4>VX>2>X>3>VX>1>X>3>VX>1>X>2>X>4>VX>1>X>2>X>4>;
Переведем ее в базис Шеффера с помощью указанных выше формул.
О
бозначим
A = X>3>X>4>VX>2>X>3>VX>1>X>3>
= X>3>·(
X>4>VX>2>VX>1>)
= X>3>·X>4>·X>4>·X>2>·X>1>=
=
X>3>·X>4>·X>4>·X>2>·X>1>·X>2>·X>1>.
B
= X>1>X>2>X>4>VX>1>X>2>X>4>=
X>1>·(X>2>·X>4>VX>2>·X>4>)
= X>1>·X>1>·X>2>·X>2>·X>4>·X>4>·X>2>·X>4>.
Окончательно
получим Y
= A
· B
.
Отсюда видно, что для реализации минимальной ДНФ в базисе Шеффера требуется 12 элементов И-НЕ. Соответственно для аппаратной реализации нам потребуется 3 интегральные микросхемы К155ЛА3.
3. Представление МДНФ в базисе Пирса. Для того, чтобы реализовать минимальную ДНФ в базисе Пирса, необходимо как и в предыдущем пункте перевести МДНФ из базиса Буля в базис Пирса, в котором используется только один элемент ИЛИ-НЕ.
Формулы перевода записываются следующим образом:
НЕ: X = XVX ИЛИ: X>1>VX>2> = X>1>VX>2 >V X>1>VX>2>
И: X>1>*X>2> = X>1>VX>1 >V X>2>VX>2>
Переведем МДНФ в базис Пирса. Введем обозначения:
A
= X>3>X>4>VX>2>X>3>VX>1>X>3>
= X>3>·X>4>·X>2>·X>3>·X>1>·X>3>
= X>3>VX>4>VX>2>VX>3>VX>1>VX>3>.
B
= X>1>·(X>2>X>4>VX>2>X>4>)
= X>1>·(X>2>·X>4>·X>2>·X>4>)
= X>1>·X>2>VX>4>VX>2>VX>4>
=
=
X>1>VX>2>VX>4>VX>2>VX>4>.
Y = A V B.
Чтобы реализовать каждую отдельную логическую сумму нам потребуется 2 элемента ИЛИ-НЕ, т.е. для 4-х логических сумм, которые составляют функцию, нам потребуется 6 логических элементов.
Всего на реализацию МДНФ в базисе Пирса понадобится 16 логических элементов ИЛИ-НЕ, а для аппаратной реализации 4 ИМС серии К155 (К155ЛЕ1).
Итак, можно подвести итоги: на реализацию МДНФ в различных базисах требуется разное кол-во логических элементов, но целесообразно выбрать тот базис, который будет более универсальным и на реализацию которого потребуется меньшее кол-во логических элементов. В нашем случае это базис Буля (11 логических элементов).
Заключение
В данной курсовой работе были рассмотрены методы минимизации ФАЛ от 4х переменных: методы Квайна, Квайна-Маккласки, карт Карно, неопределенных коэффициентов, а также рассмотрено прямое алгебраическое преобразование. Для двух из них (метода неопределенных коэффициентов и метода Квайна) были разработаны программы. При этом особенно трудно было реализовать процедуры, отвечающие за логические операции. Причем просматривалась следующая закономерность: чем легче был метод для ручного исполнения, тем труднее было написать для него программу. Взять хотя бы метод карт Карно. С его помощью вручную очень легко получить МДНФ, составить таблицу и выбрав правильные прямоугольники. Но если взяться за реализацию этого метода программно, то сразу возникают трудности, особенно при написании процедуры выбора правильных прямоугольников. Это будет очень сложная логическая процедура, кажется, что все просто.
Иначе выглядит метод неопределенных коэффициентов. Для машинной реализации он подходит больше других, так как в нем мы имеем дело с массивами, для работы с которыми не надо особо сложной логики. И конечно ручное исполнение этого метода крайне нерационально, так как приходиться решать систему из 16-ти уравнений. Это для четырех переменных, а для пяти это будет 32 уравнения. Такой метод для ручного исполнения не подходит.
В задаче курсовой работы также входил синтез логической схемы. Полученная схема МДНФ была реализована в трех базисах: Буля, Пирса, Шеффера. Анализ и оценка аппаратурных затрат также приведена в данной записке.
Список литературы
Гаджиев А.А. Методические указания к выполнению курсовой работы по дисциплине “Дискретная математика” для студентов специальности 22.01 (ВМКСиС). Махачкала, 1998 г.
Гаджиев А.А. Методические указания к выполнению лабораторного практикума по дисциплине “Дискретная математика” (часть 2. Математическая логика). Махачкала, 1998 г.
Приложение
Программа для метода Квайна
Uses Crt;
Const
R = 4;
SR = 16;
Type
Diz = string[R];
Var
S :array[1..SR*2] of Diz;
Rez :array[1..SR*2] of Diz;
Flag :array[1..SR*2] of byte;
Y :array[1..SR] of byte;
IndexS : byte;
IndexRez : byte;
i, j, k : byte;
FData : Text;
FRez : Text;
FDSNF : file of Diz;
FSImp : file of Diz;
{Функция формирования дизъюнкта}
Function MakeDiz(Number: byte): Diz;
Var
i : byte;
S : Diz;
C : char;
Begin
S:='';
for i:=0 to R-1 do
begin
C:=chr(((Number shr i) and $01) + 48);
Insert(C, S, 1);
end;
MakeDiz:=S;
End;
{Функция склеивания}
Procedure Stuck(S1, S2: Diz; IndexS1, IndexS2 : byte);
Var
i, k, n: byte;
Begin
k:=0; {кол-во разных}
for i:=1 to R do
if S1[i] <> S2[i] then
begin
k:=k+1;
n:=i;
end;
case k of
0 : begin
Inc(IndexRez);
Rez[IndexRez]:=S1;
Flag[IndexS1]:=1;
Flag[IndexS2]:=1;
end;
1 : if (S1[n]<>'*') and (S2[n]<>'*') then
begin
S1[n]:='*';
Inc(IndexRez);
Rez[IndexRez]:=S1;
Flag[IndexS1]:=1;
Flag[IndexS2]:=1;
end;
end;
End;
{Функция проверки на удаление пустого дизъюнкта}
Function Del(S : Diz): Boolean;
Var
i, k : byte;
Begin
Del:=False;
k:=0;
for i:=1 to R do
if S[i]='*' then
k:=k+1;
if k=R then
Del:=True;
End;
Procedure Clear;
Var
i, j : byte;
Begin
IndexS:=0;
for i:=1 to SR*2 do
begin
Flag[i]:=0;
S[i]:='';
end;
for i:=1 to IndexRez-1 do
if Flag[i]=0 then
for j:=i+1 to IndexRez do
if Rez[i]=Rez[j] then
Flag[j]:=1;
for i:=1 to IndexRez do
if Flag[i]=0 then
begin
Inc(IndexS);
S[IndexS]:=Rez[i];
end;
End;
{Вывод на экран массива Rez}
Procedure PrintRezult(Step: Byte);
Var
i : byte;
Begin
WriteLn('{------------------------------------------------}');
WriteLn(FRez, '{-----------------------------------------}');
if Step=0 then
begin
Write('Исходная ДНФ.');
Write(FRez, 'Исходная ДНФ.');
end
else
begin
Write('Шаг номер :', Step:2, '.');
Write(FRez, 'Шаг номер :', Step:2, '.');
end;
WriteLn(' Количество дизъюнктов :', IndexS:2);
WriteLn(FRez, ' Количество дизъюнктов :', IndexS:2);
for i:=1 to IndexS do
begin
WriteLn(S[i]);
WriteLn(FRez, S[i]);
end;
ReadKey;
End;
{Основная программа}
Begin
ClrScr;
Assign(FDSNF, 'dsnf.dat');
Rewrite(FDSNF);
Assign(FSImp, 'simplimp.dat');
Rewrite(FSImp);
Assign(FRez, 'rezult.dat');
ReWrite(FRez);
{Считать массив Y из файла}
Assign(FData, 'func.dat');
Reset(FData);
for i:=1 to SR do
Read(FData, Y[i]);
Close(FData);
{Получить массив S}
for i:=1 to SR do
S[i]:=MakeDiz(i-1);
{Преоразовать S: оставив только те элементы, для которых Y=1. Результата в Rez}
IndexRez:=0;
for i:=1 to SR do
if Y[i]=1 then
begin
Inc(IndexRez);
Rez[IndexRez]:=S[i];
end;
for i:=1 to SR*2 do
S[i]:=Rez[i];
IndexS:=IndexRez;
for i:=1 to IndexS do
Write(FDSNF, S[i]);
PrintRezult(0);
{склеивание}
for i:=1 to R do
begin
IndexRez:=0;
{------------------------------------------------------------}
for j:=1 to SR*2 do {подготовка массива Flag под склеивание}
Flag[j]:=0;
{------------------------------------------------------------}
for j:=1 to SR*2 do {склеивание}
Rez[j]:='';
for j:=1 to IndexS-1 do
for k:=j+1 to IndexS do
Stuck(S[j], S[k], j, k);
{------------------------------------------------------------}
for j:=1 to IndexS do {копирование несклеившихся компонент}
if Flag[j]=0 then
begin
Inc(IndexRez);
Rez[IndexRez]:=S[j];
end;
{------------------------------------------------------------}
Clear; {удаление одинаковых дизъюнктов}
{------------------------------------------------------------}
PrintRezult(i); {вывод результата на экран}
end;
{Удалить все дизъюнкты вида '****'}
IndexRez:=0;
for i:=1 to IndexS do
if not Del(S[i]) then
begin
Inc(IndexRez);
Rez[IndexRez]:=S[i];
end;
for i:=1 to IndexS do
Write(FSImp, S[i]);
PrintRezult(R+1);
Close(FSImp);
Close(FDSNF);
Close(FRez);
End.
Результаты работы программы (файл rezult.dat).
{----------------------------------------------------------------}
Исходная ДНФ. Количество дизъюнктов : 9
0000
0010
0011
0101
0110
0111
1010
1011
1111
{----------------------------------------------------------------}
Шаг номер : 1. Количество дизъюнктов :11
00*0
001*
0*10
*010
0*11
*011
01*1
011*
*111
101*
1*11
{----------------------------------------------------------------}
Шаг номер : 2. Количество дизъюнктов : 5
0*1*
*01*
**11
00*0
01*1
{----------------------------------------------------------------}
Шаг номер : 3. Количество дизъюнктов : 5
0*1*
*01*
**11
00*0
01*1
{----------------------------------------------------------------}
Шаг номер : 4. Количество дизъюнктов : 5
0*1*
*01*
**11
00*0
01*1
{----------------------------------------------------------------}
Шаг номер : 5. Количество дизъюнктов : 5
0*1*
*01*
**11
00*0
01*1
Программа для метода Петрика.
Uses Crt;
Type
string4 = String[4];
string16 = String[16];
TImpArray = array[1..16] of string4;
Var
DSNF : TImpArray; {ДСНФ}
SimpleImp : TImpArray; {Простые импликанты}
IndexDSNF : Integer;
IndexSImp : Integer;
QM : array[1..16, 1..16] of integer; {матрица покрытия}
S16Min : string16;
Procedure Input;
Var
FData : file of string4;
i : integer;
Begin
{ввод матрицы ДСНФ}
Assign(FData, 'dsnf.dat');
Reset(FData);
i:=0;
while not eof(FData) do
begin
Inc(i);
Read(FData, DSNF[i]);
end;
IndexDSNF:=i;
Close(FData);
{ввод простых импликант}
Assign(FData, 'simplimp.dat');
Reset(FData);
i:=0;
while not eof(FData) do
begin
Inc(i);
Read(FData, SimpleImp[i]);
end;
IndexSImp:=i;
Close(FData);
{конец ввода}
End;
Function Metka(n, m: integer): boolean;
Var
i, S : integer;
Begin
Metka:=False;
S:=0;
for i:=1 to 4 do
if SimpleImp[n, i]='*' then
S:=S+1
else
if SimpleImp[n, i]=DSNF[m, i] then
S:=S+1;
if S=4 then
Metka:=True;
End;
Procedure FormMatrix;
Var
i, j : integer;
Begin
for i:=1 to IndexSImp do
for j:=1 to IndexDSNF do
if Metka(i, j) then
QM[i, j]:=1
else
QM[i, j]:=0;
End;
Procedure PrintMatrix;
Var
i, j: integer;
Begin
TextColor(LIGHTGREEN);
Write(' ');
for i:=1 to IndexDSNF do
Write(DSNF[i]:6);
WriteLn;
for i:=1 to IndexSImp do
begin
TextColor(LIGHTGREEN);
Write(SimpleImp[i]:6);
for j:=1 to IndexDSNF do
case QM[i, j] of
1 : begin TextColor(LIGHTRED); Write(' 1'); end;
0 : begin TextColor(RED); Write(' -'); end;
end;
WriteLn;
end;
End;
Function Bin(N :integer): string16;
Var
i : integer;
S : string16;
Begin
S:='0000000000000000';
i:=0;
while N>0 do
begin
Inc(i);
Insert(Chr((N mod 2)+48), S, i);
N:=N div 2;
end;
Bin:=S;
End;
Function Pokritie(var S: string16): boolean;
Var
V : array[1..16] of integer;
i, j, Sum: integer;
Begin
Pokritie:=False;
for i:=1 to 16 do
V[i]:=0;
for i:=1 to IndexSImp do
if S[i]='1' then
for j:=1 to IndexDSNF do
if QM[i, j]=1 then
V[j]:=1;
Sum:=0;
for i:=1 to IndexDSNF do
if V[i]=1 then
Sum:=Sum+1;
if Sum=IndexDSNF then
Pokritie:=True;
End;
Function Count(S: string16): integer;
Var
i, j, C: integer;
Begin
C:=0;
for i:=1 to IndexSImp do
if S[i]='1' then
for j:=1 to 4 do
if SimpleImp[i, j]<>'*' then
C:=C+1;
Count:=C;
End;
Procedure ActionsPetrik;
Var
i, j, Index : integer;
S16 : string16;
Begin
Index:=(1 shl IndexSImp)-1;
S16Min:='1111111111111111';
for i:=1 to Index do
begin
S16:=Bin(i);
if Pokritie(S16) then
if Count(S16)<Count(S16Min) then
S16Min:=S16;
end;
End;
Procedure PrintRezult;
Var
i : integer;
Begin
WriteLn;
WriteLn;
TextColor(LIGHTGREEN);
WriteLn('Минимальная дизъюнктивная нормальная форма.');
WriteLn;
TextColor(LIGHTRED);
for i:=1 to IndexSImp do
if S16Min[i]='1' then
WriteLn(SimpleImp[i]:8);
End;
Begin
ClrScr;
Input; {ввод данных}
FormMatrix; {формирование матрицы покрытия для ее дальнейшей обработки}
PrintMatrix; {вывод матрицы}
ActionsPetrik; {формирование конъюнкции дизъюнкций
по методу Петрика и выбор минимальной из них}
PrintRezult; {печать МДНФ}
ReadKey;
End.
Результаты работы программы.
0000 0010 0011 0101 0110 0111 1010 1011 1111
0*1* - 1 1 - 1 1 - - -
*01* - 1 1 - - - 1 1 -
**11 - - 1 - - 1 - 1 1
00*0 1 1 - - - - - - -
01*1 - - - 1 - 1 - - -
Минимальная дизъюнктивная нормальная форма.
0*1*
*01*
**11
00*0
01*1