Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/magazine/archive/v2(1-4)/shakirov.pdf Дата изменения: Fri Nov 7 11:27:10 2008 Дата индексирования: Mon Oct 1 23:27:39 2012 Кодировка: Windows-1251

О предикатной эквивалентности формул алгебры логики
Э.Э. Гасанов, А.А. Шакиров
Для описания геометрических фигур можно использовать формулы алгебры логики в стандартном базисе: дизъюнкция, конъюнкция и отрицание, в которых символы переменных заменены на предикаты, описывающие базисные фигуры. В работе исследуется отношение P -равенства формул алгебры логики, введенное в [1], которое подразумевает равенство формул в случае равенства описываемых фигур. Устанавливается, что при надлежащем подборе множества базисных фигур P отношения P -равенства и обычного равенства формул являются эквивалентными. Оценивается сложность описания базиса P , при котором эта эквивалентность может быть достигнута.

1 Введение
В компьютерной математике важную роль играют формальные языки, с помощью которых можно описывать объекты, подлежащие изучению. Такие языки могут использоваться, например, для описания геометрических фигур. Мы рассмотрим этот подход для описания геометрических объектов. Суть его состоит в следующем. Задано некоторое множество P базисных исходных фигур p, из которых с помощью теоретико-множественных операций , , получается множество P, вообще говоря, новых геометрических объектов (фигур). В работе рассматриваются фигуры, задаваемые на плоскости. В этом случае базисные фигуры можно описывать двухместными предикатами, область истинности которых образует такую фигуру на плоскости. Тогда задание комбинаций теоретико-множественных операций над такими фигурами интерпретируется как формула логики предикатов, построенная из указанных предикатов и логических связок , , ѓ, соответствующих операциям , , , что приводит к формальному языку . Каждая формула логики предикатов описывает некоторую геометрическую фигуру. Пусть заданы формулы A(X1 , . . . , Xn ), B (X1 , . . . , Xn ) из и


подстановка

=

1 2 ... i1 i2 . . .

m im

.

Множество всех m-подстановок обозначим через m . Пусть M m . Если при любой подстановке M предикатов из P вместо переменных (X1 , . . . , Xn ) в формулы A и B получаемые формулы, называемые P -формулами, описывают совпадающие фигуры, то будем говорить, что формулы A и B являются (M , P )-равными. Это отношение равенства разбивает множество на классы эквивалентности, где каждый класс содержит только (M , P )-равные формулы. Обозначим это разбиение через DM ,P . Отметим, что обычное равенство формул разбивает множество на классы эквивалентности, где каждый класс содержит только равные формулы. Обозначим это разбиение через D. Здесь рассматривается вопрос о нахождении такого множества базисных фигур P = {p1 , . . . , pm }, чтобы порождаемое им разбиение DM ,P совпадало с разбиением D. Используемые ниже терминология и факты берутся из [2],[3]. Авторы выражают благодарность В.Б.Кудрявцеву за постановку задачи и А.С.Строгалову за внимание и помощь в работе.

2

Основные понятия и результаты

Пусть R и N множества действительных и натуральных чисел, соответственно; E2 = {0, 1}. R2 двумерное евклидово пространство и B n единичный n-мерный куб, т.е. B n состоит из всех векторов (1 , 2 , . . . , n ), где при i = 1, 2, . . . , n имеет место i E2 , для которых справедлива евклидова метрика. Пусть U = {u1 , u2 , . . . , un , . . . } и W = {w1 , w2 , . . . , wn , . . . } алфавиты переменных принимающих значения из R, и из E2 , соответственно. Далее для простоты вместо un и wn будем использовать знаки x, y , и X, Y , соответственно, возможно, с индексами. Пусть X1 X2 , X1 X2 , ѓX суть булевы функции, называемые, соответственно, конъюнкцией, дизъюнкцией и отрицанием и B множество этих функций. Обычным образом введем понятие формулы над B . Для E2 обозначим через X булевскую функцию такую, что ѓX, если = 0, и X, если = 1. Для упрощения записи в некоторых формулах будут опускаться скобки, как это принято в алгебре логики. Переменная Xi (1 i n) функции F (X1 , . . . , Xi-1 , Xi , Xi+1 , . . . , Xn ) называется существенной, если можно указать такие наборы

232


n = (1 , . . . , i-1 , 0, i+1 , . . . , n ) и n = (1 , . . . , i-1 , 1, i+1 , . . . , n ), соседние
по i-той координате, что F (n ) = F ( n ). В противном случае переменная Xi называется фиктивной. Две функции F (X1 , . . . , Xn ) и G(Y1 , . . . , Ym ) из P2 называются равными, если множества их существенных переменных совпадают и на любых двух наборах n и m , различающихся, может быть, только значениями несущественных переменных, выполнено






F (n ) = G( m ).
Пусть B множество всех формул над B и B (X1 , . . . , Xn ) (или просто B (n)) множество всех формул над B , реализующих функции, существенно зависящие от переменных X1 , . . . , Xn . Формулы A и B из B называются равными, если они реализуют равные функции. Это отношение равенства разбивает B на классы эквивалентности D, которые содержат точно все формулы, которые реализуют равные функции. Если A формула из B , то через Aсднф обозначим совершенную дизъюнктивную нормальную форму, равную A. Открытое множество в R2 будем называть также областью или фигурой. Пустое множество в R2 будем называть пустой фигурой. Рассмотрим множество базисных фигур в R2 G = {G1 , G2 , . . . , Gm }. Каждой фигуре Gi сопоставим предикат pi (x1 , x2 ), областью истинности которого является Gi , i = 1, 2, . . . , m. Пусть P = {p1 (x1 , x2 ), p2 (x1 , x2 ), . . . , pm (x1 , x2 )} и A(X1 , X2 , . . . , Xn ) B (n). Подставим в A вместо каждой переменной Xi предикат pj из P . Данную операцию назовем полной подстановкой (или просто подстановкой), и полученное выражение A(p1 , p2 , . . . , pm ) назовем P -формулой. Поскольку описания фигуры G как в виде открытого подмножество плоскости, так и в виде предиката p, область истинности которого есть это подмножество G, являются тавтологичными, то мы далее будем использовать предикат p для обозначения фигуры G и будем говорить "фигура p"несмотря на то, что p предикат, описывающий фигуру G. Свяжем с каждой P -формулой A(p1 , p2 , . . . , pm ) некую фигуру





FA(p

1

,p2 ,...,pm )

R

2

так, как это было сделано в [1], и будем говорить, что P -формула A(p1 , p2 , . . . , pm ) задает (или описывает) фигуру FA(p1 ,p2 ,...,pm ) . Фигуры F1 и F2 называются равными (пишем F1 = F2 ), если они совпадают в R2 как множества. P P -формулы A(P ) и B(P ) назовем P -равными (пишем A(P ) = B (P )), если они задают равные фигуры.

233


Пусть M некоторое подмножество множества всех m-подстановок m . Формулы A и B называются (M , P )-равными, (пишем A = B), если при любой соответственно одинаковой подстановке M в них предикатов из P вместо переменных получаемые P -формулы являются P -равными. Отношение (M , P )-равенства на множестве B (n) разбивает это множество на классы эквивалентности DM ,P , которые содержат точно все такие формулы, которые являются (M , P )-равными. Будем говорить, что множество базисных фигур P обладает M -свойством, если отношения равенства булевских формул и (M , P )-равенства эквивалентны, т. е. разбиения D и DM ,P совпадают, или, что то же самое, для любых двух формул A, B B (n) верно A = B тогда и только тогда, когда A = B . Множество всех граничных точек фигуры p назовем границей p фигуры p. Отрезком назовем часть прямой, заключенной между двумя различными точками этой прямой, при этом эти точки называются концами отрезка. Если x1 , x2 концы отрезка, то отрезок обозначим через [x1 , x2 ]. Последовательность отрезков в R2
M ,P M ,P

[x1 , x2 ][x2 , x3 ] . . . [xi

-1

, xi ]

назовем ломаной, и замкнутой ломаной, если x1 = xi . Не имеющую самопересечений замкнутую ломаную, состоящую из n отрезков, назовем n-угольником, а отрезки этой ломаной сторонами n-угольника. Область в R2 , граница которой является n-угольником, называется n-угольной областью. Заметим, что для любого невырожденного n-угольника существует две n-угольные области, границей которых он является (внешняя и внутренняя). Если p некоторая фигура, то функцию

h(p) =

1, 0,

если p 0 если p 0

назовем предикатом пустоты множества p. Пусть p некоторая фигура. Через p1 обозначим фигуру p, а через p0 дополнение к фигуре p, т.е. фигуру p. Пусть 1 2 ... m = i1 i2 . . . im

m-подстановка из m и P = {p1 , . . . , pm } множество базисных фигур. Тогда булевскую функцию P (1 , . . . , m ) = h(p
1 i1

p

2 i2

ћћћ p

m im

)

234


назовем определяющей функцией множества базисных фигур P относительно подстановки . Пусть M = {1 , . . . , k } m и P = {p1 , p2 , . . . , pm } множество базисных фигур, тогда булевскую функцию



P M

= P1

P 2

ћ ћ ћ Pk

назовем определяющей функцией множества базисных фигур P относительно множества подстановок M .

Теорема 1 Пусть M m , тогда множество базисных фигур P =
{p1 , p2 , . . . , pm } обладает M -свойством тогда и только тогда, когда P 1. M

множество базисных фигур Pn = {p1 , p2 , что для каждого i {1, 2, . . . , n} фигура p где 4, mi = 2i-1 - mi-1 ,

Теорема 2 Для любого n из N если M n и |M | = 1, то существует такое

. . . , pn }, обладающее M -свойством, i является mi -угольной областью,

если i = 1, 2, 3 если i > 3.

(1)

Теорема 3 Для любого m из N существует такое число n в N , что ес-

ли M n и |M | = 1, то никакое множество базисных фигур Pn = {p1 , p2 , . . . , pn }, где при i = 1, 2, . . . , n каждая область pi является ki -угольной и ki m, не может обладать M -свойством.
Обозначим через следующую подстановку

=

1 2 ... 1 2 ...

m m

.

P = {p1 , p2 , . . . , pn } справедливо P n 1 тогда и только тогда, когда на каждом слое куба B n существует хотя бы один набор такой, что P () = 1.

Теорема 4 Для любого n из N и произвольного множества базисных фигур

Теорема 5 Для любого n из N и произвольного множества базисных фигур
Pn = {p1 , p2 , . . . , pn }, такого, что pn p обладает n -свойством.
n-1

ћ ћ ћ p1 , справедливо, что P

n

235


3 Критерий M -свойства
Пусть P = {p1 , p2 , . . . , pm } некоторое множество базисных фигур и = (1 , 2 , . . . , m ) из B m , тогда пересечение


p = p



1

1

p

2

2

ћ ћ ћ pm m

будем называть элементарной областью (э. о.) (или элементарной фигурой), с кодом . Приведем доказательство теоремы 1. Необходимость. Пусть множество базисных фигур P обладает M -свойством. Докажем, что P 1. M Предположим, что существует такой набор = (1 , . . . , m ) B m , что имеет место P () = 0. Это означает, что для любого M справедливо M P () = 0, т. е. при любой подстановке M предикатов из P вместо пере менных элементарной конъюнкции (э. к.) X1 1 X2 2 ћ ћ ћ Xmm получающаяся формула задает пустую фигуру. Теперь, если взять формулы A и B из B (m) такие, что A = B и формулы Aсднф , Bсднф отличаются именно по э. к. X1 1 X2 2 ћ ћ ћ Xmm , то приходим к равенству A = B, что означает, что множество P не обладает M -свойством. Но это противоречит условию теоремы, что и доказывает необходимость. Достаточность. Пусть P 1. Докажем тогда, что множество базисных M фигур P обладает M -свойством. Предположим, что множество P не обладает M -свойством. Тогда существуют такие формулы A и B из B (m), что A = B и A = B. Пусть формулы Aсднф , Bсднф отличаются по э. к.
K = X1 1 X2 2 ћ ћ ћ Xmm . M ,P M ,P

По предположению получим, что э. к. K при любой подстановке M предикатов из P вместо переменных K это формула задает пустую фигуру. Это означает, что для любого M P (1 , . . . , m ) = 0, откуда P (1 , . . . , m ) = M 0. Но это противоречит условию, что и доказывает достаточность. Тем самым теорема 1 доказана.

4 Случай одноэлементного множества подстановок
В этом разделе мы докажем теоремы 2 и 3.

Доказательство теоремы 2
236


Говорим, что две многоугольные области p , p являются соседними, если их пересечение пусто, а пересечение их границ содержит невырожденную ломаную. Пусть n = (V , R) некоторый граф, где V = {v1 , v2 , . . . , vn } множество вершин, а R-множество ребер. Если V конечное множество, то граф n называется конечным. Про ребро (vi , vj ) будем говорить, что оно соединяет вершины vi и vj . Последовательность ребер {(vi1 , vi2 ), (vi2 , vi3 ), . . . , (vis-1 , vis )} графа n называется путем, соединяющим вершины vi1 и vis . А если vi1 = vis , то путь называется циклом. Путь называется гамильтоновым, если он проходит через каждую вершину графа n в точности по одному разу. Если в гамильтоновом пути первая вершина совпадает с последней вершиной, то путь назовем гамильтоновым циклом. Если {(vi1 , vi2 ), (vi2 , vi3 ), . . . , (vin-1 , vin )} гамильтонов путь, то договоримся обозначать его последовательностью вершин, через которые он проходит, т. е. через vi1 , vi2 , . . . , vin-1 , vin . Наборы = (1 , 2 , . . . , n ) и = (1 , 2 , . . . , n ) из B n назовем соседними, если отличаются ровно по одной координате. Единичный куб B n , принято изображать в виде графа, в котором множество вершин совпадает с множеством B n , и всякие две вершины соединяются ребром, если они соседние. Этот граф также будем обозначать через B n . Далее для простоты в записи набора = (1 , 2 , . . . , m ) B m будем опус кать круглые скобки и запятые и обозначать = 1 2 . . . m . Пусть = 1 2 . . .


1 2 . . . m 1 2 . . . k B


m и = mB m+k , называемый

1 2 . . .

k

B k , тогда набор


конкатенацией наборов и , обо-

значаем через . Известно, что в единичном кубе B n существует гамильтонов путь. Приведем пример некоторого гамильтонового пути в B n , который определим индукцией по n. 1) Базис индукции. Пусть n = 2. Путь 00, 01, 11, 10 является гамильтоновым путем в B 2 . 2) Индуктивный переход. Пусть в кубе B n-1 мы построили гамильтонов путь, который обозначим

1, 2, 3, 4, . . .
Легко видеть, что путь









2n-1 -1 , 2n-

1

.

1 0, 1 1, 2 1, 2 0, 3 0, . . .
является гамильтоновым в кубе B n .











2

n-1

-1

0,

2

n-1

-1

1,

2n-

1

1,

2n-

1

0

237

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

Лемма 1 Для любого n из N существует такое множество базисных фигур Pn = {p1 , p2 , . . . , pn }, что для любого = (1 , 2 , . . . , n ) из B n , э.о.
p = p


1

1

p

2

2

ћћћ p

n

n

непустая, и каждая фигура pi (i = 1, 2, . . . , n) является при i = 1, 2, . . . , n, mi -угольной областью, где mi удовлетворяет соотношению (1). Доказательство леммы. Будем считать, что у нас на плоскости задана ортогональная система координат. Для произвольного n 2 обозначим через
0, 1, 2, . . .
2n -1

(2)

опорный гамильтонов цикл в B n По индукции докажем следующее утверждение. Для любого n 2 существует такой базис {p1 , p2 , . . . , pn }, что 1. Для любого i {1, 2, . . . , n} область pi является mi -угольной областью, где mi удовлетворяет соотношению (1), и стороны многоугольников pi параллельным осям координат. 2. Для любого B n э. о. p непустая, односвязная многоугольная область, стороны границ которой параллельны осям координат. 3. Для любого i {0, 1, . . . , 2n - 1} p ются соседними областями.
i





иp

j

(где j = (i + 1)(mod 2n )) явля

4. Если мысленно ввести линию, переходящую от p 0 к p 1 , затем к p 2 и так далее вдоль опорного гамильтонового цикла, и в конце вернуться из p 2n -1 к p 0 , то получится движение против часовой стрелки, при этом внутренность фигуры очерченной этой мысленной линией будет оставаться слева. 5. Существует множество отрезков
2 [x0 , x0 ], [x1 , x1 ], . . . , [x1 12 12
n

-1

,x

2n -1 2

],

которые мы назовем опорными, таких, что для любого i {0, 1, . . . , 2n - 1} отрезок [xi , xi ] принадлежит общей границе сосед12 них областей p и [xj , xj ], 12
i

и p j , где j = (i + 1)(mod 2n ); при этом отрезки [xi , xi ] 12



238




p

10

Фигура p1

x4 r p11 x1 r p00
r r
3

x
r

2

x

p

01

Фигура p2

x

5

Рис. 1

ћ либо перпендикулярны друг другу и их концы касаются, т. е. (xi = 1 xj ) или (xi = xj ) или (xi = xj ) или (xi = xj ), 1 2 2 1 2 1 2 ћ либо [xi , xi ] и [xj , xj ] взаимно параллельны и имеют одинаковую 12 12 длину и расположены точно напротив друг друга,
и прямоугольник, имеющий в качестве сторон отрезки [xi , xi ] и [xj , xj ] 12 12 целиком лежит внутри одной э. о. 6. Количество таких чисел i {0, 1, . . . , 2n - 1}, что пара опорных отрезков [xi , xi ] и [xj , xj ], где j = (i + 1)(mod 2n ), перпендикулярна друг другу, 12 12 равно mn+1 . 1). Базис индукции. Пусть n = 2. Пусть p1 и p2 фигуры, изображенные на рисунке 1. Легко видеть, что условия 1 и 2 утверждения индукции выполняются. Интересующий нас гамильтонов цикл имеет вид: 00,01,11,10. С учетом этого легко проверяется и пункты 3 6, где в качестве опорных отрезков можно взять следующие отрезки [x1 , x2 ],[x2 , x3 ],[x2 , x4 ],[x2 , x5 ]. 2) Индуктивный переход. Пусть n = k , и базисное множество {p1 , p2 , . . . , pk } удовлетворяет условиям утверждения индукции для n = k . Пусть заданы э. о.

p0 , p1 , . . . , p









2k -1

,

(3)

построенные с помощью базисных фигур {p1 , p2 , . . . , pk }. Построим фигуру pk+1 так, чтобы базис {p1 , p2 , . . . , pk+1 } удовлетворял условиям утверждения индукции для n = k + 1. Пусть опорный гамильтонов цикл при n = k имеет вид (2).

239


жество опорных отрезков

Построение фигуры p

k+1

. По предположению индукции существует мноk

[x0 , x0 ], [x1 , x1 ], . . . , [x2 12 12 1

-1

,x

2k -1 2

].

(4)

Отмечаем середины каждого опорного отрезка и через эти точки проводим перпендикулярные прямые. Количество таких прямых равно 2k . Если среди опорных отрезков имеются параллельные отрезки [xi , xi ] и [xj , xj ], где 12 12 j = (i + 1)(mod 2k ), то две прямые, которые проходят через середины этих параллельных отрезков, совпадают. В таких случаях вместо двух прямых рассматривается одна прямая. Прямые пересекаются между собой в некоторых точках. В качестве сторон pk+1 -ой фигуры берутся такие отрезки прямых, которые проходят через отмеченные точки, и их концами являются точки пересечения двух прямых, проведенных через точки лежащие в соседних опорных отрезках. Легко видеть, что число углов фигуры pk+1 равно количеству таких чисел i {0, 1, . . . , 2k-1 - 1}, что пара опорных отрезков [xi , xi ] и [xj , xj ], где 12 12 j = (i + 1)(mod 2k ), перпендикулярна друг другу. Откуда согласно пункту 6 утверждения индукции число углов фигуры pk+1 равно mk+1 . По предположению индукции, все стороны границы pk -ой фигуры параллельны к осям координат. Тогда по построению pk+1 -ой фигуры видно, что стороны границы pk+1 -ой фигуры расположены перпендикулярно к сторонам границы фигуры pk . Это означает, что стороны границы фигуры pk+1 также параллельны к осям координат, что окончательно доказывает пункт 1 утверждения индукции при n = k + 1. Покажем теперь, что для любого B k+1 э. о. p , полученная с помощью базисных фигур {p1 , p2 , . . . , pk+1 } является непустой односвязной многоугольной областью, стороны границы которой параллельны осям координат. Пусть i B k и p i э. о. из (3), где i {0, 1, . . . , 2k-1 - 1}. По предположению индукции, граница p i , области p i , имеет два опорных отрезка и они расположены либо перпендикулярно, тогда один из концов отрезков совпадает, либо взаимно параллельны, тогда они имеет одинаковую длину и расположены точно на против друг от друга. Когда граница фигуры pk
i i

+1

проходит через область p i , то p



i

разбивается

на две области p 0 и p 1 (см. рис 2а и 2б), где стрелка указывает направление движения вдоль границы фигуры pk+1 против часовой стрелки. Указание направления движения важно поскольку по предположению индукции при движении от одной э. о. к другой вдоль гамильтонового цикла (2) внутренность фигуры pk+1 остается слева, тем самым слева от направления движения будут образовываться э. о. p
i

1

, а справа p
i

i

0

(i {0, 1, . . . , 2k - 1}).


По предположению индукции область p односвязная. Граница p i , есть некоторый многоугольник, стороны которого параллельны осям координат.

240


x1 pr p p p p p p p p p p p p p p p p p p p pp p p
r
i

x1 pr p p p p p p p p p p p p p p p p p p p r x p
r
i

3

1

p x2 r

i

0

r ?

p p p p p p p p p p p p r x3

1

r

-

p

i

0 4

x2 pr p p p p p p p p p p p p p p p p p p p r x
Рис. 2б

Рис. 2а

Участок границы фигуры pk


+1

, который проходит через область p i , пересе



кает только две стороны границы p i . Поэтому непустая односвязная многоугольная область p i , этим участком границы фигуры pk
i i

непустые односвязные многоугольные области p 0 и p которых также параллельны осям координат. Тем самым пункт 2 утверждения индукции при n = k + 1 доказан. Опорный гамильтонов путь в B k+1 , построенный из гамильтонового пути (2) имеет вид

+1 , разбивается на 1 , стороны границы

две

0 0, 0 1, 1 1, 1 0, 2 0, 2 1, . . .













2k -1

1,

2k -1

0.

(5)

Рассмотрим два произвольных последовательных набора из (5) (считаем, что за последним набором следует первый). Возможны следующие ситуации. а) i 0, i 1 или i 1, i 0 (i {0, 1, . . . , 2k - 1}). В обоих этих случаях области

p

i

0

иp
1

i

1

получены из области p
+1
i i

i

разбиением на две части участком границы
i

фигуры pk иp
i

, и этот участок является общим участком границ областей p

0

, следовательно p 0 и p 1 соседние области. б) i 0, j 0 или i 1, j 1 (i {0, 1, . . . , 2k - 1} k = (j + 1)(mod 2k )). В обоих


этих случаях области p i и p j соседние и их границы, согласно предположению индукции, имеют общий опорный отрезок [xi , xi ]. Участок границы фи12 гуры pk+1 , проходящий через этот отрезок, делит его пополам, оставляя при этом слева от себя (при движении из i в j ) области p i 1 и p j 1 и справа области p
i

0

иp

j

0

, тем самым половина отрезка [xi , xi ], которая остается внутри 12
i

фигуры p иp
i

k+1 0

, является общим участком границ фигур p
i

1 1

половина отрезка фигур p
0

0

иp

j

иp

j

0

. Тем самым p

i

1

иp

j

иp

j

1

, а вторая

соседние э. о.

также соседние.

241


xp p p p p p p p p rp p 1 p p p p p p p p p p p p p p p p p i 1 i 1 p2 p1 p p p r r r p p x5 x4 x6 p p p i 0 i 0 p p2 p1 p r p p p p p p p p pr pr p p p x2 x7 pp x3 p p p p i3 1 ppp p 0 p p i3 p r ? p x Рис. 3а
8

xp xp p p p p p p p p rp p 1 p p p p p p p p p p p p rp p 3 p p p p p p
r
i 1

1

p
r

i 2

1

p
r

i 3

1

-r

x p

5 0

x

6

x p
i 2

7

x p
i 3

8

i 1

0

0

p p p p p p p p rp p p p p p p p p p p p p p p rp p p p p p p p

x

2

x

4

Рис. 3б

Тем самым мы доказали пункт 3 утверждения индукции для n = k + 1. Докажем пункт 4 утверждения индукции. Проведем мысленную линию, проходящие через э. о. с кодами из B k+1 в той последовательности, которая определяется гамильтоновым циклом (5). Поскольку эта линия проходит также через э. о. с кодами из B k в той последовательности, которая определяется гамильтоновым циклом (2), то согласно предположению индукции движение вдоль этой линии, соответствует движению против часовой стрелки, что и доказывает пункт 4 утверждения индукции для n = k + 1. Теперь покажем существование опорных отрезков для случая n = k + 1. Как мы уже отмечали, любые два соседних опорных отрезка могут быть расположены либо взаимно параллельно, либо перпендикулярно. Пусть для произвольной тройки областей p i1 ,p i2 , и p i3 (i1 {0, 2k - 1}, i2 = (i1 + 1)mod 2k , i3 = (i2 + 1)mod 2k , i1 , i2 , i3 последовательные наборы из гамильтонового цикла (2)) пара опорных отрезков расположена либо взаимно параллельно, либо перпендикулярно. После проведения фигуры pk+1 области p i1 ,p i2 , и p i3 делятся на две части и будут выглядеть как на рисунке 3а и 3б. Здесь каждая из точек x5 и x8 либо угол многоугольной области pk+1 (на подобии точки x6 с рисунка 3а), либо точка пересечения прямой с опорным отрезком, предшествующим опорному отрезку [x1 , x2 ] (на подобии точки x6 с рисунка 3б). В случае 3а при n = k + 1 опорными отрезками будут


ћ [x4 , x5 ], [x1 , x4 ], [x4 , x6 ] и [x2 , x7 ], если в гамильтоновым цикле (5) набор i 1 идет вслед за i 0, ћ [x4 , x5 ], [x2 , x4 ], [x6 , x7 ] и [x3 , x7 ] в противном случае.

242


В случае 3б при n = k + 1 опорными отрезками будут

ћ [x5 , x6 ], [x1 , x6 ], [x6 , x7 ] и [x4 , x7 ], если в гамильтоновым цикле (5) набор i 1 идет вслед за i 0, ћ [x5 , x6 ], [x2 , x6 ], [x6 , x7 ] и [x3 , x7 ] в противном случае.
Тем самым на месте двух опорных отрезков для случая n = k мы получаем четыре опорных отрезка для случая n = k + 1. Легко видеть, что на рассматриваемом фрагменте эти отрезки удовлетворяют всем требованиям к опорным отрезкам. В силу произвольности выбора индекса i1 , пробегая этим индексом вдоль всего цикла (5) получим систему опорных отрезков удовлетворяющих всем требованиям пункта 5 утверждения индукции для n = k + 1. Чтобы доказать пункт 6 утверждения леммы вспомним, что пара параллельных соседних опорных отрезков возникает только в случае, изображенном на рис. 3а, т. е. каждая пара перпендикулярных соседних опорных отрезков для n = k порождает одну пару параллельных соседних опорных отрезков для n = k + 1. Следовательно в случае n = k + 1 число пар перпендикулярных соседних опорных отрезков будет равно

2k

+1

- mk

+1

= mk

+2

,

что доказывает пункт 6 утверждения индукции при n = k + 1 и тем самым полностью доказывает утверждение индукции. Остается заметить, что утверждение леммы 1 является следствием пунктов 1 и 2 доказанного утверждения. Тем самым лемма 1 доказана.

Доказательство теоремы 2. Пусть M = { } и n произвольное число из N . Возьмем множество базисных фигур P , описанное в лемме 1. Тогда
P () = P () = h(p ). M
Так как для любого B n э.о. p согласно лемме 1 не пуста, то P () = 1 M при любом B n . Откуда согласно теореме 1 следует справедливость теоремы 2. На рисунке 4 приведены первые восемь базисных фигур {p1 , p2 , . . . , p8 } (где фигура p8 нарисована более жирной линией, чем остальные), построенных по алгоритму, описанному в лемме 1. Отметим только, что для увеличения заполненности рисунка пропорции фигур p1 и p2 слегка деформированы, точнее фигура p3 проходит не через середины опорных отрезков для случая n = 2. Предположим, что на плоскости расположено k m-угольных фигур. Они задаются k ћ m отрезками. Построим (k + 1)-ю m-угольную область и посмотрим, насколько может увеличиться при этом количество э. о. Один отрезок











