В.П. Воронин - Дополнительные главы дискретной математики (1127085), страница 21
Текст из файла (страница 21)
Затем, (k − 1) + 2 = 1. Таким образом, в исходной системе содержитсязаведомо полная система 6.(d) −x, 1 − x2 , x−̇y . Решение. x−̇x = 0, 1 − 02 = 1, −1 = k − 1. Таким образом, в исходной системе содержится заведомо полная система 6.(e) {x + y, (∼ x) −̇2y}. Решение. Заметим, что при k = 2 система не полна: x + y = x ⊕ y, (∼ x) −̇2y = x = x ⊕ 1 — содержатся вклассе линейных функций. При k > 3 верно следующее: x + x + · · · + x = 0, (∼ 0) −̇2 · 0 = k − 1, x−̇2 (k − 1) ={z}|kx−̇ (k − 2) = jk−1 (x) , jk−1 (x + (k − 1)) = j0 (x).
Таким образом, исходная система сведена к системе 7, котораяполна при k > 3.2. Подобрав подходящий класс типа T (E ) или U (D), доказать, что система A не полна в Pk .(a) A = ∼ s, min (x, y) , x · y2 . Решение. Утверждается, что для E = {0, k − 1} система A ⊆ T (E ). Действительно, ∼ 0 = k − 1, ∼(k − 1) = 0, функция минимум сохраняет любое множество, 0 · 02 = 0 · (k − 1)2 = (k − 1) · 02 = 0, (k − 1) ·(k − 1)2 = k − 1. Следовательно, при k > 3 система не полна.
При k = 2, очевидно, система полна, так какпервые две функции превращаются в отрицание и конъюнкцию и образуют базис в P2 .no(b) A = 1, 2, x−̇ j2 (x), max (x, y) . Решение. Утверждается, что для E = {1, 2} система A ⊆ T (E ). Действительно, константы сохраняютэто множество, максимум сохраняет любое множество, а 1−̇ j2 (1) = 2−̇ j2 (2) = 2. Следовательно, при k > 3система полна. При k = 2 рассматривать систему не имеет смысла, так как она содержит константу 2.(c) A = {2, j0 (x) , x + j0 (x) + J1 (x) + Jk−1 (x) , min (x, y)}. Решение.
Утверждается, что для D = {0, 1} {2, . . . , k − 1} система A ⊆ U (D). Действительно, константа2 сохраняет любое разбиение, функция минимума сохраняет любое монотонное разбиение, а D монотонно,то есть все элементы одного блока находятся в одном и том же отношении порядка со всеми элементамидругого. И, наконец, обозначив f (x) = x + j0 (x) + J1 (x) + Jk−1 (x), имеем 1 = f (0) ∼ f (1) = 0 (mod D) f (a) ∼f (b) (mod D) ∀a, b ∈ {2, .
. . , k − 1} : f (a) , f (b) ∈ {2, . . . , k − 2}. Следовательно, при k > 3 система не полна.При k = 2 рассматривать систему не имеет смысла, так как она содержит константу 2.(d) A = {J2 (x) , x + j0 (x) , x + j0 (x) + J1 (x) , max (x, y)}. Решение. Утверждается, что для E = {0, 1} система A ⊆ T (E ). Действительно, J2 (0) = J2 (1) = 0, 0 +j0 (0) = 1, 1 + j0 (1) = 1, 0 + j0 (0) + J1 (0) = 1 + j0 (1) + J1 (1) = 1, а функция максимума сохраняет любоемножество. Следовательно, при k > 3 система не полна. При k = 2 рассматривать систему не имеет смысла,так как она содержит функцию J2 (x).72ГЛАВА 2.
КОНЕЧНОЗНАЧНЫЕ ЛОГИКИ(e) A = {k − 1, J0 (x) , x−̇y, x · y · z}. Решение. Утверждается, что для E = {0, k − 1} система A ⊆ T (E ). Действительно, константа сохраняет любое множество, содержащее ее как элемент, J0 (0) = k − 1, J0 (k − 1) = 0, 0−̇0 = 0−̇ (k − 1) =(k − 1) −̇ (k − 1) = 0, (k − 1) −̇0 = k − 1, 0 · 0 · 0 = 0 · 0 · (k − 1) = 0 · (k − 1) · 0 = 0 · (k − 1) · (k − 1) = (k − 1) · 0 · 0 =(k − 1) · 0 · (k − 1) = (k − 1) · (k − 1) · 0 = 0, (k − 1) · (k − 1) · (k − 1) = k − 1. Следовательно, при k > 3 система неполна. При k = 2 легко видеть, что система полна, так как первая функция — константа 1 — не сохраняетноль и не является самодвойственной, вторая функция превращается в отрицание, которое не монотонно ине сохраняет единицу, а четвертая функция не линейная.(f) A = 2x3 , 2x + y, x2 y, xJ0 (y) , x2 + (∼ y) . Решение.
Утверждается, что для E = {0} система A ⊆ T (E ). Действительно, 2·03 = 0, 2·0+0 = 0, 02 ·0 =20, 0 · J0 (0) = 0, 0 + (∼ 0) = 0. Следовательно, при k > 2 система не полна.(g) A = {x · y, max (x, y) − z + 1}. Решение. Утверждается, что для E = {1} система A ⊆ T (E ). Действительно, 1 · 1 = 1, max (1, 1) − 1 + 1 =1. Следовательно, при k > 2 система не полна. 2(h) A = −x , max (x, y) + z . Решение. Утверждается, что для E = {k − 1} система A ⊆ T (E ). Действительно,− (k − 1)2 = k − 1, max (k − 1, k − 1) + k − 1 = k − 1.Следовательно, при k > 2 система не полна.no(i) A = 1, −x · y, x2 −̇y . Решение. Утверждается, что для E = {1, k − 1} система A ⊆ T (E ). Действительно, константа единицасохраняет это множество, −1·1 = − (k − 1)·(k − 1) = k −1, −1·(k − 1) = − (k − 1)·1 = 1, 12 −̇1 = 12 −̇ (k − 1) =(k − 1)2 −̇1 = (k − 1)2 −̇ (k − 1) = 1.
Следовательно, при k > 2 система не полна.(j) A = {2, max (x, y) , x−̇y}. Решение. Утверждается, что для E = {0, 2} система A ⊆ T (E ). Действительно, константа 2 сохраняетэто множество, функция максимума сохраняет любое множество, а 0−̇0 = 0−̇2 = 2−̇2 = 0, 2−̇0 = 2. Следовательно, при k > 3 система не полна. При k = 2 рассматривать систему не имеет смысла, так как онасодержит константу 2.(k) A = {k − 2, ∼ jk−2 (x) , max (x, y) , x + y}. Решение.
Утверждается, что для E = {k − 2} система A ⊆ T (E ). Действительно, константа k − 2 сохраняет это множество, функция максимума сохраняет любое множество, а ∼ jk−2 (k − 2) = k − 2, k − 2 + k − 2 =k − 2. Следовательно, при k > 2 система не полна.(l) A = { j2 (x) , x + j0 (x) + J1 (x) , x · y, x−̇y}. Решение. Утверждается, что для E = {0, 1} система A ⊆ T (E ). Действительно, j2 (0) = j2 (1) = 0, 0 +j0 (0) + J1 (0) = 1, 1 + j0 (1) + J1 (1) = 0, 0 · 0 = 0 · 1 = 1 · 0 = 0, 1 · 1 = 1, 0−̇0 = 0−̇1 = 1−̇1 = 0, 1−̇0 = 1.Следовательно, для k > 3 система не полна. При k = 2 рассматривать систему не имеет смысла, так как онасодержит функцию j2 (x).(m) A = {1, J0 (x) , x + jk−1 (x) , min (x, y) , max (x, y)}.
Решение. Утверждается, что для D = {0} {1, . . . , k − 1} система A ⊆ U (D). Действительно, константа сохраняет любое разбиение, функции минимума и максимума сохраняют любое монотонное разбиение, а D вданном случае — монотонное, функция J0 (x) сохраняет D очевидным образом: при x 6= 0 все значения J0равны 0, то есть попадают в один блок, а блок, состоящий из одного элемента сохраняет любая функция.Обозначив третью функцию через f (x), имеем f (a) ∈ {1, . . . , k − 1} ∀a ∈ {1, .
. . , k − 1}. Следовательно, дляk > 3 система не полна. При k = 2 система, очевидно, полна, так как вторая функция превратится в отрицание, а четвертая в конъюнкцию.732.1. ФУНКЦИИ КОНЕЧНОЗНАЧНОЙ ЛОГИКИ(n) A = {1, 2, . . . , k − 1, x + j0 (x) , j2 (x) + 1, max (x, y)} Решение. Утверждается, что для D = {0, 1} {2} {3, . .
. , k − 1} система A ⊆ U (D). Действительно, константы сохраняют любое разбиение, функция максимума сохраняет данное разбиение в силу его монотонности, функция x + j0 (x) переставляет элементы в первом блоке, а остальные оставляет неподвижными,функция j2 (x) + 1 отображает элементы первого блока в единицу, второй блок оставляет неподвижным, аэлементы третьего блока отображает в единицу.
Следовательно, при k > 3 система не полна. При k = 2 рассматривать систему не имеет смысла, так как она содержит функцию j2 (x) + 1.no(o) A = 1, ∼ x, x−̇y, min (x, y) Решение. Утверждается, что для E = {1, k − 2} система A ⊆ T (E ). Действительно, константа, отрицаниеЛукасевича и минимум тривиально сохраняют это множество. Также 1−̇1 = 1−̇ (k − 2) = (k − 2) −̇ (k − 2) =1, (k − 2) −̇1 = k − 2.
Следовательно, при k > 3 система не полна. При k = 2 система, тривиально, полна,потому что отрицание Лукасевича, тривиально, перейдет в простое отрицание, а минимум — в конъюнкцию.(p) A = {∼ x, J0 (x) , J1 (x) , . . . , Jk−1 (x) , min (x, y) + ( j0 (x) + j0 (y)) · (x + y)} Решение. Утверждается, что для D = {0, k − 1} {1, . . . , k − 2} система A ⊆ U (D). Действительно, образыотрицания Лукасевича и всех Ji совпадает с первым блоком. Обозначим последнюю функцию через f (x, y).Если и x, и y принимают значение из второго блока, то и f (x, y) примет значение также из второго блока (второе слагаемое обнулится, а минимум не выводит за пределы одного блока). Далее, f (0, 0) = 0, f (0, k − 1) =f (k − 1, 0) = f (k − 1, k − 1) = k − 1, то есть первый блок переходит посредством f (x, y) в первый блок.
Пустьтеперь a из второго блока. Легко видеть, что f (0, a) = f (k − 1, a) = a, а также, f (x, y) = f (y, x), откуда следует, что наборы со значениями из разных блоков отображаются все во второй блок. Следовательно, приk > 3 система не полна. При k = 2 система полна, так как отрицание Лукасевича перейдет в простое отрицание, которое не сохраняет константы и не монотонно, а последняя функция станет равна xy ⊕ x ⊕ y, при этомявляясь нелинейной и несамодвойственной.3. Пусть E — непустое подмножество из Ek , отличное от всего Ek , и D = {E , Ek \ E }. Подсчитать число функций вPk , зависящих от переменных x1 , x2 , . .
. , xn (n > 0) и содержащихся в множестве:(a) T (E ) \U (D);(b) U (D) \ T (E );(c) T (E ) ∪U (D).e n назовем вектор из нулей и единиц (δ1 , . . . , δn ), где Решение. Для начала найдем |U (D)|hni . Типом набора αe n и βen назовемδi = 0 ⇔ αi ∈ E . Все множество наборов разобьем на классы эквивалентности: два набора α e n k назовем число единиц в его типе эквивалентными, если они имеют одинаковый тип.
Весом набора kαδen .Всего классов эквивалентности — 2n . В одном классе эквивалентности с весом l содержится (k − m)l mn−l различных наборов. Каждому такому набору внутри одного класса эквивалентности функцией, сохраняющей разбиение, ставится в соответствие либо одно из m значений из E , либо одно из k − m значений из Ek \ E , причем этивозможности несовместны.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
