Книги и конспекты / Шпоры / 17
.pdfФункции алгебры логики. Существенные и фиктивные переменные. Равные
функции. Элементарные функции и их свойства. Суперпозиция функций.
Пусть U = {u1, u2, ..., um, ...} —исходный алфавит переменных.
Будем рассматривать функции f(ui1, ui2, ..., uin)(uij = uik при j = k), аргументы которых определены на множестве E2 = {0, 1},и такие, что f(α1, α2, ..., αn) E2,
когда αi E2(i = 1, 2, ..., n).Эти функции будем называть функциями алгебры логики или булевыми функциями. В качестве переменных будем использовать символы x, y, z, ... ,
а также эти символы с индексами.
Обозначим через P2 систему функций алгебры логики над алфавитом U, содержащую константы 0 и 1. Определение: Функция f(x1, ..., xi−1, xi, xi+1, ..., xn) из P2 зависит существенным
образом от аргумента xi, если существуют такие значения α1, ..., αi−1, αi+1, ..., αn пере-
менных x1, ..., xi−1, xi+1, ..., xn, что f(α1, ..., αi−1, 0, αi+1, ..., αn) =f(α1, ..., αi−1, 1, αi+1, ..., αn).
В этом случае переменная xi называется существенной. Если xi не является существенной переменной, то она называется несущественной или фиктивной.
Определение: Функции f1(x1, ..., xn) и f2(x1, ..., xn) называются равными,
если функцию f2 можно получить из f1 путем добавления или изъятия фиктивных аргументов.
Функции тождественно равные 0 и тождественно равные 1 не содержат существенных переменных. Приведем примеры ««элементарных»» функций
1)f1(x) = 0 — константа 0;
2)f2(x) = 1 — константа 1;
3)f3(x) = x — тождественная функция;
4)f4(x) = x¯ — отрицание x;
5)f5(x1, x2) = (x1&x2) — конъюнкция x1 и x2 или логическое умножение;
6)f6(x1, x2) = (x1 x2) — дизъюнкция x1 и x2 или логическое сложение;
7)f7(x1, x2) = (x1 → x2) —импликация x1 и x2 или логическое следование;
8)f8(x1, x2) = (x1 + x2) — сложение по mod 2;
9)f9(x1, x2) = (x1/x2) —функция Шеффера.
Вследующих таблицах приводятся значения перечисленных функций.
Здесь (x1&x2) = min(x1, x2) = (x1 · x2), (x1 x2) = max(x1, x2).
|
|
|
|
|
x |
0 |
|
1 |
x |
|
x¯ |
|
||
|
|
|
|
|
0 |
0 |
|
1 |
0 |
|
1 |
|
|
|
|
|
|
|
|
1 |
0 |
|
1 |
1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
x1 |
x2 |
(x1&x2) |
(x1 x2) |
(x1 → x2) |
|
|
(x1 + x2) |
|
|
(x1|x2) |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
0 |
0 |
0 |
0 |
1 |
|
|
|
|
0 |
|
|
1 |
||
0 |
1 |
0 |
1 |
1 |
|
|
|
|
1 |
|
|
1 |
||
1 |
0 |
0 |
1 |
0 |
|
|
|
|
1 |
|
|
1 |
||
1 |
1 |
1 |
1 |
1 |
|
|
|
|
0 |
|
|
0 |