Файл: Синтез комбинационных устройств канонические формы представления логических функций.doc
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 03.02.2024
Просмотров: 81
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Минимизация логических функций методом квайна
Метод Квайна относится к числу таких методов минимизации функции алгебры логики, которые позволяют представлять функции в ДНФ или КНФ с минимальным числом членов и минимальным числом букв в членах. Этот метод содержит два этапа преобразования выражения функции: на первом этапе осуществляется переход от канонической формы (СДНФ или СКНФ) к так называемой сокращенной форме, на втором этапе—переход от сокращенной формы логического выражения к минимальной форме.
Первый этап (получение сокращенной формы).
Пусть заданная функция f представлена в СДНФ.
Переход к сокращенной форме основан на последовательном применении двух операций: операции склеивания и операции поглощения.
![](https://images.student-it.ru/files/275405/1039652_html_7dba513a978e1ca5.png)
![](https://images.student-it.ru/files/275405/1039652_html_782aa4c80892ffb1.png)
![](https://images.student-it.ru/files/275405/1039652_html_4d0a6cc3f9164886.png)
![](https://images.student-it.ru/files/275405/1039652_html_7fa234774ab1cbd0.png)
Операции склеивания и поглощения проводятся последовательно до тех пор, пока их выполнение оказывается возможным.
Покажем выполнение этих операций применительно к функции, представленной в табл. 3.5.
Записываем СДНФ функции
![]() | (3.12) |
Попарным сравнением членов (каждого из членов со всеми последующими) выявляем склеивающиеся пары членов:
![](https://images.student-it.ru/files/275405/1039652_html_42193cf544677520.png)
![](https://images.student-it.ru/files/275405/1039652_html_89466f208df53f09.png)
![](https://images.student-it.ru/files/275405/1039652_html_efa2258faa054304.png)
![](https://images.student-it.ru/files/275405/1039652_html_1dfeb8b10476342c.png)
![](https://images.student-it.ru/files/275405/1039652_html_85477b617372930d.png)
четвертый и пятый члены (результат склеивания ).
Таблица 3.5 | ||||||||
x1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
x2 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
x3 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
f(x1,x2,x3) | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
Результаты операции склеивания вводим в выражение функции и проводим операцию поглощения ими членов исходного выражения:
![](https://images.student-it.ru/files/275405/1039652_html_42193cf544677520.png)
![](https://images.student-it.ru/files/275405/1039652_html_89466f208df53f09.png)
![](https://images.student-it.ru/files/275405/1039652_html_42193cf544677520.png)
Член поглощает те члены исходного выражения, которые содержат, т. е. первый и четвертый. Эти члены вычеркиваются. Член поглощает второй и третий, а член x1? x3 – пятый член исходного выражения.
Повторяем операции склеивания и поглощения:
![](https://images.student-it.ru/files/275405/1039652_html_4a297f18f8657adc.png)
![](/images/files/275405/1039652_html_89466f208df53f09.png)
Член операции склеивания
![](/images/files/275405/1039652_html_1dfeb8b10476342c.png)
![](https://images.student-it.ru/files/275405/1039652_html_2b12f852ea68875f.png)
Дальнейшее проведение операций склеивания и поглощения оказывается невозможным, сокращенная форма выражения заданной функции (в данном примере она совпадает с минимальной формой)
![]() | (3.13) |
![](/images/files/275405/1039652_html_42193cf544677520.png)
Как видим, получено выражение существенно более простое по сравнению с СДНФ функции.
На рис. 3.27 приведена структурная схема логического устройства в базисе И, ИЛИ, НЕ, построенная с использованием выражения (3.13).
Второй этап (получение минимальной формы).
Сокращенная форма может содержать лишние члены, исключение которых из выражения функции не повлияет на значение функции.
Таким образом, дальнейшее упрощение логического выражения достигается исключением из выражения лишних членов. В этом и заключается содержание второго этапа минимизации. Покажем этот этап минимизации логического выражения на примере построения логического устройства для функции в табл. 3.6.
![](https://images.student-it.ru/files/275405/1039652_html_3071a442bc4f407f.png)
рис 3.27
Таблица 3.6 | ||||||||||||||||
![]() | 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 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
Совершенная ДНФ.данной функции
![]() | (3.14) |
Для получения сокращенной формы проводим операции склеивания и поглощения
Полученное выражение представляет собой сокращенную форму логического выражения заданной функции, а члены его — простые импликанты функции. Переход от сокращенной формы к минимальной осуществляется с помощью импликантной матрицы, приведенной в табл. 3.7.
В столбцы импликантной матрицы вписываются члены СДНФ заданной функции, в строки — простые импликанты функции, т. е. члены сокращенной формы логического выражения функции.
Таблица 3.7 | ||||||
Простые импликанты | Члены СДНФ | |||||
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | |
![]() | X | X | | | | |
X | | X | | | | |
| | X | X | | | |
| | | X | X | | |
| | | | X | X |
![](https://images.student-it.ru/files/275405/1039652_html_652992acaff3d0e4.png)
![](https://images.student-it.ru/files/275405/1039652_html_bcaeb9fa8335b83a.png)
![](https://images.student-it.ru/files/275405/1039652_html_8f202b809f1ef084.png)
![](https://images.student-it.ru/files/275405/1039652_html_8f202b809f1ef084.png)
![](https://images.student-it.ru/files/275405/1039652_html_4439101ca5f88ff4.png)
![](https://images.student-it.ru/files/275405/1039652_html_a5b5623ec3dd8ab9.png)
![]() | (3.16) |