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.

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 propositional algebra formula is called a CNF 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, moreover, 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 transformation of variables:

= /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) ;

Standard basis. Elementary formulas are literals. Elementary conjunction (disjunction). Disjunctive (conjunctive) normal form and perfect form. Theorem: any Boolean function different from 0 (from 1) can be represented in the form of SDNF (SCNF). Completeness of the standard basis. Examples of complete bases: Zhegalkin basis, Schaeffer stroke, Peirce arrow.

Standard basis is a set of three original operations of Boolean algebra: addition (union), multiplication (intersection) and negation.

Here we will call literal variable x or its negation x and denote xˆ. Boolean intersection of several literals defined by different variables, i.e. expression of the form X = xˆ 1 xˆ 2 . . . xˆ l, called elementary conjunction . The requirement that all variables be different is determined by the following. If the conjunction includes several identical literals, then due to the commutativity, associativity and idempotency of the conjunction, it is possible, passing to the equivalent formula, to leave only one literal (for example, x 1 x 1 = x 1). If the conjunction includes a variable and its negation, then the formula is equivalent to the constant 0, since x x = 0 and for any formula Y we have Y x x = 0.

The disjunction of several elementary conjunctions is called disjunctive normal form , or DNF . For example,

x 1 x 3 + x 2 x 3 x 4 + x 1 x 2 x 3 x 5 .

If the composition of variables in each elementary conjunction of a given DNF is the same, then the DNF is called perfect . The given example is a DNF that is not perfect. On the contrary, the formula

x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4

there is a perfect form.

Since in Boolean algebra addition and multiplication are symmetric operations and you can always interpret addition as multiplication, and multiplication as addition, there is a dual concept - conjunctive normal form (KNF ), which is a conjunction of elementary disjunctions, and perfect conjunctive form (SKNF ). From the principle of duality for symmetric semirings it follows that any statement regarding DNF is answered by a dual statement regarding CNF, which is obtained by replacing addition (disjunction) with multiplication, multiplication (conjunction) with addition, constant 0 with constant 1, constant 1 with constant 0, order relation with dual (inverse) in order. Therefore, further we will focus on studying only DNF.

Theorem 1.4. Any Boolean function other than the constant 0 can be represented as an SDNF.

◀Let us agree by x σ to mean the formula x if σ = 1, and the formula x if σ = 0. Let the function f(y 1 , . . . , y n) take the value 1 on the vector (t 1 , . . . , t n ) (such a vector is called constituent unit ). Then the elementary conjunction also takes the value 1 on this set, but vanishes on all other n-dimensional Boolean vectors. Consider the formula

in which the sum (union) extends to all those sets (t 1, . . . , t n) of argument values ​​on which given function takes the value 1. Note that the set of such sets is not empty, so the sum contains at least one term.

It is easy to see that the formula Φ becomes 1 for those and only for those values ​​of the variables for which the function in question becomes 1. This means that the formula Ψ represents the function f.

Corollary 1.1. The standard basis is complete.

◀ Indeed, if a function is not a constant 0, then it can be represented either in the form of an SDNF, which is a formula over a standard basis. The constant 0 can be represented, for example, by the formula f(x 1, x 2, . . . , x n) = x 1 x 1.

Example 1.2. Consider a function of three variables m(x 1, x 2, x 3) (Table 1.4), called majoritarian function ̆. This function evaluates to 1 if more than half of its arguments have the value 1. Therefore, it is often called the voting function. Let's build a SDNF for it.

The completeness of the standard basis allows you to select other complete systems functions. The completeness of the set F can be established from the following considerations. Suppose each of the three standard busis functions is representable by a formula over F. Then, by Theorem 1.3, the identity F will be complete.

Example 1.3. The set of operations modulo 2 addition, multiplication and constant 1 is called Zhegalkin basis . Addition modulo 2 and multiplication are the basic operations of the Z2 ring; expressions composed with their help are polynomials over the Z2 ring. The constant 1 in this case is necessary to write the free term. Since xx = x, then all the factors in the polynomial have degree 1. Therefore, when writing a polynomial, you can do without the concept of degree. Examples of formulas over the Zhegalkin basis:

xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.

Any such formula is called the Zhegalkin polynomial. In fact, the Zhegalkin polynomial is a polynomial over the ring Z2.

It is not difficult to construct formulas over the Zhegalkin basis, representing the operations of addition and negation of the standard basis (the multiplication of the two bases is common):

x+y=x⊕y⊕xy, x =x⊕1.

Therefore, the Zhegalkin basis is a complete set.
It can be shown that for any Boolean function the Zhegalkin polynomial is uniquely defined

(more precisely, up to the order of the terms). The coefficients of the Zhegalkin polynomial with a small number of variables can be found using the method of indefinite coefficients.

Example 1.4. Let's consider a set of a single function - the Schaeffer stroke*. This set is complete, as follows from the following easily verifiable identities:

x =x|x, xy=x|y =(x|y)|(x|y), x+y=x |y =(x|x)|(y|y).

Example 1.5. A basis consisting of a single function, the Peirce arrow, is also complete. The test for this is similar to the case of the Schaeffer stroke. However, this conclusion can also be made on the basis of the principle of duality for symmetric semirings.

*Schaeffer's stroke is a binary, but not associative, operation. Therefore, when using the infix form, you should be careful: the result depends on the order of operations. In this case, it is recommended to explicitly indicate the order of operations using parentheses, for example, write (x | y) | z, not x | y | z, although both forms are equivalent.

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 the Boolean 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. Test 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 № 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 table 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. Therefore, the subset of marked vertices is a mapping onto -dimensional cube 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, 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 (-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 and 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 – ; 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 so much complex formations 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. Thanks 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 the Karnaugh map is carried out using 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. Various ways readings result in 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 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

Inconsistency of graphical methods when large number variables are compensated by various analytical methods representations of Boolean functions. One such representation is complex of cubes, using multidimensional logical space terminology 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

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

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.

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 logical operations contained in the formula, replacing them with 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).)