2.2. АЛГЕБРА ЛОГИКИ НА ПАЛЬЦАХ

  
  Диаграммы Венна 
 

Обозначения:

	И = истина	1
	Л = ложь        0

Операнды
	X1	A
	X2	B
	X3	C

Диаграмма Венна:
	Для каждого операнда - круг
	Круг делит все на 2 множества:
		внутри круга - операнд равен  1
		снаружи круга - операнд равен 0
	Круги пересекаются со всеми другими кругами
	Если значение функции в какой то зоне равно 1 то зона штрихуется,
	a если  0 то зона остается незакрашенной


Пример диаграммы Венна для двухоперандных функций:
  


Пример диаграммы Венна для трехоперандных функций:
  





  
  NOT (НЕ) 
 
  


NOT (инверсия) - меняет значение операнда на противоположное.

	X   | НЕ X  			X | X# 
	----+-------                   ---+----
	Л   | И				0 | 1
	И   | Л                         1 | 0




Обозначения NOT:
		_
		X		X#

		~X
				-+
		-+ X	        X




  
  AND (И) 
 
  

                                               x2
		X2                            ------
	И |  Л   И			AND |  0  1  	карта Карно
	--+-----------                  ----+-------- 				
   X1	Л |  Л   Л                     |  0 |  0  0
        И |  Л   И                  x1 |  1 |  0  1



					A   B   |
	Л  и  Л  = Л			X1  X2  | AND	таблица истинности
	Л  и  И  = Л                   ---------+-----
	И  и  Л  = Л			0   0   | 0
	И  и  И  = И			0   1   | 0
				        1   0   | 0
					1   1   | 1



Обозначения AND:
		A B
		A * B           	// логическое умножение
		A . B
		A & B			// язык С
		A and B			
		A ^ B			// дезъюнкция		

Операнды называются:
	
	конъюнкт  &  конъюнкт




  
  OR (ИЛИ) 
 
  

                                               x2
	                        	     ------
	ИЛИ|  Л   И                     OR |  0  1
	---+----------			---+--------
	 Л |  Л   И                   |  0 |  0  1
	 И |  И   И                 x1|  1 |  1  1



	A   B   |
	X1  X2	| OR
	--------+-----
	0   0	| 0
	0   1	| 1
	1   0	| 1
	1   1	| 1



Обозначения OR:	
		A + B			// логическое сложение
		A | B			// язык С
		A V B			// конъюнкция
		A or B

Операнды называются:

	дезъюнкт V дезъюнкт




  
  EQV (РАВНОЗНАЧНОСТЬ) 
 
Equivalence
  

                                                        x2
                                		     -------	
	EQV|  Л  И   				EQV | 0  1
	---+---------           	        ----+-------
	 Л |  И  Л              	       |  0 | 1  0
	 И |  Л  И              	    x1 |  1 | 0  1

	
						A   B   |
	экивалетна ли              		X1  X2	| EQV
		Ложь   Лжи 	= И		--------+-----
		Ложь   Истине   = Л 		0   0	| 1
		Истина Лжи      = Л		0   1	| 0
		Истина Истине   = И		1   0   | 0
						1   1   | 1

	EQV(A,B) = (A and B)# or (A and B)




Обозначения EQV:
        	A  ~  B		// алгебра Логики
		A equ B
		A eqv B
		A ==  B



  
  IMP (СЛЕДОВАНИЕ) 
 

Implication (Следование)

Импликация (следование) из X1 -> X2
Несимметричная функция.

  

                                               x2
       X1->X2	x2                     X1->X2 ------
	IMP |  Л  И			IMP | 0  1
	----+-------- 			----+-------
    x1	  Л |  И  И                    |  0 | 1  1
	  И |  Л  И                  x1|  1 | 0  1


	A  B   |
	X1 X2  | IMP: X1->X2
        -------+-----
	0  0   |  1
	0  1   |  1
        1  0   |  0
        1  1   |  1

	Следует ли из
		Лжи Ложь      = И (Да)
		Лжи Истина    = И (Да) Из лжи может следовать что угодно
		Истины Ложь   = Л (Нет)
		Истины Истина = И (Да)
                 



Поскольку нессиметричная, то есть и сопряженная:
импликация из X2 -> X1
  


Таблица истинности получается если поменять местами X1 и X2.

	B  A   |
	X2 X1  | IMP:  X2->X1           
        -------+-----
	0  0   |  1
	0  1   |  1
        1  0   |  0
        1  1   |  1

приводим обратно:

	A  B   |
	X1 X2  | IMP:  X2->X1
        -------+-----
	0  0   |  1
	0  1   |  0
	1  0   |  1
	1  1   |  1



Обозначения импликации:
		A -> B		// импликация от А к B
		B -> A		// импликация от B к A

Операнды называются:
	
	антецедент ->   консеквент
	(посылка)	(заключение)




  
  NAND (И-НЕ) 
 
  


NAND	И-НЕ		NAND(X,Y) = not (X and Y)




	NAND | 0  1 			
	-----+-------                   
	   0 | 1  1                      
	   1 | 1  0                     

	
	A  B  | 
	X1 X2 | NAND
	------+-----
	0  0  | 1
	0  1  | 1
	1  0  | 1
	1  1  | 0




