This paper shows that synthesizing binary decision programs (formed by means of decision instructions of the type if then else and of execution instructions of the type do) and proving theorems can be carried out by using the same approach. It is proved that the same transformations acting on P-functions can be interpreted in terms of binary program synthesis and of theorem proving. Since binary program leads to algorithmic state machine design while theorem proving leads to declarative programming, this allows us to lay a bridge between logic design and declarative languages such as Prolog.

A formalism has been introduced for program description and synthesis, namely the matrix description of instructions. In this paper we put that formalism to work by associating with it computation methods based on a generalized P-function concept. Algorithms are derived for the optimal implementation of programs in asynchronously organized structures.

We show that well-known instructions such as if then else, fork, join, while do, can be represented as row matrices or column-matrices. We define a matrix-instruction which encompasses and generalizes the above instructions. This instruction provides us with a compact tool for describing algorithms and for synthesizing them in synchronous and asynchronous structures. We show, e.g., that the synthesis of a program by means of elementary instructions reduces to the factorization of a matrix into elementary matrices. A formalism and a computation method are introduced which generalize the author's previous work on the subject.

A program is defined as an indexed sequence of instructions; each of these instructions is formed by an interconnection of branching (or conditional) instructions (of the form if, then, else) followed by an interconnection of execution instructions (of the form do). A program is an efficient tool, allowing the digital system designer to describe the microprograms of discrete systems and to synthesize their control automaton. This paper deals with a method of transformation and of optimization of programs. The presented algorithm obtains, for any given program, an equivalent one with a minimum number of conditional vertices.

Considers the realization of switching functions by programs composed of certain conditional transfers (binary programs). Methods exist for optimizing binary trees, i.e. binary programs without reconvergent instructions. This paper studies methods for optimizing binary simple programs (programs with possible reconvergent instructions, but where a variable may be tested only once during a computation) and binary programs. The hardware implementations of these programs involve either multiplexers or demultiplexers and OR-gates.

The theoretical concepts of meet and join derivatives and extended vector of Boolean functions are defined. These concepts give rise to new methods (using the Kronecker matrix product) for prime implicant and prime implicate extraction. An extensive comparison between meet and join derivatives and the consensus theory is made.

The total and local unateness of discrete and of switching functions are studied from a theoretical point of view. One shows that the local unateness leads to the concept of hazard-free transition for a discrete function. Unate covers for discrete functions are defined: they are either the smallest unate functions larger than a discrete function, or the largest unate functions smaller than a discrete function. These concepts play a key role in hazard-free design of multiple-valued networks. Three-level types of multiple-valued networks using MIN and MAX gates are presented. These networks improve, from a hazard point of view the well known two-level networks presented by Eichel-berger in the frame of switching theory.

After a brief outline of classical concepts relative to Boolean differential calculus, a theoretical study of the main differential operators is undertaken. Algebraic equations relating the classical concepts of prime implicants and of the discrete Fourier transform of a Boolean function to the differential operators are derived. Application of these concepts to several important problems arising in switching practice is mentioned.