EN|RU

Том 19, номер 5, 2012 г., Стр. 35-46

УДК 519.7
Золотых Н. Ю., Чирков А. Ю.  
О верхней оценке мощности минимального разрешающего множества пороговой функции

Аннотация:
Предлагается новое необходимое и достаточное условие принадлежности точки минимальному разрешающему множеству пороговой функции $k$-значной логики. Это позволяет выделить большой подкласс пороговых функций, для которых мощность минимального разрешающего множества при фиксированном числе переменных $n$ ограничена сверху полиномом от $\log_2k$ степени $n-2$.
Ил. 1, библиогр. 17.

Ключевые слова: пороговая функция, разрешающее множество, свойство разделённости.

Золотых Николай Юрьевич 1
Чирков Александр Юрьевич 1

1. Нижегородский гос. университет им. Н. И. Лобачевского,
пр-т Гагарина, 23, корп. 2, 603950 Н. Новгород, Россия
е-mail: zolotykh@vmk.unn.ru, chirkov@vmk.unn.ru

Статья поступила 23 октября 2011 г.
Исправленный вариант — 23 марта 2012 г.

 © Институт математики им. С. Л. Соболева, 2015