Construct a truth table for the logical expression b. V

Algebraic transformations of logical expressions

Construction of truth tables

Examples

Subject of logic

Functions

Basic Binary Functions

In what order to perform logical operations

Example No. 1

Example No. 2

Example No. 3

Negation

Disjunction

Implication and equivalence

Other logic functions

Schaeffer's stroke

Pierce's arrow

Definition of equivalence

Twitter

The problem of determining the truth of an expression faces many sciences. Any evidentiary discipline must be based on some criteria for the truth of evidence. The science that studies these criteria is called the algebra of logic. The main postulate of the algebra of logic is that any most ornate statement can be represented as an algebraic expression of simpler statements, the truth or falsity of which is easy to determine.

For any “algebraic” operation on a statement, a rule is specified for determining the truth or falsity of the modified statement, based on the truth or falsity of the original statement. These rules are written through expression truth tables. Before compiling truth tables, you need to become more familiar with the algebra of logic.

Any logical expression, as well as its variables (statements), take two values: lie or truth. False is denoted by zero, and truth is denoted by one. Having understood the domain of definition and the range of acceptable values, we can consider the operations of the algebra of logic.

Negation and inversion- the simplest logical transformation. It corresponds to the particle "not." This transformation simply reverses the statement. Accordingly, the meaning of the statement also changes to the opposite. If statement A is true, then "not A" is false. For example, the statement “a right angle is an angle equal to ninety degrees” is true. Then his denial "a right angle is not equal to ninety degrees" is a lie.

Truth table for negation will be like this:

This operation may be ordinary or strict, their results will vary.

The usual disjunction or logical addition corresponds to the conjunction "or". It will be true if at least one of the statements included in it is true. For example, the expression “The earth is round or stands on three pillars” will be true, since the first statement is true, although the second is false. In the table it will look like this:

Strict disjunction or modulo addition is also called "exclusive or". This operation can take the form of a grammatical construction “one of two: either... or...”. Here, the value of a logical expression will be false if all statements included in it have the same truth. That is, both statements are either true together or false together.

Table of exclusive or

The implication is consequence and can be grammatically expressed as “from A follows B.” Here statement A will be called a premise, and B will be called a consequence. An implication can be false only in one case: if the premise is true and the consequence is false. That is, a lie cannot follow from the truth. In all other cases the implication is true. Options when both statements have the same truth do not raise questions. But why is a true consequence from a false premise true? The point is that anything can follow from a false premise. This is what distinguishes implication from equivalence.

In mathematics (and other demonstrative disciplines), implication is used to indicate a necessary condition. For example, statement A is “point O is the extremum of a continuous function,” statement B is “the derivative of a continuous function at point O becomes zero.” If O is indeed the extremum point of a continuous function, then the derivative at this point will indeed be equal to zero. If O is not an extremum point, then the derivative at this point may or may not be zero. That is, B is necessary for A, but not sufficient.

Truth table for implication as follows:

The logical operation of equivalence is essentially mutual implication. “A is equivalent to B” means that “from A follows B” and “from B follows A” at the same time. Equivalence is true when both statements are either simultaneously true or simultaneously false.

In mathematics, equivalence is used to determine a necessary and sufficient condition. For example, statement A - “Point O is the extremum point of a continuous function”, statement B - “At point O, the derivative of the function becomes zero and changes sign.” These two statements are equivalent. B contains a necessary and sufficient condition for A. Note that in this example statement, B is actually the conjunction of two others: “the derivative at point O becomes zero” and “the derivative at point O changes sign.”

Above we discussed the basic logical operations that are often used. There are other functions that are used:

The Schaeffer stroke or incompatibility is the negation of the conjunction of A and B
Peirce's arrow represents the failure of the negation of the disjunction.

To build a truth table for any logical expression, you must act in accordance with the algorithm:

Break the expression down into simple statements and label each as a variable.
Define logical transformations.
Identify the order of these transformations.
Count the rows in the future table. Their number is equal to two to the power of N, where N is the number of variables, plus one line for the table header.
Determine the number of columns. It is equal to the sum of the number of variables and the number of actions. You can represent the result of each action as a new variable, if that makes sense.
The header is filled in sequentially, first all the variables, then the results of the actions in the order in which they were performed.
You need to start filling out the table with the first variable. For her, the number of lines is divided in half. One half is filled with zeros, the second with ones.
For each subsequent variable, zeros and ones alternate twice as often.
In this way, all columns with variables are filled and for the last variable the value changes in each row.
Then the results of all actions are sequentially filled in.

As a result, the last column will display the value of the entire expression depending on the value of the variables.

Special mention should be made about order of logical actions. How to define it? Here, as in algebra, there are rules that determine the sequence of actions. They are performed in the following order:

expressions in brackets;
negation or inversion;
conjunction;
strict and ordinary disjunction;
implication;
equivalence.

To consolidate the material, you can try to create a truth table for the previously mentioned logical expressions. Let's look at three examples:

Schaeffer's stroke.
Pierce's arrow.
Definition of equivalence.

A Schaeffer stroke is a Boolean expression that can be written as "not (A and B)". There are two variables and two actions. The conjunction is in parentheses, which means it is executed first. The table will have a header and four rows with variable values, as well as four columns. Let's fill out the table:

A	B	A and B	not (A and B)
L	L	L	AND
L	AND	L	AND
AND	L	L	AND
AND	AND	AND	L

The negation of a conjunction looks like a disjunction of negations. This can be verified by constructing a truth table for the expression “not A or not B.” Do this yourself and note that there will already be three operations here.

