Рассматриваются 1-самокорректирующиеся схемы из функциональных элементов в базисе Б = {&, V, —}, каждая из которых реализует одну и ту же булеву функцию как в исправном состоянии, так и при переходе в неисправное состояние любого одного ненадежного элемента. Каждый надежный элемент имеет вес Р и всегда реализует одну и ту же приписанную ему функцию из Б. Каждый ненадежный элемент имеет вес 1 и реализует в исправном состоянии некоторую приписанную ему функцию из Б, в неисправном состоянии — булеву константу δ. Пусть L(f) — наименьшая из сложностей 1-самокорректирующихся схем, реализующих булеву функцию f; под сложностью схемы понимается сумма весов элементов этой схемы. Для булевой функции s_n(x, y) = (¬x₁\/у₁)&…&(¬x_n\/у_n) при n≥2, Р ≥3 и δ ϵ{0, 1} показано, что L(s_n(x, y)) = 6n+P-2.

функциональные элементы, самокорректирующиеся схемы, сложность

Математические вопросы и теория численных методов