Construction of truth tables for complex statements.
Boolean priority
1) inversion 2) conjunction 3) disjunction 4) implication and equivalence
How to make a truth table?
By definition, the truth table of a logical formula expresses the correspondence between various sets of variable values and the values of a 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 values of variables (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, and so on.
A convenient form of notation for finding the values of a formula is a table containing, 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% ">
The table shows that for all sets of values of the variables x and y, the formula takes the value 1, that is, is identically true.
2. Truth table for formula 96% "style =" width: 96.0% ">
The table shows that for all sets of values of the variables x and y, the formula takes the value 0, that is, is identically false .
3. Truth table for formula 96% "style =" width: 96.0% ">
The table shows that formula 0 "style =" border-collapse: collapse; border: none ">
Conclusion: we got all units in the last column. This means that the meaning of a complex statement is true for any values of simple statements K and C. Therefore, the teacher reasoned logically correctly.
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
- 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 a 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 take another look at our example from the last lesson.
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.
Good. Farther?
We build a table with the specified number of rows and columns, designate the columns and enter into the table the 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 brackets 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 first perform the disjunction and then the 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 inversion 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 there be in the table? 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
- С - 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).
Building 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 judgments 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.
The order of execution of logical operations in a complex boolean 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 rows = 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 indicated sequence, taking into account the truth tables of the main logical operations.
Example: Create a truth table for a logical expression:
D= А & (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 (denote by E);
BVC is the disjunction operation (we denote by F);
as well as the desired final value of the arithmetic expression:
D= А & (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 "> Building a logical function from 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 a disjunction of two elements: () V () .
We write each logical element in this disjunction as a conjunction of the function arguments X and Y: ( X & Y) V ( X & Y).
Page 1
Informatics lesson on "Foundations of logic, truth tables"
Theme: Howbuild a truth table?
Duration of the lesson: 40 minutesLesson type: combined:
knowledge testing - oral work;
new material - lecture;
consolidation - practical exercises;
knowledge test - tasks 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
Teach to find the meaning of logical expressions by building truth tables
Developing:
Develop logical thinking
Develop attention
Develop memory
Develop students' speech
Educational:
Develop 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);
tasks 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 affirmed or denied, which can 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 everyday life, and 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; C - 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 incoming 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 table columns in accordance with the sequence of logical operations, taking into account parentheses and priorities (¬, &, V);
Fill columns of input variables with sets of values
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
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 recorded on the left side of the table, and the corresponding values of the logical function are recorded 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 simple expressions included in it.
Definition 3
Equivalent logical expressions are called, the last columns of the truth tables of which are the same. Equivalence is indicated by the $ "=" $ sign.
When compiling a truth table, it is important to consider the following order of performing logical operations:
Picture 1.
Parentheses take precedence in the order of execution of operations.
Algorithm for constructing the truth table of a logical function
Determine the number of lines: number of lines= $ 2 ^ n + 1 $ (for title bar), $ n $ is the number of simple expressions. For example, for functions of two variables there are $ 2 ^ 2 = 4 $ combinations of sets of values of variables, for functions of three variables - $ 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.
Populate columns with the results of logical operations in a certain sequence, taking into account the truth tables of the main logical operations.
Figure 2.
Example 1
Create a truth table for the logical expression $ D = \ bar (A) \ vee (B \ vee C) $.
Solution:
- inversion ($ \ 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 determine the number of lines:
number of lines = $ 2 ^ 3 + 1 = 9 $.
The number of variables is $ 3 $.
Let's fill in the table, taking into account the truth tables of logical operations.
Figure 3.
Example 2
For this logical expression, build a truth table:
Solution:
- negation ($ \ bar (C) $);
- disjunction, because it is in parentheses ($ A \ vee B $);
- conjunction ($ (A \ vee B) \ bigwedge \ overline (C) $);
- negation, which we denote $ 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 required logical function ($ \ overline ((A \ vee B) \ bigwedge \ overline (C)) \ vee \ overline ((A \ vee C) \ bigwedge B) $).
Let's determine the number of lines:
The number of simple expressions is $ n = 3 $, so
number of lines = $2^3 + 1=9$.
Let's determine the number of columns:
The number of variables is $ 3 $.
The number of logical operations and their sequence:
