А.А. Вороненко, В.С. Федорова - Дискретная математика. Задачи и упражнения с решениями, страница 8

Используя метод сведения к заведомо полным системам, доказать полноту в Pk следующих систем:· y};1) {J0 (x), J1 (x), . . . , Jk−1 (x), x2 , x −· y, x + y};2) {k − 1, x −· y};3) {∼ x, x + 2, x −· y}.4) {−x, 1 − x2 , x −J1. Сведём данную систему к системе Россера–Туркетта:0 = J1 (J0 (x)),k − 1 = J0 (0),1 = (k − 1)2 ,· 1,k − 2 = (k − 1) −...· 1,2=3−· (x −· y) (см.

III.1.1(3)),min(x, y) = x −max(x, y) =∼ min(∼ x, ∼ y).2. Сведём данную систему к системе Поста:· y + y,max(x, y) = x −k − 2 = (k − 1) + (k − 1),· (k − 2),1 = (k − 1) −x̄ = x + 1.3. Для любого k > 3· (x −· y) = min(x, y),x−∼ min(∼ x, ∼ y) = max(x, y).63Для нечётных k получим систему Поста:(x+2) + 2 + . . . + 2 = x + 1 = x̄.{z}|(k+1)/2 разДля чётных k получим систему Россера–Туркетта:· x = 0,x−0 + 2 = 2,2 + 2 = 4,...(k − 4) + 2 = k − 2,∼ 0 = k − 1,∼ 2 = k − 3,...∼ (k − 2) = 1,· x) . .

. −· x) −· x,J0 (x) = (. . . ((k − 1) −|{z}k − 1 разДля чётных c :Jc (x) = J0 (x+2) + 2 + . . . + 2,|{z}c/2 разДля нечётных c :Jc (x) = Jk−1−c (∼ x).4. Сведём данную систему к системе Поста:· x = 0,x−1 − x2 x=0 = 1,−xx=1 = k − 1,· y =∼ y,(k − 1) −· (x −· y) = min(x, y),x−∼ min(∼ x, ∼ y) = max(x, y),−(∼ x) = k − ((k − 1) − x) = x + 1 = x̄. IIII.2.20(1, 2). Используя критерий Слупецкого, доказать полноту вPk следующих систем:· y};1) {k − 1, x − y + 2, x2 −2) {j2 (x), x + y 2 , x · y + 1}.64J1. (x − y + 2) — существенная функция, принимающая все k значений.· (k − 1) = 0,(k − 1)2 −· 0 = 1,(k − 1)2 −x − y + 2y=1 = x + 1 = x̄,x − y + 2 = x − y,(x−y) − y − .

. . − y = x + y,{z}|k−1 раз· x = j0 (x),1 −2j0 (x + (k − 1)) = j1 (x),(x + j0 (x)) − j1 (x) = h01 (x).Итак, получена система {x̄, x + j0 (x), h01 (x)}, которая является(1)полной в Pk по теореме С. Пикар.2. (x + y 2 )— существенная функция, принимающая все k значений.j2 (j2 (x)) = 0,x · 0 + 1 = 1,x + 12 = x.При помощи отрицания поста получаем все константы и функциивида x + c.j2 (x +2) = j0 (x),x + y 2 y=j0 (x) = x + j0 (x),j0 (x + (k − 1)) = j1 (x).Заметим, что(x + j0 (x)) + j12 (x) + . .

. + j12 (x) = x + j0 (x) − j1 (x) = h01 (x).{z}|k−1 разПолучили систему {x̄, x + j0 (x), h01 (x)}, которая является полной(1)в Pk по теореме С. Пикар.IIII.2.21(5, 6, 11). Исследовать на полноту в Pk следующие системы:· y};5) {2, 2x + y, x2 −6) {1, 2, max (x̄, y)};· y}.11) {∼ x, 2j0 (x), J1 (x), x −J5. Если k чётно, то все три функции сохраняют множество чётныхконстант, то есть принадлежат классу T ({0, 2, . .

. , k −2}), поэтомусистема не полна в Pk .65Если k нечётно, то(y+2x) + 2x + . . . + 2x = y + x,|{z}(k+1)/2 раз2| + 2 +{z. . . + 2} = 1,(k+1)/2 раз2 · · y = j0 (y).x − y x=1 = 1 −При нечётных k система {x + y, j0 (x)} полна в Pk .6. Система функций сохраняет множество Ek \{0}, следовательно, неявляется полной.11. Если k нечётно, то все четыре функции сохраняют множество чётных констант {0, 2, . . . , k − 1}, поэтому система не полна в Pk .Если k чётно, получим все константы:J1 (J1 (x)) = 0,∼ xx=0 = k − 1,2j0 (0) = 2,· 2 = k − 3,(k − 1) −...· 2 = 1,3−· 1 = k − 2,(k − 1) −· 2 = k − 4,(k − 2) −...· 2 = 4.6−Теперь получим систему Россера–Туркетта, что завершит доказательство полноты исходной системы:· c) = Jc+1 (x) для c 6= k − 1,J1 (x −· x) .

. . −· x) −· x,J0 (x) = (. . . ((k − 1) −|{z}k − 1 раз· (x −· y) = min(x, y),x−∼ min(∼ x, ∼ y) = max(x, y).IЗанятие № 2.5Задание детерминированных и ограниченнодетерминированных функций деревьямиIV.1.1(1– 3, 8– 10). Пусть f (x(1)x(2) . . . x(t) . . .) = y(1)y(2) . . . y(t) . . .1,1— функция из множества P2,ω. Выяснить, является ли она детерминированной:661)2)3)8)9)10)J2.3.8.9.10.y(1) = x(1) и y(t) = x(1) ⊕ x(2) ⊕ . . . ⊕ x(t) при t > 2;y(t) = x(1) ∨ x(2) ∨ .

. . ∨ x(t) ∨ x(t + 1) при t > 1;y(t) = x(1) · x(2) · . . . · x(t) · x(t + 2) → x(1) при t > 1;y(1) = 1 и y(t) = x(2 + x(t)) при t > 2;y(1) = y(2) = 0 и y(t) = x(2 + x(t)) при t > 3;y(1) = 1 и y(t) = x(2 + y(t − 1)) при t > 2.1. Да, является, так как значение функции в момент t зависиттолько от x(1), . . .

, x(t).Нет, так как y(1) = x(1) ∨ x(2), то есть y(1) существенно зависитот входа x(2).Да, несмотря на формальную зависимость от входа x(t+2), функция детерминирована, так как y(t) ≡ 1.Нет, так как при t = 2 и x(2) = 1 y(2) = x(2 + x(2)) = x(3).Да, так как y(t) = x(t)x(3) ∨ x̄(t)x(2) при t > 3.Нет, так как y(2) = x(2 + y(1)) = x(3).I1,1IV.1.2(1). Является ли детерминированной функция f из P2,ω, заданная следующим описанием:( ωe0 , если xeω = e0ω ,ωf (ex )=e1ω , в ином случае.J Нет, поскольку значение y(t) существенно зависит от бесконечногочисла входов x(s) таких, что s > t.I1,1IV.1.4(1, 2). В дереве, соответствующем функции f из P2,ω, измененаметка на ребре l -го яруса, принадлежащем цепи, отвечающей входнойпоследовательности 0ω .

Найти вес r(f ) функции f и вес r(g) вновь полученной функции g, если:1) f (exω ) ≡ e0ω , l = 3;2) f (exω ) = xeω , l = 4.J1. Вес исходной функции, очевидно, равен 1. Построим 4 ярусаинформационного дерева измененной функции. Применим естественную нумерацию вершин дерева: корень занумеруем нулём,а остальные вершины — натуральными числами по слоям, слеванаправо. Все вершины делятся на четыре класса эквивалентности: {0}, {1}, {3} и четвёртый — все остальные вершины. Поэтомуr(g) = 4.672. Вес исходной функции равен 1, так как все остаточные функциисовпадают с f . Построим 5 ярусов информационного дерева измененной функции. Все вершины делятся на пять классов эквивалентности: {0}, {1}, {3}, {7} и пятый — все остальные вершины.Поэтому r(g) = 5.IIV.1.10(1, 2). Выяснить, является ли функция f ∈ Pb2, д ограниченнодетерминированной функцией, и найти её вес:1 при t = 1,1) y(t) =x̄(t − 1) при t > 2;0 при t = 1,2) y(t) =x(t) при t > 2.J1.

Рассмотрим остаточные функции:f (0exω ) = 1f (exω ),f (1exω ) = 1f1 (exω ),f1 (0exω ) = 0f (exω ),f1 (1exω ) = 0f0 (exω ).Различных функций всего две. Следовательно, функция f является ограниченно-детерминированной, и r(f ) = 2.2. Да, является. Остаточными функциями f являются 0x(t + 1)x(t +2) . . . и x(t)x(t + 1)x(t + 2) . . ., поэтому функция f является ограниченно-детерминированной, и r(f ) = 2.IIV.1.15(1). Функция f из PA, B, д называется автономной (или константой, или функцией без входа), если она принимает постоянное значение (на множестве Aω ), то есть если на любом входном слове xeω ∈ Aωфункция f равна одному и тому же (выходному) слову из B ω .Выяснить, является ли автономной функция f ∈ P2,1,1д , и, если онаавтономна, найти её вес:y(1) = 0,f:y(t) = ȳ(t − 1), t > 2.J Да, функция является автономной, так как f (exω ) = 010101... = [01]ω ,и r(f ) = 2.IЗанятие № 2.668Представление ограниченнодетерминированных функций диаграммамиМура и каноническими уравнениямиIV.2.1(1, 2, 6, 35).

Построить диаграмму Мура, каноническую таблицу и канонические уравнения для функции f (exω ) = y(1)y(2) . . . y(t) . . .1,1из P2,од:1 при t = 1,1) y(t) =x(t − 1) → x(t) при t > 2;0 при t = 1,2) y(t) =x(t − 1) → ȳ(t − 1) при t > 2;x(t) при t = 1, 2,6) y(t) =x̄(t − 1) при t > 3; 0, если t = 3s − 2 и s > 1,1, если t = 3s − 1 и s > 1,35) y(t) = x(t) в ином случае.J1. Положим q(t) = x̄(t) и получим следующие канонические уравнения, описывающие заданную функцию: y(t) = q(t − 1) ∨ x(t),q(t) = x̄(t), q(0) = 1.Каноническая таблица:x(t) q(t − 1) y(t) q(t)0001011101011110Диаграмма Мура:692. Для запоминания x(t − 1) и y(t − 1) используем две переменные:q1 (t − 1) и q2 (t − 1) соответственно.

При этом y(1) = 0:y(t) = q̄1 (t − 1) ∨ q̄2 (t − 1), q1 (t) = x(t),q2 (t) = q̄1 (t − 1) ∨ q̄2 (t − 1),q1 (0) = 1, q (0) = 1.2Сделаем следующую замену переменных:q(t) = q̄1 (t) ∨ q̄2 (t)Тогда получаем канонические уравнения: y(t) = q(t − 1),q(t) = q̄(t − 1) ∨ x̄(t), q(0) = 0.Соответствующая каноническая таблица:x(t) q(t − 1) y(t) q(t)0001011110011110Диаграмма Мура:6. По заданной функции построим диаграмму Мура:70Каноническая таблица:x(t) q1 (t − 1) q2 (t − 1) y(t) q1 (t) q2 (t)000001010100010110011010100101101111110111111011Канонические уравнения:y(t) = q1 (t − 1) · q̄2 (t − 1) ∨ x(t) · q̄1 (t − 1), q1 (t) = q1 (t − 1) ∨ q2 (t − 1),q2 (t) = x(t) ∨ q̄1 (t − 1) · q̄2 (t − 1),q1 (0) = 0, q (0) = 0.235.

Закодируем моменты времени с помощью q1 (t) и q2 (t): пусть 00соответствует t = 3s, 01 соответствует t = 3s − 1 и 10 соответствует t = 3s − 2. Построим каноническую таблицу с учетом этого.Так как состояние 11 не достигается, то в соответствующих емустроках величины y(t), q1 (t) и q2 (t) можно доопределить произвольным образом. q1 (0) = 1, q2 (0) = 0 — начальный момент, таккак t = 1 соответствует t = 3s − 2 при s = 1.71x(t) q1 (t − 1) q2 (t − 1) y(t) q1 (t) q2 (t)000010001100100010011101100110011001110001111001Канонические уравнения:y(t) = x̄(t) · q2 (t − 1) ∨ x(t) · q̄1 (t − 1), q1 (t) = q̄1 (t − 1) · q̄2 (t − 1),q2 (t) = q1 (t − 1),q1 (0) = 1, q (0) = 0.2По таблице построим диаграмму Мура, которая, очевидно, является приведенной:IIV.2.4(2).

Найти вес ограниченно-детерминированной функции f иззаданной каноническими уравнениями:y(t) = x(t) ⊕ q1 (t − 1), q1 (t) = x(t) · q2 (t − 1),q2 (t) = q̄1 (t − 1),f:q1 (0) = 1, q (0) = 0.1,1P2,од,2J Построим каноническую таблицу:72x(t) q1 (t − 1) q2 (t − 1) y(t) q1 (t) q2 (t)000001001001101000011100100101011111110000111010Нарисуем диаграмму Мура:Так как эквивалентных вершин нет, диаграмма является приведенной,и вес функции f равен четырём.IЗанятие № 2.7Операции над ограниченнодетерминированными функциямиIV.2.8(6, 7).

Для суперпозиции f = f1 (f2 ) ограниченно-детерминированных функций f1 и f2 из Pb2,oд построить канонические уравнения иприведённую диаграмму Мура.6. Функция f1 задаётся диаграммой Мура, изображённой на рисунке:73 y2 (t) = x2 (t) | q2 (t − 1),q2 (t) = x2 (t) → q̄2 (t − 1),f2 : q (0) = 1.27. Функции f1 и f2 задаются диаграммами Мура, изображёнными нарис. 1 и рис. 2 соответственно:Рис.