1.3 Минимизация ФАЛ

1.3.1 Метод прямого алгебраического преобразования

Используя закон тавтологии и неполного склеивания имеем:

___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___

f(X₁X₂X₃X₄) = 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

___ ___ ___ ___ ___ ___ ___

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₄ V X₁X₂X₃X₄ =

___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___

=(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₄)V

___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___

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₄ V X₁X₂X₃X₄)V

___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___

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₄ V X₁X₂X₃X₄)V

___ ___ ___ ___ ___ ___ ___

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₄ V X₁X₂X₃X₄)V

___ ___ ___ ___ ___ ___ ___

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₄ V X₁X₂X₃X₄)V

___

V(X₁X₂X₃X₄ V X₁X₂X₃X₄) =

___ ___ ___ ___ ___ ___ ___ ___ ___ ___

= X₁X₂X₄ V X₁X₃X₄ V X₂X₃X₄ V X₁X₃X₄ V X₂X₃X₄ V X₁X₂X₃ V

___ ___ ___ ___ ___ ___

V X₁X₂X₄ V X₁X₂X₄ V X₂X₃X₄ V X₁X₂X₃ V X₂X₃X₄ V X₁X₂X₄ V

___ ___

V X₁X₃X₄ V X₁X₂X₃ V X₁X₃X₄ V X₁X₂X₄ =

___ ___ ___ ___ ___ ___

= (X₁X₂X₄ V X₁X₂X₄ V X₁X₃X₄ V X₁X₃X₄) V

___ ___ ___ ___ ___ ___

V (X₁X₂X₄ V X₁X₂X₄ V X₂X₃X₄ V X₂X₃X₄) V

___ ___ ___ ___ ___ ___

V (X₁X₃X₄ V X₁X₃X₄ V X₂X₃X₄ V X₂X₃X₄) V

___ ___

V (X₁X₃X₄ V X₁X₃X₄ V X₂X₃X₄ V X₂X₃X₄) V

___ ___ ___ ___ ___ ___

V (X₁X₂X₃ V X₁X₂X₃ V X₁X₂X₄ V X₁X₂X₄) V

___ ___

V (X₁X₂X₄ V X₁X₂X₄ V X₂X₃X₄ V X₂X₃X₄) V

___ ___ ___

V (X₁X₂X₄ V X₁X₂X₄ V X₁X₃X₄ V X₁X₃X₄) V X₁X₂X₃ =

___ ___ ___ ___ ___

= X₁X₄ V X₂X₄ V X₃X₄ V X₃X₄ V X₁X₂ V X₂X₄ V X₁X₄ V X₁X₂X₃ =

___ ___

= X₁X₂ V X₄ V X₁X₂X₃.

Дальнейшее упрощение невозможно.

1.3.2 Метод Квайна

При минимизации по методу Квайна предполагается, что исходная функция задана в виде ДСНФ. Функция алгебры логики f₁(X₁X₂…X_n) называется импликантой ФАЛ f₂(X₁X₂…X_n), если на любом наборе переменных, на которых значение f₁ равно единице, значение f₂ также равно единице. Простая импликанта функции - импликанта типа элементарной конъюнкции некоторых переменных, никакая часть которой не является импликантой.

Задача минимизации по методу Квайна состоит из двух этапов:

нахождение простых импликант;

нахождение минимального покрытия.

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

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

 ___ ___

f(X₁X₂X₃X₄) = X₁X₂ V X₄ V X₁X₂X₃.

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

Как видно из таблицы покрыть все столбцы можно только всеми полученными простыми минитермами. Следовательно все они войдут в МДНФ.

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

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

Наборов первого ранга всего один: ***1, таким образом он также является простой импликантой. Следовательно, простых импликант у нас 3:

101*

01**

***1

В алгебраической форме это будет выглядеть так:

___ ___

f(X₁X₂X₃X₄) = X₁X₂ V X₄ V X₁X₂X₃.

Дальнейшие действия аналогична методу Квайна.

1.3.4 Метод карт Карно

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

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

Для полученных прямоугольников получим следующие конъюнкции:

L₁ - X₄

___

L₂ - X₁X₂

___

L₃ - X₁X₂X₃

МДНФ примет следующий вид:

___ ___

f(X₁X₂X₃X₄) = X₁X₂ V X₄ V X₁X₂X₃.

