Курсовая работа: Методы минимизации логических функций
f(X1 , X2 , X3 , X4 ) = X3 X4 VX2 X3 VX1 X3 VX1 X2 X4 VX1 X2 X4 ;
Переведем ее в базис Шеффера с помощью указанных выше формул.
 |
 |
 |
ОбозначимA = X3 X4 VX2 X3 VX1 X3 = X3 ·( X4 VX2 VX1 ) = X3 ·X4 ·X4 ·X2 ·X1 =
 | |
 | |
= X3 ·X4 ·X4 ·X2 ·X1 ·X2 ·X1 .
 | |
 | |
 |  |
B = X1 X2 X4 VX1 X2 X4 = X1 ·(X2 ·X4 VX2 ·X4 ) = X1 ·X1 ·X2 ·X2 ·X4 ·X4 ·X2 ·X4 .
 |
Окончательно получим Y = A · B .
Отсюда видно, что для реализации минимальной ДНФ в базисе Шеффера требуется 12 элементов И-НЕ. Соответственно для аппаратной реализации нам потребуется 3 интегральные микросхемы К155ЛА3.
3. Представление МДНФ в базисе Пирса. Для того, чтобы реализовать минимальную ДНФ в базисе Пирса, необходимо как и в предыдущем пункте перевести МДНФ из базиса Буля в базис Пирса, в котором используется только один элемент ИЛИ-НЕ.
Формулы перевода записываются следующим образом:
 | |||||
 |  |  | | ||
НЕ: X = XVXИЛИ: X1 VX2 = X1 VX2 V X1 VX2
 | |||
 | | ||
И: X1 *X2 = X1 VX1 V X2 VX2
Переведем МДНФ в базис Пирса. Введем обозначения:
 | ||||
 | ||||
|  | |||
 | |  | ||
| ||||
A = X3 X4 VX2 X3 VX1 X3 = X3 ·X4 ·X2 ·X3 ·X1 ·X3 = X3 VX4 VX2 VX3 VX1 VX3 .
 | |||||||
 | |||||||
 | |||||||
 | |||||||
 | |||||||
 |  | ||||||
| |||||||
 |  | | |||||
 |  | ||||||
B = X1 ·(X2 X4 VX2 X4 ) = X1 ·(X2 ·X4 ·X2 ·X4 ) = X1 ·X2 VX4 VX2 VX4 =
 | |
 |
= X1 VX2 VX4 VX2 VX4 .
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;