In what case is the truth table constructed? Priority of logical operations

All tips

Construction of truth tables for complex statements.

Priority of logical operations

1) inversion 2) conjunction 3) disjunction 4) implication and equivalence

How to create a truth table?

According to the definition, the truth table of a logical formula expresses the correspondence between all possible sets of variable values and the values of the formula.

For a formula that contains two variables, there are only four such sets of variable values:

(0, 0), (0, 1), (1, 0), (1, 1).

If a formula contains three variables, then there are eight possible sets of variable values (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0 ), (1, 0, 1), (1, 1, 0), (1, 1, 1).

The number of sets for a formula with four variables is sixteen, etc.

A convenient form of recording when finding the values of a formula is a table that contains, in addition to the values of variables and formula values, also the values of intermediate formulas.

Examples.

1. Let's create a truth table for the formula 96%" style="width:96.0%">

From the table it is clear that for all sets of values of the variables x and y, the formula takes the value 1, that is, is identical to true.

2. Truth table for the 96% formula" style="width:96.0%">

From the table it is clear that for all sets of values of the variables x and y, the formula takes value 0, that is, is identically false .

3. Truth table for the 96% formula" style="width:96.0%">

From the table it is clear that formula 0 " style="border-collapse:collapse;border:none">

Conclusion: we got all ones in the last column. This means that the meaning of the complex statement is true for any meaning of the simple statements K and S. Consequently, the teacher reasoned logically correctly.

Absolutely all digital microcircuits consist of the same logical elements - the “building blocks” of any digital node. That's what we'll talk about now.

Logic element- This is a circuit that has several inputs and one output. Each state of the signals at the inputs corresponds to a specific signal at the output.

So what are the elements?

Element “AND”

Otherwise it is called “conjunctor”.

In order to understand how it works, you need to draw a table that lists the output states for any combination of input signals. This table is called " truth table" Truth tables are widely used in digital technology to describe the operation of logic circuits.

This is what the “AND” element and its truth table look like:

Since you will have to communicate with both Russian and bourgeois tech. documentation, I will provide symbolic graphic symbols (GID) of elements both according to our and non-our standards.

We look at the truth table and clarify the principle in our brain. It is not difficult to understand: a unit at the output of the “AND” element occurs only when units are supplied to both inputs. This explains the name of the element: units must be on BOTH one AND the other input.

If we look at it a little differently, we can say this: the output of the “AND” element will be zero if zero is applied to at least one of its inputs. Let's remember. Go ahead.

OR element

In another way, he is called a “disjunctor”.

We admire:

Again, the name speaks for itself.

A unit appears at the output when a unit is applied to one OR to the other OR to both inputs at once. This element can also be called the “AND” element for negative logic: a zero at its output occurs only if zeros are supplied to both one and the second input.

NOTE element

More often, it is called an “inverter”.

Do I need to say anything about his work?

NAND element

The NAND gate works exactly the same as the AND gate, only the output signal is completely opposite. Where the “AND” element should have a “0” output, the “AND-NOT” element should have a one. And vice versa. This is easy to understand from the equivalent circuit of the element:

Element "NOR" (NOR)

The same story - an “OR” element with an inverter at the output.

The next comrade is a little more cunning:
Exclusive OR element (XOR)

He's like this:

The operation it performs is often called "addition modulo 2". In fact, digital adders are built on these elements.

Let's look at the truth table. When is the output unit? Correct: when the inputs have different signals. On one - 1, on the other - 0. That's how cunning he is.

The equivalent circuit is something like this:

It is not necessary to memorize it.

Actually, these are the main logical elements. Absolutely any digital microcircuits are built on their basis. Even your favorite Pentium 4.

And finally, several microcircuits containing digital elements. The numbers of the corresponding legs of the microcircuit are indicated near the terminals of the elements. All chips listed here have 14 legs. Power is supplied to legs 7 (-) and 14 (+). Supply voltage – see the table in the previous paragraph.

A truth table is a table that describes a logical function. A logical function here is a function in which the values of the variables and the value of the function itself express truth. For example, they take the values “true” or “false” (true or false, 1 or 0).

Truth tables are used to determine the meaning of a statement for all possible cases of the truth values of the statements that make it up. The number of all existing combinations in the table is found by the formula N=2*n; where N is the total number of possible combinations, n is the number of input variables. Truth tables are often used in digital engineering and Boolean algebra to describe the operation of logic circuits.

Truth tables for basic functions

Examples: conjunction - 1&0=0, implication - 1→0=0.

Order of logical operations

Inversion; Conjunction; Disjunction; Implication; Equivalence; Schaeffer's stroke; Pierce's arrow.

The sequence of constructing (compiling) a truth table:

Determine the number N of variables used in a logical expression.
Calculate the number of possible sets of variable values M = 2 N, equal to the number of rows in the table.
Count the number of logical operations in a logical expression and determine the number of columns in the table, which is equal to the number of variables plus the number of logical operations.
Title the columns of the table with the names of variables and names of logical operations.
Fill the logical variable columns with sets of values, for example, from 0000 to 1111 in increments of 0001 in the case of four variables.
Fill in the truth table by columns with the values of intermediate operations from left to right.
Fill in the final value column for function F.

Thus, you can compile (construct) a truth table yourself.

Create a truth table online

Fill in the input field and click OK. T - true, F - false. We recommend bookmarking the page or saving it on a social network.

Designations

Sets or expressions in capital letters of the Latin alphabet: A, B, C, D...
A" - prime - complements of sets
&& - conjunction ("and")
|| - disjunction ("or")
! - negation (for example, !A)
\cap - intersection of sets \cap
\cup - union of sets (addition) \cup
A&!B - set difference A∖B=A-B
A=>B - implication "If... then"
AB - equivalence

Definition 1

Logic function– a function whose variables take one of two values: $1$ or $0$.

Any logical function can be specified using a truth table: the set of all possible arguments is written on the left side of the table, and the corresponding values of the logical function are written on the right side.

Definition 2

Truth table– a table that shows what values a compound expression will take for all possible sets of values of the simple expressions included in it.

Definition 3

Equivalent are called logical expressions whose last columns of truth tables coincide. Equivalence is indicated using the $«=»$ sign.

When compiling a truth table, it is important to consider the following order of logical operations:

Picture 1.

Parentheses take precedence in executing the order of operations.

Algorithm for constructing a truth table of a logical function

Determine the number of lines: number of lines= $2^n + 1$ (for title line), $n$ – number of simple expressions. For example, for functions of two variables there are $2^2 = 4$ combinations of sets of variable values, for functions of three variables there are $2^3 = 8$, etc.

Determine the number of columns: number of columns = number of variables + number of logical operations. When determining the number of logical operations, the order of their execution is also taken into account.

Fill columns with the results of logical operations in a certain sequence, taking into account the truth tables of basic logical operations.

Figure 2.

Example 1

Create a truth table for the logical expression $D=\bar(A) \vee (B \vee C)$.

Solution:

Let's determine the number of lines:

number of lines = $2^3 + 1=9$.

Number of variables – $3$.

inverse ($\bar(A)$);
disjunction, because it is in parentheses ($B \vee C$);
disjunction ($\overline(A)\vee \left(B\vee C\right)$) is the required logical expression.

Number of columns = $3 + 3=6$.

Let's fill in the table, taking into account the truth tables of logical operations.

Figure 3.

Example 2

Using this logical expression, construct a truth table:

Solution:

Let's determine the number of lines:

The number of simple expressions is $n=3$, which means

number of lines = $2^3 + 1=9$.

Let's determine the number of columns:

Number of variables – $3$.

Number of logical operations and their sequence:

negation ($\bar(C)$);
disjunction, because it is in parentheses ($A \vee B$);
conjunction ($(A\vee B)\bigwedge \overline(C)$);
negation, which we denote by $F_1$ ($\overline((A\vee B)\bigwedge \overline(C))$);
disjunction ($A \vee C$);
conjunction ($(A\vee C)\bigwedge B$);
negation, which we denote by $F_2$ ($\overline((A\vee C)\bigwedge B)$);
disjunction is the desired logical function ($\overline((A\vee B)\bigwedge \overline(C))\vee \overline((A\vee C)\bigwedge B)$).

Today we will talk about a subject called computer science. The truth table, types of functions, the order of their execution - these are our main questions, to which we will try to find answers in the article.

Usually this course is taught in high school, but the large number of students causes misunderstanding of some of the features. And if you are going to devote your life to this, then you simply cannot do without passing the unified state exam in computer science. A truth table, transformation of complex expressions, solving logical problems - all this can be found in the ticket. Now we will look at this topic in more detail and help you score more points on the Unified State Exam.

Subject of logic

What kind of subject is computer science? Truth table - how to build it? Why is the science of logic needed? We will answer all these questions now.

Computer science is quite a fascinating subject. It cannot cause difficulties for modern society, because everything that surrounds us, one way or another, relates to a computer.

The basics of the science of logic are taught by high school teachers in computer science classes. Truth tables, functions, simplification of expressions - all this should be explained by computer science teachers. This science is simply necessary in our lives. Take a closer look, everything obeys some laws. You threw the ball, it flew up, but after that it fell back to the ground, this happened due to the presence of the laws of physics and the force of gravity. Mom cooks soup and adds salt. Why don't we get any grains when we eat it? It's simple, the salt dissolved in water, obeying the laws of chemistry.

