А.А. Вороненко, В.С. Федорова - Дискретная математика. Задачи и упражнения с решениями (1060726), страница 7
Текст из файла (страница 7)
IЗанятие № 2.2Замкнутые классы. Представление функцийполиномами по модулю kIII.2.2(1– 3). Для функции f из Pk при заданном k подобрать классытипа T (ξ) и U (D), которым она принадлежит. При этом ξ должно бытьсобственным подмножеством множества Ek (то есть ξ 6= ∅ и ξ 6= Ek ),а D — таким разбиением {ξ1 , .
. . , ξs } множества Ek , чтобы выполнялисьнеравенства 1 < s < k:1) k = 3, f = x2 + 1;2) k = 3, f = J0 (x2 + 2x);· y 2 ) + 1.3) k = 3, f = (x2 −J1. Построим таблицу значений данной функции f :55x f (x)0 11 22 2При х ∈ ξ = {1, 2} значения f (x) принадлежат ξ. При этом ξ —собственное подмножество множества Eξ . Значит, f (x) содержитсяв классе T ({1, 2}).Рассмотрим разбиение D = {{0}, {1, 2}}. Функция f (x) сохраняет его, так как первая компонента разбиения состоит из одногоэлемента, а для второй верно f (1) = f (2) = 2. Значит, f (x) содержится в классе U ({0}, {1, 2}).2.
Построим таблицу значений данной функции f :x f (x)0 21 22 0Функция сохраняет множество {0, 2} и разбиение {{1}, {0, 2}}, поэтому содержится в классе U ({1}, {0, 2}).3. Построим таблицу значений данной функции f :@ y@x @@0120 1 21 1 12 1 12 1 1При х, y ∈ ξ = {1, 2} значения f (x) принадлежат ξ — собственному подмножеству множества Ek . Значит, f (x) содержится в классеT ({1, 2}).Рассмотрим разбиение D = {{0}, {1, 2}}. Функция f (x) сохраняет его, и поэтому f (x) содержится в классе U ({0}, {1, 2}).IIII.2.3.1.
Пусть ξ ⊆ Ek . Доказать, что T (ξ) 6= Pk тогда и только тогда, когдаξ — собственное подмножество множества Ek .2. Сколько существует различных замкнутых классов в Pk , являющихся классами сохранения множеств?3. Пусть ξ ⊆ Ek . Подсчитать число функций в Pk , содержащихся вклассе T (ξ) и зависящих от переменных x1 , x2 , . .
. , xn (n > 0).56J1. Если функция f (exn ) на множестве ξ n принимает хотя бы однозначение не из ξ, то она не принадлежит классу T (ξ). В силу замкнутости класса T (ξ), он не совпадает с Pk при ξ 6= ∅ и ξ 6= Pk .Если же ξ = ∅ или ξ = Pk , то любая функция из Pk сохраняетмножество ξ.2. k-элементное множество ξ имеет 2k подмножеств.
Из них собственными являются 2k − 2. Следовательно, соответствующих им замкнутых классов T (ξ), не равных Pk , также будет 2k − 2.3. Везде, кроме множества ξ n , функция из T (ξ) может приниматьпроизвольные значения; на множестве же ξ n — только значения,принадлежащие ξ. Поэтому общее количество функций n переменnnnных, содержащихся в T (ξ), в точности равно |ξ||ξ| · k k −|ξ| .IIII.2.4(1). Пусть D = {ξ1 , . . .
, ξs } — разбиение множества Ek . Доказать, что U (D) 6= Pk тогда и только тогда, когда 1 < s < k.J Класс сохранения разбиения U (D) замкнут. Если разбиение нетривиально (1 < s < k), то всегда найдутся два различных эквивалентныхнабора. Функция, определённая на них неэквивалентными значениями,не принадлежит классу U (D), поэтому U (D) 6= Pk . Если s = k, то эквивалентность наборов означает их совпадение.
Если s = 1, то все значенияфункций эквивалентны. Таким образом, в этих случаях U (D) = Pk . IIII.2.7(1, 6). Разложить в полином по модулю k функцию f из Pk :· x2 , k = 5;1) f = 2x −6) f = min (x2 , y), k = 3.J1. Построим таблицу значений данной функции f :x 2x x2 f (x)0 0 001 2 112 4 403 1 404 3 12Представим f (x, y) во второй форме:f (x) = j1 (x) + 2j4 (x).Воспользуемся тем, что j0 (x) = 1 − xk−1 , если k — простое числои k > 3, и ji (x) = j0 (x − i), где разность и степень берутся помодулю k. В результате получаемf (x) = j0 (x − 1) + 2j0 (x − 4) = (1 − (x − 1)4 ) + 2(1 − (x − 4)4 ) == 3x4 + 3x2 + 1.576.
Построим таблицу значений данной функции f :@ y@0 1 2x @@00 0 00 1 1120 1 1Представим f (x, y) во второй форме:f (x, y) = j1 (x) · j1 (y) + j1 (x) · j2 (y) + j2 (x) · j1 (y) + j2 (x) · j2 (y).Заметим, что j0 (x) + j1 (x) + j2 (x) = 1 при k = 3. Имеемf (x, y) = (1 − j0 (x)) · (1 − j0 (y)) = x2 · y 2 .
IIII.2.12(1, 2). Выяснить, представима ли полиномом по модулю kфункция f из Pk :· 2x2 , k = 4;1) f = 3x −2) f = 3j0 (x), k = 6.J1. Построим таблицу степеней x по модулю 4 и значений функции:x x2 x3 x4 f (x)0 0 0 001 1 1 112 0 0 023 1 3 10Отметим, что x4 ≡ x2 .
Поэтому, если f (x) представима полиномом, то он имеет степень не больше 3:f (x) = a0 + a1 · x + a2 · x2 + a3 · x3 .По вектору значений функции получаем систему уравнений:a0 + 0 · a1 + 0 · a2 + 0 · a3 = 0, a0 + 1 · a1 + 1 · a2 + 1 · a3 = 1,a0 + 2 · a1 + 0 · a2 + 0 · a3 = 2,a0 + 3 · a1 + 1 · a2 + 3 · a3 = 0Упростим систему:a0= 0,a1 + a2 + a3 = 1,2a1= 2,3a1 + a2 + 3a3 = 058Вычтем из четвёртого уравнения второе и получим уравнение 2a1 +2a3 = 3, которое не имеет решений.
Поэтому система не совместна,а функция f (x) не представима полиномом по модулю 4.2. Построим таблицу значений функции и значений x2 , x3 :x x2 x3 f (x)0 0 031 1 102 4 203 3 304 4 405 1 503Отметим, что x ≡ x. Если f (x) представима полиномом, то онимеет степень не выше 2:f (x) = a0 + a1 · x + a2 · x2 .Получаем систему уравнений:a0 + 0 · a1 + 0 · a2a0 + 1 · a1 + 1 · a2 a0 + 2 · a1 + 4 · a2a0 + 3 · a1 + 3 · a2a0 + 4 · a1 + 4 · a2a0 + 5 · a1 + 1 · a2= 3,= 0,= 0,= 0,= 0,=0Из первого уравнения a0 = 3.
Подставив a0 во второе уравнение,получаем a1 + a2 = 3. Подставив это в пятое уравнение, получимслева 3, а справа 0. Таким образом, система не имеет решений, азначит, и функцию f (x) нельзя представить полиномом по модулю6.IIII.2.13(1, 2). Подобрав подходящий класс типа T (ξ) или U (D), доказать, что система А не полна в Pk :1) A = {∼ x, min (x, y), x · y 2 };· j2 (x), max (x, y)}.2) A = {1, 2, x −J1. Функции ∼ x и min (x, y) сохраняют множество ξ = {0, k − 1}.Проверим, принадлежит ли функция x · y 2 классу T {ξ}:0 · 02 = 0,0 · (k − 1)2 = 0,(k − 1) · 02 = 0,(k − 1) · (k − 1)2 = k − 1.Все функции системы А содержатся в T ({0, k − 1}), а значит, система А не полна в Pk .592. Функции 1, 2 и max (x, y) сохраняют множество ξ = {1, 2}.
Про· j2 (x) классу T (ξ):верим, принадлежит ли функция x −· j2 (1) = 2,1−· j2 (2) = 2.2−Все функции системы А содержатся в T ({1, 2}), а значит, системаА не полна в Pk .IЗанятие № 2.3Полнота систем функций многозначной логикиIII.2.14. Как известно, системаA = {0, 1, . . . , k − 1, j0 (x), j1 (x), . . . jk−1 (x), x + y, x · y}полна в Pk .1. Доказать, что из системы A можно выделить полную в Pk подсистему, состоящую из двух функций.2. Показать, что любая подсистема системы A, состоящая из однойфункции, не полна в Pk .J1. Рассмотрим систему B = {j0 (x), x + y}. Выразим все функциисистемы A через функции системы B.
Так как A полна в Pk , тотем самым будет доказана полнота в Pk системы B.Получение недостающих функций:1 = j0 (x) + j0 (j0 (x)),2 = 1 + 1,...0 = (k − 1) + 1,ji (x) = j0 (x + (k − i)),x·y =k−1 Xk−1Xjσ1 (x) · jσ2 (y) · σ1 · σ2 =σ1 =0 σ2 =0k−1 Xk−1 u=σ1 ·σ2XXσ1 =0 σ2 =0jσ1 (x) · jσ2 (y),u=1где jσ1 (x) · jσ2 (y) = j2 (jσ1 (x) + jσ2 (y)).2. Заметим, что любая функция системы A содержится в каком-тоиз нетривиальных классов типа T (ξ):– функции 0, x + y, x · y содержатся в классе T ({0});– функции j0 (x), j1 (x), ..., jk−1 (x) — в классе T ({0, 1});– функции 1, 2, ..., k − 1 — в классе T ({1, 2, . . . , k − 1}).60Значит, никакая подсистема системы A, состоящая из одной функции, не полна в Pk .IIII.2.15.
Система Россера–ТуркеттаA1 = {0, 1, . . . , k − 1, J0 (x), J1 (x), . . . , Jk−1 (x), min (x, y), max (x, y)},как известно, полна в Pk .1. Проверить, что, удаляя из A1 любую константу, отличную от 0и k − 1, получаем подсистему, содержащуюся в некотором классетипа T (ξ), где ∅ 6= ξ 6= Ek (и, значит, неполную в Pk ).2. Выделить из системы A1 полную в Pk подсистему, состоящую из2k − 2 функций.J1. Удалим из A1 любую константу i, отличную от 0 и k − 1. Получим подсистему, содержащуюся в классе T (Ek \ {i}).2.
Рассмотрим подсистему системы A1 , состоящую из 2k−2 функций:{1, 2, . . . , k − 2, J1 (x), J2 (x), . . . , Jk−2 (x), min (x, y), max (x, y)}.Докажем, что рассматриваемая система полна:0 = J1 (J1 (x)),k − 1 = J1 (1),J0 (x) = J1 (max (1, x, J1 (x), J2 (x), . . . , Jk−2 (x)),Jk−1 (x) = J0 (max (J0 (x), J1 (x), . . . , Jk−2 (x))). IIII.2.16(1, 3). Для заданных k исследовать на полноту следующиеподсистемы системы Россера–Туркетта:1) k = 3, {1, J0 (x), J2 (x), min (x, y), max (x, y)};3) k = 4, {1, 2, J0 (x), J1 (x), min (x, y), max (x, y)}.J1. Сведём данную подсистему к заведомо полной системе Россера–Туркетта и тем самым докажем полноту подсистемы.
Для этогонужно выразить функции 0, 2, J1 (x) через функции подсистемы:0 = J0 (1),2 = J0 (0),J1 (x) = J0 (max (J0 (x), J2 (x))).3. Константы сохраняют любое разбиение. Функция Ji (x) сохраняет любое разбиение, в котором константа i принадлежит одноэлементному множеству. Минимум и максимум сохраняют все монотонные разбиения. Таким образом, все функции системы принадлежат классу U ({0}, {1}, {2, 3}). Система не полна.IIII.2.22(1, 2, 5). Доказать, что приводимые ниже системы полны вPk тогда и только тогда, когда k — простое число:611) {1, x + y + x · z};2) {x − y + 1, x2 − y, x · y 2 };5) {k − 2, x + 2y, x · y 2 }.J Система полиномов по модулю k (и, следовательно, любая её подсистема) неполна при составном k.
Для полноты подсистемы при простомk достаточно получить функции 1, x + y и x · y.1. Подставим x = y = 1 в функцию x + y + x · z, получим функциюz + 2, из которой получаются все константы тогда и только тогда,когда k — нечётное число. Далееx + y + x · z z=0 = x + y,x + y + x · z y=0 = x + x · z = x(z + 1)z=u−1 = x · u.2.x − y + 1x=y = 1,x2 − y x=1 = 0,y=1x − y + 1 = x + 1,y=0следовательно, можно получить все константы. Далееx − y + 1y=u+1 = x − u,x · y 2 x=1 = y 2 ,x−y − . .
. − y = x + y.|{z}k−1 разДля того, чтобы получить произведение, рассмотрим функциюx2 − y y=(u−v)2 = 4 · u · v.x=(u+v)Обозначим через c−1 решение уравнения c · x ≡ 1 (mod k). Тогда. . + 4uv} = uv.|4uv + .{z4−1 раз5. Если k — простое число, то(x+2y) + 2y + . . . + 2y = x + y,|{z}(k+1)/2 раз(x + y) + y + . . . + y = x − y,|{z}k−1 раз(k − 2) + . . . + (k − 2) ≡ 1|{z}(k−2)−1 раз62(mod k).Далее получаемx · y 2 x=1 = y 2 ,(x + y)2 − (x − y)2 = 4xy,4xy + . . . + 4xy = 1.I|{z}4−1 разЗанятие № 2.4Исследование систем функций на полноту.Критерий СлупецкогоIII.2.19(1– 4).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
