Оценки числовых параметров в ДНФ случайных частичных булевых функций

Авторы: 
Журнал: 
Страница: 
21
УДК: 
519.766, 519.768
Ряд задач распознавания образов сводится к построению тупиковых, сокращенных или минимальных ДНФ частичных булевых функций. Информация о метрических свойствах таких функций может значительно ускорить поиск оптимальных решений. Работа посвящена оценкам числовых параметров частичных булевых функций, принимающих значения 0 и 1 с вероятностью p и q соответственно. Для таких функций получены нижние и верхние оценки кратчайших ДНФ, вывод которых приводится в данной статье.
info_eng: 
A number of Pattern Recognition problems can be reduced to the construction of prime, irredundant,  or shortest disjunctive normal forms for partial Boolean functions. Knowledge of considered function metrical properties can facilitate finding optimal decision. The paper is devoted to numerical parameter cstimates of partial Boolcan functions taking values 0 and 1 with probabilitics p и q  correspondingly. The lower and upper bounds on the length of the shortest DNF representation of such functions are obtaned in the paper.