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

For example, is an elementary conjunction.

Definition 2.Disjunctive monomial (elementary disjunction) from variables is called 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 the algebra of logic, replace all the operations in the formula with the main ones: conjunction, disjunction, negation:

Get rid of the double negatives.

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

2.6. Perfect disjunctive and perfect conjunctive normal forms

Any Boolean function can have many DNF and CNF representations. A special place among these representations is occupied by perfect DNF (SDNF) and perfect CNF (SKNF).

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

Structurally, SDNF for each formula of the propositional algebra reduced to 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(SKNF) is a CNF in which each disjunctive monomial contains each variable from the set exactly once, and either itself or its negation enters.

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

Definition 4. Perfect conjunctive normal form(SKNF) of a given propositional algebra formula is its CNF, which satisfies the following properties.

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

Ways to find SDNF

1st way

2nd way

select the lines where the formula takes the value 1;

we make a disjunction of conjunctions, provided that if the variable is included in the conjunction with the value 1, then we write this variable, if with the value 0, then its negation. We get SDNF.

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

Ways to find SKNF

1st way– with the help of equivalent transformations:

2nd way- using truth tables:

select the lines where the formula takes the value 0;

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

Example 1 Plot the CNF functions .

Solution

Eliminate the link "" using the laws of transformation of variables:

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

/distributive laws/ =

Example 2 Convert the formula to DNF.

Solution

We express the logical operations in terms of, and:

= /Relate negation to variables and reduce double negations/ =

= /distributivity law/ .

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 build SDNF, we will compile a truth table for this formula:

We mark those rows of the table in which the formula (the last column) takes the value 1. For each such row, we write out the 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 required perfect disjunctive normal form (PDNF):

Example 4 Bring the formula to SKNF in two ways:

a) with the help of equivalent transformations;

b) using a truth table.

Solution:

We transform the second elementary disjunction:

The formula looks like:

b) compose a truth table for this formula:

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

line 2: ;

line 6: .

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

Questions and tasks for independent solution

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

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

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

but) ;

4. Convert the given DNFs to SDNFs:

5. Convert the given CNF to SKNF:

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

b) ;

For any logical formula, with the help of identical transformations, it is possible to construct an infinite number of formulas equivalent to it. In the algebra of logic, one of the main tasks is the search for canonical forms (i.e., formulas built according to a single rule, canon).

If a logical function is expressed through disjunction, conjunction and negation of variables, then this form of representation is called normal.

Among normal forms, perfect normal forms stand out (those forms in which functions are written in a unique way).

Perfect Disjunctive Normal Form (PDNF)

Definition. A formula is called an elementary conjunction if it is formed by the conjunction of a certain number of variables or their negations.

Examples: y, ¬ y, x 1 ∧ ¬ x 2 ∧ x 3 ∧ x 4

Definition. A formula is called a disjunctive normal form (DNF) if it is a disjunction of non-repeating elementary conjunctions.

DNF is written in the following form: F 1 ∨ F 2 ∨ ... ∨ F n , where F i is an elementary conjunction

Examples: ¬ x 1 ∧ x 2 ∨ x 1 ∧ ¬ x 2 ∨ x 1 ∧ ¬ x 2 ∧ x 3, ¬ y 1 ∨ y 1 ∧ y 2 ∨ ¬ y 2

Definition. A logical formula in k variables is called a perfect disjunctive normal form (PDNF) if:
1) the formula is a DNF, in which each elementary conjunction is a conjunction of k variables x 1, x 2, ..., x k, and on i-th place this conjunction is either the variable x i or its negation;
2) all elementary conjunctions in such a DNF are pairwise distinct.

Example: (¬ x 1 ∧ x 2 ∧ x 3) ∨ (x 1 ∧ ¬ x 2 ∧ x 3) ∨ (x 1 ∧ x 2 ∧ ¬ x 3)

Perfect conjunctive normal form (SKNF)

Definition. A formula is called an elementary disjunction if it is formed by the disjunction of a certain number of variables or their negations.

Examples: ¬ x 3, x 1 ∨ x 2, x 1 ∨ x 2 ∨ ¬ x 3

Definition. A formula is called a conjunctive normal form (CNF) if it is a conjunction of non-repeating elementary disjunctions.

CNF is written in the following form: F 1 ∧ F 2 ∧ ... ∧ F n , where F i is an elementary disjunction

Examples: (x 1 ∨ ¬ x 2) ∧ x 3, (x 1 ∨ x 2) ∧ (¬ x 1 ∨ x 2 ∨ x 3) ∧ (x 1 ∨ ¬ x 2 ∨ ¬ x 3)

Definition. A logical formula in k variables is called a perfect conjunctive normal form (KDNF) if:
1) the formula is a CNF, in which each elementary disjunction is a disjunction of k variables x 1 , x 2 , …, x k , and the i-th place of this disjunction is either the variable x i or its negation;
2) all elementary disjunctions in such a CNF are pairwise distinct.

