01 1 №1 Методы минимизации НДФ и КНФ (Ответы на все вопросы по теме электроника или типа того)

№1 Методы минимизации НДФ и КНФ Вопрос №1 (Методы минимизации НДФ и КНФ)

1) (или просто АВ обозначает высказывание, которое ис­тинно тогда и только тогда, когда истинны оба первоначальных вы­сказывания. Высказывание называется конъюнкцией (логиче­ским произведением) А и В; читается: «А и В»);

2) AvB обозначает высказывание, которое истинно тогда и только тогда, когда истинно хотя бы одно из первоначальных выска­зываний. Высказывание Av В называется дизъюнкцией (логической суммой) А и В; читается: «A и В»;

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция элементарных конъюнкций.

Конъюнктивной нормальной формой (КНФ) называется конъюнкция элементарных дизъюнкций.

Совершенной дизъюнктивной нормальной формой формулы А (x₁, x₂, … , x_n ), содержащей n различных переменных, называется дизъюнктивная нормальная форма, в которой:

1) нет двух одинаковых слагаемых;

2) ни одно слагаемое не содержит двух одинаковых множите­лей;

3) никакое слагаемое не содержит переменной вместе с ее от­рицанием;

4) в каждом слагаемом содержится в качестве множителя либо переменная x_i либо ее отрицание, где i = 1, 2,..., n.

- ДНФ;

- не является ДНФ.

Совершенной конъюнктивной нормальной формой формулы А (x₁, x₂, … , x_n ), содержащей n различных переменных, называется конъюнктивная нормальная форма, в которой:

1) нет двух одинаковых множителей;

2) ни один множитель не содержит двух одинаковых слагае­мых;

3) никакой множитель не содержит переменной вместе с ее от­рицанием;

4) в каждом множителе содержится в качестве слагаемого либо переменная x_i либо ее отрицание, где i = 1,

2,..., n.

- КНФ;

-не является КНФ.

Дизъюнктивная нормальная форма (ДНФ), (конъюнктивная нормальная форма (КНФ)), логических переменных, называется минимальной, если количество букв, кото­рые она содержит, будет не больше, чем в любой другой. ДНФ (КНФ) той же функции.

Пусть на каком-то наборе аргументов функция f₁ (x_{1 , ...,}х_n) принимает значение a₁ , а функция f₂ (x_{1 , ...,}х_n) — значение а_2. Тогда говорят, что функция f₁ на данном наборе накрывает значение а₂ , а функция f₂ накрывает своим значением а₁.

Каждый минтерм накрывает своим значением «единица» на со­ответствующем наборе единичное значение функции f, а все минтермы, входящие в совершенную дизъюнктивную нормальную форму (СДНФ) функции, накрывают значениями «единица» все единичные функции.

Если некоторая булева функция (фи) равна нулю на тех же набо­рах, на которых равна нулю другая функция f, то говорят, что фун­кция (фи) входит в функцию Функция ф, входящая в данную функцию, называется ее импликантой; собственной частью конъюнкции называется конъюн­кция, полученная из данной конъюнкции путем исключения одного или нескольких сомножителей.

Минтермом называется элементарное произведение, в котором каждая переменная функции входит только один раз, в прямой или инверсной форме.

Простыми импликантами булевой функции называются та­кие элементарные конъюнкции, которые сами входят в данную фун­кцию, но никакая собственная часть этих конъюнкций в эту функцию не входит.

Любая булева функция равна дизъюнкции всех своих простых импликант.

Дизъюнкция всех простых импликант называется сокращенной ДНФ функции. Любая переключательная функция имеет единствен­ную сокращенную ДНФ.

Методы минимизации ДНФ и КНФ:

1. Карты Карно (карты Вейча)

2. Метод Квайна

3. Метод импликантных матриц

1. Метод карты Вейча (Карты К а р н о ).

Карта Вейча (карта Карно) функции п аргументов содержит 2^п клеток (по числу различ­ных наборов) и составлена таким образом, что каждый аргумент представлен в одной половине всех клеток прямой формой, а в дру­гой — инверсной. Пересечению полей, отмеченных какими-либо формами аргументов, соответствует клетка, содержащая их произве­дение. На рис.1 показаны карты Вейча при n = 3, 4 и 5.

Рис 1. Рис 2.

Если исходная форма функции аналитическая, то на соответ­ствующей карте надо определить поле, занимаемое каждым элемен­том аналитической записи функции, и все клетки поля отметить еди­ницами. При этом единица, уже содержащаяся в клетке, сохраняется. После размещения всех элементов аналитической записи функции на карте Вейча отмечаются символами «в» запрещенные наборы, а ос­тавшиеся клетки заполняются нулями.

Правила склеивания с помощью карт

Два набора склеиваются, если они расположены:

в соседних клетках, т.е. в одной строке или в одном столбце;

в противоположных концах одной строки или одного столбца;

в одинаковых местах нескольких карт.

Четыре, восемь наборов склеиваются, если их образуют квад­рат, строку, столбец карты.

Четыре, восемь наборов, склеиваются, если они образуют поле, расположенное по разным концам одинаковых соседних строк или столбцов.

Пример. Найти минимальную дизъюнктивную нормальную функцию для заданного выражения

Занесем заданную функцию в карты Вейча на четыре переменных (рис. 2).

Выполнив операции склеивания и выбрав простые импликанты, получим минимальную форму функции:

2) Метод Квайна

Этот метод используется для получения сокращенной ДНФ функции из СДНФ ее с помощью операций неполного склеивания:

и поглощения A+AB=A.

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

Доказательство теоремы проверять не будем.

Чтобы получить все простые импликанты, так как один и тот же член дизъюнктивной формы может склеиваться с несколькими другими, образуя при этом различные импликанты, после склеивания исходный член следует сохранить.

Алгоритм метода Квайна.

1. Провести все возможные склеивания минтермов, входящих в СДНФ функции. В результате образуются элементарные конъюнкции ранга (n-1).

2. Так как склеиваться могут только элементарные конъюнкции одного ранга, то в дальнейших склеиваниях минтермы не участвуют, поэтому следует выполнить операции поглощения.

3. Над полученными элементарными конъюнкциями ранга (n-1) повторить операции склеивания и поглощения, образовав элементарные конъюнкции нижнего ранга, и т.д.

4. Процесс заканчивается, когда дальнейшее склеивание оказывается невозможным.

5. Оставшиеся в результате поглощения элементарные конъюнкции являются простыми импликантами функции, а дизъюнкция их есть сокращенная ДНФ функции.

Пример. Найти сокращенную ДНФ функции:

СДНФ функции

Приводим алгоритм метода:

Здесь \/ - отметка поглощения.

Сокращенная ДНФ функции:

Пример. Найти сокращенную ДНФ функции:

СДНФ функции

Проводим операции склеивания и поглощения:

Сокращенная ДНФ функции

3). Метод импликантных матриц.

Рассмотрим графический метод отыскания тупиковых форм функции из сокращенной ДНФ.

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

Конституента единицы (нуля) – это элементарная конъюнкция (дизъюнкция), в которую входят все n переменных в прямом или инверсном виде (минтерм).

В таблице по строке каждой импликанты отмечаются те минтермы, которые ею поглощаются.

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

Для случая имеем импликантную матрицу, представленную в табл.18.

В данном случае импликанты AC и являются обязательными. Их сумма покрывает все минтермы, следовательно, тупиковая форма Она единственна и поэтому является минимальной.

Таблица 18.

Пример. Найти минимальную ДНФ функции, используя метод Квайна и метод импликантных матриц:

Сокращенная ДНФ

Импликантная матрица функции дана в табл.19.

Таблица 19

Так как нет столбцов с одной отметкой, то ни одна из импликант не является обязательной. Найдем минимальное количество простых импликант, накрывающее все колонки.

Возможны две тупиковые формы функции:

;

Обе формы содержат одинаковое число букв и, следовательно, обе являются минимальными.

Возможны другие тупиковые формы данной функции, но они не минимальны:

Приложение (Не обязательно)

Выражение функции в СДНФ и СКНФ с помощью аналитических преобразований.

Для получения СДНФ функции аналитическим способом используется следующий прием:

1. аналитическое выражение функции приводится к бесскобочной записи в форме дизъюнкции каких-либо конъюнкций;

2. каждая конъюнкция, имеющая число сомножителей меньше n, умножается на выражение «1» через все недостающие переменные ( );

3. раскрываются скобки и приводятся подобные члены.

Пример. Найти СДНФ функции f(ABCD)= .

m₁₅ + m₁₄ + m₁₃ + m₁₂ + m₁₁ + m₉ + m₈ + m₃ +m₁.

Для получения СКНФ функции без использования табличной записи следует применять процедуру вида:

1. аналитическое выражение функции приводится с помощью соотношения AB+C=(A+C)(B+C) к конъюнктивной записи со скобками, причем в скобках должны стоять дизъюнкции отдельных переменных в прямой или инверсной форме;

2. к каждой дизъюнкции добавляется выражение 0 через все недостающие переменные ( );

3. вновь используется дистрибутивный закон вида и приводятся подобные члены.

Пример. Найти СКНФ функции

=М₁₅ М₁₃ М₁₁ М₁₀ М₉ М₈ М₅

Рассмотрим расширение сокращенной записи элементарного произведения до суммы минтермов.

Пусть , представим данную запись в виде

A B C D

- - 0 1

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

0 0 0 1

0 1 0 1

1 0 0 1

1 1 0 1

Полученные цифры соответствуют индексам минтермов, содержащихся в СДНФ исходной функции, т.е.

f(ABCD)=m₁+m₅+m₉+m_13.

4