RUS  ENG
Полная версия
ЖУРНАЛЫ // Математические заметки // Архив

Матем. заметки, 2012, том 92, выпуск 2, страницы 181–191 (Mi mzm7833)

Эта публикация цитируется в 1 статье

Реализация булевых функций формулами в непрерывных базисах, содержащих континуум констант

Я. В. Вегнер, С. Б. Гашков

Московский государственный университет им. М. В. Ломоносова

Аннотация: Показано, как для произвольной булевой функции $n$ переменных построить формулы сложности $O(2^{n/2})$ в базисах
$$ \{x-y,xy,|x|\} \cup [0,1],\qquad \{x-y,x*y,2x,|x|\} \cup [0,1], $$
где ${x*y=\max(-1,\min(1,x))\max(-1,\min(1,y))}$. Данные оценки, вообще говоря, по порядку неулучшаемы.
Библиография: 3 названия.

УДК: 512.563

Поступило: 26.04.2009
Исправленный вариант: 19.12.2010

DOI: 10.4213/mzm7833


 Англоязычная версия: Mathematical Notes, 2012, 92:2, 166–175

Реферативные базы данных:


© МИАН, 2024