СодержаниеЗадание1.Определить МДНФ логической функцииустройства.
1.1 Составить таблицусоответствия (истинности) функции.
1.2 Перевестилогическую функцию от табличной к аналитической форме в виде ДСНФ
1.3 Найти МДНФразличными методами.
1.3.1прямым (алгебраическим) преобразованием;
1.3.2методом Квайна;
1.3.3усовершенствованным методом Квайна (Квайна-Маккласки);
1.3.4методом карт Карно;
1.3.5методом неопределенных коэффициентов;
Задание 2. Составить алгоритм метода минимизации
2.1 Составить содержательный (словесный) алгоритм минимизациифункции, разработать граф-схему алгоритма, разработать логическую схемуалгоритма в нотации Ляпунова для метода Квайна.
2.2 Составить содержательный (словесный) алгоритм минимизациифункции, разработать граф-схему алгоритма, разработать логическую схемуалгоритма в нотации Ляпунова для метода минимального покрытия Петрика.
2.3 Разработать рабочие программы по алгоритмам.
Задание 3. Синтез схемы логического устройства.
3.1 Выполнить синтез схемы по ДСНФ и МДНФ в базисе Буля сиспользованием двухвходовых логических элементов и интегральных микросхем серии155.
3.2 Функцию МДНФ в базисе Буля полученную в первом заданиипредставить в базисах Шеффера и Пирса.
3.3 Обосновать выборбазиса по формулам МДНФ.
3.4 Реализовать в выбранном базисе логическую схему.
Задание 1.
1.1 Составить таблицу соответствия (истинности) функции.Составимтаблицу истинности для заданной функцииF(X1,X2,X3,X4).
№
X1
X2
X3
X4
F(X1, X2, X3, X4)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
МатрицуДСНФ получают путем удаления тех строк, где функция равна нулю. Для нашегослучая получим:№
X1 X2
X3
X4
2
3
5
6
7
10
11
15
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1.2 Перевести логическую функцию от табличной каналитической форме в виде ДСНФ.
Переведем логическую функцию от табличнойк аналитической форме в виде ДСНФ.
F(X1X2X3X4)= X1X2X3X4 V X1X2X3X4V X1X2X3X4 V X1X2X3X4V X1X2X3X4
V X1X2X3X4V X1X2X3X4 V X1X2X3X4V X1X2X3X4.
1.3 Найти МДНФ различными методами.
1.3.1 Метод эквивалентных преобразований.
Воснове метода минимизации булевых функций эквивалентными преобразованиями лежитпоследовательное использование законов булевой алгебры. Метод эквивалентныхпреобразований целесообразно использовать лишь для простых функций и дляколичества логических переменных не более 4-х. При большем числе переменных исложной функции вероятность ошибок при преобразовании возрастает.
Проведем прямое алгебраическое преобразование, используя закон неполногосклеивания.
F(X1X2X3X4)= X1X2X3X4 V X1X2X3X4V X1X2X3X4 V X1X2X3X4V X1X2X3X4 V
V X1X2X3X4V X1X2X3X4 V X1X2X3X4V X1X2X3X4 =
= (X1X2X3X4V X1X2X3X4) V (X1X2X3X4V X1X2X3X4)V(X1X2X3X4V X1X2X3X4) V
V (X1X2X3X4V X1X2X3X4) V (X1X2X3X4V X1X2X3X4)V(X1X2X3X4V X1X2X3X4) V
V (X1X2X3X4 V X1X2X3X4)V (X1X2X3X4 V X1X2X3X4)V(X1X2X3X4V X1X2X3X4) V
V (X1X2X3X4 V X1X2X3X4)V (X1X2X3X4 V X1X2X3X4)=
= X1X2X4 V X1X2X3V X1X3X4 V X2X3X4V X1X3X4 V X2X3X4V X1X2X4 V
V X1X2X3V X2X3X4V X1X2X3 V X1X3X4 =
= (X1X2X3 V X1X2X3V X1X3X4 V X1X3X4)V X1X2X4 V
V (X1X2X3 V X1X2X3V X2X3X4 V X2X3X4)V X1X2X4 V
V (X1X3X4 V X1X3X4V X2X3X4 V X2X3X4)=
= X1X3 VX2X3 V X3X4 V X1X2X4V X1X2X4.
Дальнейшее преобразование невозможно.Полученную функцию можно немного упростить с помощью вынесения за скобки общихпеременных.
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(X1X2X3X4)= X1X3 V X2X3 V X3X4V X1X2X4 V X1X2X4.
Эта же функция в нашем случае является иминимальной ДНФ.
1.3.3 Метод Квайна-Маккласки
В основу данного метода также положензакон неполного склеивания. Только в отличие от метода Квайна здесьпроизводится гораздо меньше сравнений, так как, разбив исходную матрицу на несколькогрупп, мы сравниваем только те наборы, которые отличаются индексом на 1 илиместоположением меток.
Распределим импликанты ДСНФ по индексам.
ДСНФ
Индекс i
1
2
3
4
5
6
7
8
9
0000
0010
0011
0101
0110
0111
1010
1011
1111
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(X1X2X3X4)= X1X3 V X2X3 V X3X4V X1X2X4 V X1X2X4.
1.3.4 Метод карт Карно.
Метод карт Карно – это один изграфических методов минимизации функции. Эти методы основаны на использованииособенности зрительного восприятия, так как с его помощью можно практическимгновенно распознать те или иные простые конфигурации.
Преимуществами метода карт Карно наддругими методами являются:
А) простота отыскания склеивающихсякомпонент;
Б) простота выполнения самого склеивания;
В) нахождение всех минимальных формфункции.
Построим таблицу метода карт Карно.
X1X2
X1X2
X1X2
X1X2
X3X4
■
X3X4
■
X3X4
■
■
■
■
X3X4
■
■
■
Теперь накроем совокупность всехквадратов с метками минимальным количеством правильных прямоугольников. Такихпрямоугольников в нашем случае будет 5: три четырехклеточных и двадвухклеточных. Этим прямоугольникам соответствуют следующие простые импликанты:
для первого – X3X4;
для второго – X1X3;
для третьего – X2X3;
для четвертого – X1X2X4;
для пятого – X1X2X4;
Минимальная ДНФ будет выглядеть так:
F(X1X2X3X4)= X1X3 V X2X3 V X3X4V X1X2X4 V X1X2X4.
Сравнивая метод карт Карно с другимиметодами минимизации функции можно сделать вывод, что первый больше всегоподходит для ручного исполнения. Время ручной работы значительно сокращается(за счет наглядного представления склеивающихся импликант). Программнаяреализация данного метода имеет свои сложности. Так, очень сложно будетреализовать оптимальный выбор правильных прямоугольников, особенно для большогочисла аргументов.
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 /> V/>V/> = 1
/> V /> V/>V/> = 1
Теперь в каждой строке необходимо выбратькоэффициент минимального ранга и приравнять его единице, а остальныекоэффициенты – 0. После этого вычеркиваем одинаковые строки, оставляя при этомодну из них (те строки, у которых все коэффициенты равны 0, такжевычеркиваются).
/> = 1
/>= 1
/>= 1
/>= 1
/>= 1
Запишем теперь конъюнкции,соответствующие коэффициентам, равным единицам. Мы получим минимальную ДНФ.
F(X1X2X3X4)= X1X3 V X2X3 V X3X4V X1X2X4 V X1X2X4.
Итак, мы получили несколькими способамиминимальную ДНФ, Во всех случаях она получилась одинаковой, то есть любой изописанных методов может быть использован для минимизации функции. Однако этиметоды существенно отличаются друг от друга как по принципу нахождения МДНФ,так и по времени исполнения. Для ручных расчетов очень удобен метод карт Карно.Он нагляден, не требует рутинных операций, а выбрать оптимальное расположение правильныхпрямоугольников не составляет большого труда. В то время как машиннаяреализация данного метода осложняется необходимостью нахождения оптимальногорасположения прямоугольников. Естественно применение других методов (методКвайна, метод Квайна-Маккласки, метод неопределенных коэффициентов) для ручныхрасчетов нецелесообразно. Они больше подойдут для машинной реализации, так каксодержат большое число повторяющихся простых операций.
Задание 2.
2.1 Схема алгоритма для метода Квайна
1. Начало.
2. Ввести матрицуДСНФ исходной функции.
3. Проверить насклеиваемость i-ю (i=1,m-1:где m – количество строк в ДСНФ) и j-ую (j=i+1, m) строки. Если строки склеиваются, топерейти к пункту 6, в противном случае перейти к пункту 5.
4. Формироватьмассив простых импликант, предварительно пометив символом ‘*’ ту переменную, покоторой данные строки склеиваются.
5. Перейти к пункту2.
6. Строку, котораяне склеилась ни с одной другой строкой записать в конечный массив.
7. Перейти к пункту2.
8. Вывод полученнойматрицы.
9. Конец.
Логическая схема алгоритма в нотации Ляпунова
1 1
VHV1Z1V2¯V3V4VK
VH – начало.
V1 – ввести матрицу ДСНФ исходнойфункции.
V2 – формировать массив простыхимпликант, предварительно пометив символом ‘*’ ту переменную, по которой данныестроки склеиваются.
V3 – строку, которая не склеилась ни содной другой строкой записать в конечный массив.
V4 – вывод полученной матрицы.
Z1 – если строки склеиваются, топерейти к пункту 3, в противном случае перейти к пункту 5.
VK – конец.
Граф-схема алгоритма.
/>
Описаниемашинныхпроцедур
Procedure Stuck(S1, S2: Diz; IndexS1, IndexS2: byte);
Данная процедура склеивает два, передаваемых ей дизъюнкта. Дизъюнктызадаются в параметрах S1, S2. Индексы IndexS1, IndexS2определяют индексы этих дизъюнктов в главном рабочем массиве. Алгоритм работыпроцедуры следующий: сначала ищется количество склеивающихся символов. Если их0, то они одинаковые, и в конечный массив записывается только один из них. Если1, то определяется местоположение символа, по которому данные две дизъюнкциисклеиваются, и заменяем этот символ на ‘*’. Все полученные результаты заносятсяв массив REZ.
Все остальные функции и процедуры программы связаны с действиями надмассивами, то есть не имеют непосредственного отношения к данному методунахождения МДНФ. Поэтому нет смысла их описывать.
2.2 Схема алгоритма для метода Петрика
1. Начало.
2. Ввести матрицуДСНФ исходной функции и простые импликанты, полученные в методе Квайна.
3. Составить таблицуметок.
4. По таблице метокпостроить конъюнкцию дизъюнкций, каждая из которых есть совокупность техимпликант, которые в данном столбце имеют метки.
5. Произвестираскрытие скобок в полученном выражении с учетом законов поглощения.
6. Выбрать одну изполученных конъюнкций и представить ее как совокупность соответсвующих простыхимпликант.
7. Если выбраннаякомбинация не является минимальной, то перейти к пункту 6, в противном случаеперейти к пункту 8.
8. Формировать МДНФ.
9. Вывод полученнойматрицы.
10. Конец.
Логическая схема алгоритма в нотации Ляпунова.
1 1
VHV1V2V3V4¯V5Z1V6V7VK
VH – начало.
V1 – ввести матрицу ДСНФ исходнойфункции и простые импликанты, полученные в методе Квайна.
V2 – составить таблицу меток.
V3 – по таблице меток построитьконъюнкцию дизъюнкций, каждая из которых есть совокупность тех импликант,которые в данном столбце имеют метки.
V4 – произвести раскрытие скобок вполученном выражении с учетом законов поглощения.
V5 – выбрать одну из полученныхконъюнкций и представить ее как совокупность соответсвующих простых импликант.
Z1 – если выбранная комбинация неявляется минимальной, то перейти к пункту 6, в противном случае перейти кпункту 8.
V6 – формировать МДНФ.
V7 – вывод полученной матрицы.
VK – конец.
Граф-схема алгоритма./> /> /> /> /> /> /> /> />
Описание машинных процедур
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 ИЛИ: X1VX2 = X1*X1* X2*X2/> /> /> /> /> /> /> /> /> />
И: X1*X2 = X1*X2 * X1*X2
Минимальная ДНФ выглядит так:
/>/>/>/>/>/>f(X1, X2, X3,X4) = X3X4VX2X3VX1X3VX1X2X4VX1X2X4;
Переведем ее в базис Шеффера с помощью указанных выше формул./> /> /> /> /> /> /> /> /> /> /> /> />
/>/>/>/>/>Обозначим A = X3X4VX2X3VX1X3= X3·( X4VX2VX1) = X3·X4·X4·X2·X1=/> /> /> /> /> /> /> />
/>/>/>= X3·X4·X4·X2·X1·X2·X1./> /> /> /> /> /> /> /> /> /> /> /> /> /> />
/>/>/>/>/>/>/>/>/>/>/>B = X1X2X4VX1X2X4=X1·(X2·X4VX2·X4) = X1·X1·X2·X2·X4·X4·X2·X4.
/>
/>/>Окончательно получим Y = A · B .
Отсюда видно, что для реализации минимальной ДНФ в базисе Шеффера требуется12 элементов И-НЕ. Соответственно для аппаратной реализации нам потребуется 3интегральные микросхемы К155ЛА3.
3. Представление МДНФ в базисе Пирса. Для того, чтобы реализовать минимальнуюДНФ в базисе Пирса, необходимо как и в предыдущем пункте перевести МДНФ избазиса Буля в базис Пирса, в котором используется только один элемент ИЛИ-НЕ.
Формулы перевода записываются следующим образом:/> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> />
НЕ: X = XVX ИЛИ: X1VX2 = X1VX2 V X1VX2/> /> /> /> /> /> /> /> /> /> />
И: X1*X2 = X1VX1 V X2VX2
Переведем МДНФ в базис Пирса. Введем обозначения:/> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> />
/>/>/>/>/>/>/>A = X3X4VX2X3VX1X3 = X3·X4·X2·X3·X1·X3 = X3VX4VX2VX3VX1VX3./> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> />
/>/>/>/>B = X1·(X2X4VX2X4)= X1·(X2·X4·X2·X4) = X1·X2VX4VX2VX4=/> /> /> /> /> /> /> /> />
/>/>/>/>= X1VX2VX4VX2VX4.
Y = A V B.
Чтобы реализовать каждую отдельную логическую сумму нам потребуется 2 элементаИЛИ-НЕ, т.е. для 4-х логических сумм, которые составляют функцию, нампотребуется 6 логических элементов.
Всего на реализацию МДНФ в базисе Пирса понадобится 16 логическихэлементов ИЛИ-НЕ, а для аппаратной реализации 4 ИМС серии К155 (К155ЛЕ1).
Итак, можно подвести итоги: на реализацию МДНФ в различных базисахтребуется разное кол-во логических элементов, но целесообразно выбрать тотбазис, который будет более универсальным и на реализацию которого потребуетсяменьшее кол-во логических элементов. В нашем случае это базис Буля (11логических элементов).
Заключение
В данной курсовой работе были рассмотрены методы минимизации ФАЛ от 4хпеременных: методы Квайна, Квайна-Маккласки, карт Карно, неопределенныхкоэффициентов, а также рассмотрено прямое алгебраическое преобразование. Длядвух из них (метода неопределенных коэффициентов и метода Квайна) былиразработаны программы. При этом особенно трудно было реализовать процедуры,отвечающие за логические операции. Причем просматривалась следующаязакономерность: чем легче был метод для ручного исполнения, тем труднее былонаписать для него программу. Взять хотя бы метод карт Карно. С его помощьювручную очень легко получить МДНФ, составить таблицу и выбрав правильные прямоугольники.Но если взяться за реализацию этого метода программно, то сразу возникаюттрудности, особенно при написании процедуры выбора правильных прямоугольников.Это будет очень сложная логическая процедура, кажется, что все просто.
Иначе выглядит метод неопределенных коэффициентов. Для машиннойреализации он подходит больше других, так как в нем мы имеем дело с массивами,для работы с которыми не надо особо сложной логики. И конечно ручное исполнениеэтого метода крайне нерационально, так как приходиться решать систему из 16-тиуравнений. Это для четырех переменных, а для пяти это будет 32 уравнения. Такойметод для ручного исполнения не подходит.
В задаче курсовой работы также входил синтез логической схемы. Полученнаясхема МДНФ была реализована в трех базисах: Буля, Пирса, Шеффера. Анализ иоценка аппаратурных затрат также приведена в данной записке.
Список литературы
1. Гаджиев А.А. Методические указания к выполнению курсовой работы подисциплине “Дискретная математика” для студентов специальности 22.01 (ВМКСиС).Махачкала, 1998 г.
2. Гаджиев А.А. Методические указания к выполнению лабораторного практикумапо дисциплине “Дискретная математика” (часть 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] ofDiz;
Flag :array[1..SR*2]of byte;
Y :array[1..SR] ofbyte;
IndexS: byte;
IndexRez: byte;
i, j, k: byte;
FData: Text;
FRez: Text;
FDSNF: file of Diz;
FSImp: file of Diz;
{Функцияформированиядизъюнкта}
FunctionMakeDiz(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; {кол-во разных}
fori:=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;
{Функцияпроверки на удаление пустого дизъюнкта}
FunctionDel(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-1do
if Flag[i]=0 then
for j:=i+1 to IndexRezdo
if Rez[i]=Rez[j] then
Flag[j]:=1;
for i:=1 to IndexRezdo
if Flag[i]=0 then
begin
Inc(IndexS);
S[IndexS]:=Rez[i];
end;
End;
{Вывод на экран массива Rez}
ProcedurePrintRezult(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);
fori:=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}
fori:=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-1do
for k:=j+1 to IndexSdo
Stuck(S[j], S[k], j,k);
{------------------------------------------------------------}
for j:=1 to IndexS do {копированиенесклеившихся компонент}
ifFlag[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 ofstring4;
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 IndexSImpdo
for j:=1 to IndexDSNFdo
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 IndexDSNFdo
Write(DSNF[i]:6);
WriteLn;
for i:=1 to IndexSImpdo
begin
TextColor(LIGHTGREEN);
Write(SimpleImp[i]:6);
for j:=1 to IndexDSNFdo
case QM[i, j] of
1: beginTextColor(LIGHTRED); Write(' 1'); end;
0: beginTextColor(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 mod2)+48), S, i);
N:=N div 2;
end;
Bin:=S;
End;
Function Pokritie(varS: string16): boolean;
Var
V: array[1..16] ofinteger;
i, j, Sum: integer;
Begin
Pokritie:=False;
for i:=1 to 16 do
V[i]:=0;
for i:=1 to IndexSImpdo
if S[i]='1' then
for j:=1 to IndexDSNFdo
if QM[i, j]=1 then
V[j]:=1;
Sum:=0;
for i:=1 to IndexDSNFdo
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 IndexSImpdo
if S[i]='1' then
for j:=1 to 4 do
if SimpleImp[i,j]'*' then
C:=C+1;
Count:=C;
End;
ProcedureActionsPetrik;
Var
i, j, Index: integer;
S16: string16;
Begin
Index:=(1 shlIndexSImp)-1;
S16Min:='1111111111111111';
for i:=1 to Index do
begin
S16:=Bin(i);
if Pokritie(S16) then
ifCount(S16)
S16Min:=S16;
end;
End;
Procedure PrintRezult;
Var
i: integer;
Begin
WriteLn;
WriteLn;
TextColor(LIGHTGREEN);
WriteLn('Минимальнаядизъюнктивнаянормальнаяформа.');
WriteLn;
TextColor(LIGHTRED);
for i:=1 to IndexSImpdo
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 10101011 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