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 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 herself, 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.

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.

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 on 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 the value 0 only on the sets of variables in lines 2 and 6, and therefore will be the required 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:

a) ;

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

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 obtain: $ 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$.

x	y	z	$ \langle x,y,z \rangle $
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

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.

x	y	z	$ \langle x,y,z \rangle $
0	0	0	0	$(x \lor y \lor z)$
0	0	1	0	$(x \lor y \lor \neg ( z ))$
0	1	0	0	$(x \lor \neg ( y ) \lor z)$
0	1	1	1
1	0	0	0	$(\neg ( x ) \lor y \lor z)$
1	0	1	1
1	1	0	1
1	1	1	1

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

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 basic 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 the conjunction includes 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 , . . . , 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 over 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 that the sum contains at least one 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.