2: Logical Basics

The lecture gives the concept of Boolean algebra, describes the problems of analysis and synthesis. The description of elementary functions of one and two variables is given. Basic equivalences are presented.

Logic algebra

In addition to the usual algebra, there is a special one, the foundations of which were laid by the nineteenth century English mathematician J. Boole. This algebra deals with the so-called propositional calculus.

Its peculiarity is the applicability for describing the operation of so-called discrete devices, among which belong a whole class of automation devices and computing equipment.

In this case, the algebra itself acts as a model of the device. This means that the operation of an arbitrary device of the specified type can only be described in some respects using the constructions of this algebra. A real real device does not physically work as the algebra of logic describes it. However, the application of the provisions of this theory allows us to make a number of practical generalizations.

Consider some scheme and present it in the form of a so-called "black" box.

We assume that the internal contents of the box is unknown.

X 1 , X 2 , X 3 - input signals, F - output signal.

We also consider that the scheme A is elementary, i.e. there is no other scheme B less than A that would be contained in A.

We construct an abstract device from elementary devices, such as A, B, C, etc. Obviously, a more complex device can be constructed from simple ways:

1. sequential connection of elements;
2. parallel connection;
3. permutations of the inputs of elements.

Then the role of Y 1 for the second element B will play:

Y1=FА(X1,X2,X3)
Y2=FБ(X1,X2)
F=F(Y1,Y2)=F(FА(X1,X2,X3),FБ(X1,X2))

Parallel connection of elements does not change the function, therefore, from the point of view of logic, this type of connection is not used. Physically sometimes they still use a parallel connection of elements, but mainly in order, for example, to amplify a signal.

In this regard, the parallel connection of elements in the algebra of logic is not considered.

The function that the element performs, generally speaking, depends on the variables that are fed to the input.

Therefore, the rearrangement of the arguments affects the nature of the function.

Thus, arbitrary, arbitrarily complex in a logical sense, schemes can be built using two methods:

1. consistent connection of elements;
2. rearrangement of the inputs of elements.

These two physical techniques in the algebra of logic correspond:

1. the principle of superposition (substituting into a function instead of its arguments for other functions);
2. argument substitution (changing the order in which the function arguments are written or replacing some function arguments with others).

So, the physical task of building and analyzing the work of a complex device is replaced by the mathematical task of synthesis and analysis of the corresponding functions of the algebra of logic.

Elementary functions of the algebra of logic

There are several synonyms in relation to the functions of the algebra of logic:

1. algebra logic functions (PAL);
2. switching functions;
3. Boolean functions;
4. binary functions.

As required, we will use all these synonyms.

Consider some set of arguments:

and we will assume that each of the arguments takes only one of two possible values, independently of the others

What is the number of different sets?

Let each binary set correspond to some binary number:

It is obvious that the number of different X 1 , X 2 , ........... X n n-digit numbers in a positional binary system is 2 n .

Suppose that a certain function F (X 1 , X 2 , ... X n ) is given on these sets and on each of them it takes either the '0' th or '1' th value.

Such a function is called a function of the algebra of logic or a switching function.

What is the number of different switching functions of the 'n' arguments?

Because the function on each set can take the value '0' or '1', and the total number of different sets is 2 n , then the total number of different functions of the arguments 'n' is: 2 ^ 2n.

Compared to the analytic function of a continuous argument, even for one argument there are many different functions.

Different computer devices contain tens and hundreds of variables (arguments), so it is clear that the number of different devices that differ from each other is almost infinite.

So, you need to learn how to build these complex functions (and therefore, the device), as well as analyze them.

Thus, it is first necessary to study these elementary functions in order to build more complex ones on their basis.

FAL of one argument

To set the PLL, you need to set its values ​​on all sets of arguments.

Let the function set an index equivalent to the set of its values ​​for the corresponding values ​​of the argument, starting from 0.0, ...., n, ....., etc. in ascending order.

These functions can be implemented on 4 elements, each of which has a maximum of one input. Thus, the principle of substitution of arguments for constructing more complex functions cannot be used.

It is necessary to consider more complex functions, i.e. FAL 2 arguments.

We give these definitions:

1. FALs that take the same value on all sets of arguments are called equal.
2. FAL essentially depends on the argument X i if

Otherwise, it does not depend significantly, and the corresponding argument is called fictitious.

For example:

It can be seen that X 3 is a dummy argument. This shows that in the function you can enter any number of dummy arguments, on which it does not significantly depend. This technique will be needed later to perform a number of transformations.

All FAL from 2 arguments. We reduce them into a single table 2.1.

  f (x 

  X 

  ) = 0 

  f (x 

  X 

  ) = X 

  f (x 

  X 

  ) = X 

  f (x 

  X 

  ) = ^ X 

  f (x 

  X 

  ) = X 

  f (x 

  X 

  ) = X 

  -> X 

  f (x 

  X 

  ) = ^ X 

  f (x 

  X 

  ) = X 

  f (x 

  X 

  ) = X 

  -> X 

  f (x 

  X 

  ) = X 

  | X 

  f (x 

  X 

  ) = 1 

These functions are introduced formally. However, they can be given a certain "logical" meaning. The algebra of logic is often called propositional calculus.

At the same time, a statement is understood as any sentence in relation to which it can be argued that it is true or false.

For example:

  B =  

there is a true saying.

Let us consider what semantic content can be put into some complex statements using the example of the PUL of 2 arguments.

Inversion

Read NOT X or X with a dash, negative X.

Take, for example, the following statement: A = , then the complex statement NOT A means: it is not true that A, i.e. it is not true that the .

From simple statements one can construct more complex ones using so-called connections.

Logical connections are FALs whose arguments are simple sentences.

Conjunction

Take 2 statements:

  A = 
 B =  

then a complex statement: A & B will be true, since both of these statements are true.

Since the truth table for conjunction coincides with the multiplication table, if the true statement is assigned the value '1' and the false statement is assigned the value '0', then a complex statement can be called a product.

The conjunction function is true when both statements are true at the same time.

Disjunction

This complex statement is true when at least one statement included in it is true.

X 1 OR X 2 is read: Some difference from the meaning of the union "or", adopted in Russian: in this case, this union is used in the sense of unification, not separation.

Logical equivalence

This complex statement is true when both statements are true or false at the same time.

It follows that, regardless of the meaning, both true and false statements are equivalent.

For example,

  A = 
 B = 
 A ~ B are equivalent. 

Implication

This complex statement is false only when X 1 is true and X 2 is false.

It reads: if X 1 , then X 2 . At the same time, X 1 is a premise, X 2 is a consequence.

If you look at the truth table, then the name of this function may seem strange, since it follows that a statement made up of two false may be true.

But in reality, that's right, because the content of statements in the algebra of logic is not interested.

Then a false consequence can follow from a false premise and this can be considered true:

  ,
 then <2 square 3>. 

Equivalence

In some cases, a complex and long utterance can be written shorter and simpler without violating the truth of the original utterance. This can be done using some equivalent ratios.

Disjunction:

those. the truth of a statement does not change if it is replaced by a shorter one, so this is the rule for bringing such members into account:

  xvx = 1 

- constantly true statement.

- (commutative) communicative law.

- a combination law.

Conjunction:

rule of bringing such members:

- constantly false statement

- constantly false statement

Addition mod 2

- with an odd number of members, 0 - with an even number of members

Rule de Morgan

Let us prove for two variables using the truth table:

X 1	X 2		X 1 & X 2
0	0	one	one
0	one	one	one
one	0	one	one
one	one	0	0

Absorption operation:

or in general

Full bonding operation:

Incomplete bonding operation: