Классы Поста

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА

Механико-математический факультет

А. Б. Угольников

Классы Поста

Рекомендовано УМО по классическому университетскому образованию в качестве учебного пособия по дискретной математике для студентов высших учебных заведений, обучающихся по направлениям подготовки высшего профессионального образования 010100 Математика, 010200 Математика. Прикладная математика

Москва 2008

УДК 519.7 ББК 22 Угольников А. Б. Классы Поста. Учебное пособие: М.: Изд-во ЦПИ при механико-математическом факультете МГУ имени М. В. Ломоносова, 2008. 64 с.

Рецензенты: Касим-Заде О. М., профессор, д.ф.-м.н. Кобельков Г. М., профессор, д.ф.-м.н.

Учебное пособие содержит доказательство конечной порождаемости всех замкнутых классов функций алгебры логики (классов Поста), на основе которого дано описание структуры всех замкнутых классов. Этот материал входит в программу обязательного курса "Дискретная математика", читаемого студентам механико-математического факультета МГУ им. М. В. Ломоносова на четвертом курсе. Для студентов и аспирантов.

c Угольников А. Б., 2008 °

Содержание Предисловие . . . . . . . . . . . . . . . . . . . . . . .

4

Введение . . . . . . . . . . . . . . . . . . . . . . . . .

5

§1 Некоторые определения и обозначения . . . . . .

7

§2 Вспомогательные утверждения . . . . . . . . . . 16 §3 Конечная порождаемость замкнутых классов . 23 §4 Структура замкнутых классов . . . . . . . . . . . 34 §5 Структура C -замкнутых классов . . . . . . . . . 44 Приложение . . . . . . . . . . . . . . . . . . . . . . . 50 Литература . . . . . . . . . . . . . . . . . . . . . . . . 58

Предисловие Данная книга содержит доказательство известной теоремы американского математика Э. Л. Поста [32–34] о том, что каждый класс функций алгебры логики, замкнутый относительно операции суперпозиции, имеет конечный базис. На основе этого доказательства приводится описание структуры всех замкнутых классов булевых функций (классов Поста). Этот материал входит в программу обязательного курса "Дискретная математика", читаемого студентам механикоматематического факультета МГУ на четвертом курсе, и служит дополнением раздела "Функции алгебры логики" обязательного курса "Введение в математическую логику", читаемого студентам первого курса факультета. В книге принят достаточно лаконичный стиль изложения: некоторые простые свойства булевых функций приводятся без подробного обоснования, что позволяет более выпукло показать основные идеи предлагаемых конструкций и методы доказательств. Заинтересованный читатель может легко восстановить все детали доказательств. Приведенный в данном издании материал может быть также использован при проведении практических занятий по вышеупомянутым обязательным курсам при изучении свойств функций алгебры логики. Автор выражает благодарность О. С. Дудаковой за подготовку оригинала-макета.

Введение Э. Пост [32–34] описал все классы булевых функций, замкнутые относительно операции суперпозиции (см. также [37]). На основе этого он показал, что каждый такой класс имеет конечный базис. В книге С. В. Яблонского, Г. П. Гаврилова и В. Б. Кудрявцева [19] было дано более компактное и простое изложение этих результатов. При этом, в отличие от работ Поста, в книге [19] предполагается, что каждый класс вместе с функцией содержит также и все функции, отличающиеся от нее фиктивными переменными, то есть фактически замыкание систем функций рассматривается относительно двух операций: суперпозиции и введения несущественной переменной. Такой подход позволил получить более простую структуру замкнутых классов, чем структура, описанная у Поста. В ней отсутствуют классы (их семнадцать), которые не являются замкнутыми относительно операции введения несущественной переменной. Описание классов Поста содержится также в [7, 8, 17, 28– 30, 35]. В работах [1] и [6] приведены доказательства конечной порождаемости всех замкнутых классов булевых функций, не использующие описание структуры Поста (см. также [31]). Некоторые свойства замкнутых классов изучены в [2, 3, 18, 20–22, 24–27]. Алгебраический подход к понятиям суперпозиции и замкнутого класса предложен в [4, 5]. В данной книге приведено доказательство конечной порождаемости замкнутых классов булевых функций (также не опирающееся на описание структуры замкнутых клас-

6

А. Б. Угольников. КЛАССЫ ПОСТА

сов) из работы автора [17], на основе которого1 дано описание структуры всех классов Поста, в том числе тех, которые отсутствуют в книге [19]. В основе этого доказательства лежит метод моделирования констант функциями определенного вида, а также специальное представление монотонных функций над системой W булевых функций вида dp (x1 , . . . , xp ) = xi xj (дизъюнкция берется по всем i, j = 1, . . . , p, i 6= j ), которые, в свою очередь, получаются отождествлением переменных у исходных функций. Эти методы ранее применялись автором при реализации функций из замкнутых классов схемами из функциональных элементов и формулами в неполных базисах (см. [10–16, 36]). В §1 даются основные определения и обозначения. Перечисление всех классов Поста потребовало несколько иначе, чем в книгах [23, 24], ввести некоторые понятия, однако отличие невелико. В §2 приводятся вспомогательные утверждения. В §3 доказывается теорема о конечной порождаемости замкнутых классов. На основе этого доказательства в §4 приводится описание всех замкнутых классов булевых функций. В §5 дается описание классов Поста, не являющихся замкнутыми относительно операции введения несущественной переменной. В книге используются обозначения замкнутых классов из работы [17]. В приложении приведены обозначения этих классов из работы Поста [34], а также из книги [19]. Следует отметить, что для замкнутых классов, которые не содержат существенных функций (а также некоторых классов конъюнкций и дизъюнкций), в книге [19] используются обозначения, отличающиеся от обозначений соответствующих классов из работы [34]. 1

Основные моменты этого доказательства изложены также в книгах [7] и [8].

§1

Некоторые определения и обозначения

Пусть E = {0, 1}, X — счетное множество переменных. Элементы множества X обозначаются символами xi , yi , zi , . . ., i = 1, 2, . . .; нижние индексы иногда опускаютe набор переменных (x1 , . . . , xn ), через ся. Обозначим через x e = (α1 , . . . , αn ), таких что E n — множество всех наборов α e α1 , . . . , αn ∈ E , n ≥ 1; через 1 — набор (1, . . . , 1), а через e 0 — набор (0, . . . , 0). Пусть f (n) — отображение множества e), x1 , . . . , xn ∈ X , заE n в E , n ≥ 1, и пусть функция f (n) (x n дает это отображение, E — область определения, E — область значений, x1 , . . . , xn — переменные, от которых завиe). Функция f (n) (x1 , . . . , xn ) называется n-местной сит f (n) (x булевой функцией (или функцией алгебры логики), а f (n) — n-местным функциональным символом, соответствующим этой функции. В дальнейшем мы верхний индекс у функциональных символов будем, как правило, опускать, указывая при этом число переменных, от которых зависят рассматриваемые функции. Множество всех таких функций обозначается через P2 . Так как наборов (σ1 , . . . , σn ) длины n из нулей и единиц конечное число (именно 2n ), то каждая функция алгебры логики может быть полностью задана таблицей (табл. 1). В левой части табл. 1 выписаны все наборы значений переменных, в правой части — соответствующие им значения функций. На каждом из 2n наборов функция f (x1 , . . . , xn ) может принимать любое из двух значений из множества E .

8

А. Б. Угольников. КЛАССЫ ПОСТА

Отсюда следует, что число функций алгебры логики от n n переменных x1 , x2 , . . . , xn равно 22 . Таблица 1 x1

x2

...

xn

f (x1 , x2 , . . . , xn )

0

0

0

σ1

σ2

1

1

... ... ... ... ...

f (0, 0, . . . , 0) ... f (σ1 , σ2 , . . . , σn ) ... f (1, 1, . . . , 1)

σn 1

e) Отметим, что каждая n-местная булева функция f (n) (x представляет собой совокупность некоторого отображения e = (x1 , . . . , xn ) пеиз E n в E и упорядоченного набора x ременных из множества X , n ≥ 1. В соответствии с этим возникает следующее понятие равенства функций.

Функции равны, если они зависят от одного и того же множества переменных и задают одно и то же отображеe) и g (n) (x e) из P2 называются ние. А именно, функции f (n) (x (n) (n) равными (обозначения f = g или f (n) ≡ g (n) ), если (n) (n) e = g (α) e для любого набора α e ∈ E n , n ≥ 1. f (α)

e) называется константой нуль (соответФункция f (n) (x ственно константой единица), если она принимает значение 0 (соответственно 1) на всех наборах из En , n ≥ 1; n-местные константы нуль и единица обозначаются через 0(n) и 1(n) соответственно (или соответственно через 0 и 1 в тех случаях, когда нет необходимости отмечать число переменных, от которых зависят эти функции). Функция e) называется селекторной, если существует такой ноf (n) (x e = (α1 , . . . , αn ) мер i, 1 ≤ i ≤ n, что для любого набора α n (n) e из E выполняется равенство f (α) = αi (такая функция (n) (1) обозначается ei (x1 , . . . , xn )); функцию e1 (x) будем обозначать также e(x) или x.

9

§1 Некоторые определения и обозначения

В дальнейшем важную роль будут играть некоторые функции одного и двух аргументов. Рассмотрим эти функции подробно. При n = 1 будет всего 4 функции, указанные в табл. 2; функция x называется отрицанием x. Таблица 2 x

0

x

x

1

0 1

0 0

0 1

1 0

1 1

При n = 2 будет уже 16 функций. Некоторые из них указаны в табл. 3. Функция x1 &x2 называется конъюнкцией x1 и x2 , она обозначается также x1 x2 . Функция x1 ∨x2 называется дизъюнкцией x1 и x2 ; x1 + x2 называется суммой x1 и x2 по модулю 2; x1 → x2 называется импликацией x1 и x2 . Таблица 3 x1

x2

x1 &x2

x1 ∨ x2

x1 + x2

x1 → x2

0 0 1 1

0 1 0 1

0 0 0 1

0 1 1 1

0 1 1 0

1 1 0 1

e) называется Переменная xi (1 ≤ i ≤ n) функции f (x существенной, если найдутся α1 , . . . , αi−1 , αi+1 , . . . , αn ∈ E такие, что

f (α1 , . . . , αi−1 , 0, αi+1 , . . . , αn ) 6= 6= f (α1 , . . . , αi−1 , 1, αi+1 , . . . , αn ).

10

А. Б. Угольников. КЛАССЫ ПОСТА

e) существенно заВ этом случае говорят, что функция f (x висит от переменной xi . Переменная xi , не являющаяся существенной, называется несущественной (или фиктивной) e); в этом случае говорят, что функпеременной функции f (x e) не зависит существенно от переменной xi . Функция f (x ция называется существенной, если она имеет по крайней мере две существенные переменные.

Одним из удобных способов задания функций являются формулы. Пусть дано некоторое множество булевых функций (n1 )

A = {f1

(n2 )

(xi1 , . . . , xin1 ), f2

(n )

(xj1 , . . . , xjn2 ), . . .}.

(n )

Пусть F = {f1 1 , f2 2 , . . .} — множество функциональных символов, соответствующих функциям из A. Дадим индуктивное определение формулы над A. 1. Выражение xi , xi ∈ X , является формулой над A; такие формулы называются тривиальными. 2. Если Φ1 , . . . , Φn — формулы над A, n ≥ 1, а f (n) — n-местный функциональный символ из F , то выражение Φ = f (n) (Φ1 , . . . , Φn ) является формулой над A; формулы Φ1 , . . . , Φn называются подформулами формулы Φ. Предполагается при этом, что никаких других формул над A не существует, то есть каждая формула над A может быть получена применением конечного числа правил 1 и 2. Таким образом, формулы над A — это слова определенного вида (конечной длины) в алфавите X ∪ F ∪ V , где V — множество вспомогательных символов, состоящее из символов левой и правой скобок, а также запятой. Для сокращения записи формул введем некоторые соглашения:

§1 Некоторые определения и обозначения

11

1) будем опускать внешние скобки; 2) не будем заключать в скобки переменные и константы. e) будем обозначать такую формулу Φ, в котоЧерез Φ(x рую входят символы переменных x1 , . . . , xn и только они. e = (α1 , . . . , αn ) ∈ E n определим Для каждого набора α e которое принимает формула Φ на наборе значение Φ(α), e Если Φ — тривиальная формула вида xi , 1 ≤ i ≤ n, то α. это значение равно αi . Пусть Φ имеет вид e) = f (m) (Φ1 (x e1 ), . . . , Φm (x em )), Φ(x e1 , . . . , x em — поднаборы набора x e, где f (m) ∈ F , m ≥ 1, x а Φ1 , . . ., Φm — формулы над A, для которых значения e 1 ), . . ., Φm (α e m ) (где α e1, . . . , α e m — поднаборы набора α) e Φ1 (α уже определены и равны β1 , . . . , βm соответственно. Тогда e = f (m) (β1 , . . . , βm ). Φ(α)

Так как мы можем определить значение формулы Φ на любом наборе переменных, то тем самым мы сопоставим этой формуле некоторую функцию f (x1 , . . . , xn ). Про функцию, сопоставленную указанным выше способом формуле, говорят, что она реализуется или выражается этой формулой. Таким образом, каждая формула выражает какую-то функцию алгебры логики. Формулы Φ1 и Φ2 называются эквивалентными (обозначение Φ1 = Φ2 ), если они реализуют равные функции. Например, формулы x1 → x2 и x1 ∨ x2 эквивалентны. Отметим ряд свойств элементарных функций. Легко видеть, что функции x1 &x2 , x1 ∨ x2 и x1 + x2 обладают свойствами коммутативности и ассоциативности. Кроме того, эти функции обладают свойствами дистрибутивности:

12

А. Б. Угольников. КЛАССЫ ПОСТА

x1 & (x2 ∨ x3 ) = (x1 & x2 ) ∨ (x1 & x3 ) x1 & (x2 + x3 ) = (x1 & x2 ) + (x1 & x3 ), x1 ∨ (x2 & x3 ) = (x1 ∨ x2 ) & (x1 ∨ x3 ). Из этих свойств нетрудно вывести следующее правило: в конъюнкции из нескольких членов можно произвольным образом их переставлять и произвольным образом расставлять скобки. Аналогично для дизъюнкции и суммы по модулю 2. Например, ((x1 x2 )(x3 x4 ))x5 = (x1 (x3 x5 ))(x4 x2 ). Это правило позволяет ввести дальнейшие соглашения, упрощающие вид формул: 3) в формулах, получающихся многократным применением конъюнкции к более простым формулам, будем опускать скобки. Аналогично для дизъюнкции и суммы по модулю 2. Например, вместо ((Φ1 ∨ Φ2 ) ∨ Φ3 ) ∨ (Φ4 ∨ Φ5 ) будем писать Φ1 ∨ Φ2 ∨ Φ3 ∨ Φ4 ∨ Φ5 . Кроме того, будем считать, что 4) конъюнкция связывает сильнее чем дизъюнкция и сумма по модулю 2, и будем опускать соответствующие скобки. Например, вместо x1 ∨ (x2 x3 ) будем писать x1 ∨ x2 x3 . Введем также следующие соглашения для записи формул:

§1 Некоторые определения и обозначения

n W

Φi = Φ1 ∨ Φ2 ∨ . . . ∨ Φn ,

n P

Φi = Φ1 + Φ2 + . . . + Φn .

i=1

i=1

13

Итак, мы определили способ порождения функций алгебры логики функциями системы A ⊆ P2 . Этот способ мы будем называть операцией суперпозиции. Если функция e) реализована некоторой нетривиальной формулой над f (x e) получена операцией A, то будем также говорить, что f (x суперпозиции из функций системы A. Очевидно, что частными случаями операции суперпозиции являются следующие операции над булевыми функциями: перестановка переменных, переименование переменных, отождествление переменных, композиция функций (то есть подстановка функций на места переменных в другие функции). Множество всех функций, которые могут быть реализованы нетривиальными формулами над A будем называть замыканием множества A относительно операции суперпозиции (обозначение [A]C ). Множество A ⊆ P2 называется замкнутым относительно операции суперпозиции (или C -замкнутым классом), если [A]C = A. Определим еще один способ порождения функций — операцию введения несущественной переменной. Результатом применения этой операции к n-местной булевой функции f (n) (x1 , . . . , xn ), n ≥ 1, является (n + 1)-местная функция алгебры логики f (n+1) (x1 , . . . , xn , xn+1 ), значение которой на произвольном наборе (α1 , . . . , αn , αn+1 ) из E n+1 определяется равенством f (n+1) (α1 , . . . , αn , αn+1 ) = f (n) (α1 , . . . , αn ).

14

А. Б. Угольников. КЛАССЫ ПОСТА

Отметим, что эта операция, вообще говоря, не является частным случаем операции суперпозиции. Замыканием множества A (относительно операции суперпозиции и введения несущественной переменной) будем называть множество всех функций, которые могут быть получены из функций системы A применением операций суперпозиции и введения фиктивной переменной (обозначение [A]). Отметим некоторые свойства операции замыкания. 1. A ⊆ [A]. 2. Если A ⊆ B , то [A] ⊆ [B]. 3. [[A]] = [A]. Множество A ⊆ P2 называется замкнутым относительно операций суперпозиции и введения несущественной переменной (или замкнутым классом), если [A] = A. Очевидно, что для любых множеств A и B из P2 множество [A] ∩ [B] является замкнутым. Отметим также, что, если [A] = A, то [A]C = A; обратное, вообще говоря, не верно. Например, если f (1) (x) — произвольная булева функция одной переменной, то [{f (1) (x)}]C 6= [{f (1) (x)}]. Система функций алгебры логики A называется полной, если [A] = P2 . Говорят, что система A, A ⊆ F ⊆ P2 , порождает класс F (соответственно C -замкнутый класс F ), если [A] = F (соответственно [A]C = F ). В этом случае говорят также, что система A является полной в классе F . Базисом класса F называется такая порождающая F система A, любая собственная подсистема которой не порождает F . Класс называется конечно порожденным, если он имеет конечный базис.

§1 Некоторые определения и обозначения

15

Пусть F и G — замкнутые классы булевых функций такие, что F ⊆ G. Класс F называется предполным в G, если F 6= G и для любой функции f ∈ G\F система F ∪{f } является полной в G. Замкнутые классы, предполные в P2 , называются также предполными классами.

§2

Вспомогательные утверждения

По определению функция f (x1 , . . . , xn ) сохраняет константу 1 (соответственно 0), если f (e 1) = 1 (соответственно f (e 0) = 0). Функция f (x1 , . . . , xn ) называется двойственe) (обозначение f ∗ (x e)); функция f назыной к функции f (x e) навается самодвойственной, если f = f ∗ . Функция f (x e для любых двух e ≤ f (β) зывается монотонной, если f (α) e = (α1 , . . . , αn ), βe = (β1 , . . . , βn ) из E n , таких, что наборов α e) не превосα1 ≤ β1 , . . . , αn ≤ βn . Говорят, что функция f (x e) (обозначение f ≤ g ), если f (α) e ≤ f (α) e ходит функции g(x e ∈ E n ; f меньше g (обозначение для любого набора α f < g ), если f ≤ g и f 6= g . Отметим, что эти отношения (как и понятие равенства функций) определены только для функций, зависящих от одного и того же множества переменных. Тем не менее, мы иногда для удобства написания будем их использовать также для сравнения функций, зависящих от разных множеств переменных, добавляя тем самым необходимое число несущественных переменных в рассматриваемые функции. e) называется линейной, если выполняется Функция f (x равенство e) = c0 + c1 x1 + . . . + cn xn f (x

(сумма берется по модулю 2), конъюнкцией, если e) = c0 & (c1 ∨ x1 ) & . . . &(cn ∨ xn ), f (x

и дизъюнкцией, если

§2

Вспомогательные утверждения

17

e) = c0 ∨ c1 x1 ∨ . . . ∨ cn xn , f (x

где ci ∈ E , i = 1, . . . , n. Говорят, что функция удовлетворяет условию < 0µ > (соответственно < 1µ >), если любые µ наборов (µ ≥ 2), на которых функция равна 0 (соответственно 1), имеют общую нулевую (соответственно единичную) компоненту. Гоe) удовлетворяет условию < 0∞ > ворят, что функция f (x ∞ (соответственно < 1 >), если существует такой номер i, 1 ≤ i ≤ n, что f ≥ xi (соответственно f ≤ xi ). Определим следующие множества булевых функций: T1 — множество всех функций, сохраняющих константу 1; T0 — множество всех функций, сохраняющих константу 0; S — множество всех самодвойственных функций; M — множество всех монотонных функций; L — множество всех линейных функций; K — множество всех конъюнкций; D — множество всех дизъюнкций; Oµ — множество всех функций, удовлетворяющих условию < 0µ >, µ = 2, 3, . . . , ∞; I µ — множество всех функций, удовлетворяющих условию < 1µ >, µ = 2, 3, . . . , ∞; U — множество всех функций, существенно зависящих не более чем от одной переменной; C — множество всех функций, не имеющих существенных переменных. Нетрудно показать, что все перечисленные множества являются замкнутыми классами (см. также [23, 24]), и для всех µ = 2, 3, . . . , ∞ выполняются соотношения 1 ∈ O∞ ⊆ . . . ⊆ Oµ ⊆ . . . ⊆ O2 ; 0 ∈ I ∞ ⊆ . . . ⊆ I µ ⊆ . . . ⊆ I 2. Будем обозначать через fT1 , fT0 , fS , fM , fL , fK , fD такие булевы функции, которые не принадлежат множествам T1 , T0 , S , M , L, K , D соответственно.

18

А. Б. Угольников. КЛАССЫ ПОСТА

e) из P2 моУтверждение 1. Каждая функция f (n) (x жет быть представлена в следующей форме: e) = a + f (n) (x

X

ai1 ,...,is (xi1 ∨ . . . ∨ xis ),

(1)

i1 ,...,is

где a, ai1 ,...,is ∈ E , а сумма (по модулю 2) берется по всевозможным непустым подмножествам {i1 , i2 , . . . , is } множества {1, 2, . . . , n}, s ≥ 1. Доказательство этого утверждения нетрудно получить, учитывая, что для любой булевой функции f (x1 , . . . , xn ), n ≥ 2, справедливо представление f = (x1 ∨ f1 ) + (x1 ∨ f0 ) + f1 , где f1 = f (1, x2 , . . . , xn ), f0 = f (0, x2 , . . . , xn ), и используя соотношение x ∨ (y + z) = (x ∨ y) + (x ∨ z) + x. Выражение вида (1) будем называть суммой дизъюнкe) из P2 и число разций. Подсчитывая число функций f (x личных сумм дизъюнкций от переменных x1 , . . . , xn , получаем, что каждая булева функция имеет единственное представление в виде суммы дизъюнкций. Таким образом, каждую булеву функцию можно выразить в виде формулы над множеством {0, 1, x ∨ y, x + y}. Поэтому [{0, 1, x ∨ y, x + y}] = P2 . Порождающие системы замкнутых классов могут быть найдены с использованием следующего простого утверждения (см. также [23, 24]). Утверждение 2 (достаточное условие полноты). Пусть даны системы булевых функций A и B , такие что [A] = F и любая функция из A выражается формулой над B . Тогда [B] = F .

§2

Вспомогательные утверждения

19

Используя достаточное условие полноты, нетрудно показать, что системы {1, x ∨ y, x + y}, {1, xy, x + y}, {x, x ∨ y}, {x, xy}, {0, x ∨ y} являются полными. Утверждение 3 (принцип двойственности). Если e) = f0 (f1 (x e), . . . , fm (x e)), F (x

то ∗ e) = f0∗ (f1∗ (x e), . . . , fm e)). F ∗ (x (x

Доказательство этого утверждения непосредственно следует из определения (см. также [23, 24]). Утверждение 4. Для любых функций fK , fD из M выполняются соотношения x ∨ y ∈ [{1, fK }],

xy ∈ [{0, fD }].

Доказательство. Рассмотрим функцию fK (x1 , . . . , xn ) из M, существенно зависящую от всех своих переменных. Очевидно, что n ≥ 2. Так как fK ∈ / K , найдется набор e ∈ E n c одной нулевой компонентой (пусть, например, α e = (0, 1, . . . , 1)) такой, что α e = fK (0, 1, . . . , 1) = 1. fK (α)

Так как функция fK существенно зависит от переменной x1 , найдется набор βe = (β2 , . . . , βn ) такой, что e = 1, fK (1, β)

e = 0, fK (0, β)

βe 6≡ e 1. Пусть, например, β2 = . . . = βk = 0, βk+1 = . . . = βn = 1, k ≥ 2. Положим x1 = x, x2 = . . . = xk = y , xk+1 = . . . = xn = 1. Тогда fK (x, y, . . . , y, 1, . . . , 1) = x ∨ y, и поэтому x ∨ y ∈ [{1, fK }].

20

А. Б. Угольников. КЛАССЫ ПОСТА

Двойственным образом устанавливается справедливость соотношения xy ∈ [{0, fD }]. Утверждение 5. Для любых функций fM , fL из T1 выполняется соотношение x ∨ y ∈ [{1, fM , fL }]. Доказательство. Рассмотрим немонотонную функцию fM (x1 , . . . , xn ) из T1 . Очевидно, что n ≥ 2. Пусть, например, функция fM немонотонна по переменной x1 . Тогда суe = (α2 , . . . , αn ), что ществует такой набор α e = 1, fM (0, α)

e = 0, fM (1, α)

e 6≡ e α 1. Пусть, например, α2 = . . . = αk = 0, αk+1 = . . . . . . = αn = 1, k ≥ 2. Положим x1 = x, x2 = . . . = xk = y , xk+1 = . . . = xn = 1. Тогда fM (x, y, . . . , y, 1, . . . , 1) — это либо x ∨ y , либо x + y + 1.

Во втором случае рассмотрим нелинейную функцию fL (x1 , . . . , xn ) из T1 , n ≥ 2. Рассмотрим представление для fL в виде суммы дизъюнкций. Выберем в этом представлении среди дизъюнкций, содержащих по крайней мере две переменные, дизъюнкцию с наименьшим числом переменных. Пусть, например, она имеет вид x1 ∨ . . . ∨ xk , k ≥ 2. Положим x1 = x, x2 = . . . = xk = y , xk+1 = . . . = xn = 1. Тогда g(x, y) = fL (x, y, . . . , y, 1, . . . , 1) ∈ / L. Так как g ∈ T1 , то g — одна из следующих функций: x ∨ y , x ∨ y , x ∨ y , xy , и требуемое утверждение следует из представлений x ∨ y = (x ∨ y) + y + 1,

x ∨ y = xy + x + 1.

§2

Вспомогательные утверждения

21

Следствие 1. Для любой функции fM выполняется соотношение x ∈ [{0, 1, fM }]. Следствие 2. Для любой функции fL выполняется соотношение x ∨ y ∈ [{1, x, fL }]. Доказательство. Действительно, из доказательства утверждения 5 следует, что множество [{1, fL , f L }] содержит одну из следующих функций: x∨y , x∨y , x∨y , xy . Поэтому x ∨ y ∈ [{1, x, fL , f L }] = [{1, x, fL , }]. Следствие 3. Для любых функций fM , fL выполняется соотношение [{0, 1, fM , fL }] = P2 . Утверждение 6. Для любой функции fS из T0 ∩ T1 выполняется по крайней мере одно из следующих соотношений: x ∨ y ∈ [{fS }], x & y ∈ [{fS }]. Доказательство. Рассмотрим несамодвойственную функцию fS (x1 , . . . , xn ) из T0 ∩ T1 . Очевидно, что n ≥ 2, e = (α1 , . . . , αn ) таи fS (x, . . . , x) = x. Существует набор α кой, что fS (α1 , . . . , αn ) = fS (α1 , . . . , αn ), e 6≡ e где α 0, e 1. Пусть, например, α1 = . . . = αk = 0, αk+1 = . . . . . . = αn = 1, 1 ≤ k < n. Положим x1 = . . . = xk = x, xk+1 = = . . . = xn = y . Тогда fS (x, . . . , x, y, . . . , y) — это либо x ∨ y , либо x & y .

Утверждение 7. Для любой монотонной функции f , такой что f 6≡ 0, 1, выполняется соотношение f ∈ [{x ∨ y, xy}].

22

А. Б. Угольников. КЛАССЫ ПОСТА

Доказательство этого утверждения нетрудно получить, учитывая, что для любой функции f (x1 , . . . , xn ) из M , n ≥ 2, справедливо представление f = x1 &f1 ∨ f0 , где f1 = f (1, x2 , . . . , xn ), f0 = f (0, x2 , . . . , xn ), причем функции f1 и f0 принадлежат множеству M , и если при этом f 6≡ 0, 1, то f1 6≡ 0, f0 6≡ 1.

§3

Конечная порождаемость замкнутых классов

Лемма 1. Пусть A — произвольное множество функций алгебры логики такое, что x ∨ y ∈ [A]. Тогда если f ∈ [A ∪ {0}], g ∈ [A] и g ≤ f , то f ∈ [A]. e) и g(x e) удовлеДоказательство. Пусть функции f (x творяют условиям леммы, а Φf — формула над A ∪ {0}, реализующая f . Заменим всякое вхождение константы 0 в Φf на новую переменную y . Получим формулу Φ над A, e) ∈ [A], причем реализующую некоторую функцию h(y, x e) = f (x e). Так как g ≤ f , то h(0, x e) = g(x e) ∨ h(g(x e), x e) f (x

и, таким образом, f ∈ [A].

Определим функцию ω(x, y, z). Положим ω = x ∨ yz . Очевидно, что ω ∈ O∞ . Лемма 2. Для любой монотонной функции f ∈ O∞ , f 6≡ 1, выполняется соотношение f ∈ [{ω}]. Доказательство. Пусть f (x1 , . . . , xn )— произвольная монотонная функция из O∞ , f 6≡ 1, n ≥ 1. Очевидно, что x ∨ y ∈ [{ω}], xy ∈ [{ω, 0}]. Поэтому в силу утверждения 7 f ∈ [{ω, 0}]. Кроме того, xi ≤ f при некотором i, 1 ≤ i ≤ n, и xi ∈ [{ω}]. Поэтому в силу леммы 1 f ∈ [{ω}]. Определим функции dp (x1 , . . . , xp ), p ≥ 2, следующим образом: _ xi xj . dp (x1 , . . . , xp ) = 1≤i<j≤p

24

А. Б. Угольников. КЛАССЫ ПОСТА

Отметим следующие свойства функций ω и dp , p ≥ 2. 1. ω ∈ [{1, fK , fD }], если fK , fD ∈ M . Действительно, в силу утверждения 4 выполняются соотношения x ∨ y, xy ∈ [{0, 1, fK , fD }]. Поэтому в силу утверждения 7 ω ∈ [{x ∨ y, xy}] ⊆ [{0, 1, fK , fD }]. Кроме того, x, x ∨ y ∈ [{1, fK , fD }], x ≤ ω , а значит, в силу леммы 1 ω ∈ [{1, fK , fD }]. 2. ω ∈ [{1, d3 }]; если p > 3, то ω ∈ [{dp }]. Это свойство следует из соотношений d3 (1, x, d3 (x, y, z)) = ω,

dp (x, . . . , x, y, z) = ω.

3. dp+1 (x1 , . . . , xp , 1) = x1 ∨ . . . ∨ xp , dp+1 (x1 , . . . , xp , 0) = = dp (x1 , . . . , xp ). 4. dp+1 (x1 , . . . , xp+1 ) > dp (x1 , . . . , xp ). 5. dp ∈ Oµ , если p ≥ µ + 1; иначе dp ∈ / Oµ для всех ∞ µ ≥ 2; dp ∈ / O , для всех p ≥ 2. 6. [{ω}] ⊂ [{ω, dp+1 }] ⊂ [{ω, dp }], p ≥ 2. Действительно, в силу леммы 1 и свойства 4 при всех p ≥ 2 выполняются соотношения [{ω}] ⊆ [{ω, dp+1 }] ⊆ [{ω, dp }]. По определению ω ∈ O∞ , а в силу свойства 5 dp+1 6∈ O∞ . Кроме того, ω, dp+1 ∈ Op , но dp ∈ / Op . 7. d3 ∈ S ; а если p 6= 3, то dp ∈ / S. Пусть f (x1 , . . . , xn ) — некоторая монотонная функция, n ≥ 2. Обозначим через Ak (f ), k = 1, . . . , n − 1, множество всех функций от k переменных, получающихся из f отождествлением переменных.

§3

Конечная порождаемость замкнутых классов

25

Лемма 3. Для любой монотонной булевой функции f (x1 , . . . , xn ), n ≥ 2, выполняется соотношение f ∈ [{ω, dn } ∪ An−1 (f )]. Доказательство. Утверждение очевидно, если f — константа, а если f ∈ O∞ , f 6≡ 1, то оно следует из леммы 2. Пусть f ∈ / O∞ , f 6≡ 0. Положим Hf = {ω, dn } ∪ An−1 (f ). Доказательство будем вести индукцией по n. Случай n = 2 очевиден. Пусть n > 2 и утверждение леммы справедливо для всех функций, зависящих менее чем от n переменных. Положим g = f (0, x2 , . . . , xn ). Если g ≡ 0, то f (x, y, . . . , y) = x&f (1, y, . . . , y) = xy, то есть xy ∈ [An−1 (f )], и утверждение леммы следует из утверждения 7. Пусть g 6≡ 0. Рассмотрим следующие функции: fji = f (x1 , . . . , xj−1 , xi , xj+1 , . . . , xn ),

i, j = 1, . . . , n, i 6= j;

gji = g(x2 , . . . , xj−1 , xi , xj+1 , . . . , xn ),

i, j = 2, . . . , n, i 6= j;

ϕ(y1 , . . . , yn ) = y1 &(y2 ∨ . . . ∨ yn ) ∨ g(y2 , . . . , yn ); λ(x1 , . . . , xn ) = ϕ(x1 , f12 , . . . , f1n ). Положим Bn−2 (g) = {gji , где i, j = 2, . . . , n; i 6= j}. Очевидно, что Bn−2 (g) ⊆ An−2 (g),

[Bn−2 (g)] = [An−2 (g)].

26

А. Б. Угольников. КЛАССЫ ПОСТА

По предположению индукции существует формула над множеством {ω, dn−1 } ∪ An−2 (g), реализующая функцию g . Поэтому найдется формула Φg над {ω, dn−1 } ∪ Bn−2 (g), реализующая g(y2 , . . . , yn ). Заменим всякое вхождение функции gji в Φg на функцию fji , i, j = 2, . . . , n, i 6= j , а всякое вхождение функции dn−1 — на функцию dn , подставляя всякий раз на место первой переменной переменную y1 . Получим формулу Φ над множеством Hf , реализующую некоторую функцию h(y1 , . . . , yn ) ∈ [Hf ]. Из определения функций g , fji , gji и свойства 3 следует соотношение h(0, y2 , . . . , yn ) = g(y2 , . . . , yn ), а так как f (1, 0, . . . , 0) = 0 и dn (1, 0, . . . , 0) = 0, то выполняются равенства h(1, 0, . . . , 0) = 0 = g(0, . . . , 0). Поэтому справедливо представление ϕ(y1 , . . . , yn ) = y1 &(y2 ∨ . . . ∨ yn ) ∨ h(y1 , . . . , yn ). Таким образом, ϕ ∈ [Hf ], а значит, и λ ∈ [Hf ]. Так как f ∈ M , то для всех i = 2, . . . , n, то выполняются соотношения x1 &f1i ≤ f, f1i ≤ xi ∨ f. Поэтому λ = x1 &(f12 ∨ . . . ∨ f1n ) ∨ g(f12 , . . . , f1n ) ≤ ≤ f ∨ g(x2 ∨ f, . . . , xn ∨ f ) ≤ f. Применение к функциям f и λ леммы 1 доказывает требуемое утверждение.

§3

Конечная порождаемость замкнутых классов

27

e) — монотонная функция, f ∈ Пусть f (x / O∞ , f 6≡ 0. Обозначим через Ff множество всех таких функций, которые получаются из f отождествлением переменных (быть может, пустым) и не принадлежат O∞ , а при всяком отождествлении двух переменных переходят в функции из O∞ . Через p(f ) обозначим минимальное число существенных переменных у функций из Ff .

Поскольку f (x, . . . , x) = x ∈ O∞ , то Ff 6= ∅ и p(f ) ≥ 2. Кроме того, любая функция h из Ff , существенно зависящая от p переменных, имеет вид h = dp (из соотношения h ∈ / O∞ следует, что h(1, 0, . . . , 0) = ... = h(0, . . . , 0, 1) = 0, а из этих равенств и соотношения h(x1 , x1 , x3 , . . . , xp ) ∈ O∞ следует, что h(1, 1, 0, . . . , 0) = 1, и т. д.). Поэтому dp(f ) ∈ [{f }].

(2)

Лемма 4. Для любой монотонной функции f ∈ / O∞ , f 6≡ 0, выполняется соотношение f ∈ [{ω, dp(f ) }]. Доказательство. Очевидно, что n ≥ 2. В силу леммы 3 имеем e) ∈ [{ω, dn } ∪ An−1 (f )]. f (x Если p(f ) < n, то применим ко всем функциям из An−1 (f ) аналогичные соотношения. Получим f ∈ [{ω, dn , dn−1 } ∪ An−2 (f )] и т. д. В конце концов получим f ∈ [{ω, dn , dn−1 , . . . , dp(f ) } ∪ Ap(f )−1 (f )],

28

А. Б. Угольников. КЛАССЫ ПОСТА

причем каждая функция из Ap(f )−1 (f ) принадлежит множеству O∞ . Из леммы 2 и свойства 6 имеем f ∈ [{ω, dp(f ) }]. e) найдется монотонЛемма 5. Для любой функции f (x e) из [{1, x ∨ y, f }] такая, что g ≤ f . ная функция g(x При этом если f ∈ T0 , то g ∈ [{x ∨ y, f }].

Доказательство. Утверждение леммы очевидно, если f — монотонная функция. Пусть f (x1 , . . . , xn ) ∈ / M , n ≥ 1. Если n = 1, то f = x1 , и утверждение леммы очевидно. Пусть n ≥ 2 и f немонотонна, например, по переменe = (α2 , . . . , αn ) такой, что ной x1 . Тогда найдется набор α e = 1, f (1, α) e = 0. Обозначим через R множество всех f (0, α) e ∈ E n−1 . Пусть ψR (x2 , . . . , xn ) — характетаких наборов α ристическая функция1 множества R. Положим e) = f ((f (x e) ∨ ψR (x2 , . . . , xn )), x2 , . . . , xn ). g1 (x

Рассмотрим произвольный набор βe = (β1 , γe ) длины n. Если γe ∈ R, то g1 (1, γe ) = g1 (0, γe ) = f (1, γe ) = 0; если же γe ∈ / R, то либо f (0, γe ) = f (1, γe ), либо f (β1 , γe ) = β1 , поэтому e = f (β). e Таким образом, g1 < f . Кроме того, g1 (β) f ∨ ψR ∈ [{1, x ∨ y, f, 0}] = P2 (в силу следствия 3 из утверждения 5), f ≤ f ∨ψR , а значит, в силу леммы 1 f ∨ ψR ∈ [{1, x ∨ y, f }]. Но тогда и g1 ∈ [{1, x∨y, f }]. Если g1 — немонотонная функция, то применим к ней аналогичное преобразование и т. д. 1

Функция ψR (x2 , . . . , xn ) называется характеристической функцией множества R ∈ E n−1 , если равенство ψR (α2 , . . . , αn ) = 1 выполняется тогда и только тогда, когда (α2 , . . . , αn ) ∈ R .

§3

Конечная порождаемость замкнутых классов

29

В конце концов2 получим искомую монотонную функцию g , такую что g ≤ f , g ∈ [{1, x ∨ y, f }]. Пусть теперь функция f принадлежит T0 и пусть Φ — формула над {1, x ∨ y, f }, реализующая функцию g , g ≤ f . Заменим всякое вхождение константы 1 в Φ на x1 ∨ . . . ∨ xn . Получим формулу над {x∨y, f }, реализующую функцию g . Лемма 6. Пусть A ⊆ S и пусть B ⊆ [A], [B ∪ {1}] = = [A ∪ {1}]. Тогда [A] = [B] = [A ∪ {1}] ∩ S. Доказательство. Очевидно, что [B] ⊆ [A] ⊆ [A ∪ {1}] ∩ S. e) — произвольная функция из [A ∪ {1}] ∩ S , а Пусть f (x Φ — формула над B ∪ {1}, реализующая f . Заменим всякое вхождение константы 1 в Φ на переменную y . Получим e). формулу над B , реализующую некоторую функцию g(y, x e e Так как функции f и g принадлежат S , а g(1, x) = f (x), то имеем g ≡ f . Поэтому [A ∪ {1}] ∩ S ⊆ [B]. Таким образом,

[A] = [B] = [A ∪ {1}] ∩ S. Лемма 7. Пусть A ⊆ T0 и пусть B ⊆ [A], x ∨ y ∈ [A], [B ∪ {1}] = [A ∪ {1}]. Тогда [A] = [B ∪ {x ∨ y}] = [A ∪ {1}] ∩ T0 . Доказательство. Очевидно, что [B ∪ {x ∨ y}] ⊆ [A] ⊆ [A ∪ {1}] ∩ T0 . 2

Можно показать, что потребуется не более n шагов, так как функция g1 монотонна по переменной x1 и эта монотонность после каждого шага будет сохраняться.

30

А. Б. Угольников. КЛАССЫ ПОСТА

e) — произвольная функция из [A∪{1}]∩T0 , а Φ — Пусть f (x формула над B ∪ {1}, реализующая функцию f . Заменим всякое вхождение константы 1 в Φ на x1 ∨. . .∨xn . Получим некоторую формулу над B ∪ {x ∨ y}. Легко видеть, что она реализует функцию f . Поэтому

[A ∪ {1}] ∩ T0 = [B ∪ {x ∨ y}]. Двойственным образом доказывается следующая Лемма 8. Пусть A ⊆ T1 и пусть B ⊆ [A], xy ∈ [A], [B ∪ {0}] = [A ∪ {0}]. Тогда [A] = [B ∪ {xy}] = [A ∪ {0}] ∩ T1 . Теорема 1. Пусть A — произвольное множество булевых функций. Тогда класс [A] имеет конечный базис. Доказательство. Рассмотрим четыре случая. 1. 0, 1 ∈ [A]. Если A целиком содержится в одном из классов K, D, L, то утверждение теоремы очевидно. Пусть в A есть функции fK , fD , fL . Если A ⊆ M , то, согласно утверждениям 4 и 7, [A] = [{0, 1, x ∨ y, xy}] = [{0, 1, fK , fD }] = M ; если же A содержит немонотонную функцию fM , то в силу следствия 3 из утверждения 5 [A] = [{0, 1, fM , fL }] = P2 . 2. 1 ∈ [A], 0 ∈ / [A]. Легко видеть, что [A] ⊆ T1 . Если A целиком содержится в одном из классов K, D, L, то утверждение теоремы очевидно. Пусть в A есть функции fK , fD , fL . а) Пусть [A] ⊆ M . Тогда в силу свойства 1 ω ∈ [{1, fK , fD }] ⊆ [A].

§3

Конечная порождаемость замкнутых классов

31

Если A ⊆ O∞ , то в силу леммы 2 A ⊆ M ∩O∞ ⊆ [{1, ω}]. Поэтому [A] = M ∩ O∞ = [{1, ω}] = [{1, fK , fD }]. Если A 6⊆ O∞ , то рассмотрим p(A) = min p(f ), где минимум берется по всем функциям f из A таким, что f ∈ / O∞ ; пусть этот минимум достигается на функции f p(A) . Из лемм 2, 4 и свойства 6 следует, что A ⊆ [{1, ω, dp(A) }], причем в силу соотношения (2) dp(A) ∈ [{f p(A) }] ⊆ [A]. Таким образом, [A] = [{1, ω, dp(A) }] = [{1, fK , fD , f p(A) }]. б) Пусть в A есть функция fM . Согласно утверждению 5, имеем x ∨ y ∈ [{1, fM , fL }] ⊆ [A]. Так как x ∨ y = (x ∨ y) ∨ y , то x ∨ y ∈ [{x ∨ y}]. Кроме того, [{x ∨ y, 0}] = P2 . Поэтому в силу леммы 1 для любой функции f ∈ O∞ выполняется соотношение f ∈ [{x ∨ y)}] (см. также доказательство леммы 2), то есть O∞ ⊆ [{x∨y)}]. Если A ⊆ O∞ , то [A] = O∞ = [{x ∨ y)}] = [{1, fM , fL }]. Пусть A 6⊆ O∞ . По лемме 5 для каждой функции f из A найдется монотонная функция gf из [{1, x ∨ y, f }] такая, что gf ≤ f , причем если f ∈ / O∞ , то и gf ∈ / O∞ . Положим D=

[

{gf },

32

А. Б. Угольников. КЛАССЫ ПОСТА

где объединение берется по всем функциям f из A, f ∈ / O∞ . p(D) p(D) b Рассмотрим функцию g и обозначим через f (произвольную) функцию из A, при помощи которой получена функция g p(D) . Имеем g p(D) ∈ [{1, x ∨ y, fbp(D) }]. По доказанному выше [D] = [{1, ω, dp(D) }]. Положим B = {1, ω, dp(D) , x ∨ y}. Таким образом, если f ∈ A, то gf ∈ [B]. Поэтому в силу леммы 1 имеем A ⊆ [B]. Так как x ∨ yz = x ∨ (x ∨ y) ∨ z, то ω ∈ [{x ∨ y}]. Поэтому из соотношений 1, x ∨ y, ω ∈ [{x ∨ y}], dp(D) ∈ [{1, x ∨ y, fbp(D) } ⊆ [A] окончательно получаем [A] = [B] = [{x ∨ y, dp(D) }] = [{1, fM , fL , fbp(D) }]. 3. 0 ∈ [A], 1 ∈ / [A]. В этом случае утверждение теоремы следует из предыдущего случая в силу принципа двойственности. 4. 0, 1 ∈ / [A]. В силу выше приведенных рассмотрений для любой системы функций A существуют конечные системы B1 , B0 такие, что B1 , B0 ⊆ A и [B1 ∪ {1}] = [A ∪ {1}],

[B0 ∪ {0}] = [A ∪ {0}].

§3

Конечная порождаемость замкнутых классов

33

Поэтому если A ⊆ S , то в силу леммы 6 [A] = [B1 ]. Если же в A есть несамодвойственная функция fS , то для любой функции g ∈ A выполняется соотношение g(x, . . . , x) = x, так как иначе множество [{fS , g}] содержит константу. Поэтому A ⊆ T0 ∩ T1 , и в силу утверждения 6 множество [A] содержит по крайней мере одну из функций x ∨ y , xy . Если x ∨ y ∈ [A], то в силу леммы 7 [A] = [B1 ∪ {x ∨ y}]; а если xy ∈ [A], то в силу леммы 8 [A] = [B0 ∪ {xy}]. Замечание 1. Отметим, что 0, 1 ∈ [A] тогда и только тогда, когда система A содержит функции fT0 , fT1 , fS (так как 0, 1 ∈ [{fT0 , fT1 , fS }]); 1 ∈ [A], 0 ∈ / [A] тогда и только тогда, когда A ⊆ T1 и в A есть функция fT0 (так как 1 ∈ [{fT0 }]); 0 ∈ [A], 1 ∈ / [A] тогда и только тогда, когда A ⊆ T0 и в A есть функция fT1 (так как 0 ∈ [{fT1 }]); 0, 1 ∈ / [A] тогда и только тогда, когда A ⊆ T0 ∩ T1 или A ⊆ S .

§4

Структура замкнутых классов

Положим T01 = T0 ∩ T1 . Обозначим через M1 , L1 , K1 , D1 , U1 , C1 , I1µ пересечение класса T1 c множествами M , L, K , D , U , C , I µ соответственно; через M0 , L0 , K0 , D0 , U0 , C0 , O0µ — пересечение класса T0 c множествами M , L, K , D , U , C , Oµ соответственно; через S01 , M01 , L01 , K01 , D01 , U01 — пересечение T01 c множествами S , M , L, K , D , U соответственно; через M Oµ , M I µ , M O0µ , M I1µ , M U — пересечение M с множествами Oµ , I µ , O0µ , I1µ , U соответственно, µ = 2, 3, . . . , ∞. Положим SM = S ∩ M,

SL = S ∩ L,

SU = S ∩ U.

Теорема 2. Множество замкнутых классов алгебры логики исчерпывается следующим списком. 1. Классы, содержащие константы 0 и 1: P2 ,

M,

L,

K,

D,

U,

M U,

C.

2. Классы, содержащие 1 и не содержащие 0: T1 , M1 , L1 , K1 , D1 , U1 , C1 , Oµ , M Oµ , µ = 2, 3, . . . , ∞. 3. Классы, содержащие 0 и не содержащие 1: T0 , M0 , L0 , K0 , D0 , U0 , C0 , I µ , M I µ , µ = 2, 3, . . . , ∞. 4. Классы, не содержащие 0 и 1: T01 , S01 , M01 , L01 , K01 , D01 , U01 ; S, SM, SL, SU ;

35

§4 Структура замкнутых классов O0µ ,

M O0µ ,

I1µ ,

M I1µ ,

µ = 2, 3, . . . , ∞. При этом все перечисленные классы различны. Доказательство. Пусть F — произвольный замкнутый класс алгебры логики. Рассмотрим четыре случая. 1. 0, 1 ∈ F . Если F ⊆ L, то F — один из классов: L = [{1, x + y}],

U = [{1, x}],

M U = [{0, 1, x}],

C = [{0, 1}].

Если F ⊆ K и F 6⊆ U , то F = K = [{0, 1, xy}]. Если F ⊆ D и F 6⊆ U , то F = D = [{0, 1, x ∨ y}]. Если же F содержит функции fL , fK , fD , то в силу теоремы 1 (см. случай 1) F — один из классов: M = [{0, 1, x ∨ y, xy}],

P2 = [{x, x ∨ y}].

2. 1 ∈ F , 0 ∈ / F . Если F ⊂ L, то F — один из классов: L1 = [{x + y + 1}],

U1 = [{1, x}],

Если F ⊂ K и F 6⊆ U , то F = K1 = [{1, xy}]. Если F ⊂ D и F 6⊆ U , то F = D1 = [{1, x ∨ y}].

C1 = [{1}].

36

А. Б. Угольников. КЛАССЫ ПОСТА

Пусть F содержит функции fL , fK , fD . а) F ⊆ M . Если F ⊆ O∞ , то в силу теоремы 1 (см. случай 2, п. а ) F = M O∞ = [{1, ω}] = [{1, x ∨ yz}]. В противном случае F = [{1, ω, dµ+1 }] (здесь p(A) = µ + 1), µ = 1, 2, . . . . При µ = 1 согласно утверждению 7 F = M1 = [{1, x ∨ y, xy}]. При µ ≥ 2, с одной стороны, 1, ω, dµ+1 ∈ M Oµ (см. свойство 5); с другой стороны, для любой функции f из M Oµ , f ∈ / O∞ , выполняется неравенство p(f ) ≥ µ + 1 (см. свойство 5), а значит, в силу леммы 4 и свойства 6 f ∈ [{1, ω, dµ+1 }]. Таким образом, в силу свойства 2 F = M Oµ = [{1, ω, dµ+1 }] = [{1, dµ+1 }], µ = 2, 3, . . . . б) F 6⊆ M . Если F ⊆ O∞ , то в силу теоремы 1 (см. случай 2, п. б ) F = O∞ = [{x ∨ y}]. Если F 6⊆ O∞ , то F = [{x ∨ y, dµ+1 }],

µ = 1, 2, . . . .

37

§4 Структура замкнутых классов

При µ = 1, с одной стороны, x ∨ y, xy ∈ T1 ; e) из T1 выполняс другой стороны, для любой функции f (x ется соотношение x1 & . . . &xn ≤ f , причем

x1 & . . . &xn , x ∨ y ∈ [{x ∨ y, xy}], и поэтому в силу леммы 1 f ∈ [{x ∨ y, xy}]. Таким образом, F = T1 = [{x ∨ y, xy}]. При µ ≥ 2, с одной стороны, x ∨ y, dµ+1 ∈ Oµ ; с другой стороны, в силу леммы 5 для любой функции f из Oµ найдется функция g ∈ M Oµ такая, что g ≤ f , причем по доказанному выше g ∈ [{x ∨ y, dµ+1 }], и поэтому в силу леммы 1 функция f принадлежит множеству [{x ∨ y, dµ+1 }]. Таким образом, F = Oµ = [{x ∨ y, dµ+1 }], µ = 2, 3, . . . . 3. 0 ∈ F , 1 ∈ / F . В силу рассмотрений предыдущего случая и принципа двойственности F — один из классов: L0 = [{x + y}],

U0 = [{0, x}],

K0 = [{0, xy}], M I ∞ = [{0, x(y ∨ z)}],

C0 = [{0}],

D0 = [{0, x ∨ y}], M0 = [{0, x ∨ y, xy}],

38

А. Б. Угольников. КЛАССЫ ПОСТА

I ∞ = [{xy}],

T0 = [{xy, x ∨ y}],

M I µ = [{0, d∗µ+1 }],

I µ = [{xy, d∗µ+1 }],

µ = 2, 3, . . . (d∗µ+1 — функция, двойственная к функции dµ+1 (x1 , . . . xµ+1 )). 4. 0, 1 ∈ / F . Если F ⊂ L, то F — один из классов: SL = [{x + y + z + 1}], SU = [{x}],

L01 = [{x + y + z}]; U01 = [{x}].

Если F ⊂ K и F 6⊆ U , то F = K01 = [{xy}]. Если F ⊂ D и F 6⊆ U , то F = D01 = [{x ∨ y}]. Пусть F содержит функции fL , fK , fD . а) F ⊆ S . Если в F есть функция fT1 , то fT1 ∈ / M. Поэтому [F ∪ {1}] = [{1, fT1 , fL }] = P2 , и в силу леммы 6 F = S = [{fT1 , fL }], например, S = [{x, d3 }]. Пусть F ⊆ T1 . Если в F есть функция fM , то в силу утверждения 5 x ∨ y ∈ [{1, fM , fL }]. Подставляя в формулу над множеством {1, fM , fL }, реализующую функцию x ∨ y , вместо константы 1 переменную z ,

§4 Структура замкнутых классов

39

получим формулу над {fM , fL }, реализующую некоторую функцию h(x, y, z) из S , причем выполняется соотношение h(x, y, 1) = x ∨ y . Поэтому h(x, y, z) = z(x ∨ y) ∨ xy = d3 (x, y, z). Значит, d3 (x, y, z) ∈ [{fM , fL }], но тогда yz ∈ {1, fM , fL } и T1 = [{x ∨ y, xy} ⊆ [{1, fM , fL }]. Таким образом, [{1, fM , fL }] = [F ∪ {1}] = T1 , и в силу леммы 6 F = T1 ∩ S = S01 = [{fM , fL }], например, S01 = [{d3 (x, y, z)}]. Если F ⊆ M , то в силу утверждения 4 x∨y ∈ [{1, fK }], а значит, d3 (x, y, z) ∈ [{1, fK }] (рассуждение аналогично приведенному выше). Так как в силу свойства 1 выполняется соотношение ω ∈ [{1, fK , fD }], то [F ∪ {1}] ⊇ [{1, fK , fD }] ⊇ [{1, ω, d3 }]. Кроме того, для любой функции f из SM , f ∈ / O∞ , в силу свойства 7 выполняется равенство p(f ) = 3. Поэтому, согласно лемме 4, имеем F ⊆ SM ⊆ [{1, ω, d3 }] = M O2 , и [F ∪ {1}] = [{1, fK , fD }] = [{1, ω, d3 }] = M O2 . Таким образом, в силу леммы 6 F = M O2 ∩ S = SM = [{fK , fD }], например, SM = [{d3 }].

40

А. Б. Угольников. КЛАССЫ ПОСТА

Пусть в F есть функция fS . Тогда в силу теоремы 1 (см. случай 4) F ⊆ T01 , и согласно утверждению 6 либо x∨y ∈ F , либо xy ∈ F . б) x ∨ y ∈ F . Пусть F ⊆ M . Если F ⊆ O∞ , то в силу теоремы 1 (см. случай 2, п. а ) [F ∪ {1}] = M O∞ = [{1, ω}] = [{1, fK , fD }], и в силу леммы 7 F = M O∞ ∩ T0 = M O0∞ = [{x ∨ y, fK , fD }], например, M O0∞ = [{x ∨ y, ω}] = [{x ∨ yz}]. В противном случае [F ∪ {1}] = [{1, ω, dµ+1 }] = [{1, fK , fD , f µ+1 }], µ = 1, 2, . . . . В силу леммы 7 F = [{1, ω, dµ+1 }] ∩ T0 = [{x ∨ y, fK , fD , f µ+1 }], µ = 1, 2, . . . . При µ = 1 F = M1 ∩ T0 = M01 = [{x ∨ y, xy}]. При µ ≥ 2 F = M Oµ ∩ T0 = M O0µ , например, M O0µ = [{x ∨ y, dµ+1 }].

§4 Структура замкнутых классов

41

Пусть в F есть функция fM . Если F ⊆ O∞ , то в силу теоремы 1 (см. случай 2, п. б ) [F ∪ {1}] = O∞ = [{x ∨ y}] = [{1, fM , fL }], и в силу леммы 7 F = O∞ ∩ T0 = O0∞ = [{x ∨ y, fM , fL }], например, O0∞ = [{x ∨ y, x ∨ yz}] = [{x ∨ yz}]. В противном случае [F ∪ {1}] = [{x ∨ y, dµ+1 }] = [{1, fM , fL , fbµ+1 }], µ = 1, 2, . . . . В силу леммы 7 F = [{x ∨ y, dµ+1 }] ∩ T0 = [{x ∨ y, fM , fL , fbµ+1 }], µ = 1, 2, . . . . При µ = 1 F = T1 ∩ T0 = T01 , например, T01 = [{x ∨ y, x ∨ yz, xy}] = [{x ∨ yz, xy}]. При µ ≥ 2

F = Oµ ∩ T0 = O0µ ,

например, O0µ = {x ∨ y, x ∨ yz, dµ+1 }] = [{x ∨ yz, dµ+1 }], µ = 2, 3, . . . .

42

А. Б. Угольников. КЛАССЫ ПОСТА

в) xy ∈ F . В этом случае в силу принципа двойственности и рассмотрений предыдущего случая F — один из классов: M I1∞ = [{x(y ∨ z)}], I1∞ = [{x(y ∨ z)],

M01 ,

T01 ,

M I1µ = [{xy, d∗µ+1 }],

I1µ = [{x(y ∨ z), d∗µ+1 }],

µ = 2, 3, . . . . Таким образом, первая часть утверждения теоремы доказана; доказательство второй части легко извлекается из приведенных рассмотрений. Замечание 2. На основе приведенных рассмотрений нетрудно построить полную диаграмму включений классов функций алгебры логики, замкнутых относительно операций суперпозиции и введения несущественной переменной (рис. 1). В приложении (табл. 4) приведен полный перечень замкнутых классов булевых функций.

Рис. 1: диаграмма включений замкнутых классов

§4 Структура замкнутых классов 43

§5

Структура C -замкнутых классов

Поскольку каждый замкнутый класс функций алгебры логики является C -замкнутым, перечислим только такие C -замкнутых классы, которые не являются замкнутыми. Определим следующие множества булевых функций:

c01 — множество всех конъюнкций, не имеющих фиктивK b 01 — множество всех дизъюнкций, не ных переменных; D

имеющих фиктивных переменных. Положим c0 = K c01 ∪ C0 , K

b1 = D b 01 ∪ C1 . D (1)

(1)

(1)

Обозначим через U (1) , M U (1) , C (1) , U1 , C1 , U0 , (1) (1) C0 , SU (1) , U01 множества всех функций одной переменной из классов U , M U , C , U1 , C1 , U0 , C0 , SU , U01 соответственно. Положим b = U (1) ∪ C, U (1)

b1 = U ∪ C1 , U 1

d M U = M U (1) ∪ C, (1)

b0 = U ∪ C0 . U 0

Легко видеть, что все перечисленные множества являются C -замкнутыми и не являются замкнутыми классами. Утверждение 8. Для любой системы A ⊆ P2 , содер(2) жащей селекторную функцию e1 , выполняется соотношение [A]C = [A].

45

§5 Структура C -замкнутых классов

Доказательство этого утверждения следует из определения операций суперпозиции и введения фиктивной переменной. Теорема 3. Множество C -замкнутых классов алгебры логики, не являющихся замкнутыми классами, исчерпывается следующим списком. 1. Классы, содержащие существенные функции: c0 , K

c01 , K

b 1, D

b 01 . D

2. Классы, содержащие константы 0(n) или 1(n) , n ≥ 2, и не содержащие существенных функций: b, U

d M U,

b1 , U

b0 . U

3. Классы функций одной переменной: (1)

(1)

(1)

(1)

(1)

U (1) , M U (1) , C (1) , U1 , C1 , U0 , C0 , SU (1) , U01 . При этом все перечисленные классы различны. Доказательство. Пусть F — произвольный C -замкнутый класс алгебры логики такой, что F 6= [F ]. Рассмотрим три случая. 1. F содержит существенную функцию f (x1 , . . . , xn ), n ≥ 2. Очевидно, что f ∈ / S. (2)

a) F ⊆ D . Если 0(n) ∈ F , n ≥ 1, то e1 ∈ F , и в силу утверждения 8 выполняется равенство F = [F ], что противоречит условию; если 1(n) ∈ F , 0(m) ∈ / F , n, m ≥ 1, то b 1 = [{x ∨ y, 1(1) }]C ; F =D если 0(m) , 1(n) ∈ / F , n, m ≥ 1, то b 01 = [{x ∨ y}]C . F =D

46

А. Б. Угольников. КЛАССЫ ПОСТА

б) F ⊆ K . Из рассмотрений, аналогичных предыдущему случаю, следует, что F — один из классов: c0 = [{xy, 0(1) }]C , F =K

c01 = [{xy}]C . F =K

Пусть F содержит функции fK и fD . Покажем, что в (2) этом случае F содержит функцию e1 . Если 0, 1 ∈ F , то (2)

e1 ∈ [{0, 1, f }]C ⊆ F. Если 1 ∈ F , 0 ∈ / F , то F ⊆ T1 . Рассмотрим функцию fD (x1 , . . . , xm ), m ≥ 1. Так как fD ∈ / D , то m ≥ 2 и найдется e = (α1 , . . . , αm ) такой, что α e 6= (0, . . . , 0), fD (α) e = 0, набор α m e e e выполняется а для любого набора β ∈ E такого, что β ≥ α e = 1. Пусть, например, α1 = . . . = α = 0, равенство fD (β) k αk+1 = . . . = αm = 1, k < m. Положим x1 = . . . = xk = x, xk+1 = . . . = xm = 1(y). Тогда (2)

fD (x, . . . , x, 1(y), . . . , 1(y)) = e1 (x, y). Если 0 ∈ F , 1 ∈ / F , то F ⊆ T0 . Рассмотрим функцию fK (x1 , . . . , xp ), p ≥ 1. Так как fK ∈ / K , то p ≥ 2 и найдется e = (α1 , . . . , αp ) такой, что α e 6= (1, . . . , 1), fK (α) e = 1, набор α p e e e выполняется а для любого набора β ∈ E , такого что β ≤ α e = 0; пусть, например, α1 = . . . = α = 1, равенство fK (β) k αk+1 = . . . = αp = 0, k < p. Положим x1 = . . . = xk = x, xk+1 = . . . = xp = 0(y). Тогда (2)

fK (x, . . . , x, 0(y), . . . , 0(y)) = e1 (x, y). Пусть 0, 1 ∈ / F . Тогда F ⊆ T0 ∩ T1 (так как f ∈ / S ), и из доказательства утверждения 6 следует, что множество [{f }]C содержит по крайней мере одну из следующих функций: x ∨ y , xy . Поэтому выполняется соотношение (2)

e1 (x, y) ∈ [{f, fD , fK }]C .

§5 Структура C -замкнутых классов

47

(2)

Таким образом, функция e1 принадлежит F , и в силу утверждения 8 F = [F ]C , что противоречит условию. 2. F не содержит существенных функций, и F 6⊆ U (1) . Если 0(2) , 1(2) ∈ F , то F — один из классов: b = [{1(2) , x}]C , U

d M U = [{0(2) , 1(2) , x}]C ;

если 1(2) ∈ F, 0(2) ∈ / F , то b1 = [{1(2) , x}]C ; F =U

если же 0(2) ∈ F, 1(2) ∈ / F , то b0 = [{0(2) , x}]C . F =U

3. F ⊆ U (1) . Тогда F — один из классов: U (1) = [{1(1) , x}]C ,

C (1) = [{0(1) , 1(1) }]C ;

M U (1) = [{0(1) , 1(1) , x}]C , (1)

U1

= [{1(1) , x}]C , (1)

C1 = [{1(1) }]C , SU (1) = [{x}]C ,

(1)

U0

= [{0(1) , x}]C ;

(1)

C0 = [{0(1) }]C , (1)

U01 = [{x}]C .

Таким образом, первая часть утверждения теоремы доказана, вторая часть очевидна. Замечание 3. На основе приведенных выше рассмотрений нетрудно построить полную диаграмму включений всех классов Поста — C -замкнутых классов булевых функций (рис. 2).

48

А. Б. Угольников. КЛАССЫ ПОСТА

P2 T0 I2 I3 I

T1 M

M0 MI2

MI3

T01 I21

I13 I1 MI21

O2 O20

M1 M01 S S01

MI31

MI

O3 O30

O

MO2

O0

MO02

MO3 MO03

SM

MO

MI1

MO0

K

D

L K1

K0

D0

L1

L0

K01

D1 D01

SL U

L01 SU

MU K0 K01

U

U0

U1 U(1) MU C

D1 D01

U01 MU(1) SU(1) U1

U0 U(1) 1

U(1)0 C0

C(1) C(1)0

U(1) 01

C1 C(1)0

Рис. 2: диаграмма включений классов Поста

§5 Структура C -замкнутых классов

49

В приложении (табл. 5) приведен перечень всех C -замкнутых классов функций алгебры логики, которые не являются замкнутыми (см. также [9]).

C

MU

Классы, содержащие константы 0 и 1: P2 M L K D U

Замкнутый класс

Приложение

все булевы функции монотонные функции линейные функции конъюнкции дизъюнкции функции, имеющие не более одной существенной переменной монотонные функции, имеющие не более одной существенной переменной функции, не имеющие существенных переменных

Входящие в него функции

0, 1

0, 1, x

x, xy 0, 1, xy, x ∨ y 1, x + y 0, 1, xy 0, 1, x ∨ y 1, x

Пример базиса

R9

R11

C1 A1 L1 P6 S6 R13

Обозначение у Поста

Замкнутые классы булевых функций

O7

O8

C1 A1 L1 P6 S6 O9

Обозначение из [19]

Таблица 4

50 А. Б. Угольников. КЛАССЫ ПОСТА

P5 S4

1, xy 1, x ∨ y 1, x

конъюнкции, сохраняющие 1 дизъюнкции, сохраняющие 1 селекторные функции и константы 1 константы 1

K1 D1 U1 C1

F3µ

F3µ 1, dµ+1

монотонные функции, удовлетворяющие условию < 0µ >

M Oµ (µ = 2, 3, . . .)

F4µ x ∨ y, dµ+1

функции, удовлетворяющие условию < 0µ >

F4µ

Oµ (µ = 2, 3, . . .)

O2

R2

O5

S3

P5

L2

A2

C2

Обозначение из [19]

1

R6

L2

x+y+1

линейные функции, сохраняющие 1

L1

M1

A2

функции, сохраняющие 1

T1 1, xy, x ∨ y

Обозначение у Поста

монотонные функции, сохраняющие 1

Пример базиса

C2

Входящие в него функции

x ∨ y, xy

Классы, содержащие 1 и не содержащие 0:

Замкнутый класс

Продолжение таблицы 4

Приложение 51

P4 S5

0, xy 0, x

селекторные функции и константы 0 константы 0 функции, удовлетворяющие условию < 1µ >

U0 C0 I (µ = 2, 3, . . .) µ

xy,

O3 F8µ

R3 F8µ d∗µ+1

O6

S5

P3

L3

A3

C3

F3∞

F4∞

Обозначение из [19]

0

R8

L3

0, x ∨ y

x+y

дизъюнкции, сохраняющие 0

K0

L0

D0

A3

монотонные функции, сохраняющие 0 линейные функции, сохраняющие 0 конъюнкции, сохраняющие 0

M0

0, xy, x ∨ y

функции, сохраняющие 0

T0

Классы, содержащие 0 и не содержащие 1: C3

F3∞

1, x ∨ yz

xy, x ∨ y

F4∞

x∨y

функции, удовлетворяющие условию < 0∞ > монотонные функции, удовлетворяющие условию < 0∞ >

O∞ M O∞

Обозначение у Поста

Пример базиса

Входящие в него функции

Замкнутый класс

Продолжение таблицы 4

52 А. Б. Угольников. КЛАССЫ ПОСТА

D01

K01

L01

M01

Классы, не содержащие 0 и 1: T01 S01

M I∞

функции, сохраняющие 0 и 1 самодвойственные функции, сохраняющие 0 и 1 монотонные функции, сохраняющие 0 и 1 линейные функции, сохраняющие 0 и 1 конъюнкции, сохраняющие 0 и1 дизъюнкции, сохраняющие 0 и1

P2 S2

xy x∨y

L4

A4

xy, x ∨ y x+y+z

C4 D1

F7∞

0, x(y ∨ z)

x ∨ yz, xy d3 (x, y, z)

F8∞

xy

S1

P1

L4

A4

C4 D1

F7∞

F8∞

F7µ

F7µ

0, d∗µ+1

монотонные функции, удовлетворяющие условию < 1µ > функции, удовлетворяющие условию < 1∞ > монотонные функции, удовлетворяющие условию < 1∞ >

M Iµ (µ = 2, 3, . . .) I∞

Обозначение из [19]

Обозначение у Поста

Пример базиса

Входящие в него функции

Замкнутый класс

Продолжение таблицы 4

Приложение 53

I1µ (µ = 2, 3, . . .)

M O0µ (µ = 3, 4, . . .)

M O02

O0µ (µ = 2, 3, . . .)

SU

x(y ∨ z), d∗µ+1

dµ+1

x ∨ y, d3

x ∨ yz, dµ+1

x

x+y+z+1

x d3 (x, y, z) d3 (x, y, z)

селекторные функции самодвойственные функции монотонные самодвойственные функции линейные самодвойственные функции селекторные функции и их отрицания функции, удовлетворяющие условию < 0µ > и сохраняющие 0 монотонные функции, удовлетворяющие условию < 02 > и сохраняющие 0 монотонные функции, удовлетворяющие условию < 0µ > и сохраняющие 0 функции, удовлетворяющие условию < 1µ > и сохраняющие 1

U01 S SM SL

Пример базиса

Входящие в него функции

Замкнутый класс

F5µ

F2µ

F22

F1µ

R4

L5

R1 D3 D2

Обозначение у Поста

F5µ

F2µ

F22

F1µ

O4

L5

O1 D3 D2

Обозначение из [19]

Продолжение таблицы 4

54 А. Б. Угольников. КЛАССЫ ПОСТА

F6µ

F1∞

F2∞

F5∞

F6∞

d∗µ+1

x ∨ yz

x ∨ yz

x(y ∨ z)

x(y ∨ z)

монотонные функции, удовлетворяющие условию < 1µ > и сохраняющие 1 функции, удовлетворяющие условию < 0∞ > и сохраняющие 0 монотонные функции, удовлетворяющие условию < 0∞ > и сохраняющие 0 функции, удовлетворяющие условию < 1∞ > и сохраняющие 1 монотонные функции, удовлетворяющие условию < 1∞ > и сохраняющие 1

O0∞

M O0∞

I1∞

M I1∞

F62

M I1µ (µ = 3, 4, . . .)

xy, d3

монотонные функции, удовлетворяющие условию < 12 > и сохраняющие 1

Обозначение у Поста

M I12

Пример базиса

Входящие в него функции

Замкнутый класс

F6∞

F5∞

F2∞

F1∞

F6µ

F62

Обозначение из [19]

Продолжение таблицы 4

Приложение 55

функции e, 0(1) функции 0(1) , 1(1)

(1) U0

C (1)

U

(1)

M U (1)

функции e, e, 0

(1)

(1)

,1

функции e, 0(1) , 1(1)

функции e, 1(1)

U1

(1)

функции e, e

SU (1)

1

(1)

,x

0(1) , 1(1) , x

0(1) , 1(1)

0(1) , x

1(1) , x

x

0(1)

1

функции 0(1)

функции 1

(1)

x

Пример базиса

(1)

функции e

Входящие в него функции

(1) C1 (1) C0

U01

(1)

Классы, не содержащие существенных функций:

Замкнутый класс

C-замкнутые классы булевых функций (не являющиеся замкнутыми)

O9

O8

O7

O6

O5

O4

O3

O2

O1

Обозначение у Поста

Таблица 5

56 А. Б. Угольников. КЛАССЫ ПОСТА

b 01 D

b 01 K

b1 D

Классы, содержащие существенные функции: b0 K

b1 U b0 U , n = 1, 2, . . . , n = 1, 2, . . .

(n)

конъюнкции, не имеющие фиктивных переменных, и константы 0(n) , n = 1, 2, . . . дизъюнкции, не имеющие фиктивных переменных, и константы 1(n) , n = 1, 2, . . . конъюнкции, не имеющие фиктивных переменных дизъюнкции, не имеющие фиктивных переменных

функции e, 0

функции e, 1

, n = 1, 2, . . .

,1

(n)

функции e, 0

(n)

функции e, e, 0(n) , 1(n) , n = 1, 2, . . .

b U d M U (n)

Входящие в него функции

Замкнутый класс

0

,x

x∨y

xy

1(1) , x ∨ y

0(1) , xy

,x

,x

(2)

0

1

(2)

,1

(2)

(2)

1(2) , x

Пример базиса

S1

P1

S3

P3

R7

R5

R10

R12

Обозначение у Поста

Продолжение таблицы 5

Приложение 57

Список литературы [1] Гаврилов Г. П. Индуктивные представления булевых функций и конечная порождаемость классов Поста // Алгебра и логика. 1984. 23, N=◦ 1. 3–26. [2] Гаврилов Г. П. Функциональные системы дискретной математики. М.: Изд-во МГУ, 1985. 39 c. [3] Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. М.: Физматлит, 2004. 416 с. [4] Мальцев А. И. Итеративные алгебры и многообразия Поста // Алгебра и логика. Новосибирск, 1966. 5, N=◦ 2. 3–26. [5] Мальцев А. И. Итеративные алгебры Поста. Новосибирск: Изд-во НГУ, 1976. 100 с. [6] Марченков С. С. К существованию конечных базисов в замкнутых классах булевых функций // Алгебра и логика. 1984. 23, N=◦ 1. 88–99. [7] Марченков С. С., Угольников А. Б. Замкнутые классы булевых функций. М.: Изд-во ИПМ им. М. В. Келдыша АН СССР, 1990. 147 с. [8] Марченков С. С. Замкнутые классы булевых функций. M.: Физматлит, 2000. 126 с.

Литература

59

[9] Нечипорук Э. И. Синтез логических сетей в неполных и вырожденных базисах // Проблемы кибернетики. Вып. 14. М.: Наука, 1965. 111–160. [10] Угольников А. Б. Синтез схем и формул в неполных базисах // Доклады АН СССР. 1979. 249, N=◦ 1. 60–63. [11] Угольников А. Б. Синтез схем и формул в неполных базисах // Препринт N=◦ 112 ИПМ им. М. В. Келдыша АН СССР. М., 1980. 22 с. [12] Угольников А. Б. О релизации булевых функций из некоторых замкнутых классов схемами из функциональных элементов в неполных базисах // Вестн. Моск. ун-та. Матем. Механ. 1985, N=◦ 3. 76–78. [13] Угольников А. Б. О сложности реализации булевых функций схемами в базисе из медианы и импликации // Вестн. Моск. ун-та. Матем. Механ. 1987. N=◦ 3. 87–89. [14] Угольников А. Б. О глубине и полиномиальной эхвивалентности формул для замкнутых классов двузначной логики // Математические заметки. 1987. 42, N=◦ 4. 603– 612. [15] Угольников А. Б. О глубине и сложности формул, реализующих функции из замкнутых классов // Докл. АН СССР. 1988. 298, N=◦ 6. 1341–1344. [16] Угольников А. Б. О глубине формул в неполных базисах // Математические вопросы кибернетики. Вып. 1. М.: Наука, 1988. 242–245. [17] Угольников А. Б. О замкнутых классах Поста // Известия ВУЗов. Математика. 1988, N=◦ 7 (314). 79–88.

60

А. Б. Угольников. КЛАССЫ ПОСТА

[18] Яблонский С. В. Функциональные построения в k -значной логике // Труды матем. ин-та АН СССР. 1958. 51. 5–142. [19] Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. М.: Наука, 1966. 119 с. [20] Яблонский С. В. Введение в теорию функций k -значной логики // Дискретная математика и математические вопросы кибернетики, 1. М.: Наука, 1974. 9–66. [21] Яблонский С. В. О некоторых результатах в теории функциональных систем // Труды Междунар. конгр. математиков. Хельсинки. 1978. 963–971. [22] Яблонский С. В. О замкнутых классах в P2 // Проблемы кибернетики. Вып. 39. М.: Наука, 1982. 262–262. [23] Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001. 384 с. [24] Конспект лекций О. Б. Лупанова по курсу "Введение в математическую логику" / Отв. ред. А. Б. Угольников. М.: Изд-во ЦПИ при механико-математическом факультете МГУ им. М. В. Ломоносова, 2007. 192 с. [25] Benzaken C. Definitions et proprietes de certains familles de fonctions boole´ennes croissantes // Compt. Rend. Acad. Sci. Paris. 1964. 259, groupe I. 1369–1371. [26] Benzaken C. Les familles de fonctions boole´ennes deduites de certaines familles de fonctions boole´ennes croissantes. Criteres de determination de l’indice d’une fonction croissante // Compt. Rend. Acad. Sci. Paris. 1965. 260, groupe I. 1528–1531.

Литература

61

[27] Benzaken C. Treillis des familles de fonctions boole´ennes croissantes, applications au coloriage d’un graphe // S´eminaire Dubreil — Pisot (Alg`ebre et Th´eorie des nombres) 19e ann´ee, 1965/1966, N=◦ 2. 1–13. [28] Kuntzman J. Alg`ebre de Boole. Bibliotheque de l’Ingenieur // Automaticien. Paris: Dunod, 1965. 319 p. [29] Lau D. On closed subsets of Boolean functions (A new proof for Post’s theorem) // J. Inform. Process. Cybernet. EIK. 1991. 27 N=◦ 3. 167–178. [30] Lau D. Funktionenenalgebren u ¨ber endlichen Mengen. Berlin, Heidelberg, New York, Hong Kong, London, Milan, Paris, Tokio: Springer, 2004. 652 p. [31] Pippenger N. Theories of Computability. Cambridge: Cambridge Univ. Press, 1997. 251 p. [32] Post E. L. Determination of all closed systems of truth tables // Bull. of the Amer. Math. Soc. 1920. 26. 437–437. [33] Post E. L. Introduction to a general theory of elementary propositions // Amer. J. Math. 1921. 43, N=◦ 3. 163–185. [34] Post E. L. Two-valued iterative systems of mathematical logic // Annals of Math. Studies. Princeton–London: Princeton Univ. Press, 1941. 5. 122 p. [35] Reschke M., Denecke K. Ein neuer Beweis f¨ ur die Ergebniss von E.L. Post u ¨ber abgeschlossene Klassen Boolescher Funktionnen // J. Process. Cybern. EIK. 1989. 25, N=◦ 7. 361–380.

62

А. Б. Угольников. КЛАССЫ ПОСТА

[36] Ugolnikov A. B. Complexity and depth of formulas realizing functions from closed classes // Proc. of Fundamentals of Computation Theory. Lecture Notes in Comp. Sci. 278. Berlin: Springer - Verlag, 1987. 456–461. [37] Solvability, provability, definability: the collected works of Emil L. Post / Martin Davis, editor. Boston, Basel, Berlin: Birkh¨auser, 1994. 554 p.

Учебное пособие

УГОЛЬНИКОВ Александр Борисович

КЛАССЫ ПОСТА

Оригинал-макет: О. С. Дудакова

Подписано в печать 21.12.2007 г. Формат 60×90 1/16. Усл. печ. л. 4,0 Заказ Тираж 300 экз. Издательство Центра прикладных исследований при механико-математическом факультете МГУ. г. Москва, Ленинские горы. Изд. лиц. № 04059 от 20.02.2001 г. Отпечатано на типографском оборудовании механико-математического факультета МГУ им. М. В. Ломоносова.