квайн маккласки логический функция

1.3.5 Метод неопределенных коэффициентов

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

1. X₁+X₂+ … + X_n = 0, если все X_i = 0 (i=1…n)

2. X₁+X₂+ … + X_n = 1, если хотя бы один элемент X_i = 1 (i 1…n)

Составим уравнения для данного метода.

= 0

= 1

= 0

= 1

= 1

= 1

= 1

= 1

= 0

= 1

= 1

= 1

= 0

= 1

= 0

= 1

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

= 1

= 1

= 1

= 1

= 1

= 1

= 1

= 1

= 1

= 1

= 1

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

= 1 X₄

___

= 1 X₁X₂

___

= 1 X₁X₂X₃

В итоге получим минимальную ДНФ:

___ ___

f(X₁X₂X₃X₄) = X₁X₂ V X₄ V X₁X₂X₃.

Глава 2. Формализация задачи минимизации ФАЛ

2.1 Задача определения простых импликант по методу Квайна-Маккласки

1. Начало

2. Вычислить вектор-столбец индексов строк матрицы ДСНФ.

3. Расположить строки матрицы ДСНФ по возрастанию их индексов и формировать подматрицы из строк с одинаковыми индексами.

4. Определить путем попарного сравнения каждой строки матрицы с индексом i со всеми строками матрицы с индексом i+1 логически соседние строки.

1, если строки логически соседние,

P =

0, в противном случае.

Если i-я строка матрицы с индексом i логически соседняя со строкой с индексом i +1, то перейти к пункту 5, в противном случае перейти к пункту 6.

5. Пометить “*” символ, по которому строки логически соседние и сформировать новую строку (n-1)-го ранга.

6. Формировать массив простых импликант.

7. Из строк (n-1)-го ранга формировать новые подматрицы по позиции расположения в них “*”.

8. Определить путем попарного сравнения первой строки матрицы с (1+m)-й строкой логически соседние строки в каждой подматрицы

1, если строки логически соседние,

P =

0, в противном случае.

Если строки логически соседние, то перейти к пункту 9, в противном случае перейти к пункту 6.

9. Пометить “*” символ, по которому строки логически соседние и формировать массивы по методу расположения двух меток.

10. Перейти к пункту 8.

11. Конец.

Граф-схема алгоритма метода Квайна-Маккласки

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

_{1 1 2 3 2 3}

V_НV₁ V₂V₃Z₁^V₄vvV₅V₆vZ₂^V₇Z₃^V_K.

V_Н - Начало

V₁ - Ввод матрицы ДСНФ исследуемой ФАЛ.

V₂ - Вычислить вектор столбец индексов строк матрицы ДСНФ.

V₃ - Расположить строки матрицы ДСНФ по возрастанию их индексов и формировать подматрицы из строк с одинаковыми индексами.

V₄ - Пометить “*” символ, по которому строки логически соседние и формировать новую строку из (n-1)-го ранга.

V₅ - формировать массив простых импликант.

V₆ - из строк (n-1)-го ранга формировать новую матрицу по позиции расположения метки.

V₇ - Пометить “*” символ, по которому строки логически соседние, и формировать массивы по месту расположения двух меток.

Z₁- Определить путем попарного сравнения каждой строки матрицы с индексом i со всеми строками матрицы с индексом i+1 логически соседние строки; если i-1 строка матрицы с индексом i логически соседние с 1-й строкой матрицы с индексом i+1, то перейти к V₅, в противном случае к пункту V₆.

Z₂- Определить путем попарного сравнения 1-й строки матрицы с (1+m)-й строкой логически соседние строки в каждой подматрице; если строки логически соседние, то V₉, в противном случае V₆.

Z₃- если нет больше склеивающихся наборов, то вывод результата, в противном случае V₈.

2.2 Задача минимального покрытия по таблице меток в методе Квайна

Схема алгоритма для решения задачи минимального покрытия по таблице меток в методе Квайна

1. Начало.

2. Ввести матрицу ДСНФ исходной функции и простые импликанты, полученные в методе Квайна.

3. Составить таблицу меток.

4. Выбрать комбинацию из простых импликант.

5. Проверить, накрывают ли выбранные импликанты все столбцы таблицы меток. Если не накрывают, то переход к пункту 4.

