ИСТИНА

Установлено, что при любом целом неотрицательном n любую булеву функцию f от n переменных можно реализовать в базисе Жегалкина неизбыточной схемой из функциональных элементов (СФЭ) с n входами и одним выходом, допускающей единичный проверяющий тест длины не более 16 относительно одиночных произвольных константных неисправностей на входах и выходах элементов. Утверждается также о существовании конечного полного базиса, в котором при любом целом неотрицательном n любую булеву функцию f от n переменных можно реализовать неизбыточной СФЭ с n входами и одним выходом, допускающей единичный проверяющий тест длины не более 6 относительно одиночных произвольных константных неисправностей на входах и выходах элементов. Установлена асимптотика вида 2n - 2 log n + O(1) функции Шеннона длины единичного проверяющего теста для СФЭ в базисе Жегалкина относительно одиночных произвольных константных неисправностей на входах и выходах элементов, а также на входах схемы. Доказано, что при добавлении двух дополнительных выходов при любом целом неотрицательном n любую булеву функцию f от n переменных можно реализовать в базисе Жегалкина неизбыточной СФЭ с n входами, допускающей единичный проверяющий тест длины не более 18 относительно одиночных произвольных константных неисправностей на входах и выходах элементов, а также на входах схемы.