СВ в 08:44, 28 октября 2026

2026-10-28T08:44:02Z

← Предыдущая		Версия 08:44, 28 октября 2026
Строка 38:		Строка 38:
	Используя эти тождества можно выполнять преобразования формул, получая им эквивалентные.		Используя эти тождества можно выполнять преобразования формул, получая им эквивалентные.

	[[Файл:p35-01-rewrite-chain.svg\|~~thumb~~\|400px\|alt=Пять строк преобразования формулы U с подписями применённых тождеств: импликация, x ⊕ 1 = ¬x, перегруппировка, x ∨ ¬x = 1, 1 ∨ 1 = 1\|Рис. 1. Список тождеств работает как набор правил: каждый шаг заменяет подформулу на эквивалентную и подписан справа. Замена <math>y\supset x=\overline y\vee x</math> и <math>x\oplus 1=\overline x</math> приводит к <math>1\vee 1</math>, то есть к <math>1</math>: формула — тавтология.]]		[[Файл:p35-01-rewrite-chain.svg\|frame\|none\|400px\|alt=Пять строк преобразования формулы U с подписями применённых тождеств: импликация, x ⊕ 1 = ¬x, перегруппировка, x ∨ ¬x = 1, 1 ∨ 1 = 1\|Рис. 1. Список тождеств работает как набор правил: каждый шаг заменяет подформулу на эквивалентную и подписан справа. Замена <math>y\supset x=\overline y\vee x</math> и <math>x\oplus 1=\overline x</math> приводит к <math>1\vee 1</math>, то есть к <math>1</math>: формула — тавтология.]]

	{{Пример		{{Пример

СВ: Новая страница: «Как мы помним, формулы называют эквивалентными, когда соответствующие им функции совпад...»

2026-10-24T19:43:22Z

Новая страница: «Как мы помним, формулы называют эквивалентными, когда соответствующие им функции совпад...»

Новая страница

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

{{Теорема
|about=о замене подформул на эквивалентные
|statement=Пусть $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)$.
|proof=Действительно, из определения эквивалентности следует, что $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}$.
}}
Это позволяет нам, записать ряд тождеств, которые мы сможем использовать для преобразования формул, заменяя подформулы на эквивалентные.

* Коммутативность: $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}$.

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

[[Файл:p35-01-rewrite-chain.svg|thumb|400px|alt=Пять строк преобразования формулы U с подписями применённых тождеств: импликация, x ⊕ 1 = ¬x, перегруппировка, x ∨ ¬x = 1, 1 ∨ 1 = 1|Рис. 1. Список тождеств работает как набор правил: каждый шаг заменяет подформулу на эквивалентную и подписан справа. Замена <math>y\supset x=\overline y\vee x</math> и <math>x\oplus 1=\overline x</math> приводит к <math>1\vee 1</math>, то есть к <math>1</math>: формула — тавтология.]]

{{Пример
|content=Рассмотрим формулу $\mathcal U = (y\supset x)\vee(x\oplus 1)\vee y$. Проведем преобразования, используя известные тождества.
<math>
(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$ задает тождественно ложную функцию.
}}
{{Определение
|definition=Формула, задающая тождественно истинную функцию, называется тавтологией.
}}
{{Определение
|definition=Формула, задающая тождественно ложную функцию, называется противоречием.
}}
{{Определение
|definition=Формула называется выполнимой, если для нее существует набор аргументов, на котором она принимает значение 1.
}}
Конспект: [[Дискретная математика]]

Основные тождества - История изменений

СВ в 08:44, 28 октября 2026

СВ: Новая страница: «Как мы помним, формулы называют эквивалентными, когда соответствующие им функции совпад...»