§ 10.11. О пороговой реализуемости логических функции

Логическая, или булева, функция

                                                                          (10.43)

которую кратко будем записывать как

                                                                                     (10.44)

характеризуется тем, что сама она и ее независимые переменные принимают только два значения, 0 или 1. Легко видеть, что булева функция (10.43) полностью определяется таблицей с числом строк, равным  . Поскольку входные и выходные переменные порогового элемента также принимают значения 0 или 1, то возникает вопрос о возможности реализации булевой функции на одном пороговом элементе или, короче, вопрос о пороговой реализуемости булевой функции.

Предположим, что

                                            (10.45)

Очевидно, что для порогового элемента должны выполняться неравенства

                                                                          (10.46)

Воспользуемся теперь тем свойством порогового элемента, что при выборе

                                                                         (10.47)

инверсия координат входного сигнала (т. е. замена нулевых координат единичными и наоборот) вызывает инверсию выходного сигнала. Тогда из (10.46) получаем

                                                                (10.48)

где  означает инверсию . Эту систему неравенств можно представить в более компактной форме

                                                                       (10.49)

где

                                                                                       

Из изложенного выше заключаем, что необходимым и достаточным условием пороговой реализуемости булевой функции (10.43) является существование такого вектора , который бы удовлетворял системе неравенств (10.49).