Example. Find CNF formulas

~ ~

The perfect disjunctive normal form of the SDNF can be constructed using the following algorithm:

1. = 1. DNF algorithm

2. = 2. DNF algorithm

3. = 3. DNF algorithm

4. = 4. DNF algorithm

5. Omit identically false terms, i.e. terms of the form

6. Complete the remaining terms with the missing variables

7. Repeat point 4.

Example. Find SDNF formulas.

~

To construct the SCNF, you can use the following scheme:

Example. Find SDNF formulas.

~

It is known (Theorems 2.11, 2.12) that SDNF and SCNF are uniquely defined by the formula and, therefore, they can be constructed using the truth table of the formula.

The scheme for constructing SDNF and SCNF according to the truth table is given below, for the formula ~ :

			~
			1 0 1 0 1 1 0 1	SDNF; SKNF.

2.2. Exercise.

2.2.1 Below are logical expressions. Simplify the expressions of your variant as much as possible using Boole's laws of logic. Then use truth tables to compare your simplified expression with the original one.

2.2.2. Clarify the question of the equivalence of f 1 and f 2 by reducing them to SDNF (Table 1).

2.2.3. Find the dual function for f 3 using the generalized and Boolean principle (Table 1). Compare the results.

№	f 1	f 2	f 3

2.3. Control questions.

2.3.1. Define a statement.

2.3.2. List the main operations on a statement.

2.3.3. What is a truth table?

2.3.4. Create truth tables for the following formulas:

~ ~ ~ ;

2.3.5. Taking into account the conventions on the order of operations, omit the “extra” parentheses and the “ ” sign in the formulas:

;

2.3.6. Using equivalent transformations, prove the identical truth of the formulas:

2.3.7. Find dual formulas:

)

2.3.8. Reduce the following formulas to perfect DNF (SDNF) form:

~

2.3.9. Reduce the following formulas to perfect CNF (SCNF) form:

~

Laboratory work No. 3

Subject:“Minimization of Boolean functions. Logic"

Target: Acquiring practical skills in working with methods for minimizing Boolean functions.

3.1. Theoretical information.

Minimal forms

As was shown in, any Boolean function can be represented in perfect normal form (disjunctive or conjunctive). Moreover, such a representation is the first step in the transition from a tabular specification of a function to its analytical expression. In what follows, we will proceed from the disjunctive form, and the corresponding results for the conjunctive form are obtained based on the principle of duality.

The canonical problem of synthesizing logical circuits in a Boolean basis comes down to minimizing Boolean functions, i.e. to representing them in disjunctive normal form, which contains the smallest number of letters (variables and their negations). Such forms are called minimal. In canonical synthesis, it is assumed that both signals and their inversions are supplied to the inputs of the circuit.

The formula presented in disjunctive normal form is simplified by repeated use of the gluing operation and the absorption operation and (the dual identities for the conjunctive normal form have the form: and ). Here, and can be understood as any Boolean algebra formula. As a result, we arrive at an analytical expression where further transformations are no longer possible, i.e. we get a dead-end form.

Among the dead-end forms there is also a minimal disjunctive form, and it may not be unique. To make sure that a given dead-end form is minimal, you need to find all dead-end forms and compare them by the number of letters they contain.

Let, for example, the function be given in perfect normal disjunctive form:

Grouping the terms and applying the gluing operation, we have .

With another grouping method we get:

Both dead-end forms are not minimal. To get the minimal form, you need to guess to repeat one term in the original formula (this can always be done, since ). In the first case, such a member may be . Then . By adding the term , we get: . Having gone through all possible options, you can make sure that the last two forms are minimal.

Working with formulas at this level is like wandering in the dark. The process of searching for minimal forms becomes more visual and purposeful if you use some graphic and analytical representations and symbols specially developed for this purpose.

Multidimensional cube

Each vertex of a -dimensional cube can be associated with a constituent of a unit. Consequently, the subset of marked vertices is a mapping on the -dimensional cube of a Boolean function of variables in perfect disjunctive normal form. In Fig. 3.1 shows such a mapping for the function from clause 3.7.

Fig. 3.1 Display of a function presented in SDNF on a three-dimensional cube

To display a function of variables presented in any disjunctive normal form, it is necessary to establish a correspondence between its miniterms and the elements of the -dimensional cube.

A miniterm of (-1) rank can be considered as the result of gluing together two miniterms of rank (constituent of unity), i.e. , On an -dimensional cube, this corresponds to replacing two vertices that differ only in the values ​​of the coordinate connecting these vertices with an edge (the edge is said to cover the vertices incident to it). Thus, the (-1)th order miniterms correspond to the edges of the -dimensional cube. Similarly, the correspondence of miniterms of the (-2)th order is established with the faces of a -dimensional cube, each of which covers four vertices (and four edges).

Elements of an -dimensional cube characterized by dimensions are called -cubes. Thus, vertices are 0-cubes, edges are 1-cubes, faces are 2-cubes, etc. Generalizing the above reasoning, we can assume that a miniterm of ()th rank in disjunctive normal form for a function of variables is represented by a -cube, and each -cube covers all those -cubes of lower dimension that are associated with its vertices. As an example in Fig. 3.2 shows a function of three variables. Here the miniterms correspond to 1-cubes (), and the miniterm is represented by a 2-cube ().

Fig.3.2 Function coverage

So, any disjunctive normal form is mapped onto an -dimensional cube by a set of -cubes that cover all the vertices corresponding to the constituents of unity (0-cubes). The converse statement is also true: if a certain set of -cubes covers the set of all vertices corresponding to unit values ​​of a function, then the disjunction of the miniterms corresponding to these -cubes is an expression of this function in disjunctive normal form. Such a collection of -cubes (or their corresponding miniterms) is said to form a covering of a function.

The desire for a minimal form is intuitively understood as a search for such a covering, the number of cubes of which would be smaller, and their dimension would be larger. The coverage corresponding to the minimum form is called the minimum coverage. For example, for the covering function in Fig. 3.3 meets minimum forms And .

Rice. 3.3 Function coverages.

left – ; on right –

The display of a function on a -dimensional cube is clear and simple when . A four-dimensional cube can be depicted as shown in Fig. 3.4, which shows a function of four variables and its minimum coverage corresponding to the expression . Using this method requires such complex constructions that all its advantages are lost.

Rice. 3.4 Function display on a four-dimensional cube

Carnot maps

Another method for graphically displaying Boolean functions uses Carnot maps, which are specially organized correspondence tables. The columns and rows of the table correspond to all possible sets of values ​​of no more than two variables, and these sets are arranged in such an order that each subsequent one differs from the previous one in the value of only one of the variables. Due to this, neighboring cells of the table horizontally and vertically differ in the value of only one variable. Cells located at the edges of the table are also considered adjacent and have this property. In Fig. Figure 3.5 shows Karnaugh maps for two, three, four variables.

Rice. 3.5 Carnaugh maps for two, three and four variables

As in ordinary truth tables, the cells of the sets in which the function takes the value 1 are filled with ones (zeros usually do not fit in, they correspond to empty cells). For example, in Fig. 3.6, A shows a Karnaugh map for a function, the display of which on a four-dimensional cube is given in Fig. 3.4. To simplify things, rows and columns corresponding to values ​​of 1 for a variable are highlighted with a curly brace indicating that variable.

Rice. 3.6 Displaying a function of four variables on a Carnaugh map

(a) and its minimum coverage (b)

Between function mappings to n-dimensional cube and the Carnot map there is a one-to-one correspondence. On the Carnot map s-a cube corresponds to a set of 2 neighboring cells placed in a row, column, square or rectangle (taking into account the proximity of opposite edges of the map). Therefore, all the provisions set out above (see paragraph. multidimensional cube), are valid for Karnaugh maps. So, in Fig. 3.6, b shows the coverage of map units corresponding to the minimal disjunctive form the function in question.

Reading miniterms from a Karnaugh map follows a simple rule. Cells forming s-cube, give miniter (n–s)-th rank, which includes those (n–s) variables that keep the same values ​​on this s-cube, where the value 1 corresponds to the variables themselves, and the value 0 corresponds to their negations. Variables that do not retain their values ​​for s-cube, are absent in the miniterm. Different ways of reading result in different representations of the function in disjunctive normal form (the one on the far right is minimal) (Figure 3.7).

The use of Karnaugh maps requires simpler constructions compared to mapping on n-dimensional cube, especially in the case of four variables. To display functions of five variables, two Karnaugh maps for four variables are used, and for a function of six variables, four such maps are used. With a further increase in the number of variables, Karnaugh maps become practically unusable.

Famous in literature Veitch cards They differ only in the different order of the sets of variable values ​​and have the same properties as Karnaugh maps.

Complex of cubes

The inconsistency of graphical methods with a large number of variables is compensated by various analytical methods for representing Boolean functions. One such representation is complex of cubes, using the terminology of a multidimensional logical space in combination with specially developed symbolism.

). 0-cubes corresponding to the constituents of unity are represented by sets of variable values ​​on which the function is equal to unity. Obviously in the recording

Rice. 3.8 Complex of cubes of a function of three variables ( A) and its symbolic representation ( b)

The complex of cubes forms maximum function coverage. Excluding from it all those s-cubes that are covered by cubes of higher dimension, we obtain coverings corresponding to dead-end forms. So, for the example under consideration (Fig. 3.8) we have a dead-end covering

,

which corresponds to the function . In this case, this coverage is minimal.

For two Boolean functions, the disjunction operation corresponds to the union of their cube complexes, and the conjunction operation corresponds to the intersection of their cube complexes. The negation of a function corresponds to the complement of a complex of cubes, i.e. , and is determined by all vertices at which the function takes the value 0. Thus, there is a one-to-one correspondence (isomorphism) between the algebra of Boolean functions and Boolean sets representing complexes of cubes.

Representing a function in the form of complexes of cubes is less visual, but its most important advantages are that restrictions on the number of variables are removed and the encoding of information is facilitated when using computers.

Minimizing Boolean Functions

Formulation of the problem. Minimizing a circuit in a Boolean basis comes down to finding the minimum disjunctive form that corresponds to the minimum coverage. The total number of letters included in normal form is expressed by the cost of coverage , where is the number of cubes that form the covering of a given function of n variables. Minimum coverage is characterized by the lowest value of its price.

Typically, the minimization problem is solved in two steps. First, we look for a reduced cover that includes all -cubes of maximum dimension, but does not contain a single cube covered by any cube of this cover. The corresponding disjunctive normal form is called reduced, and its miniterms are called simple implicants. For a given function, the reduced coverage is unique, but it may be redundant due to the fact that some of the cubes are covered by collections of other cubes.

At the second step, a transition is made from reduced to dead-end disjunctive normal forms, from which minimal forms are selected. Dead-end forms are formed by excluding from the reduced covering all redundant cubes, without which the remaining set of cubes still forms a covering of a given function, but with the further exclusion of any of the cubes, it no longer covers the set of all vertices corresponding to single values ​​of the function, i.e. it ceases to be a covering .

A reduced coverage cube that covers vertices of a given function that are not covered by any other cubes cannot be redundant and will always be included in the minimum coverage. Such a cube, like its corresponding implicant, is called an extremal (essential implicant), and the vertices it covers are called canceled vertices. The set of extremals forms the core of the covering; it is clear that when moving from a reduced covering to a minimal one, first of all, all extremals should be isolated. If the set of extremals does not form a covering, then it is supplemented to cover with cubes from the reduced covering.

The given definitions are illustrated in Fig. 3.9, where the reduced coverage (see Fig. 3.9a, ) and minimum coverages (Fig. 3.9b) and (see Fig. 3.9, b) are expressed as follows.

Definition 1.Conjunctive monomial (elementary conjunction) of variables is the conjunction of these variables or their negations.

For example, is an elementary conjunction.

Definition 2.Disjunctive monomial (elementary disjunction) from variables is the disjunction of these variables or their negations.

For example, is an elementary disjunction.

Definition 3. A formula that is equivalent to a given propositional algebra formula and is a disjunction of elementary conjunctive monomials is called disjunctive normal form(DNF) of this formula.

For example,– DNF.

Definition 4. A formula that is equivalent to a given propositional algebra formula and is a conjunction of elementary disjunctive monomials is called conjunctive normal form(CNF) of this formula.

For example, – KNF.

For each propositional algebra formula one can find a set of disjunctive and conjunctive normal forms.

Algorithm for constructing normal forms

Using the equivalences of logical algebra, replace all the basic operations in the formula: conjunction, disjunction, negation:

Get rid of double negatives.

Apply, if necessary, the properties of distributivity and absorption formulas to the operations of conjunction and disjunction.

2.6. Perfect disjunctive and perfect conjunctive normal forms

Any Boolean function can have many representations in the form of DNF and CNF. A special place among these representations is occupied by perfect DNF (SDNF) and perfect CNF (SCNF).

Definition 1. Perfect disjunctive normal form(SDNF) is a DNF in which each conjunctive monomial contains each variable from the set exactly once, either itself or its negation.

Structurally, the SDNF for each propositional algebra formula reduced to a DNF can be defined as follows:

Definition 2. Perfect disjunctive normal form(SDNF) of a propositional algebra formula is called its DNF, which has the following properties:

Definition 3. Perfect conjunctive normal form(SCNF) is a CNF in which each disjunctive monomial contains each variable from the set exactly once, and either itself or its negation appears.

Structurally, the SCNF for each propositional algebra formula reduced to the CNF can be defined as follows.

Definition 4. Perfect conjunctive normal form(SCNF) of a given formula of propositional algebra is called such a CNF of it that satisfies the following properties.

Theorem 1. Every Boolean function of variables that is not identically false can be represented in SDNF, and in a unique way.

Methods for finding SDNF

1st method

2nd method

select the lines where the formula takes the value 1;

we compose a disjunction of conjunctions under the condition that if a variable is included in the conjunction with a value of 1, then we write down this variable; if with a value of 0, then its negation. We get SDNF.

Theorem 2. Every Boolean function of variables that is not identically true can be represented in SCNF, and in a unique way.

Methods for finding SCNF

1st method– using equivalent transformations:

2nd method– using truth tables:

select the lines where the formula takes the value 0;

we compose a conjunction of disjunctions under the condition that if a variable is included in the disjunction with a value of 0, then we write down this variable; if with a value of 1, then its negation. We get SKNF.

Example 1. Construct CNF functions.

Solution

Let's eliminate the connective "" using the laws of variable transformation:

= /de Morgan's laws and double negation/ =

/distributive laws/ =

Example 2. Give the formula to DNF.

Solution

Let's express logical operations using and:

= /let's classify negation as variables and reduce double negatives/ =

= /law of distributivity/ .

Example 3. Write the formula in DNF and SDNF.

Solution

Using the laws of logic, we reduce this formula to a form containing only disjunctions of elementary conjunctions. The resulting formula will be the desired DNF:

To construct the SDNF, let’s create a truth table for this formula:

We mark those rows of the table in which the formula (last column) takes the value 1. For each such row, we write out a formula that is true on the set of variables of this row:

line 1: ;

line 3: ;

line 5: .

The disjunction of these three formulas will take the value 1 only on the sets of variables in lines 1, 3, 5, and therefore will be the desired perfect disjunctive normal form (PDNF):

Example 4. Bring the formula to SKNF in two ways:

a) using equivalent transformations;

b) using a truth table.

Solution:

Let us transform the second elementary disjunction:

The formula looks like:

b) draw up a truth table for this formula:

We mark those rows of the table in which the formula (last column) takes the value 0. For each such row, we write out a formula that is true on the set of variables of this row:

line 2: ;

line 6: .

The conjunction of these two formulas will take the value 0 only on the sets of variables in lines 2 and 6, and therefore will be the desired perfect conjunctive normal form (PCNF):

Questions and tasks for independent solution

1. Using equivalent transformations, reduce the formulas to DNF:

2. Using equivalent transformations, bring the formulas to CNF:

3. Using the second distributive law, convert DNF to CNF:

A) ;

4. Convert the given DNFs to SDNFs:

5. Convert the given CNF to SCNF:

6. For given logical formulas, construct SDNF and SCNF in two ways: using equivalent transformations and using a truth table.

b) ;

Conjunctive normal form is convenient for automatically proving theorems. Any Boolean formula can be reduced to CNF. For this you can use: the law of double negation, de Morgan’s law, distributivity.

Encyclopedic YouTube

• 1 / 5

  Formulas in KNF:

  ¬ A ∧ (B ∨ C), (\displaystyle \neg A\wedge (B\vee C),) (A ∨ B) ∧ (¬ B ∨ C ∨ ¬ D) ∧ (D ∨ ¬ E) , (\displaystyle (A\vee B)\wedge (\neg B\vee C\vee \neg D)\wedge ( D\vee\neg E),) A∧B. (\displaystyle A\wedge B.)

  Formulas not in KNF:

  ¬ (B ∨ C) , (\displaystyle \neg (B\vee C),) (A ∧ B) ∨ C , (\displaystyle (A\wedge B)\vee C,) A ∧ (B ∨ (D ∧ E)) . (\displaystyle A\wedge (B\vee (D\wedge E)).)

  But these 3 formulas not in CNF are equivalent to the following formulas in CNF:

  ¬ B ∧ ¬ C , (\displaystyle \neg B\wedge \neg C,) (A ∨ C) ∧ (B ∨ C) , (\displaystyle (A\vee C)\wedge (B\vee C),) A ∧ (B ∨ D) ∧ (B ∨ E) . (\displaystyle A\wedge (B\vee D)\wedge (B\vee E).)

  Construction of CNF

  Algorithm for constructing CNF

  1) Get rid of all the logical operations contained in the formula, replacing them with the basic ones: conjunction, disjunction, negation. This can be done using equivalent formulas:

  A → B = ¬ A ∨ B , (\displaystyle A\rightarrow B=\neg A\vee B,) A ↔ B = (¬ A ∨ B) ∧ (A ∨ ¬ B) . (\displaystyle A\leftrightarrow B=(\neg A\vee B)\wedge (A\vee \neg B).)

  2) Replace the negation sign relating to the entire expression with negation signs relating to individual variable statements based on the formulas:

  ¬ (A ∨ B) = ¬ A ∧ ¬ B , (\displaystyle \neg (A\vee B)=\neg A\wedge \neg B,) ¬ (A ∧ B) = ¬ A ∨ ¬ B . (\displaystyle \neg (A\wedge B)=\neg A\vee \neg B.)

  3) Get rid of double negatives.

  4) Apply, if necessary, the properties of distributivity and absorption formulas to the operations of conjunction and disjunction.

  Example of CNF construction

  Let us bring the formula to CNF

  F = (X → Y) ∧ ((¬ Y → Z) → ¬ X) . (\displaystyle F=(X\rightarrow Y)\wedge ((\neg Y\rightarrow Z)\rightarrow \neg X).)

  Let's transform the formula F (\displaystyle F) to a formula that does not contain → (\displaystyle \rightarrow ):

  F = (¬ X ∨ Y) ∧ (¬ (¬ Y → Z) ∨ ¬ X) = (¬ X ∨ Y) ∧ (¬ (¬ Y ∨ Z) ​​∨ ¬ X) . (\displaystyle F=(\neg X\vee Y)\wedge (\neg (\neg Y\rightarrow Z)\vee \neg X)=(\neg X\vee Y)\wedge (\neg (\neg \ neg Y\vee Z)\vee \neg X).)

  In the resulting formula, we transfer the negation to the variables and reduce double negatives:

  F = (¬ X ∨ Y) ∧ ((¬ Y ∧ ¬ Z) ∨ ¬ X) . (\displaystyle F=(\neg X\vee Y)\wedge ((\neg Y\wedge \neg Z)\vee \neg X).)

  For example, the following formula is written in 2-CNF:

  (A ∨ B) ∧ (¬ B ∨ C) ∧ (B ∨ ¬ C) . (\displaystyle (A\lor B)\land (\neg B\lor C)\land (B\lor \neg C).)

  Simple conjunction called conjunction one or several variables, at this each variable meets Not more one times (or herself, or her negation).

  For example, is a simple conjunction,

  Disjunctive normal shape(DNF) called disjunction simple conjunctions.

  For example, the expression is DNF.

  Perfect disjunctive normal shape(SDNF) called like this disjunctive normal form, at which V every conjunction included All variables given list (or themselves, or their denial), and V one And volume sameok.

  For example, the expression is DNF, but not SDNF. Expression is SDNF.

  Similar definitions (with replacement of conjunction by disjunction and vice versa) are true for CNF and SKNF. Let us give the exact wording.

  Simple disjunction called disjunction one or several variables, at this each variable included Not more one times (or herself, or her negation).For example, the expression is a simple disjunction,

  Conjunctive normal shape(KNF) called conjunction simple disjunctions(for example, the expression is CNF).

  A perfect conjunctive normal form (PCNF) is a CNF in which each simple disjunction includes all the variables of a given list (either themselves or their negations), and in the same order.

  For example, the expression is SKNF.

  Let us present algorithms for transitions from one form to another. Naturally, in specific cases (with a certain creative approach) the use of algorithms can be more labor-intensive than simple transformations using a specific type of a given form:

  a) transition from DNF to CNF

  The algorithm for this transition is as follows: we put two negations above the DNF and, using De Morgan’s rules (without touching the upper negation), we reduce the negation of the DNF back to DNF. In this case, you have to open the brackets using the absorption rule (or Blake's rule). The negation (upper) of the resulting DNF (again according to de Morgan's rule) immediately gives us the CNF:

  Note that CNF can also be obtained from the original expression if we take out at beyond brackets;

  b) transition from CNF to DNF

  This transition is carried out by simply opening the brackets (the absorption rule is again used)

  Thus, we received DNF.

  The reverse transition (from SDNF to DNF) is associated with the problem of minimizing DNF. This will be discussed in more detail in section. 5, here we will show how to simplify DNF (or SDNF) according to Blake’s rule. This type of DNF is called abbreviated DNF;

  c) abbreviation DNF (or SDNF) by rule Blake

  The application of this rule consists of two parts:

  If among the disjoint terms in the DNF there are terms , then to the entire disjunction we add the term TO 1 TO 2. We perform this operation several times (possibly sequentially, or simultaneously) for all possible pairs of terms, and then apply normal absorption;

  If the added term was already contained in the DNF, then it can be discarded completely, for example,

  or

  Of course, the abbreviated DNF is not uniquely defined, but they all contain the same number of letters (for example, there is DNF , after applying Blake’s rule to it, one can arrive at a DNF equivalent to this):

  c) transition from DNF to SDNF

  If some simple conjunction is missing a variable, for example, z, insert the expression into it, and then open the parentheses (we do not write repeating disjoint terms). For example:

  d) transition from KNF to SKNF

  This transition is carried out in a manner similar to the previous one: if a simple disjunction is missing some variable (for example, z, then we add an expression to it (this does not change the disjunction itself), after which we open the brackets using the distribution law):

  Thus, SKNF was obtained from CNF.

  Note that the minimal or reduced CNF is usually obtained from the corresponding DNF.

  Normal forms of logical functions The representation of a Boolean function in the form of a disjunction of conjunctive terms of the constituents of the unit Ki 2.7 is called the disjunctive normal form of the DNF of this function. contain exactly one of all logical variables taken with or without negations, then this form of representation of a function is called the perfect disjunctive normal form SDNF of this function. As you can see, when composing a SDNF function, you need to create a disjunction of all minterms for which the function takes the value 1.

  
  Share your work on social networks

  If this work does not suit you, at the bottom of the page there is a list of similar works. You can also use the search button

  
  

  Lecture 1.xx

  Normal forms of logical functions

  Representation of a Boolean function in the form of a disjunction of conjunctive terms (unit constituent) K i

  , (2.7)

  called disjunctive normal form(DNF) of this function.

  If all conjunctive terms in DNF are minterms , i.e. contain exactly one of all logical variables, taken with or without negations, then this form of function representation is calledperfect disjunctive normal form(SDNF ) this function. It's called SDNF perfect , because each term in the disjunction includes all the variables; disjunctive , because the main operation in the formula is disjunction. Concept “normal shape” means an unambiguous way to write a formula that implements a given function.

  Taking into account the above, the following theorem follows from Theorem 2.1.

  Theorem 2. Any Boolean function(not identically 0) can be presented in SDNF, .

  Example 3. Let us have a table given function f (x 1 , x 2 , x 3 ) (Table 10).

  Table 10

  			f (x 1 , x 2 , x 3 )

  Based on formula (2.6) we obtain:

  As you can see, when composing a SDNF function, you need to create a disjunction of all minterms for which the function takes the value 1.

  Representation of a Boolean function in the form of a conjunction of disjunctive terms (zero constituent) D i

  , (2.8)

  called conjunctive normal form(CNF) of this function.

  If all disjunctive CNF terms are maxterms , i.e. they contain exactly one of all the logical variables of the function, taken with or without negations, then such a CNF is calledperfect conjunctive normal form(SKNF) of this function.

  Theorem 3. Any Boolean function(not identical to 1) may be submitted to SKNF, and such a representation is the only one.

  The proof of the theorem can be carried out similarly to the proof of Theorem 2.1 based on the following Shannon lemma on conjunctive decomposition.

  Shannon's Lemma . Any Boolean function f (x 1, x 2, …, x m) from m variables can be represented like this:

  . (2.9)

  It should be noted that both forms of representation of a logical function (DNF and CNF) are theoretically equal in their capabilities: any logical formula can be represented both in DNF (except for the identical zero) and in CNF (except for the identical one). Depending on the situation, the representation of a function in one form or another may be shorter.

  In practice, DNF is most often used, because this form is more familiar to a person: since childhood, he is more accustomed to adding products than multiplying sums (in the latter case, he intuitively has a desire to open the brackets and thereby move on to DNF).

  Example 4. For the function f (x 1 , x 2 , x 3 ), given by the table. 10, write it to SKNF.

  Unlike the SDNF, when compiling the SCNF in the truth table of a logical function, you need to look at the combinations of variables at which the function takes the value 0, and create a conjunction of the corresponding maxterms,but the variables must be taken with reverse inversion:

  It should be noted that it is impossible to directly move from the SDNF of a function to its SCNF or vice versa. When attempting such transformations, the results are functions that are the opposite of the desired ones. Expressions for the SDNF and SCNF functions can be directly obtained only from its truth table.

  Example 5. For the function f (x 1 , x 2 , x 3 ), given by the table. 10, try to switch from SDNF to SKNF.

  Using the result of example 2.3 we get:

  As you can see, under the general inversion we obtained the SCNF of a logical function, which is the inverse of the function obtained in example 2.4:

  because it contains all the maxterms that are not in the expression for the SCNF of the function under consideration.

  1. Using the properties of the operations (see Table 9) identity (), sum modulo 2 (), implication (), we move on to the operations AND, OR, NOT (in the Boolean basis).

  2. Using the properties of negation and De Morgan’s laws (see Table 9), we ensure that negation operations apply only to individual variables, and not to entire expressions.

  3. Using the properties of the logical operations AND and OR (see Table 9), we obtain the normal form (DNF or CNF).

  4. If necessary, move on to perfect forms (SDNF or SKNF). For example, to obtain SCNF you often need to use the property: .

  Example 6. Convert a logical function to SKNF

  Carrying out the steps of the above algorithm in order, we get:

  Using the absorption property, we get:

  Thus, we have obtained the CNF function f (x 1 , x 2 , x 3 ). To obtain its SCNF, you need to repeat each disjunction in which any variable is missing, twice with this variable and with its negation:

  2.2.6. Minimizing Logic Functions

  Since the same logical function can be represented as h personal formulas, then finding the simplest form R mule defining a Boolean function, simplifies the logic circuit that implements the Boolean function to tion. Minimum form l O logical functionin some basis we can consider one that contains the minimum number of superpositions of fun To tions of the basis, allowing for parentheses. However, it is difficult to build an effective l algorithm for such minimization to obtain the minimum parenthesis r we.

  Let's consider a simpler minimization problem in the synthesis of combinational circuits, in which we are looking not for the minimal parenthetical form of a function, but for its minimal DNF. There are simple, efficient algorithms for this task.

  Quine's method

  The function to be minimized is represented in SDNF, and all possible incomplete gluing operations are applied to it

  , (2.10)

  and then absorption

  , (2.11)

  and this pair of steps is applied repeatedly. Thus, it is possible to reduce the rank of terms. This procedure is repeated until there is not a single term left that can be bonded to any other term.

  Note that the left side of equation (2.10) could immediately be minimized in a simpler and more obvious way:

  This method is bad because with such direct minimization, conjunctive terms either disappear, although there are still possible cases of their use for gluing and absorption with the remaining terms.

  It should be noted that Quine’s method is quite labor-intensive, so the likelihood of making mistakes during transformations is quite high. But its advantage is that theoretically it can be used for any number of arguments and as the number of variables increases, the transformations become less complicated.

  Karnaugh map method

  The method of Carnot maps (tables) is a more visual, less labor-intensive and reliable way to minimize logical functions, but its use is practically limited to functions of 3-4 variables, maximum 5-6 variables.

  Carnot map this is a two-dimensional tabular form of representing the truth table of a Boolean function, which allows you to easily find the minimum DNFs of logical functions in a graphical visual form. Each cell of the table is associated with the SDNF minterm of the function being minimized, and in such a way that any symmetry axes of the table correspond to zones that are mutually inverse with respect to some variable. This arrangement of cells in the table makes it easy to determine the sticking terms of the SDNF (differing in the inversion sign of only one variable): they are located symmetrically in the table.

  Truth tables and Carnaugh maps for the AND and OR functions of two lanes e The variables are presented in Fig. 8. A value is written in each cell of the map A The value of a function on the set of argument values ​​corresponding to this cell N Comrade

  A) AND b) OR

  Rice. 8. Example of Karnaugh maps for functions of two variables

  In the Karnaugh map there is only one 1 for the And function, so it cannot be glued to anything. The expression for the minimal function will contain only the term corresponding to this 1:

  f = xy.

  In the Carnot map for the OR function there are already three 1s and you can make two sticking pairs, with the 1 corresponding to the term xy , is used twice. In the expression for the minimal function, you need to write down the terms for the pairs being glued together, leaving in them all the variables that do not change for this pair, and removing the variables that change their value. For horizontal gluing we get x , and for vertical y , as a result we get the expression

  f = x + y.

  In Fig. 9 shows the truth tables of two functions of three variables ( A ) and their Carnot maps ( b and c). Function f 2 differs from the first in that it is not defined on three sets of variables (in the table this is indicated by a dash).

  When determining the minimum DNF function, the following rules are used. All cells containing 1 are combined into closed rectangular areas called k-cubes, where k = log 2 K, K quantity 1 in a rectangular area. In this case, each area should be a rectangle with the number of cells 2 k, where k = 0, 1, 2, 3, …. For k = 1 rectangle is called one is a cube and contains 2 1 = 2 units; for k = 2 rectangle contains 2 2 = 4 units and is called two-cube; for k = 3 region of 2 3 = 8 units is called three-cube ; etc. Units that cannot be combined into rectangles can be called zero-cubes , which contain only one unit (2 0 = 1). As can be seen, for even k areas can have a square shape (but not necessarily), and if odd k only rectangles.

  						b c

  Rice. 9. Example of Karnaugh maps for functions of three variables

  These regions can overlap, that is, the same cells can enter different regions. Then the minimal DNF function is written as the disjunction of all conjunctive terms corresponding to k - cubes.

  Each of the indicated areas on the Karnaugh map is represented in a minimal DNF by a conjunction, the number of arguments in which is k less than the total number of function arguments m , i.e. this number is equal mk . Each conjunction of a minimal DNF is composed only of those arguments that for the corresponding area of ​​the map have values ​​either without inversions or only with inversions, i.e., do not change their meaning.

  Thus, when covering map cells with closed areas, one should strive to ensure that the number of areas is minimal, and each area contains as many cells as possible, since in this case the number of terms in the minimal DNF will be minimal and the number of arguments in the corresponding conjunction will be minimal.

  For the function according to the Karnaugh map in Fig. 9, b we find

  since for the upper closed region the variables x 1 and x 2 have values ​​without inversions, for the lower x 1 matters with inversion, and x 3 without inversion.

  Undefined values ​​in the map in Fig. 9, V can be further defined by replacing it with zero or one. For this function, it is clear that it is more profitable to replace both undefined values ​​with 1. In this case, two areas are formed, which are different types of 2-cubes. Then the expression for the minimum DNF function will be as follows:

  When constructing closed areas, it is allowed to fold the Carnot map into a cylinder both horizontally and vertically. R tikal axes with the union of opposite faces R you, i.e. units located along the edges of the Carnot symmetry map h but can also be combined.

  Carnaugh maps can be drawn in different ways (Fig. 10).

  									x 2 x 3

  a b

  Rice. 10. Different ways to depict Carnaugh maps
  for a function of 3 variables

  But the most convenient options for Karnaugh maps for functions of 2-4 variables are those shown in Fig. 11 tables, because they show for each cell A We have all variables in direct or inverse form.

  a b

  Rice. eleven. The most convenient image of Carnaugh maps
  for functions 3 ( a) and 4 (b) variables

  For functions of 5 and 6 variables, the method shown in Fig. 10, V .

  Rice. 12. Image of a Karnaugh map for a function of 5 variables

  Rice. 13. Image of a Karnaugh map for a function of 6 variables

  Other similar works that may interest you.vshm>
  9020.		THE PRINCIPLE OF DUALITY. EXPANSION OF BOOLEAN FUNCTIONS INTO VARIABLES. PERFECT DISJUNCTIVE AND CONJUNCTIVE NORMAL FORMS	96.34 KB
  	This theorem is constructive in nature, since it allows for each function to construct a formula that implements it in the form of a perfect d.n. f. To do this, in the truth table for each function, we mark all the rows in which
  6490.		Description and minimization of logical functions	187.21 KB
  	The relationship between a function's arguments and its values ​​is expressed in verbal form. Example: A three-argument function takes a value when any two or more function arguments are equal. It consists of constructing a truth table containing function values ​​for all sets of argument values. In this example, using the truth table, we obtain the following entry in the form of DNF...
  6707.		Design of relational databases. Design problems in the classical approach. Principles of normalization, normal forms	70.48 KB
  	What is a relational database project? This is a set of interconnected relationships in which all attributes are defined, the primary keys of the relationships are specified, and some additional properties of the relationships are specified that relate to the principles of maintaining integrity. Therefore, the database design must be very accurate and verified. In fact, a database project is the foundation of a future software package that will be used for quite a long time and by many users.
  4849.		Forms and methods of implementing state functions	197.3 KB
  	The term “function” has far from the same meaning in domestic and foreign scientific literature. In philosophical and general sociological terms, it is considered as “an external manifestation of the properties of an object in a given system of relations”; as a set of ordinary or specific actions of individuals or bodies
  17873.		Formation of logical UUD for 3rd grade students	846.71 KB
  	Psychological and pedagogical aspects of the problem of forming logical universal actions in primary schoolchildren Methods for assessing the formation of logical UUDs. The development of a concept for the development of universal educational activities in the general education system meets new social needs. The most important task of the modern education system is the formation of universal educational activities of UUD. The formation of universal educational activities is the key to preventing school difficulties.
  2638.		Technical implementation of logical connections in automatic blocking systems	1.04 MB
  	Technical implementation of logical connections in automatic blocking systems Technical implementation of control algorithms for three-digit and four-digit batteries can be achieved using relay contact and contactless discrete and integral logic elements...
  10203.		APPLICATION OF THE CONCEPT OF RISK ORIENTED APPROACH TO BUILDING STRUCTURAL AND LOGICAL MODELS OF EMERGENCY OCCURENCE AND DEVELOPMENT	70.8 KB
  	General risk analysis The production environment is becoming saturated with powerful technological systems and technologies that make human labor productive and less physically difficult, but more dangerous. Risk is characterized by the unexpectedness and suddenness of the onset of a dangerous situation. Every day we are faced with numerous risks, but most of them remain potential. Risk theory provides for a quantitative assessment of the negative impact on a person, as well as damage to his health and life.
  11576.		Concept, types and forms of transactions. Consequences of failure to comply with the required form of transactions	49.82 KB
  	Recognition of a transaction as invalid; types of invalid transactions. The applied value of the course work lies in simplifying the concept of a transaction, that is, its public presentation in a more accessible form.
  6213.		Function approximation	3.08 MB
  	The first consists of replacing a certain function specified analytically or tabularly with another function close to the original one but simpler and more convenient for calculations. For example, replacing a function with a polynomial allows you to obtain simple formulas for numerical integration and differentiation; Replacing the table with an approximating function allows you to obtain values ​​at its intermediate points. The second problem also arises: restoring a function on a certain segment from the values ​​of the function given on this segment in a discrete set of points. The answer to this question...
  14058.		Evolution of state functions	29.99 KB
  	The Russian state as a legal phenomenon must first of all ensure the implementation of the purpose of the state as well as its main constitutional characteristics as a democratic federal legal social secular state with a republican form of government. The main purpose of the state is determined by Art.