Задача по дискретной математике

akv3986

задача 1
Доказать , что в системе (Р_од.2 ; С) имеется бесконечное число замкнутых классов
задача 2
Как выглядит диаграммы Мура для автоматных перестановок на множестве Е^w(_2)!
Пожалуйста помогите решить столь не сложные задачи, у меня что-то ничего не выходит.

Sibtog

фига себе несложные...

Alexx13

см. Кудрявцев В.Б. О мощностях множеств предполных множеств некоторых функциональных систем, связанных с автоматами.-В кн.: Проблемы кибернетики. Вып.13 М.: Наука,1965,с. 45-74
Теорема Кудрявцева. Мощность множества предполных в (P_од. k, C, O) классов равна континууму.
предполные классы замкнутые
(инфа из Яблонского)
п.с. занимаюсь умножением целых чисел

62408

А что, обратная связь O никак не повлияет?

62408

Посмотри ещё книгу В.Б. Кудрявцева "Введение в теорию автоматов" ("Красная книга" с. 166-167.

Alexx13

Alexx13

\\ А что, обратная связь O никак не повлияет?
самому интересно

CokpaT

помагите решить
Паможим чем сможим
где вы откопали эти задачи, скажите? Все-таки не каждый встречный считает классы од-функций... И от ... эээ... от того, откуда взялась задача м.б. зависит, наколько сложное надо придумывать решение И насколько легко спрашивающий осознает предложенные варианты решений
Кстати, уточните, что такое (Р_од.2 ; С)? Можно словами, что-то типа "ограниченно-детерм. функции с опер. суперпозиции и..... Что такое "2"?
И что понимается под "Как выглядит диаграммы Мура для автоматных перестановок на множестве Е^w(_2)!" Что такое "автоматные перестановки"? И что за множество е-дубльвэ-два?

CokpaT

Теорема Кудрявцева. Мощность множества предполных в (P_од. k, C, O) классов равна континууму.
По-моему, здесь это не нужно. Наверно надо просто построить континуальное семейство од-функций. Это же бесконечные последовательности, вот надо каждой бесконечной последовательности цифр сопоставить од-функцию. Должно быть наверное просто... я думаю...

CokpaT

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

akv3986

пояснения E^w(_2) я незнал как выразить но это обозначяет что у Е нижний индек 2 а верхний омега

akv3986

А задачи один препод дал очень нужно мне эти решения тут как говорится есть свой спортивный интерес решения просто я уже с этим парился 1.5 недели так же есть и не спортивный интерес связанный с учебой !

CokpaT

Ну, мущщины, хемуль, где вы там все?! Может, тряхнете стариной?
Я думаю, первая задача - нечто в таком духе.
Лемма: пусть А, B - конечные автоматы с числом состояний соответственно p и q. Рассмотрим автомат AB - их композицию. Тогда он будет иметь
либо p*q,
либо p*q', где q' <=q,
либо q*p', где p'<=p состояний. Сколько на самом деле - это надо еще подумать. Мне кажется, что одно из трех
Смысл в том, что при композиции мы будем получать автомат, у которого число состояний составное.
Тогда получается
Теорема: рассмотрим множество автоматов, у которых числа состояний - это простые числа. Тогда ни один из них нельзя получить композицией остальных.
Вот мы и получили счетную независимую систему автоматов. И она порождает континуум замкнутых классов (каждый класс - это некоторое подмножество функций системы, а множество всех подмножеств счетного множества - континуум).
Как-то типа того, я думаю.

akv3986

а по подробний нельзя?
а ту я не знаю как построить такие автоматы!

CokpaT

Новая мысль про первую задачу.
(кстати, автор, а вы вообще знаете, что такое од-функция или что такое замкнутый класс или ...? Просто насколько подробно мне надо писать... И, конечно, хорошо, чтобы кто-нибудь проверил идею, а то мало ли что я напишу )
Рассмотрим последовательность од-функций (или автоматов, что то же самое): A_1, A_2, ... A_n, ...
где для каждого номера i=1,2,... автомат A_i устроен следующим образом: он имеет i состояний и на любой входящей последовательности выдает последовательность 0000...0100000..01... то есть периодическую последовательность с периодом i, где первые i-1 нулей, потом одна единица, потом опять i-1 нуль, одна единица и т.д. И тогда если мы в A_i будем подставлять любые функции A_1, ..... то в результате все равно будет выдаваться та же последовательность, то есть получится та же функция A_i. Это значит, что ни одна из функций A_1, A_2, ... не выражается через остальные. А значит вот и континуум замкнутых классов: выбираем любое подмножество функций, замыкаем, вот и класс. Для разных подмножеств, так как функции друг через друга не выражаются, получаем разные классы. У счетного множества континуум подмножеств, следовательно мощность множества классов - континуум.

akv3986

Да я знаю что такое од фунуции и что такой замкнутый класс

akv3986

а как ты производишь замыкание?
И там не образуется новые функции?

CokpaT

Из множества A_1, ... выбираем любое подмножество и замыкаем его. Т.е. просто рассматриваем замкнутый класс, порожденный функциями из подмножества. Образуются или нет там новые функции - это нам вообще не важно. Самое главное - чтобы для разных подмножеств эти классы не совпадали. Но так как (если рассуждения в моем предыдущем тексте верные ) ни одна из функций A_1, A_2, ... не выражается через другие, то для разных подмножеств получим разные классы (для любой пары подмножеств найдется функция, которая принадлежит одному и не принадлежит другому. И через функции другого подмножества она не выражается.)
(на самом деле, если все верно, то при замыкании даже новых функций образовываться не будет: что бы мы не подставляли в функцию A_i, только ее и получим. Но это здесь не важно).

akv3986

В начале нужно же докозать, что A_i не возможно получить через другиее элементы этого множистав! А как это сделать?

CokpaT

В начале нужно же докозать, что A_i не возможно получить через другиее элементы этого множистав! А как это сделать?
Ну я написала... Возьмем A_k, подставим в него... все, что угодно. A_k у нас, по определению, устроен так, что что бы не подавалось на вход, на выходе выдается k-периодическая последовательность 00..0100..01 (k-1 нуль). Поэтому, подставляя что-то (что угодно) в A_k, мы получим только A_k. И A_i никак не получим.
М.б. я глючу, так что если непонятно, спрашивай, найдем ошибку

akv3986

ПЛИЗ вторую тоже помогите решить!

akv3986

это множества все 2-значных последовательностей g ,где g={g(1g(2...,g(m...} , g(i) принодлежит E^k для всех i (i=1,2,...)
Как теперь понятно? Это пояснение обозначения E^w(_2)

CokpaT

тогда уж не E^k, а E^2, раз двузначных...
Так, а что делают перестановки? Что куда переставляется, на каких множествах они действуют?

Genmaximus

Первая задача - прям в книжке есть "Введение в теорию автоматов".

Genmaximus

А что за множество Е^w(_2)! ?
Оставить комментарий
Имя или ник:
Комментарий: