Книги и конспекты / Горьковой Дискретная Математика

где пересечение берется над C4.

В соответствии с вновь введенными обозначениями,

G k будет иметь вид

W4

1

Zk(x41)Zk(x21 ), k(x12)Zk(x41 )Zk(x32)},

где (G r) = ( 3r ) ( 1r ) ( 2r ) ( 3r ) = 1 2 k W3 k x Zk x Zk x Rk x , r , .

Положим

2(x31 )Z4(x22)Z1(x31)Z3(x22), 1(x21 )Z2(x11), 3(x12)Z4(x32)}.

На рисунке 5.6. изображен граф GΠ(5)(x), где ребрами обозначены Z-ки, связывающие соответствующие

90

k(xij ), а светлыми кружочками обозначены вершины, смежные x C5.

Теорема 31. Если G 5-критический граф, то он содержит подграф, с точностью до гомоморфизма

го одну вершину x. В силу 3-приведенности π(5), вершина x C5 опирается над каждой парой классов (Ci, Cj ), i > j, i, j {1, 4}, по крайней мере на одну

Z-ку. В частности, так как π(4) = {C1 , C2, C3 , C4} приведена относительно C4, то предположим, что x C5

опирается на -ки 1(Π1 ) = (1( 41) 1( 11)) 2(Π1 ) =

Z 41 C41 Z C41 , 42

(2( 41 ) 2( 21)) 3(Π2 ) = (3( 42) 3( 32)) 4(Π2 ) =

C42 Z C42 , 43 C43 Z C43 , 41

(4( 42 ) 4( 12)).

C41 Z C41

Для каждой из указанных Z-к k(Πrj ), существует

4

по крайней мере еще три -ки (Π1 ) (Π2 ) и (Π2 )

Z k 42 , k 43 k 41

приведенной последовательно относительно C5 и C4, то согласно теореме 31 имеем (xS1(x11 ))R(2(x21 )Sx).

В силу тех же причин для раскраски π(5) − C1 имеем 2(x21)R3(x32 ), а для раскраски π(5) − C2 имеем

3(x32 )R4(x12).

Так как фактор-степень x инвариантна относительно любых преобразований над (C1, C2 , C3, C4 ), то и инверсия Z-ки 1(x11)Z1(x31 ) не должна изменить фактор-

91

степень x. А это будет тогда, когда будет выполняться, с точностью до гомоморфмзма, соотношение

[xS2(x21 )]Z2(x11)Z1(x21 )R1(x31)Z4(x22 )Z[4(x12)Sx]. (5.2.3)

Фактор-степень x C5 должна быть инвариантна и относительно инверсии Z-ки [xS1(x11 )]R[2(x21 )Sx]. В этом случае должно выполняться (с точностью до гомоморфизма) соотношение

