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

1 2 3 4 5

Содержание

Задание 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.

Составить таблицу соответствия (истинности) функции.

Составим таблицу истинности для заданной функции F (X₁,X₂,X₃,X₄).

№	X₁	X₂	X₃	X₄	F(X_1, X_2, X_3, X₄)
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₁	X₂	X₃	X₄
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

Перевести логическую функцию от табличной к аналитической форме в виде ДСНФ.

Переведем логическую функцию от табличной к аналитической форме в виде ДСНФ.

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

Найти МДНФ различными методами.

Метод эквивалентных преобразований.

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

Проведем прямое алгебраическое преобразование, используя закон неполного склеивания.

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₄ =

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

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

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

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

Метод Квайна

При минимизации по методу Квайна предполагается, что минимизируемая логическая функция задана в виде ДСНФ. Здесь используется закон неполного склеивания. Минимизация проводится в два этапа: нахождение простых импликант, расстановка меток и определение существенных импликант (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	*000** 001* 010 010 011 011 *011** 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		01 *01* 01 01 11 11

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

Простые импликанты
1 2 3 4 5	01 01 *11 000 01*1

Перенеся все выделенные строки в конечный массив, получим матрицу СДНФ. Алгебраическая запись СДНФ будет выглядеть следующим образом:

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

Эта же функция в нашем случае является и минимальной ДНФ.

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

В основу данного метода также положен закон неполного склеивания. Только в отличие от метода Квайна здесь производится гораздо меньше сравнений, так как, разбив исходную матрицу на несколько групп, мы сравниваем только те наборы, которые отличаются индексом на 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	000 001 010 010 011 011 011 011 111 101 1*11

Распределенные наборы 3-го ранга
1	2	3	4
010 011 *111	010 011 1*11	000 011	001* 011* 101*

Распределенные наборы 2-го ранга
12	14	24
**11	01	01

Примечание. Во всех выше приведенных таблицах простые импликанты отмечены жирным шрифтом с подчеркиванием.

Анализируя, видим, что СДНФ примет следующий вид:

Простые импликанты
1 2 3 4 5	01 01 *11 000 01*1

Или в алгебраической форме:

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

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

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

Преимуществами метода карт Карно над другими методами являются:

А) простота отыскания склеивающихся компонент;

Б) простота выполнения самого склеивания;

В) нахождение всех минимальных форм функции.

Построим таблицу метода карт Карно.

	X₁X₂	X₁X₂	X₁X₂	X₁X₂
X₃X₄	■
X₃X₄		■
X₃X₄	■	■	■	■
X₃X₄	■	■		■

Теперь накроем совокупность всех квадратов с метками минимальным количеством правильных прямоугольников. Таких прямоугольников в нашем случае будет 5: три четырехклеточных и два двухклеточных. Этим прямоугольникам соответствуют следующие простые импликанты:

для первого – X₃X₄;

для второго – X₁X₃;

для третьего – X₂X₃;

для четвертого – X₁X₂X₄;

для пятого – X₁X₂X₄;

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

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

Сравнивая метод карт Карно с другими методами минимизации функции можно сделать вывод, что первый больше всего подходит для ручного исполнения. Время ручной работы значительно сокращается (за счет наглядного представления склеивающихся импликант). Программная реализация данного метода имеет свои сложности. Так, очень сложно будет реализовать оптимальный выбор правильных прямоугольников, особенно для большого числа аргументов.

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

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

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

Построим матрицу неопределенных коэффициентов для четырех аргументов. В этом случае мы будем иметь систему из 16-ти уравнений.

Система приведена на следующей странице.

Приравняем все коэффициенты 0 в тех строках, которым соответствует 0 в векторе столбце. Затем приравняем 0 соответствующие коэффициенты в других строках. После этих преобразований система примет следующий вид:

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

Запишем теперь конъюнкции, соответствующие коэффициентам, равным единицам. Мы получим минимальную ДНФ.

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

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

Задание 2.

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями: