Logic function is a function in which variables take only two values: logical one or logical zero. The truth or falsity of complex propositions is a function of the truth or falsity of simple ones. This function is called the Boolean judgment function f (a, b).

Any logical function can be specified using a truth table, on the left side of which a set of arguments is written, and on the right side - the corresponding values ​​of the logical function.

When constructing a truth table, it is necessary to take into account the order in which logical operations are performed. Operations in a logical expression are performed from left to right, taking into account parentheses, in the following order:

• 1. inversion;
• 2. conjunction;
• 3. disjunction;
• 4. implication and equivalence.

To change the specified order of logical operations, parentheses are used.

The following is proposed truth table construction algorithm.

• 1. Define number of sets of input variables- all possible combinations of values ​​of variables included in expressions, according to the formula: Q=2 n, where n is the number of input variables. It determines the number of rows in the table.
• 2. Enter all sets of input variables into the table.
• 3. Determine the number of logical operations and the sequence of their execution.
• 4. Fill in the columns with the results of performing logical operations in the indicated sequence.

In order not to repeat or miss any possible combination of values ​​of input variables, you should use one of the methods suggested below for filling out the table.

Method 1. Each set of values ​​of the source variables is a number code in the binary number system, and the number of digits of the number is equal to the number of input variables. The first set is the number 0. By adding 1 to the current number each time, we get the next set. The last set is the maximum value of the binary number for a given code length.

For example, for a function of three variables, the sequence of sets consists of numbers:

Method 2. For a function of three variables, the data sequence can be obtained as follows:

• a) divide the column of values ​​of the first variable in half and fill the upper half with zeros, the lower half with ones;
• b) in the next column for the second variable, divide the half in half again and fill it with groups of zeros and ones; fill the other half in the same way;
• c) do this until the groups of zeros and ones consist of one character.

Method 3. Use the known truth table for the two arguments. When adding a third argument, first write the first 4 rows of the table, combining them with the value of the third argument equal to 0, and then write the same 4 rows again, but now with the value of the third argument equal to 1. As a result, the table for three arguments will be 8 lines:

For example, let's build a truth table for a logical function:

The number of input variables in a given expression is three (A,B,C). This means that the number of input sets Q=2 3 =8 .

The columns of the truth table correspond to the values ​​of the original expressions A,B,C, intermediate results and ( B V C), as well as the desired final value of a complex arithmetic expression:

• 0 0 0 1 0 0
• 0 0 1 1 1 1
• 0 1 0 1 1 1
• 0 1 1 1 1 1
• 1 0 0 0 0 0
• 1 0 1 0 1 0
• 1 1 0 0 1 0
• 1 1 1 0 1 0
• 7.4. Logical functions and their transformations. Laws of logic

For the operations of conjunction, disjunction and inversion, the laws of Boolean algebra are defined, allowing identical (equivalent) transformations of logical expressions.

Laws of logic

• 1. ¬¬A
• 2. A&B
• 3.AVB
• 4. A&(B&C)
• 5.AV(BVC)
• 6. A&(BVC)
• 7.AV(B&C)
• 8. A&A
• 9.AVA
• 10. AV¬A
• 11. A&¬A
• 12. A&I
• 13. AVI
• 14. A&L
• 15. AVL
• 16.¬(A&B)
• 17.¬(AVB)
• 18. A => B

Based on the laws, it is possible to simplify complex logical expressions. This process of replacing a complex logical function with a simpler but equivalent one is called function minimization.

Example 1. Simplify the expressions so that the resulting formulas do not contain the negation of complex statements.

Solution

Example 2. Minimize function

To simplify the expression, the absorption and adhesion formulas were used.

Example 3. Find the negation of the following statement: “If the lesson is interesting, then none of the students (Misha, Vika, Sveta) will look out the window.”

Solution

Let us denote the statements:

Y- “The lesson is interesting”;

M- “Misha looks out the window”;

B- “Vika looks out the window”;

C- "Sveta is looking out the window."

When simplifying the expression, the formula for replacing operations and De Morgan's law were used.

Example 4. Determine the participant in the crime based on two premises: logical computer table

• 1) “If Ivanov did not participate or Petrov participated, then Sidorov participated”;
• 2) “If Ivanov did not participate, then Sidorov did not participate.”

Solution

Let's make up the expressions:

I- “Ivanov participated in the crime”;

P- “Petrov participated in the crime”;

S- "Sidorov participated in the crime."

Let's write the premises in the form of formulas:

Let's check the result using the truth table:

Answer: Ivanov participated in the crime.

Constructing a logical function from its truth table

We learned how to create a truth table for a logical function. Let's try to solve the inverse problem.

Consider the rows where the truth value of the function Z is true (Z=1). The function for this truth table can be written as follows: Z(X,Y) = (¬ X& ¬Y)V(X& ¬Y).

Each line where the function is true (equal to 1) corresponds to a bracket representing a conjunction of arguments, and if the value of the argument is O, then we take it with negation. All brackets are connected to each other by a disjunction operation. The resulting formula can be simplified by applying the laws of logic:

Z(X,Y)<=>((¬X& ¬Y) VX)&((¬X&Y)V ¬Y)<=>(XV(¬X& ¬Y)) &(¬YV(¬X&¬Y))<=>((XV¬X)&(XV ¬Y))&((Y¬V ¬X)&(¬YV ¬Y))<=>(1&(XV ¬Y))&((¬YV ¬X)& ¬Y)<=>(XV ¬Y)&((¬YV ¬X)& ¬Y).

Check the resulting formula: create a truth table for the function Z(X,Y).

Write down the rules for constructing a logical function using its truth table:

• 1. Select those rows in the truth table in which the function value is equal to 1.
• 2. Write down the required formula in the form of a disjunction of several logical elements. The number of these elements is equal to the number of selected lines.
• 3. Write each logical element in this disjunction as a conjunction of function arguments.
• 4. If the value of any function argument in the corresponding row of the table is 0, then we take this argument with a negation.

1. Determine the procedure.

2. Determine the dimension of the truth table.

The number of columns is determined by the number of logical variables (there are two of them, A, B) and the number of actions (there are also two of them).

4. Formulate an answer.
The last column has one "0", corresponding to A equal to "1" and B equal to "0". It turns out that this function is false if and only if the logical variable A is true and the logical variable B is false, which corresponds to the logical function CONSEQUENCE.
This means that this function is equal to the logical consequence of the variables A and B: If A, then B.

Create a truth table for a logical function:

1. Determine the procedure.

2. Determine the dimension of the truth table.

The "header" of the table contains two lines - action numbers and logical operations of the actions.
The number of columns is determined by the number of logical variables (there are two A, B) and the number of actions (there are five).
The number of rows in the table is equal to two to the power equal to the number of logical variables - in the case of two variables, 4 rows are obtained.
3. Fill in the table columns one by one in accordance with the logical function of a given column.


4. Formulate an answer.
In the last column, “1” corresponds to A equal to B, and “0” to A not equal to B. It turns out that this function is true when A is equal to B and false when A is not equal to B, which corresponds to the logical function IDENTITY.
This means that this function is equal to the logical IDENTITY of the variables A and B: A is identical to B.

Computer science: personal computer hardware Yashin Vladimir Nikolaevich

4.3. Logical functions and truth tables

The relationships between logical variables and logical functions in the algebra of logic can also be displayed using the corresponding tables, which are called truth tables. Truth tables are widely used because they clearly show what values ​​a logical function takes for all combinations of values ​​of its logical variables. The truth table consists of two parts. The first (left) part refers to logical variables and contains a complete list of possible combinations of logical variables A, B, C... etc. The second (right) part of this table defines the output states as a logical function of combinations of input quantities.

For example, for a logical function F=A v B v C(disjunctions) of three logical variables A, B, And WITH the truth table will have the form shown in Fig. 4.1. To record the values ​​of logical variables and logical functions, this truth table contains 8 rows and 4 columns, i.e. the number of lines for recording the values ​​of arguments and functions of any truth table will be equal to 2n, Where P - the number of arguments of a logical function, and the number of columns is n + 1.

Rice. 4.1. Truth table for a logical function F=A v IN v C

A truth table can be compiled for any logical function, for example, in Fig. 4.2 shows the truth table of a logical function F=A? B? C(equivalences).

Logical functions have corresponding names. For two binary variables, there are sixteen logical functions, the names of which are given below. In Fig. 4.3 presents a table showing logical functions F 1, F 2, F 3, … , F 16 two logical variables A And IN.

Function F 1 = 0 and is called the zero constant function, or zero generator.

Rice. 4.2. Truth table for a logical function F=A? B? C

Rice. 4.3. Logical functions F 1, F 2, F 3,… F 16 of two arguments A And IN

Function F 2 = A & B called the conjunction function.

A.

Function F 4 = A A.

called the ban function on a logical variable IN.

Function F 6 = B called the function of repetition by logical variable IN.

called the exclusive OR function.

Function F 8 = A v B called the disjunction function.

called the Peirce function.

called the equivalence function.

IN.

Function F 12 = B? A B? A.

called the negation (inversion) function of a logical variable A.

Function F 14 = A? B called the implication function A? B.

called the Schaeffer function.

Function F 16 = 1 is called generator function 1.

Among the logical functions of variables listed above, there are several logical functions that can be used to express other logical functions. The operation of replacing one logical function with another in the algebra of logic is called the operation of superposition or the superposition method. For example, the Schaeffer function can be expressed using the logical functions of disjunction and negation using De Morgan's law:

Logical functions that can be used to express other logical functions by superposition are called basic logical functions. Such a set of basic logical functions is called a functionally complete set of logical functions. In practice, three logical functions are most widely used as such a set: conjunction, disjunction and negation. If a logical function is represented using basic functions, then this form of representation is called normal. In the previous example, the Schaeffer logical function, expressed in terms of base functions, is represented in normal form.

Using a set of basic functions and the corresponding technical devices that implement these logical functions, you can develop and create any logical device or system.

Rice. 4.4. Function Wizard - Step 1 of 2 Dialog Box

As can be seen from Fig. 4.4, as part of the logical functions of the program MS Excel includes a functionally complete set of logical functions, consisting of the following logical functions: AND (conjunction), OR (disjunction), NOT (negation). Thus, using a functionally complete set of logical functions of the program MS Excel other functions can be implemented. Logical IF function (implication), also included in logical functions MS Excel, performs a logical check and, depending on the result of the check, performs one of two possible actions. In this program, it has the following format: = IF (arg1;arg2;arg3), where arg1 is a logical condition; arg2 – return value provided that the value of argument arg1 is true (TRUE); arg3 is the return value provided that the value of arg1 is not true (FALSE). For example, if in an arbitrary cell of the program sheet MS Excel enter the expression “=IF (A1 = 5; “five”; “not five”)”, then when entering the number 5 in cell A1 and pressing the “Enter” key, the word “five” will be automatically written in cell A1, when entering any other number in cell A1 the word “not five” will be written in it. As already noted, using the logical functions of the program MS Excel is possible present other logical functions and their corresponding truth tables.

Using the logical functions IF and AND, we implement a modified truth table of a logical function F = A & B(conjunction), consisting of two rows and three columns, which allows when changing the values ​​(0 or 1) of logical variables A and B automatically set, for example, in cell E6 the value of the function F = A & B, corresponding to the values ​​of these logical variables. To do this, enter the following expression in cell E6: “=IF(AND(C6;D6);1;0)”, then when you enter the values ​​0 or 1 in cells C6 and D6, a logical function will be executed in cell E6 F = A & B. The result of these actions is shown in Fig. 4.5.

Rice. 4.5. Implementation of a modified truth table of a logical function F = A & B

This text is an introductory fragment. From the book Computer Science and Information Technologies: Lecture Notes author Tsvetkova A V

1. Logical commands Along with the means of arithmetic calculations, the microprocessor command system also has means of logical data conversion. By logical we mean such data transformations, which are based on the rules of formal

From the book Computer 100. Starting with Windows Vista author Zozulya Yuri

Logical functions in Excel When making calculations, you often have to choose a formula depending on specific conditions. For example, when calculating wages, different bonuses may be applied depending on length of service, qualifications or specific working conditions that are calculated

From an Excel workbook. Multimedia course author Medinov Oleg

Logical functions Logical functions can be used in mathematical, engineering calculations, or comparative data analysis. We will look at one logical function using the IF function as an example. Using the IF function, you can create a logical expression and

From the book Computer Science: Personal Computer Hardware author Yashin Vladimir Nikolaevich

4.1. Logical variables and logical operations Information (data, machine instructions, etc.) in a computer is represented in a binary number system, which uses two digits - 0 and 1. An electrical signal passing through electronic circuits and connections

From the book PHP Reference by the author

Boolean functions for determining the type of a variable is_scalar Tests whether a variable is simple. Syntax: bool is_scalar(mixed var) Returns true if var is of a scalar type (chils, strings, booleans) but not complex (arrays or objects). is_null Tests whether

From the book HTML 5, CSS 3 and Web 2.0. Development of modern Web sites author Dronov Vladimir

Logical Operators Logical operators perform operations on logical values. All of them are given in table. 14.5. And in the table Figures 14.6 and 14.7 show the results of executing these operators. The main area of ​​application of logical operators is comparison expressions (for more information, see

From the XSLT book author Holzner Stephen

XPath Boolean Functions XPath also supports the following set of Boolean functions: boolean(). Reduces the argument to a logical value; false(). Returns false; lang(). Checks whether the language set in the xml:lang attribute matches the language passed to the function; not().

From the book XSLT Technology author Valikov Alexey Nikolaevich

Logical Operators There are two logical operators in XSLT - or and and. These operations are binary, that is, each of them is defined for two operands. If the operands are not Boolean values, they are implicitly cast to Boolean type. The semantics of or and and are obvious - they

From the book C Programming Language for a Personal Computer author Bochkov S. O.

Logical operations Logical operations perform the logical functions AND (&&) and OR (||) on their operands. The operands of logical operations can be of integer type, floating type, or pointers. The types of the first and second operands may differ. Always first

From the book A Brief Introduction to Bash Programming author Rodriguez Harold

Logical AND and OR You've already seen what control structures are and how to use them. There are two more ways to solve the same problems. These are logical AND - "&&" and logical "OR" - « || " Logical AND is used as follows: expression_1&&expression_2 First

From the book Firebird DATABASE DEVELOPER'S GUIDE by Borri Helen

Logical Operators Firebird provides three logical operators that can operate on other predicates in different ways. * NOT specifies the negation of the search term to which it applies. It has the highest priority.* AND creates a complex predicate, combining two

From the book The C Language - A Guide for Beginners by Prata Steven

Understanding truth and falsity Semantically, if a predicate returns "uncertain", it is neither true nor false. In SQL, statements are only resolved as true or false - a statement that does not evaluate to true is treated as

From the book Data Recovery 100% author Tashkov Petr Andreevich

IV. Logical Operators Typically, logical operators "treat" conditional expressions as operands. Operation! has one operand located on the right. The remaining operations have two operands: one on the left and one on the right. && Logical AND: the result of the operation is true,

From the C++ book for beginners by Lippman Stanley

Logical violations If the drive is physically healthy, but appears as empty or unformatted, and the data on it is not visible to the operating system, then in this case the file system service tables are damaged. The data almost always remains on

From the book Description of the PascalABC.NET language author RuBoard Team

12.3.4. Logical function objects Logical function objects support the operations "logical AND" (returns true if both operands are true - uses the && operator associated with the Type type), "logical OR" (returns true if at least one of the operands is equal to true, –

From the author's book

Logical operations The logical operations include the binary operations and, or and xor, as well as the unary operation not, which have operands of type boolean and return a value of type boolean. These operations follow the standard rules of logic: a and b is true only if a and b are true, a or b is true

Select the lines where
and write down the conjunctions of all variables, whereby, if a variable in this set is equal to 1, then we write it itself, and if the variable = 0, then its negation.

For this example

the conjunction of these disjunctions will be the desired formula:

Definition: Conjunction called elementary, if all the variables included in it are different. The number of letters included in an elementary conjunction or elementary disjunction is called rank.

The number 1 is considered an elementary conjunction of rank 0. A variable is considered an elementary conjunction or an elementary disjunction of rank 1. The number 0 is considered an elementary disjunction of rank 0. Any conjunction of variables that is not identically false can be reduced to an elementary form, and any disjunction of letters that is not identically true , can also be reduced to elementary form. To do this, we need to apply the properties of commutativity, idempotency and associativity of conjunction and disjunction.

It has been rigorously proven that any Boolean algebra formula can be expressed using the operations , &, . Intuitively, this fact is obvious; let us recall the algorithm for composing a formula using a truth table. In this case, we use only these operations. This form of recording is called disjunctive normal form(DNF). This is a kind of mechanism for normalizing logic algebra formulas.

Definition: DNF is a disjunction of various elementary conjunctions (i.e., each conjunction consists of elementary statements or their negations).

CNF is defined similarly - conjunctive normal form.

Definition: If in a DNF all elementary conjunctions have the same rank, equal to the number of variables on which the DNF depends, then it is called perfect (SDNF).

Theorem. For any function that is not identically false, there exists a unique SDNF.

Consequence . Any Boolean function that is not identically false can be represented as a superposition &,,, and the negation applies only to variables.

Definition: A system of logical operations is called functionally complete if, using these operations and constants of this system, any function of Boolean algebra can be represented.

Systems (&,,); (,); (&,),(/) – are functionally complete

(&,) – functionally incomplete.

We will accept these facts without proof, and when solving problems, we will try to represent any formula using (&,,). Later we will discuss in more detail the issue of functional completeness and incompleteness of the system of operations.

Topic 1.7. Methods for simplifying logical expressions. Methods for solving logical problems.

Let's consider an example of solving a logical problem.

Example :

After discussing the composition of the expedition participants, it was decided that two conditions must be met.

If Arbuzov goes, then Bryukvin or Vishnevsky should go

If Arbuzov and Vishnevsky go, then Bryukvin will go

Draw up a logical formula for decision-making in symbolic form, simplify the resulting formula and formulate a new condition for forming an expedition based on it.

Let us introduce variables and the corresponding elementary statements.

- Arbuzov will go

- Bryukvin will go

- Vishnevsky will go

Then the developed conditions for the formation of the expedition will look like this:

Let's create a general formula and simplify the expression

those. if Arbuzov goes, then Bryukvin will go.

Example:

If the weather is good tomorrow, we will go to the beach or go to the forest. Let's create a formula for our behavior for tomorrow.

- good weather

- we will go to the beach

- we'll go to the forest

Now let's construct the negation of this phrase

That. we will receive the statement “Tomorrow the weather will be good, and we will not go to the forest or to the beach.

Anyone can build a truth table and check this statement.

Example :

Brown, John and Smith were detained on suspicion of the crime. One of them is a respected old man in the city, the second is an official, and the third is a well-known swindler. During the investigation, the old man told the truth, the swindler lied, and the third detainee told the truth in one case and lied in the other.

Here's what they said:

Brown: I did it. It's not John's fault. (B&D)

John: It's not Brown's fault. Criminal Smith. (B&S)

Smith: It's not my fault. Blame Brown (S&B)

Let us describe these statements formally:

Brown committed the crime

John committed the crime

- Smith committed the crime

Then their words are described by the following expressions:

Brown:

John:

Smith:

Because according to the conditions of the problem, two of these are false and one is true, then

Let's create a truth table

Only case 2 remains, i.e. criminal Smith, and both of his statements are false.

hence - false and - true

= 1 – John is a respected old man

It remains that Brown is an official, and since - false, then – true.

Using the laws and identities of Boolean algebra, you can simplify logical expressions.

Example :

Exercise:

Purpose of the service. The online calculator is designed for constructing a truth table for a logical expression.
Truth table – a table containing all possible combinations of input variables and their corresponding output values.
The truth table contains 2n rows, where n is the number of input variables, and n+m are columns, where m are output variables.

Instructions. When entering from the keyboard, use the following notations: For example, the logical expression abc+ab~c+a~bc must be entered like this: a*b*c+a*b=c+a=b*c
To enter data in the form of a logical diagram, use this service.

Rules for entering a logical function

1. Instead of the v (disjunction, OR) symbol, use the + sign.
2. There is no need to specify a function designation before a logical function. For example, instead of F(x,y)=(x|y)=(x^y) you need to simply enter (x|y)=(x^y) .
3. The maximum number of variables is 10.

The design and analysis of computer logic circuits is carried out using a special branch of mathematics - logic algebra. In the algebra of logic, three main logical functions can be distinguished: “NOT” (negation), “AND” (conjunction), “OR” (disjunction).
To create any logical device, it is necessary to determine the dependence of each of the output variables on the existing input variables; this dependence is called a switching function or a logic algebra function.
A logical algebra function is called completely defined if all 2n of its values ​​are given, where n is the number of output variables.
If not all values ​​are defined, the function is called partially defined.
A device is called logical if its state is described using a logic algebra function.
The following methods are used to represent a logical algebra function:

• verbal description is a form that is used at the initial design stage and has a conditional representation.
• description of a logic algebra function in the form of a truth table.
• description of a logic algebra function in the form of an algebraic expression: two algebraic forms of FAL are used:
  A) DNF – disjunctive normal form is the logical sum of elementary logical products. DNF is obtained from the truth table using the following algorithm or rule:
  1) in the table, those rows of variables are selected for which the output function =1.
  2) for each line of variables, a logical product is written; Moreover, variables =0 are written with inversion.
  3) the resulting product is logically summed up.
  Fdnf= X 1 *X 2 *X 3 ∨ X 1 x 2 X 3 ∨ X 1 X 2 x 3 ∨ X 1 X 2 X 3
  A DNF is said to be perfect if all variables have the same rank or order, i.e. Each work must include all variables in direct or inverse form.
  b) CNF – conjunctive normal form is a logical product of elementary logical sums.
  CNF can be obtained from the truth table using the following algorithm:
  1) select sets of variables for which the output function =0
  2) for each set of variables we write an elementary logical sum, and the variables =1 are written with inversion.
  3) the resulting amounts are logically multiplied.
  Fsknf=(X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3)
  CNF is called perfect, if all variables have the same rank.

In algebraic form, you can build a circuit of a logical device using logical elements.

Figure 1 - Logic device diagram

All operations of the algebra of logic are defined truth tables values. The truth table determines the result of an operation for everyone is possible x logical values ​​of the original statements. The number of options reflecting the result of applying operations will depend on the number of statements in the logical expression. If the number of statements in a logical expression is N, then the truth table will contain 2 N rows, since there are 2 N different combinations of possible argument values.

Operation NOT - logical negation (inversion)

A logical operation is NOT applied to a single argument, which can be a simple or complex logical expression. The result of the operation is NOT the following:

• if the original expression is true, then the result of its negation will be false;
• if the original expression is false, then the result of its negation will be true.

The following conventions are NOT accepted for the negation operation:
not A, Ā, not A, ¬A, !A
The result of the negation operation is NOT determined by the following truth table:

A	not A
0	1
1	0

The result of the negation operation is true when the original statement is false, and vice versa.

OR operation - logical addition (disjunction, union)

The logical OR operation performs the function of combining two statements, which can be either a simple or a complex logical expression. Statements that are the starting points for a logical operation are called arguments. The result of the OR operation is an expression that will be true if and only if at least one of the original expressions is true.
Designations used: A or B, A V B, A or B, A||B.
The result of the OR operation is determined by the following truth table:
The result of the OR operation is true when A is true, or B is true, or both A and B are true, and false when the arguments A and B are false.

Operation AND - logical multiplication (conjunction)

The logical operation AND performs the function of intersection of two statements (arguments), which can be either a simple or a complex logical expression. The result of the AND operation is an expression that will be true if and only if both original expressions are true.
Designations used: A and B, A Λ B, A & B, A and B.
The result of the AND operation is determined by the following truth table:

A	B	A and B
0	0	0
0	1	0
1	0	0
1	1	1

The result of the AND operation is true if and only if statements A and B are both true, and false in all other cases.

Operation “IF-THEN” - logical consequence (implication)

This operation connects two simple logical expressions, of which the first is a condition, and the second is a consequence of this condition.
Designations used:
if A, then B; A entails B; if A then B; A→B.
Truth table:

A	B	A → B
0	0	1
0	1	1
1	0	0
1	1	1

The result of the implication operation is false only if premise A is true and conclusion B (consequence) is false.

Operation “A if and only if B” (equivalence, equivalence)

Designation used: A ↔ B, A ~ B.
Truth table:

A	B	A↔B
0	0	1
0	1	0
1	0	0
1	1	1

Operation “Addition modulo 2” (XOR, exclusive or, strict disjunction)

Notation used: A XOR B, A ⊕ B.
Truth table:

A	B	A⊕B
0	0	0
0	1	1
1	0	1
1	1	0

The result of the equivalence operation is true only if A and B are both true or false at the same time.

Priority of logical operations

• Actions in parentheses
• Inversion
• Conjunction (&)
• Disjunction (V), Exclusive OR (XOR), sum modulo 2
• Implication (→)
• Equivalence (↔)

Perfect disjunctive normal form

Perfect disjunctive normal form of a formula(SDNF) is an equivalent formula, which is a disjunction of elementary conjunctions and has the following properties:

1. Each logical term of the formula contains all the variables included in the function F(x 1,x 2,...x n).
2. All logical terms of the formula are different.
3. Not a single logical term contains a variable and its negation.
4. No logical term in a formula contains the same variable twice.

SDNF can be obtained either using truth tables or using equivalent transformations.
For each function, the SDNF and SCNF are uniquely defined up to permutation.

Perfect conjunctive normal form

Perfect conjunctive normal form of a formula (SCNF) This is a formula equivalent to it, which is a conjunction of elementary disjunctions and satisfies the properties:

1. All elementary disjunctions contain all the variables included in the function F(x 1 ,x 2 ,...x n).
2. All elementary disjunctions are different.
3. Each elementary disjunction contains a variable once.
4. Not a single elementary disjunction contains a variable and its negation.