Построение дискретного преобразователя, на основе дизъюнктора, конъюнктора и инвертора, реализуемого проводимость z=f(x1, x2, x3, x4)

Будем говорить, что набор (α₁,….,α_n)ϵZ₂ⁿ не превосходит (β₁,…..,β_n) ϵZ₂ⁿ:

                      (α₁,….,α_n) (β₁,…..,β_n)

                                 если 

Функция f(x₁,……, x_n)называется монотонной, если для любых наборов (α₁,….,α_n), (β₁,…..,β_n) таких, что (α₁,….,α_n) (β₁,…..,β_n) выполнено условие f(α₁,….,α_n) ≤ f(β₁,…..,β_n)

 

5. Класс L линейных функций:

Линейной будем называть функцию, полином Жегалкина которой имеет степень не больше единицы, то есть функцию вида:

f(x₁,……, x_n) = a_nx_n + a_n-1x_n-1 +…+ax + a₀

Теорема: Критерий полноты:

Ɓ полная система тогда и только тогда, когда Ɓ не содержится целиком ни в одном из следующих классов: T₀, T₁, S, M, L.

В соответствии с этими  определениями выясним класс  принадлежности функции f(x₁, x₂, x₃, x₄). Для этого составим таблицу следующего вида:

Таблица 3: Принадлежность к классам f(x₁, x₂, x₃, x₄):

	T0	T1	S	M	L
f(x1,x2,x3,x4)	─	─	─	─	─

 

Как видно из таблицы 2:

1. f(0, 0, 0 ,0)=1 f(x₁, x₂, x₃, x₄) T₀

2. f(1, 1, 1, 1)=0 f(x₁, x₂, x₃, x₄) T₁

3. f(x₁, x₂, x₃, x₄) (g(x₁, x₂, x₃, x₄))* f(x₁, x₂, x₃, x₄) S

4. Пусть ( )=(0, 0, 0, 0) и =(1, 1, 1, 1), так что ( ) , тогда f(0, 0, 0 ,0) = 1 (1, 1, 1, 1) = 0 f(x₁, x₂, x₃, x₄) М, то есть функция f(x₁, x₂, x₃, x₄) немонотонная

5. Из вида полинома Жегалкина следует, что функция f(x₁, x₂, x₃, x₄) не линейная, следовательно f(x₁, x₂, x₃, x₄) L

 

Вывод: Система, состоящая из функции f(x₁, x₂, x₃, x₄), является полной в соответствии с критерием полноты системы.

 

7. Сокращенная ДНФ, ДНФ Квайна, ДНФ типа ∑Т, минимальная ДНФ и минимальная КНФ.

 

Сокращенной ДНФ функции f  называется ДНФ, состоящая из всех простых импликант.

Простой импликантой называется элементарная конъюнкция, соответствующая максимальной грани.

Пусть f булева функция, тождественно неравная единицы, тогда грань N называется максимальной, если:

1. N N_f
2. не существует такой грани Nˈ такой, что N Nˈ N_f и размерность грани Nˈ больше размерности грани N

 

Алгоритм  нахождения сокращенной ДНФ:

Пусть f – булева функция, не равная тождественно нулю, для которой нужно найти сокращенную ДНФ:

1. Пусть f 1, то сокращенная ДНФ также равна 1.
2. Если , то для нее записывается совершенная КНФ.
3. Используя законы дистрибутивности, раскрываем скобки в СКНФ; после чего удаляются заведомо нулевые конъюнкции, а из повторяющихся конъюнкций оставляют только одну.
4. К оставшимся конъюнкциям применяют, если возможно, закон поглощения, состоящий в следующем: если K₁ ˅K₁K₂=K₁

5. После выполнения всех этих действий будет получена сокращенная ДНФ.

 

СКНФ:

Последовательно раскроем скобки, применяя сразу закон поглощения, удаляя нулевые конъюнкции, и из повторяющихся оставляем только одну:

Получили сокращенную дизъюнктивную  нормальную форму:

f(x₁, x₂, x₃, x₄)

 Найдем сокращенную ДНФ графическим путем с помощью графа:

Четырехмерный двоичный куб для данной функции:

 

Рисунок 1. Четырехмерный  двоичный куб

            

Выделим теперь максимальные грани. Получаем следующий набор максимальных граней:

Таблица 4: Наборы (x₁, x₂, x₃, x₄) для максимальных граней:

α1	0	0	0	0
α2	0	0	0	1
α3	0	0	1	0
α4	0	0	1	1
α5	0	1	0	0
α6	0	1	0	1
α7	0	1	1	0
α8	1	0	1	0

 

Построим, граф соответствующий  максимальным граням:

Рисунок 2. Граф, соответствующий  максимальным

 граням функции f

 

Получилось три грани N₁,N₂,N₃ размерности два и одна N₄ размерности один. Запишем теперь простые импликанты:

K_N1=

K_N2=

K_N3=

K_N4=

Получаем сокращенную ДНФ:

f(x₁, x₂, x₃, x₄)

ДНФ Квайна:

Пусть f – булева функция, неравная тождественно нулю, тогда максимальная грань N из N_f называется ядровой, если существует такая точка α ϵ N_f, которая содержится только в одной грани N.

 

Совокупность всех ядровых граней называется ядром функции.

 

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

 

Найдем ядро данной функции f(x₁, x₂, x₃, x₄):

Как видно из графа  все грани являются ядровыми, так  как в каждой есть точка, которая  принадлежит только этой грани: в N₁ точка α₄, в N₂ точка α₆, в N₃ точка α₇, в N₄ точка α₈.

Таким образом, ядром  данной функции является множество

 ker f={ N₁,N₂,N₃, N₄ }

Так как все грани ядровые, то ДНФ Квайна совпадает с сокращенной ДНФ.

Однако, существует и  другой способ нахождения ДНФ Квайна.

Метод Квайна нахождения ДНФ Квайна

(а  также ДНФ типа ∑Т и минимальной ДНФ):

 

Для применения метода Квайна составляется следующая таблица:

Таблица 5. Таблица Квайна:

	α1	α2	…..	αS
KN1
KNs

Где K_N1,…, K_NS – это элементарные конъюнкции, соответствующие  максимальным граням в N_f   α₁,…, α_S – это точки из N_f

Если α_j ϵ N_Ki, то в i-й строке и j-м столбце данной таблицы делается соответствующая заметка.

Если в j-м столбце данной таблицы находится только одна заметка, находящаяся в i-строке, то N_Ki – ядровая грань.

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

 

Применим данный метод  к полученной сокращенной ДНФ:

Таблица 6: Таблица Квайна функции f(x₁, x₂, x₃, x₄)

	0000	0001	0010	0011	0100	0101	0110	1010
	*	*	*	*
	*	*			*	*
	*		*		*		*
			*					*

 

Как видно из таблицы  все грани ядровые, следовательно  ДНФ Квайна совпадает с сокращенной.

ДНФ Квайна: f(x₁, x₂, x₃, x₄)

 

ДНФ типа ∑Т:

Пусть f – булева функция, неравная тождественно нулю, тогда ДНФ типа ∑Т функции f состоит из всех элементарных конъюнкций, соответствующих максимальным граням, которые входят в хотя бы одно непреводимое покрытие.

 

Пусть f – булева функция, неравная тождественно нулю ,тогда покрытие

N₁,…., N_S множества N_f называется непреводимым, если

   1. грани N₁,…., N_S – максимальные в N_f

   2. ни одну грань из данного покрытия нельзя удалить таким образом. чтобы оставшиеся грани также образовывали покрытие N_f

   Пусть f – булева функция, неравная тождественно нулю, пусть α ϵ N_f, тогда пучком. проходящим через точку α, будем называть совокупность вех максимальных граней, проходящих через α.

 

 Пусть f – булева функция, неравная тождественно нулю, N максимальная грань в N_f и α ϵ N_f, тогда α называется регулярной точкой грани N, если существует β ϵ N_f N: пучок, проходящий через β содержится в пучке, проходящем через α.

Теорема Журавлева:

Простая импликанта входит в запись ДНФ типа ∑Т тогда и  только тогда, когда она соответствует  нерегулярной грани.

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

Все грани нерегулярные, поэтому ДНФ типа ∑Т совпадает  с сокращенной ДНФ и ДНФ  Квайна.

ДНФ типа ∑Т: f(x₁, x₂, x₃, x₄)

Минимальная ДНФ:

Минимальная ДНФ в смысле любого индекса сложности можно искать среди ДНФ, соответствующих неприводимым покрытиям.

Для данной функции f(x₁, x₂, x₃, x₄) нельзя привести неприводимое покрытие, то есть нельзя удалить ни одну грань, чтобы осталось покрытие N_f, образованное максимальными гранями, так как все грани являются ядровыми, следовательно минимальная ДНФ совпадает с сокращенной ДНФ.

Минимальная ДНФ: f(x₁, x₂, x₃, x₄)

 

Минимальная КНФ:

Элементарной  дизъюнкцией будем называть выражение вида:

, где x_i,….,х_i – различные символы независимых переменных.

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

 

Конъюнктивной нормальной формой (КНФ) будем называть выражение вида:

  , где D₁,D₂,...,D_S – различные элементарные дизъюнкции

Замечание: Пусть функция f – булева функция, где f≠1, имеет представление в виде КНФ. В качестве такой формы можно взять СКНФ.

Различные КНФ сравниваются между собой на основании некоторого заданного индекса сложности. Индекс сложности для КНФ определяется по аналогии с индексом сложности для ДНФ:

Пусть К – множество  КНФ, то L: K→R называется индексом сложности, если удовлетворяет аксиомам:

1. положительная определенность  
2. монотонность
3. выпуклость
4. инвариантность относительно замены

Замечание: Заметим, что индексы сложности для ДНФ и КНФ однозначно связаны между собой, а именно: пусть на множестве ДНФ задан индекс сложности L, тогда можно определить L: D→R двойственный индекс сложности L^* на множестве КНФ: L^*: K→R

L^*(K)=L(K^*)

Задача о нахождении минимальной КНФ в смысле некоторого индекса сложности L^* сводится к задаче минимизации ДНФ в смысле индекса L: это делается следующим образом:

Предположим, что необходимо найти минимальную КНФ для f, где f≠1, в смысле индекса сложности L^*:

1. g=f*  (g≠0)
2. Для функции g необходимо найти минимальную ДНФ в смысле индекса L: L^*(D)=L(D^*)
3. Если g имеет минимальную ДНФ в смысле L вида: , то f будет представляться в виде :

 

Найдем минимальную  КНФ для функции f(x₁, x₂, x₃, x₄). Значения для функции g были указаны в таблице 1. Для начала найдем сокращенную ДНФ для функции g, а затем по ней и минимальную ДНФ. Для нахождения сокращенной ДНФ используем как аналитический, так и графический способы:

1. Аналитический: