Схема алгоритма для метода Квайна

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}

V_HV₁Z₁­V₂¯V₃V₄V_K

V_H – начало.

V₁ – ввести матрицу ДСНФ исходной функции.

V₂ – формировать массив простых импликант, предварительно пометив символом ‘*’ ту переменную, по которой данные строки склеиваются.

V₃ – строку, которая не склеилась ни с одной другой строкой записать в конечный массив.

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

Z₁ – если строки склеиваются, то перейти к пункту 3, в противном случае перейти к пункту 5.

V_K – конец.

 

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

 

 

Описание машинных процедур

Procedure Stuck(S1, S2: Diz; IndexS1, IndexS2: byte);

Данная процедура склеивает два, передаваемых ей дизъюнкта. Дизъюнкты задаются в параметрах S1, S2. Индексы IndexS1, IndexS2 определяют индексы этих дизъюнктов в главном рабочем массиве. Алгоритм работы процедуры следующий: сначала ищется количество склеивающихся символов. Если их 0, то они одинаковые, и в конечный массив записывается только один из них. Если 1, то определяется местоположение символа, по которому данные две дизъюнкции склеиваются, и заменяем этот символ на ‘*’. Все полученные результаты заносятся в массив REZ.

Все остальные функции и процедуры программы связаны с действиями над массивами, то есть не имеют непосредственного отношения к данному методу нахождения МДНФ. Поэтому нет смысла их описывать.

Схема алгоритма для метода Петрика

1. Начало.

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

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

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

5. Произвести раскрытие скобок в полученном выражении с учетом законов поглощения.

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

7. Если выбранная комбинация не является минимальной, то перейти к пункту 6, в противном случае перейти к пункту 8.

8. Формировать МДНФ.

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

10. Конец.

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

                        _{1        1}

V_HV₁V₂V₃V₄¯V₅Z₁­V₆V₇V_K

V_H – начало.

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

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

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

V₄ – произвести раскрытие скобок в полученном выражении с учетом законов поглощения.

V₅ – выбрать одну из полученных конъюнкций и представить ее как совокупность соответсвующих простых импликант.

Z₁ – если выбранная комбинация не является минимальной, то перейти к пункту 6, в противном случае перейти к пункту 8.

V₆ – формировать МДНФ.

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

V_K – конец.