20.Формула д.Моргана и переход к инвертируемым базисам.

Для работы в инвертируемых логических базисах таких как И-НЕ, ИЛИ-НЕ удобными являются формулы Д.Моргана.

формулы Д.Моргана применимы при любом числе аргументов. Пользуясь ими можно легко переводить логические схемы из булевого базиса в котором человеку более привычнее мыслить в инверт-е базисы И-НЕ или ИЛИ-НЕ которые эффективнее всего реализуются интегральной технологией. Для примера рассмотрим логическую функцию в виде дизъюнктивной нормальной формы.

У=

Проинвертируем дважды правую часть рассматриваемого выражения:

У=

Проведем преобразование правой части исп-я формулы Моргана у=

По полученному выражению построим логическую схему элементов И-НЕ:

21.Минимизация логической функции методом Квайна-Маккласки

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

X1	X2	X3	X4	Y
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	0 1 0 0 0 1 0 0 0 1 1 1 0 1 0 0

У=

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

Номера групп	1 стадия	2 стадия	3 стадия
0	-	-	-
1	0001	0*01 *001	**01
2	0101 1001 1010	*101 10*1 1*01 101*	10*1 101*
3	1011 1101	-	-

Далее производят склеивание наборов. Склеиваются только наборы соседних групп различающихся лишь в одном разряде.

Результат склеивания содержит на месте разряда с различающимся значением символ * и заносится в столбец следующей стадии. А пара склеивающихся наборов вычеркивается, при этом вычеркнутые наборы должны вычеркиваться в последующих поисках совпадающих пар наборов.

Выделим склеивающие пары линиями. Результаты склеивания наборов первой стадии запишем во второй столбец.

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

Для данного примера сокращенная форма имеет вид:

У=

У=

Переход от сокращенной формы к минимальной производится с помощью импликантной матрицы.

Простые импликанты	0001	0101	1001	1010	1011	1101
**01	*	*	*			*
10*1			*		*
101*				*	*

Из данной таблицы следует, что минимальная функция имеет вид:

У_мин=