§ 10.12. Критерий реализуемости

Нельзя ли по виду матрицы  определить пороговую реализуемость булевой функции ? Оказывается, можно. Для этого дополним каждый из векторов  и  координатами 1 и 0 и составим расширенную матрицу

                                                                 (10.50)

Эта расширенная матрица соответствует новому пороговому элементу, отличающемуся от прежнего наличием двух дополнительных входов, выбор весов которых  и  позволяет удовлетворить условию нормировки

                                                                            (10.51)

При этом, как следует из (10.47),

                                                                                 (10.52)

и условие (10.49) заменяется условием

                                                                                 (10.53)

Но построению матрица  такова, что существует вектор , обладающий тем свойством, что при ,

                                                                              (10.54)

Если теперь рассмотреть матрицу   как платежную матрицу некоторой игры, а векторы  и  как смешанные стратегии игроков, то условия (10.53), (10.54) будут выполнены, если цена игры  будет больше . Таким образом, мы приходим к следующей формулировке критерия реализуемости.

Для пороговой реализуемости булевой функции необходимо и достаточно, чтобы цена  игры, определяемой платежной матрицей . была больше .