Частично-рекурсивные и вычислимые функции

Алгебра логики.

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

2. Всегда ли длина минимальной днф минимальна.

3. Если Частично-рекурсивные и вычислимые функциисложность минимальной ДНФ функции Частично-рекурсивные и вычислимые функции , то найти Частично-рекурсивные и вычислимые функции .

4. Может ли быть в полиноме Жегалкина несущественная переменная?

5. Существует ли функция, принадлежащая одному из пяти предполных классов в Частично-рекурсивные и вычислимые функции и не принадлежащая остальным?

6. Сколько минимальных ДНФ у линейных и монотонных функций?

7. Известно, что Частично-рекурсивные и вычислимые функции . Вопрос: полно ли Частично-рекурсивные и вычислимые функции ?

8. Пример ДНФ, являющейся кратчайшей, но не минимальной.

9. Привести пример функций, на которых доказывается не локальность ДНФ Частично-рекурсивные и вычислимые функции .

10. Как строить минимальную ДНФ для монотонной функции?

11. Критерий полноты в классе монотонных функций в Частично-рекурсивные и вычислимые функции . Найти классы, предполные в Частично-рекурсивные и вычислимые функции , базис.

12. Пересечение всех замкнутых классов в Частично-рекурсивные и вычислимые функции .

13. Пересечение всех предполных классов в Частично-рекурсивные и вычислимые функции .

14. Построить конечную полную систему тождеств для Частично-рекурсивные и вычислимые функции над базисом Частично-рекурсивные и вычислимые функции (функция голосования).

15. Доказать, что Частично-рекурсивные и вычислимые функции .

16. Конъюктивная нормальная форма. Поможет ли в поиске минимальной КНФ знание минимальной ДНФ для конкретной функции?

17. Критерии полноты в предполных классах.

18. Как связаны монотонные и антимонотонные функции? Замкнуты ли антимонотонные функции?

19. Когда сокращённая и совершенная ДНФ монотонной функции совпадают?

20. Пусть Частично-рекурсивные и вычислимые функции -д.н.ф., Частично-рекурсивные и вычислимые функции -д.н.ф., полученная из Частично-рекурсивные и вычислимые функции . Как связаны Частично-рекурсивные и вычислимые функции и Частично-рекурсивные и вычислимые функции , где Частично-рекурсивные и вычислимые функции -сложность д.н.ф.

21. Для функции f(x1,…,xn) известны все её минимальные ДНФ. Описать минимальные ДНФ для функции f( Частично-рекурсивные и вычислимые функции ,…, Частично-рекурсивные и вычислимые функции ).

Многозначная логика.

1. Конечно ли число предполных классов в Частично-рекурсивные и вычислимые функции ?

2. Оценить (как-нибудь) число предполных классов в Частично-рекурсивные и вычислимые функции .

3. Вычислить пересечение всех предполных классов в Частично-рекурсивные и вычислимые функции .

4. Полна ли в Частично-рекурсивные и вычислимые функции система функций Частично-рекурсивные и вычислимые функции ?

5. Частично-рекурсивные и вычислимые функцииШеферова в Частично-рекурсивные и вычислимые функции , Частично-рекурсивные и вычислимые функции ?

6. Возможно ли равенство: Частично-рекурсивные и вычислимые функции ?

7. Частично-рекурсивные и вычислимые функции . Когда Частично-рекурсивные и вычислимые функции ?

8. Будет ли полна в Частично-рекурсивные и вычислимые функции система, состоящая из одной функции, если ее замыкание содержит все одноместные функции?

9. Верно ли утверждение, что система, содержащая все одноместные функции, принимающие не более k-2 значения и существенную функцию, полна?

10. Выразить Частично-рекурсивные и вычислимые функции через систему функций Частично-рекурсивные и вычислимые функции .

11. В любом ли Частично-рекурсивные и вычислимые функции имеются нелинейные функции?

12. Частично-рекурсивные и вычислимые функциипредполно в Частично-рекурсивные и вычислимые функции . Описать Частично-рекурсивные и вычислимые функции . ( Частично-рекурсивные и вычислимые функциимножество перестановок).

13. Частично-рекурсивные и вычислимые функции — множество всех одноместных функций, принимающих не более k-1 значения. Верно ли утверждение, что Частично-рекурсивные и вычислимые функции полно тогда и только тогда, когда S содержит существенную функцию.

14. Частично-рекурсивные и вычислимые функции предполный класс в Частично-рекурсивные и вычислимые функции или нет?

15. Дано Частично-рекурсивные и вычислимые функции и Частично-рекурсивные и вычислимые функции . Найти все такие M.

16. Дано Частично-рекурсивные и вычислимые функции . Какие могут быть M и N?

17. Существуют ли в Частично-рекурсивные и вычислимые функции замкнутые классы с бесконечным базисом?

18. Полна ли система Частично-рекурсивные и вычислимые функции в Частично-рекурсивные и вычислимые функции ?

19. При каких k в Частично-рекурсивные и вычислимые функции любую функцию можно представить полиномом по модулю k?

20. Каковы ширина и глубина решётки замкнутых классов в Рк?

21. М0 – класс в Рк сохраняющий 0. Показать, что М0 предполный.

22.Частично-рекурсивные и вычислимые функции — множество всех функций изЧастично-рекурсивные и вычислимые функции , принимающих не более k-2 значений. Полна ли системаЧастично-рекурсивные и вычислимые функции Частично-рекурсивные и вычислимые функции {f}, где f – существенная функция? (k=3 и k=4).

23. Если класс H конечнопорождённый в Рк, то всегда ли найдётся в нём предполный класс?

24. Пусть Частично-рекурсивные и вычислимые функции – класс всех полиномов по mod k. Верно ли утверждение Частично-рекурсивные и вычислимые функции РкЧастично-рекурсивные и вычислимые функции: Частично-рекурсивные и вычислимые функции Рк (x) Частично-рекурсивные и вычислимые функции: Частично-рекурсивные и вычислимые функции ?

Частично-рекурсивные и вычислимые функции.

1. Пример не всюду определенной частично-рекурсивной функции.

2. Вычислимость функции, растущей быстрее любой вычислимой функции.

3. Пример невычислимой функции.

4. Понятие частично-рекурсивной функции.

5. Можно ли произвольную частично-рекурсивную функцию доопределить до общерекурсивной?

6. Пример невычислимой всюду определенной функции.

7. Может ли функция, принимающая 2 (n) значения, быть невычислимой?

8. Существует ли функция, растущая быстрее, чем любая одномерная вычислимая функция?

9. Сузится ли класс рекурсивных функций, если выбросить операцию примитивной рекурсии?

10. Понятие алгоритма.

11. Моделирование автомата машиной Тьюринга.

12. Существует ли алгоритм проверки однозначности декодирования, если отображение, задающее кодирование, задается алгоритмом?

13. Существует ли не всюду определенная примитивно-рекурсивная функция?

14. Существует ли универсальная общерекурсивная функция для класса общерекурсивных?

15. Показать, что усеченная разность является примитивно-рекурсивной.

Автоматы.

1. Примеры автоматов, на которых достигаются оценки Мура.

2. Понятие однородной структуры.

3. Число неизоморфных автоматов, имеющих два входа, два состояния и один выход.

4. Определение магазинного автомата.

5. Автоматы Мура, Медведева, Мили.

6. Написать канонические уравнения для автомата, заданного логической сетью и диаграммой Мура.

7. Полна ли в классе ограниченно-детерминированных функций система:

{штрих Шеффера, Частично-рекурсивные и вычислимые функции }?

8. Базис Частично-рекурсивные и вычислимые функции с какой сложностью может быть реализована автоматная схема с n входами, m выходами и p состояниями, если все элементы имеют сложность 1?

9. Сколько состояний у задержки. Написать канонические уравнения задержки.

10. Частично-рекурсивные и вычислимые функции — множество состояний автомата. Регулярно ли множество входных слов, заставляющих не более одного раза зайти в правую часть и вернуться?

11. Как связаны длины периодов входных и выходных слов автомата?

12. Привести пример универсальной однородной структуры.

13. Написать канонические уравнения для автомата:
Частично-рекурсивные и вычислимые функции

14. Существует ли полная система для автоматов вида:
а) Частично-рекурсивные и вычислимые функции и б) Частично-рекурсивные и вычислимые функции , где функция F из Р2.

15. Можно ли все автоматы Мура получить из автомата вида:
Частично-рекурсивные и вычислимые функции , где функция F из Р2.

16. Построить автомат, представляющий а(А Частично-рекурсивные и вычислимые функции ), где а:

Частично-рекурсивные и вычислимые функции

17. Автомат В обратный к автомату А, если Частично-рекурсивные и вычислимые функции есть тождественный автомат (входной и выходной алфавиты – {0,1}). Когда для А существует обратный?

18. А=В={0,1} – входной и выходной алфавиты автомата а. Можно ли распознать свойство а(А Частично-рекурсивные и вычислимые функции )= А Частично-рекурсивные и вычислимые функции ?

Случайные записи:

Лекция 3: Рекурсивные функции


Похожие статьи:

Добавьте постоянную ссылку в закладки. Вы можете следить за комментариями через RSS-ленту этой статьи.
Комментарии и трекбеки сейчас закрыты.