Оценки немонотонной сложности логических схем

С. 48–52.

Михайлович А. В., Кочергин В. В.

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

Ключевые слова: функции многозначной логики, multi-valued logic functions, схемная сложность, inversion complexity, Markov's theorem, инверсионная сложность, теорема Маркова, nonmonotone complexity, немонотонная сложность, схемы из функциональных элементов, circuit complexity

В книге

Материалы 5-й Российской школы-семинара "Синтаксис и семантика логических систем"

Улан-Удэ: Издательство Бурятского госуниверситета, 2017.