The conjunctive normal form of a logical function. Normal forms: dnf, knf, sdnf, sknf

Simple disjunction(eng. inclusive disjunction) or disjunctome(English disjunct) is called the disjunction of one or more variables or their negations, and each variable occurs no more than once.

Simple disjunction

• complete, if each variable (or its negation) enters it exactly once;
• monotonous, if it does not contain negations of variables.

Conjunctive normal form, CNF(English conjunctive normal form, CNF) is a normal form in which a Boolean function has the form of a conjunction of several simple clauses.

CNF example:$f(x,y) = (x \lor y) \land (y \lor \neg ( z ))$

SKNF

Perfect conjunctive normal form, SKNF(English perfect conjunctive normal form, PCNF) is a CNF that satisfies the conditions:

• it has no identical simple disjunctions
• every simple disjunction is complete

SKNF example:$f(x,y,z) = (x \lor \neg ( y ) \lor z) \land (x\lor y \lor \neg ( z ))$

Theorem: For any Boolean function $f(\vec ( x ))$ not equal to the identical unit, there is a SKNF defining it.

Proof: Since the inverse of the function $\neg ( f ) (\vec x)$ is equal to one on those tuples on which $f(\vec x)$ is equal to zero, then the SDNF for $\neg ( f ) (\vec x)$ can be write it like this:

$\neg ( f ) (\vec x) = \bigvee\limits_ ( f(x^ ( \sigma_ ( 1 ) ) , x^ ( \sigma_ ( 2 ) ) , ... ,x^ ( \sigma_ ( n ) )) = 0 ) (x_ ( 1 ) ^ ( \sigma_ ( 1 ) ) \wedge x_ ( 2 ) ^ ( \sigma_ ( 2 ) ) \wedge ... \wedge x_ ( n ) ^ ( \sigma_ ( n ) )) $, where $ \sigma_ ( i ) $ denotes the presence or absence of negation at $ x_ ( i ) $

Find the inversion of the left and right sides of the expression:

$ f(\vec x) = \neg (( \bigvee\limits_ ( f(x^ ( \sigma_ ( 1 ) ) , x^ ( \sigma_ ( 2 ) ) , ... ,x^ ( \sigma_ ( n ) )) = 0 ) (x_ ( 1 ) ^ ( \sigma_ ( 1 ) ) \wedge x_ ( 2 ) ^ ( \sigma_ ( 2 ) ) \wedge ... \wedge x_ ( n ) ^ ( \sigma_ ( n ) ))) )) $

Applying the de Morgan rule twice to the expression obtained on the right side, we get: $ f(\vec x) = \bigwedge \limits_ ( f(x^ ( \sigma_1 ) , x^ ( \sigma_2 ) , \dots ,x^ ( \ sigma_n )) = 0 ) $ $(\neg ( x_1^ ( \sigma_1 ) ) \vee \neg ( x_2^ ( \sigma_2 ) ) \vee \dots \vee \neg ( x_n^ ( \sigma_n ) )) $

The last expression is SKNF. Since the SKNF is obtained from the SDNF, which can be constructed for any function that is not identically zero, the theorem is proved.

Algorithm for constructing SKNF according to the truth table

• In the truth table, we mark those sets of variables on which the value of the function is equal to $0$.
• For each marked set, we write the disjunction of all variables according to the following rule: if the value of some variable is $0$, then we include the variable itself in the disjunction, otherwise its negation.
• We connect all obtained disjunctions by conjunction operations.

An example of constructing a SKNF for a median

one). In the truth table, we mark those sets of variables on which the value of the function is equal to $0$.

2). For each marked set, we write the conjunction of all variables according to the following rule: if the value of some variable is $0$, then we include the variable itself in the disjunction, otherwise its negation.

3). We connect all obtained disjunctions by conjunction operations.

$ \langle x,y,z \rangle = (x \lor y \lor z) \land (\neg ( x ) \lor y \lor z) \land (x \lor \neg ( y ) \lor z) \land (x \lor y \lor \neg ( z ))$

