Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Из данных рассуждений легко извлекается алгоритм: строим классы 910, 91х, ..., 91г* до момента стабилизации и рассматриваем класс 91,*, но которому и определяем, имеет место полнота для $ или нет. Теорема доказана.
Теорема 5. Из всякой полной в Р„ системы ф можно выделить конечную подсистему, являющуюся также полной.
Доказательство. Пусть ф = {Д, Д, ..Д, ...}. В силу полноты функция \\{хи хг) может быть выражена через функции системы ф б виде формулы
х2) = Я[ЛА, ..Дг].
Очевидно, что подсистема}/^, .... Дг] является искомой. Теорема доказана.
Таким образом, существенно бесконечных полных систем не бывает, и тем самым введенное выше ограничение в задаче распознавания полноты является не столь сильным, как это могло казаться первоначально.
Второй подход в решении вопроса о полноте связан с проверкой некоторых свойств класса ф.
Введем одно понятие и докажем относительно него две леммы.
Пусть 91 — класс функций /гДгд, ..ур) из Рк, зависящих от р переменных г/1, ..уР. Предположим, что он содержит функции &{уи ..., уР)^у^ (1=1, р).
Определение. Функция /(ад, ..., ж„) сохраняет множество 91, если для любых функцийЬ, 1 (г/А, .. .,ур), ...,
«• • I Ур) из 91
/ (Ч (У1 Ур)* * • ?, Л,п {ух г/р)) ЕЕ 91.
Обозначим через 511 класс всех функций из Рк, сохраняющих множество 91.
Пример 4. Пусть к = 2, р = 1 и 91 = {у, уХ. Тогда функция /(ж,, ..., хп), сохраняющая множество 91, удовлетворяет соотношению
/Ол..../")-л
откуда _ __ _
/(щ, .. о„) — /(щ оп)\
Значит, функция хп) — самодвойственная, и класс
54 Ч. I. ФУНКЦИО ЦАЛЪ11 ыл; LiliLi i JMvmi и иш^лцишнл
сохранения множества 31 есть класс S самодвойственных функций.
Лемма 1. Класс ЭЛ всех функций, сохраняющих !Л, является замкнутым.
Доказательство. Очевидно, что класс ЯЛ содержит тождественную функцию. Поэтому для обоснования замкнутости класса ЯЛ достаточно показать, что функция
ф=/(/. / т) принадлежит классу ЯЛ, если функции
f* fit • ? ч fm принадлежат классу ЯЛ. Пусть Ф зависит от п переменных. Возьмем произвольные функции hilf .,.i hin из класса 91. Тогда
Ф(Ч> ‘ * ? *4l)==/(/l (^*1Т ' ' *>^0 ’ 1 * * ? !
в / {Нц * • • I ^т)>
где функции fflf ..Hm принадлежат классу 91, поэтому И f(HU ..., Hm) принадлежит 91. Лемма доказана.
Лемма 2. Если класс 91 таков, что [^1уг. ?Vp — то для класса ЯЛ, сохраняющего 91, имеет место равенство
^2/1*--I/p =
Доказательство. Пусть h(yu .. ., ур)е 51. Тогда если hiit ...t hip^ то
h(hh, ...thip)ez[myv..yp = %
Т. е. k е С другой стороны, если
/{уи
ю, подставляя вместо уи . .у$ функции glt ..., gP, получим
}(gi, ..Ы G -л или f(yu ..., ур) е 91.
Лемма доказана._______________________„_______________________
Тебрема 6 (о функциональной полноте, А. В. Кузнецов [15]). Можно построить систему замкнутых классов в Рк
ЯЛ„ ЯЛ2, ..., ЯЛ»,
каждый из которых целиком не содержит ни одного из остальных классов, и такую, что подсистема функций из Рк полна тогда и только тогда, когда она целиком не содержится ни в одном из классов SKlt ..ЯЛ*.
ГЛ. 2. fc-ЗНАЧИЛ Я ЛОГИКА
55
Доказательство. Построение системы классов ..., 2Я*. Пусть 9?t, 9i2, ..., % — система всех таких собственных подмножеств функций из Ph, зависящих от двух переменных х± и х2, которые удовлетворяют следующим условиям (i =* 1, .. I):
1) 3?? содержит обе функции gt(x 1лХ2)~Хи gn{Xi., х2) =
9
2) [2i?JXlpf2 — 5?{.
Указанные подмножества строятся путем просмотра всех собственных подмножеств множества функций из
Рк, зависящих от переменных дц и х3 (их < 2feh ). При этом оставляются те подмножества, которые содержат обе функции gi и g2, и далее для каждого оставшегося подмножества проверяют условие [Sftbcpcg =* 5^1 что может быть осуществлено так же, как в теореме о распознавании полноты.
Обозначим далее через STli класс сохранения подмножества S?j. В силу лемм 1 и 2 SMj — замкнутый класс такой, что
su.
Отсюда следует, что все классы (? == 1л ., I) различны и не являются полными.
Далее остается только удалить те классы, которые содержатся в каком-либо из остальных классов.’ Мы получим систему
ав„ эх,.
Необходимость вытекает из свойств замкнутости и неполноты классов Sfy ., s).
Достаточность. Пусть 2Я ^ Ph — система функций, целиком не содержащаяся ни в одном из классов 37?j {/ = 1, ..., s). Можно считать, что 2Я — замкнутый класс. Обозначим через 2J?' класс [2Я ? {gt, g2}]. Очевидно, что классы 2J? и Ш' либо одновременно полны, либо неполны, так как
U [{gu g,}],
и функция Уh (ац, х?) либо входит в 5Я и Ж, либо не содержится ни в одном из этих Классов. Возьмем 9?' = Покажем, что Si" содержит все функции, зависящие от
4 1. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
переменных ад и х2. В самом деле, если это не так, то очевидно, что
r = и 5K'sSDi; = afy.
Так как Ш1 s ЭЛ', то получаем, что SD?sSP^, что противоречиво. Таким образом, 9?', а значит и 2Л', содержит функцию Vk{xu ад). Отсюда вытекает полнота класса ШГ, а следовательно и класса 23?. Теорема доказана.
Следует обратить внимание на то обстоятельство, что теорема Кузнецова доказывает, что возможно выразить условия полноты системы ф в терминах принадлежности ее к специальным классам 2Л|, ..9Л*. Однако фактическое построение классов даже при небольших к связано с трудоемкими вычислениями, которые невозможно осуществить. В силу этого возникает вопрос о поиске других, более эффективных критериев. Мы увидим, что эта цель достижима, но за счет введения ограничений, т. е. за счет знания дополнительной информации об исходной системе
