Формулы алгебры двоичных функций. Таблицы истинности. Равносильные формулы

1. 
   x0=1;
   
2. 
   0x=0;
   
3. 
   x0=0;
   
4. 
   1x=1;
   
5. 
   x1 =1;
   
6. 
   xy =0;
   
7. 
   y =1.
   

4. 
   

1. 
   xy=1, xy=0, x=…, y=…;
   
2. 
   xy=0, x=…;
   
3. 
   xy=0, xy=1, y =…;
   
4. 
   xy=1, ( y)( y)=…;
   
5. 
   xy=0, xy=0, xy=1, x=... ;
   
6. 
   xy=0, xy=1; xy=1, yx=… .
   

Обычно применяют следующее соглашение об упрощении записи формул. В записи формул можно опускать:

• 
  внешние скобки;
  
• 
  знак конъюнкции;
  
• 
  скобки, определяющие порядок действий, в ассоциативном случае;
  
• 
  часть скобок, определяющих порядок действий, при условии, что конъюнкция  «сильнее» дизъюнкции , и обе они «сильнее» остальных двуместных связок, а отрицание «сильнее» всех связок.
  

ПРИМЕР. Дана формула ((((ab) )c)((a )a)). Ее упрощенная запись имеет вид: ab c(a )a.

5. 
   Учитывая соглашения о порядке выполнения операций, опустить «лишние» скобки и знак «» в формулах:
   

1. 
   (xy)((yz)(( y)(x )));
   
2. 
   ((xy)(x((y(xz))(yz))) ).
   

6. 
   Восстановить скобки и знак «» в формулах:
   

1. 
   xyxyz;
   
2. 
   (xxyz)(xyz);
   
3. 
   xyz(xyz)xy(x(yz));
   
4. 
   xyx(yz)(xy)xzyz;
   

7. 
   Составить таблицы истинности для следующих формул:
   

1. 
   (x )(x|(yz)) (здесь x|y= ).
   

ОПР. Две двоичные функции на одном и том же наборе переменных равны (одинаковы), если их значения на каждом из наборов значений переменных совпадают.
ОПР. Две формулы равносильны, если они реализуют одинаковые функции.

8. 
   Доказать, что: F₁F₂ 1 т. и т.т., когда F₁ и F₂ равносильны.
   
9. 
   (д/з 1 столбец) Применяя таблицу истинности, доказать равносильность формул (таблицу истинности можно составить одну для нескольких функций):
   

1. 
   xx  1;
   
2. 
   x0   ;
   
3. 
   x0   ;
   
4. 
   xx  1;
   
5. 
   x1 =  ;
   
6. 
   xx= 0;
   
7. 
   x0 = x;
   
8. 
   x1 = 
   
9. 
   x  1;
   
10. 
    xy  yx;
    
11. 
    xy  yx;
    
12. 
    xx  xx =  .
    

10. 
    Выяснить, равносильны ли формулы F и G, применяя равносильные преобразования:
    

1. 
   F = xy y , G = xy
   
2. 
   F =  , G = x ( x )
   
1. 
   Применяя равносильные преобразования, упростить формулу: xzx yz yz.
   

Утверждение1. Основные равносильности остаются справедливыми при подстановке вместо переменных любых формул алгебры двоичных функций.
Пример. Основная равносильность x   1 означает, в частности, что x₁   1, 1  1, .
Утверждение2. Если С — произвольная формула, и А  В, то  , АС  ВС, АС  ВС, АС  ВС, АС  ВС, АС  ВС.

12. 
    Проверить с помощью равносильных преобразований свойства двоичных функций:
    
    1. 
       xy=(xy); b) (x+y)z=xz+yz;
       
13. 
    Установить помощью равносильных преобразований, выполняется ли равносильность формул F и G:
    

1. 
   F = x(y~z), G = (xy)~(xz);
   
2. 
   F = x(y~z), G = (xy)~(xz).