Основные формулы алгебры логики
Таблица истинности булевых операций
| \( x \) |
\( y \) |
\( x \lor y \) |
\( x \land y \) |
\( x \oplus y \) |
\( x \rightarrow y \) |
\( x \sim y \) |
\( x \mid y \) |
\( x \downarrow y \) |
| 0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
| 0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
| 1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
| 1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
Обозначения:
- \( x \lor y \) — дизъюнкция (логическое "ИЛИ")
- \( x \land y \) — конъюнкция (логическое "И")
- \( x \oplus y \) — исключающее "ИЛИ" (сложение по модулю 2)
- \( x \rightarrow y \) — импликация ("если \( x \), то \( y \)")
- \( x \sim y \) — эквивалентность (\( x \) равно \( y \))
- \( x \mid y \) — штрих Шеффера (отрицание конъюнкции, "NAND")
- \( x \downarrow y \) — стрелка Пирса (отрицание дизъюнкции, "NOR")
Основные эквивалентности
1. Коммутативность
\[
x \lor y = y \lor x, \quad x \land y = y \land x, \quad x \oplus y = y \oplus x, \quad x \sim y = y \sim x.
\]
2. Ассоциативность
\[
(x \lor y) \lor z = x \lor (y \lor z) = x \lor y \lor z,
\]
\[
(x \oplus y) \oplus z = x \oplus (y \oplus z) = x \oplus y \oplus z,
\]
\[
(x \land y) \land z = x \land (y \land z) = x \land y \land z.
\]
3. Дистрибутивность
\[
(x \lor y) \land z = (x \land z) \lor (y \land z),
\]
\[
(x \land y) \lor z = (x \lor z) \land (y \lor z).
\]
4. Законы де Моргана
\[
\overline{x \lor y} = \overline{x} \land \overline{y}, \quad \overline{x \land y} = \overline{x} \lor \overline{y}.
\]
5. Законы поглощения
\[
x \lor x = x, \quad x \land x = x,
\]
\[
x \lor \overline{x} = 1, \quad x \land \overline{x} = 0,
\]
\[
x \lor 1 = 1, \quad x \land 1 = x,
\]
\[
x \lor 0 = x, \quad x \land 0 = 0.
\]
6. Преобразование операций
\[
x \mid y = \overline{x \land y},
\]
\[
x \downarrow y = \overline{x \lor y} ,
\]
\[
x \rightarrow y = \overline{x} \lor y,
\]
\[
x \oplus y = (x \land \overline{y}) \lor (\overline{x} \land y),
\]
\[
x \sim y = (x \land y) \lor (\overline{x} \land \overline{y}).
\]
Дополнительная информация
