Decomposition of boolean functions in variables. Lab Algebra of Logic Functions (Boolean Functions) 5.4 Decomposition of Functions in Variables Normal Forms

Then the function f(x 1, x 2, x 3) can be represented as a disjunction of two functions of two variables, and this formula will look like:

Consider the following formulas:

The left side of the first formula is equivalent to the right one, since for x 1 =0 and in accordance with the conjunction operation. The validity of the second formula can be shown similarly. Thus, putting these formulas in the previous disjunction, we get:

This expression is called the expansion of the function f(x 1 ,x 2 ,x 3) with respect to the variable x 1 .

Now, similarly, we can expand the functions f(0,x 2 ,x 3) and f(1,x 2 ,x 3) in x 2 . Get

Substituting these formulas into the previous ones, we get

In accordance with the distributivity of the operation &, we introduce the variable x 1 and its inversion into brackets, we get

In general, for a function f(x 1 ,x 2 ,..,x n) of n variables, the expansion in m variables (m £ n) has the form

where the disjunction is taken over all 2 m sets of variables x 1 ,x 2 ,..,x m .

Consider the decomposition (*4) in the extreme case when m=n. (see example (*3)).

Then in all conjunctions the values ​​of the function f on each fixed set have values ​​equal to zero or one. Removing all zero conjunctions, we obtain a new decomposition, and in this new decomposition we remove the factors of functions in the conjunctions, because they are equal to 1. The remaining expression is called CDNF (perfect disjunctive normal form).

Let's do all this for example (*3).

After removing from (*3) conjunctions with zero values ​​of the function f on the given sets, we get:

Since according to the truth table

f(0,0,0) = f(0,1,0) = f(1,1,0) = f(1,1,1)=1

then from the conjunctions we remove the factors of the functions, after which we get:

This is the perfect disjunctive normal form of the Boolean function f.

Lemma. Any Boolean function (except for the constant "0") has a PDNF, and only one.

Similarly, you can enter the conjunctive form,

Construction of SDNF for a function given by a table

This corollary is constructive, since according to the function table, it allows you to construct a formula that is SDNF (if ).
sdnf functions f contains exactly as many conjunctions as there are ones in the table f; to each “single” set (d 1 ,…,d n), those. the set on which the value of the function is equal to 1 corresponds to the conjunction of all variables in which x i taken with a negative if d i=0, and without negation if d i =1.

The set B, on which two binary operations (conjunction and disjunction) and one unary operation (negation) are defined and two elements 0 and 1 are allocated, is called a Boolean algebra.

Moreover, for these operations, the following properties must be met:

Associativity

commutativity

Distributivity of conjunction with respect to disjunction

Distributivity of disjunction with respect to conjunction

Idempotency

Twice no

Constant properties

De Morgan rules

Law of contradiction

Law of the excluded middle

In the algebra of logic, these laws are called equivalences.

Perfect normal forms

Perfect disjunctive normal form

Let us introduce the notation:

; A A =1; X A =1 if X=A, X A =0 if XA.

The formula X A 1…… X A n , where A=- any binary set, and among the variables Xi may be the same is called an elementary conjunction.

Any disjunction of elementary conjunctions is called a disjunctive normal form (DNF).

An elementary conjunction is called correct if each variable occurs at most once in it (including its occurrence under the negation sign).

For example: 1) (the conjunction icon is omitted in this case).

1),4) are regular elementary conjunctions;

2) - the variable x enters once by itself and the second time under the sign of negation;

The variable y appears three times: once by itself and twice under the negation sign.

A correct elementary conjunction is called complete with respect to the variables x 1 ... .. x n if it includes each of these variables and only once (there may also be a negation sign).

For example: of the conjunctions listed in the previous example, only 4) are complete with respect to the variables x, y, z, t; and with respect to the variables x,y,z only 1 is complete).

A perfect disjunctive normal form (PDNF) with respect to the variables x 1 .....x n is a disjunctive normal form in which there are no identical elementary conjunctions and all elementary conjunctions are correct and complete with respect to the variables x 1 .....x n

Variable expansion

Theorem 1. Any logical function can be represented in SDNF:

where m, and the disjunction is taken over all 2 m sets of values ​​of the variables x 1 ,…x m . The function f is expanded in the first n-variables. This equality is called expansion in variables. x 1 ,… x m . For example, for n=4, m=2, the decomposition looks like:

the theorem is proved by substituting an arbitrary set (b 1 ,…,b m , b m+1 ,…,b n) of all n-variables into both sides of equality (1).

For m = 1, from (1) we obtain the expansion of the function in one variable:

Obviously, a similar expansion is valid for any of the n-variables.

Another important case is when n=m. In this case, all variables on the right side of (1) get fixed values ​​and the functions in the conjunction of the right side become equal to 0 or 1, which gives:

where the disjunction is taken over all sets (b 1 …b n) on which f=1. For f=0, the set of conjunctions on the right side is empty. Such a decomposition is called a perfect disjunctive normal form. The SDNF of the function f contains exactly as many conjunctions as there are ones in the truth table of f. Each unit set (b 1 ,…, b n) corresponds to the conjunction of all variables, in which x i is taken with negation if b i =0 b , and without negation if b i =1. Thus, there is a one-to-one correspondence between the truth table of the function f and its SDNF, and, therefore, the SDNF for any logical function is unique. The only function that doesn't have an SDNF is the constant 0.

Theorem 2. Any logical function can be represented as a Boolean formula.

Indeed, for any function, except for the constant 0, its SDNF can serve as such a representation. The constant 0 can be represented by a Boolean formula.

Decomposition of boolean functions in variables.

Let G be a parameter equal to 0 or 1. Let us introduce the notation:

It is easy to check by checking that x G = 1 if and only if x= G. It follows that the conjunction is equal to 1 (here G is equal to 0 or 1) if and only if . For example, the conjunction (in which G 2 \u003d G 1 \u003d 0, G 3 \u003d G 4 \u003d 1) is 1 only if x 1 = x 2 = 0, x 3 = x 4 = 1.

Theorem 1Any Boolean function f(x 1 ,x 2 ,…,x n) must be represented in the following form:

where 1 ≤ k ≤ n, in the disjunction is taken over all sets of variable values.

This representation is called the expansion of the function in terms of variables. For example, for n = 4, k = 2, expansion (3.1) has the form:

.

Let us prove the expansion (3.1). To do this, take an arbitrary set of variable values . Let us show that the left and right sides of relation (3.1) take on the same value. Indeed, since x G = 1 if and only if x= G, then among 2 only one conjunction of the right-hand side of (3.1) turns to unity, in which . All other conjunctions are equal to zero.

For this reason . As a corollary of expansion (3.1), we obtain the following two special expansions.

Variable expansion x n:

If the Boolean function is not a constant 0, then the expansion is valid

Expansion in all variables:

, (3.3)

where the disjunction is taken over all sets , for which the value of the function equals 1.

Decomposition (3.3) is usually called the perfect disjunctive normal form (abbreviated notation SDNF) of the function.

Decomposition (3.3) gives a way to construct an SDNF. To do this, in the truth table, mark all the rows , in which . For each such row, we form a conjunction and then connect all the resulting conjunctions with a disjunction sign.

Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, there is a one-to-one correspondence between the truth table of a function and her SDNF. And this means that the SDNF for the Boolean function is unique.

A single boolean function that does not have a sdnf is the constant 0.

Example 1 Find the perfect disjunctive form for a function .

Let's make a truth table for this function:

From here we get: = = .

An important role in the algebra of logic is played by the following decomposition of Boolean functions.

Theorem 2Any boolean function must be presented in the following form:

where 1≤k≤n, and the conjunction is taken over all 2 k sets of variable values.

Indeed, let is an arbitrary set of variable values. Let us show that the left and right parts of relation (3.4) take on the same value. Since only when , then among 2 k disjunctions on the right-hand side of (3.4) only one vanishes, in which . All other disjunctions are equal to 1.

For this reason = = .

Expansions of Boolean functions follow directly from expansion (3.4):

The last decomposition is called the perfect conjunctive normal form (CKNF). Decomposition (3.6) gives a way to construct the SKNF. To do this, in the truth table, we mark all the lines in which. For each such row, we form a disjunction and then we connect all the resulting conjunctions with a conjunction sign. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, there is a one-to-one correspondence between the truth table of a function and her SKNF. And this means that the SKNF for the Boolean function is unique.

The only boolean function that does not have SKNF is the constant 1.

Example 2 Find the perfect conjunctive normal form for a function .

Let's make a truth table for this function.

From here we get SKNF

Form formula (short notation), where - conjunctions called disjunctive normal form (DNF).

By virtue of the above definition of DNF, there will be, for example, expressions: , .

As noted in paragraph 2.2, all logical operations can be reduced to three: conjunctions, disjunctions and denials. Moreover, in view of de Morgan's law, the negation sign can be assumed to apply only to variables.

Now, using the distributive law, we open the brackets and get the disjunctive normal form. So, the following theorem is true.

Theorem 3 For any formula of the algebra of logic, there exists a disjunctive normal form equivalent to it.

The proof of this theorem gives a way to construct a disjunctive normal form for any formula in the algebra of logic.

Example 3 Find the disjunctive normal form for the following formula: .

Excluding sign by law and applying the laws of de Morgan and double negation, we get:

Then, applying the law of distributivity, we expand the brackets

The last expression is the disjunctive normal form.

View shape (short notation), where are disjunctions called conjunctive normal form (CNF).

These are, for example, expressions:

, .

As shown above, for any formula of the algebra of logic there exists a disjunctive form equivalent to it. Using the distributive law , it is easy to obtain a CNF from a given DNF.

So, the following theorem is true.

Theorem 4 For any formula of the algebra of logic, there exists a conjunctive normal form equivalent to it.

The proof of this theorem gives a way to construct a conjunctive normal form for any formula in the algebra of logic.

Example 4 Find disjunctive and conjunctive normal forms for the following formula: .

Using the law , we exclude the sign . We get the formula.

Using de Morgan's law, we obtain the formula . Expanding the brackets, we obtain the disjunctive normal form

.

To get the conjunctive normal form, apply to the formula distributive law, we get:

The last expression is the conjunctive normal form. Since and , the resulting CNF is equivalent to the following CNF:

Among all the normal formulas of this formula, we single out the perfect normal form, both disjunctive and conjunctive. Considering decomposition (3), it is easy to see that the perfect disjunctive normal form of a formula of the algebra of logic containing exactly n distinct variables is its disjunctive normal form, in which:

1) all conjunctions are pairwise distinct;

2) each conjunction contains exactly n variables;

3) in each conjunction there are all n variables.

In Example 1, we have considered one of the ways to construct an SDNF based on the compilation of a truth table. The next way to construct SDNF is based on the application of the laws of the algebra of logic.

Example 5 Find the perfect disjunctive form of the formula .

Using that , we get . In view of de Morgan's laws and double negation, we have obtained a disjunctive normal form. This DNF is equivalent to the formula .

Expanding the brackets, we get: .

Using the law of idempotency, we obtain the required SDNF:

Taking into account the decomposition (3.6), it is easy to see that the perfect conjunctive normal form of the formula of the algebra of logic containing exactly n different variables, there is its conjunctive normal form, in which:

1) all disjunctions are pairwise distinct;

2) each disjunction contains exactly n members; identically true, if it, for all values ​​of the variables included in it, takes on the value true.

Examples of identically true formulas are the formulas:

identically false, if it, with all the values ​​of the variables included in it, takes on the value False.

Examples of identically false formulas are the formulas:

The formula of the algebra of logic is usually called doable, if for some values ​​of the variables included in it, it takes the value true.

Examples of feasible formulas are the following formulas:

In the algebra of logic, one can pose the following problem: to indicate a method (algorithm) that allows for each formula of the algebra of logic to find out whether it is identically true or not. The task is called resolution problems.

Consider the following two ways to solve this problem.

Method 1 (table) In order to determine whether a given formula is identically true or not, it is sufficient to compile its truth table.

At the same time, this method, although it provides a fundamental solution to the solvability problem, is rather cumbersome.

Method 2 based on the reduction of formulas to normal form.

Theorem 4A formula of the algebra of logic is identically true if and only if every disjunction in its conjunctive normal form contains some variable together with its negation.

Indeed, if each disjunction in conjunctive normal form contains a variable together with its negation, then all disjunctions are equal to 1, because , . It follows that CNF is identically true.

Let now the given formula be identically true, and let there is some disjunction in the CNF of this formula. Let us assume that the given disjunction does not contain a variable together with its negation. In this case, we can give the value 0 to each variable that is not under the negation sign, and the value 1 to each variable that is under the negation sign. After this substitution, all disjunctions will become equal to 0, therefore, the formula is not identically true. We got a contradiction.

Example 7 Find out if the formula is identically true

.

Using that , we get .

Applying the distributivity law, we obtain CNF:

Since every disjunction contains some variable along with its negation, the formula is identically true.

Similarly to the previous theorem, the following theorem is proved:

Theorem 5A formula of the algebra of logic is identically false if and only if every conjunction in its disjunctive form contains some variable together with its negation.

Decomposition of boolean functions in variables. - concept and types. Classification and features of the category "Decomposition of Boolean functions in variables." 2017, 2018.