2.5. НОРМАЛЬНАЯ ФОРМА ЛОГИЧЕСКОЙ ФУНКЦИИ

Def
===
	ЭЛЕМЕНТАРНАЯ КОНЪЮНКЦИЯ 
		логическое произведение переменных функции,
		при зтом каждая переменная может входить либо
		в неизмененном виде, либо в виде инверсии
		(каждая переменная может входить только один раз)

	Пример:
		F(x1,x2,x3,x4)
			
			x1*x2*x3*x4
			x1*x2#*x3*x4
			x1*x2#*x3#*x4
			x1#*x2#*x3#*x4#

Каждой элементарной конъюнкции соответствует свой входной набор,
на котором ее значение превращается в 1 (на всех остальных оно равно 0)

		--------------------------------------
                                        Входной набор
		Эл.Конъюнкция		x1 x2 x3 x4
		--------------------------------------
		x1*x2*x3*x4		1  1  1  1
		x1*x2#*x3*x4            1  0  1  1
		x1*x2#*x3#*x4           1  0  0  1
		x1#*x2#*x3#*x4#		0  0  0  0
		--------------------------------------

Элементарные конъюнкции для двухоперандной функции:
  

Элементарные конъюнкции для трехоперандной функции:
  





Def
===
	ЭЛЕМЕНТАРНАЯ ДИЗЪЮНКЦИЯ
		логическое сумма  переменных функции,
		при зтом каждая переменная может входить либо
		в неизмененном виде, либо в виде инверсии
		(каждая переменная может входить только один раз)
	

	Пример:
		F(x1,x2,x3,x4)

			x1+x2+x3+x4
			x1#+x2+x3+x4#
			x1#+x2#+x3#+x4#

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

		--------------------------------------
                                        Входной набор
		Эл.Дизъюнкция		x1 x2 x3 x4
		--------------------------------------
		x1+x2+x3+x4		0  0  0  0
		x1#+x2+x3+x4#           1  0  0  1
		x1#+x2#+x3#+x4#         1  1  1  1
		--------------------------------------




Def
===
	РАНГ ЭЛЕМЕНТАРНОЙ КОНЪЮНКЦИИ/ДИЗЪЮНКЦИИ
		равен количеству переменных в ней



Def
===
	СОСЕДНИЕ ЭЛЕМЕНТАРНЫЕ КОНЪЮНКЦИИ/ДИЗЪЮНКЦИИ
		две злементарные конъюнкции/дизъюнкции одного ранга
		которые отличаются только инверсией одной из переменных

	На диаграмме Венна такие области имеют общую границу
	На карте Карно (до 4x4) - это соседние клетки.



Def
===
	НОРМАЛЬНАЯ ФОРМА ФУНКЦИИ
		это представление функции в виде суммы элементарных
		конъюнкций (ранга равного числу переменных функции)
		это конъюнктивная нормальная форма
		(элементарную конъюнкцию в ней называют МИНИТЕРМ)

		или представление функции в виде произведения элементарных
		дизъюнкций (ранга равного числу переменных функции)
		это дизъюнктивная нормальная форма
		(элементарную дизъюнкцию в ней называют МАКСИТЕРМ)
	

	

Общий вид нормальной формы:

	F1(x) 	   = c0*x + c1*x#
	F2(x1,x2)  = c0*x1*x2 + c1*x1*x2# + c2*x1#*x2 + c3*x1#*x2#

	F2(x1,x2)  = (c0 + x1  + x2) * (c1 + x1  + x2#) * 
		     (c2 + x1# + x2) * (c3 + x1# + x2#)


	Для конкретной функции все коэффициенты 'c' равны 0 или 1
	Пример:
	   Конъюнктивная форма:
		AND(x1,x2) = 1*x1*x2 + 0*x1#*x2 + 0*x1*x2# + 0*x1#*x2#
			   = x1*x2		

			--------------------------------------------------------
			args   |       	        минтермы               |   +
			x2 x1  |c0*x1*x2|c1*x1#*x2|c2*x1*x2#|c3*x1#*x2#| Result
			-------+--------+---------+---------+----------+--------
			0  0   |   0	   (0)        (0)	(0)    |   0		       	
			0  1   |   0       (0)        (0)       (0)    |   0
			1  0   |   0       (0)        (0)       (0)    |   0
			1  1   |   1       (0)        (0)       (0)    |   1
			--------------------------------------------------------


		OR (x1,x2) = 1*x1*x2 + 1*x1*x2# + 1*x1#*x2 + 0*x1#*x2#
			   = x1*x2 + x1*x2# + x1#*x2

			--------------------------------------------------------
			args   |       	        минтермы               |   +
			x2 x1  |c0*x1*x2|c1*x1#*x2|c2*x1*x2#|c3*x1#*x2#| Result
			-------+--------+---------+---------+----------+--------
			0  0   |   0	     0        0         (0)    |   0 			       	
			0  1   |   0         0        1         (0)    |   1
			1  0   |   0         1        0         (0)    |   1
			1  1   |   1         0        0         (0)    |   1
			--------------------------------------------------------

		XOR (x1,x2) = 0*x1*x2 + 1*x1#*x2 + 1*x1*x2# + 0*x1#*X2#
			    = x1#*x2 + x1*x2#

			--------------------------------------------------------
			args   |       	        минтермы               |   +
			x2 x1  |c0*x1*x2|c1*x1#*x2|c2*x1*x2#|c3*x1#*x2#| Result
			-------+--------+---------+---------+----------+--------
			0  0   |  (0)	     0        0         (0)    |   0 			       	
			0  1   |  (0)        0        1         (0)    |   1
			1  0   |  (0)        1        0         (0)    |   1
			1  1   |  (0)        0        0         (0)    |   0
			--------------------------------------------------------



	   Дизъюнктивная форма:
		OR (x1,x2) = (x1 + x2) * (1 + x1  + x2#) * (1 + x1# + x2) *
					 (1 + x1# + x2#)
			   = (x1 + x2)

			--------------------------------------------------------
			args   |       	        мaкстермы              |   *
			x2 x1  |c0+x1+x2|c1+x1#+x2|c2+x1+x2#|c3+x1#+x2#| Result
			-------+--------+---------+---------+----------+--------
			0  0   |   0	   (1)        (1)      (1)     |   0 			       	
			0  1   |   1       (1)        (1)      (1)     |   1
			1  0   |   1       (1)        (1)      (1)     |   1
			1  1   |   1       (1)        (1)      (1)     |   1
			--------------------------------------------------------


		AND(x1,x2) = (0 + x1 + x2)  * (0 + x1 + x2#) * 
			     (0 + x1# + x2) * (1 + x1# + x2#)
			   = (x1 + x2) * (x1 + x2#) * (x1# + x2)


			--------------------------------------------------------
			args   |       	        мaкстермы              |   *
			x2 x1  |c0+x1+x2|c1+x1#+x2|c2+x1+x2#|c3+x1#+x2#| Result
			-------+--------+---------+---------+----------+--------
			0  0   |   0	    1	      1		(1)    |   0           	
			0  1   |   1        0         1         (1)    |   0
			1  0   |   1        1         0         (1)    |   0
			1  1   |   1        1         1         (1)    |   1
			--------------------------------------------------------

		XOR(x1,x2) = (0 + x1 + x2)  * (1 + x1# + x2) * 
			     (1 + x1 + x2#) * (0 + x1# + x2#) 
			   = (x1 + x2)*(x1# + x2#)

			--------------------------------------------------------
			args   |       	        мaкстермы              |   *
			x2 x1  |c0+x1+x2|c1+x1#+x2|c2+x1+x2#|c3+x1#+x2#| Result
			-------+--------+---------+---------+----------+--------
			0  0   |   0	   (1)	     (1)	 1     |   0           	
			0  1   |   1       (1)       (1)         1     |   1
			1  0   |   1       (1)       (1)         1     |   1
			1  1   |   1       (1)       (1)         0     |   0
			--------------------------------------------------------




	Логическую сумму двух соседних элементарных коньюнкций ранга R
	можно заменить на элементарную конъюнкцию ранга R-1
	выбросив переменную, инверсия которой различается:

	Основание:
		A * B * C + A * B * C# = A * B * (C + C#) = A * B
						 +------+
						   = 1


			        x1	      x1#	 	
	Пример:              -----            ------
		OR (x1,x2) = x1*x2 + x1*x2# + x1#*x2
			     -----   ------
				x2      x2#  


		OR (x1,x2) = x2 + x1*x2#
		OR (x1,x2) = x1 + x1#*x2



Здесь приведены все минтермы для функции 3х переменных:
  




Здесь приведены все макстермы для функции 3х переменных: