Как найти вес ограниченно детерминированной функции

8.1 Детерминированные функции.

8.2 Графическое задание детерминированных функций

8.3 Ограниченно-детерминированные функции.

8.4 Каноническое уравнение ограниченно-детерминированных функций

Автоматом называют дискретный преобразователь информации, способный принимать различные состояния, переходить под воздействием входных сигналов из одного состояния в другое и выдавать выходные сигналы.

Если множество состояний автомата, а так же множество входных и выходных сигналов конечны, то автомат называют конечным автоматом. Все реальные автоматы являются конечными.

Информацию, поступающую на вход автомата, и преобразующую входную информацию принято кодировать конечной совокупностью символов. Эту совокупность называют алфавитом, отдельные символы, образующие алфавит буквами, а любые конечные упорядоченные последовательности букв данного алфавита словами в этом алфавите.

Автоматы функционируют в дискретные моменты времени, которые обозначаются натуральными числами t=0, 1, 2,…. В каждый момент дискретного времени на вход автомата поступает один сигнал (буква), фиксируется определённое состояние автомата и с выхода снимается один сигнал. Реальные автоматы могут иметь, вообще говоря, несколько входов и выходов. В некоторых случаях для решения задач синтеза удобно заменить такие автоматы автоматами с одним входом и одним выходом. Для этого достаточно закодировать соответствующим образом входные и выходные сигналы исходного алфавита. Если, например, автомат имеет два входа, на каждый из которых подаются сигналы 0 или 1, то все возможные комбинации входных сигналов можно закодировать четырьмя буквами (0, 0), (0, 1), (1, 0), (1, 1).

Процесс дискретного преобразования информации автоматами можно описать с помощью детерминированных функций.

8.1 Детерминированные функции. Обозначим через ={0, 1, …, k-1}, где k – некоторое натуральное число, а через множество всех k-значных последовательностей A Таких, что А={A(1), A(2),…,A(t), …}, где A(i) для всех i=1, 2,… .

Обозначим через множество всех функций y=F определённых на наборах , где и принимающие значение из . Функции из преобразуют наборы k-значных последовательностей в k-значные последовательности. В множество включим так же все последовательности из , рассматривая их как функции, зависящие от пустого множества переменных, т. е. как константы.

С помощью векторной записи функции от N переменных из можно свести к функции от одной переменной. Обозначим набор переменных через Х, вместо y=F будем писать y=F (Х). При этом значение переменной Х есть вектор А= компонентами которого являются последовательности из , .Будем рассматривать а как последовательность векторов , где .

Таким образом, мы будем считать, что выполняется тождество: =.

Лемма 1: Число наборов , где равно .

Итак, функцию y=F с помощью векторной записи можно свести к функции y=, где N=. Таким образом, изучение функции y=F из можно свести к изучению функции от одной переменной из , где N=.

Определение 1: Функция y= из называется детерминированной, если какого бы ни было число t и каковы бы ни были последовательности а и b такие, что

A(1)=B(1), A(2)=B(2), … A(t)=B(t) значение функций α, β, где α=, β= представляют собой последовательности, у которых тоже совпадают первые t членов, т. е. α(1)=β(1), α(2)=β(2), …, α(t)=β(t).

Множество всех детерминированных функций обозначим через .

Из определения детерминированной функции следует, что значение α(t) (α=) зависит только от значения первых t членов входной последовательности а, т. е. А(1), А(2), …, А(t), следовательно.

α(t)=φ(А(1), А(2), …, А(t)).

Приведём примеры как детерминированных, так и недетерминированных функций.

Пример 1. Рассмотрим функцию y=, определённую следующим образом

Покажем, что данная функция недетерминированная. Действительно, возьмём две входные последовательности и . Тогда и . Следовательно, данная функция недетерминированная.

Пример 2. Рассмотрим функцию из , определённую следующим образом .Здесь выходная последовательность – почленная конъюнкция входных последовательностей. Очевидно, что .

Пример 3. Рассмотрим функцию z=X+y осуществляющую сложение 2-значных последовательностей в двоичной системе с бесконечным числом разрядов. Для этого используется обычный алгоритм сложения двух чисел столбиком

Очевидно, что Z(T) определяется по первым T слагаемых, т. е. X+y.

Детерминированная функция может быть проинтерпретирована следующим образом. Пусть мы имеем некоторый «дискретный преобразователь», в котором существует N Входов и один выход .

На входы в моменты времени T=1,2,…,M, … подаются входные последовательности

И в эти же моменты T На выходе возникает выходная последовательность , причем . Очевидно, что в дискретном преобразователе значения α(T) Зависит только от значений входных последовательностей в момент времени 1,2,…,T и не зависит от значений в будущие моменты времени. Поэтому преобразование есть детерминированная функция.

8.2 Графическое задание детерминированных функций. Пусть . Выше мы показали, что с помощью векторной записи данную функцию можно свести к функции , где . Рассмотрим бесконечную фигуру:

Построена она следующим образом, и называть её будем деревом. Возьмём произвольную вершину , которую назовём корнем дерева. Из неё проведём N рёбер, которые образуют первый ярус. Из концов каждого из рёбер также проведём N рёбер, которые образуют второй ярус и т. д. .Рёбра каждого пучка нумеруются слева направо числами 0,1,…,N-1 или их значениями в k-ичной системе счисления.

В дальнейшем на рисунках номера рёбер будут опускаться. Далее, каждому ребру в построенном дереве произвольным образом припишем одно из чисел множества {0,1,…,k-1}. В результате получим так называемое нагруженное дерево. Рассмотрим следующее нагруженное дерево.

Начиная движение с корня дерева, пойдём по рёбрам. Так, например, последовательности (0,0,1,1…), где числа 0,0,1,1, … – номера рёбер, соответственно, 1-го,2-го,3-го,4-го и т. д. ярусов соответствует выделенный маршрут и последовательность (0,1,1,1…).

Теорема 1: Функция из будет детерминированной тогда и только тогда, когда она может быть заданна с помощью нагруженного дерева.

Доказательство: Покажем, что любое нагруженное дерево задает некоторую детерминированную функцию. Действительно, пусть – произвольная последовательность чисел, где , i=1,2,…. Будем считать, что – номер ребра 1-го яруса, – номер ребра 2-го яруса и т. д. Данной последовательности в нагруженном дереве соответствует единственный маршрут, ведущий из корня дерева. Числа, приписанные выделенным ребрам образуют выходную последовательность . Покажем, что построенная функция из является детерминированной. Пусть и – две входные последовательности такие, что . Ясно, что маршруты в нагруженном дереве, соответствующие данным последовательностям на первых t ярусах совпадают. А это значит, что , т. е. функция детерминированная. Обратное утверждение очевидно. Теорема доказана.

Рассмотрим следующие примеры:

Пример 4. . Ясно, что и число ребер, выходящих из вершин равно . Построим дерево соответствующее данной функции.

. . . . . . . . . .

Например, входной последовательности {0,1,1,…} будет соответствовать входная последовательность {1,0,0,…}.

Пример 5. , которая задаётся следующим образом.

, где X(t)·y(t) – конъюнкция.

Для данной функции k=n=2 и число ребер, выходящих из вершин равно N==4. Ребру с номером D=(0,0) соответствует значение (0,0)=0

1=(0,1) 0·1=0

2=(1,0) 1·0=0

3=(1,1) 1·1=1.

Следовательно, данной функции соответствует следующее нагруженное дерево.

Пример 6. , k=n=1, N==1.

Дерево, соответствующее данной функции строится следующим образом. Процесс приписывания ребрам чисел начинается с 1-го яруса

0=(0,0) 0+0=0

1=(0,1) 0+1=1

2=(1,0) 1+0=1

3=(1,1) 1+1=0

При этом, если появляется перенос в следующий разряд, то конец соответствующего ребра кончается кружочком. Это позволяет выполнить вычисление в следующем ярусе.

8.3 Ограниченно-детерминированные функции. Возьмем нагруженное дерево для некоторой детерминированной функции . Пусть – произвольная его вершина -го яруса. Данную вершину можно рассматривать как корень нагруженного дерева. Согласно теореме 1 оно определяет некоторую детерминированную функцию .

Определение 2. Два поддерева с корнями и исходного дерева называются эквивалентными, если .

Очевидно, что при естественном наложении двух эквивалентных поддеревьев их нумерации совпадают. Так, в дереве Рис.1 и Рис.2 все поддеревья эквивалентны, а в дереве Рис.3 поддеревья с корнями эквивалентны, а с корнями и не эквивалентны.

Определение 3. Весом дерева и весом соответствующей детерминированной функции называется максимальное число попарно неэквивалентных поддеревьев.

Например, все функции из примеров 4,5 равен 1, а из примера 6 равен 2.

Определение 4. Детерминированная функция называется ограниченно – детерминированной функцией, если она имеет конечный вес.

Класс всех ограниченно – детерминированных функций обозначим через

Функции из примеров 4,5,6 являются ограниченно-детерминирован ными функциями.

Рассмотрим следующую детерминированную функцию.

Пример 7. . Ясно, что вес данной функции , т. е. она не является ограниченно-детерминированной.

Пусть , вес которой равен r. Рассмотрим алфавит , который назовём внутренним алфавитом. Каждой вершине нагруженного дерева, соответствующей функции припишем одну из букв алфавита с соблюдением следующего правила: эквивалентным вершинам приписываются одни и те же буквы из . В результате получаем так называемое полное нагруженное дерево.

Для любой ограниченно – детерминированной функции соответствующее ей полное нагруженное дерево можно свести к коечному дереву с занумерованными ребрами и вершинами. Если в нем провести отождествление эквивалентных вершин, то получим так называемую диаграмму Мура. В ней нулём отмечена начальная вершина и ребрам приписаны пары чисел (a, b), первое из которых обозначает номер ребра, а второе число соответствующее этому ребру. Так функция соответствует диаграмме Мура.

А функция

8.4 Каноническое уравнение ограниченно-детерминированных функций. Пусть – ограниченно-детерминированная функция с весом R.

Пусть – входная последовательность. Ей соответствует выходная последовательность и последовательность состояний .

Возьмем другую входную последовательность . Ей соответствуют, соответственно, выходная последовательность и последовательность состояний

.

В общем случае из того, что не следует, что . Однако, если и , то и . Другими словами это означает, что если два одноименных ребра () выходят из эквивалентных вершин (), то они будут нагружены одной и той же буквой () и входить в эквивалентные вершины (). Это означает, что

(*)

Уравнения (*) называются каноническими уравнениями функции . Первое уравнение называется уравнением выход, второе уравнением перехода.

Уравнение (*) можно задать с помощью канонической таблицы.

Пусть X(t) и y(t) из {0,1}, а . Если вес r≤2, то каноническая таблица есть таблица истинности. Если r>2, то каноническая таблица не является таблицей истинности. Но с помощью кодирования всех чисел алфавита в двоичной системе счисления мы её можем преобразовать в таблицу истинности.

Рассмотрим теперь функцию от n переменных с весом r>1, – внутренний алфавит. Закодируем все числа из алфавита в двоичной системе счисления наборами из {0,1} длинной . В этом случае канонические уравнения искомой функции имеют вид.

(**)

В дальнейшем договоримся, что начальные состояния в канонических уравнениях (**) Q(0)=0, а в уравнениях (*) .

Пример 8. Найти канонические уравнения функции

Ранее мы показали, что вес данных функций равен 2 и её диаграмма Мура

Построим каноническую таблицу.

X(t)	Y(t)	Q(t-1)	Z(t)	Q(t)
0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1	0 1 1 0 1 0 0 1	0 0 0 1 0 1 1 1

Данная каноническая таблица является таблицей истинности.

Запишем канонические уравнения, используя результаты раздела 3.

Используя законы алгебры логики

Пример 9. Найти каноническое уравнение для функции заданной следующей диаграммой Мура

Строим каноническую таблицу.

X(t)	Y(t)	Q(t-1)	Z(t)	Q(t)
0 0 1 1	0 1 0 1	0 0 0 0	0 1 1 0	0 0 0 0

Отсюда

Заметим, что если вес функции равен 1, то в канонических уравнениях будет отсутствовать.

Пример 10. Найти канонические уравнения ограничено-детерминированой функции заданной следующей диаграммой Мура:

Ясно, что вес данной функции равен 3. Построим каноническую таблицу для данной функции:

X(t)	Q(t-1)	Y(t)	Q(t)
0 0 0 1 1 1	0 1 2 0 1 2	0 1 0 0 0 0	1 1 2 2 1 2

Данная таблица не является таблицей истинности. Преобразуем данную таблицу в таблицу истинности. Для этого значения второго и четвёртого столбца закодируем в двоичной системе счисления:

X(t)			Y(t)
0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1	0 1 0	0 0 1	1 1 0
Не определена
0 0 0	1 0 1	0 1 0
Не определена

Доопределим данную функцию следующим образом:

X(t)			Y(t)
0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1	0 1 0 1 0 0 0 1	0 0 1 1 1 0 1 1	1 1 0 1 0 1 0 1

Составим канонические уравнения используя аппарат булевой алгебры:

Y(t)=

=

=

Итак, искомые канонические уравнения имеют вид:

Каждой ограниченно-детерминированной можно сопоставить канонические уравнения. Однако выбор канонических уравнений не однозначен. Эта неоднозначность связана:

1) с различными способами кодирования состояний.

2) с различными способами доопределения функций.

Очевидно, что канонические уравнения позволяют вычислить

По входной последовательности A={A(1),A(2),…,A(t),…}

Выходную последовательность B={B(1),B(2),…,B(t),…}.

Итак, для задания конечного автомата фиксируется три конечных множества (алфавита):

– множество возможных входных сигналов

– множество возможных выходных сигналов

– множество возможных внутренних состояний автомата

На этих множествах задаются две детерминированные функции

– функцию переходов Ψ, определяющую состояние автомата Q(t) дискретного времени t в зависимости от состояния автомата Q(t-1) и значения входного сигнала в момент времени t.

Q(t)= Ψ(X(t),Q(t-1))

– функцию выходов Ф, определяющую зависимость выходного сигнала автомата y(t) от состояния автомата Q(t-1) и входного сигнала X(t) в момент времени t.

Y(t)=Ф(X(t),Q(t-1))

Кроме того на множестве состояний автомата фиксируется одно из внутренних состояний Q(0) в качестве начального состояния.

Вопросы для самоконтроля

1. Дайте определение детерминированной функции.

2. Приведите примеры детерминированных функций.

3. Приведите примеры недетерминированных функций.

4. Приведите графическую интерпретацию детерминированных функций.

5. Что такое бесконечное нагруженное дерево?

6. Что такое вес бесконечно нагруженного дерева?

7. Какие функции называются ограниченно детерминированными?

8. Приведите примеры ограниченно детерминированных функций.

9. Приведите примеры неограниченно детерминированных функций.

10. Что такое диаграмма Мура?

11. Дайте определение канонических уравнений ограниченно детерминированных функций.

< Предыдущая		Следующая >

Возьмем нагруженное
дерево для некоторой детерминированной
функции
.
Пусть– произвольная его вершина-го
яруса. Данную вершину можно рассматривать
как корень нагруженного дерева. Согласно
теореме 1 оно определяет некоторую
детерминированную функцию.

Определение 2
Два поддерева с корнямииисходного дерева называются эквивалентными,
если.

Очевидно, что при
естественном наложении двух эквивалентных
поддеревьев их нумерации совпадают.
Так, в дереве (рис.3 и рис.4) все поддеревья
эквивалентны, а в дереве (рис.5) поддеревья
с корнями
эквивалентны, а с корнямиине эквивалентны.

Определение 3
Весом дерева и весом соответствующей
детерминированной функции называется
максимальное число попарно неэквивалентных
поддеревьев.

Например, все
функции из примеров 4, 5 равны 1, а из
примера 6 равны 2.

Определение 4
Детерминированная функцияназывается ограниченно – детерминированной
функцией, если она имеет конечный вес.

Класс всех
ограниченно –детерминированных
функций обозначим через

Функции из примеров
4, 5, 6 являются ограниченно-детерминирован-
ными функциями.

Рассмотрим следующую
детерминированную функцию.

Пример 7 .
Ясно, что вес данной функции,
т. е. она не является ограниченно-детерминированной.

Пусть
,
вес которой равенr.
Рассмотрим алфавит,
который назовём внутренним алфавитом.
Каждой вершине нагруженного дерева,
соответствующей функцииприпишем одну из букв алфавитас соблюдением следующего правила:
эквивалентным вершинам приписываются
одни и те же буквы из.
В результате получаем так называемое
полное нагруженное дерево.

Для любой ограниченно
– детерминированной функции соответствующее
ей полное нагруженное дерево можно
свести к конечному дереву с занумерованными
ребрами и вершинами. Если в нем провести
отождествление эквивалентных вершин,
то получим так называемую диаграмму
Мура. В ней нулём отмечена начальная
вершина и ребрам приписаны пары чисел
(a,b), первое
из которых обозначает номер ребра, а
второе, чем данное ребро нагружено. Так
функциясоответствует диаграмме Мура.

А функция

8.4 Каноническое уравнение ограниченно-детерминированных функций

Пусть
– ограниченно-детерминированная функция
с весомr.

Пусть
– входная последовательность. Ей
соответствует выходная последовательностьи последовательность состояний.

Возьмем другую
входную последовательность
.

Ей соответствуют,
выходная последовательность и
последовательность состояний

;

.

В общем случае из
того, что
не следует, что.
Однако, еслии,
тои.
Другими словами это означает, что если
два одноименных ребра ()
выходят из эквивалентных вершин (),
то они будут нагружены одной и той же
буквой ()
и будут входить в эквивалентные вершины
().
Это означает, что

(8.1)

Уравнения (8.1)
называются каноническими уравнениями
функции
.
Первое уравнение называется уравнением
выход, второе уравнением перехода.

Уравнения (8.1) можно
задать с помощью канонической таблицы.

x(t)	q(t-1)	y(t)	q(t)

Пусть x(t)
иy(t) из
{0,1}, а.
Если весr≤ 2, то каноническая
таблица есть таблица истинности. Еслиr> 2, то каноническая
таблица не является таблицей истинности.
Но с помощью кодирования всех чисел
алфавитав двоичной системе счисления мы её
можем преобразовать в таблицу истинности.

Рассмотрим теперь
функцию от nпеременныхс весомr> 1,– внутренний алфавит. Закодируем все
числа из алфавитав двоичной системе счисления наборами
из {0,1} длинной.
В этом случае канонические уравнения
искомой функции имеют вид:

(8.2)

В дальнейшем
договоримся, что начальные состояния
в канонических уравнениях (8.2) q(0)
= 0, а в уравнениях (8.1).

Пример 8 Найти
канонические уравнения функции

Ранее мы показали,
что вес данных функций равен 2 и её
диаграмма Мура

Построим каноническую
таблицу.

x(t)	y(t)	q(t-1)	z(t)	q(t)
0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1	0 1 1 0 1 0 0 1	0 0 0 1 0 1 1 1

Данная каноническая
таблица является таблицей истинности.

Запишем
канонические уравнения, используя
результаты темы 3.

Используя законы
алгебры логики:

Пример 9 Найти
каноническое уравнение для функции
заданной следующей диаграммой Мура

Строим каноническую
таблицу.

x(t)	y(t)	q(t-1)	z(t)	q(t)
0 0 1 1	0 1 0 1	0 0 0 0	0 1 1 0	0 0 0 0

Отсюда

Заметим, что если
вес функции равен 1, то в канонических
уравнениях
будет отсутствовать.

Пример 10 Найти
канонические уравнения
ограниченно-детерминиро-ванной функции,
заданной следующей диаграммой Мура:

Ясно, что вес данной
функции равен 3. Построим каноническую
таблицу для данной функции:

x(t)	q(t-1)	y(t)	q(t)
0 0 0 1 1 1	0 1 2 0 1 2	0 1 0 0 0 0	1 1 2 2 1 2

Данная таблица не
является таблицей истинности. Преобразуем
данную таблицу в таблицу истинности.
Для этого значения второго и четвёртого
столбца закодируем в двоичной системе
счисления:

x(t)			y(t)
0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1	0 1 0	0 0 1	1 1 0
Не определена
0 0 0	1 0 1	0 1 0
Не определена

Доопределим данную
функцию следующим образом:

x(t)			y(t)
0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1	0 1 0 1 0 0 0 1	0 0 1 1 1 0 1 1	1 1 0 1 0 1 0 1

Составим канонические
уравнения, используя аппарат булевой
алгебры:

1) y(t)=

=

=;

;

Итак, искомые
канонические уравнения имеют вид:

Каждой
ограниченно-детерминированной функции
можно сопоставить канонические уравнения.
Однако выбор канонических уравнений
не однозначен. Эта неоднозначность
связана:

1) с различными
способами кодирования состояний;

2) с различными
способами доопределения функций.

Очевидно, что
канонические уравнения позволяют
вычислить

по
входной последовательности
a={a(1),a(2),…,a(t),…}

выходную
последовательность b={b(1),b(2),…,b(t),…}.

Итак, для задания
конечного автомата фиксируется три
конечных множества (алфавита):

– множество
возможных входных сигналов
;

– множество
возможных выходных сигналов
;

– множество
возможных внутренних состояний автомата
.

На этих множествах
задаются две детерминированные функции:

– функция переходов
Ψ, определяющая состояние автоматаq(t)дискретного времениtв зависимости от состояния автоматаq(t-1)и значения входного сигнала в момент
времениt: q(t)=
Ψ(x(t),q(t-1));

– функция выходов
Ф, определяющая зависимость выходного
сигнала автоматаy(t)от состояния автоматаq(t-1)и входного сигналаx(t)в момент времениt:
y(t)=Ф(x(t),q(t-1)).

Кроме того, на
множестве состояний автомата фиксируется
одно из внутренних состояний q(0)в качестве начального состояния.

Вопросы для
самоконтроля

1 Дайте определение
детерминированной функции.

2 Приведите примеры
детерминированных функций.

3 Приведите примеры
недетерминированных функций.

4 Приведите
графическую интерпретацию детерминированных
функций.

5 Что такое
бесконечное нагруженное дерево?

6 Что такое вес
бесконечно нагруженного дерева?

7 Какие функции
называются ограниченно-детерминированными?

8 Приведите примеры
ограниченно-детерминированных функций.

9 Приведите примеры
неограниченно-детерминированных
функций.

10 Что такое диаграмма
Мура?

11 Дайте определение
канонических уравнений ограниченно-детерми-

нированных функций.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Используя метод сведения к заведомо полным системам, доказать полноту в 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 соответственно:Рис.