VLSI DV Interview Puzzles · All levels

Three-Variable Implication Chain

How many legal tuples exist, and what is P(c==1)? Explain why c can still be 1 when b==0.

Puzzle

Difficulty: Hard · Puzzle 4 of 6 · Topic: Constraint Solving Order Puzzles

How many legal tuples exist, and what is P(c==1)? Explain why c can still be 1 when b==0.

Code

systemverilog

class chain_imp;
  rand bit a;
  rand bit b;
  rand bit c;
  constraint rel {
    (a == 1) -> (b == 1);
    (b == 1) -> (c == 1);
  }
endclass

Hint

Split on b first; implication only constrains when antecedent is true.

Step-by-step solution

diagram

1) If b=0: second implication imposes no requirement on c; first implication forces a=0. Tuples: (0,0,0),(0,0,1).
2) If b=1: second implication forces c=1; first implication allows a=0 or 1. Tuples: (0,1,1),(1,1,1).
3) Total legal tuples=4.
4) c==1 appears in 3 tuples -> P(c==1)=3/4.

Answer

Answer: There are 4 legal tuples and P(c==1)=3/4 (75%).

Why candidates get it wrong

A common wrong claim is that b==0 implies c==0; implication does not force the consequent when antecedent is false.

Interviewer follow-up

Add one constraint that makes P(c==1)=1/2 without changing legality too much.

Navigate