Logical expressions. Each compound statement can be expressed as a formula (logical expression), which includes boolean variables, denoting statements, and logical operation signs, denoting logical functions.
To write a compound statement in the form of a logical expression in a formal language (the language of logic algebra) in a compound statement, you need to select 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 ≠ 4)". Let's analyze a compound statement. It contains two simple statements:
A ="2 2 = 5" - false (0),
В = «2 2 = 4 >> - true (1).
Then a compound statement can be written in the following form:
"(A or V) and (⌐A or (⌐ V)".
Now you need to write a 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 determined: inversion, conjunction, disjunction. Brackets can be used to change the specified order:
F = (A v V) & (⌐ A v ⌐ V).
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.
Let us substitute the values of the logical variables into the logical expression and, using the truth tables of the basic logical operations, we obtain the value of the logical function:
F = (AvB)&(⌐ Av⌐ B) = (0v1) & (1v0) = 1 & 1 = 1 .
Truth tables. For each compound statement (logical expression), you can build a truth table that determines its truth or falsity for all possible combinations of the initial values of simple statements (logical variables).
When constructing truth tables, it is advisable to be guided by a certain sequence of actions.
First, you need to determine the number of rows in the truth table. It is equal to the number of possible combinations of values of logical variables included in a logical expression. If the number of boolean variables is n, then:
number of lines = 2 n.
In our case, the logical function F = (AvB)&(⌐ Av⌐ B) has 2 variables and therefore the number of rows in the truth table should be 4.
Second, it is necessary to determine the number of columns in the truth table, which is equal to the number of boolean variables plus the number of boolean operations.
In our case, the number of variables is two, and the number of logical operations is five, that is, the number of columns of the truth table is seven.
Thirdly, it is necessary to build a truth table with the specified number of rows and columns, designate the columns and add possible sets of values of the initial logical variables to the table.
Fourth, it is necessary to fill in the truth table by columns, performing basic logical operations in the required sequence and in accordance with their truth tables (Table 4.4). Now we can determine the value of the boolean function for any set of boolean variable values.
Table 4.4. Logic function truth table
F=(AvB)&(⌐ Av⌐ B)
|
(AvB) & (⌐Av⌐B) |
||||||
Equivalent logical expressions. Boolean expressions in which the last columns of the truth tables match are called equivalent. The "=" sign is used to indicate equivalent logical expressions.
Let us prove that logical expressions ⌐А & ⌐В and ⌐(AvB) are equivalent. Let's first construct a truth table of a logical expression ⌐А & ⌐ В(Table 4.5).
Table 4.5. Boolean expression truth table ⌐A& ⌐B
|
⌐A&⌐ V |
||||
Now let's build the truth table of the logical expression ⌐(AvB) (Table 4.6).
Table 4.6. Boolean expression truth table ⌐(AvB)
|
⌐(AvB) |
|||
The values in the last columns of the truth tables are the same, therefore, logical expressions are equivalent:
⌐А & ⌐В = ⌐ (AvB).
Logic function is a function in which variables only take two values: logical unit or logical zero ... The truth or falsity of complex judgments is a function of the truth or falsity of simple ones. This function is called 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.
The order of performing logical operations in a complex logical expression:
1. inversion;
2. conjunction;
3. disjunction;
4. implication;
5. equivalence.
Brackets are used to change the specified order of operations.
For each compound statement (logical expression), you can build truth table, which determines its truth or falsity for all possible combinations of the initial values of simple statements (logical variables).
When constructing a truth table, it is advisable to be guided by a certain sequence of actions.
Algorithm for constructing truth tables for complex expressions:
number of lines = 2 n + line for header,
n- the number of simple statements.
number of columns = number of variables + number of logical operations;
o determine the number of variables (simple expressions);
o 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 indicated sequence, taking into account the truth tables of the main logical operations.
Example: Create a truth table for a logical expression:
D = A & (B C).
Solution:
1. Determine the number of lines:
there are three simple statements at the entrance: A, B, C so n = 3 and number of rows = 2 3 +1 = 9.
2. Determine the number of columns:
o simple expressions (variables): A, B, C ;
o intermediate results (logical operations):
o A - inversion (denote by E );
o B C is the disjunction operation (we denote by F );
o as well as the desired final value of the arithmetic expression:
o D = A & (B C) ... those. D = E & F is a conjunction operation.
3. Fill in the columns taking into account the truth tables of logical operations.
Create a logical function for a given truth table.
Rules for constructing a logical function according to its truth table:
1. Select in the truth table those rows in which the value of the function is 1 .
2. Write out 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. Each logical element in this disjunction is written as a conjunction of the function arguments.
4. If the value of any function argument in the corresponding row of the table is 0 , then this argument is taken with negation.
Solution.
1. In the first and third rows of the truth table, the value of the function is 1 .
2. Since there are two lines, we get disjunction two elements: () V () .
3. Each logical element in this disjunction is written in the form conjunctions function arguments X and Y : (X & Y) V (X & Y) .
4. We take an argument with negation if its value in the corresponding row of the table is 0 and we get the required function:
5. Z (X, Y) = (X & Y) V (X & Y) .
Example 4. Determine the participant in the crime based on two premises:
1) "If Ivanov did not participate or Petrov participated, then Sidorov participated";
2) 2) "If Ivanov did not participate, then Sidorov did not participate."
Solution
Let's compose expressions:
I- "Ivanov participated in the crime";
P- "Petrov participated in the crime";
S- "Sidorov took part in the crime."
Let's write the parcels in the form of formulas:
Let's check the result using the truth table:
Answer: Ivanov took part in the crime.
The number of input variables in the given expression is three (A, B, C)... Hence, the number of input sets Q = 2 3 = 8.
Truth table columns 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:
| A | B | C | B V C | ||
Page 1
Informatics lesson on "Foundations of logic, truth tables"
Topic: Howbuild a truth table?
Duration of the lesson: 40 minutesLesson type: combined:
knowledge testing - oral work;
new material - lecture;
consolidation - practical exercises;
knowledge test - assignments for independent work.
Educational:
Learn to compose logical expressions from statements
Introduce the concept of "truth table"
Examine the sequence of actions for constructing truth tables
To teach to find the meaning of logical expressions by building truth tables
Developing:
Develop logical thinking
Develop attention
Develop memory
Develop students' speech
Educational:
Cultivate the ability to listen to teachers and classmates
Educate the accuracy of keeping a notebook
Foster discipline
Organizational moment (2 min).
Repetition of the material from the previous lesson + checking homework (oral questioning) (5 min).
Explanation of the new material (10 min).
Physical education (1 min).
Anchoring
analysis of an example (5 min);
practical exercises (10 min);
assignments for independent work (5 min).
white board;
handout reference material "Truth tables";
demonstration of the presentation "Truth tables".
1. Organizational moment
Greetings.
Checking for those absent from the class.
Announcement of grades for the last lesson.
3 students work on cards:
Combine the correct definitions or notations:
|
1. Logic |
1. |
|
2. Utterance |
2. Logical addition |
|
3. Algebra of logic |
3. Science about the forms and ways of thinking |
|
4. Boolean variable |
4. Logical negation |
|
5. Disjunction |
5. TRUE and FALSE |
|
6. Inversion |
6.  |
|
7. Conjunction |
7.  |
|
8. Implication |
8. Science of operations on statements |
|
9. Equivalence |
9. A declarative sentence in which something is asserted or denied, which may be true or false |
The rest are oral.
1) Examples are written on the board:
For logical expressions, formulate compound statements in ordinary language:
B) (X = Y) and (X = Z). (Answer: numbersX, YandZare equal to each other)
2) Give examples of compound statements from school subjects and write them down using logical operations: literature, biology, geography, history.
What logical connectives did you use? ( Inversion, disjunction and conjunction)
We saw that logic is quite tightly connected with our daily life, and we also saw that almost any statement can be written in the form of a formula.
Let's remember the basic definitions and concepts:
3. Explanation of the new material
From a compound statement, make a formula by replacing simple statements with variables.
Task: Glass was broken in the classroom. The teacher explains to the director: Kolya or Sasha did it. But Sasha did not do this, because at that time he was passing me a test. Consequently, Kolya did it.
Solution: Let's formalize this complex statement:
K - Kolya did it; S - Sasha did it.
Expression form:
In the last lesson, we found the meaning of a compound statement by substituting the initial values of the incoming boolean variables. And today we learn that it is possible to build a truth table that determines the truth or falsity of a logical expression for all possible combinations of the initial values of simple statements (logical variables) and that it is possible to determine the values of the initial logical variables, knowing what kind of result we need.
So, the topic of today's lesson: "How to build a truth table?"
Have we used the concept of "truth table" for several lessons in a row? So what is truth table?
A truth table is a table, the truth of a complex statement for all possible values of the input variables.
Consider our example again.
and build a truth table for this compound statement
When constructing truth tables, there is a certain sequence of actions. Let's write down
It is necessary to determine the number of rows in the truth table.
number of lines = 2 n, where n is the number of logical variables
It is necessary to determine the number of columns in the truth table.
number of columns = number of boolean variables + number of boolean operations.
It is necessary to build a truth table with the specified number of rows and columns, enter the names of the columns of the table in accordance with the sequence of logical operations, taking into account the brackets and priorities (¬, &, V);
Fill input variable columns with value sets
Carry out filling of the truth table by columns, performing logical operations in accordance with the established sequence.
|
TO |
WITH |
 |
 |
 |
|
|
0 |
0 |
1 |
0 |
0 |
1 |
|
0 |
1 |
0 |
1 |
0 |
1 |
|
1 |
0 |
1 |
1 |
1 |
1 |
|
1 |
1 |
0 |
1 |
0 |
1 |
4. Physical education
Anchoring
parsing an example.
practical exercises.
assignments for independent work.
A) 
|
A |
V |
 |
 |
|
0 |
0 |
0 |
1 |
|
0 |
1 |
0 |
0 |
|
1 |
0 |
0 |
0 |
|
1 |
1 |
1 |
0 |
B) 
|
A |
V |
 |
 |
|
|
0 |
0 |
1 |
0 |
1 |
|
0 |
1 |
0 |
1 |
0 |
|
1 |
0 |
1 |
1 |
1 |
|
1 |
1 |
0 |
1 |
0 |
V) 
|
A |
V |
WITH |
|
 |
|
|
0 |
0 |
0 |
1 |
0 |
0 |
|
0 |
0 |
1 |
1 |
1 |
1 |
|
0 |
1 |
0 |
0 |
0 |
0 |
|
0 |
1 |
1 |
0 |
0 |
0 |
|
1 |
0 |
0 |
1 |
0 |
1 |
|
1 |
0 |
1 |
1 |
1 |
1 |
|
1 |
1 |
0 |
0 |
0 |
1 |
|
1 |
1 |
1 |
0 |
0 |
1 |
Assignment for independent work "Who is faster?"
Prepared cards for students, in which it is necessary to fill in the truth table by columns, performing logical operations in accordance with the established sequence.
|
A |
V |
WITH |
|
|||
Answer:
|
A |
V |
WITH |
|
|
 |
 |