[xS1(x11 )Z1(x31)Z3(x22)R[3(x32 )Sx], (5.2.4)

так как (как и в первом случае над (C1 , C2)) вершина x должна опираться над (C2, C3 ) после указанных инверсий на Z-ку.

Точно так же инверсия Z-ки 3(x32)R4(x12) влечет (с точностью до гомоморфизма) соотношение

[xS4(x12 )]Z4(x22 )Z2(x31)R[2(x21 )Sx]. (5.2.5)

Итак, из (5.2.3), (5.2.4), (5.2.5) имеем, с точностью до гомоморфизма,

2(x31)Z4(x22 )Z1(x31)Z3(x22)

и

1(x21)Z2(x11), 3(x12 )Z4(x32).

Учитывая, что 5 опирается на -ки 1(Π1 ) 2(Π1 ) x C Z 41 , 42 ,

3(Π2 ) 4(Π2 ) имеем

43 , 41 ,

1(x41)SxS1(x11 ), 2(x41)SxS2(x21 ), 3(x41)SxS3(x32 ),

4(x41)SxS4(x12 ).

Что и требовалось.

92

Теорема 32. Граф GΠ(5)(x) содержит подграф, стягиваемый к F5.

Д о к а з а т е л ь с т в о. Пусть GΠ(5)(x) задает-

ся формулой (5.2.2). Рассмотрим G k при = 1. Так

W(4) k

как 1(x11 )SxS1(x41 ), то имеются некоторые вершины

y1 1(x41 ) и z1 1(x11) такие, что y1SxSz1 . Из того, что (xS2(x21 ))Z2(x11 )Z1(x21), следует существование прос-

той цепи из вершины x C5 в вершину z2 1(x21). А из того, что (xS3(x32 ))R3(x22 )Z1(x31) существует простая цепь из вершины x C5 в вершину z3 1(x31). Все

указанные простые цепи не имеют общих вершин.

Так как 1(x41)Z1(x11), 1(x41)Z1(x32 )R1(x22)Z1(x31),

1(x41 ) Z1(x21), то существуют непересекающиеся простые цепи из вершины y1 в вершины z1, z2 и z3, принад-

соответственно.

А так как 1(x11)Z1(x31 )R1(x21)Z1(x11 ), то существует простой цикл, содержащий вершины z1′ 1(x11), z2′

1(x21 ), z3′ 1(x31). Очевидно, z1 и z1′ , z2 и z2′ , z3 и z3′

связаны непересекающимися простыми цепями. Таким образом, вершины x, y1, z1′ , z2′ , z3′ вместе с простыми цепями, связывающими их, образуют подграф графа G, стягиваемый к F5.

93

6

АЛГЕБРА ЛОГИКИ

6.1. Функции алгебры логики

Пусть U = {u1, u2, ..., um, ...} —исходный алфавит переменных. Будем рассматривать функции f (ui1 , ui2 , ..., uin )(uij =6 uik при j =6 k), аргументы которых определены на множестве E2 = {0, 1},

и такие, что f (α1, α2, ..., αn) E2, когда αi E2(i = 1, 2, ..., n).

Эти функции будем называть функциями алгебры логики или булевыми функциями. В качестве переменных будем использовать символы x, y, z, ... , а также эти символы с индексами. Функции алгебры логики будем задавать с помощью таблиц

Обозначим через P2 систему функций алгебры логики над алфавитом U , содержащую константы 0 и 1.

О п р е д е л е н и е 53. Функция 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) =6 f (α1, ..., αi−1, 1, αi+1, ..., αn).

В этом случае переменная xi называется существенной. Если xi не является существенной переменной, то она называется несущественной или фиктивной.

90

О п р е д е л е н и е 54. Функции 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).

91

6.2.Формулы и функции

Оп р е д е л е н и е 55. Пусть P — некоторое подмножество функций из P2.

a)Б а з и с и н д у к ц и и. Каждая функция f (x1, ..., xm) из P называется формулой над P.

б) И н д у к т и в н ы й п е р е х о д. Пусть f (x1, ..., xm) — функция из P и A1, ..., Am — выражения, являющиеся либо формулами над P, либо символами переменных из U . Тогда выражение f (A1, ..., Am) называется формулой над P.

П р и м е р 20. Пусть P — множество ««элементарных»» функций. Следующие выражения являются формулами над P:

1){[(x1x2) + x1] + x2};

2)[¯xx(x2 + x3)];

3){x1 [(x2 → x3)(x3 → x2)]}.

Вдальнейшем запись A[f1, ..., fs] означает, что формула A построена из f1, ..., fs. А запись A(x1, ..., xn) означает, что при построении формулы A использовались переменные x1, ..., xn. Пусть A — произвольная формула над P, тогда формулы, которые использовались для ее построения, будем называть подформулами формулы A.

О п р е д е л е н и е 56. Говорят, что формула B = B[g1, ..., gs], gi = gi(x1, ...xn) имеет то же строение, что и фор-

мула A = A[f1, ..., fs], fi = fi(x1, ..., xn), i = 1, s, если формула B

Пр и м е р 21.

1)D = {x1, (x1&x2)}, A = [x1&(x2&x3)];

2)D = {x1, (x1 → x2)}, B = [x1 → (x2 → x3)].

Очевидно, что A и B имеют одинаковое строение.

Строение формулы будем обозначать через C и писать A = C[f1, ..., fs]. Каждая формула однозначно определяется своим строением и упорядоченной совокупностью {f1, f2, ..., fs}.

Сопоставим теперь каждой формуле A(x1, ..., xn) над P функцию f (x1, ..., xn) из P2 с помощью индукции следующим образом.

92

а) Б а з и с и н д у к ц и и. Если A(x1, ..., xn) = f (x1, ..., xn), где f P, то формуле A(x1, ..., xn) сопоставим функ-

цию f (x1, ..., xn).

