5
Practical lesson: logical operations
Textbook: p. 28
GoalPicks out statements, builds truth tables of compound expressions, checks that expressions are equal and solves logic puzzles.
New words
equivalent expressions: expressions that have the same value for every combination of inputs · teng kuchli ifodalarDe Morgan’s laws: ¬(A ∨ B) = ¬A ∧ ¬B and ¬(A ∧ B) = ¬A ∨ ¬B · De Morgan qonunlarialways-true expression: its truth table column contains only 1s · doim rost ifodaalways-false expression: its truth table column contains only 0s · doim yolg‘on ifoda
Explanation
In this practical lesson we apply logical operations on our own. When building a truth table of a compound expression, fill the columns step by step: negations first, then ∧, then ∨. If two expressions give the same value in every row, they are equivalent. Important equalities: ¬(¬A) = A; ¬(A ∨ B) = ¬A ∧ ¬B; ¬(A ∧ B) = ¬A ∨ ¬B. With them “OR” can be written using only ∧ and ¬: A ∨ B = ¬(¬A ∧ ¬B). A ∨ ¬A is always true, and A ∧ ¬A is always false. In logic puzzles, mark each sentence as a statement and test the two possibilities (true or false) in turn.
Worked examples
Compare ¬(A ∨ B) and ¬A ∧ ¬B. (A,B) = 11: 0 and 0; 10: 0 and 0; 01: 0 and 0; 00: 1 and 1. The columns match, so the expressions are equivalent.
Puzzle: Person A said, “At least one of the two of us is a liar” (a truth-teller always tells the truth, a liar always lies). If A were a liar, the sentence would be true – a contradiction. So A is a truth-teller, the sentence is true, and therefore B is a liar.
Class activity
“Table masters”: pairs build the tables for ¬(A ∧ B) and ¬A ∨ ¬B separately and compare them; the first pair with the right conclusion wins.
Practice
1
Build the truth table of ¬(A ∧ B) (rows 11, 10, 01, 00).
0, 1, 1, 1
2
With A = 1, B = 0 evaluate ¬(A ∨ B) and ¬A ∧ ¬B and compare.
Both are 0.
3
Write A ∨ B using only ∧ and ¬.
¬(¬A ∧ ¬B)
4
Why is A ∨ ¬A always true?
If A is true, the first part is true; if A is false, ¬A is true. In both cases the OR is true.