Задание 6.3.5
Необходимо составить таблицу Поста и найти все базисы системы из следующих функций:
$f_1 = x \lor (y \sim z)$, $f_2 = x(x \oplus y)$, $f_3 = (x \rightarrow z)y$, $f_4 = \overline{x} | (x \lor y)$.
1. Упрощение функций (если возможно):
- $f_1 = x \lor (y \sim z) = x \lor ((y \land z) \lor (\overline{y} \land \overline{z}))$
- $f_2 = x(x \oplus y) = x(\overline{x}y \lor x\overline{y}) = x\overline{x}y \lor xx\overline{y} = 0 \lor x\overline{y} = x\overline{y}$
- $f_3 = (x \rightarrow z)y = (\overline{x} \lor z)y = \overline{x}y \lor zy$
- $f_4 = \overline{x} | (x \lor y) = \overline{\overline{x} \lor (x \lor y)} = x \land (\overline{x} \land \overline{y}) = x\overline{x}\overline{y} = 0$
2. Составление таблицы истинности для каждой функции:
| x |
y |
z |
$f_1 = x \lor (y \sim z)$ |
$f_2 = x\overline{y}$ |
$f_3 = \overline{x}y \lor zy$ |
$f_4 = 0$ |
| 0 |
0 |
0 |
1 |
0 |
0 |
0 |
| 0 |
0 |
1 |
0 |
0 |
1 |
0 |
| 0 |
1 |
0 |
0 |
0 |
1 |
0 |
| 0 |
1 |
1 |
1 |
0 |
1 |
0 |
| 1 |
0 |
0 |
1 |
1 |
0 |
0 |
| 1 |
0 |
1 |
1 |
1 |
1 |
0 |
| 1 |
1 |
0 |
1 |
0 |
0 |
0 |
| 1 |
1 |
1 |
1 |
0 |
1 |
0 |
3. Определение принадлежности функций классам Поста:
-
T0 (сохраняющие 0): Функция принадлежит T0, если $f(0, 0, ..., 0) = 0$.
- $f_1(0, 0, 0) = 1$ - не принадлежит T0.
- $f_2(0, 0) = 0$ - принадлежит T0.
- $f_3(0, 0, 0) = 0$ - принадлежит T0.
- $f_4 = 0$ - принадлежит T0.
-
T1 (сохраняющие 1): Функция принадлежит T1, если $f(1, 1, ..., 1) = 1$.
- $f_1(1, 1, 1) = 1$ - принадлежит T1.
- $f_2(1, 1) = 0$ - не принадлежит T1.
- $f_3(1, 1, 1) = 1$ - принадлежит T1.
- $f_4 = 0$ - не принадлежит T1.
-
S (самодвойственные): Функция принадлежит S, если $f(\overline{x_1}, \overline{x_2}, ..., \overline{x_n}) = \overline{f(x_1, x_2, ..., x_n)}$.
- $f_1 = x \lor (y \sim z)$. Не принадлежит S.
- $f_2 = x\overline{y}$. Не принадлежит S.
- $f_3 = \overline{x}y \lor zy$. Не принадлежит S.
- $f_4 = 0$. Не принадлежит S.
-
M (монотонные): Функция принадлежит M, если для любых наборов $a$ и $b$ таких, что $a \le b$ (покоординатно), выполняется $f(a) \le f(b)$.
- $f_1 = x \lor (y \sim z)$. Не принадлежит M.
- $f_2 = x\overline{y}$. Не принадлежит M.
- $f_3 = \overline{x}y \lor zy$. Не принадлежит M.
- $f_4 = 0$. Принадлежит M.
-
L (линейные): Функция принадлежит L, если она может быть представлена в виде $f(x_1, x_2, ..., x_n) = a_0 \oplus a_1x_1 \oplus a_2x_2 \oplus ... \oplus a_nx_n$.
- $f_1 = x \lor (y \sim z)$. Не принадлежит L.
- $f_2 = x\overline{y}$. Не принадлежит L.
- $f_3 = \overline{x}y \lor zy$. Не принадлежит L.
- $f_4 = 0$. Принадлежит L.
4. Таблица Поста:
| Функция |
T0 |
T1 |
S |
M |
L |
| $f_1$ |
− |
+ |
− |
− |
− |
| $f_2$ |
+ |
− |
− |
− |
− |
| $f_3$ |
+ |
+ |
− |
− |
− |
| $f_4$ |
+ |
− |
− |
+ |
+ |
5. Полнота системы:
Система функций полна, если она не содержится целиком ни в одном из классов Поста T0, T1, S, M, L.
6. Базисы:
Базисом называется полная система, из которой нельзя удалить ни одну функцию без потери полноты.
- {$f_1, f_2$} - полна, так как $f_1$ не сохраняет 0, а $f_2$ не сохраняет 1. Также $f_1$ и $f_2$ не самодвойственны, не монотонны и не линейны.
- {$f_1, f_4$} - не полна, так как $f_4$ сохраняет 0.
- {$f_2, f_3$} - не полна, так как не сохраняет 1.
- {$f_2, f_4$} - не полна, так как не сохраняет 1.
- {$f_3, f_4$} - не полна, так как не сохраняет 1.
