булева алгебра1
.pdf7Классы, сохраняющие константы
Определение 7.1 . Пусть f(x1, ..., xn) P2. f называют функцией, сохраняющей ноль, если f(0, ..., 0) = 0.
Множество всех функций сохраняющих 0 назовем T0:
T0 = {f(x1, ..., xn) | f P2, f(0, ..., 0) = 0}.
Утверждение 7.1 . Класс функций T0 замкнут.
Определение 7.2 . Пусть f(x1, ..., xn) P2. f называют функцией, сохраняющей единицу, если f(1, ..., 1) = 1.
Множество всех функций сохраняющих 1 назовем T1:
T1 = {f(x1, ..., xn) | f P2, f(1, ..., 1) = 1}.
Утверждение 7.2 . Класс функций T1 замкнут.
8Двойственность
Определение 8.1 . Пусть f(x1, ..., xn) P2. Двойственной функцией к функции f называется f (x1, ..., xn) = f(x1, ..., xn).
Пример 8.1 . Пусть f(x, y, z) = xy z. Тогда f (x, y, z) = x · y z = x · y z.
Определение 8.2 . Функция f(x1, ..., xn) P2 самодвойственная, если f (x1, ..., xn) = f(x1, ..., xn).
Обозначим за S множество всех самодвойственных функций:
S = {f | f(x1, ..., xn) P2, f (x1, ..., xn) = f(x1, ..., xn)}.
Пример 8.2 . Пусть f = x y, f = x y = xy. f 6= f и, следовательно, f не является самодвойственной.
Пример 8.3 . Пусть f функция голосования:
f(x, y, z) = xy xz yz.
11
f (x, y, z) = x · y x · z y · z = x · y · x · z · y · z =
= (x y)(x z)(y z) = (x xz xy yz)(y z) =
xy xz xyz xz xy xyz yz yz = xy xz yz xyz =
= xy xz yz = f(x, y, z).
Функция голосования самодвойственная.
Утверждение 8.1 (Принцип двойственности).
Пусть U = f(U1, ..., Un) формула задающая фукнцию F (x1, ..., xn),
где Ui формулы, задающие fi(xj1 , ..., xjki ), i = 1, n. Тогда, если Ui формулы, задающие fi , i = 1, n, то формула задающая F U может
иметь вид U = f (U1 , ..., Un).
Следствие 8.2 . Пусть f(x1, ..., xn) задана формулой U над множеством фукнций {0, 1, ¬, , }. Тогда f (x1, ..., xn) задается формулой, полученной из U заменой: нулей на единицы, единиц на нули, конъюнкций на дизъюнкции, дизъюнкций на конъюнкции.
Пример 8.4 . Пусть f(x, y, z) = (0 x)(y xz). Тогда
f (x, y, z) = 1 · x y(x z).
Утверждение 8.3 . Класс функций S замкнут. |
|
|
|
|||||||
Лемма 8.4 (О |
несамодвойственной |
функции). |
Пусть |
|||||||
f(x1, ..., xn) / S. Тогда, подставляя в f |
вместо аргументов x или |
|
|
|||||||
x |
||||||||||
можно получить константу. |
|
|
|
|
||||||
Доказательство. Пусть |
(α1, ..., αn), αi |
{0, 1}, такой |
набор, что |
|||||||
f(α1, ..., αn) = |
f( |
α |
1, ..., |
α |
n). |
Такой набор обязан существовать в силу |
несамодвойственности функции f.
Рассмотрим функцию ϕ(x) = f(xα1 , ..., xαn ). Тогда
ϕ(0) = f(0α1 , ..., 0αn ) = f(α10, ..., αn0) = f(α1, ..., αn) = = f(α1, ..., αn) = f(1α1 , ..., 1αn ) = ϕ(1).
Следовательно ϕ(x) константа.
12
9Монотонность
Определение 9.1 . |
Пусть |
αn = (α1, ..., αn), |
|
αi, βi {0, 1}. |
αn предшествует набору βn |
||
Говорят, что набор |
e |
e |
e |
|
|
||
после набора αn) и пишут αn βn, если |
|||
e |
e |
e |
|
βen = (β1, ..., βn),
(набор βen следует
α1 ≤ β1, α2 ≤ β2, ..., αn ≤ βn.
Будем говорить, что αen строго предшествует βen и обозначать αen βen, если αen βen и αen 6= βen.
Будем говорить, что αen непосредственно предшествует βen и обозначать αen 0 βen, если если αen βen и не существует набора γen такого, что αen γen βen.
Замечание 9.1 . , отношения частичного порядка.
Определение 9.2 . Пусть f(x1, ..., xn) P2. Функция f называется монотонной, если
|
|
αn βn |
= f(αn) ≤ f(βn). |
||||
Класс всех |
монотонных функций будем обозначать M. |
||||||
|
e |
e |
e |
e |
|||
Пример 9.1 . |
Функция x является монотонной. Функция |
|
не |
||||
x |
|||||||
монотонна. |
|
|
|
|
|
|
|
Утверждение 9.1 . Класс функций M замкнут.
Лемма 9.2 (О немонотонной функции). Пусть f(x1, ..., xn) / M. Тогда, подставляя в f вместо аргументов 0, 1, x можно получить x.
Доказательство. Так как f / M, существуют два набора αen и βen, такие что αen βen и f(αen) > f(βen). Очевидно, что f(αen) = 1 и f(βen) = 0.
Пусть αen отличен от βen в t позициях.
a) Пусть t = 1. Тогда для некоторого i верно, что
αen = (α1, ..., αi−1, 0, αi+1, ..., αn)
13
и
βen = (α1, ..., αi−1, 1, αi+1, ..., αn).
Определим функцию ϕ(x) следующим образом:
ϕ(x) = f(α1, ..., αi−1, x, αi+1, ..., αn).
Тогда,
ϕ(0) = f(α1, ..., αi−1, 0, αi+1, ..., αn) = 1
ϕ(1) = f(α1, ..., αi−1, 1, αi+1, ..., αn) = 0.
То есть ϕ(x) = x, что и требовалось доказать.
b) Пусть теперь t > 1. В этом случае построим последовательность наборов
αen = γen(0) γen(1) ... γen(t − 1) γen(t) = βen,
где каждая пара наборов γen(i − 1) и γen(i) отличаются только в одной позиции, i = 1, t. Это не трудно сделать, последовательно заменяя каждую позицию, в которой наборы αen и βen разтличаются с нуля на единицу. Поскольку f(αen) = 1 и f(βen) = 0, найдется такое k, что γen(k − 1) = 1 и γen(i) = 0. Такая ситуация возвращает нас к пункту a) доказательства.
10 Линейность
Определение 10.1 . Пусть f(x1, ..., xn) P2. Функция f линейная, если ее полином Жегалкина имеет вид
f(x1, ..., xn) = α0 α1x1 α2x2 ... αnxn.
Обозначим L класс всех линейных функций.
Пример 10.1 . x линейная функция. Функция x y не является линейной.
Утверждение 10.1 . Класс функций L замкнут.
14
Лемма 10.2 (О нелинейной функции). Пусть f(x1, ..., xn) / L. Тогда, подставляя в f вместо аргументов x, y, x, y и, возможно,
навешивая отрицание над f можно получить x y. |
|
V |
|
||||||||
|
|
{ |
|
} |
|
| | L |
|
|
/ L. |
||
Доказательство. Пусть |
f(x1, ..., xn) = |
I{1,...,n} α(I) |
i I xi и f |
||||||||
Тогда существует |
I |
|
1, ..., n |
|
: |
I |
≥ |
2 α(I ) |
= |
0 |
|
|
|
|
|
|
, |
6 |
. Не умаляя |
общности, положим {1, 2} I .
f(x1, ..., xn) =
= x1x2f1,2(x3, ..., xn) x1f1(x3, ..., xn) x2f2(x3, ..., xn) f0(x3, ..., xn),
причем α3, ..., αn: f1,2(α3, ..., αn) = 1. Действительно, такие α3, ..., αn существуют, поскольку, если бы f1,2(σ3, ..., σn) = 0, σ3, ..., σn {0, 1}, то функция f приняла бы вид
f(x1, ..., xn) = x1f1(x3, ..., xn) x2f2(x3, ..., xn) f0(x3, ..., xn),
что противоречит нашему предположению, что {1, 2} I и α(I ) = 1. Рассмотрим
ψ(x, y) = f(x, y, α3, ..., αn) = xy xf1(α3, ..., αn)
yf2(α3, ..., αn) f0(α3, ..., αn) = xy xβ yγ δ.
Теперь определим ϕ(x, y), как ϕ(x, y) = ψ(x γ, y β) γβ δ. Тогда
ϕ(x, y) = ((x γ)(y β) (x γ)β (y β)γ δ) γβ δ =
= xy xβ yγ γβ xβ γβ yγ γβ δ γβ δ = xy.
Таким образом, мы получили фукнцию ϕ(x, y) = x y, причем
ϕ(x, y) = f(x f2(α3, ..., αn), y f1(α3, ..., αn), α3, ..., αn)
f1(α3, ..., αn)f2(α3, ..., αn) f0(α3, ..., αn),
где добавление к x и y констант f2(α3, ..., αn) и f1(α3, ..., αn) равносильно навешиванию отрицания над переменной, если соответствующая константа равна 1, а добавление константы f1(α3, ..., αn)f2(α3, ..., αn) f0(α3, ..., αn) к f означает возможное навешивание отрицания над этой функцией.
15
11 Критерий полноты системы функций
Итак, мы рассмотрели пять классов функций T0, T1, S, M, L.
|
T0 |
T1 |
S |
M |
L |
¬x |
− |
− |
+ |
− |
+ |
0 |
+ |
− |
− |
+ |
+ |
1 |
− |
+ |
− |
+ |
+ |
xy |
+ |
+ |
− |
+ |
− |
Каждый из этих классов функций замкнут и, как можно видеть из таблицы, ни один не совпадает с P2.
Теорема 11.1 . Для полноты системы функций P P2 необходимо и достаточно, чтобы P не лежал полностью ни в одном из классов T0,
T1, S, M, L:
|
P 6 T0, P 6 T1, P 6 S, P 6 M, P 6 L. |
|
||||
Доказательство. |
Пусть f0, f1, fS, fM , fL |
P такие |
функции, |
что |
||
f0 / T0, |
f1 / T1, |
fS / S, |
fM / M, |
fL / L |
(некоторые |
из |
функций могут совпадать). Проведем доказательство в несколько этапов, последовательно доказав, что с помощью суперпозиций функций из P можно выразить систему {¬, }, чем и докажем полноту P.
1) Покажем, что с помощью f0, f1, fS можно получить 0 и 1.
a) Пусть f0(1, ..., 1) = 1. |
Пусть |
ϕ(x) |
= f0(x, ..., x). Тогда |
|||||
ϕ(0) = ϕ(1) = 1. |
Значит ϕ(x) = |
1 и, имея единицу, можно получить |
||||||
вторую константу 0 = f1(1, ..., 1). |
|
|
|
|
|
|||
b) Пусть теперь f0(1, ..., 1) |
= 0. |
Тогда |
ϕ(x) = f0(x, ..., x) = |
|
. |
|||
x |
||||||||
Подставляя в fS |
x и |
|
по лемме о несамодвойственной функции получаем |
|||||
x |
константу 0 или 1 и с помощью x получаем вторую константу.
2)По лемме о немонотонной функции, подставляя константы в fM можно получить ¬x.
3)Используя fL, константы и ¬x, по лемме о нелинейной функции можно получить x y.
Так как {¬, } полная системя функций, то и система P полная.
16
Пример 11.1 . Требуется проверить на полноту систему функций P = {0, 1, xy, x y z}. Рассмотрим принадлежность функций P классам T0, T1, S, M, L и заполним таблицу.
|
T0 |
T1 |
S |
M |
L |
0 |
+ |
− |
− |
+ |
+ |
1 |
− |
+ |
− |
+ |
+ |
xy |
+ |
+ |
− |
+ |
− |
x y z |
+ |
+ |
+ |
− |
+ |
Рассмотрим, например, проверку функции x y z: a) 0 0 0 = 0 x y z T0;
b) 1 1 1 = 1 x y z T1;
c) x y z = 1 (1 x) (1 y) (1 z) = x y z x y z S; d) (1, 0, 0) (1, 1, 0), но 1 = 1 0 0 > 1 1 0 = 0 x y z / M; e) Очевидно, функция является линейной: x y z L.
Теперь, заполнив и проанализировав таблицу, можно убедиться, что система функций P является полной, так как в каждом столбце, соответствующем одному из классов присутствует хотябы один минус. В то же время ни одно подмножество P полной системой не является, поскольку, если вычеркнуть в таблице хотябы одну строку, появится столбец не имеющий минуса.
17