В.П. Воронин - Дополнительные главы дискретной математики (1127085), страница 19
Текст из файла (страница 19)
Рассмотрим теперь некоторые нетривиальные замкнутые классы.Определение 2.1.3. Пусть ∅ E Ek . f (exn ) ∈ Pk сохраняет множество E , если выполнена следующая импликация: α1 , . . . , αn ∈ E ⇒ f (α1 , . . . , αn ) ∈ E . Классом функций, сохраняющих множество E называется T (E ).Лемма 2.1.1. Для любого множества E ⊆ Ek класс T (E ) замкнут. Док-во. Поскольку тождественная функция сохраняет любое множество, для доказательства замкнутости достаточно доказать, что суперпозиция функций, сохраняющих E , также сохраняет E . Пусть функцииf1 (x1 , .
. . , xn ) , . . . , fm (x1 , . . . , xn ) ∈ T (E ) (без ограничения общности будем считать, что они зависят от одних и техe = (α1 , . . . , αn ) ∈ E значения функцийже переменных). Пусть также f (x1 , . . . , xm ) ∈ T (E ). Для любого набора αf1 (α1 , . . . , αn ) = β1 ∈ E , . . . , fm (α1 , . . . , αn ) = βm ∈ E . Но тогда и f (β1 , . . . , βm ) ∈ E .Описанное семейство замкнутых классов обладает следующими свойствами.Утверждение 2.1.1. T (E ) = Pk , T (E ) = Pk , а также ∅с Pk .EEk ⇒ T (E ) — непустое множество, не совпадающее Док-во.
Первое свойство очевидно, второе принимается по договоренности, а третье следует из того, что, например,отрицание Поста не сохраняет никакое непустое собственное подмножество Ek .Функции максимума и минимума, очевидно, сохраняют любое E ⊆ Ek .Утверждение 2.1.2. Всего в Pk существует 2k − 2 классов, сохраняющих непустые собственные множества,причем все они попарно различны и ни один из них не содержится в другом. Док-во.
Действительно, пусть E1 6= E2 . Возможны 2 варианта:1. Существуют такие a и b, что a ∈ E1 \E2 и b ∈ E2 \E1 , то есть E1 * E2 и E2 * E1 . В этом случае, очевидно, для функцийконстант выполняется a ∈/ T (E2 ) , b ∈/ T (E ), то есть эти классы не совпадают, и ни один из них не содержится вовтором.2. E2 E1 , то есть существует такое a, что a ∈ E1 \ E2 . В этом случае классы T (E1 ) и T (E2 ) различны, потому чтоконстанта a содержится в первом из них и не содержится во втором. Покажем, что во втором классе существуетфункция, не содержащаяся в первом. Поскольку E2 не пусто, существует c ∈ E2 . Также,(поскольку E1 6= Ek , сущеc если x ∈ E2 ,ствует точка d ∈ Ek \ E1 .
Класс T (E2 ), очевидно, содержит функцию такого вида: f (x) =d в противном случае.Функция f (x) по построению содержится в классе T (E2 ), но, очевидно, не содержится в классе T (E1 ), так какf (a) = d ∈/ E2 .66ГЛАВА 2. КОНЕЧНОЗНАЧНЫЕ ЛОГИКИОсталось только подсчитать число этих классов. Так как все они различны, то их число равно числу непустых собственных подмножеств Ek , то есть 2k − 2.Определение 2.1.4. Множество функций A называется предполным классом в Pk , если оно само является замкнутым и неполным в Pk классом, но для любой функции f , не содержащейся в A выполняется [A ∪ { f }] = Pk .Утверждение 2.1.3. Для любого непустого подмножества E ( Ek класс T (E ) является предполным в Pk .
Док-во. Пусть E — любое собственное непустое подмножество Ek . Для произвольной функции f ∈/ T (E ) рассмотe ∈ E n : f (αe ) = f (α1 , α2 , . . . , αn ) = b ∈рим замыкание [T (E ) ∪ { f }]. Для f справедливо f ∈/ T (E ) ⇒ ∃α/ E . С другойстороны, очевидно, классу T (E ) принадлежит такая функция (для a ∈ E ):(az∈E,g (x, y, z) =Vk (x, y) z ∈/ E.e )), реализует функцию Вебба.Таким образом, суперпозиция функций из объединения g (x, y, f (αУтверждение 2.1.3 показывает, что все замкнутые классы, сохраняющие непустые собственные подмножества Ek ,являются предполными. Если вспомнить P2 , то там существовало ровно пять предполных классов: два класса сохраняющих константы, классы линейных, самодвойственных и монотонных функций и их структура условно выгляделатак:`P```2`b"" %% ee bb"`" %`` e ` b`T0 T1 LSMАналогичная ситуация наблюдается и в Pk :P` ` ` ` k` ` `QQ AA@@ Q` ```A` @` Q`k2 −2,(2.5)где выделены как раз те 2k − 2 предполных классов.nnnЧисло функций, зависящих от n переменных в классе T (E ) при |E | = m для 1 6 m < n, очевидно, равно mm kk −m .nДействительно, всего наборов длины n, составленных из символов E , — m .
Им могут соответствовать лишь значения из m-элементного множества. Остальным же kn − mn наборам могут соответствовать любое из k значений. Такимобразом получено, чтоnnn|T (E )|hni = mm kk −m .Рассмотрим теперь другое семейство замкнутых классов:Определение 2.1.5. Пусть D1 , D2 , . . . , Ds — попарно непересекающиеся непустые множества (блоки), в объединениидающие все Ek . В этом случае представление Ek = D1 ∪ D2 ∪ . . . ∪ Ds называется разбиением Ek .Случаи s = 1 и s = k порождают тривиальные разбиения Ek и {0} ∪ {1} ∪ . .
. ∪ {k − 1} соответственно. Все остальные разбиения называются нетривиальными. По заданному разбиению D можно на множествах Ek и Ekn ввести отношение эквивалентности следующим образом: ∀a, b ∈ Ek : a ∼ b (mod D) (a и b эквивалентны по разбиению D) тогда иe ∼ βe (mod D) ⇔ ∀i = 1, n ⇒ αi ∼ βi (mod D), еслитолько тогда,когда они в этом разбиении попадают в один блок; αe | = βe = n.|αОпределение 2.1.6. Функция f (exn ) от n переменных сохраняет разбиение D, если e ∼ βe (mod D) ⇒ f (αe ) ∼ f βeα(mod D).Классом функций, сохраняющих разбиение D называется множество всех функций, сохраняющих заданное разбиение D.Также, как и в случае сохранения множества, выделяются вырожденные случаи. Тривиальными называются разбиение в виде одного блока U (Pk ) и разбиение в виде k блоковU ({0} ∪ {1} ∪ .
. . ∪ {k − 1}) .672.1. ФУНКЦИИ КОНЕЧНОЗНАЧНОЙ ЛОГИКИВсе функции сохраняют тривиальные разбиения, иными словами, классы всех функций, сохраняющих тривиальныеразбиения, являются полными в Pk , поэтому имеет смысл рассматривать эти классы только при k > 3. Любая тождественная функция сохраняет любое разбиение. Отрицание Поста не сохраняет никакое нетривиальное разбиение. Изэтого следует, что для любого разбиения класс сохраняющих его функций не пуст. Справедливо более сильное утверждение, а именно, что ∅ U (D) Pk для любого нетривиального разбиения D.
Действительно, если есть хотя бы дваблока, один из которых содержит хотя бы два элемента a и b, а второй содержит хотя бы один элемент c, то достаточнов качестве примера функции, не сохраняющей данное разбиение, рассмотреть отображение a в a, b в c, а на остальныхэлементах — произвольно.Лемма 2.1.2. Для любого разбиения класс функций, его сохраняющих, замкнут. Док-во. Поскольку тождественная функция сохраняет любое разбиение, для доказательства замкнутости достаточно доказать, что суперпозиция сохраняющих разбиение функций также сохраняет разбиение. Рассмотрим произxn ) , f (exm ) ∈ U (D). Докажем, что F (exn ) = f ( f1 (exn ) , .
. . , fm (exn )) ∈ U (D). Расвольное разбиение D и пусть f1 (exn ) , . . . , fm (eee = (α1 , . . . , αi , . . . , αn ) и β = (β1 , . . . , βi , . . . , βn ).смотрим для этого любые два эквивалентные по разбиениюD набора α nee ) ∼ f j β (mod D) ∀ j = 1, m, или, что то же самое,Из f j (ex ) ∈ U (D) ∀ j = 1, m следует, что f j (α e ) , f2 (αe ) , . .
. , fi (αe ) , . . . , fm (αe )) ∼ f1 βe , f2 βe , . . . , fi βe , . . . , fm βe( f1 (αe ) , . . . , fm (αe )) ∼ fИз того, что f (exm ) ∈ U (D), следует, что f ( f1 (α e ) ∼ F βe (mod D).F (α(mod D). f1 βe , . . . , fm βe(mod D), или, по-другому,Два введенных выше замкнутых класса можно рассматривать как частные случаи класса функций, сохраняющихпредикат.Определение 2.1.7.
s-местным предикатом называется функция k-значной логики P (y1 , . . . , ys ), принимающаяe предикат принимает значение, равное единице, то этот набортолько значения 0 или 1. Если на некотором наборе αe ∈ P. Упорядоченная s-ка наборов удовлетворяет предикату P, если она удовлетворяетудовлетворяет предикату: αему покомпонентно:e1 = α11 , . .
. , αn1 αe2 = α12 , . . . , αn2α∈ P ⇔ ∀ j = 1, n ⇒ α 1j , α 2j , . . . , α sj ∈ P···es = (α1s , . . . , αns )αРассматриваются только случаи s > 1. Предикаты, являющиеся тождественным нулем или тождественной единицей,называются тривиальными. В этом случае предикат существенно зависит от нуля переменных.
В случае s = 1 предикат называется характеристической функцией. В случае s = 2 — разбиением.Определение 2.1.8. Функция f (exn ) сохраняет предикат P, если для любой упорядоченной s-ки наборов длины neee1 ) , . . . , f (αes )) также удовлетворяет предикату P. Классом функций, сохраняю(α1 , . .
. , αs ) упорядоченная s-ка ( f (αщих предикат P, называется множество W (P) всех функций, сохраняющих предикат P.Так как любой набор удовлетворяет предикату P ≡ 1, W (P) = Pk . Также, предикат, тождественно равный нулю, сохраняет любая функция. Очевидно, что класс, сохраняющий нетривиальный предикат не пуст и не совпадает со всемPk , за некоторыми исключениями. Действительно, для любого нетривиального s-местного предиката существует упорядоченная s-ка, ему не удовлетворяющая. Тогда функцию, не сохраняющую предикат, определяем по следующемуправилу: для некоторой упорядоченной s-ки различных наборов, удовлетворяющей предикату, ставим в соответствиеупорядоченную s-ку, не удовлетворяющую предикату.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
