ВУЗ:
Составители:
Рубрика:
3. Двойственность
Определение 4. Логическая функция
f
∗
(x
1
, . . . , x
n
) = ¬f(x
1
, . . . , x
n
)
называется двойственной функцией к функции f(x
1
, . . . , x
n
).
Очевидно, что таблица значений для двойственной функции f
∗
получается из таблицы значений функции f инвертированием (т.е. за-
меной 0 на 1 и 1 на 0) столбца функции и его переворачиванием, или же
только инвертированием, но всех столбцов — и функции, и аргументов.
x
1
x
2
x
3
f(x
1
, x
2
, x
3
) f
∗
(x
1
, x
2
, x
3
)
0 0 0 1 0
0 0 1 1 0
0 1 0 0 1
0 1 1 1 1
1 0 0 0 0
1 0 1 0 1
1 1 0 1 0
1 1 1 1 0
Двойственность обладает свойством взаимности.
Предложение 1. Функция f является двойственной к f
∗
, т.е.
f
∗∗
= f.
Упражнение 4. Докажите предложение 1.
Пример 8. ∨
∗
= ∧, ∧
∗
= ∨; 0
∗
= 1, 1
∗
= 0; ⊕
∗
=⇔, ⇔
∗
= ⊕.
Если f
∗
= f, то функция f называется самодвойственной. Тако-
ва, например, функция ¬ = ¬
∗
.
Теорема 3. Если F (x
1
, . . . , x
n
) = f(f
1
(x
1
, . . . , x
n
), . . . , f
m
(x
1
,
. . . , x
n
)), то F
∗
(x
1
, . . . , x
n
) = f
∗
(f
∗
1
(x
1
, . . . , x
n
), . . . , f
∗
m
(x
1
, . . . , x
n
)).
Имеем равенства
F
∗
(x
1
, . . . , x
n
) = ¬F (x
1
, . . . , x
n
) =
= ¬f(f
1
(x
1
, . . . , x
n
), . . . , f
m
(x
1
, . . . , x
n
)) =
= ¬f(¬¬f
1
(x
1
, . . . , x
n
), . . . , ¬¬f
m
(x
1
, . . . , x
n
)) =
= ¬f(¬f
∗
1
(x
1
, . . . , x
n
), . . . , ¬f
∗
m
(x
1
, . . . , x
n
)) =
= f
∗
(f
∗
1
(x
1
, . . . , x
n
), . . . , f
∗
m
(x
1
, . . . , x
n
)).
31
Страницы
- « первая
- ‹ предыдущая
- …
- 30
- 31
- 32
- 33
- 34
- …
- следующая ›
- последняя »
