Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.2k answers


531 users

0 votes
Hello, Could you please give any tips helpful to approach this question?
Assuming Peter and Paul develope a circuit. Paul tries to convince Peter that f may be replaced by f' to save hardware ressources.
f = !x0 & !x1 & !x2 | x3 & (x1 | x2) | x0 & !x2 & !x3
f' = !x0 & !x1 | x3

Show that f and f' are not equivalent. Try finding a counterexample for the equivalence of both formulas. You may use the Online Training Tools.

A counterexample is the (partial) variable assignment for which the two formulas differ. Give your counterexample as a conjunction of literals (a literal is either a variable or its negation).

Hint: A possible solution might look like this: !x0 & x1 & !x2 & x3 
Best Regards,
in # Study-Organisation (Bachelor) by (290 points)

1 Answer

0 votes
Well, I think the task is pretty clear, isn't it? You have to check whether the given formulas are equivalent or not. That can be done in many ways as discussed in the lecture, either by making truth tables for both formulas, using sequent calculus, transforming one formula to the other by means of Boolean algebra or converting both formulas to a canonical normal form to compare. Anyone of these methods can prove the equivalence or disprove it. In case the formulas are not equivalent, there is a counterexample, i.e., a model that satisfies one of the formulas, but not the other one. That model can be written down as an assignment to variables or as a cube as mentioned in the exercise text.
by (166k points)
Imprint | Privacy Policy