Сколько существует операций над множествами?

2

С. Г. Гиндикин
Сколько существует операций над множествами?

Множества могут состоять не только из чисел, но и из лодей, машин, животных, растений и т. д. В жизни множества обычно называются поразному. Так, например, говоря не множество коров, а стADO коров, не множество лошадей, а мабун лошадей, не множество инструментов, а набор инструментов и т. д.

Эти слова взяты из учебника математики для IV класса. Вы наверняка знаете, что над множествами можно произвольить операции объединения и пересечения, которые иногда называются сложением и умножением множества. Приходилось ли вам слышать о каких-нибудь других операциях над множествами? Может быть, вы знаете, что такое разность множества или их симметрическая разность? А много ли вообще существует операция над множествами? Конечно или бесконечно их число? Для того чтобы ответить на эти вопросы, прежде всего надо дать себе отчет в том, что же следует называть операцией над множествами? Мы даим общее определение таких операций и рассケjem о некоторых их интересных свойств. О более трудных вещерах расссказывается в тексте, набранном мелким шрифтом (при первом чтении эту часть текста можно опустить).

1. Обедининие и пересечение
   Напомним, что обедининие $A \cup B$ множества $A, B$ состоит из элементов, входящих хотя бы в одно из множества $A, B$, а пересечение $A \cap B$ состоит из элементов, которые входят в оба эти множества. Образование обедининия и пересечения или построится рисунком 1, на котором «кругги» символизируют множества, над которых произвольится операция, а закрашенная область отвечает множеству, которое получается в результате операции. Заметательно, что множества могут быть самой разнообразной природы, и тем не менее эти диаграммы очень удобны при изучении операций над ними.

Обе рассматриваемые операции обладают следующим двумя свойствами:
$A \cup B = B \cup A; \ A \cap B = B \cap A$ (коммутиативность),
$A \cup (B \cup C) = (A \cup B) \cup C;$
$A \cap (B \cap C) = (A \cap B) \cap C$ (ассоциативность).

Коммутиативность очень из определений (см. рис. 1). Доказать ассоциативность вам помогет рисунок 2. Расстановка скобок предписывает порядок, в котором должны выполняться операции. Рисунок подсказывает, что в каком бы из указаных выше порядков не выполнялись операции обедининия, в результате получится множество, состоящее из

3

Элементов, входящих хотя бы в одной из наших множества. Аналогично в случае пересечения получается множество, состоящее из элементов, входящих в каждой из наших множества. Мы советуем читателю проведити аккуратные рассуждания, и не исключаем, что будет не слишкомлегко перевести на язык слов то, что очень/noиз рисунков.

Ассоциативность позволяет, например, в случае объединения при многократном проведении операции над множествами $A_1, \dots, A_n$ не фиксировать при помощи скобок порядок, в котором производятся операции, и говорить просто об объединении $n$ множества $A_1 \cup A_2 \cup \dots \cup A_n$; это множество состоит из элементов, содержащих хотя бы в одном из множества $A_1, \dots, A_n$. Коммутитивный же закон показывает, что можно как угодно менять порядок $A_1, A_2, \dots, A_n$.

В числовом случае сложение и умножение связны между собой следующим соотношением: $a (b + c) = ab + ac$ (дистирибутивность умножения относительно сложения). Это соотношение позволяет вычисть общий множитель за скобку и раскрывать скобки. Для множества таких соотношения два:

$$A \cap (B \cup C) = (A \cap B) \cup (A \cap C);$$
$$A \cup (B \cap C) = (A \cup B) \cap (A \cup C).$$

На рисунке 3 приведены диаграммы, иллюстрирующие эти соотношения. Для доказательства, например, первого из них достаточно заметить, что множество, стоящее и справа и слева, состоит из элементов, входящих в множество $A$ и по крайней мере в одной из множества $B$ или $C$. Отметим, что в числе случаев второе соотношение имело бы вид $a + bc = (a + b) (a + c)$, что, разумеется, неверно.

Первое из соотношений (2) показывает, что любую последовательность объединений и пересечений можно преобразовать в такую последовательность этих операций, что сначала выполняется все пересечения, а потом объединения. Убедитесь, например, что $(A \cup B) \cap ((C \cap D) \cup E)$ можно преобразовать в $(A \cap C \cap D) \cup (A \cap E) \cup (B \cap C \cap D) \cup (B \cap E)$. Можно сделать и так, что вначале будет выполнять все объединения (пользоваться вторым соотношением). Продумайте аналогичные этих преобразований в числовом случае.

2. Разность и симметрическая разность

Разность $A \setminus B$ множества $A$ и $B$ называется множество, состоящее из тех элементов $A$, которые не входят в $B$ (рис. 4). Разность не является симметрической разностью. Для доказательства, например, первого из них достаточно заметить, что множество, стоящее и справа и слева, состоит из элементов, входящих в множество $A$ и по крайней мере в одной из множества $B$ или $C$. Отметим, что в числе случаев второе соотношение имело бы вид $a + bc = (a + b) (a + c)$, что, разумеется, неверно.

Первое из соотношений (2) показывает, что любую последовательность объединения и пересечения можно преобразовать в такую последовательность этих операций, что сначала выполняется все пересечения, а потом объединения. Убедитесь, например, что $(A \cup B) \cap ((C \cap D) \cup E)$ можно преобразовать в $(A \cap C \cap D) \cup (A \cap E) \cup (B \cap C \cap D) \cup (B \cap E)$. Можно сделать и так, что вначале будет выполнять все пересечения (пользоваться вторым соотношением). Продумайте аналогичные этих преобразований в числовом случае.

4

Ляется ни коммутативной, ни ассоциативной операцией. Доказать это вам помогет рисунок 5. Заметьте также, что разность не является операцией, обратной объединению (которая, как мы уже говорили, иногда называют сложением множества). Вы убедитесь в этом, доказав следующее соотношение:

$$(A \setminus B) \cup B = A \cup B;$$
$$(A \setminus B) \cup (A \cap B) = A.$$

Симметрическая разность $A \triangle B$ множество $A$ и $B$ состоит из элементов, входящих в одно и только одно из множества $A$ и $B$ (рис. 6): $A \triangle B = (A \setminus B) \cup (B \setminus A)$. Симметрическая разность является коммутативной и ассоциативной операцией. Доказите это, воспользовавшись рисунком 7. Для симметрической разности и пересечения выполняется дистрибутное соотношение:

$$A \cap (B \triangle C) = (A \cap B) \triangle (A \cap C)$$
(см. рис. 8). Однако $A \triangle (B \cap C)$ может не совпадать с $(A \triangle B) \cap (A \triangle C)$ (см. рис. 9). Ситуация анализочная числовой. Для этого, как мы увидим, имеются глубокие причины.

3. Универсальное множество и дополнительное множество

Будем предложать в дальнейшем, что все рассматриваемые множества являются подмножествами некоторого фиксированного множества. Мы будем называть его универсальным образом. Если, например, рассматриваются множества точек на плоскости, то универсальным является множество всех точек на плоскости; если рассматриваются множества натуральных чисел, то универсальным является множество всех натуральных чисел.

Если фиксированную универсальное множество $I$, то можно говорить о дополнительном $\bar{A}$ множество $A$ (до $I$): $\bar{A} = I \setminus A$, то есть $\bar{A}$ состоит из элементов $I$, не входящих в $A$

5

(см. рис. 10). Дополнительную универсальную множеству пусто: $\bar{I} = 0$ (пустое множество).

Операция дополнительная позволяет связывать операции объединения и пересечения следующим образом:

$$\bar{A} \cup \bar{B} = \bar{A} \cap \bar{B}.$$

Действительно, $\bar{A} \cap \bar{B}$ состоит из элементов, входящих в $\bar{A}$ и $\bar{B}$, то есть не входящих ни в $\bar{A}$, ни в $\bar{B}$, или, что то же, не входящих в объединение $\bar{A} \cup \bar{B}$, что и утверждается. Из полученного соответствия, что

$$\bar{A} \cup \bar{B} = \bar{A} \cap \bar{B}, \quad \bar{A} \cap \bar{B} = \bar{A} \cup \bar{B}.$$

(3)

Для получения первого из этих соответствий достаточно заменить, что из совпадения множеств следует совпадение их дополнительной и что $\bar{C} = C$ (дополнитель к дополнительно совпадет с исходным множеством). Для получения второго нужно учеть, что поскольку $\bar{A} \cup \bar{B} = \bar{A} \cap \bar{B}$ для любых $A$ и $B$, то можно в качестве этих множеств взять $\bar{A}, \bar{B}$: $\bar{A} \cup \bar{B} = \bar{A} \cap \bar{B} = \bar{A} \cap \bar{B}$. Соответствия (3) носят название закон де Моргана. Они показывают, что объединение можно выражить через пересечение и дополнительное, а пересечение — через объединение и дополнительное.

Отметим, что $A \setminus B = A \cap \bar{B}$, а значит, $A \triangle B = (A \cap \bar{B}) \cup (\bar{A} \cap \bar{B})$.

4. Закон двойственности

Изучение операций над множеств состоит в получении различных точекств, связывающих операции. Имеются в виду утверждения следующого вида. Над множеством $A_1, \dots, A_n$ двумя способами выполняются какие-то последовательности операций и утверждается, что эти комбинации операций всегда (для любых $A_1, \dots, A_n$) приводят к совпадению множеств. Все законы (1), (2), (3) являются также то жею точкойствами. Важно уметить получать из уже имеющихся точекств новые. Например, мы уже фактически пользовались тем, что если в точекстве заменить $A_1, \dots, A_n$ на $\bar{A}_1, \dots, \bar{A}_n$ или перейти к дополнительному в обеих частях точекств, то также получим точекств.

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

Закон двойственности. Если в точекстве, содержащем только операции объединения, пересечения и дополнительия, заменить все пересечения на объединения, а все объединения — на пересечении, то вновь получится точекств.

Проверьте, что таким образом из коммутативности и ассоциативности объединения получаются коммутативность и ассоциативность пересечения, и обратно, а из одного дистрибутного соответствия (2) — другое.

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

Рассмотрим точекств

$$A_1 \cap ((A_2 \cup \bar{A}_3) \cap (\bar{A}_4 \cap A_5)) = A_1 \cap (\bar{A}_2 \cap A_3) \cup (\bar{A}_4 \cap A_5),$$

его легко проверить, пользоваться законами де Моргана. Перейдем в обеих частях точекств к дополнительному и заменим все $A_1, \dots, A_5$ на $\bar{A}_1, \dots, \bar{A}_5$:

$$\bar{A}_1 \cap ((\bar{A}_2 \cup A_3) \cap (\bar{A}_4 \cap A_5)) = \bar{A}_1 \cap (\bar{A}_2 \cap \bar{A}_3) \cup (\bar{A}_4 \cap \bar{A}_5).$$

Заменим теперь все операции объединения и пересечения при помощи (3). Если мы упрощим полученное точекств, пользоваться тем, что две черты над одним выражением

6

Можно уничтожить, то получим нужное тожество:

$$A_1 \cup ((A_2 \cap A_3) \cup (A_4 \cap A_5)) = A_1 \cup (A_2 \cup A_3) \cap (A_4 \cup A_5).$$

Строое доказательство проводится из таких же сообщений.

5. Что такое операция над множеством?

Попытайте сами дать ответ на этот вопрос, а затем сравните вашы выводы с тем, что расссказывает ниже.

Задать операцию над множеством — это прежде всего значит указать способ по двум заданным множеством $A$ и $B$ строить треть множество; обозначим его через $A \bigcirc B^*$). Если мы оставимся в определении на этом месте, то получим необозримое количество операций. Но, может быть, вам удалось подметить, что во всех операциях, которые мы показатривали, вопрос о том, входит ли какой-либо элемент в $A \bigcirc B$, полностью решался исходя только из того, в какие из множеств $A$, $B$ он входит, а в какие — нет. Включим это требование в определение операции. Сформулируем его более подробно.

Если заданы два множества $A$ и $B$, то возникает разбнение универсального множества $I$ на четыре непересекающихся подмножества: множество $A \cap B$, состоящее из элементов, содержащихся в общих множеств $A$ и $B$; множество $\overline{A} \cap \overline{B}$, состоящее из элементов, не попавших ни в одной из этих множеств; множество $\overline{A} \cap B$, состоящее из элементов, попавших в $B$, но не попавших в $A$, и множество $\overline{A} \cap \overline{B}$, состоящее из элементов, входящих в $A$, но не входящих в $B$. Будем называть эти множества однойками. Наше дополнительное требование на операцию состоит в том, что если два элемента находится в одной dolbe, то они или она входят

*) Разумеется, $A \bigcirc B$, как и $A$, и $B$ должны содержаться в универсальном множестве $I$.

Рис. 11.

в $A \bigcirc B$, или она не входят. Другими словами, $A \bigcirc B$ является объединением некоморого числа долек. Разбнение на дольки хорошего иллюстрируется диаграммами, которые мы рисовали (на рис. 11 соответствующие области окрашены в разные цвета); в этом и заключается причина, по которой диаграммы удобны при изучении операций.

6. Сколько существует операций над парой множеств?

Теперь мы можем легко ответить на этот вопрос. Различных операций столько, сколько существует различных способов выбрать долек, составляющие $A \bigcirc B$. Имеется 4 долек, а различных способов образования $A \bigcirc B$ — 16. Столько же имеется и различных подмножества в множестве из 4 элементов (считая пустое множество и все множество). Эти вычисления можно проводить непосредственно, а можно воспользоваться следующей комбинаторной леммой, которая нам пригодится в дальнейшем.

Лемма. В множестве из $n$ элементов имеет $2^n$ различных подмножества.

Доказательство. Пусть $N$ — такое множество. Занumerуем каким-то образом его элементы. Поставим в соответствие каждойому подмножеству $M$ в $N$ набор из нулей и единиц длины $n$, причем на $k$-м месте мы ставим 1, если $k$-й элемент множества $N$ входит в $M$, и 0 — в противном случае. Такие наборы называются двончными. Между поимно-

7

Жествами в $N$ и двойными наборами длины $n$ возникает взаимно однозначное соответствие. При этом набору из одних нулей отвечает пустое множество, а набору из одних единиц — все множества $N$. Итак, число подмножества в $N$ совпадает с числом двойных наборов длины $n$. Доказем по индукции, что это число $f(n)$ равно $2^n$. При $n = 1$ это очевидно; пусть $f(n - 1) = 2^{n-1}$. Каждый набор длины $n$ получается из набора длины $n - 1$ добавлением 0 или 1, то есть из каждого набора длины $n - 1$ получается два набора длины $n$, а значит, $f(n) = 2f(n - 1) = 2^n$.

Полагая $n = 4$, мы получаем, что существует 16 подмножества в множестве из 4 элементов и, следовательно, 16 операций над двумя множествами. В числе этих операций попадают операции $A \bigcirc B = 0$ (пустое множество) для любых $A$ и $B$ ($A \bigcirc B$ не содержит ни одной дольки) и $A \bigcirc B = I$ при любых $A$ и $B$ ($A \bigcirc B$ — объедининие всех дольек). Эти операции мы будем обозначать через 0 и 1 соответственно. В числе операций попадут также $A \bigcirc B = A$, $A \bigcirc B = B$, $A \bigcirc B = \overline{A}$, $A \bigcirc B = \overline{B}$, так как во всех четырех случайных множества, стоящее справа, является объедининием двух дольек (например, $\overline{A} = (\overline{A} \cap B) \cup (\overline{A} \cap \overline{B})$). Перечислим остальные операции:
$A \bigcup B$, $A \cap B$, $A \setminus B$, $B \setminus A$, $A \triangle B$, $A \cup B$, $A \cap B$, $A \setminus B$, $B \setminus A$, $A \triangle B$.

Заметим, что в числе операций вошли операции образования долек *). Из того, что каждая операция является объедининием долек, следует, что каждая операция может быть выражена через объедининие, пересечение и дополнение.

*) Для представления операций, которые мы несколько легкомыслино называем «разбением на дольки», существует в полне серbezный термин «совершенная дизюнктивная нормальная форма», а дольки при этом называются «полными правильными элементарными коньонкциями».

Рис. 12.

Укажем еще одно представление операций через указанные три. Наозовем дополнение к долке довеском. В силу (3) довескам отвечают операции $\overline{A} \cup \overline{B}$, $A \cup B$, $A \cup \overline{B}$, $\overline{A} \cup B$. (В этом также легко убедиться, рисунками). Задавая операцию $A \bigcirc B$, можно вместе того, чтобы перечислять, какие дольки входят в $A \bigcirc B$, указывать, какие дольки не входят в него, и тогда $A \bigcirc B$ будет пересечением довесков, соответствующих этим долькам. Например, $\overline{A} \cap B = (A \cup B) \cap (\overline{A} \cup \overline{B}) \cap (\overline{A} \cup B)$ рассмотрите самостояльно и другие примеры. Представление операций в виде пересечения довесков *) можно получить из представления в виде объедининия долек при помощи закона двойственности (проделяйте это!).

7. Двоичные таблицы для операций
   Поставим в соответствие каждой дольке двойный набор из двух элементов: $A \cap B => (1, 1)$, $\overline{A} \cap \overline{B} => (0, 0)$, $\overline{A} \cup B => (0, 1)$, $A \cup \overline{B} => (1, 0)$. Здесь 1 указывает на то, что долька входит в соответствующей множество ($A$ или $B$), а 0 — что не входит и, значит, входит в дополнение (см. рис. 12). При задании операции $A \bigcirc B$ поставим в соответствие каждой дольке, закодированной таким набором, 1, если эта долька

*) И для этого представления есть серbezное наименование; «совершенная коньонктивная нормальная форма».

8

входит в $A \bigcirc B$, и 0, если не входит. Все это можно записать в виде таблицы, в котором строки будут отвецать долькам, и строку, например, 1,0|0 следует воспринять как закодированную запись фразы: если неекоторий элемент входит в первое множество ($A$) и не входит во второе ($B$), то он не входит в $A \bigcirc B$. Такая таблица называется двойной или бульевой таблицей операции, и она полностью задает операцию. Выше приведена сводная двойная таблица всех операций над парой множества.

Обратите внимание на столбцы таблицы, отвецующие $A \cap B$, $A \triangle B$ и $\bar{A}$. Если $(x, y)$ — набор, отвецующий дольке, то в столбце для $A \cap B$ стоит просто $xy$, в столбце для $A \triangle B$ — остаток от деления $x + y$ на 2, а в столбце для $\bar{A}$ — остаток от деления $x + 1$ на 2. Эти действия над элементами $x, y = 0,1$ носят название арфметических операций по модулю 2, и для них сохраняются все основные законы общих арфметических операций (коммутитивность, ассоциативность, диспribутивность умножения относительно сложения) *). Этот факт позволяет замененные нами свойства симметрической разности.

*) Об операциях по модели (арфметике остатков) можно прочитать в журнале «Квант» № 5 за 1970 г.

8. Операции над $n$ множества

С таким операциями мы уже фактически имели дело, но они всегда были выражены через операции над парами множества. Сейчас мы даим общее определение. Задать операцию над $n$ множества — это значит задать закон построения по набору из любых $n$ множества $A_1, \dots, A_n$ однозначно определенного множества $f(A_1, \dots, A_n)$, причем вопрос о входении некоторого элемента в $f(A_1, \dots, A_n)$ полностью определяется тем, в какие из множества $A_1, \dots, A_n$ этот элемент входит, а в какие — нет. Положим $A^\sigma = A$ при $\sigma = 1$ и $A^\sigma = \bar{A}$ при $\sigma = 0$. Заметим, что множество $A_1^{\sigma_1} \cap A_2^{\sigma_2} \cap \dots \cap A_n^{\sigma_n}$ состоит из всех элементов, входящих в $A_j$, если $\sigma_j = 1$, и не входящих в $A_j$, если $\sigma_j = 0$. Операцию $A_1^{\sigma_1} \cap A_2^{\sigma_2} \cap \dots \cap A_n^{\sigma_n}$ будет, как и при $n = 2$, назвать долькой, отвецующей набору $(\sigma_1, \sigma_2, \dots, \sigma_n)$. Долек существует столько, сколько существует двойных наборов длины $n$, то есть (по лемме) $2^n$. На рисунке 13 вы видите разбиение на дольки при $n = 3$.

Из определения операции следует, что каждая операция $f(A_1, \dots, A_n)$ является обтеканием некомотрою числа долек. Для задания операции каждой долке, закодированной двой

9

Рис. 13.

ным набором σ, поставим в соответствии 1 или 0, смотря по тому, входит эта долка в $f(A_1, \dots, A_n)$ или нет. В результате операции отвечает двойный набор длины $2^n$ (столько имеется долек), а значит, существует $2^{(2n)}$ различных операций над множествами. Поскольку во всех случаях $f(A_1, \dots, A_n)$ является объединением долек, одновременно мы получаем, что каждой операция выражается через объединения, пересечения и дополнительия. Другое представление мы получим, если рассмотрим две и three операции к долкам, они имеют вид $A_1^{\sigma_1} \cup \dots \cup A_n^{\sigma_n}$. Всякая операция может быть представлена в виде пересечения довесков.

Итак, оказалось, что, во-первых, имеется конечное число операций над $n$ множествами, а, во-вторых, все эти операции могут быть выражены через операции над парами множества — объединение, пересечение и дополнительие $^*$). Этим и обьясняется, что во многих вопросах теории множества ограничиваются рассмотренем этих трех операций. Впрочем, учитывая (3), можно ограничиться двумя операциями: объединением и дополнительным или пересечением и дополнительным.

Существуют и другие возможности выбирать основные операции, через которых выражаются все остальные операции. Рассмотрим, например, операцию $A \cap B$. Если взять

*) Дополнительное считать операцией над одним множествором ($n=1$).

в качестве $A$ и $B$ одно и то же множество $C$, то мы получим $\overline{C}$. Проделав последовательно эти две операции, мы получим $A \cap B$. Но через пересечение и дополнительное можно выразить любую операцию. Значит, любую операцию можно выразить через единственную операцию $\overline{A \cap B}$. Проверьте, что и через операцию $A \cup B$ тоже можно выразить все операции. Эти две замечательные операции носят название операций Шефера. Докажите, что в качестве систем основных операций можно выбрать $\overline{A} \cup B$, $\overline{C}$ или $\overline{A} \cup B$, 0.

9. Монotonные операции.

А все ли операции можно выразить через объединения и пересечения, не прибегая к дополнительному? Оказывается, нет. Для того чтобы убедиться в этом, надо найти какое-то свойство, который все операции, представляющиеся через объединение и пересечение, обладают, но есть операции, которые этим свойством не обладают. Как мы заметили в п.1 при обсуждении соответствия (2), всегда можно так изменить порядок объединения и пересечения, что вначале будут выполняться пересечения, а затем объединения. Возможность такого представления накладывается с целью определения на множество долек, из которых может состоять $f(A_1, \dots, A_n)$, если $f(A_1, \dots, A_n)$ выражается через объединения и пересечения. Набор этих долек должен быть устроен следующим образом: имеются подмножества $M_1, \dots, M_k$ в множестве $N = \{1, 2, \dots, n\}$ и долка, отечеющая $\sigma = (\sigma_1, \dots, \sigma_n)$, входит в $f(A_1, \dots, A_n)$ тогда и только тогда, когда или $\sigma_j = 1$ при всех $j \in M_1$, или $\sigma_j = 1$ при всех $j \in M_2$, и так далее. Например, в случае $(A_1 \cap A_3 \cap \bigcap A_5) \cup A_4 \cup (A_2 \cap A_5)$ имеем: $M_1 = \{1, 3, 5\}, M_2 = \{4\}, M_3 = \{2, 5\}$. Нетрудно убедиться, что такие совокупности наборов от характераизуют тем, что в них вместе с каждой набором $\sigma$ входят все наборы $\sigma'$, у которых на всех тех местах, на которых $\sigma$ стоит единицы, также стоит единицы (будем это символически обозначать так: $\sigma' \geq \sigma$). Теперь ясно, что, например, операция $A \setminus B = A \cap B$ не обладает этим свойством: она совпадает с единственной долкой, отечеющей набору (1, 0), а $(1, 1) \geq (1, 0)$ отечеает долке, не входящей в $A \setminus B$. Операции, которые выражаются через объединения и пересечения, а также 0, 1 будем называть многоотнеными. Очевидно, что дополнительное — также немногоотненная операция: считая $n = 1$, мы видим, что $A$ совпадает с долкой для $\sigma = (0) \leq \sigma' = (1)$.

10

10. Линейные операции

Всякую операцию можно выразить через $A \cap B, A \triangle B, I$. Действительно, $\overline{A} = A \triangle I$, $A \cup B = (A \cap B) \triangle (A \triangle B)$, а в п. 8 мы доказали, что любая операция выражается через пересечение и дополнение. Исследуем этот факт с точки зрения арифметической интерпретации операций. Пусть $f(A_1, \dots, A_n)$—произвольная операция; рассмотрим ее двончную таблицу (см. п. 7). Обозначим через $\tilde{f}(x_1, \dots, x_n)$ значение в этой таблице, отвечающее двончному набору $(x_1, \dots, x_n)$.

Если мы выразим $f$ через $A \cap B, A \triangle B, I$, то для $f$ возникнет выражение через арифметические операции по модулю 2. Раскрыв скобки и приводя подобные члены, мы получим представление для $\tilde{f}$ в виде многочлена от $x_1, \dots, x_n$. Учитывая, что $x_j$ принимают значения 0, 1, а в результате берется лишь остаток от деления значения многочлена на 2, мы можем силюно упростить вид многочлена. Во-первых, можно считать, что все ненулевые коэффициенты равны 1 (2x делится на 2), во вторых, переменные $x_j$ будут входить в одночлены не выше чем в первой степени $(x^2 = x$ при $x = 0, 1)$.

Исследуем теперь операции такого вида: $f(A_1, A_2, \dots, A_n) = A_1 \triangle A_2 \triangle \dots \triangle A_n$. (В записи мы воспользовались коммутиативно и ассоциативно $A \triangle B$; см. п. 2.) Полученное в результате множество состоит из таких элементов, которые входят в нечетное число множества $A_1, \dots, A_n$, а потом эти операции будем называть идикарами нечетности. Проверку этого утверждения легко осуществить непосредственно (при $n = 2, 3$, см. рис. 6, 7), и можно заметить, что в этом случае $\tilde{f}(x_1, \dots, x_n) = x_1 + \dots + x_n$ по модулю 2. Отсюда видно, что через симметрическую разность нельзя выразить, например, пересечение $A \cap B$, так как $A \cap B$ состоит из элементов, попавших в два множества. Если добавить операцию 1, то мы получим еще индикаторы четности $A_1 \triangle \dots \triangle A_n \triangle I$; им отведют полиномы первой степени $x_1 + \dots + x_n + 1$. Пересечение мы опять выразить не сможем, так как элементы, не входящие ни в $A$, ни в $B$, не входят и в $A \cap B$. Будем называть операции, выражющейся через $A \triangle B$ и $I$ (то есть индикаторы четности и нечетности), линейными операциями, а остальные операции — не линейными. Эти термины связаны с отвечающим этим операциям полиномами.

11. Описание системы основных операций

Будем понимать под системой основных операций такие системы операций, что все остальные операции через них выражаются.

У нас уже имеется несколько примеров системы основных операций. Кроме того, в предыдущих двух пунктах мы доказали, что наборы $\{A \cap B, A \cup B\}$, $\{A \triangle B, I\}$ нельзя принять за системы основных операций. При этом мы получили необходимые условия на такие системы; они обязательно должны содержать неполнением и неонотонные операции. Замечательно, что в таких же терминах даны необходимые и достаточно условия. Мы сделаем это не в самом общей системе. Будем говорить, что для системы операции выполняется предположение 01, если эта система содержит 0 и 1.

Теорема Поста. Систему операций, удовлетворяющих предположению 01, можно принять за систему основных операций модели и только модели, когда она содержит неонотонную и неонотонную операции.

Имеется общая формулировка теоремы Поста для любых систем (без предположения 01); при этом число условий теоремы, то без предположения 01 они должны в п. 9, 10. Очевидно, что они сохраняются и при условии 01, так как 0 и 1 являются монотонными и линейными операциями $(A \triangle A = 0)$.

Достаточно будет следовать из двух приводимых ниже задач.

Задание 1. Доказать, что в предположении 01 из всякой неонотонной операции можно получить операцию дополнительно.

Пусть $f$ — неонотонная операция и $f(A_1, \dots, A_n)$ входит только, отвечающая $\sigma$, а только, отвечающая $\sigma' \geq \sigma$, не входит. Тогда, если на $j$-м месте и в $\sigma$ и $\sigma'$ стоит 0, то вместо $A_j$ подставляем пустое множество, если же и тут и там стоит 1, то подставляем универсальное множество $I$. На остальных местах, поскольку $\sigma' \geq \sigma$, в $\sigma$ стоит 0, а в $\sigma' - 1$. Подставим вместо этих $A_j$ одно и то же множества $A$. Тогда должна, отвечающая $\sigma$, превращаться в $A$, а должна, отвечающая $\sigma'$, — в $A$. Операция $\varphi(A)$, которая получится в результате, будет совпадать с $A$, так как $\varphi(A)$ содержит $A$ и не содержит $A$.

Задание 2. Доказать, что в предположении 01 через всякую неонотонную операцию и дополнение можно выразить пересечение.

Эту задачу попробуйте решить самостоятельно. Наше решение приведено на с. 58.

*) См. книгу Гиндикин С. Г., Алгебра логики в задачах, М., «Наука», 1972.