Conjunctive normal form of a logical function. Conjunctive forms of representing logical functions

For any logical formula, using identity transformations, one can construct infinitely many formulas equivalent to it. In the algebra of logic, one of the main tasks is the search for canonical forms (i.e., formulas constructed according to a single rule, the 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 are distinguished (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 disjunctive normal form (DNF) if it is a disjunction of non-repeating elementary conjunctions.

The DNF is written in the following form: F 1 ∨ F 2 ∨ ... ∨ F n , where F i is the 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 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 contains 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 (PCNF)

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 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 (CPNF) if:
1) the formula is CNF, in which each elementary disjunction is a disjunction of k variables x 1, x 2, ..., x k, and in the i-th place of this disjunction there is either a 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 an SDNF or SKNF.

Algorithm for constructing SDNF using a truth table

1. Select all table rows in which the function value 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 with disjunction operations.

Algorithm for constructing SCNF using a truth table

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

Analysis of the algorithms shows that if on most of the rows of the truth table the value of the function is 0, then to obtain its logical formula it is better to construct a SDNF, otherwise - SCNF.

Example: A truth table of a logical function of three variables is given. 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 1, then we will construct the SCNF. As a result, we obtain the following logical formula:
F = (¬ x ∨ y ∨ z) ∧ (¬ x ∨ y ∨ ¬ z)

Let's check the resulting formula. To do this, we will construct a truth table for 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 constructed for the logical formula, we note that the columns of function values ​​coincide. This means that the logical function is constructed correctly.

Let us introduce the concept of an 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

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

An arbitrary logical function, defined by an analytical 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;

Using the distributivity axiom with respect to multiplication:

Uses of the absorb operation:

Exceptions in disjunctions of repeated variables or their negations;

Removing all identical elementary disjunctions except one;

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

The validity of the listed operations follows from the basic axioms and identical 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;

Using the axiom of distributivity;

Removing all identical elementary disjunctions except one.

In perfect CNF any logical function can be represented except

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

Elementary disjunctions included in a perfect CNF function are called zero constituents. Each zero constituent included in a perfect CNF vanishes on a single 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 constant of zero in perfect CNF is represented by the conjunction 2nconstituents of zero. Let us formulate a rule for compiling the SCNF of a logical function using a correspondence table.

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

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

For the first row of the table, which corresponds to the zero set of the function 000, we find the constituent of zero. Having performed similar operations for the second, third and fifth lines, we determine the required 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 SCNF and vice versa.

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

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

Normal form comes 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 (PCNF) is a CNF that satisfies three conditions:

does not contain identical elementary disjunctions;

none of the disjunctions contain the same variables;

each elementary disjunction contains each variable included in a given CNF.

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

Rules for constructing SKNF using a truth table

For each set of variables for which the function is equal to 0, the sum is written down, and variables that have a value of 1 are 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 included in a given DNF, and in the same order.

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

Rules for constructing SDNF using a truth table

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

Examples of finding SCNF and SDNF

Example 1

Write a logical function using its truth table:

Picture 1.

Solution:

Let's use the rule for constructing SDNF:

Figure 2.

We get SDNF:

Let's use the rule for constructing the SCNF.

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 basic 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 that by x σ we 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 the 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 makes it possible 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 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.