ПРИЛОЖЕНИЕ А. БИНАРНАЯ БУЛЕВА АЛГЕБРА. КОЛЬЦО КЛАССОВ ВЫЧЕТОВ ПО МОДУЛЮ n. ПОЛЯ ГАЛУА ХАРАКТЕРИСТИКИ p

А1. Введение

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

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

Кольца классов вычетов по модулю рассматриваются главным образом для того, чтобы ввести поля Галуа. Предполагается, что читатель имеет представление о группах конечного порядка.

А2. Булева алгебра

Рассмотрим следующий простой пример булевой структуры, построенной на множестве на котором заданы операции

и операция дополнения:

В этом частном случае операцию можно рассматривать как обычное умножение:

Ввиду того, что операция V очень близка к сложению, используют вместо V символ и говорят, что имеют дело со следующей булевой операцией:

Мы рассмотрели в § 39 (пример 3) булеву структуру для множества Кажется естественным исследовать вопрос о том, существует ли гомоморфизм в крайне простую структуру в такой постановке гомоморфизм не представляет интереса, так как при этом невозможно различать подмножества с несколькими элементами. Тем не менее, желая сохранить простоту булевой записи, определяют гомоморфизм в множество функций (называемых характеристическими), принимавших только два значения: 0 или 1.

Рис. 514.

Характеристическая функция подмножества. Рассмотрим подмножество А множества (рис. 514).

Соотнесем подмножеству А характеристическую функцию

такую, что

Например, на рис. 514

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

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

Если положим

то либо не принадлежит дополнению (отрицанию) А, следовательно,

либо следовательно,

Из диаграмм на рис, 515 видно, что

или

Пишут также вместо

Рис. 515

Характеристическая функция пересечения. Рассмотрим подмножества и их характеристические функции

Если то можно записать

Если

Легко видеть (рис. 516), что если известны значения то значение равно их произведению. Таким образом,

или

Характеристическая функция объединения. Как и раньше, положим

Легко видеть (рис. 517), что

при условии, что

Можно ли представить с помощью соотношения из обычной алгебры? Получим это соотношение, используя найденные ранее результаты.

Рис. 516.

Напомним теорему де Моргана

Таким образом,

Следовательно,

Приходят к таблице сложения:

Когда множества не пересекаются, и точько в этом случае, можно не различать

Рис. 517. (см. скан)

Алгебра характеристических функций. Характеристические функции могут принимать только два значения: 0 или 1; все числовые значения, получающиеся при операциях также равны 0 или 1. Это говорит о том, что булева алгебра,

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

Таким образом, если значения двух характеристических функций, то

Характеристическое свойство чисел 0 и 1 — быть равным своему квадрату:

Отсюда

далее

а также

Итак, булева алгебра описывается таблицами:

Известно, что булева структура (с операциями изоморфна алгебре логики (с операциями и «не»).

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

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

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

Пример.

Из этой таблицы видно, что функции

тождественны, т. е. булева алгебра дистрибутивна. Числа стоящие слева, взяты для облегчения перечисления двоичных переменных. Так, числу 6 соответствует число 110 в двоичной системе, откуда

Канонические формы. Рассмотрим подмножества множества и соответствующие им характеристические функции которые будут называться также булевыми переменными. Имеем

Итак,

Пусть

— булева функция от подмножеств и

ее характеристическая функция, Сопоставим

функцию заменяя в выражении для подмножества соответственно переменными а операции соответственно на Например,

сопоставляется Очевидно, что

так как по построению

Рассмотрим функцию

и положим

где некоторые бинарные функции. Если

и если

Итак,

Поступая аналогично с имеем

Отсюда

Действуя так же с получим

Положим

Тогда

Форма называется дизъюнктивной канонической формой, или первой канонической формой.

Положим теперь

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

Обозначим

Тогда

Форма называется конъюнктивной канонической формой, или второй канонической формой.

Можно доказать, что разложения единственны.

Пример. Детали вычислений мы оставляем читателю. Пусть

Находим последовательно

Для простоты выписываем члены с ненулевыми коэффициентами:

Тогда

Выписываем

Тогда

Легко перейти от одной формы к другой, учитывая, что

Булевы уравнения. Мы ограничимся здесь простейшими уравнениями. Рассмотрим уравнение

Говорят, что это уравнение решено, если оно представлено в виде

так как достаточно затем определить -выборки для которых Уравнение

сводится к

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

Имеем последовательно

Таким образом, решения уравнения таковы:

Разложение запишется в виде

Булевы уравнения вида или встречаются во многих задачах. Например, рассмотрим конечное множество Тот факт, что описывается уравнением

где булевы переменные, соотнесенные элементам

Пример. Пусть Определим подмножества условием

Это условие сводится к уравнению решения которого уже найдены. Выпишем подмножества А:

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

— булевы функции), равносильно доказательству того, что

Утверждение -необходимое и достаточное условие того, что — равносильно тому, что

Основные формулы двухэлементной булевой алгебры. Дадим здесь сводку основных формул для булевых характеристических функций

УПРАЖНЕНИЯ

(см. скан)

(см. скан)