Denoted by the figure of speech "either ... or ..." The compound statement "either A or B" is considered true when either A or B is true, but not both at once; otherwise the compound statement is false.
Those. the result is true (equal to 1), if A is not equal to B (A≠B).
This operation is often compared to disjunction because they are very similar in properties, and both are similar to the union "or" in everyday speech. Compare the rules for these operations:
1. true if true or , or both at once.
2. true if true or, but not both at once.
Operation rules out last option("both at once") and for this reason is called exclusive "OR". Ambiguity natural language is that the union "or" can be used in both cases.
5. Implication (logical consequence) is formed by combining two statements into one using the figure of speech "if ..., then ....".
Entry: A®B
A compound statement formed by the operation of implication is false if and only if a false conclusion follows from a true premise (the first statement) (the second statement).
Those. if 1 implies 0, then the result is 0, otherwise it is 1.
For example, the statement "If a number is divisible by 10, then it is divisible by 5" is true, because both the first and second statements are true.
The statement "If a number is divisible by 10, then it is divisible by 3" is false, because a false conclusion is drawn from a true premise.
"This quadrilateral is a square" (BUT) and "A circle can be circumscribed around a given quadrilateral" (AT). Then the compound statement reads as "If the given quadrilateral is a square, then a circle can be circumscribed around it."
In ordinary speech, the link "if...then" describes a causal relationship between statements. But in logical operations, the meaning of statements is not taken into account. Only their truth or falsity is considered. Therefore, one should not be embarrassed by the "meaninglessness" of implications formed by statements that are completely unrelated in content. For example, like this: "If the President of the United States is a Democrat, then there are giraffes in Africa", "If a watermelon is a berry, then there is gasoline in the gas station."
6. Equivalence (logical equality, ~ º Û) is formed by combining two statements into one using the figure of speech "...if and only if..."
A compound statement formed by the equivalence operation is true if and only if both statements are either false or true at the same time.
For example, the statements "A computer can perform calculations if and only if it is turned on" and "A computer cannot perform calculations if and only if it is not turned on" are true, since both simple statements are simultaneously true.
truth tables
For each compound statement (logical function) it is possible to build a truth table that determines its truth or falsity for all possible combinations of the initial values of simple statements.
truth table this is table view logic circuit (operation), which lists all possible combinations of truth values of input signals (operands) together with the truth value of the output signal (result of the operation) for each of these combinations.
Reflecting the above logical operations in the truth table:
In the algebra of propositions, all logical functions can be reduced by logical transformations to three basic ones: logical addition, logical multiplication, and logical negation.
Let us prove that the operation implication A®B is equivalent to the logical expression:
Often, in order to demonstrate the limited capabilities of single-layer perceptrons in solving problems, they resort to considering the so-called problem XOR - Exclusive OR.
The essence of the problem is as follows. The logical function XOR is given - exclusive OR. This is a function of two arguments, each of which can be zero or one. It takes the value when one of the arguments is equal to one, but not both, otherwise. The problem can be illustrated with a single-layer, single-neuron, two-input system shown in the figure below.
Denote one input by , and the other by , then all their possible combinations will consist of four points on the plane. The table below shows the required relationship between inputs and output, where input combinations that should produce a zero output are labeled and , a single output is labeled and .
| points | Meaning | Meaning | Required Output |
| 0 | 0 | 0 | |
| 1 | 0 | 1 | |
| 0 | 1 | 1 | |
| 1 | 1 | 0 |
One neuron with two inputs can form a decision surface in the form of an arbitrary straight line. In order for the network to implement the XOR function given by the table above, you need to position the line so that the points are on one side of the line, and the points are on the other. Trying to draw such a straight line in the figure below, we are convinced that this is impossible. This means that no matter what values are assigned to the weights and threshold, a single-layer neural network is unable to reproduce the input-output relationship required to represent the XOR function.
However, the XOR function is easily formed by a two-layer network, and in many ways. Let's consider one of these ways. Let's modernize the network in the figure by adding another hidden layer of neurons:
Note that this network given as is, i.e. it can be assumed that she is already trained. The numbers above the arrows show the values of the synaptic weights. As an activation function, we use the unit jump function with the threshold , which has the following graph:
Then the result of the operation of such a neural network can be represented as the following table:
| points | Meaning | Meaning | Required Output | |||
| 0 | 0 | 0 | 0 | 0 | 0 | |
| 1 | 0 | 1 | 1 | 0 | 1 | |
| 0 | 1 | 1 | 0 | 1 | 1 | |
| 1 | 1 | 0 | 0 | 0 | 0 |
Each of the two neurons of the first layer forms a decision surface in the form of an arbitrary straight line (divides the plane into two half-planes), and the neuron of the output layer combines these two solutions, forming a decision surface in the form of a strip formed by parallel straight lines of neurons of the first layer:
The neural network used in this article to solve the XOR problem is primitive and does not use all the features of multilayer networks. Obviously, multilayer neural networks have greater representing power than single-layer ones, only in the case of the presence of nonlinearity. And in this network, a threshold linear function activation. Such a network cannot be trained, for example, by applying the backpropagation algorithm.
In this article, we will talk about some bitwise operations. Consider the main ones: XOR (exclusive OR), AND (AND), NOT (NOT) and OR (OR).
As you know, the minimum unit of measurement of information is bit, which stores one of 2 values: 0 ( False, false) or 1 ( True, true). Thus, a bit cell can simultaneously be in only one of two possible states.
To manipulate bits, certain operations are used - logical or boolean. They can be applied to any bit, regardless of whether its value is zero or one. Well, let's look at examples of the use of the three basic logical operations.
Logical AND operation (and)
AND denoted by & .
The AND operator is performed with 2 bits, let's take a and b for example. Execution result AND operations is 1 if a and b are both 1. Otherwise, the result is 0. For example, using AND you can find out if a number is even or not.
Look at the truth table of the AND operation:
Logical operation OR (OR)
Denoted by the sign | .
Operator OR also performed with 2 bits (a and b). The result is 0 if a and b are both 0, otherwise it is 1. Look at the truth table.
Logical operation XOR (exclusive OR)
The XOR operator is denoted by ^ .
XOR performed with 2 bits (a and b). The result of the XOR operation ( XOR) is 1 when one of the bits b or a is 1. Otherwise, the result of applying the XOR operator is 0.
The truth table of the logical operation for XOR (exclusive OR) looks like this:
By using XOR (exclusive OR), you can swap the values of 2 variables of the same data type without using a temporary variable. And yet, using XOR, you can encrypt the text, for example:
String msg = "This is a message"; char message = msg.toCharArray(); String key = ".*)"; String encryptedString = new String(); for(int i = 0; i< message.length; i++){ encryptedString += message[i]^key.toCharArray(); }
I agree, XOR is far from the best reliable method encryption, but this does not mean that it cannot be made part of any encryption algorithm.
Logical operation NOT (NOT)
This is a bitwise negation, so it is performed with one bit and is denoted by ~ .
The result depends on the state of the bit. If it is in the zero state, then the result of the operation is one and vice versa. Everything is extremely simple.
These 4 logical operations should be remembered first of all, because with their help you can get almost any possible result. There are also operations such as<< (побитовый сдвиг влево) и >> (bitwise right shift).
An electrical circuit designed to perform any logical operation on input data is called a logic element. The input data is represented here in the form of voltages of various levels, and the result of a logical operation at the output is also obtained in the form of a voltage of a certain level.
Operands in this case are fed - signals are received at the input of the logic element in the form of a high or low level voltage, which essentially serve as input data. So, a high-level voltage - a logical one - indicates the true value of the operand, and a low-level voltage of 0 - a false value. 1 - TRUE, 0 - FALSE.
Logic element- an element that implements certain logical relationships between input and output signals. Logic gates are commonly used to build logic circuits computers, discrete circuits of automatic control and management. For all types of logical elements, regardless of their physical nature, discrete values of input and output signals are characteristic.
Logic elements have one or more inputs and one or two (usually inverse to each other) outputs. The values of "zeros" and "ones" of the output signals of logic elements are determined by the logic function that the element performs, and the values of "zeros" and "ones" of the input signals, which play the role of independent variables. There are elementary logical functions from which any complex logical function can be composed.
Depending on the device of the element circuit, on its electrical parameters, the logic levels (high and low voltage levels) of the input and output have the same values for high and low (true and false) states.
Traditionally, logic elements are produced in the form of special radio components - integrated circuits. Logical operations such as conjunction, disjunction, negation and modulo addition (AND, OR, NOT, exclusive OR) are the main operations performed on logical elements of basic types. Let's take a closer look at each of these types of logical elements.
Logical element "AND" - conjunction, logical multiplication, AND
"AND" - a logical element that performs a conjunction or logical multiplication operation on the input data. This element can have from 2 to 8 (the most common in production are “AND” elements with 2, 3, 4 and 8 inputs) inputs and one output.
Symbols of logical elements "AND" with a different number of inputs are shown in the figure. In the text, the logical element "AND" with one or another number of inputs is designated as "2I", "4I", etc. - the element "AND" with two inputs, with four inputs, etc.
The truth table for the 2I element shows that the output of the element will be a logical unit only if the logical units are simultaneously at the first input AND at the second input. In the other three possible cases the output will be zero.
In Western schemes, the icon of the "And" element has a straight line at the entrance and a rounding at the exit. On domestic schemes - a rectangle with the symbol "&".
Logical element "OR" - disjunction, logical addition, OR
"OR" - a logical element that performs a disjunction or logical addition operation on the input data. It, like the “AND” element, is available with two, three, four, etc. inputs and one output. Symbols of logical elements "OR" with a different number of inputs are shown in the figure. These elements are designated as follows: 2OR, 3OR, 4OR, etc.
The truth table for the element "2OR" shows that for the appearance of a logical unit at the output, it is enough that the logical unit is at the first input OR at the second input. If logical ones are at once on two inputs, the output will also be one.
In Western schemes, the icon for the "OR" element has a rounded entry and a rounded, pointed exit. On domestic schemes - a rectangle with the symbol "1".
Logic element "NOT" - negation, inverter, NOT
"NOT" - a logical element that performs a logical negation operation on the input data. This element, which has one output and only one input, is also called an inverter, since it actually inverts (inverts) the input signal. The figure shows symbol logical element "NOT".
The truth table for the inverter shows that a high input potential gives a low output potential and vice versa.
In Western schemes, the icon of the "NOT" element has the shape of a triangle with a circle at the exit. On domestic schemes - a rectangle with the symbol "1", with a circle at the exit.
Logical element "AND-NOT" - conjunction (logical multiplication) with negation, NAND
"AND-NOT" - a logical element that performs a logical addition operation on the input data, and then a logical negation operation, the result is output. In other words, it is basically an "AND" element, complemented by a "NOT" element. The figure shows the symbol of the logical element "2I-NOT".
The truth table for the "NAND" element is the opposite of the table for the "AND" element. Instead of three zeros and one - three ones and zero. The "NAND" element is also called the "Schaeffer element" in honor of the mathematician Henry Maurice Schaeffer, who first noted the significance of this in 1913. Designated as "I", only with a circle at the exit.
Logical element "OR-NOT" - disjunction (logical addition) with negation, NOR
"OR-NOT" - a logical element that performs a logical addition operation on the input data, and then a logical negation operation, the result is output. In other words, this is an "OR" element, supplemented by a "NOT" element - an inverter. The figure shows the symbol of the logic element "2OR-NOT".
The truth table for the element "OR-NOT" is opposite to the table for the element "OR". A high potential at the output is obtained only in one case - both inputs are fed simultaneously with low potentials. Referred to as "OR", only with a circle at the output indicating inversion.
Logical element "exclusive OR" - addition modulo 2, XOR
"XOR" - a logical element that performs the operation of logical addition modulo 2 on the input data, has two inputs and one output. Often these elements are used in control schemes. The figure shows the symbol of this element.
The image in Western schemes is like that of "OR" with an additional curved strip on the input side, in the domestic one - like "OR", only instead of "1" it will be written "=1".
This logical element is also called "inequivalence". High level voltage will be at the output only when the signals at the input are not equal (on one unit, on the other zero or on one zero, and on the other one) even if there are two units at the input at the same time, the output will be zero - this is the difference from " OR". These logic elements are widely used in adders.
The exclusive OR operation (disambiguation, modulo two addition) is denoted by the symbol and differs from the logical OR only when A=1 and B=1.
Thus, the non-equivalence of two statements X1 and X2 is called such a statement Y, which is true if and only if one of these statements is true and the other is false.
The definition of this operation can be written as a truth table (Table 6):
Table 6 - Truth table of the EXCLUSIVE OR operation
As can be seen from Table 6, the logic of the element corresponds to its name.
This is the same "OR" element with one small difference. If the value at both inputs is equal to a logical unit, then the output of the "EXCLUSIVE OR" element, unlike the "OR" element, is not one, but zero.
The EXCLUSIVE OR operation actually compares two binary digits for a match.
Each logical connective is considered as an operation on logical statements and has its own name and designation (Table 7).
Table 7 - Basic logical operations
|
Designation operations |
read |
Operation name |
Alternative designations |
|
Negation (inversion) |
dash from above |
||
|
Conjunction (logical multiplication) | |||
|
Disjunction (logical addition) | |||
|
If...then |
implication |
|
|
|
Then and only then |
Equivalence | ||
|
Or either |
EXCLUSIVE OR (modulo 2 addition) |
|
Order of execution of logical operations in a complex logical expression
The system of logical operations of inversion, conjunction, disjunction allows you to build an arbitrarily complex logical expression.
When calculating the value of a logical expression, a certain order of execution of logical operations is adopted.
1. Inversion.
2. Conjunction.
3. Disjunction.
4. Implication.
5. Equivalence.
Parentheses are used to change the specified order of operations.
Boolean expressions and truth tables
Boolean expressions
Each compound statement can be expressed as a formula (logical expression), which includes boolean variables, denoting statements, and signs of logical operations, denoting logical functions.
To write a compound statement in the form of a logical expression in a formal language (the language of the algebra of logic) in a compound statement, it is necessary to single out simple statements and logical connections between them.
Let us write in the form of a logical expression the compound statement “(2 2=5 or 2∙2=4) and (2∙2≠5 or 2∙ 2 ≠four)".
Let's analyze the compound statement. It contains two simple statements:
A \u003d "2 2 \u003d 5" - false (0),
B \u003d "2 2 \u003d 4" - true (1).
Then the compound statement can be written in the following form:
«( BUTorAT) and (Ā orAT)».
Now it is necessary to write the statement in the form of a logical expression, taking into account the sequence of execution of logical operations. When performing logical operations, the following order of their execution is defined:
inversion, conjunction, disjunction.
Parentheses can be used to change the specified order:
F = (AvAT) & (Ā vAT).
The truth or falsity of compound statements can be determined purely formally, guided by the laws of the algebra of statements, without referring to the semantic content of statements.
We substitute the values of logical variables into the logical expression and, using the truth tables of basic logical operations, we obtain the value of the logical function:
F= (A v B) & ( Ā v B) = (0 v 1) & (1 v 0) = 1 & 1 = 1.
truth tables
Tables in which logical operations reflect the results of calculations of complex propositions for different values of the original simple propositions are called truth tables.
Simple statements are denoted by variables (for example, A and B).
When constructing truth tables, it is advisable to be guided by a certain sequence of actions:
it is necessary to determine the number of rows in the truth table. It is equal to the number of possible combinations of values of boolean variables included in the boolean expression. If the number of boolean variables is P, then:
number of rows = 2 n .
In our case, the logical function 
has 2 variables and therefore the number of rows in the truth table must be 4;
it is necessary to determine the number of columns in the truth table, which is equal to the number of logical variables plus the number of logical operations.
In our case, the number of variables is two: A and B, and the number of logical operations is five (Table 8), that is, the number of columns in the truth table is seven;
it is necessary to build a truth table with the specified number of rows and columns, designate the columns and enter into the table possible sets of values of the initial logical variables;
it is necessary to fill the truth table by columns, performing basic logical operations in the required sequence and in accordance with their truth tables.
Now we can define the value of a boolean function for any set of boolean variable values.
Table 8 - Logic function truth table
