Practice question · Put in order
Order the steps of the foolproof procedure for deciding whether two boolean expressions are equivalent.
- Evaluate the second expression on the same rows and record its output column
- Evaluate the first expression on each row and record its output column
- List every combination of the input variables, giving 2 to the power n rows
- Declare the expressions equivalent only if the columns agree on every single row
- Compare the two output columns row by row
Hints
- Both expressions have to be evaluated over the same set of rows before any comparison is possible.
- The verdict is the last step, and it depends on all rows, not on finding one row that agrees.
Show the answer
- List every combination of the input variables, giving 2 to the power n rows
- Evaluate the first expression on each row and record its output column
- Evaluate the second expression on the same rows and record its output column
- Compare the two output columns row by row
- Declare the expressions equivalent only if the columns agree on every single row
Why
The input rows must be fixed first, or the two columns are not comparable. Agreement on every row is required: a single differing row is enough to prove non-equivalence, whereas agreement on some rows proves nothing. This exhaustive check is why the truth table is called the complete specification of a function.
Practise Truth Tables and Logical Equivalence
The app has 6 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Truth Tables and Logical Equivalence
- A synthesis tool replaces a designer's carefully written expression with a completely different gate…
- Two boolean expressions with identical truth tables are interchangeable in a circuit, so the choice between…
- Consider the three-input function (A AND B) OR (NOT C). Evaluate it on each row below and select every row…