Considering Peirce's Arrow, which represents the negation of the disjunction "not (A or B)", let's compare it with the conjunction of negations "not A and not B". Let's fill in two tables:

A	B	not A	not B	not A and not B
L	L	AND	AND	AND
L	AND	AND	L	L
AND	L	L	AND	AND
AND	AND	L	L	L

The meanings of the expressions coincided. After studying these two examples, we can come to a conclusion about how to open parentheses after negation: negation is applied to all variables in the parentheses, conjunction changes to disjunction, and disjunction changes to conjunction.

We can say about statements A and B that they are equivalent if and only if A follows from B and B follows from A. Let's write this as a logical expression and build a truth table for it. "(A is equivalent to B) is equivalent to (from A follows B) and (from B follows A)."

There are two variables and five actions. We build the table:

All values in the last column are true. This means that the above definition of equivalence is true for any values of A and B. This means that it is always true. Exactly using truth table you can check the correctness of any definitions and logical constructions.

The solution to logical expressions is usually written in the form truth tables – tables in which actions show what values a logical expression takes for all possible sets of its variables.

When constructing a truth table for a logical expression, it is necessary to take into account order of execution of logical operations , namely:

actions in brackets,
inversion (negation),
& (conjunction),
v ( disjunction),
=> (implication),
<=> (equivalence ).

Algorithm for constructing a truth table :

1. Find out the number of rows in the table (calculated as 2 n, where n – number of variables + row of column headings).

2. Find out the number of columns (calculated as the number of variables + the number of logical operations).

3. Establish the sequence of logical operations.

4. Construct a table, indicating the names of the columns and possible sets of values of the original logical variables.

5. Complete the truth table by column.

6. Write down the answer.

Example 6

Let's build a truth table for the expressionF =(Av B )&( ¬ A v¬ B) .

1. Number of rows=2 2 (2 variables+column header row)=5.

2. Number of columns = 2 logical variables (A, B) + 5 logical operations (v,&, ¬ , v, ¬ ) = 7.

3. Let’s arrange the order of operations: 1 5 2 43

(A v B ) & ( ¬ A v¬ B)

4-5. Let's build a table and fill it in columns:

6. Answer: F =0, with A= B=0 and A= B=1

Example 7

Let's build a truth table for a logical expression F=X v Y& ¬ Z.

1. Number of rows=2 3 +1=(3 variables+column header row)=9.

2. Number of columns = 3 logical variables + 3 logical operations = 6.

3. Let us indicate the order of actions: 3 2 1

X v Y& ¬ Z

4-5.Buildm table and fill it in columns:

			¬ Z	Y& ¬ Z	X v Y& ¬ Z
0	0	0			0
0	0	1			0

6. Answer:
F =0, at X= Y= Z= 0; at X= Y=0 and Z= 1.

Exercise 8

Construct truth tables for the following logical expressions:

1. F =(Av B )&( ¬ A& ¬ B).

2. F = X& ¬ Y v Z.

Test yourself (standard answers)

Note!

To avoid errors, it is recommended to list sets of input variables as follows:

A) divide the column of values of the first variable in half and fill the upper part of the column with zeros and the lower part with ones;

B) divide the column of values of the second variable into four parts and fill each quarter with alternating groups of zeros and ones, starting with a group of zeros;

C) continue dividing the columns of values of subsequent variables by 8, 16, etc. parts and filling them with groups of zeros or ones until the groups of zeros and ones consist of a single character.

Tautology - identically true formula true " ("1

Contradiction - identically false formula , or a formula taking the value " lie " ("0 ") for any values of the variables included in it.

Equivalent formulas - two formulas A And IN taking the same values, with the same sets of values of the variables included in them.The equivalence of two logical algebra formulas is denoted by the symbol.

Computer science: personal computer hardware Yashin Vladimir Nikolaevich

4.3. Logic 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.

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 allowances 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

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.

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.

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.

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.

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).

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.

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.

(A v B )&( ¬ A v¬ B)

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.

Construction of truth tables and logical functions

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.

Order of logical operations in a complex logical expression:

1. inversion;

2. conjunction;

3. disjunction;

4. implication;

5. equivalence.

Parentheses are used to change the specified order of operations.

Algorithm for constructing truth tables for complex expressions :

number of lines = 2 n + line for title ,

n is the number of simple statements.

number of columns = number of variables + number of logical operations ;

· determine the number of variables (simple expressions);

· determine the number of logical operations and the sequence of their execution.

3. Fill in the columns with the results of performing logical operations in the designated sequence, taking into account the truth tables of basic logical operations.

Example: Create a truth table for a logical expression:

D= A & (BVC)

Solution:

1. Determine the number of lines:

There are three simple statements at the input: A, B, C, therefore n = 3 and the number of lines = 23 +1 = 9.

2. Determine the number of columns:

simple expressions (variables): A, B, C;

intermediate results (logical operations):

A- inversion (denoted by E);

BVC- disjunction operation (denoted by F);

as well as the desired final value of the arithmetic expression:

D= A & (BVC) . i.e. D = E & F is a conjunction operation.

Fill in the columns taking into account the truth tables of logical operations.

font-size:12.0pt">Construction of a logical function using its truth table:

Let's try to solve the inverse problem. Let a truth table be given for some logical function Z (X,Y):

font-size:12.0pt">1 .

Since there are two lines, we get the disjunction of two elements: () V () .

We write each logical element in this disjunction as a conjunction of function arguments X and Y: ( X & Y) V ( X & Y).