The principle of duality. expansion of Boolean functions in variables. perfect disjunctive and conjunctive normal forms. Laboratory work Algebra of logic functions (Boolean functions) Boolean function expansion theorem

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.

Consider the question of representation n-local boolean function f(x 1 ,x 2 ,…,x n) by some propositional algebra formula.

Let's introduce the notation, where is a parameter equal to 0 or 1.

It's obvious that

Theorem 1.1. Every function of the algebra of logicf(x 1 , x 2 ,…, x n ) for anym(1£ m £ n) can be represented in the following form:

where the disjunction is taken over all possible sets of values ​​of the variables .

Proof. Consider an arbitrary set of values ​​of all variables of a given function. Let us show that on this set the left and right parts of formula (1) take the same value. The left side is , right

because , if only , if , then the corresponding logical term can be discarded.

Comment. The representation of the function specified in the theorem is called the expansion of the function in terms of m variables .

Corollary 1(expansion in one variable).

In this case, the functions and called decomposition components.

Consequence 2(expansion in all variables).

It is obvious that if , then

So if the function f(x 1 ,x 2 ,…,x n) is not an identically false function, then it can be expressed by an equivalent formula, which is a logical sum of different products of the form , and such a representation is unique.

The form of formula (2) can be greatly simplified. It is known that any formula of the algebra of logic can be reduced by means of equivalent transformations to a formula containing only conjunction and negation or disjunction and negation. As a result of carrying out equivalent transformations, several formulas can be obtained, however, only one of them will have the following properties:

1. Each logical term contains all the variables included in the formula f(x 1 ,x 2 ,…,x n).

2. No logical term contains both a variable and its negation.

3. All logical terms in the formula are different.

4. No logical term contains the same variable twice.

These four properties are called properties of perfection(or properties of C).

If f(x 1 ,x 2 ,…,x n) is given by the truth table, then the corresponding logic algebra formula can be restored quite simply. For all argument values x 1 ,x 2 ,…,x n, at which f takes the value 1, you need to write down the conjunction of the elementary variables of the propositions, taking for the term of the conjunction x i, if x i=1, and if x i=0. The disjunction of all recorded conjunctions will be the necessary formula. About values f 0 you don't have to worry, because the corresponding term in the formula will be equal to 0 and can be discarded due to the equivalence fÚ 0 ≡ f.

For example, let the function f(x, y, z) has the following truth table:

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 form (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 expansion (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 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 Lying.

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.