Minimizing Logical Functions, On the Need for Minimization - Computer Science

Minimizing Boolean Functions

On the need to minimize

Structural formulas in the form of logical functions in SDNF and SKNF uniquely determine the structure of the logic scheme of the combination device. However, one can not be sure that the device constructed by such a formula will most fully satisfy the given requirements. If we consider the identity of the algebra of logic for two logical functions , in general, the number of operations on the right side of the identity is not equal to the number of operations on the left. Since for realization of each operation a logical element is necessary, it is necessary to give preference to the combination device, the structural formula of which has fewer operations. Therefore, by means of identical transformations of the structural formula, which lead only to a change in its form, and not values, it is possible to simplify the scheme of the combination device. The transformation of a structural formula to simplify a combination device is called its minimization.

Algebraic minimization. The method of algebraic minimization of the structural formulas of combinational devices represented by logical functions in SDNF and SKNF consists in simplifying the initial expression with the help of axioms, laws and identities of the algebra of logic. Below is a summary of its main points. In the above relations, the symbols A, B, C can reflect both logical variables and logical functions.

The three basic logical operations (negation, addition and multiplication) considered above are defined in the logic algebra and an equivalence relation (=), satisfying the following properties:

the reflexivity (A = A), symmetry (if A = B, then B = A);

• transitivity (if A = B, B = C then A = C).

We give the axioms of the algebra of logic

(3.6)

(3.7)

(3.8)

(3.9)

(3.10)

(3.11)

Axiom (3.6) reflects the already well-known fact that the algebra of logic operates only with binary variables. The axioms (3.7) - (3.11) are in fact a more general form of representation of the above rules of logical addition, multiplication and negation of binary variables.

Consider the basic laws of algebra of logic.

Commutative (moving law)

(3.12)

Associative (combination) law

(3.13)

Distributive (distributive) law

(3.14)

The duality law (de Morgan's theorem)

(3.15)

Other relationships.

The absorption rule

(3.16)

Rule gluing

(3.17)

The above axioms, laws and relations, with the exception of (3.11), are written in pairs. Each of the expressions entering into the pair can be obtained from the other by replacing the addition operations by multiplication, 0 by 1, and vice versa. If the logical expression includes operations of addition and multiplication, then you should follow the order of operations: first multiply, then add. In complex logical expressions, parentheses are used to specify the order of operations.

In the expressions (3.7) - (3.10), (3.16), (3.17), the right-hand side is simpler than the left one, therefore, by means of the corresponding transformations, we can achieve a significant simplification of the original expression.

thematic pictures

Also We Can Offer!

Other services that we offer

If you don’t see the necessary subject, paper type, or topic in our list of available services and examples, don’t worry! We have a number of other academic disciplines to suit the needs of anyone who visits this website looking for help.

How to ...

We made your life easier with putting together a big number of articles and guidelines on how to plan and write different types of assignments (Essay, Research Paper, Dissertation etc)