Нахождение, оценка и сравнение числа бесповторных булевых функций в различных базисах
Диссертация
В связи с тем, что булевы функции являются признанной моделью для проектирования схем, применяемых в электронике, сформировалось направление исследований, связанное с нахождением для булевых функций представлений, имеющих наименьшую сложность. Даже для простых базисных множеств точное решение этой задачи связано с почти полным перебором. В связи с быстрым ростом числа булевых функций при… Читать ещё >
Содержание
- Глава I. Основные понятия и результаты
- 1. Основные понятия и терминология
- 2. Обзор результатов по бесповторным булевым функциям
- Глава II. Количество бесповторных булевых функций в бинарных базисах
- 3. Нерекуррентная формула для числа бесповторных булевых функций в элементарном базисе
- 4. Связь между числом бесповторных функций в элементарном базисе и числами Эйлера второго порядка
- 5. Оценки числа бесповторных булевых функций в элементарном базисе
- 6. Нерекуррентная формула для числа бесповторных булевых функций в линейном бинарном базисе
- 7. Оценки числа бесповторных булевых функций в линейном бинарном базисе".'.-.-.,
- 8. Сравнение числа бесповторных булевых функций в бинарных базисах
- Глава III. Количество бесповторных булевых функций в произвольных базисах
- 9. Рекуррентная формула для числа бесповторных булевых функций в Нелинейном базисе
- 10. Рекуррентная формула для числа бесповторных булевых функций в линейном базисе
- 11. Количество бесповторных булевых функций в предэлементарных базисах
- 12. Сравнение числа бесповторных булевых функций в различных базисах
Список литературы
- Дискретная математика и математические вопросы кибернетики. Под редакцией Яблонского С. В. и Лупанова О. Б. М.: Наука, 1974. — Т 1. — 312 с.
- Андреев А. Е. Об одном методе получения более чем квадратичных эффективных нижних оценок сложности 7г-схем // Вестн. МГУ. Сер. 1. Матем.Мех. 1987. — N 1. — С. 70 — 73.
- Артюхов В. Л., Копейкин Г. А., Шалыто А. А. Настраиваемые модули для управляющих логических устройств. -Ленинград: Энер-гоиздат, 1981. 166 с.
- Винокуров С. Ф., Манцивода Ю. В., Перязев Н. А. Минимизация булевых функций в классах нормальных форм методом разложения // Фундаментальные проблемы математики и механики. Матматика. М.: Изд-во Московского ун-та, 1994. — С. 316 — 317.
- Винокуров С. Ф., Гайдуков А. И., Корсуков А. В. Библиотека классов булевых функций // Сб. тр. Иркутского университета. Иркутск, 1995. -Т. 3. — С. 228 — 229.
- Гершкович Ю. Б., Полтерович В. М. О бесповторных суперпозициях функций алгебры логики от двух переменных / / Автоматика и телемех. 1966. — С. 71 — 79.
- Глушков В. И. Введение в кибернетику. Киев: Изд-во АН УССР, 1964. — 324 с.
- Глушков Р. М., Капитонова Ю. В., Мищенко А. Т. Логическое проектирование дискретных устройств. Киев: Наукова думка, 1987. -264 с.
- Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики: Пер. с англ. М.: Мир, 1998. -703 с.
- Гурвич В. А. О бесповторных булевых функциях // Успехи матем. наук. 1977. — 32, N 1. — С. 183 — 184.
- Гурвич В. А. Критерий бесповторности функций алгебры логики // ДАН СССР. 1991. — 318, N 3. — С. 532 — 537.
- Казаков В. Д. О скобочных минимальных выражениях булевых функций // Duexieme Congres Mathematique Hongrois, Budapest.- 1961. V. 2.
- Кириченко К. Д. О критериях бесповторности булевых функций в различных базисах // Оптимизация, управление, интеллект.- 2000, N 4. С. 93 — 101.
- Кириченко К. Д. Критерий бесповторности функции алгебры логики в бинарном базисе // Международная конференция «Логика и приложения». Новосибирск. — 2000. — 57 — 58.
- Кузнецов А.В. О бесповторных контактных схемах и бесповторных суперпозициях функций алгебры логики // Труды МИ АН СССР. Т.51.— М.: Из-во АН СССР. 1958. С.186−225.
- Лупанов О. Б. О сложности реализаций функций алгебры логики формулами // Проблемы кибернетики. Вып. 3. гиз, 1963. С. 61 80.
- Лупанов О. Б. Асимптотическая оценка сложности управляющих систем. М.: Изд-во МГУ, 1984. — 137 с.
- Манцивода (Перязева) Ю. В. Минимизация булевых функций в классе бинарных формул // Международная Сибирская конференция по исследованию операций. Новосибирск. -1998. — С. 131.
- Манцивода (Перязева) Ю. В. Минимизация представлений булевых функций термами // Труды Восточно Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в ВУЗе. — Иркутск, 1999. — С. 167 — 170.
- Манцивода (Перязева) Ю. В. Алгоритм линейной минимизации булевых функций и его программная реализация. Иркутский университет. Серия: Дискретная математика и информатика. Вып. 9. — Иркутск, 1999. — 25 с.
- Нигматуллин Р. Г. Сложность булевых функций. М.: Наука, 1991. — 240 с.
- Перязев Н. А. Представление функций алгебры логики бесповторными формулами // Тезисы сообщений на XI Межреспубликанской конференции по математической логике. Казань. — 1992.- С. 110.
- Перязев Н. А. Реализация булевых функций бесповторными формулами // Фундаментальные проблемы математики и механики. Математика. М.: Изд-во Моск. ун-та, 1994. — С. 320.
- Перязев П. А. Реализация булевых функций бесповторными формулами в некоторых базисах // Сб. Алгебра, логика и приложения. Иркутск, 1994. — С. 143 — 154.
- Перязев Н. А. Реализация булевых функций бесповторными формулами // Дискретная математика. 1995. — Т. 7, N 3. — С. 61 — 68.
- Перязев Н. А. Сложность представлений булевых функций формулами в немонолинейных базисах // Иркутский университет. Серия: Дискретная математика и информатика. Вып. 2. — Иркутск, 1999. — 15 с.
- Перязев Н. А., Разгильдеев В. Т. Число бесповторных булевых функций в бинарных базисах // Тезисы докладов на XI Международной конференции по проблемам теоретической кибернетики.- Ульяновск. 1996. — С. 161 — 162.
- Перязев Н. А. Основы теории булевых функций. М.: Физматлит, 1999. — 112 с.
- Риордан Дж. Введение в комбинаторный анализ. М.: ИЛ, 1963.- 287 с.
- Стеценко В.А. О предплохих базисах в // Математические вопросы кибернетики. 4(1992), С. 139 — 177.
- Субботовская Б. А. О реализации линейных функций формулами в базисе V, // ДАН СССР. — 1961. — Т. 136, N 3. — С. 553 — 555.
- Субботовская Б. А. О сравнении базисов при реализации функций алгебры логики формулами // ДАН СССР. 1963. — Т.149, N 4.- С. 784 787.
- Храпченко В. М. О сложности реализации линейной функции в классе П-схем // Математические заметки. -1971. Т. 9, N 1. — С. 35 — 40.
- Храпченко В. М. О сложности реализации симметрических функций формулами // Математические заметки. -1972. Т. 11., N 1.- С. 109 120.
- Черухин Д. Ю. Алгоритмический критерий сравнения булевых базисов // Математические вопросы кибернетики, вып. 8 М.: Наука. Физматлит, 1999. — С. 77 — 122.
- Шеннон К. Э. Работы по теории информации и кибернетике. М.: ИЛ., 1963. — 829 с.
- Яблонский С. В. О суперпозициях функций алгебры логики // Математичесий сборник. 1952. — Т. 30, N 2. — С. 329 — 345.
- Яблонский С. В. Об алгоритмических трудностях синтеза минимальных контактных схем // Проблемы кибернетики. Вып. 2.- М.: Физматгиз, 1959. С. 75 — 122.
- Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986. — 384 с.
- Abhyankar S. Absolute minimal expressions of Boolean function.- «IRE Tr. on EC.». 1959. — V. EC-8, No 1.
- Fischer M., Meyer A. R., Paterson M. S. Lower bounds on the size of Boolean formulas, preliminary report // Proc. 7th Annual ACM Symposium on Theory of Computing, Albuquerque. 1975. — P.37 44.
- Fischer M., Meyer A. R., Paterson M. S. Q (nlogn) lower bounds on length of Boolean formulas // SIAM J. Comput. 1962. -V. 11, No 3. — P. 416 — 427.
- Gessel I., Stanley R. P. Stirling polinomials // Journal of Combinatorial Theory. series A. — 1978. — P. 24 — 33.
- Ginsburg J. Note on Stirling’s numbers // American Mathematical Monthly. 1928. — P. 77 — 80.
- Hodes L., Specker E. Lengths of formulas and elimination of quantifiers // Contributions to mathematical logic. Amsterdam.- 1968. P. 175 — 188.
- Post E. L. Introduction to a general theory of elementary propositions // Amer. J. Math. 1921. — V. 43, No 4. — P. 163 — 185.
- Post E. L. Two-valued iterative systema of mathematical logic // Annals of Math. Studies. 1941. — No 5.
- Shannon С. E. A symbolic analysis of relay and switching circuits // Trans.AIEE. 1938. -V. 57. — P. 713 — 723.
- Shannon С. E. The synthesis of two-terminal switching circuits // Bell.System. Techn. J. 1949. — V. 28. — P. 59 — 98.
- Stetsenco V. On almost bad Boolean bases // Theoretical Computer Science. 136. 1994. — P. 419 — 469.
- Работы автора по теме диссертации
- Зубков О. В. Количество бесповторных булевых функций в приведенных базисах // Конф. «Студент и научно-технический прогресс. Молодые ученые к 80-летию ИГУ», тезисы докладов. Иркутск, ИГУ. — 1998. — С 45.
- Зубков О. В. Число бесповторных булевых функций // Третий Сибирский Конгресс по прикладной и индустриальной математике. Сибирская конференция по исследованию операций. Новосибирск. — 1998. — С 126.
- Зубков О.В. Формулы для нахождения числа бесповторных булевых функций в различных базисах // Проблемы теоретической кибернетики. Тезисы докладов XII Международной конференции. Нижний Новгород. — 1999. Часть I, — С 83.
- Зубков О.В. Число бесповторных функций алгебры логики в некоторых базисах // Материалы международной конференции по математической логике. Новосибирск. — 1999. — С. 24−25.
- Зубков О. В. Рекуррентные формулы для нахождения количества бесповторных булевых функций в различных базисах // Синтез и сложность управляющих систем. Материалы XII международной школы-семинара. М.: Изд-во МГУ, 2001. Т 1. — С. 93 — 99.
- B. И. Пантелеев, Н. А. Перязев, Ю. В. Перязева- Под ред.
- C.Ф. Винокурова и Н. А. Перязева. М.: Физматлит, 2001. — 192 с.
- Зубков О. В. Оценки числа бесповторных булевых функций в бинарных базисах // Иркутский университет. Серия: Дискретная математика и информатика. Вып. 15. Иркутск, 2002. — 36 с.