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 Составить таблицу соответствия (истинности) функции.
| № | X1 | X2 | X3 | X4 | F(X1, X2, X3, X4) |
| 0123456789101112131415 | 0000000011111111 | 0000111100001111 | 0011001100110011 | 0101010101010101 | 1011011100110001 |
Матрицу ДСНФ получают путем удаления тех строк, где функция равна нулю. Для нашего случая получим:
| № | X1 | X2 | X3 | X4 |
| 023567101115 | 000000111 | 000111001 | 011011111 | 001101011 |
1.2Перевести логическую функцию от табличной к аналитической форме в виде ДСНФ.
Переведем логическую функцию от табличной к аналитической форме в виде ДСНФ.
F(X1X2X3X4) = X1X2X3X4 V X1X2X3X4 V X1X2X3X4 V X1X2X3X4 V X1X2X3X4
V X1X2X3X4 V X1X2X3X4 V X1X2X3X4 V X1X2X3X4.
1.3 Найти МДНФ различными методами.
1.3.1 Метод эквивалентных преобразований.
В основе метода минимизации булевых функций эквивалентными преобразованиями лежит последовательное использование законов булевой алгебры. Метод эквивалентных преобразований целесообразно использовать лишь для простых функций и для количества логических переменных не более 4-х. При большем числе переменных и сложной функции вероятность ошибок при преобразовании возрастает.
Проведем прямое алгебраическое преобразование, используя закон неполного склеивания.
F(X1X2X3X4) = X1X2X3X4 V X1X2X3X4 V X1X2X3X4 V X1X2X3X4 V X1X2X3X4 V
V X1X2X3X4 V X1X2X3X4 V X1X2X3X4 V X1X2X3X4 =
= (X1X2X3X4 V X1X2X3X4) V (X1X2X3X4 V X1X2X3X4)V(X1X2X3X4 V X1X2X3X4) V
V (X1X2X3X4 V X1X2X3X4) V (X1X2X3X4 V X1X2X3X4)V(X1X2X3X4 V X1X2X3X4) V
V (X1X2X3X4 V X1X2X3X4) V (X1X2X3X4 V X1X2X3X4)V(X1X2X3X4 V X1X2X3X4) V
V (X1X2X3X4 V X1X2X3X4) V (X1X2X3X4 V X1X2X3X4) =
= X1X2X4 V X1X2X3 V X1X3X4 V X2X3X4 V X1X3X4 V X2X3X4 V X1X2X4 V
V X1X2X3V X2X3X4 V X1X2X3 V X1X3X4 =
= (X1X2X3 V X1X2X3 V X1X3X4 V X1X3X4) V X1X2X4 V
V (X1X2X3 V X1X2X3 V X2X3X4 V X2X3X4) V X1X2X4 V
V (X1X3X4 V X1X3X4 V X2X3X4 V X2X3X4) =
= X1X3 V X2X3 V X3X4 V X1X2X4 V X1X2X4.
Дальнейшее преобразование невозможно. Полученную функцию можно немного упростить с помощью вынесения за скобки общих переменных.
1.3.2 Метод Квайна
При минимизации по методу Квайна предполагается, что минимизируемая логическая функция задана в виде ДСНФ. Здесь используется закон неполного склеивания. Минимизация проводится в два этапа: нахождение простых импликант, расстановка меток и определение существенных импликант (Q-матрица).
| ДСНФ, ранг 4 | |||
| 123456789 | 000000100011010101100111101010111111 | ||
| Наборы 3-го ранга | |||
| 1-22-32-52-73-63-84-65-66-97-88-9 | 00*0001*0*10*0100*11*01101*1011**111101*1*11 | 1234567891011 | |
| Наборы 2-го ранга | |||
| 2-82-103-54-65-116-9 | 0*1**01*0*1**01***11**11 | ||
Как видно из таблиц, при получении матрицы второго ранга первый и седьмой наборы третьего ранга не склеились ни с какими другими наборами. Их необходимо занести в конечную матрицу простых импликант. В матрице же второго ранга мы видим, что некоторые наборы одинаковые. Их необходимо вычеркнуть, так как дизъюнкция одинаковых наборов равна этой же дизъюнкции (это следует из закона повторения)
| Простые импликанты | |
| 12345 | 0*1**01***1100*001*1 |
Перенеся все выделенные строки в конечный массив, получим матрицу СДНФ. Алгебраическая запись СДНФ будет выглядеть следующим образом:
F(X1X2X3X4) = X1X3 V X2X3 V X3X4 V X1X2X4 V X1X2X4.
Эта же функция в нашем случае является и минимальной ДНФ.
1.3.3Метод Квайна-Маккласки
В основу данного метода также положен закон неполного склеивания. Только в отличие от метода Квайна здесь производится гораздо меньше сравнений, так как, разбив исходную матрицу на несколько групп, мы сравниваем только те наборы, которые отличаются индексом на 1 или местоположением меток.
Распределим импликанты ДСНФ по индексам.
| ДСНФ | Индекс i | |
| 123456789 | 000000100011010101100111101010111111 | 012223234 |
| Распределенные наборы 4-го ранга | ||||
| i=0 | i=1 | i=2 | i=3 | i=4 |
| 0000 | 0010 | 0011010101101010 | 01111011 | 1111 |
Сравнивая соседние группы и распределяя полученные наборы по положению символа ‘*’ получим:
| Наборы 3-го ранга | |
| 1234567891011 | 00*0001*0*10*0100*11*01101*1011**111101*1*11 |
| Распределенные наборы 3-го ранга | |||
| 1 | 2 | 3 | 4 |
| *010*011*111 | 0*100*111*11 | 00*001*1 | 001*011*101* |
| Распределенные наборы 2-го ранга | ||
| 12 | 14 | 24 |
| **11 | *01* | 0*1* |
Примечание. Во всех выше приведенных таблицах простые импликанты отмечены жирным шрифтом с подчеркиванием.
Анализируя, видим, что СДНФ примет следующий вид:
| Простые импликанты | |
| 12345 | 0*1**01***1100*001*1 |
Или в алгебраической форме:
F(X1X2X3X4) = X1X3 V X2X3 V X3X4 V X1X2X4 V X1X2X4.
1.3.4Метод карт Карно.
Метод карт Карно – это один из графических методов минимизации функции. Эти методы основаны на использовании особенности зрительного восприятия, так как с его помощью можно практически мгновенно распознать те или иные простые конфигурации.
Преимуществами метода карт Карно над другими методами являются:
А) простота отыскания склеивающихся компонент;
Б) простота выполнения самого склеивания;
В) нахождение всех минимальных форм функции.
Построим таблицу метода карт Карно.
| X1X2 | X1X2 | X1X2 | X1X2 | |
| X3X4 | ■ | |||
| X3X4 | ■ | |||
| X3X4 | ■ | ■ | ■ | ■ |
| X3X4 | ■ | ■ | ■ |
Теперь накроем совокупность всех квадратов с метками минимальным количеством правильных прямоугольников. Таких прямоугольников в нашем случае будет 5: три четырехклеточных и два двухклеточных. Этим прямоугольникам соответствуют следующие простые импликанты: