Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Если х)— произвольная функция одной переменной из Рк, то
§(х)= шах {/5(0), о(х), 1{х), ../8(й-1),а-1(з:)},
и, в частности, ~а = тах{Д_,1 о (а), /»-иП.-м/и-Дж)}-
в) Получение тт(г1( а2). Мы видели, что
'-'ппп(а„ аг) = тах(~~аг).
4 С. В. Яблонский
MI 4.1. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
<) г под а
min(;ri, хг) — ~max(~2i, ~32).
Таким образом, мы можем при помощи формул над исходной системой функций выразить любую из функций системы
{О, 1, ..к~ 1, /о(я), ..7h-i(tf),
min(ari, а?2)', max(xi, x2)},
относительно которой доказано, что она полная. Поэтому и система {?, шах (я,, х2)} является полной. Теорема доказана.
Введем обозначение: Уь(я1, хг) =max(ari1 я2) + 1-
Функция Vk (хи ага) называется функцией Вебба и представляет собой аналог функции Шеффера.
4. Система ф = (УДач, я2)} является полной. Вопрос о ее полноте может быть легко сведен к полноте системы 3.
С понятием полноты связано понятие замыкания и замкнутого класса.
Определение. Пусть 2)1 — произвольное подмножество функций из Замыканием 501 называется множество [50t] всех функций из Ph, представимых в виде формул через функции множества 501.
Определение. Класс (множество) 501 называется (функционально) замкнутым, если [SDt] = 501.
Для данных понятий справедливы высказывания, которые были сделаны при рассмотрении аналогичных понятий в Р2. Приведем примеры замкнутых множеств.
Пример 2. 1) Класс ЗЛ = JPfcf очевидно, является замкнутым.
2) Пусть еГ Обозначим через Tg множество всех функций f{x 1, ..хп) из Рк таких, что }(аи ..., а») в 8, если (г = 1, ..л). Другими словами, Tg — мно^
жество всех функций из Pkt сохраняющих <%\ будем , записывать это так:
/(#, <Г, ...,
Класс 50t — Tg, очевидно, является замкнутым.
IJ терминах замыкания можно дать другое определении полноты, эквивалентное исходному: 50t — полная снегами, если [50t] = Рк.
IV!. й. ЛОГИКА
51
Понятие замкнутого класса может быть приложено к решению вопроса об обосновании неполноты некоторых систем.
Пример 3. Рассмотрим систему ф={~х,тах(х,,хг)). Пусть & = {0, к—1}. Так как обе функции сохраняют &, то
№1 е Т8.
Поскольку при А1 > 3, <§ =? Ек) то Т % не содержит, например, константу 1. Значит при к > 3 $ не будет полной системой. На этом примере видно, что, хотя система ^—х, тах(х,, х?)} и является обобщением системы {х, XI V хг} булевых функций, она не является полной.
§ 3. Распознавание полноты. Теорема о полноте
Теперь мы перейдем к обсуждению вопросов полноты для произвольных систем ф. Следовательно, здесь нас будет интересовать, каким образом по множеству $ можно узнать, будет оно полным или нет. Мы рассмотрим два подхода к решению этой задачи.
Первый' подход алгоритмический. Он требует уточнения слов «задана произвольная система ф». Ввиду этого мы несколько сузим задачу и будем предполагать, что система ф конечна:
и, стало быть, она может быть явно задана либо перечнем таблиц, либо списком формул. Так же как и в случае к — 2, можно считать, что каждая из функций системы ф зависит от переменных
Наша задача может быть сформулирована следующим образом: существует ли алгоритм, позволяющий для каждой конечной системы ф выяснять, будет она полнохг или нет (задача распознавания полноты).
Для произвольного р > 1 обозначим
(^1! * * '1 ®р)=
и через Шх1.,.хр —множество всех функций из 5Й, зависящих ОТ переменных Хи . . ., Хр.
Теорема 4. Существует алгоритм для распознавания полноты.
4*
52 Ч. I. ФУШ\Ц1ШНА. 1ЬНЫЙ ^иииигы ^ ШШ-АНЦПЛИ
Доказательство. Построим по индукции последовательность множеств
Эф, Эф, ? * -» Эф, • * ?
функций ОТ двух переменных Х1 И Х2.
Базис индукции. Положим Эф ~ А, где А — пустое множество.
Индуктивный переход. Пусть уже построены множества Эф, Эф, .. Эф; покажем, как определяется множество Эф-ц- Для этого выпишем функции, входящие в Эф (г> 0):
Я = 1^1 (-Гг, Х2), . . . , к,г {хх, ж2)} (5, = 0 при г = 0),
и для каждого ? (? = !,...,«) рассмотрим всевозможные формулы вида
1г(Н1(хи Х2), . Нп{Х\, хг)),
где Хг) есть Либо фуНКЦИЯ Ь,,(х!, Х2) {/ = 1, . . 5г),
либо X.,).
Таким образо.м, просматривая ?($,? +2)" формул, мы, быть может, получим функции, не вошедшие в Эф. Обозначим их через
^вг+1 (^1» ?З-зФ • ? • I {?^1) ^г)*
Положим Э^г+1 = Эфу (^и х2), . .к*г+1 {%1, з^а)) *
Очевидно, что
Е 8ф = . . . Е Эф Е . . .
Из построения ЯСНО, ЧТО если Э1г+1 = Я, то Эф = Эф+1 = .. т. е. цепочка множеств стабилизируется. Обозначим через г* минимальный номер множества, начиная с которого наступает стабилизация. Тогда цепочка множеств
Эф с= Эф с: . .. с= Эф*
строго возрастает. Так как мощность Эф не больше, чем
А^2, то Значит, момент стабилизации может
быть обнаружен через ограниченное число шагов. Рассмотрим множество Эф*. Возможны два случая.
1) ЭФ* содержит все функции от двух переменных хи х2 и, значит, содержит \\(хи х2). Тогда исходная система полна.
2) Эф* не содержит всех функций от двух переменных. Поскольку в этом случае = ЭФ* (см. заме-
ГЛ. 2. А-ЗНАЧНАЯ ЛОГИКА
53
чание 1 из § 2 гл. 1), то [ф] не содержит всех функций от переменных ж, и х2. Следовательно, ф не полна.
