Quantum Approach to Informatics

CHAPTER 4

QUANTUM COMPUTING

4.1 LOGIC OPERATIONS

4.1.1 Classical Logic Operations

Classical logic can be introduced in several ways. In philosophical discourse one usually introduces the truth value of a proposition by utilizing a variable taking the two values false and true. In algebraic terms, the former is usually denoted by o and the latter by 1; this is obviously highly useful in representing digital information in binary form. In this context the variable is, of course, the standard bit of information.

Functions defined on the set of values {0, 1} are called logical functions, and the ensuing algebra is called a Boolean algebra. There are three basic logical functions, which have been given the names NOT, OR, and AND. The first one operates on a single input bit, whereas the other two operate on two input bits. They are denoted by

The functional dependence of the logical functions are represented in truth tables, which list the inputs to the left and the result of applying the function at the right. Thus we obtain

The truth functions defined by these tables also have a set-theoretic ...