Example: (x 1 ∨ x 2 ∨ x 3) ∧ (¬ x 1 ∨ ¬ x 2 ∨ x 3)

notice, that any logical function that is not identically equal to 0 or 1 can be represented as SDNF or SKNF.

Algorithm for constructing SDNF according to the truth table

1. Select all rows of the table in which the value of the function is equal to one.
2. For each such line, write the conjunction of all variables as follows: if the value of some variable in this set is equal to 1, then we include the variable itself in the conjunction, otherwise, its negation.
3. We connect all the resulting conjunctions by disjunction operations.

Algorithm for constructing SKNF according to the truth table

1. Select all rows of the table in which the value of the function is equal to zero.
2. For each such row, write the disjunction of all variables as follows: if the value of some variable in this set is 0, then we include the variable itself in the conjunction, otherwise, its negation.
3. We connect all obtained disjunctions by conjunction operations.

The analysis of the algorithms shows that if the value of the function is equal to 0 on most of the rows of the truth table, then to obtain its logical formula, it is better to construct an SDNF, otherwise, a SKNF.

Example: Given a truth table of a logical function of three variables. Construct a logical formula that implements this function.

x	y	z	F(x, y, z)
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

Because on most rows of the truth table, the value of the function is equal to 1, then we construct the SKNF. As a result, we get the following logical formula:
F = (¬x ∨ y ∨ z) ∧ (¬x ∨ y ∨ ¬z)

Let's check the resulting formula. To do this, we construct a truth table of the function.

x	y	z	x	¬ x ∨ y ∨ z	¬z	¬ x ∨ y ∨ ¬ z	F(x, y, z)
0	0	0	1	1	1	1	1
0	0	1	1	1	0	1	1
0	1	0	1	1	1	1	1
0	1	1	1	1	0	1	1
1	0	0	0	0	1	1	0
1	0	1	0	1	0	0	0
1	1	0	0	1	1	1	1
1	1	1	0	1	0	1	1

Comparing the original truth table and the one built for the logical formula, we note that the function value columns are the same. This means that the logical function is built correctly.

standard basis. Elementary formulas are literals. Elementary conjunction (disjunction). Disjunctive (conjunctive) normal form and perfect form. Theorem: any Boolean function other than 0 (from 1) can be represented as SDNF (SKNF). Completeness of the standard basis. Examples of complete bases: Zhegalkin's basis, Sheffer's stroke, Pierce's arrow.

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

Here we will call literal variable x or its negation x and denote xˆ. Boolean intersection of multiple literals defined by different variables, i.e. expression of the form X = xˆ 1 xˆ 2 . . . xˆ l, is called elementary conjunction . The requirement that all variables be different is due to the following. If a conjunction contains several identical literals, then due to the commutativity, associativity, and idempotency of the conjunction, passing to an equivalent formula, we can 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 example given 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

is the perfect form.

Since in Boolean algebra addition and multiplication are symmetrical operations and one can always interpret addition as multiplication and multiplication as addition, there is also a dual concept - conjunctive normal form (KNF ), which is a conjunction of elementary disjunctions, and perfect conjunctive form (SKNF ). It follows from the principle of duality for symmetric semirings that any statement about DNF corresponds to a dual statement about CNF, which is obtained by replacing addition (disjunction) by multiplication, multiplication (conjunction) by addition, constant 0 by constant 1, constant 1 by constant 0, order relations by 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 , . . . , yn) take the value 1 on the vector (t 1 , . . . , tn ) (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 , . . . , tn) of argument values ​​on which the given function takes the value 1. term.

It is easy to see that the formula Φ turns into 1 for those, and only for those values ​​of the variables, for which the considered function turns into 1. Hence, 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 as 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 majority 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 an SDNF for it.

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

Example 1.3. The set of operations modulo 2 addition, multiplication and constant 1 is called the Zhegalkin basis . Modulo 2 addition and multiplication are the basic operations of the ring Z2, expressions composed with their help are polynomials over the ring Z2. The constant 1 in this case is needed to write the free member. Since xx \u003d x, then all 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 easy to construct formulas over the Zhegalkin basis, representing the operations of addition and negation of the standard basis (multiplication of 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 terms). The coefficients of the Zhegalkin polynomial with a small number of variables can be found by the method of indeterminate coefficients.

Example 1.4. Consider a set of a single function - the Schaeffer stroke*. This set is complete, which follows from the following easily verified identities:

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

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

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

Disjunctive and conjunctive normal forms of the propositional algebra. For each function of propositional logic, a truth table can be compiled. The inverse problem is also always solvable. Let us introduce several definitions.

Elementary conjunctions (conjuncts) are called conjunctions of variables or their negations, in which each variable occurs at most

once.

Disjunctive normal form(DNF) is a formula that has the form of a disjunction of elementary conjunctions.