б) И н д у к т и в н ы й п е р е х о д. Пусть A(x1, ..., xn) = f0(A1, ..., Am), где Ai(i = 1, ..., m) являются либо формулами над

P, либо символами переменной xj(i). Тогда по предположению индукции Ai сопоставлена либо функция fi из P2, либо тождественная функция fi = xj(i). Сопоставим формуле A(x1, ...xn) функцию

f (x1, ..., xn) = f0(f1, ..., fm).

Если функция f соответствует формуле A, то говорят, что формула A реализует функцию f .

Функцию f , соответствующую формуле A, будем называть суперпозицией функций из P, а процесс получения функции f из P будем называть операцией суперпозиции.

П р и м е р 22. Пусть

f3(x1, x2, x3) = {x1 [(x2 → x3)(x3 → x2)]}

функция, соответствующая формуле из примера 17.

Для нахождения функции f3 , будем искать те наборы значений переменных x1, x2, x3, на которых функция принимает значение 1. Очевидно, это равносильно определению значений переменных, при которых формула

{x1 [(x2 → x3)(x3 → x2)]}

равна 0. Последнее имеет место при x1 = 0 и в тех случаях, когда [(x2 → x3)(x3 → x2)] обращается в 0. Наконец, формула [(x2 → x3)(x3 → x2)] обращается в 0, когда по крайней мере одна из формул (x2 → x3), (x3 → x2) обращается в 0, что имеет место при x2 = 1, x3 = 0, или при x2 = 0, x3 = 1. Таким образом, f (x1, x2, x3) равна 1 на наборах (001) и (010).

6.3. Эквивалентность. Принцип двойственности.

О п р е д е д е л е н и е 57. Формулы A и B над P

называются эквивалентными, в этом случае мы пишем A = B, если соответствующие им функции fA и fB равны.

П р и м е р 23. 0 = (x&x),

(x1(x2 + x3)) = {x1 [(x2 → x3)(x3 → x2)]},

93

(x → y) = (y → x).

Обозначим через (x1 ◦ x2) любую из функций (x1&x2), (x1

x2), (x1 + x2).

1. Функция (x1 ◦ x2) обладает свойством ассоциативности:

((x1 ◦ x2) ◦ x3) = (x1 ◦ (x2 ◦ x3)).

2. Функция (x1 ◦ x2) обладает свойством коммутативности:

(x1 ◦ x2) = (x2 ◦ x1).

3. Для конъюнкции и дизъюнкции выполняются дистрибутивные законы:

((x1 x2)&x3) = ((x1&x3) (x2&x3)), ((x1&x2) x3) = ((x1 x3)&(x2 x3)).

4.Имеют место следующие соотношения между отрицанием, конъюнкцией и дизъюнкцией:

x = x, (x1&x2) = (x1 x2), (x1 x2) = (x1&x2).

5.Выполняются следующие свойства конъюнкции и дизъюнк-

ции:

С помощью приведенных равенств легко осуществлять эквивалентные преобразования и, тем самым, получать новые тождества.

П р и м е р 24.

x1 x1x2 = x1 · 1 x1x2 = x1(x2 x2) x1x2 =

=x1x2 x1x2 x1x2 = x1x2 x1x2 x1x2 =

=x1x2 x1x2 = x1(x2 x2) = x1 · 1 = x1.

Таким образом, x1 x1x2 = x1, т.е. получаем правило поглощения произведения x1x2 множителем x1. Здесь x1x2 = x1&x2.

94

Существует еще один способ получения тождеств. Он основан на использовании так называемого принципа двойственности.

О п р е д е л е н и е 58. Функция [f (x1, ..., xn)] = f (x1, ..., xn),

называется двойственной функцией к функции f (x1, ..., xn). Для простоты будем обозначать двойственную функцию через

f (x1, ..., xn).

Легко видеть, что функция 0 двойственна 1, функция 1 двойственна 0, функция x двойственна x, функция x двойственна x,

функция x1&x2 двойтсвенна x1 x2, функция x1 x2 двойственна x1&x2.

Из определения двойственности вытекает, что

f = (f ) = f,

т.е. функция f является двойственной к f .

Из теоремы вытекает П р и н ц и п д в о й с т в е н н о с т и. Если форму-

ла A = C[f1, ..., fs] реализует функцию f (x1, ..., xn), то формула

95