☰ Contents · Computing

Building truth tables

Lessons 3 · 1 lessons · M. R. Fayziyeva, D. M. Sayfurov, N. S. Xaytullayeva. Informatics and Information Technologies, Grade 9. “Nashriyot uyi Tasvir”, Tashkent, 2020
3

Building truth tables of logical expressions

Textbook: pp. 10–12
GoalBuilds the truth table of a logical expression step by step: finds the number of variables and operations and the number of columns and rows.
New words
truth table: a table listing the value of an expression for every combination of its variables · rostlik jadvalilogical formula: statements joined by logical connectives in a fixed order · mantiqiy formulaalgebra of statements: the set of statements together with the operations ∧, ∨, ¬, =>, <=> · mulohazalar algebrasi2ⁿ rows: a table of an expression with n variables has 2ⁿ rows · 2ⁿ qator
Explanation

A truth table shows the value of an expression for every possible combination of its variables. The procedure: 1) find the number of variables n; 2) count the operations k; 3) fix the order of operations from the brackets and priorities; 4) the number of columns is c = n + k; 5) write the variables and each operation in the header row; 6) the number of rows is r = 2ⁿ (not counting the header); 7) write the values of the variables as binary numbers in increasing order (00, 01, 10, 11…); 8) fill the columns from left to right. Each variable has two values, so n variables give 2·2·…·2 = 2ⁿ combinations: 4 rows for two, 8 for three, 16 for four. The last column gives the value of the whole expression.

Worked examples
For A ∧ ¬B: n = 2, k = 2 (¬ and ∧), so there are 4 columns: A, B, ¬B, A ∧ ¬B; and 4 rows. (A,B) = 00: ¬B = 1, result 0; 01: ¬B = 0, result 0; 10: ¬B = 1, result 1; 11: ¬B = 0, result 0. Last column: 0, 0, 1, 0.
In (A ∨ B) => C we have n = 3, k = 2, so 5 columns and 8 rows. For (A,B,C) = 000, 001, 010, 011, 100, 101, 110, 111 the column A ∨ B is 0, 0, 1, 1, 1, 1, 1, 1 and the result is 1, 1, 0, 1, 0, 1, 0, 1.
Class activity

“Table masters”: each group gets an expression on the board, first writes the number of columns and rows, then fills in the table. The first group to finish without mistakes wins.

Practice
1
How many columns and rows does the table of ¬A ∨ B ∧ C have?
2
Build the table of ¬A ∨ B for (A,B) = 00, 01, 10, 11 and compare it with the results of A => B.
3
Write the last column of A ∧ (A ∨ B) for (A,B) = 00, 01, 10, 11.
4
Why does the table of an expression with four variables have exactly 16 rows?