Определение

Формулы U₁ и U₂ называются эквивалентными, если представляемые ими функции равны.

Эквивалентность формул U₁ и U ₂ представляется записью U₁  U₂. Такие записи называются тождествами.

ТЕОРЕМА 4.1. Теорема о замене равных

Пусть U₁  подформула формулы V и U₁  U₂.

Тогда формула W, получаемая из V заменой подформулы U₁ на формулу U ₂, эквивалентна формуле V.

Доказательство

Покажем что на одном и том же наборе значений всех различных переменных, входящих в V и W, значения функций f_V и f_W совпадают.

Действительно, при вычислении значений f_V и f_W на произвольном наборе значений переменных значения, подставляемые вместо подформул U₁ и U₂, совпадают. Поскольку всюду, за исключением U₁ и U₂, формулы V и W одинаковы, то дальнейшее вычисление значений V и W протекает одинаково и поэтому приводит к совпадающим значениям.

Поэтому f_V и f_W совпадают с точностью до несущественных переменных.

Доказательство окончено.

Доказанная теорема позволяет сформулировать правило замены равных, состоящее в допустимости замены подформул произвольных формул на эквивалентные им подформулы. Как следует из теоремы о замене равных, такие преобразования формул не приводят к изменению функции, представляемой исходной формулой.

Преобразования формул, производимые в соответствии с правилом замены равных, называются эквивалентными преобразованиями.

При проведении эквивалентных преобразований обычно используют соотношения эквивалентности из некоторого стандартного семейства схем таких преобразований.

4.6. Тождества для элементарных функций

Приведем основные общие соотношения эквивалентности, справедливые для формул, составленных с помощью элементарных функций.

1. Для каждой функции  { +, &, } справедливы соотношения ассоциативности и коммутативности:

U₁  (U₂  U₃)  (U₁  U₂) U₃ и U₁  U₂  U₂  U₁.

2. Для функций & и  справедливы соотношения дистрибутивности:

U₁  (U₂ & U₃)  (U₁  U₂) & (U₁  U₃);

U₁ & (U₂  U₃)  (U₁& U₂)  (U₁& U₃).

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 обозначают произвольные формулы.

Упражнение. Проверить справедливость приведенных соотношений эквивалентности.

Соотношения ассоциативности позволяют опускать скобки в формулах, составленных из функций равного приоритета. Например, корректны следующие записи: x₁ x₂ . . . x_n и x₁& x₃ & x ₄.

В указанных случаях будем также использовать сокращенные записи: и .

В дальнейшем записи формул будут применяться в качестве обозначения представляемых ими функций. Например, в тексте может быть использовано выражение: "Рассмотрим булевскую функцию ", которое понимается как: "Рассмотрим булевскую функцию, представляемую формулой: ".

Упражнение.

1. Переменная x_i является существенной переменной функций f (x₁, . . . , x_n) и g (x₁, . . . , x_n). Является ли x_i существенной переменной функции f (x₁, . . . , x_n)  g (x₁ , . . . , x_n)?

2. Переменные x_i и x_j являются существенными переменными функции f (x₁, . . . , x_n). Является ли x_i существенной переменной функции, получаемой из f заменой переменной x_j на переменную x_i?

3. Все переменные функции f (x₁, . . . , x_n) являются существенными. Сколько существенных переменных имеет функция f (x_n, . . . , x₁)?

4. Все переменные функции f (x₁, . . . , x_n) являются существенными. Сколько существенных переменных может иметь функция f (x₁, . . . , x₁)?

74