Доказательство теоремы 3

243


rr p p p p p r r r r rr r r r p p rrrr r r p p r rr r r r r p r r p p

p p r r p

r r

r r r r

r rr p

p

p

r rr p

r r

p p r r p

r r

p

rr r

p

p

p

rr r

p

r r

r r r r

p

r p r p p

r r r r r

r

r r p p p

r rr r p

p

p

r rr

r

r

r p p

p

rrrr rr

Рис. 4

244


(k + 1)-ой m-угольной фигуры пересекает максимум (k ћ m) отрезков, а таких отрезков имеется m штук. В итоге точек пересечения будет не более, чем (k ћ m2 ) и, значит (k + 1)-я m-угольная фигура увеличивает число э. о. не более, чем на (k ћ m2 ). Отсюда вытекает, что после проведения n m-угольных фигур плоскость будет разбита на не более, чем 2 + 1 ћ m2 + 2 ћ m2 + ћ ћ ћ + (n - 1) ћ m2
частей. В итоге, число частей, на которое n m-угольных областей могут раз22 бить плоскость, не превышает 2 + m (n -n) . 2 Поскольку, для любого m N существует такое число n N , что выполняется следующее неравенство

2n > 2 +

m2 (n2 - n) , 2

то для любого m N с помощью n штук m-угольных фигур невозможно разбить плоскость на 2n непустых э. о. Следовательно, некоторые э. о. будут пустыми. Откуда сразу следует, что для любого базового множества Pn = {p1 , p2 , . . . , pn }, в котором каждая фигура не более, чем m-угольная область, определяющая функция Pn 1. M Откуда как следствие теоремы 1 имеем утверждение теоремы 3. Теорема 3 доказана.

5 Случай полного множества подстановок
В этом разделе мы докажем теоремы 4 и 5. Доказательство теоремы 4. Необходимость. Пусть P n 1. Предполо n n жим, что существует такой слой Bi B n , что для любого набора из Bi верно P () = 0. Возьмем произвольную подстановку

=


1 2 ... j1 j2 . . .

n jn

n из n и произвольный набор = (1 , . . . , n ) Bi . n Рассмотрим такой набор (1 , . . . , n ) Bi , что ji = i , где i = 1, 2, . . . , n. Тогда
n P () = h(p11 ћ ћ ћ pn ) = h(pj j j



j
1

1

ћћћ p


jn jn

) = P ( ) = 0.




n Откуда следует, что для любого набора из Bi P n () = 0, что противо речит условию. Необходимость доказана.

245


Достаточность. Возьмем произвольный слой i, где i {1, 2, . . . , n} и про n n извольный набор (1 , . . . , n ) Bi . Пусть = (1 , . . . , n ) Bi такой набор, P ( , . . . , ) = 1. что 1 n Возьмем такую подстановку
= 1 2 ... j1 j2 . . . n jn ,

что i = ji , где i = 1, 2, . . . , n. j j j Тогда P (1 , . . . , n ) = P (j1 , . . . , jn ) = h(pj1 1 ћ ћ ћ pjn n ) = h(p1 1 ћ ћ ћ pnjn ) = P (1 , . . . , n ) = 1. Откуда в силу произвольности слоя i и набора (1 , . . . , n ) имеем P n 1. Теорема 4 доказана. Доказательство теоремы 5. Пусть i {0, 1, . . . , n}. Обозначим

i = (1, . . . , 1, 0, . . . , 0).
i




n-i Pn ( i

n Легко видеть, что i Bi и э.о. pi не пуста. Откуда следует, что 1 и согласно теореме 4 Pn обладает n -свойством. Теорема 5 доказана.

)=

Список литературы
[1] А.А. Шакиров, К логическому описанию геометрических фигур. Фундаментальная и прикладная математика (в печати). [2] С.В. Яблонский, Г.П. Гаврилов, В.Б. Кудрявцев. Функции алгебры логики и классы Поста. - Москва, Наука, 1966. [3] Д. Гильберт, В. Аккерман. Основы теоретической логики. - Москва, 1947.

246