Now pay attention to how you speak.

“If I take my cat to the veterinarian, he will be vaccinated.”
“Today was a very difficult day because the test was coming.”
“I don’t want to go to university because today there will be a colloquium” and so on.

Everything you say must obey the laws of logic. This applies to both business and friendly conversations. It is for this reason that it is necessary to understand the laws of logic so as not to act at random, but to be confident in the outcome of events.

Functions

In order to create a truth table for the problem proposed to you, you need to know logical functions. What it is? A Boolean function has some variables that are statements (true or false), and the value of the function itself should give us the answer to the question: “Is the expression true or false?”

All expressions take the following meanings:

True or false.
I or L.
1 or 0.
Plus or minus.

Here, give preference to the method that is more convenient for you. In order to construct a truth table, we need to list all combinations of variables. Their number is calculated by the formula: 2 to the power of n. The result of the calculation is the number of possible combinations; the variable n in this formula denotes the number of variables in the condition. If the expression has many variables, then you can use a calculator or make a small table for yourself with raising two to a power.

In total, in logic there are seven functions or connections connecting expressions:

Multiplication (conjunction).
Addition (disjunction).
Consequence (implication).
Equivalence.
Inversion.
Schaeffer's stroke.
Pierce's arrow.

The first operation presented in the list is called “logical multiplication”. It can be marked graphically in the form of an inverted checkmark, & or *. The second operation on our list is logical addition, graphically indicated by a check mark, +. The implication is called a logical consequence and is indicated by an arrow pointing from the condition to the consequence. Equivalence is indicated by a two-way arrow; the function has a true value only in those cases when both values are either the value "1" or "0". Inversion is called logical negation. The Schaeffer stroke is called a function that denies conjunction, and the Peirce arrow is a function that denies disjunction.

Basic Binary Functions

The logical truth table helps you find the answer to a problem, but to do this you need to memorize the tables of binary functions. They will be provided in this section.

Conjunction (multiplication). If there are two, then as a result we get the truth, in all other cases we get a lie.

The result is false during logical addition only in the case of two false input data.

A logical consequence has a false result only when the condition is true and the consequence is false. Here you can give an example from life: “I wanted to buy sugar, but the store was closed,” therefore, the sugar was never purchased.

Equivalence is true only when the input data values are the same. That is, for pairs: “0;0” or “1;1”.

In the case of inversion, everything is elementary: if the input contains a true expression, then it is converted to false, and vice versa. The picture shows how it is indicated graphically.

The Schiffer stroke will produce a false result only if there are two true expressions.

In the case of Peirce's arrow, the function will be true only if we have only false expressions as input.

In what order to perform logical operations

Please note that constructing truth tables and simplifying expressions is only possible with the correct order of operations. Remember in what order they need to be carried out, this is very important to obtain the right result.

logical negation;
multiplication;
addition;
consequence;
equivalence;
negation of multiplication (Schaeffer stroke);
negation of addition (Pierce's arrow).

Example No. 1

Now we propose to consider an example of constructing a truth table for 4 variables. It is necessary to find out in what cases F=0 for the equation: not A+B+C*D

The answer to this task will be a list of the following combinations: “1;0;0;0”, “1;0;0;1” and “1;0;1;0”. As you can see, creating a truth table is quite simple. Once again I would like to draw your attention to the order of actions. In this particular case it was as follows:

Inverse of the first simple expression.
The conjunction of the third and fourth expressions.
Disjunction of the second expression with the results of previous calculations.

Example No. 2

Now we will look at another task that requires constructing a truth table. Computer science (the examples were taken from a school course) can also be used as an assignment. Let's briefly consider one of them. Is Vanya guilty of stealing the ball if the following is known:

If Vanya did not steal or Petya did, then Seryozha took part in the theft.
If Vanya is not guilty, then Seryozha did not steal the ball.

Let's introduce the notation: I - Vanya stole the ball; P - Petya stole; S - Seryozha stole.

Based on this condition, we can create an equation: F=((notI+P) implication C)*(notI implication notC). We need those options where the function takes a true value. Next, you need to create a table, since this function has as many as 7 actions, we will omit them. We will enter only the input data and the result.

Please note that in this problem we used plus and minus instead of the signs “0” and “1”. This is also acceptable. We are interested in combinations where F=+. Having analyzed them, we can draw the following conclusion: Vanya participated in stealing the ball, since in all cases where F takes the value +, AND has a positive value.

Example No. 3

Now we suggest you find the number of combinations when F=1. The equation is as follows: F=notA+B*A+notB. Let's create a truth table:

Answer: 4 combinations.