В.П. Воронин - Дополнительные главы дискретной математики (1127085), страница 22
Текст из файла (страница 22)
Итак, число функций, сохраняющих разбиение внутри класса эквивалентности веса ln−lln−llравно mm (k−m) +(k − m)m (k−m) . Поскольку классы эквивалентности не пересекаются, всего разных функций,зависящих от одних и тех же n переменных, сохраняющих данное разбиение —∏et ∈Bnnn eet (t )tn−tn−tmn−ket k (k−m)kt kmn−ket k (k−m)kt km+ (k − m)= ∏ mm (k−m) + (k − m)m (k−m).t=0Теперь легко сказать, сколько функций содержится в пересечении: если в наборе все переменные из E , то имставятся в соответствие значения только из E , то есть при t = 0 второе слагаемое пропадает:nn t (t )tn−tnn−t|T (E ) ∩U (D)|hni = mm · ∏ mm (k−m) + (k − m)m (k−m).t=1nДля того, чтобы ответить на поставленные вопросы осталось вспомнить, что |T (E )|hni = mm kkзом,n −mn.
Таким обра-74ГЛАВА 2. КОНЕЧНОЗНАЧНЫЕ ЛОГИКИ(a)|T (E ) \U (D)|hni = |T (E )|hni − |T (E ) ∩U (D)|hninn t (t )tn−tn−tnnnn= mm · kk −m − mm · ∏ mm (k−m) + (k − m)m (k−m)t=1mn=m· kkn −mnn−∏ mmn−t (k−m)tmn−t (k−m)t+ (k − m)(n)t!,t=1(b)|U (D) \ T (E )|hni = |U (D)|hni − |T (E ) ∩U (D)|hninn t (t )tn−tn−t= ∏ mm (k−m) + (k − m)m (k−m)t=0nn t (t )tn−tn−tn− mm · ∏ mm (k−m) + (k − m)m (k−m)t=1nn t (t )tn−tnn−t,= (k − m)m · ∏ mm (k−m) + (k − m)m (k−m)t=1(c)|T (E ) ∪U (D)|hni = |T (E )|hni + |U (D)|hni − |T (E ) ∩U (D)|hninn t (t )tn−tnnnn−t= mm kk −m + ∏ mm (k−m) + (k − m)m (k−m)t=0mn−m n−tnt (t )tn−t· ∏ mm (k−m) + (k − m)m (k−m)nt=1n= mm kkn −mnnn t (t )tnn−tn−t.+ (k − m)m · ∏ mm (k−m) + (k − m)m (k−m)t=14.
Исследовать на полноту в Pk следующие системы:(a) {k − 1, x + 2, max (x, y)}. Решение. Возможны два случая:i. k > 3 — нечетное. Тогда x + 2 + · · · + 2 = x + 1 = x, и исходная система содержит систему Поста, которая| {z }k+12разявляется полной в Pk .ii. k > 4 — четное.
В этом случае утверждается, что для E = {1, 3, . . . , k − 1} исходная система содержитсяв T (E ), то есть сохраняет нечетное множество и является неполной.Рассматривать систему при k = 2 не имеет смысла, так как она содержит функцию x + 2.no(b) 1, x, x−̇y . Решение. Утверждается, что для E = {1, 2} исходная система содержится в T (E ). Действительно, константы сохраняют это множество, и 1−̇1 = 1−̇2 = 2−̇2 = 1, 2−̇1 = 2.
Следовательно, для k > 3 система неполна. Рассматривать систему при k = 2 не имеет смысла, так как она содержит константу 2.(c) {k − 2, x + y, min (x, y)}. Решение. Возможны два случая:i. k > 2 — четное. В этом случае, подобно 4(a)ii, система сохраняет четное множество.ii. k > 3 — нечетное.
Тогда x + (k − 2) + · · · + (k − 2) = x, и исходная система содержит систему Поста, ко|{z}k−12торая является полной в Pk .раз752.1. ФУНКЦИИ КОНЕЧНОЗНАЧНОЙ ЛОГИКИ(d) 1, k − 1, x−̇ 2k , min (x, y) . k Решение. Утверждается, что для D = 0, . . . , 2k2 + 1, . . . , k − 1 исходная система содержится вU (D). Действительно, константы сохраняют любое разбиение, минимум сохраняет любое монотонное разбиение, а D — монотонное. Далее, третья функция отображает первый блок в 0, а второй блок в первый.Следовательно, при k > 3 система не полна. При k = 2 система также не полна, так как целиком содержитсяв классе монотонных функций (в случае k = 2 она превратится в {0, 1, x · y}).5.
Выделить базис из полной в Pk системы A :(a) A = {k − 1, j0 (x) , j1 (x) , . . . , jk−1 (x) , x · y, x−̇y}. Решение. Рассмотрим подсистему B = {k − 1, x−̇y, jk−1 (x)} ⊂ A . Она является полной, так какjk−1 (k − 1) ≡ 1 и система сводится к полной системе 6. Докажем, что если убрать из нее любую функцию,(1)она перестанет быть полной.
Действительно, A \ {k − 1} ⊆ T ({0}) , A \ {x−̇y} ⊆ Pk , C = A \ { jk−1 (x)} ⊆T ({0, k − 1}). Последнее равенство, однако, не доказывает неполноту в случае k = 2. При k = 2 A \ { jk−1 (x)}является и полной системой, и базисом, так как k − 1 = 1 — не сохраняет 0 и не самодвойственная, а вторая— x−̇y = xy ⊕ x — нелинейная, не сохраняет единицу и не монотонная. Следовательно, при k > 3 базисомявляется система B, а при k = 2 — система C .(b) A = x − 2, J0 (x) , max (x, y) , x−̇y2 , x2 · y . Решение. Рассмотрим подсистему B = J0 (x) , x−̇y2 . Покажем, что она полная.
Действительно,(. . . (J0 (x) −̇J02 (x))−̇ · · · −̇J02 (x))−̇ J02 (x) ≡ 0, J0 (0) = k − 1, x−̇ (k − 1)2 ≡ x−̇1, (k − 1) −̇1 = k − 2, (k − 2) −̇1 =|{z}k−1 разk − 3, . . . , 2−̇1 = 1. Таким образом полученывсе константы и функции вида x−̇m для любого m = 1, k − 1.(k − 1 x 6 m,Используя тот факт, что J0 (x−̇m) =получим теперь все Jm для 0 6 m 6 k − 1:0x > m,Jm (x) = (.
. . (J0 (x−̇m) −̇J02 (x−̇ (m − 1)))−̇ · · · −̇J02 (x−̇ (m − 1)) −̇ J02 (x−̇ (m − 1)) .|{z}k−1 разДалее заметим, чтоx−̇y ≡ (. . . (x−̇J12 (y))−̇J22 (y))−̇J22 (y))−̇ · · · ) −̇Ji2 (y))−̇Ji2 (y))−̇ · · · )−̇ Ji2 (y))|{z}i раз22−̇ · · · ) −̇Jk−1(y))−̇ · · · )−̇ Jk−1(y)|{z}k−1 разДействительно, при y = i только квадраты соответствующих Ji будут равны единицам, остальные же будутнулями. Следовательно, из x при y = i будет усеченно вычитаться как раз i.
Таким образом, система A сведена к системе 6: получены усеченная разность и константы 0 и k − 1. Базисность этой системы при условииполноты очевидна: первая функция существенно зависит только от одной переменной, а вторая сохраняет,например, ноль.(c) A = 2, j0 (x, ) , x + y2 , x2 −̇y, x · y · z Решение. Рассмотрим подсистему B = j0 (x) , x + y2 .
Докажем ее полноту. Заметим, что j0 ( j0 (x)) +j02 (x) ≡ 1, x + 12 = x. Имея отрицание Поста и j0 можно получить все ji для 0 6 i 6 k − 1. Далее, используятот же прием, что и в примере 5b, получим x + y = x + j12 (y) + j22 (y) + j22 (y) + · · · + ji2 (y) + · · · + ji2 (y) + · · · +|{z}i раз2j2 (y) + · · · + jk−1(y). Таким образом, система B сводится к системе 7, которая полна при k > 3. При k = 2|k−1{z}k−1 разсистема B теряет смысл, так как содержит константу 2.
Базисность B очевидна: как и в 5b одна из функцийсущественно зависит только от одной переменной, а вторая — сохраняет ноль.76ГЛАВА 2. КОНЕЧНОЗНАЧНЫЕ ЛОГИКИУпражнения.1. Используя метод сведения к заведомо полным системам, доказать полноту в Pk следующих систем:(a) {x, min (x, y)};(b) {min (x, y) − 1};(c) J0 (x) , x + y, x · y2 ;(d) 1, x2 + y, x2 −̇y ;(e) J0 (x) , x + y, x · y2 ;(f) {k − 2, xẏ + 1, (∼ x) −̇y};(g) k − 1, x2 − y, x2 −̇y ;(h) {1, 2 · x + y, x−̇y};(i) 1, x2 − y, min (x, y) ;(j) 1, x + y + 2, x2 −̇y ;(k) {x · j0 (y) , min (x, y)}.2. Подобрав подходящий класс типа T (E ) или U (D), доказать, что системаA = {1 − x, j0 (x) , j1 (x) , .
. . , jk−1 (x) , x · y, x−̇y, min (x, y)}не полна в Pk .3. Как известно (см. теорему 2.2), системаA = {0, 1, . . . , k − 1, j0 (x) , j1 (x) , . . . , jk−1 (x) , x + y, x · y}полна в Pk .(a) Доказать, что из системы A можно выделить полную в Pk подсистему, состоящую из двух функций.(b) Показать, что любая подсистема системы A , состоящая из одной функции, не полна в Pk .4.
Система Россера-ТуркеттаA1 = {0, 1, . . . , k − 1, J0 (x) , J1 (x) , . . . , Jk−1 (x) , min (x, y) , max (x, y)} ,как известно, полна в Pk (см. теорему 2.1).(a) Проверить, что, удаляя из A1 любую константу, отличную от 0 и k − 1, получаем подсистему, содержащуюсяв некотором классе типа T (E ), где ∅ 6= E 6= Ek (и, значит, неполную в Pk ).(b) Выделить из системы A1 полную в Pk подсистему, состоящую из 2k − 2 функций.5.
Для заданных k исследовать на полноту следующие подсистемы системы Россера-Туркетта:(a) k = 3, {1, J0 (x) , J2 (x) , min (x, y) , max (x, y)};(b) k = 3, {1, 2, J2 (x) , min (x, y) , max (x, y)};(c) k = 4, {1, 2, J0 (x) , J1 (x) , min (x, y) , max (x, y)};(d) k = 4, {1, 2, J0 (x) , J3 (x) , min (x, y) , max (x, y)}.6.(a) Для k = 3, 4 и 5 подсчитать число различных замкнутых классов в Pk , являющихся классами сохраненияразбиений.(b) Пусть D = {E1 , . . . , Es } — разбиение множества Ek . Подсчитать число функций в Pk , содержащихся в классеU (D) и зависящих от переменных x1 , x2 , .
. . , xn (n > 0).7. Исследовать на полноту в Pk следующие системы:(a) {0, 1, x−̇ (∼ y)};(b) 2, 2x + y, x2 −̇y ;(c) {1, 2, max (x, y)};(d) {2−̇x, x · y, max (x, y)};(e) {k − 2, 2x + y, x−̇y};772.2. ТЕОРЕМЫ О ФУНКЦИОНАЛЬНОЙ ПОЛНОТЕ(f) {∼ x, −x · y, min (x, y)};(g) {2, x + y, x−̇y};(h) {∼ x, 2 j0 (x) , J1 (x) , x−̇y};(i) {1, ∼ x, J0 (x) + J1 (x) , max (x.y)};(j) {0, 1, ∼ x, 2 − j0 (x) − 2 j1 (x) , min (x, y)};(k) {k − 2, ∼ x, x−̇y};2.2 Теоремы о функциональной полнотеТеорема об алгоритмической разрешимости проблемы распознавания полноты в k-значной логике. Рассмотрим конечную систему функций A = { f1 , .
. . , fm }, зависящих от одних и тех же n переменных x1 , . . . , xn . Обозначимgnm (x1 , . . . , xn ) = xm — селекторную функцию для 1 6 m 6 n. Используем две из них: g21 (x1 , x2 ) = x1 , g22 (x1 , x2 ) = x2 .Теорема 2.4. Существует алгоритм, распознающий в Pk при k > 2 полноту любой конечной системы. Док-во.
Построим последовательность вложенных друг в друга множествN 0 = ∅ : N0N1N2···NrNr+1···Nr∗ = Nr∗ +1 = · · ·по следующим индуктивным правилам: N1 — множество всех 2 функций двух переменных, реализуемых формулами виgда f (H1 (x1 , x2 ) , H2 (x1 , x2 ) , . . . , Hn (x1 , x2 )), где Hi (x1 , x2 ) = 12 . Заметим, что |N1 | 6 m · 2n (поскольку всего функцийg2в A — m, все зависят от n переменных, на месте каждой из которых стоит одна из двух функций). Пусть уже построены все классы, до r-го включительно, и |Nr | = sr .
Тогда класс Nr+1 — это множество всехдвух пере функцийg21менных, реализуемых формулами вида f (H1 (x1 , x2 ) , H2 (x1 , x2 ) , . . . , Hn (x1 , x2 )), где Hi (x1 , x2 ) = g22 . Очевидно, чтоhi ∈ Nr|Nr+1 | 6 m · (sr + 2)n . Это следует из того, что любая функция из Nr+1 реализуется формулой над Nr+1 . Все функции22из Nr зависят от двух переменных. Поскольку всего функций от двух переменных kk , не более, чем за kk + 2 шаговвозникнет ситуация, Nr∗ = Nr∗ +1 = · · ·. Как только построен последний уникальный класс, мы проверяем наличие внем функции Вебба.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
