Mathematics /4. Applied Mathematics

Dr. Sci. (Phys.-Math), Prof. Alekhina M.A.,
Cand. Sci. (Phys.-Math), Docent Moiseev A.V.

Penza State Technological University,

The recurrent formula for unreliability of circuits
in the Rosser-Turkett basis (in )

Let , , and let be the set of all k-valued logic functions, i.e. functions of the type . Consider the realization of functions of the set by circuits of unreliable functional elements in the basis Rosser-Turkett (also denote and by and Ú respectively [1]).

We assume, that the circuit of unreliable elements realizes the function , if in the absence of faults in it for each input set the output value is equal .

Let the circuit realizes the function , and let be an arbitrary input set of the circuit , and . Denote by the probability of the value at the output of the circuit on the input set , and denote by the fault probability at the output of the circuit on the input set . Obviously, . (In expressions , ,..., the addition is performed .)

For example, if the input set of the circuit is such that, then the fault probability on this set is

The unreliability of the circuit , realizing the function , is called a number equal to the maximum fault probability at the output of the circuit . The reliability of the circuit is .

Elements of the circuit are supposed to be prone independently of each other inverse faults at the outputs with a probability , i.e. each basic element with his assigned function on any input set such, that , gives a value , with a probability . That’s why the fault probability at the output of every basic element is . Obviously, the unreliability of any basic element is also equal , and his reliability is .

Let be a function of , and let be an arbitrary circuit, realizing the function . Using we construct a new circuit, which will be used to improve the reliability of the original circuit . For this we take two copies of the circuit and connect their outputs with inputs of the basic element, realizing . The resulting circuit will be called a circuit . Further we take two copies of the circuit and connect their outputs with inputs of the basic element, realizing Ú. Denote the resulting circuit by . It’s easy to check, that the circuit realizes the same function .

A recurrence relation for the unreliability of circuits and is found in Theorem 1.

Theorem 1. Let be an arbitrary function of , be any circuit, realizing , and be the unreliability of the circuit . Then the circuit realizes the function with the unreliability , satisfying the inequality:
.

Proof. Let be an arbitrary function. Without loss of generality we can assume that the function depends on variables . Let be any circuit, realizing , and be an arbitrary set, . Denote by a fault probability at the output of the circuit (i.e. ) and define a fault probability at the output of the circuit on the same set, given that the unreliability of the subcircuit of three elements (two conjunctors and one disjunctor) no more than ,

Previously [2], it was proved inequality: .

Then . Hence,

Theorem 1 is proved.

Thus, the recurrent formula for the unreliability of original and constructed circuits is found in the Rosser-Turkett basis for all . Earlier, similar formulas are known only for k equal 3 [3] and 4 [2]. In the case this formula is precisely proposed formula, but the proof of the corresponding theorem is more cumbersome.

This work was supported by the Russian Foundation for Basic Research (project number 14-01-00273).

References

[1] S. V. Jablonski: Introduction to Discrete Mathematics, A textbook for higher education, ed. V. A. Sadovnichii, Moscow (in Russia), 2001.

[2] M. A. Alekhina, S. P. Kargin: Asymptotically optimal reliable circuits in the Rosser-Turkett basis in P₄, University proceedings. Volga region. Physical and mathematical sciences. 2015. N 1. P. 38–54.

[3] M. A. Alekhina, O. Yu. Barsukova: Estimates of unreliability of circuits in the Rosser-Turkett basis, University proceedings. Volga region. Physical and mathematical sciences. 2014. N 1. P. 5–19.