Обозначения NAND:
		___
		A B  		(AB)#
		_____
		A * B		(A * B)#
		_____
		A ^ B		(A ^ B)#
		_____
		A & B		(A & B)#
		_______
		A and B		(A and B)#

		A / B		Штрих Шеффера






  
  NOR (ИЛИ-НЕ) 
 
  


NOR	ИЛИ-НЕ		NOR(X,Y)  = not (X or  Y)




	NOR  | 0  1
	-----+-------    
	   0 | 1  0
	   1 | 0  0


	A  B  |
	X1 X2 | NOR
	------+-----
	0  0  | 1
        0  1  | 0
	1  0  | 0
	1  1  | 0



Обозначения NOR:
		_____
		A + B		(A + B)#
		_____
		A V B		(A V B)#
		______
		A or B		(A or B)#

		  |
		A V B		Стрелка Пирса




  
  XOR (ИСКЛЮЧАЮЩЕЕ ИЛИ) 
 
  


	XOR (исключающее ИЛИ) - это сложение по модулю 2
	XOR(X,Y) = not (EQV(X,Y))
	XOR(X,Y) = (A# and B) or (B# and A)

	XOR  | 0  1
	-----+------
	   0 | 0  1
	   1 | 1  0


	A  B  |
	X1 X2 | XOR
	------+-----
	0  0  | 0
	0  1  | 1
	1  0  | 1
	1  1  | 0


	заметим что кроме того x1 XOR x2 это  X1 != X2




Обозначение ХOR:
		A (+) B
		A xor B
		A <>  B
		A !=  B



  
  ЗАПРЕТ 
 

Несимметричная функция

Запрет по Х2 (X1 <- X2):
  


Смысл в понятие теории множеств:
	вычитание X1 - X2
	т.е. подмножество элементы которого содержаться в X1,
	     но не содержаться в X2.


Смысл:
	F  =  0, если X2 = 1
	     X1, если X2 = 0

	X1 <- X2 = not(X1 -> X2)

	B  A  |
	X2 X1 | X1 <- X2
	------+---------
	0  0  | 0
	0  1  | 1
	1  0  | 0
	1  1  | 0

приводим:


	A  B  |
	X1 X2 | X1 <- X2
	------+---------
	0  0  | 0
	0  1  | 0
	1  0  | 1
	1  1  | 0

	собственно еще это можно выразить как X1 > X2



Сопряженная ей функция: запрет по Х1 (X2 <- X1)
  


	а эту можно выразить как X1 < X2



Обозначение запрета:
	X1 <- X2	запрет по X2
	X2 <- X1	запрет по X1

	X1 >  X2	запрет по X2
	X2 >  X1	запрет по X1
	X1 <  X2	запрет по X1
	X2 <  X1	запрет по X2

	X1 -  X2	запрет по X2
	X2 -  X1	запрет по X1



  
  Вырожденные случаи 
 

Назовите функции соответствуещее случаям:

  
  Нульоперандные вырожденные 
 

  

  




  
  Однооперандные вырожденные 
 

  

  


  

  






  
  Примеры 
 

Самостоятельно вычислите какие функции изображены на примерах:

  

  





  
  Трехоперандные функции 
 

  
  AND3 
 
  


	AND(A, B, C) = A * B * C = (A * B) * C = A * (B * C)

	B C A | AND
	------+----
	0 0 0 | 0
	0 0 1 | 0
	0 1 0 | 0
	0 1 1 | 0
	1 0 0 | 0
	1 0 1 | 0
	1 1 0 | 0
	1 1 1 | 1



  
  OR3 
 
  



	OR(A, B, C) = A + B + C = (A + B) + C = A + (B + C)

	B C A | OR
	------+----
	0 0 0 | 0
	0 0 1 | 1
	0 1 0 | 1
	0 1 1 | 1
	1 0 0 | 1
	1 0 1 | 1
	1 1 0 | 1
	1 1 1 | 1
	



  
  NAND3 
 
  


	NAND(A, B, C) = NOT(AND(A, B, C))


	B C A | NAND
	------+----
	0 0 0 | 1
	0 0 1 | 1
	0 1 0 | 1
	0 1 1 | 1
	1 0 0 | 1
	1 0 1 | 1
	1 1 0 | 1
	1 1 1 | 0



  
  NOR3 
 
  


	NOR(A, B, C) = NOT(OR(A, B, C))

	B C A | NOR
	------+----
	0 0 0 | 1
	0 0 1 | 0
	0 1 0 | 0
	0 1 1 | 0
	1 0 0 | 0
	1 0 1 | 0
	1 1 0 | 0
	1 1 1 | 0



  
  XOR3 
 
  


	XOR(A, B, C) = A (+) B (+) C = [A (+) B] (+) C = A (+) [B (+) C]

	B C A | XOR
	------+----
	0 0 0 | 0
	0 0 1 | 1
	0 1 0 | 1
	0 1 1 | 0
	1 0 0 | 1
	1 0 1 | 0
	1 1 0 | 0
	1 1 1 | 1