On implementation of some systems of elementary conjunctions in the class of separating contact circuits
Elena Gennad'evna Krasulina · Discrete Mathematics and Applications · 2023
Abstract We show that the system of elementary conjunctions Ω n , 2 k = K 0 , … , K 2 k − 1 $ \Omega_{n,2^k} = {K_0,\ldots,K_{2^{k} -1}} $ such that each conjunction depends essentially on n variables and corresponds to some codeword of a linear ( n , k )-code can be implemented by a separating contact circuit of complexity at most 2 k +1 +4 k ( n − k ) − 2. We also show that if a contact (1, 2 k )-terminal network is separating and implements the system of elementary conjunctions Ω n , 2 k $ \Omega_{n,2^k} $ , then the number of contacts in it is at least 2 k +1 − 2.