G2.4.2 Prove or Refute

EasyImplementIcarus · browser samples / server checksReview the topic

Decide for seven equations whether they hold on every input row, and give a counterexample row for each one that does not.

Hardware context: The enable signal of a press interlock, and seven rewrites found in a design review of control logic. Prove or refute seven equations, one of them a dual, and give a counterexample for each false one.

A design review found seven rewrites in a block of control logic. Each one replaced an expression with another that was meant to be equal. Some of the rewrites are laws. Some only look like laws.

This is an Implement problem with no logic in it. For each equation, write TRUE as 1 if the two sides are equal on every input row, and 0 if not. For each false equation, write ROW: one input row abc where the sides differ.

Equation 0 is worked in the specification as an example. Prove or refute equations 1 to 7 by a truth table, by the laws of the lesson, or by duality. Equations 3 and 4 use XOR: solve them by truth table.

Signals in the Timeline

SignalWidthRole
item8input of each check
Full specification
EquationLeft sideRight side
0a + aba + b
1ab + a'c + bcab + a'c
2a + bc(a + b)(a + c)
3a ^ bc(a ^ b)(a ^ c)
4a(b ^ c)ab ^ ac
5(ab)'a'b'
6ab + a'b' + bcab + a'b'
7(a + b)(a' + c)(b + c)(a + b)(a' + c)

ab is AND, a + b is OR, a' is NOT and ^ is XOR. NOT binds first, then AND, then XOR, then OR.

ConstantWhat to write
TRUE0 to TRUE71 when the two sides are equal on all eight rows. 0 when some row gives two different values.
ROW0 to ROW7Three bits abc: a row where the sides differ. Any such row is right. It is ignored when TRUE is 1.

A worked example. Equation 0 is false: for abc = 010 the left side is 0 and the right side is 1. So TRUE0 = 0 and ROW0 = 010. The row 011 would also be right.

Examples

Example 1

No Value May Stay Unknown
Input
all sixteen constants
Output
no_unknown_values = yes

The starter holds x in every constant. Each verdict must become 0 or 1, and each row three known bits.

Example 2

Equation 0 Is False
Input
a + ab = a + b
Output
holds = 0

For abc = 010, a + ab is 0 and a + b is 1. One such row refutes the equation, so TRUE0 is 0.

Example 3

Equation 0: The Row Must Show the Difference
Input
a + ab = a + b, at your row
Output
sides_differ_or_true = yes

The check evaluates both sides at your row. Here the row is 010, and the two sides differ there.

Constraints and Contract

  • Keep the module name answer and its sixteen outputs.
  • Each TRUE constant is one bit. Each ROW constant is three bits in the order a b c.

Hints

Hint 1

A truth table with eight rows settles each equation. Write both columns and compare them.

Hint 2

One row where the two sides differ is enough to refute an equation. Agreement on a few rows proves nothing.

Hint 3

Consensus needs two terms that hold one variable plain in one term and inverted in the other, and agree on the rest.

What the grader checks: The check compares each verdict with a truth table computed in JavaScript. It evaluates both sides of each equation at the row you give, and accepts any row where they differ. It tests your proofs, not a circuit.

17 checks on Icarus · browser samples / server checks. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain public samples only. A passing result establishes the tested cases, not a proof for all possible inputs.

See all 2 steps and the final capstone

Report a problem with this page

Your code SystemVerilogSaved locally
Ln 1, Col 1Tab indents · Ctrl/⌘ + Enter runs samples
Not run yet

No Value May Stay Unknown

Input
all sixteen constants
Expected output
no_unknown_values = yes

The starter holds x in every constant. Each verdict must become 0 or 1, and each row three known bits.

Run samples executes all 3 public checks. Check all tests runs 17 checks on the server.

Icarus · browser samples / server checks