SKNF examples for some functions

Pierce arrow: $ x \downarrow y = (\neg ( x ) \lor ( y )) \land (( x ) \lor \neg ( y )) \land (\neg ( x ) \lor \neg ( y ) ) $

Exclusive or: $ x \oplus y \oplus z = (\neg ( x ) \lor \neg ( y ) \lor z) \land (\neg ( x ) \lor y \lor \neg ( z )) \land (x \lor \neg ( y ) \lor \neg ( z )) \land (x \lor y \lor z)$

The conjunctive normal form is convenient for automatic proofs of theorems. Any Boolean formula can be reduced to CNF. To do this, you can use: the law of double negation, the law of de Morgan, 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 are not in CNF 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 main 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, referring to the entire expression, by negation signs, related 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 negative signs.

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

  An example of constructing a CNF

  Let us reduce 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 the double negations:

  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).)
  

  Example. Find CNF formulas

  ~ ~

  

  The perfect disjunctive normal form of 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. Fill in the remaining terms with the missing variables

  7. Repeat point 4.

  Example. Find sdnf formulas.

  ~

  

  

  

  

  The following scheme can be used to construct the SKNF:

  Example. Find sdnf formulas.

  
  

  ~

  

  It is known (Theorems 2.11, 2.12) that SDNF and SKNF are uniquely defined by the formula and, therefore, they can be built according to the truth table of the formula .

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

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

  2.2. The task.

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

  
  
  

  

  

  

  

  

  

  2.2.2. Find out 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 according to the generalized and Boolean principle (Table 1). Compare the results.

  №	f1	f2	f 3

  2.3. Test questions.

  2.3.1. Define a statement.

  2.3.2. List the basic operations on the 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" brackets and the sign "" in the formulas:

  ;

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

  2.3.7. Find dual formulas:

  

  

  )

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

  ~

  2.3.9. Convert the following formulas to the perfect CNF (SKNF) form:

  

  ~

  

  

  Laboratory work № 3

  Topic:“Minimization of Boolean functions. Logic"

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

  3.1. Theoretical information.

  Minimum Forms

  As 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 definition of a function to its analytical expression. In the future, we will start from the disjunctive form, and the corresponding results for the conjunctive form are obtained on the basis of the duality principle.

  The canonical problem of synthesizing logic circuits in a Boolean basis is reduced 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 fed to the inputs of the circuit.

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

  Among dead-end forms there is also a minimal disjunctive form, and it may not be unique. To make sure that this 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 members and applying the gluing operation, we have .

  With another grouping method, we get:

  Both dead end forms are non-minimal. To get the minimum 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 can be . Then . By adding the term , we get: . After going through all the possible options, we 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 some graphic and analytical representations and symbols specially designed for this purpose are used.

  Multidimensional cube

  Each vertex of a -dimensional cube can be assigned a unit constituent. Therefore, the subset of marked vertices is a mapping on the -dimensional cube of a Boolean function of variables in perfect disjunctive normal form. On fig. 3.1 shows such a mapping for the function from Section 3.7.

  

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

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

  The miniterm of the (-1)th rank can be considered as the result of gluing two miniterms of the -th rank (unit constituent), i.e. , On a -dimensional cube, this corresponds to replacing two vertices, which 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 miniterms of the ( -1) order correspond to the edges of the -dimensional cube. Similarly, the miniterms of the ( -2)th order correspond to the faces of the -dimensional cube, each of which covers four vertices (and four edges).

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

  

  Fig.3.2 Function coverage

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

  The desire for a minimal form is intuitively understood as a search for such a cover, the number of -cubes of which would be smaller, and their dimensions would be larger. The cover corresponding to the minimum shape is called the minimum cover. For example, for the coverage function in Fig. 3.3 corresponds to the 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 drawn as shown in Fig. 3.4, which displays 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

  Karnot maps

  Another method for graphing boolean functions uses Carnot cards, which are specially organized lookup tables. The columns and rows of the table correspond to all possible sets of values ​​for at most two variables, and these sets are arranged in such an order that each subsequent set differs from the previous one by the value of only one of the variables. Due to this, the adjacent cells of the table both 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. On fig. 3.5 shows Karnaugh maps for two, three, four variables.

  
  

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

  As in ordinary truth tables, the cells of the sets on 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, but shows the Karnaugh map for the function, the display of which on a four-dimensional cube is given in fig. 3.4. To simplify, the rows and columns corresponding to the values ​​1 for some variable are highlighted with a curly bracket with the designation of this variable.

  
  

  Rice. 3.6 Carnot chart display of a function of four variables

  (a) and its minimum coverage (b)

  Between function mappings on n-dimensional cube and on the Karnaugh map there is a one-to-one correspondence. On the map of Carnot s-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 in the above (see paragraph multidimensional cube) are valid for Carnot maps. So, in fig. 3.6, b the coverage of map units is shown corresponding to the minimum disjunctive form the function in question.

  The reading of miniterms from the Karnot map is carried out according to a simple rule. The cells that form s-cube, give miniter (n–s) 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 ​​on s-cube, are absent in the minitherm. Various ways reads lead to different representations of the function in disjunctive normal form (the rightmost one is minimal) (Figure 3.7).

  
  

  The use of Karnaugh maps requires simpler constructions compared to displaying on n-dimensional cube, especially in the case of four variables. To display functions of five variables, two Karnot 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, Karnot maps become practically unusable.

  Known in Literature Veitch's cards differ only in a different order of the sets of variable values ​​and have the same properties as Karnaugh maps.

  Complex of cubes

  The failure of graphical methods for a large number of variables is compensated by various analytical methods for representing Boolean functions. One of these representations is complex of cubes, which uses the terminology of a multidimensional logical space in combination with specially designed 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 record

  

  Rice. 3.8 Complex of cubes of functions of three variables ( but) and its symbolic representation ( b)

  The complex of cubes forms maximum function coverage. Excluding 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 cover

  ,

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

  For two Boolean functions, the disjunction operation corresponds to the union of their cube complexes, and the conjunction operation to the intersection of their cube complexes. The negation of a function corresponds to the addition 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.

  The representation of 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 information coding is facilitated when using computers.

  Minimizing Boolean Functions

  Formulation of the problem. Minimization of a scheme in a Boolean basis is reduced to finding the minimum disjunctive form, which corresponds to the minimum coverage. Total number letters included in the normal form is expressed by the cover price , where is the number of - cubes forming the coverage of the given function in n variables. The minimum coverage is characterized by the lowest value of its price.

  Usually, the minimization problem is solved in two steps. First, a reduced cover is searched for that includes all -cubes of maximum dimension, but does not contain any cube covered by any cube of this cover. The corresponding disjunctive normal form is called reduced, and its miniterms are called simple implicants. For this function, the reduced coverage is the only one, 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, the transition from reduced to dead-end disjunctive normal forms is carried out, from which minimal forms are selected. Dead-end forms are formed by excluding all redundant cubes from the reduced cover, without which the remaining set of cubes still forms a cover of a given function, but with further exclusion of any of the cubes, it no longer covers the set of all vertices corresponding to unit values ​​of the function, i.e., it ceases to be a cover .

  A reduced cover 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 cover. Such a cube, as well as the implicant corresponding to it, is called an extremal (essential implicant), and the vertices covered by it are called canceled vertices. The set of extremals forms the core of the coverage, it is clear that when passing from a reduced coverage to a minimum coverage, first of all, all extremals should be selected. If the set of extremals does not form a cover, then it is complemented to a cover by cubes from the reduced cover.

  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.9b) are expressed as follows.

  normal form logical formula does not contain signs of implication, equivalence and negation of non-elementary formulas.

  Normal form exists in two forms:

  conjunctive normal form (CNF)-- conjunction of several disjunctions, for example, $\left(A\vee \overline(B)\vee C\right)\wedge \left(A\vee C\right)$;

  disjunctive normal form (DNF)-- disjunction of several conjunctions, for example, $\left(A\wedge \overline(B)\wedge C\right)\vee \left(B\wedge C\right)$.

  SKNF

  Perfect conjunctive normal form (SKNF) is a CNF that satisfies three conditions:

  does not contain identical elementary disjunctions;

  none of the disjunctions contains the same variables;

  each elementary disjunction contains every variable in the given CNF.

  Any Boolean formula that is not identically true can be represented in SKNF.

  Rules for constructing SKNF according to the truth table

  For each set of variables for which the function is 0, the sum is recorded, with variables that have a value of 1 taken with a negation.

  SDNF

  Perfect Disjunctive Normal Form (PDNF) is a DNF that satisfies three conditions:

  does not contain identical elementary conjunctions;

  none of the conjunctions contains the same variables;

  each elementary conjunction contains every variable from the given DNF, moreover, in the same order.

  Any Boolean formula that is not identically false can be represented in SDNF, moreover, in a unique way.

  Rules for constructing SDNF according to the truth table

  For each set of variables in which the function is equal to 1, the product is written, and the variables that have a value of 0 are taken with negation.

  Examples of finding SKNF and SDNF

  Example 1

  Write a logical function according to its truth table:

  Picture 1.

  Solution:

  Let's use the rule for constructing SDNF:

  

  Figure 2.

  We get SDNF:

  Let's use the SKNF construction rule.

  Let us introduce the concept of elementary disjunction.

  An elementary disjunction is an expression of the form

  The conjunctive normal form (CNF) of a logical function is the conjunction of any finite set of pairwise distinct elementary disjunctions. For example, logical functions

  are conjunctions of elementary disjunctions. Therefore, they are written in conjunctive normal form.

  An arbitrary logical function given by an analytic expression can be reduced to CNF by performing the following operations:

  Using the inversion rule if the negation operation is applied to a logical expression;

  Uses of the axiom of distributivity with respect to multiplication:

  Using the absorb operation:

  Exceptions in disjunctions of repeating variables or their negations;

  Removal of all identical elementary disjunctions, except for one;

  Deleting all disjunctions that simultaneously include a variable and its negation.

  The validity of the listed operations follows from the basic axioms and identity relations of the algebra of logic.

  A conjunctive normal form is called perfect if each elementary disjunction included in it contains in direct or inverse form all the variables on which the function depends.

  The transformation of CNF to perfect CNF is carried out by performing the following operations:

  Additions to each elementary disjunction of conjunctions of variables and their negations, if they are not included in this elementary disjunction;

  Use of the axiom of distributivity;

  Removal of all identical elementary disjunctions, except for one.

  Any logical function can be represented in a perfect CNF except

  identically equal to one (). A distinctive property of a perfect CNF is that the representation of a logical function in it is unique.

  The elementary disjunctions included in a perfect CNF function are called zero constituents. Each zero component in a perfect CNF vanishes on the only set of variable values, which is the zero set of the function. Consequently, the number of zero sets of a logical function coincides with the number of zero constituents included in its perfect CNF.

  The logical function zero constant in perfect CNF is represented by the conjunction 2nconstituent of zero. Let us formulate a rule for compiling the SKNF of a logical function according to the correspondence table.

  For each line of the correspondence table in which the function is equal to zero, an elementary disjunction of all variables is compiled. The disjunction includes the variable itself, if its value is equal to zero, or negation, if its value is equal to one. The resulting elementary disjunctions are combined by the conjunction sign.

  
  

  Example 3.4. For the logical function z(x) given by the lookup table 2.2, we define the perfect conjunctive form.

  For the first row of the table, which corresponds to the zero function set 000, we find the null component . Performing similar operations for the second, third and fifth rows, we determine the desired perfect CNF function:

  It should be noted that for functions whose number of unit sets exceeds the number of zero sets, it is more compact to write them in the form of SKNF and vice versa.