The conjunctive normal form of a logical function is called. Special Representations of Boolean Functions
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 elementary functions 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 | ||
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 instance,
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 that x σ is a formula x if σ = 1 and a 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 prime. 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.
Definition 1.Conjunctive monomial (elementary conjunction) from variables is called the conjunction of these variables or their negations.
for instance, is an elementary conjunction.
Definition 2.Disjunctive monomial (elementary disjunction) from variables is called the disjunction of these variables or their negations.
for instance, 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 instance,- 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 instance, – 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:
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) 
;
Let us introduce the concept of elementary disjunction.
An elementary disjunction is an expression of the form
Conjunctive Normal Form (CNF) logic function is called a 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 boolean 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.