|
0 |
0 |
0 |
1 |
0 |
1 |
0 |
|
0 |
0 |
1 |
0 |
0 |
0 |
1 |
|
0 |
1 |
0 |
1 |
0 |
1 |
0 |
|
0 |
1 |
1 |
0 |
0 |
0 |
1 |
|
1 |
0 |
0 |
1 |
0 |
1 |
0 |
|
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
1 |
1 |
0 |
1 |
1 |
1 |
0 |
|
1 |
1 |
1 |
0 |
1 |
1 |
0 |
Summarizing the lesson, homework (2 min).
D / Z is not set, since the lesson is paired, the children come through the lesson and continue to study the topic "Fundamentals of logic and logical foundations of a computer."
Page 1
We learn to compose logical expressions from statements, define the concept of "truth table", study the sequence of actions for constructing truth tables, learn to find the value of logical expressions by building truth tables.
Lesson objectives:
- Educational:
- Learn to compose logical expressions from statements
- Introduce the concept of "truth table"
- Examine the sequence of actions for constructing truth tables
- To teach to find the meaning of logical expressions by building truth tables
- Introduce the concept of equivalence of logical expressions
- Teach to prove the equivalence of logical expressions using truth tables
- Strengthen the skills of finding the values of logical expressions by building truth tables
- Developing:
- Develop logical thinking
- Develop attention
- Develop memory
- Develop students' speech
- Educational:
- Cultivate the ability to listen to teachers and classmates
- Educate the accuracy of keeping a notebook
- Foster discipline
During the classes
Organizing time
Hello guys. We continue to study the basics of logic and the topic of our today's lesson "Composing logical expressions. Truth tables ". After studying this topic, you will learn how logical forms are made from statements, and determine their truth by compiling truth tables.
Homework check
Write down the solution to household problems on the board
Everyone else open notebooks, I'll go through, check how you did your homework
Let's repeat the logical operations one more time
In what case will the compound statement be true as a result of the operation of logical multiplication?
A compound statement formed as a result of the operation of logical multiplication is true if and only if all simple statements included in it are true.
When will a compound statement be false as a result of the logical addition operation?
A compound statement formed as a result of a logical addition operation is false when all simple statements included in it are false.
How does inversion affect a statement?
Inversion makes a true statement false and, conversely, false - true.
What can you say about implication?
Logical following (implication) is formed by combining two statements into one with the help of the turn of speech "if ... then ...".
Denoted A-> V
A compound statement formed by the operation of logical following (implication) is false if and only if a false conclusion follows from the true premise (the first statement) (the second statement).
What can you say about the logical operation of equivalence?
Logical equality (equivalence) is formed by combining two statements into one with the help of a turn of speech "... if and only if ...", "... if and only if ..."
A compound statement formed by a logical operation of equivalence is true if and only if both statements are either false or true at the same time.
Explanation of the new material
Okay, we have repeated the material we have covered, and now we are moving on to a new topic.
In the last lesson, we found the meaning of a compound statement by substituting the initial values of the incoming boolean variables. And today we learn that it is possible to build a truth table that determines the truth or falsity of a logical expression for all possible combinations of the initial values of simple statements (logical variables) and that it is possible to determine the values of the initial logical variables, knowing what kind of result we need.
Let's look at our example from the last lesson again.
and build a truth table for this compound statement
When constructing truth tables, there is a certain sequence of actions. Let's write down
- It is necessary to determine the number of rows in the truth table.
- number of lines = 2 n, where n is the number of logical variables
They wrote it down. Building a truth table
What do we do first?
Determine the number of columns in a table
How do we do it?
We count the number of variables. In our case, the logical function
contains 2 variables
Which?
A and B
How many rows will there be in the table?
The number of rows in the truth table must be 4.
What if there are 3 variables?
Number of rows = 2³ = 8
Right. What do we do next?
Determine the number of columns = the number of boolean variables plus the number of boolean operations.
How much will be in our case?
In our case, the number of variables is two, and the number of logical operations is five, that is, the number of columns of the truth table is seven.
Okay. Farther?
We build a 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 and fill in the truth table by columns.
Which operation will we perform first? Just consider parentheses and priorities
You can do a logical negation first, or find the value first in the first parenthesis, then the inverse and the value in the second parenthesis, then the value between those parentheses
┐Аv┐В |
(AvB) & (┐Av┐B) |
|||||
Now we can determine the value of a boolean function for any set of boolean variables
Now we write down the item "Equivalent logical expressions".
Boolean expressions in which the last columns of the truth tables match are called equivalent. The sign “=“ is used to denote equivalent logical expressions,
Let us prove that the logical expressions ┐ А & ┐В and AvB are equivalent. Let's first construct the truth table of the logical expression
How many columns will there be in the table? 5
Which operation will we perform first? Inversion A, inversion B
┐А & ┐В |
||||
Now let's build the truth table of the logical expression AvB
How many rows will there be in the table? 4
How many columns will there be in the table? 4
We all understand that if we need to find the negation for the whole expression, then the priority, in our case, belongs to the disjunction. Therefore, we perform disjunction first and then inversion. In addition, we can rewrite our boolean expression AvB. Because we need to find the negation of the whole expression, and not individual variables, then the inverse can be taken outside the brackets ┐ (AvB), and we know that first we find the value in brackets
┐ (AvB) |
|||
Have built tables. Now let's compare the values in the last columns of the truth tables, since it is the last columns that are the resulting ones. They coincide, therefore, logical expressions are equivalent and we can put the “=” sign between them
Solving problems
1.
How many variables does this formula contain? 3
How many rows and columns will the table have? 8 and 8
What will be the sequence of operations in our example? (inversion, bracketed operations, bracketed operation)
Bv┐B (1) |
(1) => ┐C |
Av (Bv┐B => ┐C) |
|||||
2. Prove with the help of truth tables the equivalence of the following logical expressions:
(A → B) AND (Av┐B)
What conclusion do we draw? These boolean expressions are not equivalent
Homework
Prove using truth tables that logical expressions
┐A v ┐B and A & B are equivalent
Explanation of the new material (continued)
We have been using the concept of "truth table" for several lessons in a row, and what is truth table, how do you think?
A truth table is a table that establishes a correspondence between the possible sets of values of logical variables and the values of functions.
How did you do your homework, what was your conclusion?
Expressions are equivalent
Remember, in the previous lesson we made a formula from a compound statement, replacing simple statements 2 * 2 = 4 and 2 * 2 = 5 with variables A and B
Now let's learn to make logical expressions from statements.
Write down the assignment
Write it in the form of a logical formula of the statement:
1) If Ivanov is healthy and rich, then he is healthy
We analyze the statement. Revealing simple statements
A - Ivanov is healthy
B - Ivanov is rich
Okay, so what will the formula look like then? Just do not forget, so that the meaning of the statement is not lost, place parentheses in the formula
2) A number is prime if it is divisible only by 1 and by itself
A - the number is divisible only by 1
B - the number is divisible only by itself
C - the number is prime
3) If a number is divisible by 4, it is divisible by 2
A - divisible by 4
B - divisible by 2
4) An arbitrary number is either divisible by 2 or divisible by 3
A - divisible by 2
B - divisible by 3
5) An athlete is subject to disqualification if he behaves incorrectly in relation to an opponent or a referee, and if he took "doping".
A - the athlete is subject to disqualification
B - behaves incorrectly towards the opponent
С - behaves incorrectly towards the judge
D - took "doping".
Solving problems
1. Build a truth table for a formula
((p & q) → (p → r)) v p
Explaining how many rows and columns will there be in the table? (8 & 7) What will be the sequence of operations and why?
(p & q) → (p → r) |
((p & q) → (p → r)) v p |
|||||
We looked at the last column and concluded that for any set of input parameters, the formula takes on a true value, such a formula is called a tautology. Let's write the definition:
A formula is called a law of logic, or a tautology, if it takes the same value “true” for any set of values of the variables included in this formula.
And if all values are false, what do you think about such a formula?
We can say that the formula is not feasible
2. Write in the form of a logical formula of the statement:
The seaport administration issued the following order:
- If the captain of the ship receives a special instruction, then he must leave the port in his ship.
- If the captain does not receive special instructions, then he should not leave the port, or he will henceforth be deprived of admission to this port.
- The captain is either denied access to this port, or does not receive special instructions
We identify simple statements, draw up formulas
- A - the captain receives a special instruction
- B - leaves the port
- C - is deprived of admission to the port
- ┐А → (┐В v С)
- С v ┐А
3. Write down the compound statement “(2 * 2 = 4 and 3 * 3 = 9) or (2 * 2 ≠ 4 and 3 * 3 ≠ 9)” in the form of a logical expression. Build a truth table.
A = (2 * 2 = 4) B = (3 * 3 = 9)
(A & B) v (┐A & ┐B)
┐А & ┐В |
(A & B) v (┐A & ┐B) |
|||||
Homework
Choose a compound statement that has the same truth table as not (not A and not (B and C)).
- A&V or CIA;
- (A or B) and (A or C);
- A and (B or C);
- A or (not B or not C).