Elementary disjunctions (by clauses) are called disjunctions of variables with or without negations.

Conjunctive normal form(CNF) is a formula that has the form of a conjunction of elementary disjunctions.

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

DNF construction algorithm:

1. Go to Boolean operations using equivalent transformation formulas.

2. Go to formulas with close negatives, that is, to a formula in which negatives are located no higher than above the variables - apply de Morgan's laws.

3. Open the brackets - apply the laws of distributivity.

4. Repeating terms to take one time - the law of idempotence.

5. Apply the laws of absorption and semi-absorption.

Example 6 Find DNF formulas: .

In Boole algebra, principle of duality. It is as follows.

The function is called dual to the function if . Those. to find a function dual to a given one, it is necessary to construct the negation of the function from the negations of the arguments.

Example 7 Find the function dual to .

Among the elementary functions of the algebra of logic 1 is dual to 0 and vice versa, x is dual to x, is dual to , is dual to and vice versa.

If in the formula F 1 representing the function all conjunctions are replaced

on disjunction, disjunction on conjunction, 1 on 0, 0 on 1, then we get the formula F * , representing the function * , dual .

The conjunctive normal form (CNF) is a dual concept for DNF, so it can be easily constructed according to the scheme:

Example 8 Find CNF formulas: .

Using the result of Example 6, we have

Perfect disjunctive and perfect conjunctive normal forms. In each of the types of normal forms (disjunctive and conjunctive) one can single out a class of perfect forms of SDNF and SKNF.

A perfect elementary conjunction is a logical product of all variables with or without negation, and each variable is included in the product only once.

Any DNF can be reduced to SDNF by splitting conjunctions that do not contain all variables, i.e. addition for the missing variable x i is multiplied using the law of distributivity

Example 9 Find SDNF for DNF example 6

Perfect elementary disjunction the logical sum of all variables with or without negations is called, moreover, each variable is included in the sum only once.

Any CNF can be reduced to SKNF by adding a conjunction term that does not contain any variable X i by conjunction and applying the distributive law

Example 10 . Convert CNF to SKNF:

To construct the SKNF, you can use the scheme

Example 11. Find SKNF for the formula of example 6.

Every function has an SDNF and, moreover, the only one . Each function has a SKNF and, moreover, a single .

Because SDNF and SKNF are uniquely defined by formulas, they can be built according to the truth table of the formula.

To construct an SDNF, it is necessary to select rows in which F takes the value 1 and write down perfect elementary conjunctions for them. If the value of the variable in the desired row of the truth table is equal to one, then in the perfect conjunct it is taken without negation, if zero, then with negation. Then perfect conjuncts (their number is equal to the number of units in the table) are connected by disjunction signs.

To build SKNF according to the truth table, it is necessary to select rows in it, where F=0, and write down perfect elementary disjunctions, and then connect them with conjunction signs. If in the required row of the truth table (F=0) the value of the variable corresponds to zero, then in the perfect disjunct it is taken without negation, if it is equal to one, then with negation.

Example 12. Find SDNF and SKNF according to the truth table for the formula of example 6.

Table 14 shows only the final value F=10101101. The validity of this statement should be verified independently by constructing an expanded truth table.

Table 14

x	y	z

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

For example, is a simple conjunction,

disjunctive normal form(DNF) called disjunction simple conjunctions.

For example, the expression is DNF.

Perfect disjunctive normal form(SDNF) called such disjunctive normal the form, at which in every conjunction are included all variables given list (or themselves, or them denial), and in one And volume sameokay.

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

Similar definitions (with the substitution of conjunction for disjunction and vice versa) are true for CNF and SKNF. We present the exact formulations.

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

Conjunctival normal form(KNF) called conjunction simple disjunctions(for example, the expression - CNF).

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

For example, the expression is SKNF.

We 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 laborious than simple transformations that use a specific form of a given shape:

a) transition from DNF to CNF

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

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

b) transition from CNF to DNF

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

Thus, we got DNF.

The reverse transition (from SDNF to DNF) is related to the problem of minimizing DNF. This will be discussed in more detail in sect. 5, here we show how to simplify DNF (or SDNF) according to Blake's rule. Such a DNF is called abbreviated DNF;

c) abbreviation DNF (or SDNF) by rule Blake

The application of this rule has two parts:

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

If the added term was already contained in the DNF, then it can be discarded altogether, 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 a DNF , after applying the Blake rule to it, one can arrive at a DNF equivalent to the given one):

c) transition from DNF to SDNF

If a variable is missing in some simple conjunction, for example, z, insert the expression into it, after which we open the brackets (we do not write the repeating disjunct terms). For example:

d) transition from CNF to SKNF

This transition is carried out in a manner similar to the previous one: if some variable is missing in a simple disjunction (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 is obtained from CNF.

Note that the minimum or abbreviated CNF is usually derived from the corresponding DNF.