6. Если данная комбинация не является минимальной, то переход к пункту 4.

7. Формируем минимальную ДНФ по выбранным простым импликантам.

8. Вывод полученной матрицы.

9. Конец.

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

_{1 2 1 2}

V_HV₁V₂V₃V₄ Z₁ Z₂V₅V₆V_K

V_H - начало.

V₁ - ввести матрицу ДСНФ исходной функции и простые импликанты, полученные в методе Квайна.

V₂ - составить таблицу меток.

V₃ - выбрать комбинацию из простых импликант.

V₄ - проверить, накрывают ли выбранные импликанты все столбцы таблицы меток.

Z₁ - выбранные простые импликанты не накрывают всех столцов таблицы меток.

Z₂ - данная комбинация не является минимальной.

V₅ - формировать МДНФ.

V₆ - вывод полученной матрицы.

V_K - конец.

Граф-схема алгоритма

Глава 3. Синтез логической схемы

3.1 Синтез схемы для МДНФ в базисе Буля (И, ИЛИ, НЕ) с использованием двухвходовых логических элементов

В базисе Буля используется 3 логические схемы: НЕ, ИЛИ, И. Вот их графическое изображение:

X1 X1

__

X X X1VX2 X1*X2

X2 X2

Для аппаратной реализации минимальной ДНФ нам потребуется 3 ИМС серии К155 : одна ИМС К155ЛН1 (элементы НЕ), одна ИМС К155ЛЛ1 (элементы ИЛИ) и одна ИМС К155ЛИ1 (элементы И). Всего в базисе Буля используются 7 логических элементов. Схема для МДНФ в базисе Буля приведена в приложении.

3.2 Представление МДНФ в базисах Шеффера и Пирса

Базис Шеффера. Для того, чтобы реализовать минимальную ДНФ в базисе Шеффера, необходимо перевести базис Буля в базис Шеффера, в котором используется только один логический элемент: И-НЕ.

Формулы перевода из базиса Буля в базис Шеффера записываются следующим образом:

НЕ: X = X*X ИЛИ: X₁VX₂ = X₁*X₁ * X₂*X₂

И: X₁*X₂ = X₁*X₂ * X₁*X₂

Минимальная ДНФ выглядит так:

___ ___

f(X₁X₂X₃X₄) = X₁X₂ V X₄ V X₁X₂X₃.

Переведем ее в базис Шеффера с помощью указанных выше формул.

f(X₁X₂X₃X₄) = X₁X₂ V X₄ V X₁X₂X₃ = X₄ · X₁ · X₂ · X₁ · X₃ · X₂ =

= X₄ · X₁ · X₂ · X₁ · X₃ · X₂.

Отсюда видно, что для реализации минимальной ДНФ в базисе Шеффера требуется 10 элементов И-НЕ. Соответственно для аппаратной реализации нам потребуется 3 интегральные микросхемы К155ЛА3.

Базис Пирса. Для того, чтобы реализовать минимальную ДНФ в базисе Пирса, необходимо как и в предыдущем пункте перевести МДНФ из базиса Буля в базис Пирса, в котором используется только один элемент ИЛИ-НЕ.

Формулы перевода записываются следующим образом:

НЕ: X = XVX ИЛИ: X₁VX₂ = X₁VX₂ V X₁VX₂

И: X₁*X₂ = X₁VX₁ V X₂VX₂

Переведем МДНФ в базис Пирса.

f(X₁X₂X₃X₄) = X₁X₂ V X₄ V X₁X₂X₃ = X₄ · X₁ · X₂ · X₁ · X₃ · X₂.

Всего на реализацию МДНФ в базисе Пирса понадобится 11 логических элементов ИЛИ-НЕ, а для аппаратной реализации 3 ИМС серии К155 (К155ЛЕ1).

3.3 Сравнительный анализ аппаратурных затрат

Для проведения сравнительного анализа составим следующую таблицу:

Итак, можно подвести итоги: на реализацию МДНФ в различных базисах требуется разное кол-во логических элементов, но целесообразно выбрать тот базис, который будет более универсальным и на реализацию которого потребуется меньшее кол-во логических элементов. Как видно из этой таблицы наиболее рационально было бы применить для аппаратной реализации базис Буля, так как в нем используется меньше всего микросхем при одно м том количестве корпусов ИМС.

Заключение

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

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

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

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

Список использованной литературы

1. Гаджиев А.А. Методические указания к выполнению курсовой работы по дисциплине “Дискретная математика” для студентов специальности 22.01 (ВМКСиС). Махачкала, 1998 г.

2. Гаджиев А.А. Методические указания к выполнению лабораторного практикума по дисциплине “Дискретная математика” (часть 2. Математическая логика). Махачкала, 1998 г.

3. Савельев А.Я. Прикладная теория цифровых автоматов. Москва. 1987г.

Приложение

Приложение 1. Рабочая программа решения задачи по методу Квайна-Маккласки

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;

IndexM : array[1..SR*2] 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;

{Процедура разбивает импликанты по индексам}

Procedure MakeIndex(F : Integer);

Var

i : Integer;

Function GetIndex(S : Diz; F : Integer): Integer;

Var

tS : Diz;

i, V, Code : Integer;

Begin

if F=0 then

begin

V:=0;

for i:=1 to 4 do

if S[i]='1' then

V:=V+1;

end

else

begin

tS:='';

for i:=1 to 4 do

if S[i]='*' then

tS:=tS+chr(i+48);

Val(tS, V, Code);

end;

GetIndex:=V;

End;

Begin

for i:=1 to IndexS do

IndexM[i]:=GetIndex(S[i], F);

End;

{Вывод на экран массива Rez}

Procedure PrintRezult(Step: Byte);

Var

IM : array[1..SR*2] of byte;

i, j, k, Count : byte;

Num : Integer;

Begin

ClrScr;

MakeIndex(Step);

for i:=1 to SR*2 do

IM[i]:=0;

if Step=0 then

WriteLn('Исходная ДНФ.')

else

WriteLn('Шаг : ', Step:2);

Count:=0; j:=1;

while Count<IndexS do

begin

Num:=1;

while IM[Num]=1 do

Num:=Num+1;

Num:=IndexM[Num];

k:=0;

for i:=1 to IndexS do

begin

GotoXY(j*8, 5+k);

if IndexM[i]=Num then

begin

Write(S[i]);

IM[i]:=1;

Count:=Count+1;

k:=k+1;

end;

end;

j:=j+1;

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-1 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);

Close(FSImp);

Close(FDSNF);

Close(FRez);

End.

Результаты работы программы

Исходная ДНФ.

0001 0011 0111 1111

0100 0101 1011

0110 1101

1001

1010

Шаг : 1

00*1 0*01 *001 010*

01*0 0*11 *011 011*

01*1 1*01 *101 101*

10*1 1*11 *111

11*1

Шаг : 2

0**1 *0*1 **01 01** 101*

1**1 *1*1 **11

Шаг : 3

***1 01** 101*

Шаг : 4

***1 01** 101*

Приложение 2. Рабочая программа решения задачи минимального покрытия по таблице

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(YELLOW);

WriteLn;

Write(' ');

for i:=1 to IndexDSNF do

Write(DSNF[i]:6);

WriteLn;

for i:=1 to IndexSImp do

begin

TextColor(YELLOW);

Write(SimpleImp[i]:6);

for j:=1 to IndexDSNF do

case QM[i, j] of

1 : begin TextColor(GREEN); Write(' #'); end;

0 : begin TextColor(GREEN); 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 Min;

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(YELLOW);

WriteLn(' МДНФ.');

WriteLn;

TextColor(GREEN);

for i:=1 to IndexSImp do

if S16Min[i]='1' then

WriteLn(SimpleImp[i]:8);

End;

Begin

ClrScr;

WriteLn('Нахождение минимального покрытия по таблице меток.');

Input; {ввод данных}

FormMatrix; {формирование матрицы покрытия для ее дальнейшей обработки}

PrintMatrix; {вывод матрицы}

Min; {нахождение минимального покрытия по таблице меток}

PrintRezult; {печать МДНФ}

ReadKey;

End.

Результаты работы программы

Нахождение минимального покрытия по таблице меток.

0001 0011 0100 0101 0110 0111 1001 1010 1011 1101 1111

***1 # # - # - # # - # # #

01** - - # # # # - - - - -

101* - - - - - - - # # - -

МДНФ.

***1

01**

101*

Размещено на Allbest.ru