 |
|
ТОЖДЕСТВА ДЛЯ ЭЛЕМЕНТАРНЫХ ФУНКЦИЙ
Приведем основные общие соотношения эквивалентности, справедливые для формул, составленных с помощью элементарных функций.
1. Для каждой функции * Î { +, &,Ú} справедливы соотношения ассоциативности и коммутативности:
U1 * (U2 *U3) º (U1 *U2) *U3 и U1 *U2 º U2 * U1.
2. Для функций & иÚсправедливы соотношения дистрибутивности:
U1 Ú (U2& U3) º (U1 Ú U2)&(U1 Ú U3);
U1 & (U2 Ú U3) º (U1& U2)Ú (U1& U3).
3. Соотношения Де-Моргана:
;
.
4. Правило снятия двойного отрицания: 
.
5. Правила сокращения для конъюнкций и дизъюнкций:
0&Uº0; UÚUºU;
0 Ú UºU;UÚ 
º1;
1&UºU; U&U ºU;
1ÚUº1;U& º0.
В приведенных тождествах записиU, U1,U2,U3 обозначают произвольные формулы.
Упражнение.Проверить справедливость приведенных соотношений эквивалентности.
Соотношения ассоциативности позволяют опускать скобки в формулах, составленных из функций равного приоритета. Например, корректны следующие записи: x1 
x2 . . . xn и x1& x3& x 4.
В указанных случаях будем также использовать сокращенные записи: 
и 
.
В дальнейшем записи формул будут применяться в качестве обозначения представляемых ими функций. Например, в тексте может быть использовано выражение: "Рассмотрим булевскую функцию 
", которое понимается как: "Рассмотрим булевскую функцию, представляемую формулой: ".
Упражнение.
1. Переменная xi является существенной переменной функций
f (x1,. . ., xn) и g (x1,. . ., xn). Является ли xi существенной переменной функции f (x1,. . ., xn) Ú g (x1 ,. . ., xn)?
2. Переменные xi и xj являются существенными переменными функции f (x1,. . ., xn). Является ли xi существенной переменной функции, получаемой из f заменой переменной xj на переменную xi?
3. Все переменные функции f (x1,. . ., xn) являются существенными. Сколько существенных переменных имеет функция f (xn,. . ., x1)?
4. Все переменные функции f (x1,. . ., xn) являются существенными. Сколько существенных переменных может иметь функция f (x1,. . ., x1)?