СКАЧАТЬ F(X₁,X₂,X_3,X₄)=V₁(1,2,4,6,8,9,13,15):  111.zip [199,67 Kb] (cкачиваний: 175)

СКАЧАТЬ  F(X₁,X₂,X_3,X₄)=V₁(1,3,7,9,10,12,14) :  raschetnaya-kvayn.zip [223,93 Kb] (cкачиваний: 157)

2. Расчетная часть 

Задание: Минимизировать логическую функцию: а) методом Квайна;

 б) методом Квайна – Мак-Класки

F(X₁,X₂,X_3,X₄)=V₁(1,2,4,6,8,9,13,15)

Решение: а) Метод Квайна 

Таблица истинности для данной логической функции. 

Таблица №2.1

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

Для выполнения операции склеивания в выражении функции выявляются пары членов вида  и , различающиеся лишь тем, что один из аргументов в одном из членов представлен без инверсии, а в другом – с инверсией. Затем проводится склеивание таких пар членов: , и результаты склеивания w вводятся в выражение функции в качестве дополнительных членов. Далее выполняется операция поглощения. Она основана на равенстве  (член w поглощает член ). При проведении этой операции из логического выражения вычеркиваются все члены, поглощаемые членами, которые введены в результате операции склеивания.

Операции склеивания и поглощения выполняются последовательно до тех пор, пока это возможно.

Таблица №2.2

В таблице №2.2 ранг понизился до 3-х

Составим таблицу №2.3

Таблица №2.3

Дальнейшее проведение операции склеивания и поглощения оказывается невозможным.

Расстановка меток:

Составим таблицу №2.4 используя результаты таблицы №2.3

В строки таблицы №2.4 записываем комбинации 2-го ранга и незаполненные строки. Столбцами здесь являются исходные комбинации. Если в какую-либо начальную комбинацию входят составляющие комбинации любой строки, то на пересечении данной строки и столбца проставляем метку.

Вычеркивание столбцов:

В таблице №2.4 находим тот столбец где получена только одна метка затем по данной метке определяем соответствующие ей строки. Комбинации данной строки участвуют в ответе.

Таблица №2.4

Затем в данной строке находим все метки и вычеркиваем те столбцы в которых расположены метки соответствующие найденной строке. Оформляем таблицу №2.5

Выбор минимального покрытия:

В таблице №2.5 необходимо выбрать такое сочетание меток, которое должно включать метки во всех столбцах. Если получаем несколько вариантов, то необходимо выбрать покрытие с минимальным суммарным числом аргументов.

Так как в таблице №2.4 были вычеркнуты все столбцы, то таблица №2.5 для данной логической функции будет отсутствовать.

В ответе будут участвовать 5 слагаемых, т. к. пятая строка таблицы №2.4 не содержала столбец с одной меткой и не была вычеркнута.

Минимальная дизъюнктивная нормальная форма заданной функции

F(X₁,X₂,X₃,X₄)=

б) Метод Квайна – Мак-Класки. 

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

1. СДНФ функции представляют наборами значений аргументов, на которых функция равна лог.1.

2. Все члены в этой форме СДНФ разбивают на группы по числу единиц, содержащихся в наборах (представленных в двоичной форме).

3. Производят склеивание наборов. Склеиваться могут только наборы соседних групп, различающиеся лишь в одном разряде. Результат склеивания пары наборов содержит на месте разряда с различающимися значениями в наборах символ * и заносится в графу следующего этапа, а пара склеивающихся наборов вычеркивается (при этом вычеркнутые наборы должны использоваться в последующих поисках склеивающихся пар наборов). Так, склеивание пары наборов 0001 и 0101 графы I этапа приводит к набору 0*01, записываемому в графе II этапа.

Результаты склеивания наборов II этапа заносятся в графу III этапа. Сюда перенесены и не вычеркнутые наборы из графы II этапа. Дальнейшее склеивание оказывается невозможным.

Наборы графы последнего этапа изображают простые импликанты функции, т.е. члены сокращенной ДНФ.

ДНФ соответствует логическому выражению, получаемому по правилу; каждый набор соответствует отдельной импликанте; каждому символу в наборе соответствует переменная функции с индексом, совпадающим с номером позиции символа в наборе; если символом является *, то соответствующая переменная в выражении импликанты отсутствует; если символом является 0, то соответствующая переменная в выражении импликанты присутствует с инверсией; при символе 1 переменная записывается без инверсии.

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

Для нахождения СДНФ необходимо из таблицы истинности выбрать лишь те комбинации, которые на выходе дают «1».

Функцию можно записать через наборы, представленные в двоичной форме:

СДНФ:  

2. Все члены в этой форме СДНФ разобьем на группы по числу единиц, содержащихся в наборах (представленных в двоичной форме). Эта разбивка наборов на группы для рассматриваемой функции представлена в графе I этапа табл. №2.5

Таблица №2.5

Получили сокращенную ДНФ функции

или

Переход от сокращенной ДНФ к минимальной ДНФ может производиться с помощью импликантной матрицы, как и в методе Квайна. Различие может состоять лишь в том, что в импликантной матрице члены СДНФ и сокращенной ДНФ удобней представлять соответствующими им двоичными комбинациями. Импликантная матрица приведена в таблице №2.6

Таблица №2.6

В ответе будут участвовать 5 слагаемых, т. к. все столбцы матрицы перекрываются импликантами *001, 0*10, 01*0, 100*, 11*1 и не перекрываются импликантой 1*01.

Из таблицы следует, что минимальная ДНФ функции

Проверка минимизации с помощью программы EWB 

Для этого воспользуемся логическим преобразователем

Записываем в логический преобразователь исходную функцию вида:

F(X₁,X₂,X_3,X₄)=V₁(1,2,4,6,8,9,13,15)

Для преобразования таблицы истинности в логическое выражение в СДНФ необходимо нажать кнопку

Получили СДНФ

Для упрощения исходной функции необходимо нажать на кнопку

Получили упрощенное логическое выражение

Упрощенная схема будет иметь следующий вид

         A        B          C          D

Как видно результат минимизации по методу Квайна, метода Квайна – Мак-Класки и при помощи программы EWB совпадает, что говорит о правильной минимизации исходной функции.