Основные тождества

Как мы помним, формулы называют эквивалентными, когда соответствующие им функции совпадают. Рассмотрим, как можно получить из формулы эквивалентные ей.

Теорема (о замене подформул на эквивалентные):

Пусть $f$ — некоторая элементарная функция.

Если формулы $\mathcal U_1$, $\mathcal U_2$, ..., $\mathcal U_n$ эквивалентны соответственно формулам $\mathcal B_1$, $\mathcal B_2$, ..., $\mathcal B_n$, то формула $\mathcal U = f(\mathcal U_1, \mathcal U_2,...,\mathcal U_n)$

эквивалентна формуле $\mathcal B = f(\mathcal B_1, \mathcal B_2, ...,\mathcal B_n)$.

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

Действительно, из определения эквивалентности следует, что $f_{\mathcal U_i} = f_{\mathcal B_i}$, $i=\overline{1,n}$. При этом, формула $\mathcal U$ реализует функцию $f_{\mathcal U} = f(f_{\mathcal U_1}, f_{\mathcal U_2}, ..., f_{\mathcal U_n})$, а формула $\mathcal B$ реализует функцию $f_{\mathcal B} = f(f_{\mathcal B_1}, f_{\mathcal B_2}, ..., f_{\mathcal B_n})$. Следовательно $f_{\mathcal U} = f_{\mathcal B}$.

[math]\displaystyle{ \blacksquare }[/math]

Это позволяет нам, записать ряд тождеств, которые мы сможем использовать для преобразования формул, заменяя подформулы на эквивалентные.

• Коммутативность: $x\circ y = y\circ x$, если $\circ\in\{\wedge, \vee, \oplus, \equiv, |, \downarrow\}$.
• Ассоциативность: $x\circ (y\circ z)=(x\circ y)\circ z$, если $\circ\in\{\wedge, \vee, \oplus, \equiv\}$. Мы уже указывали на это свойство раньше.
• Правила де Моргана: $\overline{x\wedge y} = \overline x\vee \overline y$, $\overline{x\vee y}=\overline{x}\wedge\overline{y}$.
• Правила поглощения: $x\vee xy = x$, $x(x\vee y)=x$.
• Дистрибутивность: * $x(y\vee z) = xy\vee xz$ — дистрибутивность $\wedge$ относительно $\vee$,
• $x\vee yz = (x\vee y) (x\vee z)$ — дистрибутивность $\vee$ относительно $\wedge$,
• $x(y\oplus z) = xy \oplus xz$ — дистрибутивность $\wedge$ относительно $\oplus$.
• Формулы расщепления: $x = xy\vee x\overline y$, $x = (x\vee y)(x\vee\overline y)$.
• * $0= x\overline x = x\wedge 0 = x\oplus x$,
• $1 = x\vee \overline x = x\vee 1 = x\equiv x$,
• $x = \neg\neg x = x\vee x = x x = x\wedge 1 = x\vee 0$.
• * $\overline x = x\oplus 1$,
• $x\equiv y = (x\oplus y)\oplus 1$,
• $x\oplus y = (x\vee y) \overline{x y} = x \overline{y}\vee \overline{x} y$,
• $x\supset y = \overline x\vee y = xy\oplus x\oplus 1$,
• $x\downarrow y = \overline x \wedge \overline y = \overline{x\vee y}$,
• $x | y = \overline x \vee \overline y = \overline{x\wedge y}$.

Используя эти тождества можно выполнять преобразования формул, получая им эквивалентные.

Рис. 1. Список тождеств работает как набор правил: каждый шаг заменяет подформулу на эквивалентную и подписан справа. Замена [math]\displaystyle{ y\supset x=\overline y\vee x }[/math] и [math]\displaystyle{ x\oplus 1=\overline x }[/math] приводит к [math]\displaystyle{ 1\vee 1 }[/math], то есть к [math]\displaystyle{ 1 }[/math]: формула — тавтология.

Пример

Рассмотрим формулу $\mathcal U = (y\supset x)\vee(x\oplus 1)\vee y$. Проведем преобразования, используя известные тождества.

[math]\displaystyle{ (y\supset x)\vee(x\oplus 1)\vee y = (\overline y\vee x)\vee(\overline x)\vee y = \overline y\vee x \vee \overline x\vee y = 1\vee 1 = 1. }[/math] Таким образом, формула $\mathcal U$ задает тождественно истинную функцию.

Очевидно, что формула $\mathcal B = \overline{\mathcal U}= \overline{(y\supset x)\vee(x\oplus 1)\vee y}=\overline 1 = 0$,

то есть $\mathcal B$ задает тождественно ложную функцию.

Определение:

Формула, задающая тождественно истинную функцию, называется тавтологией.

Определение:

Формула, задающая тождественно ложную функцию, называется противоречием.

Определение:

Формула называется выполнимой, если для нее существует набор аргументов, на котором она принимает значение 1.

Конспект: Дискретная математика